An Optimal Agnostic PAC Algorithm

The paper, by Markus Engelund Mathiasen, Jian Qian, and Nikita Zhivotovskiy, resolves the sample complexity of agnostic PAC classification up to universal constants at every fixed value of the Bayes risk within the class. The central claim is stated in the abstract:

"Let H ⊆ −1, +1 X be a class of finite VC dimension d ≥ 1. Writing L for the binary risk and L∗ = min h∈H L(h), we construct a learner achieving the statistically optimal risk bound: from an i.i.d. sample of size n, for every 0 L(ĥ) ≤ L∗ + 7 · 10 8 (sqrt(L∗(d + log(1/δ))/n) + (d + log(1/δ))/n)."

The main theorem proved in the body of the paper is Theorem 1:

"There is a deterministic, generally improper learner that uses neither L∗ nor δ and outputs a classifier ĥ: X → −1, +1 such that for every distribution, every n ≥ 1, and every 0 L(ĥ) ≤ L∗ + 2 · 10 8 (sqrt(L∗(d + log(48/δ))/n) + (d + log(48/δ))/n). (2)"

This is matched, up to universal constants, by the lower bound of Devroye, Györfi, and Lugosi, quoted in the introduction:

"There is a universal constant c > 0 such that, for every learner, including a randomized or improper learner, and every admissible choice of d, n, δ, and L∗ within the usual nontrivial boundaries, there are an instance space, a class H of VC dimension d, and a distribution satisfying min h∈H L(h) = L∗ for which, with probability at least δ,

L(ĥ) ≥ L∗ + c(sqrt(L∗(d + log(1/δ))/n) + (d + log(1/δ))/n). (1)"

Thus Theorem 1 determines, up to universal constants, the distribution-free high probability minimax excess risk bound for binary classification at every fixed L∗, interpolating between the realizable rate (when L∗ = 0) and the standard agnostic rate (when L∗ is bounded away from zero).

The introduction describes the two classical regimes. In the agnostic setting where L∗ is bounded away from zero, empirical risk minimization analyzed via empirical process methods gives the optimal d/n rate. In the realizable case, uniform convergence is insufficient; the seminal work of Haussler, Littlestone, and Warmuth used the one-inclusion graph and leave-one-out analysis to obtain the optimal expected rate, while the first optimal high-probability PAC bound was due to Hanneke, building on Simon, with later optimal constructions including bagging, aggregation of one-inclusion rules, and majority-of-three consistent classifiers.

The best previous upper bound in the agnostic case, due to Hanneke, Larsen, and Zhivotovskiy, had an extra polylogarithmic factor in the fast-rate term: the paper states it as

L(ĥ) ≤ L∗ + C(sqrt(L∗ log 5(n/d)(d + log(1/δ))/n) + (d + log(1/δ))/n),

which is suboptimal by the polylogarithmic factor in the fast rate term. By comparison, the ERM bound incurs a multiplicative log(1/L∗) factor in the VC part of the square root term and a log(n/d) factor in the VC part of the fast rate term. Other results achieved the optimal order only when L∗ is very small, namely when L∗ ≲ (d + log(1/δ))/n.

The paper's construction follows Long's idea of orienting the entire Boolean cube in the agnostic one-inclusion graph algorithm. The key novelty is Lemma 2.1, described in the introduction as a class dependent edge isoperimetric inequality that controls induced edge counts through approximation errors and projected Rademacher widths.

The setup: for a finite coordinate set P, the Boolean cube is G P = (V P, E P) with V P = −1,+1 P and edges v, v⊕p; for U ⊆ V P, E U denotes internal edges and D U(v) = p ∈ P: v⊕p ∈ U. For a fixed nonempty trace F ⊆ V P with VC(F) ≤ d, the Hamming distance to F is ρ F(v) = min f∈F DIS(v,f), and the projected Rademacher width is

R D(F) = E ε max f∈F Σ p∈D ε p f(p),

which satisfies R D(F) ≤ 60√(dD) via chaining and covering.

Lemma 2.1 states:

"There are weights w v,p ∈ [0, 1], fixed simultaneously for all v ∈ V P and p ∈ P with the following properties. The first relation below holds for every v ∈ V P and p ∈ P, and the second for every v ∈ V P and D ⊆ P:

