An Optimal Agnostic PAC Algorithm

An Optimal Agnostic PAC Algorithm Markus Engelund Mathiasen∗

Jian Qian†

Nikita Zhivotovskiy‡

August 6, 2026

arXiv:2608.06363v1 [cs.LG] 6 Aug 2026

Abstract Let H ⊆ {−1, +1}X be a class of finite VC dimension d ≥ 1. Writing L for the binary risk and L∗ = minh∈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 < δ ≤ 1/2, with probability at least 1 − δ, ! r ∗ (d + log(1/δ)) L d + log(1/δ) L(b h) ≤ L∗ + 7 · 108 + . n 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örfi, and Lugosi [A Probabilistic Theory of Pattern Recognition, Springer, 1996].

1

Introduction

Determining sharp risk bounds in PAC classification has been one of the central problems in statistical learning theory since the introduction of VC theory and the PAC model [8, 26, 27]. Throughout, let H ⊆ {−1, +1}X be a class of measurable hypotheses with VC(H) = d ≥ 1. Let S = ((Xi , Yi ))ni=1 be an i.i.d. sample from the distribution of (X, Y ). We write L(h) = P(h(X) ̸= Y ) and L∗ = minh∈H L(h).1 Historically, bounds in this setting have been proved by two rather different methods. In the agnostic setting, when L∗ is bounded away from zero by a constant, empirical risk minimization is analyzed through classical empirical process p methods, including chaining and covering bounds for VC classes. This approach gives the optimal d/n rate in this regime. In the realizable, or noiseless, case, the uniform convergence analysis of empirical risk minimization does not give the optimal d/n rate. The seminal work of Haussler, Littlestone, and Warmuth is based on the one-inclusion graph, and its leave-one-out analysis gives the optimal expected rate [20]. The first optimal high probability PAC bound was proved by Hanneke [18], building on the work of Simon [25]. Several later constructions also attain the optimal PAC rate, including bagging [21], aggregation of one-inclusion rules [2], and, very recently, a majority of three consistent classifiers [24]. These results rely on specific combinatorial or probabilistic arguments rather than a direct empirical process analysis. The remaining question is how the optimal rate changes between the realizable and fully agnostic settings, and which algorithms attain the intermediate rates. The relevant expectation and deviation ∗

Department of Computer Science, Aarhus University. markusm@cs.au.dk. Division of Artificial Intelligence and Data Science, School of Computing and Data Science, The University of Hong Kong. jianqian@hku.hk. ‡ Department of Statistics, University of California, Berkeley. zhivotovskiy@berkeley.edu. 1 We assume that all maps depending on the data are measurable and that this minimum is attained. †

1

lower bounds go back to Devroye, Györfi, and Lugosi [10, 11].2 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 minh∈H L(h) = L∗ for which, with probability at least δ, ! r ∗ (d + log(1/δ)) L d + log(1/δ) . (1) L(b h) ≥ L∗ + c + n n The probability is over the sample and any internal randomness of the learner. This bound gives the optimal realizable rate when L∗ = 0, the usual agnostic rate when L∗ is bounded away from zero, and the intermediate rates between them. It remained open whether any learner could attain it. Several upper bounds nearly match this lower bound. Hanneke, Larsen, and Zhivotovskiy [19] proved ! r 5 ∗ (d + log(1/δ)) L log (n/d)(d + log(1/δ)) L(b h) ≤ L∗ + C , + n n where C > 0 is a universal constant. This is suboptimal by the polylogarithmic factor in the fast p 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 [9, 19]. Other results give the optimal order when L∗ is close to zero, namely when L∗ ≲ (d + log(1/δ))/n. In this regime, Long’s agnostic one-inclusion graph algorithm [22], combined with the probability arguments in Section 3, achieves the optimal bound, as does the result of Asilis, Høgsgaard, and Velegkas [5]. The resulting bounds have a leading coefficient greater than one on L∗ , which is harmless in this regime because the excess is absorbed by the fast rate term. We prove the following theorem. Theorem 1 (An optimal agnostic PAC learner). There is a deterministic, generally improper learner that uses neither L∗ nor δ and outputs a classifier b h : X → {−1, +1} such that for every distribution, every n ≥ 1, and every 0 < δ < 1, with probability at least 1 − δ, ! r ∗ (d + log(48/δ)) L d + log(48/δ) L(b h) ≤ L∗ + 2 · 108 + . (2) n n Together with the matching lower bound in (1), Theorem 1 determines, up to universal constants, the distribution-free high probability minimax excess risk bound for binary classification at every fixed L∗ . Our construction remains close to Long’s original idea of orienting the entire Boolean cube in the agnostic one-inclusion graph algorithm and deriving the corresponding leave-one-out bound. The key new ingredient is Lemma 2.1, a class dependent edge isoperimetric inequality that controls induced edge counts through approximation errors and projected Rademacher widths. Once this orientation is available, we apply suffix averaging with variance control, adapted from Aden-Ali, Cherapanamjeri, Shetty, and Zhivotovskiy [2], to rules trained on successive prefixes of the sample. A final thresholding step derandomizes the predictor and gives the desired high probability bound.

2

Edge isoperimetry and the optimal leave-one-out bound

This section proves the optimal leave-one-out bound used in Theorem 1. Section 3 converts the resulting leave-one-out rule into an optimal PAC learner. We first introduce the cube notation for The exact form of (1) is not stated in these references. Within the usual nontrivial boundaries for L∗ , it follows by retaining the bounded witness in their dimension dependent construction and combining it with their deviation and realizable lower bounds. Audibert later sharpened the corresponding expected risk bound [6]. 2

2

the one-inclusion analysis. Let P be a nonempty finite coordinate set and let VP = {−1, +1}P . For v ∈ VP and p ∈ P , let v ⊕p be obtained from v by flipping coordinate p. The Boolean cube GP = (VP , EP ) has  EP = {v, v ⊕p } : v ∈ VP , p ∈ P . For U ⊆ VP , let EU = {e ∈ EP : e ⊆ U } be the cube edges with both endpoints in U . For v ∈ VP , let DU (v) = {p ∈ P : v ⊕p ∈ U } be the coordinate directions from v to a neighbor in U . Thus GP [U ] = (U, EU ) and degU (v) = |DU (v)| for v ∈ U . In particular, GP [F] is the one-inclusion graph of a trace F ⊆ VP [20]. Orienting the full cube with vertex bounds depending on distance to the trace goes back to Long [22, Lemmas 15 and 16] and also appears in later agnostic analyses [4, 15]. The sets U ⊆ VP will be the cuts in the Hall condition below. Fix a nonempty F ⊆ VP with VC(F) ≤ d. For u, v ∈ VP , define their disagreement set by DIS(u, v) = {p ∈ P : u(p) ̸= v(p)}. The Hamming distance from v to F is ρF (v) = min | DIS(v, f )|. f ∈F

