📊 statistics

An Optimal Agnostic PAC Algorithm

This paper presents an agnostic PAC learning algorithm for binary classification that achieves a statistically optimal risk bound, settling the sample complexity up to universal constants by matching established lower bounds.

Original authors: Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy

Published 2026-08-07

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to tell the difference between cats and dogs. You show it thousands of pictures, but the world is messy: sometimes the cat is hiding in the dark, sometimes the dog is wearing a hat, and sometimes the labels you give the robot are just plain wrong. This is the world of machine learning, specifically a field called statistical learning theory. The big question here is: how many examples does a robot need to see before it becomes good at guessing?

To answer this, scientists use a concept called VC dimension (named after Vapnik and Chervonenkis). Think of VC dimension as a measure of how "confusing" or "complex" the robot's brain is. A simple brain that only looks at ear shape has a low VC dimension; a super-complex brain that looks at every single pixel has a high one. The goal is to find a "sweet spot" where the robot learns fast enough to be useful but isn't so complex that it memorizes the training photos instead of learning the rules. For decades, mathematicians have been trying to find the perfect formula that tells us exactly how much "extra" error a robot will make compared to the absolute best possible robot, given a certain number of examples and a certain level of complexity.

For a long time, there was a gap in our knowledge. We knew the best possible speed for learning when the data was perfect (no mistakes in the labels), and we knew the speed when the data was very messy. But what about the middle ground? What if the data is just a little bit noisy? Previous attempts to solve this were like trying to run a race with a heavy backpack; they were close, but they carried extra "logarithmic" weight that made them slower than they needed to be. The big question was: Can we build a learner that runs at the absolute fastest possible speed, no matter how much noise is in the data, without carrying that extra weight?

This paper, titled "An Optimal Agnostic PAC Algorithm," answers that question with a resounding "yes." The authors, Markus Engelund Mathiasen, Jian Qian, and Nikita Zhivotovskiy, have constructed a specific learning algorithm that achieves the statistically optimal risk bound. In plain English, this means they found a way to train a classifier that makes the fewest possible mistakes, mathematically proving that no other method can beat them (up to some universal constants) for any fixed level of noise. They didn't just guess; they proved it.

Here is how they did it, using a story about a very organized library and a clever game of "one-inclusion."

The Problem: The Noisy Library

Imagine a massive library where every book is a picture, and every book has a label on the spine saying "Cat" or "Dog." However, the librarian is a bit clumsy. Sometimes they mislabel a book, or the book is damaged. You want to build a system that can look at a new, unlabeled book and guess its label correctly.