w v,p + w v⊕p,p = 1, (5)

Σ p∈D w v,p ≤ ρ F(v) + R D(F). (6)

Consequently, for every U ⊆ V P, the induced subgraph satisfies the localized edge bound

E U ≤ Σ v∈U (ρ F(v) + R D U(v)(F)). (7)"

The proof is a random restriction argument: each coordinate is independently omitted with probability 1/2; for each subset T, π T(v) is the first member of F minimizing DIS(v,f) ∩ T; the weights are defined as w v,p = P T(p ∈ DIS(v, π T(v)) p ∉ T). The symmetry relation (5) holds because omitting p makes v and v⊕p conditionally identical. For (6), the paper encodes the omitted set by Rademacher signs ε p, uses the pointwise identity B ∩ D ∩ T c = B ∩ D ∩ T + Σ p∈D ε p 1 p ∈ B, and bounds the resulting maximum over F by the projected Rademacher width R D(F).

The remarks compare Lemma 2.1 with earlier results. Haussler–Littlestone–Warmuth only control U ⊆ F via E U ≤ VC(U)U ≤ dU. Long's cube orientation gives E U ≤ 15 Σ v∈U(d + ρ F(v)), but the coefficient 15 on ρ F(v) prevents a leave-one-out bound with coefficient one on the empirical optimum. Asilis et al. use the omitted-coordinate mechanism to get (5) but not (6) simultaneously for every D. Dughmi, Kalayci, and York prove the all-coordinate bound E U ≤ Σ v∈U ρ F(v) + (U/2) R P(F), using the single full width; Lemma 2.1 instead controls one assignment for every D ⊆ P, allowing the vertexwise choice D = D U(v).

Lemma 2.1 is converted into an orientation via Hall's theorem: if capacities c x satisfy E G(W) ≤ Σ x∈W c x for every W ⊆ V, then every edge can be assigned to an endpoint so that at most c x edges are assigned to x, giving an orientation with outdegree at most c x.

Theorem 2 states: for nonempty finite coordinate set P, d ≥ 1, and ∅ ≠ F ⊆ V P with VC(F) ≤ d, there is a deterministic orientation σ of the full cube such that

out(v; σ) ≤ ρ F(v) + 120√(dρ F(v)) + 7202d. (11)

Consequently, for every input sequence allowing repetitions, there is a deterministic, generally improper leave-one-out rule depending only on the unlabeled sequence such that for every label sequence,

L̂ S LOO ≤ L̂ S* + 120√(d L̂ S*/n) + 7202 d/n. (12)

The proof bounds E U by combining (6) with R D(F) ≤ 60√(dD), using the elementary inequality √(ab) ≤ (a+b)/2 to obtain ρ F(v) + 3601d + (900/3601) deg U(v), relabeling edge endpoints so the endpoint closer to F is first (using the 1-Lipschitz property ρ F(v) − ρ F(v⊕p) ≤ 1), and applying a delicate ratio estimate to show

Σ v∈U deg U(v)/√(ρ F(v)+3601d) < 4 Σ v∈U √(ρ F(v)+3601d).

Cauchy–Schwarz then yields Σ v √deg U(v) < 2 Σ v √(ρ F(v)+3601d), and hence the Hall capacity bound. The leave-one-out conclusion follows by applying the orientation to P = 1,...,n with the trace F = (h(x 1),...,h(x n)): h ∈ H; the prediction rule (Algorithm 1) fixes all coordinates except the held-out one, tests both completions, and predicts the coordinate of the edge head selected by σ. The prediction is wrong exactly when the true completion is the tail, so n L̂ S LOO = out(v y; σ), and ρ F(v y) = n L̂ S*.

Since the orientation need not be permutation invariant, the predictions are symmetrized: given a labeled sample S and unlabeled query x, one appends x, uniformly permutes the indexed points, and applies the leave-one-out rule while hiding the coordinate occupied by x. The resulting score q(x;S) ∈ [−1,1] is deterministic and symmetric. Averaging (12) over permutations gives, for every labeled sample S = ((x i,y i)) i=1 m,