For every v, v ′ ∈ VP with | DIS(v, v ′ )| = 1, the triangle inequality gives |ρF (v) − ρF (v ′ )| ≤ 1. For D ⊆ P , let RD (F) = Eε max f ∈F

X

(3)

εp f (p)

p∈D

be the unnormalized signed Rademacher width of the projection F|D . Keeping the constants in the chaining and covering arguments of Devroye and Lugosi [12, Sections 3.2 and 4.3] gives p RD (F) ≤ 60 d|D|. (4) Up to a universal constant, the same bound follows by combining the VC covering number bound of Dudley [14] with chaining. This is the only point at which the VC dimension enters our proof. By contrast, the realizable one-inclusion analysis of Haussler, Littlestone, and Warmuth uses the VC dimension directly to control induced edge counts [20]. The following lemma is the key connection between induced edge counts on the Boolean cube, the Hamming distance to F, and projected Rademacher widths. We discuss its isoperimetric interpretation and partial precedents after the proof. Lemma 2.1 (Class dependent edge isoperimetry on the Boolean cube). There are weights wv,p ∈ [0, 1], fixed simultaneously for all v ∈ VP and p ∈ P with the following properties. The first relation below holds for every v ∈ VP and p ∈ P , and the second for every v ∈ VP and D ⊆ P : wv,p + wv⊕p ,p = 1, X wv,p ≤ ρF (v) + RD (F).

(5) (6)

p∈D

Consequently, for every U ⊆ VP , the induced subgraph satisfies the localized edge bound X
|EU | ≤ ρF (v) + RDU (v) (F) . v∈U

3

(7)

Proof. Let T contain each coordinate of P independently with probability 1/2. Since F is finite, fix any order on it. For each T ⊆ P , let πT (v) be the first member of F minimizing | DIS(v, f ) ∩ T |. In particular, v|T = v ′ |T implies πT (v) = πT (v ′ ). (8) Define the weights

(9)

wv,p = PT (p ∈ DIS(v, πT (v)) | p ∈ / T). Clearly wv,p ∈ [0, 1]. Suppose p ∈ / T . Then v|T = v ⊕p |T , so (8) gives πT (v) = πT (v ⊕p ).