The "best possible" system (let's call it the Oracle) knows the true rules of the universe. Even the Oracle will make some mistakes because the librarian's labels are sometimes wrong. This minimum error rate is called $L^*$ . Your goal is to build a system that gets as close to the Oracle's performance as possible, using a limited number of books ( $n$ ) from the library.

The paper proves that their new system, let's call it The Optimizer, will have an error rate ( $L(\hat{h})$ ) that is bounded by:
$L(\hat{h}) \le L^* + 7 \cdot 10^8 \left( \sqrt{\frac{L^*(d + \log(1/\delta))}{n}} + \frac{d + \log(1/\delta)}{n} \right)$
Don't let the math scare you. The key part is the square root term. This formula says that the extra mistakes you make (the "excess risk") shrink as you get more books ( $n$ ), and it shrinks at the fastest possible speed allowed by the laws of probability. Previous methods had extra factors (like $\log(n)$ ) that slowed them down, but The Optimizer cuts those out.

The Secret Sauce: The Cube and the Orientation

How did they do it? They used a brilliant combination of two ideas: The One-Inclusion Graph and Suffix Averaging.

1. The One-Inclusion Graph (The Cube Game)
Imagine all possible ways the books in your sample could be labeled. If you have $n$ books, there are $2^n$ possible label combinations. You can visualize these combinations as the corners of a giant, multi-dimensional cube (a "Boolean cube").

Two corners are connected by an edge if they differ by exactly one book's label.
The "Oracle" (the best possible rule) lives somewhere in this cube.
The goal is to figure out which direction to point when you are at a corner, so you move closer to the Oracle.

The authors use a technique called orientation. Imagine you are standing on a corner of this cube. You need to decide which way to go. The paper introduces a new mathematical tool called Lemma 2.1, which is a "class-dependent edge isoperimetric inequality." In our library analogy, this is like a rule that says: "The number of paths you need to check to find the right direction depends on how far you are from the Oracle and how complex the library is."

They prove that you can assign a direction to every edge in this giant cube such that, no matter where you start, you never have to take more than a specific number of steps to get close to the best answer. This step is crucial because it turns a messy guessing game into a deterministic path.

2. Suffix Averaging (The Committee Vote)
Once they have this perfect orientation, they need to turn it into a real-world predictor. They use a trick called suffix averaging.
Imagine you are building a team of experts. You don't just ask one expert for an opinion. Instead, you ask a series of experts who have seen slightly different amounts of data.

Expert 1 has seen the first $k$ books.
Expert 2 has seen the first $k+1$ books.
...
Expert $m$ has seen the first $2k-1$ books.

The final prediction is the average of all these experts' opinions. This is powerful because it smooths out the randomness. If one expert gets unlucky with a noisy book, the others balance them out. The paper proves that this averaging process, combined with their perfect cube orientation, keeps the error rate low even when the data is noisy.

3. The Final Polish: Thresholding
The averaged result is a number between -1 and 1 (a "score"). To get a final "Cat" or "Dog" answer, they use a threshold. They test a few different cut-off points on a separate set of validation books to pick the one that works best. This step ensures the final result is a simple, deterministic rule (a binary classifier) rather than a fuzzy probability.

Why This Matters

Before this paper, if you wanted the fastest possible learning rate, you had to choose between methods that worked well for perfect data and methods that worked well for messy data. You couldn't have the best of both worlds without paying a penalty.

This paper shows that you can have the best of both worlds. They constructed a learner that:

Doesn't need to know the noise level: It works without knowing how messy the data is ( $L^*$ ) or how confident you want to be ( $\delta$ ).
Is optimal: It matches the theoretical lower bound (the speed limit of learning) established by previous researchers like Devroye, Györfi, and Lugosi.
Is deterministic: It doesn't rely on luck; it gives the same answer every time you run it on the same data.

The authors explicitly rule out the idea that we need "polylogarithmic" factors (those extra slow-downs) to get optimal results in the agnostic (noisy) setting. They prove that those factors are unnecessary. They also show that while some previous methods (like simple majority votes) work well for perfect data, they fail to maintain the optimal speed when noise is introduced.

In short, this paper closes a long-standing chapter in the history of machine learning theory. It provides the "perfect" algorithm for binary classification in the real world, where data is never perfect. It's a bit like finding a map that guarantees you can reach the treasure in the minimum number of steps, no matter how many potholes are on the road. The authors didn't just suggest this was possible; they built the map and proved it works.

=== DRAFT ===

Technical Summary: An Optimal Agnostic PAC Algorithm

Problem Statement
The paper addresses the fundamental problem of determining sharp risk bounds in agnostic Probably Approximately Correct (PAC) learning for binary classification. Let $H \subseteq \{-1, +1\}^{\mathcal{X}}$ be a hypothesis class with VC dimension $d \geq 1$ . Given an i.i.d. sample $S$ of size $n$ from a distribution over $\mathcal{X} \times \{-1, +1\}$ , the goal is to construct a learner that outputs a classifier $\hat{h}$ such that its risk $L(\hat{h})$ is close to the optimal risk $L^* = \min_{h \in H} L(h)$ .

Historically, bounds in this setting have been derived via two distinct regimes:

Realizable Case ( $L^*=0$ ): Optimal rates of $O(d/n)$ are achieved using combinatorial arguments like the one-inclusion graph (Haussler, Littlestone, Warmuth) or specific aggregation schemes.
Agnostic Case ( $L^* > 0$ ): Classical empirical process methods (chaining, covering) yield optimal rates of $O(\sqrt{d/n})$ when $L^*$ is bounded away from zero.

The open question, established by lower bounds from Devroye, Györfi, and Lugosi, is whether a single algorithm can achieve the optimal rate across the entire spectrum of $L^*$ , specifically matching the bound:
$L(\hat{h}) \leq L^* + C \left( \sqrt{\frac{L^*(d + \log(1/\delta))}{n}} + \frac{d + \log(1/\delta)}{n} \right)$
Previous upper bounds either incurred suboptimal polylogarithmic factors in the fast rate term or required specific conditions on $L^*$ (e.g., $L^* \lesssim (d+\log(1/\delta))/n$ ) to achieve optimality.

Methodology
The authors construct a deterministic, generally improper learner that achieves the optimal bound without prior knowledge of $L^*$ or the confidence parameter $\delta$ . The methodology proceeds in three main stages:

Class-Dependent Edge Isoperimetry (Section 2):
The core theoretical innovation is Lemma 2.1, a class-dependent edge isoperimetric inequality on the Boolean cube. Unlike previous results that bound edge counts solely by VC dimension or distance to a trace, this lemma introduces weights $w_{v,p}$ that simultaneously satisfy:
- $w_{v,p} + w_{v \oplus p, p} = 1$ (partitioning edges).
- $\sum_{p \in D} w_{v,p} \leq \rho_F(v) + R_D(F)$ , where $\rho_F(v)$ is the Hamming distance to a trace $F$ and $R_D(F)$ is the unnormalized Rademacher width of the projection of $F$ onto coordinates $D$ .
This inequality allows for a localized bound on the number of induced edges $|E_U|$ in a subgraph, controlling them via both the distance to the optimal trace and the complexity of the projection.
Optimal Leave-One-Out Orientation (Section 2):
Using Hall's Marriage Theorem, the authors convert the isoperimetric inequality into a deterministic orientation $\sigma$ of the full Boolean cube. This orientation ensures that for any vertex $v$ , the out-degree is bounded by:
$\text{out}(v; \sigma) \leq \rho_F(v) + 120\sqrt{d \rho_F(v)} + 7202d$
This leads to a leave-one-out rule where the expected error is bounded by the optimal empirical risk plus a term scaling with $\sqrt{d L^*/n}$ and $d/n$ .
From Leave-One-Out to PAC Bounds (Section 3):
To convert the leave-one-out rule into a high-probability PAC guarantee, the authors employ a two-step derandomization and averaging process:
- Symmetrization and Suffix Averaging: The deterministic leave-one-out rule is symmetrized over permutations. A randomized predictor $\hat{p}$ is constructed by averaging these symmetrized scores over a suffix of the sample (indices $k$ to $2k-1$ ). This step utilizes reverse and forward martingale arguments (Lemmas 3.1 and 3.2) adapted from Aden-Ali et al. to control the variance and deviation of the excess risk, ensuring the bound holds uniformly in $L^*$ .
- Thresholding and ERM: The randomized predictor $\hat{p}$ (taking values in $[-1, 1]$ ) is converted into a deterministic binary classifier. This is achieved by considering a class of thresholded hypotheses $T_{\hat{p}} = \{ x \mapsto 2\mathbb{1}[\hat{p}(x) \geq u] - 1 \}$ . An empirical risk minimizer (ERM) is selected from this class using an independent validation sample. Crucially, the nested structure of the threshold class allows for a local entropy bound without incurring an additional logarithmic factor in the sample size, preserving the optimal coefficient on $L^*$ .

Key Contributions and Results
The paper proves Theorem 1, establishing the existence of a deterministic learner that, for any distribution, sample size $n$ , and confidence $\delta$ , outputs a classifier $\hat{h}$ satisfying:
$L(\hat{h}) \leq L^* + 2 \cdot 10^8 \left( \sqrt{\frac{L^*(d + \log(48/\delta))}{n}} + \frac{d + \log(48/\delta)}{n} \right)$
with probability at least $1-\delta$ . The final derivation in the proof of Theorem 1 yields a tighter constant of approximately $3.1 \cdot 10^7$ .

Optimality: This bound matches the lower bounds of Devroye, Györfi, and Lugosi up to universal constants. It is the first result to achieve the optimal rate for every fixed $L^*$ , bridging the gap between the realizable and fully agnostic regimes without suboptimal polylogarithmic factors.
Algorithmic Properties: The learner is deterministic, generally improper (outputting a classifier not necessarily in $H$ ), and does not require knowledge of $L^*$ or $\delta$ .
Technical Novelty: The proof relies on the new class-dependent edge isoperimetric inequality (Lemma 2.1), which controls induced edge counts through a combination of approximation errors and projected Rademacher widths, a technique distinct from previous combinatorial or pure empirical process approaches.

Significance
The paper claims to settle the sample complexity of agnostic PAC learning up to universal constants. By constructing an algorithm that attains the minimax excess risk bound for binary classification at every fixed $L^*$ , the authors resolve a long-standing open question regarding the existence of a single algorithm that is optimal across the entire spectrum of noise levels. The work demonstrates that the optimal rate is achievable without sacrificing the leading coefficient of the $L^*$ term, a feat previously thought difficult due to the tension between realizable and agnostic analysis techniques.

The Problem: The Noisy Library

The Secret Sauce: The Cube and the Orientation

Why This Matters

Technical Summary: An Optimal Agnostic PAC Algorithm

More like this