(1/(2m)) Σ i=1 m q(x i; S−i) − y i ≤ L̂ S* + 120√(d L̂ S*/m) + 7202 d/m. (13)

The paper adapts the reverse and forward martingale proof of Aden-Ali, Cherapanamjeri, Shetty, and Zhivotovskiy from the realizable to the agnostic setting, retaining the comparator dependent variance needed for a bound uniform in L∗ and avoiding the logarithmic factor in Dughmi–Kalayci–York. The randomized learner is defined as follows: fix k ≥ 1, take Z i = (X i,Y i) for i = 1,...,2k i.i.d., set q t(x) = q(x; (Z 1,...,Z t)) for k ≤ t ≤ 2k−1, and average the scores over the suffix:

p̂(x) = (1/k) Σ t=k 2k−1 q t(x). (14)

The predictor predicts +1 with probability (1+p̂(x))/2; by linearity, L(p̂) = (1/k) Σ L(q t). The observation Z 2k is a fresh point used to analyze q 2k−1 and does not enter the learner.

Two lemmas control the excess risk. Lemma 3.1 (reverse martingale) fixes h ∈ H and defines Δ t+1,h = l(q t(X t+1),Y t+1) − 1 h(X t+1) ≠ Y t+1. It asserts that for every 0 max((1/k) Σ m=k+1 2k Δ m,h, 0) ≤ 8200(√(L(h)(d+log(1/δ))/k) + (d+log(1/δ))/k). (16)

The proof uses a random uniform permutation of the 2k observations and a reverse filtration exposing the permutation backward; the leave-one-out bound (13) controls the conditional means and second moments of the martingale differences, Bernstein's inequality controls the number of errors of h on the full sample, and Freedman's inequality is applied to the reverse martingale.

Lemma 3.2 (forward martingale) asserts that with probability at least 1 − δ,

(1/k) Σ t=k 2k−1(L(q t) − L(h)) ≤ max((1/k) Σ m=k+1 2k Δ m,h, 0) + 5√(L(h) log(1/δ)/k) + 10 log(1/δ)/k. (17)

Its proof observes that E[Δ t+1,h S≤t] = L(q t) − L(h), so ξ t+1,h = L(q t) − L(h) − Δ t+1,h is a martingale difference; a Bernstein moment-generating bound is iterated over t, and the parameter λ is chosen as min(1/2, √(log(1/δ)/(kL(h)))) when L(h) > 0 and λ = 1/2 when L(h) = 0, yielding the two regimes in (17).

Combining the two lemmas with a union bound yields Theorem 3:

The predictor p̂: X → [−1, 1] in (14) is constructed from 2k − 1 i.i.d. observations and depends on neither L∗ nor δ. For every 0 L(p̂) ≤ L∗ + 17000(√(L∗(d + log(3/δ))/k) + (d + log(3/δ))/k). (18)

Theorem 3 gives a randomized predictor; Theorem 1 requires a deterministic binary classifier. The paper notes that in the realizable case suffix averaging can be made binary by majority vote at a factor at most two in risk, but such a factor is harmless when L∗ = 0, but would lose the coefficient one on L∗ in the agnostic case. Instead, the final step is empirical risk minimization over the threshold class of the fixed score p:

T p = x ↦ 2·1 p(x) ≥ u − 1: −1 ≤ u ≤ 1 ∪ x ↦ −1.

Lemma 3.3 states that if ĥ is an empirical risk minimizer over T p on an independent i.i.d. validation sample of size k, then for every 0 L(ĥ) ≤ inf h∈T p L(h) + 223000(√(inf h∈T p L(h) log(12/δ)/k) + log(12/δ)/k).

The proof reduces the threshold class relative to a minimizer h∗ to two nested chains: the upper branch consists of hypotheses with h(x) ≥ h∗(x) pointwise and the lower branch those with h(x) ≤ h∗(x); within each branch the disagreement sets DIS(h,h∗) are nested, while sets from opposite branches are disjoint. The induced class has an empirical L2 cover of radius u and size at most 1 + q/u squared, where q is the empirical mass of the union of the two extremal disagreement sets; chaining gives Rademacher complexity at most 28√(s/k) for the sublevel set G s. Applying the local Rademacher complexity bound of Bartlett–Bousquet–Mendelson [7, Theorem 3.3], whose subroot function s ↦ 28√(s/k) has fixed point 784/k, yields the stated constants.