The labelings v and v ⊕p have opposite labels at p, while this common fit has one fixed label there. Hence 1{p ∈ DIS(v, πT (v))} + 1{p ∈ DIS(v ⊕p , πT (v ⊕p ))} = 1. Taking conditional expectation given p ∈ / T proves (5). It remains to prove (6). Fix v ∈ VP and D ⊆ P , and set ( +1, p ∈ / T, εp = −1, p ∈ T. Then (εp )p∈P are independent Rademacher signs. First, X wv,p = 2ET DIS(v, πT (v)) ∩ D ∩ T c . p∈D

Indeed, PT (p ∈ / T ) = 1/2, so the conditional probability in (9) equals twice the corresponding unconditional probability. Next, applying the pointwise identity X |B ∩ D ∩ T c | = |B ∩ D ∩ T | + εp 1{p ∈ B} p∈D

to B = DIS(v, πT (v)) gives X X wv,p = 2ET DIS(v, πT (v)) ∩ D ∩ T + 2ET εp 1{p ∈ DIS(v, πT (v))} p∈D

p∈D

≤ 2ET DIS(v, πT (v)) ∩ T + 2ET max f ∈F

X

εp 1{p ∈ DIS(v, f )}.

(10)

p∈D

For the first term, we dropped the restriction to D; for the second, we replaced the particular choice πT (v) ∈ F by the maximum over f ∈ F. By the definition of πT (v), 2ET DIS(v, πT (v)) ∩ T = 2ET min | DIS(v, f ) ∩ T | f ∈F

≤ min 2ET | DIS(v, f ) ∩ T | = ρF (v). f ∈F

Meanwhile, since 21{p ∈ DIS(v, f )} = 1 − v(p)f (p), we have 2ET max f ∈F

X

εp 1{p ∈ DIS(v, f )} = ET

p∈D

X

εp + ET max

p∈D

= RD (F). 4

f ∈F

X p∈D

(−εp v(p))f (p)

P Here ET p∈D εp = 0, and (−εp v(p))p∈D are again independent Rademacher signs. Combining the last two displays with (10) proves (6). Finally, every edge {v, v ⊕p } ∈ EU contributes wv,p + wv⊕p ,p = 1 to the incidence sum. Hence we have X X |EU | = wv,p . v∈U p∈DU (v)

Applying (6) with D = DU (v) and summing over v ∈ U proves (7). Remark 2.2 (Relation to cube edge isoperimetry). For every nonempty U ⊆ VP , the edge isoperimetric inequality on the cube [23, Theorem 2.39] gives |EU | ≤

|U | log2 |U |. 2

For a subcube of dimension k, both sides equal k2k−1 . Lemma 2.1 gives instead the following localized bound relative to any F ⊆ VP : X
ρF (v) + RDU (v) (F) . |EU | ≤ v∈U

The quantity on the right depends on the position of U relative to F and on the internal coordinate sets DU (v). In general, neither bound dominates the other. Remark 2.3. Several earlier results capture different parts of Lemma 2.1. • For every nonempty U ⊆ F, Haussler, Littlestone, and Warmuth [20] proved |EU | ≤ VC(U )|U | ≤ d|U |. The inclusion U ⊆ F is essential for the second inequality and leaves an arbitrary U ⊆ VP uncontrolled by d alone. • Long’s cube orientation [22, Lemmas 15 and 16] applies to every U ⊆ VP and gives X |EU | ≤ 15 (d + ρF (v)) . v∈U

The construction uses distance shells but does not give a Rademacher width restricted to a coordinate set. More importantly, the coefficient 15 on ρF (v) prevents a leave-one-out bound with coefficient one on the empirical optimum. • Asilis, Devic, Dughmi, Sharan, and Teng [4, Appendix E.3, proof of Proposition 69] use the same omitted coordinate mechanism to define a fractional orientation. Hiding the edge coordinate makes its endpoints conditionally identical, and averaging gives (5). Their argument does not give (6) simultaneously for every D ⊆ P . • For every U ⊆ VP , Dughmi, Kalayci, and York prove the all-coordinate bound |EU | ≤

X

ρF (v) +

v∈U

|U | RP (F), 2

with equality for U = VP ; see [15, Lemmas 8 and 9, and Section 3.4]. Their inequality uses the single full width RP (F). Lemma 2.1 instead controls one assignment for every D ⊆ P , allowing the vertexwise choice D = DU (v). 5

Lemma 2.1 is converted into an orientation by the Hall argument commonly used in agnostic leave-one-out analyses. We recall the required definitions. An orientation of a finite graph G = (V, E) chooses a head σ(e) ∈ e for each edge. Its outdegree at x is out(x; σ) = |{e ∈ E : x ∈ e, σ(e) ̸= x}|. For W ⊆ V , write EG (W ) = {e ∈ E : e ⊆ W }. A form of Hall’s theorem states that if integer capacities cx ≥ 0 satisfy the following inequality for every W ⊆V, X |EG (W )| ≤ cx , x∈W

then every edge can be assigned to one endpoint so that, for every x ∈ V , at most cx edges are assigned to x [13, Theorem 2.1.2]. Taking the assigned endpoint as the tail gives an orientation with outdegree at most cx . Combining Lemma 2.1 with (4) and this Hall condition yields the optimal agnostic leave-one-out bound. For a labeled sequence S = ((xi , yi ))ni=1 ∈ (X × {−1, +1})n , a leave-one-out rule observes all inputs and all labels except yi when predicting ybi . We denote b ∗S = 1 min L n h∈H

n X

b LOO = 1 and L S n

1{h(xi ) ̸= yi },

i=1

n X

1{b yi ̸= yi }.

i=1

Theorem 2 (Orientation of the cube and the leave-one-out bound). Let P be a nonempty finite coordinate set, let d ≥ 1, and let ∅ = ̸ F ⊆ VP satisfy VC(F) ≤ d. There is a deterministic orientation σ of the full cube such that, for every v ∈ VP , p out(v; σ) ≤ ρF (v) + 120 dρF (v) + 7202d. (11) Consequently, for every n ≥ 1 and every input sequence x1 , . . . , xn , allowing repetitions, there is a deterministic, generally improper leave-one-out rule depending only on the unlabeled sequence such that, for every (y1 , . . . , yn ) ∈ {−1, +1}n , s b∗ b LOO ≤ L b ∗ + 120 dLS + 7202 d . L (12) S S n n Proof. Fix a nonempty U ⊆ VP . By (5), we have X X |EU | =

wv,p .

v∈U p∈DU (v)

For every v ∈ U , (6) and (4) give X

wv,p ≤ ρF (v) + 60

p∈DU (v)

p 900 d degU (v) ≤ ρF (v) + 3601d + degU (v). 3601

√ The last step uses the elementary inequality ab ≤√(a + b)/2. Relabel the endpoints of an edge {v, v ⊕p } ∈ EU so that ρF (v) ≤ ρF (v ⊕p ). By (3) and 1 + x ≤ 1 + x/2 for x ≥ 0, r p 1/ ρF (v) + 3601d 1 1 p ≤ 1+ ≤1+ . ⊕p 3601d 7202d 1/ ρF (v ) + 3601d Consequently, 1

1

1 p −p ≤ min ⊕p 7202d ρF (v) + 3601d ρF (v ) + 3601d 6

1 p

ρF (v) + 3601d

,p

1 ρF (v ⊕p ) + 3601d

! .

By (5), it holds that 1 1 p +p ⊕p ρF (v) + 3601d ρF (v ) + 3601d wv⊕p ,p

wv,p

=2

!

p +p ρF (v) + 3601d ρF (v ⊕p ) + 3601d 1

+ (wv⊕p ,p − wv,p )  ≤ 2+

1 7202d



!

1

p −p ρF (v) + 3601d ρF (v ⊕p ) + 3601d ! wv⊕p ,p wv,p p +p . ρF (v) + 3601d ρF (v ⊕p ) + 3601d

The last step uses |wv⊕p ,p − wv,p | ≤ 1 and the fact that the weighted average is at least the smaller reciprocal. Summing this inequality over EU and applying the preceding bound gives  X P X 1 degU (v) p∈DU (v) wv,p p p ≤ 2+ 7202d ρF (v) + 3601d ρF (v) + 3601d v∈U v∈U !  X p 1 900 degU (v) p ≤ 2+ ρF (v) + 3601d + . 7202d 3601 ρF (v) + 3601d v∈U

Moving the last term to the left gives   X  X  p 1 degU (v) 1 900 p 2+ ≤ 2+ ρF (v) + 3601d. 1− 3601 7202d 7202d ρF (v) + 3601d v∈U v∈U 2+1/(7202d) For d ≥ 1, 1−(900/3601)(2+1/(7202d)) < 4. Dividing the preceding inequality therefore gives

Xp degU (v) p <4 ρF (v) + 3601d. ρF (v) + 3601d v∈U v∈U X

Cauchy-Schwarz inequality now yields Xp

degU (v) ≤

v∈U

X

degU (v)

p ρF (v) + 3601d v∈U

!1/2

!1/2 Xp ρF (v) + 3601d v∈U

<2

Xp ρF (v) + 3601d. v∈U

Finally, we have |EU | ≤

X v∈U

ρF (v) + 60

 X  p p d degU (v) < ρF (v) + 120 d (ρF (v) + 3601d) . v∈U

The empty set p satisfies the same bound trivially. Hence Hall’s theorem, with integer capacity ⌈ρF (v) + 120 d(ρF (v) + 3601d)⌉ at v, gives an orientation such that, using ⌈x⌉ < x + 1 and √ √ √ x + y ≤ x + y, p p √ out(v; σ) < ρF (v) + 120 dρF (v) + 120 3601 d + 1 < ρF (v) + 120 dρF (v) + 7202d. Choose the first feasible orientation in a fixed ordering of the finitely many orientations. This proves (11). 7

For the leave-one-out statement, apply the orientation result with P = {1, . . . , n} to the trace  F = (h(x1 ), . . . , h(xn )) : h ∈ H . Write vy = (y1 , . . . , yn ) ∈ VP . This edge prediction convention is due to Long [22]; see also the general agnostic one-inclusion formalism of Asilis et al. [4]. Algorithm 1 The agnostic leave-one-out rule. Inputs: The orientation σ, a held-out index i ∈ {1, . . . , n}, and the observed labels (yj )j̸=i . Output: A prediction ybi ∈ {−1, +1}. For the held-out coordinate i, predict as follows. 1: Fix coordinate j at yj for every j ̸= i. 2: Complete coordinate i with each of its two signs; the two completions form a cube edge. 3: Set y bi equal to coordinate i of the head selected by σ. By construction, the predictor is wrong at coordinate i exactly when the true completion is the tail of this edge. Hence b LOO nL = out(vy ; σ). S b ∗ and VC(F) ≤ d, dividing (11) by n proves (12). Since ρF (vy ) = nL S

3

From leave-one-out to PAC bounds

Let P be a distribution on X × {−1, +1}. We identify a randomized binary predictor with its measurable conditional mean g : X → [−1, 1]: on input x, it predicts +1 with probability (1 + g(x))/2. We write ℓ(a, y) = |a − y|/2 and extend the notation L to the risk of such a score: 1 L(g) = E(X,Y )∼P ℓ(g(X), Y ) = E(X,Y )∼P |g(X) − Y |. 2 For {−1, +1}-valued g, this agrees with the usual binary classification risk. If g depends on the data, the expectation is over an independent test point conditional on the training sample.

3.1

Symmetrization of the agnostic one-inclusion-graph algorithm

The orientation from Theorem 2 need not be invariant under permutations of the sample, so we symmetrize its predictions. Given a labeled sample S and an unlabeled query x, append x, uniformly permute the resulting indexed points, and apply the corresponding deterministic leave-one-out rule while hiding the coordinate occupied by x. Let q(x; S) be the expectation of the resulting signed prediction over this permutation. The score q(x; S) ∈ [−1, 1] is deterministic and symmetric in the observations of S. −i for the sample with observation i removed. For a labeled sample S = ((xi , yi ))m i=1 , write S Averaging (12) over all permutations gives, for every S, s m b∗ 1 X b ∗ + 120 dLS + 7202 d . |q(xi ; S −i ) − yi | ≤ L (13) S 2m m m i=1

8

3.2

A randomized learner by suffix averaging

The argument below adapts the reverse and forward martingale proof of Aden-Ali, Cherapanamjeri, Shetty, and Zhivotovskiy [2] from the realizable to the agnostic setting. Dughmi, Kalayci, and York [15] gave a related conversion for bounded agnostic losses. Here we retain the comparator dependent variance needed for a bound uniform in L∗ and avoid the additional logarithmic factor in their analysis. Even in the realizable case, some one-inclusion rules that are optimal in expectation have tails no better than Markov’s inequality [1]. Thus an orientation result of Theorem 2 alone does not give the optimal dependence on δ. Suffix averaging gives the required confidence dependence. Fix an integer k ≥ 1. Let Zi = (Xi , Yi ), i = 1, . . . , 2k, be i.i.d. observations and write S≤t = (Z1 , . . . , Zt ). For k ≤ t ≤ 2k − 1, set qt (x) = q(x; S≤t ), where q is the symmetrized leave-one-out score satisfying (13). The randomized predictor averages the scores qt over the suffix of training times t = k, . . . , 2k − 1. Its conditional mean is 2k−1

pb(x) =

1 X qt (x). k

(14)

t=k

P Thus it predicts +1 with probability (1 + pb(x))/2 and, by linearity, L(b p) = k −1 2k−1 t=k L(qt ). Only Z1 , . . . , Z2k−1 enter the construction of pb. The additional observation Z2k is the fresh point used to analyze q2k−1 and does not enter the learner. Derandomization is deferred to the next subsection. For every h ∈ H, linearity gives 2k−1
1 X L(b p) − L(h) = L(qt ) − L(h) . k

(15)

t=k

As in [2], the reverse martingale lemma below uses permutation invariance to apply (13) along a random deletion sequence and control the realized excess loss on the held-out observations. The forward martingale lemma compares this sequential excess loss with its conditional mean, the population excess risk in (15). Together they yield the randomized guarantee in Theorem 3. Lemma 3.1 (Reverse martingale). Let Zi = (Xi , Yi ), 1 ≤ i ≤ 2k, be i.i.d. observations, and let qt (x) = q(x; (Z1 , . . . , Zt )), where q is the deterministic symmetric score satisfying (13). Fix h ∈ H and, for k ≤ t ≤ 2k − 1, let ∆t+1,h = ℓ(qt (Xt+1 ), Yt+1 ) − 1{h(Xt+1 ) ̸= Yt+1 }. For every 0 < δ ≤ 1/3, with probability at least 1 − 2δ, ! ! r 2k X 1 L(h)(d + log(1/δ)) d + log(1/δ) max ∆m,h , 0 ≤ 8200 + . k k k

(16)

m=k+1

Lemma 3.2 (Forward martingale). Under the assumptions and notation of Lemma 3.1, for every 0 < δ ≤ 1/3, with probability at least 1 − δ, ! r 2k−1 2k X
2 1 X L(h) log(1/δ) log(1/δ) L(qt ) − L(h) ≤ max ∆m,h , 0 + 5 + 10 . (17) k k k k t=k

m=k+1

Theorem 3 (The optimal risk bound for the randomized predictor). The predictor pb : X → [−1, 1] in (14) is constructed from 2k − 1 i.i.d. observations and depends on neither L∗ nor δ. For every 0 < δ < 1, with probability at least 1 − δ, ! r ∗ (d + log(3/δ)) L d + log(3/δ) L(b p) ≤ L∗ + 17000 + . (18) k k 9

Proof of Theorem 3. Choose h∗ ∈ H with L(h∗ ) = L∗ . Apply Lemmas 3.1 and 3.2 with confidence δ/3. A union bound shows that both conclusions hold simultaneously with probability at least 1 − δ. On this event, 2k−1

L(b p) − L∗ =

1 X L(qt ) − L∗ k t=k

2k X

!

r

L∗ log(3/δ) log(3/δ) + 10 k k m=k+1 ! r r L∗ (d + log(3/δ)) d + log(3/δ) L∗ log(3/δ) log(3/δ) ≤ 16400 + +5 + 10 k k k k ! r L∗ (d + log(3/δ)) d + log(3/δ) . < 17000 + k k 2 ≤ max k

∆m,h∗ , 0

+5

The claim follows. Proof of Lemma 3.1. Fix h ∈ H and 0 < δ ≤ 1/3. The independent permutation below exploits the symmetry of q. Conditional on the observations, exposing the permutation backward makes the ei , Yei ), next removed observation uniform among those that remain. Draw i.i.d. observations Wi = (X 1 ≤ i ≤ 2k, and an independent uniform permutation π of {1, . . . , 2k}. Set Zm = Wπ(m) . For k ≤ m ≤ 2k, let Rm be the σ-algebra generated by the complete sample and the permutation indices already exposed at positions 2k, . . . , m + 1:
Rm = σ W1 , . . . , W2k , π(j) : m < j ≤ 2k . Thus Rm reveals which m indices remain, but not their order. Let Im be the set of these indices and −i be obtained from B by deleting W . write Bm = (Wi )i∈Im in any fixed order. For i ∈ Im , let Bm m i Conditional on Rm , the index π(m) is uniform on Im . Because q is symmetric, if π(m) = i, then the −i ). first m − 1 observations give the same prediction as q( · ; Bm For i ∈ Im , let
ei ; B −i ), Yei − 1{h(X ei ) ̸= Yei }. ∆i,m,h = ℓ q(X m It follows that ∆m,h = ∆π(m),m,h and E[∆m,h | Rm ] =

1 X ∆i,m,h . m i∈Im

After π(m) is revealed, ∆m,h is measurable with respect to Rm−1 . Hence, as m runs from 2k down to k + 1, ∆m,h − E[∆m,h | Rm ] forms a martingale difference sequence with respect to the reverse filtration. The empirical optimum on Bm is at most the empirical loss of h. Applying (13) to Bm and subtracting the empirical loss of h gives q P q P ei ) ̸= Yei } e e d i∈Im 1{h(X d 2k d d i=1 1{h(Xi ) ̸= Yi } E[∆m,h | Rm ] ≤ 120 + 7202 ≤ 120 + 7202 , m m k k (19) 10

where the last inequality uses m ≥ k and bounds the sum over Im by the sum over the complete sample. For the conditional second moment, applying (a − b)2 ≤ a + b, valid for a ∈ [0, 1] and b ∈ {0, 1}, to the two losses, averaging over the uniform choice of i ∈ Im , and using (13) again gives q P ei ) ̸= Yei } d i∈Im 1{h(X X 2 d ei ) ̸= Yei } + 120 E[∆2m,h | Rm ] ≤ + 7202 1{h(X m m m i∈Im q P 2k e e d 2k d 2X i=1 1{h(Xi ) ̸= Yi } e e 1{h(Xi ) ̸= Yi } + 120 + 7202 . (20) ≤ k k k i=1

The number of errors p made by h on the complete sample is distributed as Bin(2k, L(h)). Bernstein’s inequality and 2 kL(h) log(1/δ) ≤ kL(h) + log(1/δ) imply that, with probability at least 1 − δ,   2k 1X log(1/δ) e e . 1{h(Xi ) ̸= Yi } ≤ 3 L(h) + k k

(21)

i=1

On the event in (21), q P r e e d 2k 3d(L(h) + log(1/δ)/k) d d i=1 1{h(Xi ) ̸= Yi } 120 + 7202 ≤ 120 + 7202 k k k k ! r L(h)(d + log(1/δ)) d + log(1/δ) + . ≤ 8000 k k

(22)

Conditionally on W1 , . . . , W2k , we apply Freedman’s inequality [17] to the preceding martingale differences, with m read in decreasing order. By (20), their predictable quadratic variation satisfies v u 2k 2k 2k h i u X X X 2 ei ) ̸= Yei } + 120td ei ) ̸= Yei } + 7202d, E (∆m,h − E[∆m,h | Rm ]) Rm ≤ 2 1{h(X 1{h(X i=1

m=k+1

i=1

and |∆m,h − E[∆m,h | Rm ]| ≤ 2. Moreover, summing (19) over m = k + 1, . . . , 2k gives v u 2k 2k u X X ei ) ̸= Yei } + 7202d. E[∆m,h | Rm ] ≤ 120td 1{h(X i=1

m=k+1

Therefore, conditionally on W1 , . . . , W2k , with probability at least 1 − δ, q P 2k e e d 2k 1 X d i=1 1{h(Xi ) ̸= Yi } ∆m,h ≤ 120 + 7202 k k k m=k+1 v q P  u u 2k ei ) ̸= Yei } d 2k 1{h( X u 4X d log(1/δ) i=1 ei ) ̸= Yei } + 240 + t 1{h(X + 14404  k k k k i=1

+

2 log(1/δ) . 3k

(23) 11

It remains to simplify the square root term. On the event in (21), (22) gives q P   2k 2k e e X d 1{h( X ) = ̸ Y } i i d log(1/δ) i=1 ei ) ̸= Yei } + 240 4 1{h(X + 14404  k k k k i=1 2  L(h) log(1/δ) log(1/δ) ≤ 12 + 12 k k ! r L(h)(d + log(1/δ)) d + log(1/δ) log(1/δ) + 16000 + k k k !2 r L(h)(d + log(1/δ)) d + log(1/δ) ≤ 16024 + . k k p The last inequality follows because both L(h) log(1/δ)/k and log(1/δ)/k are bounded by the parenthesized expression. Substituting these bounds into (23) gives ! r 2k 1 X L(h)(d + log(1/δ)) d + log(1/δ) ∆m,h ≤ 8000 + k k k m=k+1 ! r √ L(h)(d + log(1/δ)) d + log(1/δ) 2 log(1/δ) + 16024 + + k k 3k ! r L(h)(d + log(1/δ)) d + log(1/δ) + < 8200 . k k The event in (21) has probability at least 1 − δ, and averaging the conditional Freedman bound shows that (23) holds with probability at least 1 − δ. Thus both bounds hold simultaneously with probability at least 1 − 2δ. On their intersection, taking the positive part in the preceding display gives (16). Since (Z1 , . . . , Z2k ) has the original i.i.d. law, the proof follows. Proof of Lemma 3.2. Fix h ∈ H and 0 < δ ≤ 1/3. Conditionally on S≤t , the prediction qt is fixed and Zt+1 is an independent observation. Hence E[∆t+1,h | S≤t ] = L(qt ) − L(h). Since (a − b)2 ≤ a + b for a, b ∈ [0, 1], applying this inequality to the losses of qt and h gives Var(∆t+1,h | S≤t ) ≤ E[∆2t+1,h | S≤t ] ≤ L(qt ) + L(h) = L(qt ) − L(h) + 2L(h).

(24)

Therefore ξt+1,h = L(qt ) − L(h) − ∆t+1,h is a martingale difference with respect to the sample prefixes. It satisfies ξt+1,h ≤ 2 and, by (24), 2 E[ξt+1,h | S≤t ] ≤ L(qt ) − L(h) + 2L(h).

Fix 0 < λ < 3/2. The Bernstein moment generating bound gives    
λ2 L(qt ) − L(h) + 2L(h) S≤t ≤ 1. E exp λξt+1,h − 2(1 − 2λ/3) 12

Iterating this inequality over t and applying Markov’s inequality shows that, with probability at least 1 − δ, ! 2k−1 2k−1 2k X X X

log(1/δ) λ L(qt ) − L(h) + 2kL(h) + L(qt ) − L(h) − ∆m,h ≤ . (25) 2(1 − 2λ/3) λ t=k

t=k

m=k+1

Choose λ = min algebra gives



1 2,

q

log(1/δ) kL(h)



when L(h) > 0, and λ = 1/2 when L(h) = 0. Since λ ≤ 1/2, simple

2k−1

2 1 X L(qt ) − L(h) ≤ max k k t=k

If λ =

2k X

! ∆m,h , 0

+ 3λL(h) + 2

m=k+1

log(1/δ) . λk

(26)

p log(1/δ)/(kL(h)), the last two terms in (26) equal r r r L(h) log(1/δ) L(h) log(1/δ) L(h) log(1/δ) 3 +2 =5 . k k k

If λ = 1/2, then L(h) ≤ 4 log(1/δ)/k, and 3λL(h) + 2

3 log(1/δ) log(1/δ) log(1/δ) = L(h) + 4 ≤ 10 . λk 2 k k

This proves (17).

3.3

A deterministic binary predictor

Theorem 3 gives the desired bound for a randomized predictor, while Theorem 1 requires a deterministic binary classifier. In the realizable case, suffix averaging can be made binary by majority vote at a factor of at most two in risk [2]. Such a factor is harmless when L∗ = 0, but would lose the coefficient one on L∗ in the agnostic case. We instead choose a threshold on an independent validation sample. The final step is empirical risk minimization over the class obtained by thresholding the fixed score. For any reference threshold, the hypotheses above and below it form two nested families. This structure gives the local entropy bound below without an additional logarithmic factor in the sample size. Applying this bound in [7, Theorem 3.3] gives the next lemma with the displayed constants. Lemma 3.3. Let p : X → [−1, 1] be measurable and fixed independently of an i.i.d. validation sample Zi = (Xi , Yi ), 1 ≤ i ≤ k, where k ≥ 1. Consider the binary threshold class  Tp = x 7→ 21{p(x) ≥ u} − 1 : −1 ≤ u ≤ 1 ∪ {x 7→ −1}. If b h is an empirical risk minimizer over Tp , then, for every 0 < δ < 1, with probability at least 1 − δ, ! r inf L(h) log(12/δ) log(12/δ) h∈T p L(b h) ≤ inf L(h) + 223000 + . h∈Tp k k Proof. Assume first that the infimum is attained and let h∗ be a minimizer. Otherwise, take h∗ with risk arbitrarily close to the infimum and let the approximation error tend to zero. For h ∈ Tp , set gh (x, y) = 1{h(x) ̸= y} − 1{h∗ (x) ̸= y}. 13

Then E(gh (X, Y ) + 2L(h∗ )) = L(h) + L(h∗ ) and Var(gh (X, Y ) + 2L(h∗ )) = Var(gh (X, Y )) ≤ Egh (X, Y )2 = P(h(X) ̸= h∗ (X)) ≤ L(h) + L(h∗ ) = E(gh (X, Y ) + 2L(h∗ )). Order the threshold chain pointwise. Relative to h∗ , the chain has two branches. The upper branch consists of the hypotheses h satisfying h(x) ≥ h∗ (x) for every x ∈ X , and the lower branch consists of those satisfying h(x) ≤ h∗ (x) for every x ∈ X . Within either branch the sets DIS(h, h∗ ) are nested, while sets from opposite branches are disjoint. For every (x, y), gh (x, y) = −y1DIS(h,h∗ ) (x) on the upper branch and gh (x, y) = y1DIS(h,h∗ ) (x) on the lower branch. ∗ For s > 0, let Gs = {gh : Egh (X, Y )2 ≤ s}. Let A+ s be the union of DIS(h, h ) over the upper branch with gh ∈ Gs , and define A− s analogously over the lower branch. For every such h, P(X ∈ DIS(h, h∗ )) = Egh (X, Y )2 ≤ s. For these nested threshold sets, the probability of each union − is the supremum of the probabilities of its members. Thus P(X ∈ A+ s ) ≤ s and P(X ∈ As ) ≤ s. + − Since sets from opposite branches are disjoint, As ∩ As = ∅. Define k

q=

1X − 1{Xi ∈ A+ s ∪ As }, k i=1

and let th be the empirical mass of DIS(h, h∗ ), with positive sign for the upper branch and negative sign for the lower branch. Since the disagreement sets are nested within each branch and disjoint across branches, for gh , gh′ ∈ Gs , k
2 1X gh (Zi ) − gh′ (Zi ) = |th − th′ |. k i=1

√ The coordinates th lie in an interval of length at most q. Hence, for 0 < u ≤ q, the class Gs has an empirical L2 cover of radius u and size at most 1+q/u2 . Applying the chaining argument conditionally to the Rademacher process and retaining the numerical constant in the proof of [12, Section 3.2] gives r Z √q r  k 1X 12 q  (2 + log 2)q Eε sup εi g(Zi ) ≤ √ log 1 + 2 du ≤ 12 . u k k 0 g∈Gs k i=1

+ − Taking expectation over the pvalidation sample and using Eq = P(X ∗∈ As ∪ As ) ≤ 2s shows that the last display is less than 28 s/k. The common translation by 2L(h ) has zero expected Rademacher ∗ sum. Finally, apply the first part of [7, Theorem 3.3] to the class {gp h + 2L(h ) : h ∈ Tp }, with ∗ 2 T (gh + 2L(h )) = Egh (X, Y ) and B = 1. The subroot function s 7→ 28 s/k has fixed point 784/k. Empirical optimality gives k k

1X 1X ∗ gbh (Zi ) + 2L(h ) ≤ gh∗ (Zi ) + 2L(h∗ ) = 2L(h∗ ). k k i=1

i=1

Since the range of this class has length two, the cited theorem shows that, for every fixed K > 1, with probability at least 1 − δ, ∗

2L(h ) K(551936 + 26b) + 22b L(b h) − L(h∗ ) ≤ + , b = log(12/δ). K −1 k p For L(h∗ ) > 0, choose K = 1 + 2L(h∗ )k/(551936 + 26b); for L(h∗ ) = 0, take K = 1 + (551936 + 26b)−1 . Since b ≥ log 12 and 551936 + 26b < 222142b, substitution gives the stated bound. 14

Proof of Theorem 1. For n ≥ 6, let k = ⌊n/3⌋. Form the [−1, 1]-valued predictor pb in (14) from observations 1, . . . , 2k−1, and use the next k observations, 2k, . . . , 3k−1, as an independent validation block. List the distinct values pb(Xi ) on the validation block in increasing order. For each listed value u, include the classifier x 7→ 21{b p(x) ≥ u} − 1, together with the rule identically equal to −1, and choose any empirical risk minimizer b h from this finite list, with ties resolved by a fixed rule. b Consequently, h is an empirical risk minimizer over Tpb. With the fixed rule for resolving ties, b h is a deterministic function of the sample and is the classifier output by the learner. For every x ∈ X and y ∈ {−1, +1}, Z 1 1 1 1{2 1{b p(x) ≥ u} − 1 ̸= y} du = |b p(x) − y|. 2 −1 2 Integrating this identity and applying Fubini’s theorem gives Z
1 1 L x 7→ 21{b p(x) ≥ u} − 1 du = L(b p). 2 −1 Therefore, we have inf h∈Tpb L(h) ≤ L(b p). Condition on the first 2k − 1 observations, so that pb is fixed and the validation block remains i.i.d. Applying Lemma 3.3 with confidence δ/4, and using the preceding inequality, gives ! r L(b p ) log(48/δ) log(48/δ) + . L(b h) ≤ L(b p) + 223000 k k We apply Theorem 3 with confidence δ/16. On the event supplied by this theorem, ! r L∗ (d + log(48/δ)) d + log(48/δ) ∗ L(b p) ≤ L + 17000 + , k k √ √ √ and the inequality a + b ≤ a + b gives r r L(b p) log(48/δ) L∗ log(48/δ) ≤ k k v ! r u ∗ (d + log(48/δ)) u 17000 log(48/δ) L d + log(48/δ) +t + k k k ! r √ L∗ (d + log(48/δ)) d + log(48/δ) + ≤ (1 + 17000) k k ! r L∗ (d + log(48/δ)) d + log(48/δ) < 132 + . k k For the second inequality, we used log(48/δ)/k ≤ (d + log(48/δ))/k, which is at most the expression in parentheses. Substituting these bounds into the validation inequality gives ! r ∗ (d + log(48/δ)) L d + log(48/δ) L(b h) < L∗ + 3.1 · 107 + . k k A union bound shows that the two events hold simultaneously with probability at least 1 − 5δ/16, and hence at least 1 − δ. Since k ≥ n/6, the last display implies (2). When n < 6, return the classifier identically equal to −1. The error term in (2) exceeds one, so the bound is immediate. Finally, suppose that 0 < δ ≤ 1/2. Since d + log(1/δ) ≥ 1 + log 2 and log 48 < 52 (1 + log 2), we
have d + log(48/δ) ≤ 27 d + log(1/δ) . Thus (2) also implies the bound stated in the abstract. 15

Acknowledgements The work of Markus Engelund Mathiasen is supported by the European Union (ERC, TUCLA, 101125203). Views and opinions expressed are those of the authors only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.

References [1] Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy. The One-Inclusion Graph algorithm is not always optimal. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 72–88. PMLR, 2023. URL: https://proceedings. mlr.press/v195/aden-ali23a.html. [2] Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy. Optimal PAC bounds without uniform convergence. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1203–1223, Los Alamitos, CA, USA, 2023. IEEE Computer Society. doi:10.1109/FOCS57990.2023.00071. [3] Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev. Adversarial laws of large numbers and optimal regret in online classification. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pages 447–455, New York, NY, USA, 2021. Association for Computing Machinery. doi:10.1145/3406325.3451041. [4] Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, and Shang-Hua Teng. Regularization and optimal multiclass learning. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 260–310. PMLR, 2024. URL: https://proceedings.mlr.press/ v247/asilis24a.html. [5] Julian Asilis, Mikael Møller Høgsgaard, and Grigoris Velegkas. On agnostic PAC learning in the small error regime. In Advances in Neural Information Processing Systems, volume 38, pages 123346–123388. Curran Associates, Inc., 2025. URL: https: //papers.nips.cc/paper_files/paper/2025/hash/b2a2bd5d5051ff6af52e1ef60aefd255-Abstract-Conference.html. [6] Jean-Yves Audibert. Fast learning rates in statistical inference through aggregation. The Annals of Statistics, 37(4):1591–1646, 2009. doi:10.1214/08-AOS623. [7] Peter L. Bartlett, Olivier Bousquet, and Shahar Mendelson. Local Rademacher complexities. The Annals of Statistics, 33(4):1497–1537, 2005. doi:10.1214/009053605000000282. [8] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik–Chervonenkis dimension. Journal of the ACM, 36(4):929–965, 1989. doi:10.1145/76359.76371. [9] Stéphane Boucheron, Olivier Bousquet, and Gábor Lugosi. Theory of classification: A survey of some recent advances. ESAIM: Probability and Statistics, 9:323–375, 2005. doi:10.1051/ps:2005018. [10] Luc Devroye, László Györfi, and Gábor Lugosi. A Probabilistic Theory of Pattern Recognition, volume 31 of Stochastic Modelling and Applied Probability. Springer, New York, NY, 1996. doi:10.1007/978-1-4612-0711-5. [11] Luc Devroye and Gábor Lugosi. Lower bounds in pattern recognition and learning. Pattern Recognition, 28(7):1011–1018, 1995. doi:10.1016/0031-3203(94)00141-8. [12] Luc Devroye and Gábor Lugosi. Combinatorial Methods in Density Estimation. Springer Series in Statistics. Springer, New York, NY, 2001. doi:10.1007/978-1-4613-0125-7. [13] Reinhard Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, Berlin, Heidelberg, 5th edition, 2017. doi:10.1007/978-3-662-53622-3. [14] Richard M. Dudley. Central limit theorems for empirical measures. The Annals of Probability, 6(6):899–929, 1978. doi:10.1214/aop/1176995384. [15] Shaddin Dughmi, Yusuf Hakan Kalayci, and Grayson York. Is transductive learning equivalent to PAC learning? In Gautam Kamath and Po-Ling Loh, editors, Proceedings of The 36th International Conference on Algorithmic Learning Theory, volume 272 of Proceedings of Machine Learning Research, pages 418–443. PMLR, 2025. URL: https://proceedings.mlr. press/v272/dughmi25a.html. [16] Yuval Filmus, Steve Hanneke, Idan Mehalel, and Shay Moran. Optimal prediction using expert advice and randomized Littlestone dimension. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 773–836. PMLR, 2023. URL: https://proceedings. mlr.press/v195/filmus23a.html. [17] David A. Freedman. On tail probabilities for martingales. The Annals of Probability, 3(1):100–118, 1975. doi:10.1214/aop/ 1176996452. [18] Steve Hanneke. The optimal sample complexity of PAC learning. Journal of Machine Learning Research, 17(38):1–15, 2016. URL: https://www.jmlr.org/papers/v17/15-389.html.

16

[19] Steve Hanneke, Kasper Green Larsen, and Nikita Zhivotovskiy. Revisiting agnostic PAC learning. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1968–1982, Los Alamitos, CA, USA, 2024. IEEE Computer Society. doi:10.1109/FOCS61266.2024.00118. [20] David Haussler, Nick Littlestone, and Manfred K. Warmuth. Predicting {0, 1}-functions on randomly drawn points. Information and Computation, 115(2):248–292, 1994. doi:10.1006/inco.1994.1097. [21] Kasper Green Larsen. Bagging is an optimal PAC learner. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 450–468. PMLR, 2023. URL: https://proceedings.mlr.press/v195/larsen23a.html. [22] Philip M. Long. The complexity of learning according to two models of a drifting environment. Machine Learning, 37(3):337–354, 1999. Expanded version of the paper in the Proceedings of the Eleventh Annual Conference on Computational Learning Theory (COLT 1998), pp. 116–125, doi:10.1145/279943.279968. doi:10.1023/A:1007666507971. [23] Ryan O’Donnell. Analysis of Boolean Functions. Cambridge University Press, New York, NY, 2014. doi:10.1017/ CBO9781139814782. [24] Divit Rawal and Nikita Zhivotovskiy. Majority-of-Three is optimal, 2026. Version 1, submitted 11 June 2026. arXiv: 2606.13614. [25] Hans U. Simon. An almost optimal PAC algorithm. In Peter Grünwald, Elad Hazan, and Satyen Kale, editors, Proceedings of the 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 1552–1563. PMLR, 2015. URL: https://proceedings.mlr.press/v40/Simon15a.html. [26] Leslie G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984. doi:10.1145/1968.1972. [27] Vladimir N. Vapnik and Alexey Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264–280, 1971. doi:10.1137/1116025.

A

Development of the proof and AI disclosure

This project began in spring 2026 while the first author was visiting UC Berkeley. From the outset, the authors sought to combine two ideas. The Boolean cube orientation of Long [22] gives an agnostic leave one out bound of the correct order, but with a coefficient greater than one on the empirical optimum. Dughmi, Kalayci, and York [15] relate the discounted edge density of the agnostic one inclusion graph to empirical Rademacher complexity, using the full coordinate set. An analogy with agnostic online classification also proved useful. Alon, Ben-Eliezer, Dagan, Moran, Naor, and Yogev [3] obtain the optimal horizon dependent regret bound in terms of Littlestone dimension. Filmus, Hanneke, Mehalel, and Moran [16] localize this dependence to thepk mistakes of the best comparator and obtain the optimal randomized expected mistake bound k +Θ( k Ldim(H)+ Ldim(H)). This suggested the localized bound in Lemma 2.1. The main obstacle was whether an isoperimetric result such as Lemma 2.1 could hold at all. In May 2026, the authors used OpenAI GPT-5.5 Pro to study simple VC classes such as thresholds and intervals. In early July, automated runs with the same model suggested an argument for classes of VC dimension one based on their tree structure. The authors then examined axis parallel rectangles. In early August, experiments with GPT-5.6 Sol in Ultra mode helped resolve the rectangle case. These examples led the authors to the general random restriction argument in Lemma 2.1. The PAC conversion combines suffix averaging from Aden-Ali, Cherapanamjeri, Shetty, and Zhivotovskiy [2] with a comparator dependent martingale bound. The single prompt below compresses these experiments. It states Lemma 2.1 without a proof hint and gives more detailed hints for the remaining steps. On August 6, 2026, the authors tested it 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.

17

Full prompt for Theorem 1, GPT-5.6 Sol Pro, August 6, 2026 Let \(\mathcal H\subseteq\{-1,+1\}^{\mathcal X}\) have VC dimension \(d\ge1\). Write \(L(h)=\mathbb P(h(X)\ne Y)\) and \(L^*=\min_{h\in\mathcal H}L(h)\), assuming measurability and attainment. Given an i.i.d. sample of size \(n\), construct a deterministic, generally improper classifier \(\widehat h:\mathcal X\to\{-1,+1\}\), without using \(L^*\) or \(\delta\), such that for every distribution, \(n\ge1\), and \(\delta\in(0,1)\), with probability at least \(1-\delta\), \[ L(\widehat h)\le L^*+C\left( \sqrt{\frac{L^*(d+\log(1/\delta))}{n}} +\frac{d+\log(1/\delta)}{n} \right), \] where \(C>0\) is a universal constant. Give a complete proof. Hints. 1) First construct a coefficient-one fractional orientation of the full Boolean cube. Let \[ V\subseteq\{-1,+1\}^m \] be a finite class with \(\operatorname{VC}(V)\le d\). For \(y\in\{-1,+1\}^m\), define \[ \rho_V(y)=\min_{v\in V}d_H(y,v). \] For \(D\subseteq[m]\), define the projected Rademacher width \[ \operatorname{Rad}_D(V) =\mathbb E_\varepsilon \sup_{v\in V} \sum_{i\in D}\varepsilon_i v_i. \] Prove the following stronger statement. There exist weights \[ w_{y,i}\in[0,1], \qquad y\in\{-1,+1\}^m,\ i\in[m], \] such that \[ w_{y,i}+w_{y^{\oplus i},i}=1 \] for every vertex \(y\) and coordinate \(i\), and such that for every \(y\in\{-1,+1\}^m\) and every coordinate set \(D\subseteq[m]\), \[ \sum_{i\in D}w_{y,i} \le \rho_V(y)+C_1\operatorname{Rad}_D(V). \] 2) For \(U\subseteq\{-1,+1\}^m\), with \(D_U(y)=\{i:y^{\oplus i}\in U\}\) and internal cube edges \(E_U\), deduce \(|E_U|\le\sum_{y\in U}(\rho_V(y)+C_1\operatorname{Rad}_{D_U(y)}(V))\). To localize the Rademacher term, use that \(\rho_V\) is \(1\)-Lipschitz along cube edges, bound the VC dimension of the Hamming neighborhood \(\{y:\rho_V(y)\le t\}\) by \(C(d+t)\), and combine the edge-density bound for VC classes with Cauchy--Schwarz over the level sets of \(\rho_V\). 3) Combine this with \(\operatorname{Rad}_D(V)\le C\sqrt{d|D|}\) and the Hall orientation criterion to obtain \(\operatorname{out}(y)\le\rho_V(y)+C(\sqrt{d\rho_V(y)}+d)\); apply this to the trace of \(\mathcal H\) to obtain a coefficient-one leave-one-out bound. 4) Symmetrize the rule and average over the half-sample suffix \(t=k,\ldots,2k-1\); use a backward martingale to pass from the suffix leave-one-out bounds to the realized held-out errors, and a forward martingale to pass to the population risk; then derandomize by relative validation over the nested threshold classifiers, without a logarithmic factor. Fix all tie rules.

18

Related documents

• Greedy-Like Defective Coloring: Distributed Algorithms and Applications#423920
• Algorithmic Fairness in Computational Medicine#679223
• Decentralized Machine Learning with Centralized Performance Guarantees via Gibbs Algorithms#142680
• Decentralized Machine Learning with Centralized Performance Guarantees via Gibbs Algorithms#124075
• Deterministic and Random Bipartite Matching on General Networks: Convex Flow Reformulation, Asymptotic Properties, and Fast Algorithms#998512