Closing the Last Log Factor: An Optimal Agnostic PAC Learner

Paper: 2608.06363 Authors: Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy Categories: cs.LG, cs.AI, cs.DS, math.ST

Note on sourcing: what follows is built from the abstract plus the surrounding literature (Hanneke; Aden-Ali–Cherapanamjeri–Shetty–Zhivotovskiy; Larsen; Zhivotovskiy–Hanneke). I have not read the full construction, so the “Core Mechanism” section describes the shape of the argument the result almost certainly has, not verbatim internals. Treat it as a well-informed reconstruction and check the paper before citing details.

The Gap

Binary classification, VC class H of dimension d, best achievable risk L* = min_h L(h). Two endpoints of this problem have been settled for years:

• Worst case (L** ~ 1/2): n = Theta((d + log(1/delta))/eps^2). Plain ERM gets this, and it is tight.
• Realizable (L** = 0): n = Theta((d + log(1/delta))/eps). This one took decades. ERM is *provably off by a log(1/eps) factor (Auer–Ortner). Hanneke (2016) gave the first optimal learner via a recursive majority-vote scheme; Aden-Ali, Cherapanamjeri, Shetty and Zhivotovskiy (2023) gave a cleaner one built on the one-inclusion graph and explicitly “without uniform convergence”; Larsen showed plain bagging of ERMs also does it.

Everything between those endpoints was open. The target shape has been known since Devroye, Györfi and Lugosi (1996), who proved the matching lower bound:

L(h) <= L* + sqrt( L*(d + log(1/delta)) / n ) + (d + log(1/delta)) / n

This is the “optimistic” or first-order rate: it degrades gracefully from the fast 1/n realizable regime to the slow 1/sqrt(n) agnostic regime as noise grows. The best upper bounds carried avoidable logs. Vapnik-style relative deviation bounds give ERM sqrt(L*(d log(n/d) + log(1/delta))/n) + (d log(n/d) + log(1/delta))/n — the log(n/d) is exactly the realizable-case defect leaking into the noisy regime. Localization arguments (Zhivotovskiy–Hanneke) shaved this partially. And since the L* = 0 slice of the bound is a statement ERM cannot satisfy, no sharper analysis of ERM would ever close it — you need a different algorithm.

[ Q: sample complexity of agnostic PAC at every noise level L* ? ]
                 |
      +----------+----------+
      |                     |
      v                     v
[ L* ~ 1/2: solved ]   [ L* = 0: solved 2016-2023 ]
[ ERM is optimal   ]   [ ERM provably lossy, need voting ]
      |                     |
      +----------+----------+
                 |
                 v
[ GAP: the whole interpolating curve. Upper bounds
  carry log(n/d); ERM cannot be patched by analysis ]
                 |
                 v
[ Assumption: the realizable-case machinery (subsample
  + aggregate) can be made noise-aware ]
                 |
                 v
[ Method: subsample at a size indexed by a guess of L*,
  vote, then select among the guesses ]
                 |
                 v