For n ≥ 6, let k = ⌊n/3⌋. The learner forms p̂ from observations 1,...,2k−1 and uses the next k observations as an independent validation block. It lists the distinct values p̂(X i) on the validation block, includes the classifiers x ↦ 2·1 p̂(x) ≥ u − 1 for each listed u plus the identically −1 rule, and selects an empirical risk minimizer from this finite list with a fixed tie-breaking rule, so ĥ is an ERM over T p̂. The identity

(1/2) ∫−1 1 1 2·1 p̂(x) ≥ u − 1 ≠ y du = (1/2)p̂(x) − y

and Fubini give inf h∈T p̂ L(h) ≤ L(p̂). Applying Lemma 3.3 with confidence δ/4 and Theorem 3 with confidence δ/16, using √(a+b) ≤ √a + √b and log(48/δ)/k ≤ (d + log(48/δ))/k, yields

L(ĥ) < L∗ + 3.1 · 10 7 (√(L∗(d + log(48/δ))/k) + (d + log(48/δ))/k).

A union bound shows the two events hold simultaneously with probability at least 1 − 5δ/16, hence at least 1 − δ; since k ≥ n/6, this implies (2). For n < 6, the learner returns the classifier identically equal to −1, and the error term in (2) exceeds one, so the bound is immediate. Finally, for 0 < δ ≤ 1/2, the paper notes that d + log(1/δ) ≥ 1 + log 2 and log 48 < (5/2)(1 + log 2), so d + log(48/δ) ≤ 27(d + log(1/δ)), which converts (2) into the abstract's bound with coefficient 7 · 10 8.

The appendix describes the research process. The project began in spring 2026 while the first author visited UC Berkeley, combining Long's cube orientation (which gives an agnostic leave-one-out bound of the correct order but with coefficient greater than one on the empirical optimum) with the discounted edge density approach of Dughmi, Kalayci, and York. An analogy with agnostic online classification — Alon et al.'s optimal horizon-dependent regret bound in terms of Littlestone dimension and Filmus et al.'s localization to the mistakes of the best comparator — suggested the localized bound in Lemma 2.1. The authors used large language models experimentally: in May 2026 they used OpenAI GPT-5.5 Pro to study simple VC classes such as thresholds and intervals; in early July automated runs suggested an argument for VC dimension one classes; in early August experiments with GPT-5.6 Sol in Ultra mode helped resolve the axis-parallel rectangle case, leading to the general random restriction argument. The paper states that on August 6, 2026, they tested a single prompt in 16 separate runs with GPT-5.6 Sol in Pro mode:

In 11 of these runs, the model produced an essentially correct proof outline for Lemma 2.1 and completed the remaining steps. The runs took 123 minutes on average.

The full prompt is reproduced in the appendix; it asks for a complete proof of the main theorem and gives hints: construct a coefficient-one fractional orientation of the full Boolean cube, prove Lemma 2.1 with projected Rademacher widths, derive the localized edge bound, combine with R D(F) ≤ C√(dD) and the Hall orientation criterion to obtain out(y) ≤ ρ V(y) + C(√(dρ V(y)) + d), apply to the trace to get a coefficient-one leave-one-out bound, symmetrize, average over the half-sample suffix with backward and forward martingales, and derandomize by relative validation over nested threshold classifiers without a logarithmic factor.

• Achieve optimal agnostic PAC classification.

The improved AI system can learn a binary classifier from n i.i.d. samples over any hypothesis class of VC dimension d with the statistically optimal excess-risk bound, up to universal constants, for every fixed Bayes risk L*:

[

L(h) L* + O! (sqrt L*(d+ (1/delta)) over n + d+ (1/delta) over n).

]

This removes the polylogarithmic factors present in earlier agnostic algorithms and matches the known lower bound.

• Learn without knowing L or delta.*

