Paper deep dive
An Optimal Agnostic PAC Algorithm
Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 96%
Last extracted: 8/9/2026, 1:55:41 AM
Summary
This paper presents an optimal agnostic PAC learning algorithm that achieves the statistically optimal risk bound for binary classification with finite VC dimension. The authors construct a deterministic, generally improper learner that matches the known lower bounds up to universal constants, settling the sample complexity of agnostic PAC learning. The key technical contribution is a class-dependent edge isoperimetric inequality on the Boolean cube, which allows for an optimal leave-one-out bound via Hall's theorem.
Entities (9)
Relation Signals (7)
Markus Engelund Mathiasen → affiliatedwith → Aarhus University
confidence 100% · Markus Engelund Mathiasen Department of Computer Science, Aarhus University.
Jian Qian → affiliatedwith → The University of Hong Kong
confidence 100% · Jian Qian Division of Artificial Intelligence and Data Science, School of Computing and Data Science, The University of Hong Kong.
Nikita Zhivotovskiy → affiliatedwith → University of California, Berkeley
confidence 100% · Nikita Zhivotovskiy Department of Statistics, University of California, Berkeley.
An Optimal Agnostic PAC Algorithm → achieves → statistically optimal risk bound
confidence 95% · we construct a learner achieving the statistically optimal risk bound
Lemma 2.1 → establishes → class dependent edge isoperimetry
confidence 95% · Lemma 2.1 (Class dependent edge isoperimetry on the Boolean cube).
An Optimal Agnostic PAC Algorithm → matches → lower bounds of Devroye, Györfi, and Lugosi
confidence 95% · matching the lower bounds of Devroye, Györfi, and Lugosi
One-inclusion graph → usedby → Haussler, Littlestone, and Warmuth
confidence 90% · The seminal work of Haussler, Littlestone, and Warmuth is based on the one-inclusion graph
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Let $H\subseteq\{-1,+1\}^X$ be a class of finite VC dimension $d\ge1$. Writing $L$ for the binary risk and $L^*=\min_{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\le 1/2$, with probability at least $1-\delta$, \[ L(\widehat h) \le L^*+ 7\cdot10^8\left( \sqrt{\frac{L^*(d+\log(1/\delta))}{n}} +\frac{d+\log(1/\delta)}{n} \right). \] 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].
Tags
Links
- Source: https://arxiv.org/abs/2608.06363v1
- Canonical: https://arxiv.org/abs/2608.06363v1
PDF not stored locally. Use the link above to view on the source site.
Full Text
61,410 characters extracted from source content.
Expand or collapse full text
An Optimal Agnostic PAC Algorithm Markus Engelund Mathiasen Department of Computer Science, Aarhus University. markusm@cs.au.dk. Jian Qian Division of Artificial Intelligence and Data Science, School of Computing and Data Science, The University of Hong Kong. jianqian@hku.hk. Nikita Zhivotovskiy Department of Statistics, University of California, Berkeley. zhivotovskiy@berkeley.edu. (August 6, 2026) Abstract Let ℋ⊆−1,+1H \-1,+1\^X be a class of finite VC dimension d≥1d≥ 1. Writing L for the binary risk and L∗=minh∈ℋL(h)L^*= _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/20<δ≤ 1/2, with probability at least 1−δ1-δ, L(h^)≤L∗+7⋅108(L∗(d+log(1/δ))n+d+log(1/δ)n).L( h)≤ L^*+7· 10^8 ( L^*(d+ (1/δ))n+ d+ (1/δ)n ). This settles the sample complexity of agnostic PAC learning up to universal constants at every fixed L∗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 [27, 26, 8]. Throughout, let ℋ⊆−1,+1H \-1,+1\^X be a class of measurable hypotheses with VC(ℋ)=d≥1VC(H)=d≥ 1. Let S=((Xi,Yi))i=1nS=((X_i,Y_i))_i=1^n be an i.i.d. sample from the distribution of (X,Y)(X,Y). We write L(h)=ℙ(h(X)≠Y)L(h)=P(h(X)≠ Y) and L∗=minh∈ℋL(h)L^*= _h L(h).111We assume that all maps depending on the data are measurable and that this minimum is attained. Historically, bounds in this setting have been proved by two rather different methods. In the agnostic setting, when L∗L^* is bounded away from zero by a constant, empirical risk minimization is analyzed through classical empirical process methods, including chaining and covering bounds for VC classes. This approach gives the optimal d/n 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/nd/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 [19], building on the work of Simon [25]. Several later constructions also attain the optimal PAC rate, including bagging [21], aggregation of one-inclusion rules [1], 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 lower bounds go back to Devroye, Györfi, and Lugosi [11, 10].222The exact form of (1) is not stated in these references. Within the usual nontrivial boundaries for L∗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]. There is a universal constant c>0c>0 such that, for every learner, including a randomized or improper learner, and every admissible choice of d,n,δd,n,δ, and L∗L^* within the usual nontrivial boundaries, there are an instance space, a class ℋH of VC dimension d, and a distribution satisfying minh∈ℋL(h)=L∗ _h L(h)=L^* for which, with probability at least δ, L(h^)≥L∗+c(L∗(d+log(1/δ))n+d+log(1/δ)n).L( h)≥ L^*+c ( L^*(d+ (1/δ))n+ d+ (1/δ)n ). (1) The probability is over the sample and any internal randomness of the learner. This bound gives the optimal realizable rate when L∗=0L^*=0, the usual agnostic rate when L∗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 [18] proved L(h^)≤L∗+C(L∗(d+log(1/δ))n+log5(n/d)(d+log(1/δ))n),L( h)≤ L^*+C ( L^*(d+ (1/δ))n+ ^5(n/d)(d+ (1/δ))n ), where C>0C>0 is a universal constant. This is suboptimal by the polylogarithmic factor in the fast rate term. By comparison, the ERM bound incurs a multiplicative log(1/L∗) (1/L^*) factor in the VC part of the square root term and a log(n/d) (n/d) factor in the VC part of the fast rate term [9, 18]. Other results give the optimal order when L∗L^* is close to zero, namely when L∗≲(d+log(1/δ))/nL^* (d+ (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∗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∗L^* nor δ and outputs a classifier h^:→−1,+1 h:X→\-1,+1\ such that for every distribution, every n≥1n≥ 1, and every 0<δ<10<δ<1, with probability at least 1−δ1-δ, L(h^)≤L∗+2⋅108(L∗(d+log(48/δ))n+d+log(48/δ)n).L( h)≤ L^*+2· 10^8 ( L^*(d+ (48/δ))n+ d+ (48/δ)n ). (2) 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∗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 [1], 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 one-inclusion analysis. Let P be a nonempty finite coordinate set and let VP=−1,+1PV_P=\-1,+1\^P. For v∈VPv∈ V_P and p∈Pp∈ P, let v⊕pv p be obtained from v by flipping coordinate p. The Boolean cube GP=(VP,EP)G_P=(V_P,E_P) has EP=v,v⊕p:v∈VP,p∈P.E_P= \\v,v p\:v∈ V_P,\ p∈ P \. For U⊆VPU V_P, let EU=e∈EP:e⊆UE_U=\e∈ E_P:e U\ be the cube edges with both endpoints in U. For v∈VPv∈ V_P, let DU(v)=p∈P:v⊕p∈UD_U(v)=\p∈ P:v p∈ U\ be the coordinate directions from v to a neighbor in U. Thus GP[U]=(U,EU)G_P[U]=(U,E_U) and degU(v)=|DU(v)| _U(v)=|D_U(v)| for v∈Uv∈ U. In particular, GP[ℱ]G_P[F] is the one-inclusion graph of a trace ℱ⊆VPF V_P [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⊆VPU V_P will be the cuts in the Hall condition below. Fix a nonempty ℱ⊆VPF V_P with VC(ℱ)≤dVC(F)≤ d. For u,v∈VPu,v∈ V_P, define their disagreement set by DIS(u,v)=p∈P:u(p)≠v(p)DIS(u,v)=\p∈ P:u(p)≠ v(p)\. The Hamming distance from v to ℱF is ρℱ(v)=minf∈ℱ|DIS(v,f)|. _F(v)= _f |DIS(v,f)|. For every v,v′∈VPv,v ∈ V_P with |DIS(v,v′)|=1|DIS(v,v )|=1, the triangle inequality gives |ρℱ(v)−ρℱ(v′)|≤1.| _F(v)- _F(v )|≤ 1. (3) For D⊆PD P, let ℜD(ℱ)=εmaxf∈ℱ∑p∈Dεpf(p) R_D(F)=E_ _f _p∈ D _pf(p) be the unnormalized signed Rademacher width of the projection ℱ|DF|_D. Keeping the constants in the chaining and covering arguments of Devroye and Lugosi [12, Sections 3.2 and 4.3] gives ℜD(ℱ)≤60d|D|. R_D(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]w_v,p∈[0,1], fixed simultaneously for all v∈VPv∈ V_P and p∈Pp∈ P with the following properties. The first relation below holds for every v∈VPv∈ V_P and p∈Pp∈ P, and the second for every v∈VPv∈ V_P and D⊆PD P: wv,p+wv⊕p,p=1, w_v,p+w_v p,p=1, (5) ∑p∈Dwv,p≤ρℱ(v)+ℜD(ℱ). _p∈ Dw_v,p≤ _F(v)+ R_D(F). (6) Consequently, for every U⊆VPU V_P, the induced subgraph satisfies the localized edge bound |EU|≤∑v∈U(ρℱ(v)+ℜDU(v)(ℱ)).|E_U|≤ _v∈ U ( _F(v)+ R_D_U(v)(F) ). (7) Proof. Let T contain each coordinate of P independently with probability 1/21/2. Since ℱF is finite, fix any order on it. For each T⊆PT P, let πT(v) _T(v) be the first member of ℱF minimizing |DIS(v,f)∩T||DIS(v,f)∩ T|. In particular, v|T=v′|TimpliesπT(v)=πT(v′).v|_T=v |_T _T(v)= _T(v ). (8) Define the weights wv,p=ℙT(p∈DIS(v,πT(v))∣p∉T).w_v,p=P_T (p (v, _T(v)) p∉ T ). (9) Clearly wv,p∈[0,1]w_v,p∈[0,1]. Suppose p∉Tp∉ T. Then v|T=v⊕p|Tv|_T=v p|_T, so (8) gives πT(v)=πT(v⊕p). _T(v)= _T(v p). The labelings v and v⊕pv p have opposite labels at p, while this common fit has one fixed label there. Hence p∈DIS(v,πT(v))+p∈DIS(v⊕p,πT(v⊕p))=1.1\p (v, _T(v))\+1\p (v p, _T(v p))\=1. Taking conditional expectation given p∉Tp∉ T proves (5). It remains to prove (6). Fix v∈VPv∈ V_P and D⊆PD P, and set εp=+1,p∉T,−1,p∈T. _p= cases+1,&p∉ T,\\ -1,&p∈ T. cases Then (εp)p∈P( _p)_p∈ P are independent Rademacher signs. First, ∑p∈Dwv,p=2T|DIS(v,πT(v))∩D∩Tc|. _p∈ Dw_v,p=2E_T |DIS(v, _T(v))∩ D∩ T^c |. Indeed, ℙT(p∉T)=1/2P_T(p∉ T)=1/2, so the conditional probability in (9) equals twice the corresponding unconditional probability. Next, applying the pointwise identity |B∩D∩Tc|=|B∩D∩T|+∑p∈Dεpp∈B|B∩ D∩ T^c|=|B∩ D∩ T|+ _p∈ D _p1\p∈ B\ to B=DIS(v,πT(v))B=DIS(v, _T(v)) gives ∑p∈Dwv,p _p∈ Dw_v,p =2T|DIS(v,πT(v))∩D∩T|+2T∑p∈Dεpp∈DIS(v,πT(v)) =2E_T |DIS(v, _T(v))∩ D∩ T |+2E_T _p∈ D _p1\p (v, _T(v))\ ≤2T|DIS(v,πT(v))∩T|+2Tmaxf∈ℱ∑p∈Dεpp∈DIS(v,f). ≤ 2E_T |DIS(v, _T(v))∩ T |+2E_T _f _p∈ D _p1\p (v,f)\. (10) For the first term, we dropped the restriction to D; for the second, we replaced the particular choice πT(v)∈ℱ _T(v) by the maximum over f∈ℱf . By the definition of πT(v) _T(v), 2T|DIS(v,πT(v))∩T| 2E_T |DIS(v, _T(v))∩ T | =2Tminf∈ℱ|DIS(v,f)∩T| =2E_T _f |DIS(v,f)∩ T| ≤minf∈ℱ2T|DIS(v,f)∩T|=ρℱ(v). ≤ _f 2E_T|DIS(v,f)∩ T|= _F(v). Meanwhile, since 2p∈DIS(v,f)=1−v(p)f(p),21\p (v,f)\=1-v(p)f(p), we have 2Tmaxf∈ℱ∑p∈Dεpp∈DIS(v,f) 2E_T _f _p∈ D _p1\p (v,f)\ =T∑p∈Dεp+Tmaxf∈ℱ∑p∈D(−εpv(p))f(p) =E_T _p∈ D _p+E_T _f _p∈ D(- _pv(p))f(p) =ℜD(ℱ). = R_D(F). Here T∑p∈Dεp=0E_T _p∈ D _p=0, and (−εpv(p))p∈D(- _pv(p))_p∈ D are again independent Rademacher signs. Combining the last two displays with (10) proves (6). Finally, every edge v,v⊕p∈EU\v,v p\∈ E_U contributes wv,p+wv⊕p,p=1w_v,p+w_v p,p=1 to the incidence sum. Hence we have |EU|=∑v∈U∑p∈DU(v)wv,p.|E_U|= _v∈ U _p∈ D_U(v)w_v,p. Applying (6) with D=DU(v)D=D_U(v) and summing over v∈Uv∈ U proves (7). ∎ Remark 2.2 (Relation to cube edge isoperimetry). For every nonempty U⊆VPU V_P, the edge isoperimetric inequality on the cube [23, Theorem 2.39] gives |EU|≤|U|2log2|U|.|E_U|≤ |U|2 _2|U|. For a subcube of dimension k, both sides equal k2k−1k2^k-1. Lemma˜2.1 gives instead the following localized bound relative to any ℱ⊆VPF V_P: |EU|≤∑v∈U(ρℱ(v)+ℜDU(v)(ℱ)).|E_U|≤ _v∈ U ( _F(v)+ R_D_U(v)(F) ). The quantity on the right depends on the position of U relative to ℱF and on the internal coordinate sets DU(v)D_U(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⊆ℱU , Haussler, Littlestone, and Warmuth [20] proved |EU|≤VC(U)|U|≤d|U|.|E_U| (U)|U|≤ d|U|. The inclusion U⊆ℱU is essential for the second inequality and leaves an arbitrary U⊆VPU V_P uncontrolled by d alone. • Long’s cube orientation [22, Lemmas 15 and 16] applies to every U⊆VPU V_P and gives |EU|≤15∑v∈U(d+ρℱ(v)).|E_U|≤ 15 _v∈ U (d+ _F(v) ). The construction uses distance shells but does not give a Rademacher width restricted to a coordinate set. More importantly, the coefficient 1515 on ρℱ(v) _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⊆PD P. • For every U⊆VPU V_P, Dughmi, Kalayci, and York prove the all-coordinate bound |EU|≤∑v∈Uρℱ(v)+|U|2ℜP(ℱ),|E_U|≤ _v∈ U _F(v)+ |U|2 R_P(F), with equality for U=VPU=V_P; see [15, Lemmas 8 and 9, and Section 3.4]. Their inequality uses the single full width ℜP(ℱ) R_P(F). Lemma˜2.1 instead controls one assignment for every D⊆PD P, allowing the vertexwise choice D=DU(v)D=D_U(v). 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)G=(V,E) chooses a head σ(e)∈eσ(e)∈ e for each edge. Its outdegree at x is out(x;σ)=|e∈E:x∈e,σ(e)≠x|out(x;σ)=|\e∈ E:x∈ e,\ σ(e)≠ x\|. For W⊆VW V, write EG(W)=e∈E:e⊆WE_G(W)=\e∈ E:e W\. A form of Hall’s theorem states that if integer capacities cx≥0c_x≥ 0 satisfy the following inequality for every W⊆VW V, |EG(W)|≤∑x∈Wcx,|E_G(W)|≤ _x∈ Wc_x, then every edge can be assigned to one endpoint so that, for every x∈Vx∈ V, at most cxc_x edges are assigned to x [13, Theorem 2.1.2]. Taking the assigned endpoint as the tail gives an orientation with outdegree at most cxc_x. 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))i=1n∈(×−1,+1)nS=((x_i,y_i))_i=1^n∈(X×\-1,+1\)^n, a leave-one-out rule observes all inputs and all labels except yiy_i when predicting y^i y_i. We denote L^S∗=1nminh∈ℋ∑i=1nh(xi)≠yi,andL^SLOO=1n∑i=1ny^i≠yi. L_S^*= 1n _h _i=1^n1\h(x_i)≠ y_i\, L_S^LOO= 1n _i=1^n1\ y_i≠ y_i\. Theorem 2 (Orientation of the cube and the leave-one-out bound). Let P be a nonempty finite coordinate set, let d≥1d≥ 1, and let ∅≠ℱ⊆VP V_P satisfy VC(ℱ)≤dVC(F)≤ d. There is a deterministic orientation σ of the full cube such that, for every v∈VPv∈ V_P, out(v;σ)≤ρℱ(v)+120dρℱ(v)+7202d.out(v;σ)≤ _F(v)+120 d _F(v)+7202d. (11) Consequently, for every n≥1n≥ 1 and every input sequence x1,…,xnx_1,…,x_n, 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,+1n(y_1,…,y_n)∈\-1,+1\^n, L^SLOO≤L^S∗+120dL^S∗n+7202dn. L_S^LOO≤ L_S^*+120 d L_S^*n+7202 dn. (12) Proof. Fix a nonempty U⊆VPU V_P. By (5), we have |EU|=∑v∈U∑p∈DU(v)wv,p.|E_U|= _v∈ U _p∈ D_U(v)w_v,p. For every v∈Uv∈ U, (6) and (4) give ∑p∈DU(v)wv,p≤ρℱ(v)+60ddegU(v)≤ρℱ(v)+3601d+9003601degU(v). _p∈ D_U(v)w_v,p≤ _F(v)+60 d _U(v)≤ _F(v)+3601d+ 9003601 _U(v). The last step uses the elementary inequality ab≤(a+b)/2 ab≤(a+b)/2. Relabel the endpoints of an edge v,v⊕p∈EU\v,v p\∈ E_U so that ρℱ(v)≤ρℱ(v⊕p) _F(v)≤ _F(v p). By (3) and 1+x≤1+x/2 1+x≤ 1+x/2 for x≥0x≥ 0, 1/ρℱ(v)+3601d1/ρℱ(v⊕p)+3601d≤1+13601d≤1+17202d. 1/ _F(v)+3601d1/ _F(v p)+3601d≤ 1+ 13601d≤ 1+ 17202d. Consequently, |1ρℱ(v)+3601d−1ρℱ(v⊕p)+3601d|≤17202dmin(1ρℱ(v)+3601d,1ρℱ(v⊕p)+3601d). | 1 _F(v)+3601d- 1 _F(v p)+3601d |≤ 17202d ( 1 _F(v)+3601d, 1 _F(v p)+3601d ). By (5), it holds that 1ρℱ(v)+3601d+1ρℱ(v⊕p)+3601d 1 _F(v)+3601d+ 1 _F(v p)+3601d =2(wv,pρℱ(v)+3601d+wv⊕p,pρℱ(v⊕p)+3601d) =2 ( w_v,p _F(v)+3601d+ w_v p,p _F(v p)+3601d ) +(wv⊕p,p−wv,p)(1ρℱ(v)+3601d−1ρℱ(v⊕p)+3601d) +(w_v p,p-w_v,p) ( 1 _F(v)+3601d- 1 _F(v p)+3601d ) ≤(2+17202d)(wv,pρℱ(v)+3601d+wv⊕p,pρℱ(v⊕p)+3601d). ≤ (2+ 17202d ) ( w_v,p _F(v)+3601d+ w_v p,p _F(v p)+3601d ). The last step uses |wv⊕p,p−wv,p|≤1|w_v p,p-w_v,p|≤ 1 and the fact that the weighted average is at least the smaller reciprocal. Summing this inequality over EUE_U and applying the preceding bound gives ∑v∈UdegU(v)ρℱ(v)+3601d _v∈ U _U(v) _F(v)+3601d ≤(2+17202d)∑v∈U∑p∈DU(v)wv,pρℱ(v)+3601d ≤ (2+ 17202d ) _v∈ U _p∈ D_U(v)w_v,p _F(v)+3601d ≤(2+17202d)∑v∈U(ρℱ(v)+3601d+9003601degU(v)ρℱ(v)+3601d). ≤ (2+ 17202d ) _v∈ U ( _F(v)+3601d+ 9003601 _U(v) _F(v)+3601d ). Moving the last term to the left gives (1−9003601(2+17202d))∑v∈UdegU(v)ρℱ(v)+3601d≤(2+17202d)∑v∈Uρℱ(v)+3601d. (1- 9003601 (2+ 17202d ) ) _v∈ U _U(v) _F(v)+3601d≤ (2+ 17202d ) _v∈ U _F(v)+3601d. For d≥1d≥ 1, 2+1/(7202d)1−(900/3601)(2+1/(7202d))<4. 2+1/(7202d)1-(900/3601)(2+1/(7202d))<4. Dividing the preceding inequality therefore gives ∑v∈UdegU(v)ρℱ(v)+3601d<4∑v∈Uρℱ(v)+3601d. _v∈ U _U(v) _F(v)+3601d<4 _v∈ U _F(v)+3601d. Cauchy-Schwarz inequality now yields ∑v∈UdegU(v)≤(∑v∈UdegU(v)ρℱ(v)+3601d)1/2(∑v∈Uρℱ(v)+3601d)1/2<2∑v∈Uρℱ(v)+3601d. _v∈ U _U(v)≤ ( _v∈ U _U(v) _F(v)+3601d )^1/2 ( _v∈ U _F(v)+3601d )^1/2<2 _v∈ U _F(v)+3601d. Finally, we have |EU|≤∑v∈U(ρℱ(v)+60ddegU(v))<∑v∈U(ρℱ(v)+120d(ρℱ(v)+3601d)).|E_U|≤ _v∈ U ( _F(v)+60 d _U(v) )< _v∈ U ( _F(v)+120 d ( _F(v)+3601d ) ). The empty set satisfies the same bound trivially. Hence Hall’s theorem, with integer capacity ⌈ρℱ(v)+120d(ρℱ(v)+3601d)⌉ _F(v)+120 d( _F(v)+3601d) at v, gives an orientation such that, using ⌈x⌉<x+1 x <x+1 and x+y≤x+y x+y≤ x+ y, out(v;σ)<ρℱ(v)+120dρℱ(v)+1203601d+1<ρℱ(v)+120dρℱ(v)+7202d.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). For the leave-one-out statement, apply the orientation result with P=1,…,nP=\1,…,n\ to the trace ℱ=(h(x1),…,h(xn)):h∈ℋ.F= \(h(x_1),…,h(x_n)):h \. Write vy=(y1,…,yn)∈VPv_y=(y_1,…,y_n)∈ V_P. 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,…,ni∈\1,…,n\, and the observed labels (yj)j≠i(y_j)_j≠ i. Output: A prediction y^i∈−1,+1 y_i∈\-1,+1\. For the held-out coordinate i, predict as follows. 1: Fix coordinate j at yjy_j for every j≠ij≠ i. 2: Complete coordinate i with each of its two signs; the two completions form a cube edge. 3: Set y^i y_i 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 nL^SLOO=out(vy;σ).n L_S^LOO=out(v_y;σ). Since ρℱ(vy)=nL^S∗ _F(v_y)=n L_S^* and VC(ℱ)≤dVC(F)≤ d, dividing (11) by n proves (12). ∎ 3 From leave-one-out to PAC bounds Let P be a distribution on ×−1,+1X×\-1,+1\. We identify a randomized binary predictor with its measurable conditional mean g:→[−1,1]g:X→[-1,1]: on input x, it predicts +1+1 with probability (1+g(x))/2(1+g(x))/2. We write ℓ(a,y)=|a−y|/2 (a,y)=|a-y|/2 and extend the notation L to the risk of such a score: L(g)=(X,Y)∼Pℓ(g(X),Y)=12(X,Y)∼P|g(X)−Y|.L(g)=E_(X,Y) P (g(X),Y)= 12E_(X,Y) P|g(X)-Y|. For −1,+1\-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)q(x;S) be the expectation of the resulting signed prediction over this permutation. The score q(x;S)∈[−1,1]q(x;S)∈[-1,1] is deterministic and symmetric in the observations of S. For a labeled sample S=((xi,yi))i=1mS=((x_i,y_i))_i=1^m, write S−iS^-i for the sample with observation i removed. Averaging (12) over all permutations gives, for every S, 12m∑i=1m|q(xi;S−i)−yi|≤L^S∗+120dL^S∗m+7202dm. 12m _i=1^m|q(x_i;S^-i)-y_i|≤ L_S^*+120 d L_S^*m+7202 dm. (13) 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 [1] 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∗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 [2]. 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≥1k≥ 1. Let Zi=(Xi,Yi)Z_i=(X_i,Y_i), i=1,…,2ki=1,…,2k, be i.i.d. observations and write S≤t=(Z1,…,Zt)S_≤ t=(Z_1,…,Z_t). For k≤t≤2k−1k≤ t≤ 2k-1, set qt(x)=q(x;S≤t)q_t(x)=q(x;S_≤ t), where q is the symmetrized leave-one-out score satisfying (13). The randomized predictor averages the scores qtq_t over the suffix of training times t=k,…,2k−1t=k,…,2k-1. Its conditional mean is p^(x)=1k∑t=k2k−1qt(x). p(x)= 1k _t=k^2k-1q_t(x). (14) Thus it predicts +1+1 with probability (1+p^(x))/2(1+ p(x))/2 and, by linearity, L(p^)=k−1∑t=k2k−1L(qt)L( p)=k^-1 _t=k^2k-1L(q_t). Only Z1,…,Z2k−1Z_1,…,Z_2k-1 enter the construction of p p. The additional observation Z2kZ_2k is the fresh point used to analyze q2k−1q_2k-1 and does not enter the learner. Derandomization is deferred to the next subsection. For every h∈ℋh , linearity gives L(p^)−L(h)=1k∑t=k2k−1(L(qt)−L(h)).L( p)-L(h)= 1k _t=k^2k-1 (L(q_t)-L(h) ). (15) As in [1], 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)Z_i=(X_i,Y_i), 1≤i≤2k1≤ i≤ 2k, be i.i.d. observations, and let qt(x)=q(x;(Z1,…,Zt))q_t(x)=q(x;(Z_1,…,Z_t)), where q is the deterministic symmetric score satisfying (13). Fix h∈ℋh and, for k≤t≤2k−1k≤ t≤ 2k-1, let Δt+1,h=ℓ(qt(Xt+1),Yt+1)−h(Xt+1)≠Yt+1. _t+1,h= (q_t(X_t+1),Y_t+1)-1\h(X_t+1)≠ Y_t+1\. For every 0<δ≤1/30<δ≤ 1/3, with probability at least 1−2δ1-2δ, 1kmax(∑m=k+12kΔm,h,0)≤8200(L(h)(d+log(1/δ))k+d+log(1/δ)k). 1k ( _m=k+1^2k _m,h,0 )≤ 8200 ( L(h)(d+ (1/δ))k+ d+ (1/δ)k ). (16) Lemma 3.2 (Forward martingale). Under the assumptions and notation of Lemma˜3.1, for every 0<δ≤1/30<δ≤ 1/3, with probability at least 1−δ1-δ, 1k∑t=k2k−1(L(qt)−L(h))≤2kmax(∑m=k+12kΔm,h,0)+5L(h)log(1/δ)k+10log(1/δ)k. 1k _t=k^2k-1 (L(q_t)-L(h) )≤ 2k ( _m=k+1^2k _m,h,0 )+5 L(h) (1/δ)k+10 (1/δ)k. (17) Theorem 3 (The optimal risk bound for the randomized predictor). The predictor p^:→[−1,1] p:X→[-1,1] in (14) is constructed from 2k−12k-1 i.i.d. observations and depends on neither L∗L^* nor δ. For every 0<δ<10<δ<1, with probability at least 1−δ1-δ, L(p^)≤L∗+17000(L∗(d+log(3/δ))k+d+log(3/δ)k).L( p)≤ L^*+17000 ( L^*(d+ (3/δ))k+ d+ (3/δ)k ). (18) Proof of Theorem˜3. Choose h∗∈ℋh^* with L(h∗)=L∗L(h^*)=L^*. Apply Lemmas˜3.1 and 3.2 with confidence δ/3δ/3. A union bound shows that both conclusions hold simultaneously with probability at least 1−δ1-δ. On this event, L(p^)−L∗ L( p)-L^* =1k∑t=k2k−1(L(qt)−L∗) = 1k _t=k^2k-1 (L(q_t)-L^* ) ≤2kmax(∑m=k+12kΔm,h∗,0)+5L∗log(3/δ)k+10log(3/δ)k ≤ 2k ( _m=k+1^2k _m,h^*,0 )+5 L^* (3/δ)k+10 (3/δ)k ≤16400(L∗(d+log(3/δ))k+d+log(3/δ)k)+5L∗log(3/δ)k+10log(3/δ)k ≤ 16400 ( L^*(d+ (3/δ))k+ d+ (3/δ)k )+5 L^* (3/δ)k+10 (3/δ)k <17000(L∗(d+log(3/δ))k+d+log(3/δ)k). <17000 ( L^*(d+ (3/δ))k+ d+ (3/δ)k ). The claim follows. ∎ Proof of Lemma˜3.1. Fix h∈ℋh and 0<δ≤1/30<δ≤ 1/3. The independent permutation below exploits the symmetry of q. Conditional on the observations, exposing the permutation backward makes the next removed observation uniform among those that remain. Draw i.i.d. observations Wi=(X~i,Y~i)W_i=( X_i, Y_i), 1≤i≤2k1≤ i≤ 2k, and an independent uniform permutation π of 1,…,2k\1,…,2k\. Set Zm=Wπ(m)Z_m=W_π(m). For k≤m≤2k≤ m≤ 2k, let ℛmR_m be the σ-algebra generated by the complete sample and the permutation indices already exposed at positions 2k,…,m+12k,…,m+1: ℛm=σ(W1,…,W2k,π(j):m<j≤2k).R_m=σ (W_1,…,W_2k,π(j):m<j≤ 2k ). Thus ℛmR_m reveals which m indices remain, but not their order. Let ImI_m be the set of these indices and write Bm=(Wi)i∈ImB_m=(W_i)_i∈ I_m in any fixed order. For i∈Imi∈ I_m, let Bm−iB_m^-i be obtained from BmB_m by deleting WiW_i. Conditional on ℛmR_m, the index π(m)π(m) is uniform on ImI_m. Because q is symmetric, if π(m)=iπ(m)=i, then the first m−1m-1 observations give the same prediction as q(⋅;Bm−i)q(\,·\,;B_m^-i). For i∈Imi∈ I_m, let Δi,m,h=ℓ(q(X~i;Bm−i),Y~i)−h(X~i)≠Y~i. _i,m,h= (q( X_i;B_m^-i), Y_i )-1\h( X_i)≠ Y_i\. It follows that Δm,h=Δπ(m),m,h _m,h= _π(m),m,h and [Δm,h∣ℛm]=1m∑i∈ImΔi,m,h.E[ _m,h _m]= 1m _i∈ I_m _i,m,h. After π(m)π(m) is revealed, Δm,h _m,h is measurable with respect to ℛm−1R_m-1. Hence, as m runs from 2k2k down to k+1k+1, Δm,h−[Δm,h∣ℛm] _m,h-E[ _m,h _m] forms a martingale difference sequence with respect to the reverse filtration. The empirical optimum on BmB_m is at most the empirical loss of h. Applying (13) to BmB_m and subtracting the empirical loss of h gives [Δm,h∣ℛm]≤120d∑i∈Imh(X~i)≠Y~im+7202dm≤120d∑i=12kh(X~i)≠Y~ik+7202dk,E[ _m,h _m]≤ 120 d _i∈ I_m1\h( X_i)≠ Y_i\m+7202 dm≤ 120 d _i=1^2k1\h( X_i)≠ Y_i\k+7202 dk, (19) where the last inequality uses m≥km≥ k and bounds the sum over ImI_m by the sum over the complete sample. For the conditional second moment, applying (a−b)2≤a+b(a-b)^2≤ a+b, valid for a∈[0,1]a∈[0,1] and b∈0,1b∈\0,1\, to the two losses, averaging over the uniform choice of i∈Imi∈ I_m, and using (13) again gives [Δm,h2∣ℛm] [ _m,h^2 _m] ≤2m∑i∈Imh(X~i)≠Y~i+120d∑i∈Imh(X~i)≠Y~im+7202dm ≤ 2m _i∈ I_m1\h( X_i)≠ Y_i\+120 d _i∈ I_m1\h( X_i)≠ Y_i\m+7202 dm ≤2k∑i=12kh(X~i)≠Y~i+120d∑i=12kh(X~i)≠Y~ik+7202dk. ≤ 2k _i=1^2k1\h( X_i)≠ Y_i\+120 d _i=1^2k1\h( X_i)≠ Y_i\k+7202 dk. (20) The number of errors made by h on the complete sample is distributed as Bin(2k,L(h))Bin(2k,L(h)). Bernstein’s inequality and 2kL(h)log(1/δ)≤kL(h)+log(1/δ)2 kL(h) (1/δ)≤ kL(h)+ (1/δ) imply that, with probability at least 1−δ1-δ, 1k∑i=12kh(X~i)≠Y~i≤3(L(h)+log(1/δ)k). 1k _i=1^2k1\h( X_i)≠ Y_i\≤ 3 (L(h)+ (1/δ)k ). (21) On the event in (21), 120d∑i=12kh(X~i)≠Y~ik+7202dk 120 d _i=1^2k1\h( X_i)≠ Y_i\k+7202 dk ≤1203d(L(h)+log(1/δ)/k)k+7202dk ≤ 120 3d(L(h)+ (1/δ)/k)k+7202 dk ≤8000(L(h)(d+log(1/δ))k+d+log(1/δ)k). ≤ 8000 ( L(h)(d+ (1/δ))k+ d+ (1/δ)k ). (22) Conditionally on W1,…,W2kW_1,…,W_2k, we apply Freedman’s inequality [17] to the preceding martingale differences, with m read in decreasing order. By (20), their predictable quadratic variation satisfies ∑m=k+12k[(Δm,h−[Δm,h∣ℛm])2|ℛm]≤2∑i=12kh(X~i)≠Y~i+120d∑i=12kh(X~i)≠Y~i+7202d, _m=k+1^2kE [ ( _m,h-E[ _m,h _m] )^2 |R_m ]≤ 2 _i=1^2k1\h( X_i)≠ Y_i\+120 d _i=1^2k1\h( X_i)≠ Y_i\+7202d, and |Δm,h−[Δm,h∣ℛm]|≤2| _m,h-E[ _m,h _m]|≤ 2. Moreover, summing (19) over m=k+1,…,2km=k+1,…,2k gives ∑m=k+12k[Δm,h∣ℛm]≤120d∑i=12kh(X~i)≠Y~i+7202d. _m=k+1^2kE[ _m,h _m]≤ 120 d _i=1^2k1\h( X_i)≠ Y_i\+7202d. Therefore, conditionally on W1,…,W2kW_1,…,W_2k, with probability at least 1−δ1-δ, 1k∑m=k+12kΔm,h 1k _m=k+1^2k _m,h ≤120d∑i=12kh(X~i)≠Y~ik+7202dk ≤ 120 d _i=1^2k1\h( X_i)≠ Y_i\k+7202 dk +(4k∑i=12kh(X~i)≠Y~i+240d∑i=12kh(X~i)≠Y~ik+14404dk)log(1/δ)k + ( 4k _i=1^2k1\h( X_i)≠ Y_i\+240 d _i=1^2k1\h( X_i)≠ Y_i\k+14404 dk ) (1/δ)k +2log(1/δ)3k. + 2 (1/δ)3k. (23) It remains to simplify the square root term. On the event in (21), (22) gives (4k∑i=12kh(X~i)≠Y~i+240d∑i=12kh(X~i)≠Y~ik+14404dk)log(1/δ)k ( 4k _i=1^2k1\h( X_i)≠ Y_i\+240 d _i=1^2k1\h( X_i)≠ Y_i\k+14404 dk ) (1/δ)k ≤12L(h)log(1/δ)k+12(log(1/δ)k)2 ≤ 12 L(h) (1/δ)k+12 ( (1/δ)k )^2 +16000(L(h)(d+log(1/δ))k+d+log(1/δ)k)log(1/δ)k +16000 ( L(h)(d+ (1/δ))k+ d+ (1/δ)k ) (1/δ)k ≤16024(L(h)(d+log(1/δ))k+d+log(1/δ)k)2. ≤ 16024 ( L(h)(d+ (1/δ))k+ d+ (1/δ)k )^2. The last inequality follows because both L(h)log(1/δ)/k L(h) (1/δ)/k and log(1/δ)/k (1/δ)/k are bounded by the parenthesized expression. Substituting these bounds into (23) gives 1k∑m=k+12kΔm,h 1k _m=k+1^2k _m,h ≤8000(L(h)(d+log(1/δ))k+d+log(1/δ)k) ≤ 8000 ( L(h)(d+ (1/δ))k+ d+ (1/δ)k ) +16024(L(h)(d+log(1/δ))k+d+log(1/δ)k)+2log(1/δ)3k + 16024 ( L(h)(d+ (1/δ))k+ d+ (1/δ)k )+ 2 (1/δ)3k <8200(L(h)(d+log(1/δ))k+d+log(1/δ)k). <8200 ( L(h)(d+ (1/δ))k+ d+ (1/δ)k ). The event in (21) has probability at least 1−δ1-δ, and averaging the conditional Freedman bound shows that (23) holds with probability at least 1−δ1-δ. Thus both bounds hold simultaneously with probability at least 1−2δ1-2δ. On their intersection, taking the positive part in the preceding display gives (16). Since (Z1,…,Z2k)(Z_1,…,Z_2k) has the original i.i.d. law, the proof follows. ∎ Proof of Lemma˜3.2. Fix h∈ℋh and 0<δ≤1/30<δ≤ 1/3. Conditionally on S≤tS_≤ t, the prediction qtq_t is fixed and Zt+1Z_t+1 is an independent observation. Hence [Δt+1,h∣S≤t]=L(qt)−L(h).E[ _t+1,h S_≤ t]=L(q_t)-L(h). Since (a−b)2≤a+b(a-b)^2≤ a+b for a,b∈[0,1]a,b∈[0,1], applying this inequality to the losses of qtq_t and h gives Var(Δt+1,h∣S≤t)≤[Δt+1,h2∣S≤t]≤L(qt)+L(h)=L(qt)−L(h)+2L(h).Var( _t+1,h S_≤ t) [ _t+1,h^2 S_≤ t]≤ L(q_t)+L(h)=L(q_t)-L(h)+2L(h). (24) Therefore ξt+1,h=L(qt)−L(h)−Δt+1,h _t+1,h=L(q_t)-L(h)- _t+1,h is a martingale difference with respect to the sample prefixes. It satisfies ξt+1,h≤2 _t+1,h≤ 2 and, by (24), [ξt+1,h2∣S≤t]≤L(qt)−L(h)+2L(h).E[ _t+1,h^2 S_≤ t]≤ L(q_t)-L(h)+2L(h). Fix 0<λ<3/20<λ<3/2. The Bernstein moment generating bound gives [exp(λξt+1,h−λ22(1−2λ/3)(L(qt)−L(h)+2L(h)))|S≤t]≤1.E [ (λ _t+1,h- λ^22(1-2λ/3) (L(q_t)-L(h)+2L(h) ) ) | S_≤ t ]≤ 1. Iterating this inequality over t and applying Markov’s inequality shows that, with probability at least 1−δ1-δ, ∑t=k2k−1(L(qt)−L(h))−∑m=k+12kΔm,h≤λ2(1−2λ/3)(∑t=k2k−1(L(qt)−L(h))+2kL(h))+log(1/δ)λ. _t=k^2k-1 (L(q_t)-L(h) )- _m=k+1^2k _m,h≤ λ2(1-2λ/3) ( _t=k^2k-1 (L(q_t)-L(h) )+2kL(h) )+ (1/δ)λ. (25) Choose λ=min(12,log(1/δ)kL(h))λ= ( 12, (1/δ)kL(h) ) when L(h)>0L(h)>0, and λ=1/2λ=1/2 when L(h)=0L(h)=0. Since λ≤1/2λ≤ 1/2, simple algebra gives 1k∑t=k2k−1(L(qt)−L(h))≤2kmax(∑m=k+12kΔm,h,0)+3λL(h)+2log(1/δ)λk. 1k _t=k^2k-1 (L(q_t)-L(h) )≤ 2k ( _m=k+1^2k _m,h,0 )+3λ L(h)+2 (1/δ)λ k. (26) If λ=log(1/δ)/(kL(h))λ= (1/δ)/(kL(h)), the last two terms in (26) equal 3L(h)log(1/δ)k+2L(h)log(1/δ)k=5L(h)log(1/δ)k.3 L(h) (1/δ)k+2 L(h) (1/δ)k=5 L(h) (1/δ)k. If λ=1/2λ=1/2, then L(h)≤4log(1/δ)/kL(h)≤ 4 (1/δ)/k, and 3λL(h)+2log(1/δ)λk=32L(h)+4log(1/δ)k≤10log(1/δ)k.3λ L(h)+2 (1/δ)λ k= 32L(h)+4 (1/δ)k≤ 10 (1/δ)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 [1]. Such a factor is harmless when L∗=0L^*=0, but would lose the coefficient one on L∗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:→[−1,1]p:X→[-1,1] be measurable and fixed independently of an i.i.d. validation sample Zi=(Xi,Yi)Z_i=(X_i,Y_i), 1≤i≤k1≤ i≤ k, where k≥1k≥ 1. Consider the binary threshold class p=x↦2p(x)≥u−1:−1≤u≤1∪x↦−1.T_p= \x 21\p(x)≥ u\-1:-1≤ u≤ 1 \∪\x -1\. If h h is an empirical risk minimizer over pT_p, then, for every 0<δ<10<δ<1, with probability at least 1−δ1-δ, L(h^)≤infh∈pL(h)+223000(infh∈pL(h)log(12/δ)k+log(12/δ)k).L( h)≤ _h _pL(h)+223000 ( _h _pL(h) (12/δ)k+ (12/δ)k ). Proof. Assume first that the infimum is attained and let h∗h^* be a minimizer. Otherwise, take h∗h^* with risk arbitrarily close to the infimum and let the approximation error tend to zero. For h∈ph _p, set gh(x,y)=h(x)≠y−h∗(x)≠y.g_h(x,y)=1\h(x)≠ y\-1\h^*(x)≠ y\. Then (gh(X,Y)+2L(h∗))=L(h)+L(h∗)E(g_h(X,Y)+2L(h^*))=L(h)+L(h^*) and Var(gh(X,Y)+2L(h∗)) (g_h(X,Y)+2L(h^*)) =Var(gh(X,Y))≤gh(X,Y)2 =Var(g_h(X,Y)) _h(X,Y)^2 =ℙ(h(X)≠h∗(X))≤L(h)+L(h∗)=(gh(X,Y)+2L(h∗)). =P(h(X)≠ h^*(X))≤ L(h)+L(h^*)=E(g_h(X,Y)+2L(h^*)). Order the threshold chain pointwise. Relative to h∗h^*, the chain has two branches. The upper branch consists of the hypotheses h satisfying h(x)≥h∗(x)h(x)≥ h^*(x) for every x∈x , and the lower branch consists of those satisfying h(x)≤h∗(x)h(x)≤ h^*(x) for every x∈x . Within either branch the sets DIS(h,h∗)DIS(h,h^*) are nested, while sets from opposite branches are disjoint. For every (x,y)(x,y), gh(x,y)=−yDIS(h,h∗)(x)g_h(x,y)=-y1_DIS(h,h^*)(x) on the upper branch and gh(x,y)=yDIS(h,h∗)(x)g_h(x,y)=y1_DIS(h,h^*)(x) on the lower branch. For s>0s>0, let s=gh:gh(X,Y)2≤sG_s=\g_h:Eg_h(X,Y)^2≤ s\. Let As+A_s^+ be the union of DIS(h,h∗)DIS(h,h^*) over the upper branch with gh∈sg_h _s, and define As−A_s^- analogously over the lower branch. For every such h, ℙ(X∈DIS(h,h∗))=gh(X,Y)2≤sP(X (h,h^*))=Eg_h(X,Y)^2≤ s. For these nested threshold sets, the probability of each union is the supremum of the probabilities of its members. Thus ℙ(X∈As+)≤sP(X∈ A_s^+)≤ s and ℙ(X∈As−)≤sP(X∈ A_s^-)≤ s. Since sets from opposite branches are disjoint, As+∩As−=∅A_s^+∩ A_s^-= . Define q=1k∑i=1kXi∈As+∪As−,q= 1k _i=1^k1\X_i∈ A_s^+∪ A_s^-\, and let tht_h be the empirical mass of DIS(h,h∗)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′∈sg_h,g_h _s, 1k∑i=1k(gh(Zi)−gh′(Zi))2=|th−th′|. 1k _i=1^k (g_h(Z_i)-g_h (Z_i) )^2=|t_h-t_h |. The coordinates tht_h lie in an interval of length at most q. Hence, for 0<u≤q0<u≤ q, the class sG_s has an empirical L2L_2 cover of radius u and size at most 1+q/u21+q/u^2. Applying the chaining argument conditionally to the Rademacher process and retaining the numerical constant in the proof of [12, Section 3.2] gives εsupg∈s1k∑i=1kεig(Zi)≤12k∫0qlog(1+qu2)u≤12(2+log2)qk. _ _g _s 1k _i=1^k _ig(Z_i)≤ 12 k _0 q (1+ qu^2 )\,du≤ 12 (2+ 2)qk. Taking expectation over the validation sample and using q=ℙ(X∈As+∪As−)≤2sEq=P(X∈ A_s^+∪ A_s^-)≤ 2s shows that the last display is less than 28s/k28 s/k. The common translation by 2L(h∗)2L(h^*) has zero expected Rademacher sum. Finally, apply the first part of [7, Theorem 3.3] to the class gh+2L(h∗):h∈p\g_h+2L(h^*):h _p\, with T(gh+2L(h∗))=gh(X,Y)2T(g_h+2L(h^*))=Eg_h(X,Y)^2 and B=1B=1. The subroot function s↦28s/ks 28 s/k has fixed point 784/k784/k. Empirical optimality gives 1k∑i=1k(gh^(Zi)+2L(h∗))≤1k∑i=1k(gh∗(Zi)+2L(h∗))=2L(h∗). 1k _i=1^k (g_ h(Z_i)+2L(h^*) )≤ 1k _i=1^k (g_h^*(Z_i)+2L(h^*) )=2L(h^*). Since the range of this class has length two, the cited theorem shows that, for every fixed K>1K>1, with probability at least 1−δ1-δ, L(h^)−L(h∗)≤2L(h∗)K−1+K(551936+26b)+22bk,b=log(12/δ).L( h)-L(h^*)≤ 2L(h^*)K-1+ K(551936+26b)+22bk, b= (12/δ). For L(h∗)>0L(h^*)>0, choose K=1+2L(h∗)k/(551936+26b)K=1+ 2L(h^*)k/(551936+26b); for L(h∗)=0L(h^*)=0, take K=1+(551936+26b)−1K=1+(551936+26b)^-1. Since b≥log12b≥ 12 and 551936+26b<222142b551936+26b<222142b, substitution gives the stated bound. ∎ Proof of Theorem˜1. For n≥6n≥ 6, let k=⌊n/3⌋k= n/3 . Form the [−1,1][-1,1]-valued predictor p p in (14) from observations 1,…,2k−11,…,2k-1, and use the next k observations, 2k,…,3k−12k,…,3k-1, as an independent validation block. List the distinct values p^(Xi) p(X_i) on the validation block in increasing order. For each listed value u, include the classifier x↦2p^(x)≥u−1x 21\ p(x)≥ u\-1, together with the rule identically equal to −1-1, and choose any empirical risk minimizer h h from this finite list, with ties resolved by a fixed rule. Consequently, h h is an empirical risk minimizer over p^T_ p. With the fixed rule for resolving ties, h h is a deterministic function of the sample and is the classifier output by the learner. For every x∈x and y∈−1,+1y∈\-1,+1\, 12∫−112 1p^(x)≥u−1≠yu=12|p^(x)−y|. 12 _-1^11\2\,1\ p(x)≥ u\-1≠ y\\,du= 12| p(x)-y|. Integrating this identity and applying Fubini’s theorem gives 12∫−11L(x↦2p^(x)≥u−1)u=L(p^). 12 _-1^1L (x 21\ p(x)≥ u\-1 )\,du=L( p). Therefore, we have infh∈p^L(h)≤L(p^) _h _ pL(h)≤ L( p). Condition on the first 2k−12k-1 observations, so that p p is fixed and the validation block remains i.i.d. Applying Lemma˜3.3 with confidence δ/4δ/4, and using the preceding inequality, gives L(h^)≤L(p^)+223000(L(p^)log(48/δ)k+log(48/δ)k).L( h)≤ L( p)+223000 ( L( p) (48/δ)k+ (48/δ)k ). We apply Theorem˜3 with confidence δ/16δ/16. On the event supplied by this theorem, L(p^)≤L∗+17000(L∗(d+log(48/δ))k+d+log(48/δ)k),L( p)≤ L^*+17000 ( L^*(d+ (48/δ))k+ d+ (48/δ)k ), and the inequality a+b≤a+b a+b≤ a+ b gives L(p^)log(48/δ)k L( p) (48/δ)k ≤L∗log(48/δ)k ≤ L^* (48/δ)k +17000log(48/δ)k(L∗(d+log(48/δ))k+d+log(48/δ)k) + 17000 (48/δ)k ( L^*(d+ (48/δ))k+ d+ (48/δ)k ) ≤(1+17000)(L∗(d+log(48/δ))k+d+log(48/δ)k) ≤(1+ 17000) ( L^*(d+ (48/δ))k+ d+ (48/δ)k ) <132(L∗(d+log(48/δ))k+d+log(48/δ)k). <132 ( L^*(d+ (48/δ))k+ d+ (48/δ)k ). For the second inequality, we used log(48/δ)/k≤(d+log(48/δ))/k (48/δ)/k≤(d+ (48/δ))/k, which is at most the expression in parentheses. Substituting these bounds into the validation inequality gives L(h^)<L∗+3.1⋅107(L∗(d+log(48/δ))k+d+log(48/δ)k).L( h)<L^*+3.1· 10^7 ( L^*(d+ (48/δ))k+ d+ (48/δ)k ). A union bound shows that the two events hold simultaneously with probability at least 1−5δ/161-5δ/16, and hence at least 1−δ1-δ. Since k≥n/6k≥ n/6, the last display implies (2). When n<6n<6, return the classifier identically equal to −1-1. The error term in (2) exceeds one, so the bound is immediate. Finally, suppose that 0<δ≤1/20<δ≤ 1/2. Since d+log(1/δ)≥1+log2d+ (1/δ)≥ 1+ 2 and log48<52(1+log2) 48< 52(1+ 2), we have d+log(48/δ)≤72(d+log(1/δ)).d+ (48/δ)≤ 72 (d+ (1/δ) ). Thus (2) also implies the bound stated in the abstract. ∎ 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] I. Aden-Ali, Y. Cherapanamjeri, A. Shetty, and N. Zhivotovskiy (2023) Optimal PAC bounds without uniform convergence. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), Los Alamitos, CA, USA, p. 1203–1223. External Links: Document Cited by: Appendix A, §1, §1, §3.2, §3.2, §3.3. [2] I. Aden-Ali, Y. Cherapanamjeri, A. Shetty, and N. Zhivotovskiy (2023) The One-Inclusion Graph algorithm is not always optimal. In Proceedings of Thirty Sixth Conference on Learning Theory, G. Neu and L. Rosasco (Eds.), Proceedings of Machine Learning Research, Vol. 195, p. 72–88. External Links: Link Cited by: §3.2. [3] N. Alon, O. Ben-Eliezer, Y. Dagan, S. Moran, M. Naor, and E. Yogev (2021) 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, New York, NY, USA, p. 447–455. External Links: ISBN 9781450380539, Document Cited by: Appendix A. [4] J. Asilis, S. Devic, S. Dughmi, V. Sharan, and S. Teng (2024) Regularization and optimal multiclass learning. In Proceedings of Thirty Seventh Conference on Learning Theory, S. Agrawal and A. Roth (Eds.), Proceedings of Machine Learning Research, Vol. 247, p. 260–310. External Links: Link Cited by: §2, 3rd item, §2. [5] J. Asilis, M. M. Høgsgaard, and G. Velegkas (2025) On agnostic PAC learning in the small error regime. In Advances in Neural Information Processing Systems, Vol. 38, p. 123346–123388. External Links: Link Cited by: §1. [6] J. Audibert (2009) Fast learning rates in statistical inference through aggregation. The Annals of Statistics 37 (4), p. 1591–1646. External Links: Document Cited by: footnote 2. [7] P. L. Bartlett, O. Bousquet, and S. Mendelson (2005) Local Rademacher complexities. The Annals of Statistics 33 (4), p. 1497–1537. External Links: Document Cited by: §3.3, §3.3. [8] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth (1989) Learnability and the Vapnik–Chervonenkis dimension. Journal of the ACM 36 (4), p. 929–965. External Links: Document Cited by: §1. [9] S. Boucheron, O. Bousquet, and G. Lugosi (2005) Theory of classification: a survey of some recent advances. ESAIM: Probability and Statistics 9, p. 323–375. External Links: Document Cited by: §1. [10] L. Devroye, L. Györfi, and G. Lugosi (1996) A probabilistic theory of pattern recognition. Stochastic Modelling and Applied Probability, Vol. 31, Springer, New York, NY. External Links: Document Cited by: §1. [11] L. Devroye and G. Lugosi (1995) Lower bounds in pattern recognition and learning. Pattern Recognition 28 (7), p. 1011–1018. External Links: Document Cited by: §1. [12] L. Devroye and G. Lugosi (2001) Combinatorial methods in density estimation. Springer Series in Statistics, Springer, New York, NY. External Links: Document Cited by: §2, §3.3. [13] R. Diestel (2017) Graph theory. 5th edition, Graduate Texts in Mathematics, Vol. 173, Springer, Berlin, Heidelberg. External Links: Document Cited by: §2. [14] R. M. Dudley (1978) Central limit theorems for empirical measures. The Annals of Probability 6 (6), p. 899–929. External Links: Document Cited by: §2. [15] S. Dughmi, Y. H. Kalayci, and G. York (2025) Is transductive learning equivalent to PAC learning?. In Proceedings of The 36th International Conference on Algorithmic Learning Theory, G. Kamath and P. Loh (Eds.), Proceedings of Machine Learning Research, Vol. 272, p. 418–443. External Links: Link Cited by: Appendix A, 4th item, §2, §3.2. [16] Y. Filmus, S. Hanneke, I. Mehalel, and S. Moran (2023) Optimal prediction using expert advice and randomized Littlestone dimension. In Proceedings of Thirty Sixth Conference on Learning Theory, G. Neu and L. Rosasco (Eds.), Proceedings of Machine Learning Research, Vol. 195, p. 773–836. External Links: Link Cited by: Appendix A. [17] D. A. Freedman (1975) On tail probabilities for martingales. The Annals of Probability 3 (1), p. 100–118. External Links: Document Cited by: §3.2. [18] S. Hanneke, K. G. Larsen, and N. Zhivotovskiy (2024) Revisiting agnostic PAC learning. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), Los Alamitos, CA, USA, p. 1968–1982. External Links: Document Cited by: §1, §1. [19] S. Hanneke (2016) The optimal sample complexity of PAC learning. Journal of Machine Learning Research 17 (38), p. 1–15. External Links: Link Cited by: §1. [20] D. Haussler, N. Littlestone, and M. K. Warmuth (1994) Predicting 0,1\0,1\-functions on randomly drawn points. Information and Computation 115 (2), p. 248–292. External Links: Document Cited by: §1, 1st item, §2, §2. [21] K. G. Larsen (2023) Bagging is an optimal PAC learner. In Proceedings of Thirty Sixth Conference on Learning Theory, G. Neu and L. Rosasco (Eds.), Proceedings of Machine Learning Research, Vol. 195, p. 450–468. External Links: Link Cited by: §1. [22] P. M. Long (1999) The complexity of learning according to two models of a drifting environment. Machine Learning 37 (3), p. 337–354. Note: Expanded version of the paper in the Proceedings of the Eleventh Annual Conference on Computational Learning Theory (COLT 1998), p. 116–125, doi:10.1145/279943.279968 External Links: Document Cited by: Appendix A, §1, §2, 2nd item, §2. [23] R. O’Donnell (2014) Analysis of boolean functions. Cambridge University Press, New York, NY. External Links: Document Cited by: Remark 2.2. [24] D. Rawal and N. Zhivotovskiy (2026) Majority-of-Three is optimal. Note: Version 1, submitted 11 June 2026 External Links: 2606.13614 Cited by: §1. [25] H. U. Simon (2015) An almost optimal PAC algorithm. In Proceedings of the 28th Conference on Learning Theory, P. Grünwald, E. Hazan, and S. Kale (Eds.), Proceedings of Machine Learning Research, Vol. 40, p. 1552–1563. External Links: Link Cited by: §1. [26] L. G. Valiant (1984) A theory of the learnable. Communications of the ACM 27 (11), p. 1134–1142. External Links: Document Cited by: §1. [27] V. N. Vapnik and A. Ya. Chervonenkis (1971) On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications 16 (2), p. 264–280. External Links: Document Cited by: §1. Appendix 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 the k mistakes of the best comparator and obtain the optimal randomized expected mistake bound k+Θ(kLdim(ℋ)+Ldim(ℋ))k+ ( kLdim(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 [1] 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. Full prompt for Theorem˜1, GPT-5.6 Sol Pro, August 6, 2026