[ Evidence: theorem, one universal constant (7 * 10^8),
  every 0 < delta <= 1/2, matches DGL'96 lower bound ]
                 |
                 v
[ Conclusion: agnostic PAC sample complexity is settled
  up to universal constants at every fixed L* ]

The Increment

One sentence: Before, we knew the optimal sample complexity of agnostic PAC learning only at the two ends of the noise spectrum and had upper bounds with stray log factors in between; after, the entire curve is pinned down to a universal constant.

Core Mechanism

The result cannot come from a single estimator, so the construction is a pipeline. The first ingredient is a base learner that is optimal in expectation in the near-realizable regime. The one-inclusion graph predictor of Haussler, Littlestone and Warmuth is the canonical choice: given n points it has expected error at most d/n when the data is realizable, with no logs anywhere. Its weakness is confidence — it is good on average, and says nothing about tails.

The second ingredient converts average-case goodness into high-probability goodness without paying log(1/delta) multiplicatively against d. This is the subsample-and-vote trick from the realizable line of work: draw several subsamples of the training set, run the base learner on each, and take the pointwise majority. A majority vote errs at a point only if a constant fraction of the voters err there, so the failure probability is squeezed exponentially. This is why voting beats ERM: it is not about bias, it is about the tail of the error distribution. Uniform convergence over H is never invoked; the bound is about what this particular algorithm outputs.

The third ingredient is the genuinely agnostic part. The right subsample size depends on the noise level: in a near-realizable problem you want each voter trained on a small subsample (the fast 1/n regime rewards low variance in the aggregate), while at L* ~ 1/2 you want to use essentially all the data. Since L* is unknown, you run the whole voting machine at a geometric ladder of guesses k = 1, 2, 4, ... , n for L* n, producing a candidate h_k per rung, and then select among the candidates by empirical comparison on held-out data. The selection step must use a variance-sensitive (Bernstein / relative-deviation) comparison, because at small L* the differences you are trying to resolve are themselves of order L*, not of order 1. The union bound over O(log n) rungs is what the analysis has to absorb without letting a log n back into the final bound — presumably by charging the ladder against the confidence budget rather than against d. The stated constant 7 * 10^8 is the honest price of stacking these reductions.

   S : n i.i.d. points
     |
     +--------------------------- split ---------------------------+
     |                                                            |
  S_train                                                      S_select
     |                                                            |
     v                                                            |
  guesses of the noise scale: k = 1, 2, 4, ... , n                |
     |                                                            |
     +-- for each k: subsample size s(k)                          |
     |        |                                                   |
     |        +--> [sub_1] [sub_2] ... [sub_m]   (size s(k) each)  |
     |               |        |            |                      |
     |             [ A ]    [ A ]    ...  [ A ]  A = base learner  |
     |               |        |            |     (one-inclusion /  |
     |               +--------+-----+------+      ERM on subsample)|
     |                             |                               |
     |                             v                               |
     |                    [ pointwise MAJORITY ]  --> h_k          |
     |                                                            |
     v                                                            v
  candidates \{ h_1, h_2, h_4, ... , h_n \} ---------> [ variance-aware
                                                        (Bernstein)
                                                        tournament ]
                                                             |
                                                             v
                                                          h-hat
                                                   (improper: a vote,
                                                    generally not in H)

The metaphor: astrophotography. You want a sharp image of a faint galaxy. The unknown L** is the sky brightness — how much noise the night is throwing at you. A single long exposure with auto settings is ERM: it uses all the light, and on a dark night it is blurred by exactly the artifacts you cannot analyze away. So instead you shoot many short frames (subsamples), each individually noisy but unbiased, and stack them (majority vote). Stacking does not make any single frame better; it cancels the per-frame randomness, which is precisely the tail control that turns an in-expectation guarantee into a high-probability one. The exposure length per frame is the subsample size, and the correct exposure depends on the sky brightness you do not know: dark sky wants many short frames, bright sky wants long ones. So you bracket — shoot a ladder of exposure settings, stack each — and then judge the stacked results against a resolution chart (the held-out selection set), keeping the sharpest. The chart has to be read with a magnifier calibrated to how faint the target is: that magnifier is the Bernstein-style comparison, which resolves differences of size L* instead of differences of size 1. The final print is a composite of many frames, not one photograph — which is exactly why the learner is improper.

Key Concepts

• First-order (optimistic) rates: Why should L** appear inside the square root? Think about a coin. To estimate a bias p you need roughly p(1-p)/eps^2 flips, because the variance of a Bernoulli is p(1-p), not 1/4. A rare event is cheap to measure in absolute terms. Classification inherits this: the excess risk of a candidate is a sum of per-point disagreements whose variance is controlled by how often anyone errs at all, i.e. by L*. When L* = 0 the variance vanishes and you get the 1/n regime; when L* = 1/2 variance is maximal and you get 1/sqrt(n). The bound sqrt(L* d/n) + d/n is just the Bernstein trade-off written out, and it is the right shape at every noise level rather than only in the worst case.

• Why uniform convergence is the wrong instrument: The classical recipe is “make the empirical risk close to the true risk for *every h in H, then anything that minimizes the former nearly minimizes the latter.” The catch is that this proves too much. Concretely, there are classes and distributions where some legitimate ERM — a hypothesis with zero training error — has true error ~ d log(1/eps)/n, off by a log factor from optimal (Auer–Ortner). So the deficiency is in the learner, not the proof, and no amount of chaining or localization can rescue it. The modern move is to design an algorithm whose output you can control directly (a specific vote, a specific compression scheme) and analyze that object, giving up the generality of uniform convergence to gain a constant-factor-tight rate.

• Majority voting as tail suppression: Bagging is usually sold as variance reduction for unstable predictors. Here it does something sharper. Suppose each voter, trained on its own subsample, errs at a given test point with probability q over the draw. The majority errs at that point only if at least half the voters do, an event of probability roughly exp(-c**m) for q well below 1/2. Averaging over test points turns a d/n-in-expectation base learner into a (d + log(1/delta))/n-with-probability-1-delta learner — the log(1/delta) enters additively rather than multiplying d, which is precisely the difference between optimal and not.

Framework Shift

Before (mainstream approach):          After (this paper):

   S (all n points)                       S
        |                                 |
        v                        +--------+--------+
   [ single ERM ]                 |       |        |    subsample size
        |                        [A]     [A] ...  [A]   set by a GUESS
        v                         |       |        |    of the noise L*
   analysis tool:                 +---+---+---+----+
   sup over h in H                    |
   | L(h) - L_n(h) |             [ MAJORITY VOTE ] --> h_k, one per guess
        |                                |
        v                                v
   pays log(n/d) exactly           [ Bernstein tournament
   where L* is small                 picks the rung ]
                                         |
   proper, practical,                    v
   provably lossy                     h-hat : improper, expensive,
                                              provably optimal

From “one estimator, ever-sharper analysis” to “engineered estimator, elementary analysis”, the core shift is that the log factors were never in the proof — they were in the algorithm.

Expert Assessment

Problem choice: A real gap, and an old one. The target inequality has been sitting in Devroye–Györfi–Lugosi since 1996 as a lower bound with no matching upper bound, and the realizable slice of it consumed serious effort from 2016 to 2023. This paper is the natural terminus of that trajectory: having learned how to beat ERM at L** = 0, the field owed us the interpolation. Nobody manufactured this question — it is the last open cell in a table everyone teaches from. The flip side is that it is a closing result rather than an opening one: it terminates a line rather than starting one, and its value is largely conceptual bookkeeping. The sample complexity of agnostic PAC learning is now a solved problem, which is worth saying out loud.

Method maturity: Clever composition rather than a single new idea, and I mean that descriptively, not dismissively. Every ingredient — one-inclusion graph, subsample-and-vote, noise-level ladder, variance-aware selection — exists in the literature; the contribution is making them compose without any step leaking a log. That is where the real work is, and where the 7 ** 10^8 comes from. The constant is a legitimate red flag about how many reductions are stacked, and it strongly suggests the pipeline is not the “right” algorithm, merely an algorithm. Larsen’s result that plain bagging suffices in the realizable case makes me suspect a much simpler learner — bagged ERM with a subsample size chosen by validation — also achieves this, and that a future paper will prove it in three pages with a constant under 100. Two things I would want checked before believing the result is final in spirit: whether the learner must be improper (I expect yes, and if a proper learner provably cannot achieve this rate, that is a headline the abstract is not making), and what the computational cost is, since O(log n) rungs times m voters times a one-inclusion-graph call is not something you would run.

Experimental integrity: No experiments, and none are owed — this is a statement about a lower bound being matched, and the only “baselines” are prior theorems. The scrutiny to apply is different: is the bound uniform in n and delta (the abstract claims every 0 < delta <= 1/2, which is the right quantifier and rules out the common cheat of assuming delta is not too small); does it hold for all d >= 1 without hidden n >= poly(d) conditions; is the selection step charged honestly for the sample it consumes. The abstract’s phrasing is careful in exactly the places where such results usually hedge, which is a good sign. Constants of this size are unfalsifiable in practice, so the only real check is the proof.

Writing quality: The abstract does its job — states the inequality, names the lower bound it matches, quantifies the claim. The corner I would bet on being cut is the constant: papers with a 7 ** 10^8 almost always present it as an unavoidable artifact rather than budgeting it, and a short table showing which reduction contributes which factor would tell readers where the slack is and hand the next author a target. The section I would most want rewritten is the one comparing to prior art in the intermediate regime — readers need to see precisely which term in Zhivotovskiy–Hanneke or in the relative-deviation ERM bound was the obstruction, rather than a citation list. And a paragraph on properness and computation, even if the answers are “improper” and “polynomial but silly”, would preempt the two questions every reader will have.

Verdict: strong accept — it settles a thirty-year-old question with the correct quantifiers, and the ugly constant is a matter of taste rather than a defect in the claim.

Takeaways

Concrete things that transfer:

• Subsample-and-vote is a tail-control device, not just a variance reducer. If you have a procedure with a good guarantee *in expectation and you need a good guarantee with high probability, running it on independent subsamples and aggregating pointwise is often strictly better than boosting confidence by retraining and validating. The failure probability decays exponentially in the number of voters, and crucially the confidence term enters additively rather than multiplying the complexity term. This applies well outside classification — any median-of-means or majority-of-estimators construction.
• When the optimal hyperparameter depends on an unknown noise level, ladder it and select. The k = 1, 2, 4, ... sweep over guesses of L**, followed by variance-aware selection, is Lepski’s method in disguise, and it is the standard answer to adaptive bandwidth, adaptive regularization, and adaptive learning rate problems. The reusable detail is that the selection criterion must be calibrated to the scale you are trying to resolve: comparing candidates with a Hoeffding-type bound when the true differences are of order L* will wash out exactly the signal you need.
• If your bound has a log factor you cannot remove, check whether the algorithm is the problem. The Auer–Ortner lower bound for ERM is the archetype: years of effort went into sharper analyses of an estimator that simply could not achieve the target. Before improving a proof, ask whether there is a lower bound against the procedure itself.
• First-order bounds are the practically relevant ones. In any regime where your achievable error is genuinely small — most of modern practice — the sqrt(L** d/n) term dominates sqrt(d/n) by a factor of sqrt(L*), which is the difference between “need a million labels” and “need thirty thousand”. Reporting a worst-case 1/sqrt(n) rate for a low-noise problem is leaving most of the guarantee on the table.
• Not transferable: the algorithm itself. With a 7 ** 10^8 constant and a nested subsample/vote/tournament structure, this is an existence proof. Do not deploy it.