The improved system can use a deterministic, generally improper learner that does not require the user to specify the optimal risk or the confidence parameter in the algorithm design, while still providing a high-probability guarantee for every 0< delta<1. This makes it suitable for fully adaptive, deployment-safe learning pipelines.

• Use provably tight leave-one-out prediction.

The system can implement the paper’s hypercube-orientation algorithm: for each held-out example, it orients the edges of the Boolean cube on the trace of the hypothesis class using Hall’s theorem and the new class-dependent edge-isoperimetric inequality. It then predicts the label corresponding to the head of the oriented edge, yielding

[

L S LOO L S* + 120 sqrt d, L S*/n + 7202d/n,

]

with no extra logarithmic factors.

• Symmetrize non-permutation-invariant rules without losing optimality.

Because the orientation need not be permutation invariant, the improved system can uniformly permute the indexed sample, apply the leave-one-out rule with the query point inserted at a random coordinate, and average the resulting scores. It thereby obtains a deterministic symmetric scoring function q(x;S) in[-1,1] whose risk is well-behaved and whose excess risk obeys the optimal rate.

• Construct confidence-rated predictors with martingale concentration.

The system can form a suffix-averaged predictor

[

p(x)= 1k sum t=k 2k-1 q t(x)

]

and guarantee, with probability 1-delta,

[

L(p) L* + 17000 (sqrt L*(d+ (3/delta)) over k + d+ (3/delta) over k),

]

using reverse and forward martingale arguments that preserve the comparator-dependent variance needed for uniformity in L*. This is useful for calibrated prediction, downstream thresholding, and model selection.

• Derandomize any randomized predictor with near-optimal threshold validation.

Given a score function p(x), the improved system can list the distinct scores on a validation set, define the threshold class

[

T p=x 2 times 1p(x) u-1: -1 u 1 x-1,

]

and run empirical risk minimization over the observed thresholds. It then outputs a deterministic binary classifier satisfying

[

L(h) h in T pL(h) + O! (sqrt L(h) (1/delta) over k +(1/delta) over k),

]

avoiding the factor-two loss of a simple majority vote and the usual logarithmic penalties.

• Use local Rademacher complexity for adaptive model selection.

The improved system can exploit the paper’s chaining-based bound R D(F) 60 sqrt dD and the nested-chain structure of threshold classes to compute tight data-dependent complexity estimates. This enables model selection, threshold tuning, and aggregation with optimal rates rather than conservative union bounds.

• Transfer the new isoperimetric lemma to other learning problems.

The core Lemma 2.1 — a class-dependent edge-isoperimetric inequality with weights satisfying

[

w v,p+w v p,p=1, sum p in Dw v,p rho F(v)+R D(F)

]

— can be reused by the improved system to design optimal algorithms in online classification, active learning, multiclass learning, or other settings where the hypothesis class has finite combinatorial dimension.

• Accelerate mathematical discovery with LLM-assisted proof generation.

The paper demonstrates that an LLM, given a high-level proof plan with key lemmas and hints, can produce a correct proof outline for a major open problem in 11 of 16 runs, averaging 123 minutes. The improved AI system can therefore be used as an automated research assistant: it can generate candidate proofs from structured hints, run multiple attempts in parallel, verify logical steps, and complete missing arguments, significantly accelerating progress in statistical learning theory.

• Solve special-case-driven generalization tasks.

Following the method in the appendix, the improved system can first solve simplified cases (thresholds, intervals, VC-dimension-one classes, axis-parallel rectangles) using automated experimentation with large language models, then infer the general random-restriction argument. This gives the system the ability to discover general theorems from structured case analyses.

Let H-1,+1 X be a class of finite VC dimension d 1. Writing L for the binary risk and L*= h in H L(h), we construct a learner achieving the statistically optimal risk bound: from an i.i.d. sample of size n, for every 0< delta 1/2, with probability at least 1-delta, [ L(h) L*+ 7 times10 8 ( sqrt L*(d+ (1/delta)) over n + d+ (1/delta) over n ).] This settles the sample complexity of agnostic PAC learning up to universal constants at every fixed L*, matching the lower bounds of Devroye, Gy"orfi, and Lugosi [A Probabilistic Theory of Pattern Recognition, Springer, 1996].