On Agnostic PAC Learning in the Small Error Regime
Authors: Julian Asilis
Mikael Møller Høgsgaard
Grigoris Velegkas
Venue: NeurIPS 2025 spotlight ()
Keywords: PAC learning
statistical learning
agnostic learning
supervised learning
Primary area: theory
TL;DR: Improved sample complexity bounds for agnostic binary classification in the tau-based model!

Abstract: Binary classification in the classic PAC model exhibits a curious phenomenon: Empirical Risk Minimization (ERM) learners are suboptimal in the realizable case yet optimal in the agnostic case. Roughly speaking, this owes itself to the fact that non-realizable distributions $\\mathcal{D}$ are more difficult to learn than realizable distributions -- even when one discounts a learner's error by $\\mathrm{err}(h^\\ast_\\mathcal{D})$, i.e., the error of the best hypothesis in $\\mathcal{H}$. Thus, optimal agnostic learners are permitted to incur excess error on (easier-to-learn) distributions $\\mathcal{D}$ for which $\\tau = \\mathrm{err}(h^\\ast_\\mathcal{D})$ is small.

Recent work of Hanneke, Larsen, and Zhivotovskiy (FOCS '24) addresses this shortcoming by including $\\tau$ itself as a parameter in the agnostic error term. In this more fine-grained model, they demonstrate tightness of the  error lower bound $\\tau + \\Omega \\left(\\sqrt{\\frac{\\tau (d + \\log(1 / \\delta))}{m}} + \\frac{d + \\log(1 / \\delta)}{m} \\right)$ in a regime where $\\tau > d/m$, and leave open the question of whether there may be a higher lower bound when $\\tau \\approx d/m$, with $d$ denoting $\\mathrm{VC}(\\mathcal{H})$.
In this work, we resolve this question by exhibiting a learner which achieves error $c \\cdot \\tau + O \\left(\\sqrt{\\frac{\\tau (d +
\\log(1 / \\delta))}{m}} + \\frac{d + \\log(1 / \\delta)}{m} \\right)$ for a constant $c \\leq 2.1$, matching the lower bound and demonstrating optimality when $\\tau =O( d/m)$. Further, our learner is computationally efficient and is based upon careful aggregations of ERM classifiers, making progress on two other questions of Hanneke, Larsen, and Zhivotovskiy (FOCS '24). We leave open the interesting question of whether our approach can be refined to lower the constant from 2.1 to 1, which would completely settle the complexity of agnostic learning.

On Agnostic PAC Learning in the Small Error Regime
Julian Asilis
Mikael Møller Høgsgaard Aarhus University hogsgaard&cs au. dk
Grigoris Velegkas" Google Research gvelegkas@google.com
USC asilisQusc.edu
Abstract
Binary classification in the classic PAC model exhibits a curious phenomenon: Empirical Risk Minimization (ERM) learners are suboptimal in the realizable case yet optimal in the agnostic case. Roughly speaking, this owes itself to the fact that non-realizable distributions DD are more difficult to learn than realizable distributions even when one discounts a learner's 's error by err err(h)). i.e., the error of the best hypothesis in H. Thus, optimal agnostic learners are permitted incur excess error on (easier-to-learn) distributions 'D for which = err(h)) is small. Recent work of Hanneke, Larsen, and Zhivotovskiy (FOCS '24) addresses this shortcoming by including т itself as a parameter in the agnostic error term. In this more fine- anneggrined model, they demonstrate tightness of the error lower bound T + 2t( 7(d+log() /8))/m + d+ log(l (m))m in a regime where T > d/m, and leave open the question of whether there may be higher lower bound when zs d/m, with denoting VC(H). In this work, we resolve this question by exhibiting a learner which achieves error c T + D(//((=Hog(///))// + d-log(1/6//m) for a constant S 2.1, matching the lower bound and demonstrating optimality when T = (dd/m) Further, our learner is computationally efficient and is based upon careful aggregations of ERM classifiers, making progress on two other questions of Hanneke, Larsen, and Zhivotovskiy (FOCS '24). We leave open the interesting question of whether our approach can be refined to lower the constant from 2.1 I, which would completely settle the complexity of agnostic learning.
Introduction
Binary classification stands perhaps the most fundamental setting in supervised learning, and one of its best-understood. In Valiant's celebrated Probably Approximately Correct (PAC) framework, learning is formalized using domain X in which unlabeled data points reside, the label space ) = (+1). and a probability distribution D over x y. The purpose of a learner A is to receive a training set (æi, y: ) " of points drawn i.i.d. from D and then emit hypothesis A(S) X y which is unlikely to mispredict the label of a new data point (I, y) drawn from D.
At the center of learning problem is hypothesis class of functions H. C y with which the learner A must compete. More precisely, A is tasked with emitting a hypothesis f whose error, denoted LD(f) := ((a.))> (f(x) + v), is nearly as small that of the best hypothesis in H. We assume for simplicity such best hypothesis exists and denote it hop arg minkew (D(h) or when D is clear from context with ht" Of course, the distribution D unknown to A, and A judged on its performance across broad family of allowable distributions D.. In realizable learning, (D inf (h(h) = 0}. meaning A promised that there always exists a ground truth hypothesis h² H. attaining zero error. In this case, for A to compete with the performance of hi simply requires that it attains error < e for all realizable distributions the training set S ~ D and using the smallest amount of data possible). In agnostic learning. ID defined as the set of all probability distributions over X' V, meaning any data mettraannnatingg process
(with high probability over
39th Conference on Neural Information Processing Systems (NcurIPS 2025).
Part of the work done while the author PhD student Yale University.

---

is allowed. Thus, A is not equipped with any information concerning D E ID at the outset, but in turn it is only required to emit a hypothesis f with CD(f) < (D(h)) c.
Perhaps the most fundamental questions in PAC learning ask: What is the minimum number of samples required to achieve error at most c? And which learners attain these rates? For realizable binary classification, the optimal sample complexity of learning remained a foremost open question for decades, and was finally resolved by breakthrough work of Hanneke (2016) which built upon that of Simon (2015). Notably, optimal binary classification requires the use of learners which emit hypotheses f outside of the underlying hypothesis class H. Such learners are referred as being improper. This has the effect of excluding Empirical Risk Minimization (ERM) from contention as an optimal learner for the realizable case. Recall that ERM leamner proceed by selecting hypothesis his E H. incurring the fewest errors on the training set S. (For realizable learning, note that hig will then incur zero error on S.) ERM, then, an example of a proper learner, which always emits a hypothesis in the underlying class H. Agnostic learning, however, exhibits no such properness barrier for optimal learning. In fact, ERM algorithms are themselves optimal agnostic learners, despite their shortcomings on realizable distributions. This somewhat counter-intuitive behavior owes itself to the fact that agnostic learners are judged on a worst-case basis across all possible distributions D. Simply put, non-realizable distributions are more difficult to learn than realizable distributions even when one discounts the error term by (hh)) - and thus ERM learners are permitted to incur some unnecessary eπrоr realizable distributions, so long as they remain within the optimal rates induced by the more difficult (non-realie realizzeliz) distributions.
In light of this behavior, it is natural to ask for more refined perspective agnostic learning, in which the error incurred beyond r == LD is itself studied as a function of т. Note that this formalism addresses the previously-deseribel issue by demanding that learners attain superior performance on distributions with smaller values of (such as realizable distributions, for which 0). Precisely this perspective was recently studied by Hanneke et al. (2024), who established that all proper learners, including ERM, are sub-optimal for r E [SQ (m/d)(d + In (1 (1/5))/m), o(1)), by establishing new lower bound and an optimal learner in this regime. While settling the sample complexity for a wide range of r, Hanneke et al. (2024) leave open several interesting questions.
Problem 1.1. Let the regime where T R d/m??
VC(H) and m = (S). What the optimal sample complexity of learning in
Problem 1.2. Are learners based upon majority voting, such as bagging, optimal in the T b-based agnostic learning framewok??
Problem 1.3. Can one design a computationally efficient learner which is optimal in the --based agnostic learning framework?
The primary focus of our work is to resolve Open Problem 1.1, thereby extending the understanding of optimal error rates across a broader range of T. As part of our efforts, we also make progress on Open Problems 1.2 and 1.3,
now describe.
1.1 Overview of Main Results
We now present our primary result and a brief overview of our approach.
Theorem 1.4. For any domain X, hypothesis class H. of VC dimension d. number of samples m, parameter å E (0, 1), there is an algorithm such that for any distribution 'D over X x (-1, 13 returns a classifier lig: + (-1,1} that, with probability at least 1 6, has error bounded by
min (211 (v rid++a(1/81) (VV + d+H((1/6)
. (v 7(d+1u(1/))
Imm (m/e)) (d+tiu())))
where T is the error of the best hypothesis in H.
Notably. Theorem 1.4 settles the sample complexity of agnostic learning in the regime r = O(d/ m)) by exhibiting an optimal learner which attains existing lower bounds. Furthermore, it improves upon the learner of Hanneke et al. (2024) when (l//(m//)) d/ m). In light of Theorem 1.4, only the polylog range r E o characterized.
o(n (l1))(mmm)) d+ln(1/)) remains to have its optimal error rates
Let us briefly describe our approach. Hanneke et al. (2024), building upon Devroye et al. (1996), states that any learner, upon receiving m i..dd samples from D, must produce with probability at least

---

5 hypothesis incurring error 7 + ( ( in(1/8))/m + (d + lm(1/6))mm) for worst-case D. Our first elementary observation is that, due this lower bound. by designing a learner whose error is bounded by c. T + O(vr(d + In(1/5))/m hm1mm/m---- (d+In(1//)) (--nn111))) /mm for some numerical constant 2 1, we can get tight bound in the regime r = O(4/m), thus resolving Open Problem 1.1. Furthermore, to make progress across the full regime r E [o, 1/2], , it is crucial to obtain a constant e whose value is close to 1. Motivated by this observation, our primary result gives algorithm that proceeds by taking majority votes over ERMs trained on carefully crafted subsamples of the training set S, and which achieves error 2.1 T + O( O[v + ln(1/8))/m + (d + In(1/5))/m), Notably, this brings us within striking distance of the constant = - we leave open the intriguing question of whether our technique can be refined to lower e to 1, which would completely settle the complexity of agnostic learning.
Our approach is inspired by Hanneke (2016), but introduces several new algorithmic components and ideas in the analysis. More concretely, we first modify Hanneke's s sample splitting scheme, and then randomly select a small fraction of the resulting subsamples on which to run ERM,, rather than running ERM on all such subsamples. This improves the ERM-oracle efficiency of the algorithm. In order to decrease the value of the constant multiplying т, our main insight is to run two independent copies of the above classifier, as well as one ERM that is trained elements coming from a certain "region of disagreement" of the previous two classifiers. For any test point 2, if both of the voting output
label y and have "confidence" in their vote, we output y; otherwise the prediction of the ERM. We hope that this idea of breaking ties between voting classifiers using ERMs that are trained on their region of disagreement can find further applications. Our resulting algorithm employs a voting scheme at its center, making progress on Open Problem 1.2, and is computationally efficient with respect ERM oracle calls, making considerable progress on Open Problem 1.3. Finally, we combine this algorithm with the learner of Hanneke et al. (2024) to obtain a brest-of-both-worblee result. An overview of all the steps is presented in the start of Section 3.2.
classifiers agree
1.2 Related Work
The PAC learning framework for statistical learning theory dates to the seminal work of Valiant (1984), with roots in prior work of Vapnik and Chervonenkis (Vapnik and Chervonenkis, 1964, 1974). In binary classification, finiteness of the VC dimension was first shown to characterize learnability by Blumer et al. (1989). Tight lower bounds on the sample complexity of learning VC classes in the realizable case were established by Ehrenfeucht et al. (1989) and matched by upper bounds of Hanneke (2016), building upon work of Simon (2015). Subsequent works have established different optimal PAC learners for the realizable setting (Aden-Ali et al., 2023, 2024; Høgsgaard, 2025; Larsen, 2023). For agnostic learning in the standard PAC framework, ERM is known to achieve sample complexity matching existing lower bounds (Anthony and Bartlett, 2009; Boucheron et al., 2005; Haussler, 1992). As described, we direct our attention to a more fine-gratie grained view of agnostic learning, in which the error incurred by learner above the best-in-class hypothesis hü is itself studied as a function of r = LD (hi)). Bounds employing T in the error term are sometimes referred to as first-order bounds and have been previously analyzed in fields such online learning (Maurer and Pontil, 2009; Wagenmaker et al., 2022). Hanneke et al. (2024) appear to be the first to consider r-optimal-dependence for upper bounds in PAC learning; we adopt their perspective in this work.
2 Preliminaries
Notation For a natural number m E N. [m] denotes the set {I...., m). Random variables are written in bold face (e.g., x) and their realizations in non-bold type face (e.g.. x). For set Z, Z denotes the set of all finite sequences in Z, i.e., z = UsEN Zt. For a sequence S of length m and indices < j E [m]. Sli j] denotes the smallest contiguous subsequence of S which includes both its ith and jthh entries. Furthermore, we employ 1-indexing for sequences. For 5 = (a, b, c). for instance, S[1 : 2] = (a, b). The symbol LJ is used to denote concatenation of sequences. as in (a, 6) Li (c, d) = (a, b, c, d). When S, E Z are sequences in Z and each element e S appears in St no less frequently than in S. we write S E St. For a sequence S and a set A we denote by S A the longest subsequence of S that consists solely of elements of A. If S is finite set, then EgwS [f()) denotes the expected value of f over a uniformly random draw of x E S.
Learning Theory Let us briefly recall the standard language of supervised learning. Unlabeled data points are drawn from domain X, which we permit to be arbitrary throughout the paper. We
3

---

study binary classification, in which data points are labeled by one of two labels in the label set Y' = {=1}. A function X 3' referred to as hypothesis or classifier, and collection of such functions H S ) is hypothesis class. Throughout the paper, we employ the 0-1 loss function f--1: V'yy' - Ryo defined by f-- (V: v/) Tly * y/]. training set sequence labeled data ((21.81)... . ym) E (X x > A learner is a function which receives training sets and emits hypotheses, e.g., A: (X' x + y The purpose of a learner to emit hypothesis h which attains low error,
points
enror, with respect an unknown probability distribution D over X x V. That is, Lp (f) = (= [1((z) * y]]. A natural proxy for the true error of h is its empirical error on a training set = (Ii (0.3h))m[m) denoted (h) = B(z,y)) [1[h(a) + vi]- If A a learner for H with the property that A(S) arg min Cs for all training sets S, then A is said to be an empirical risk minimization (ERM) learner for H. Throughout the paper we will use to denote an arbitrary ERM learner.
Proof Sketch
We now provide detailed explanation of our approach and comprehensive sketch of the proof. We divide our discussion into two parts. In the first, we present simple approach that achieves an error bound of 15T + O( 7(
(d+lu(1/8)/mm. Recall that this resolves the optimal sample
complexity for the regime & d/m. In the second part, we describe several modifications to the algorithm and new ideas in its analysis which drive the error down to 2.1r ((d++)((1//))) (d+In(1/4)/m)
3.1 First Approach: Multiplicative Constant 15
A crucial component of our algorithm is scheme S' for recursively splitting the input training sequence into subsequences, which adapts Hanneke's recursive splitting algorithm (Hanneke, 2016) and is formalized in Algorithm I and depicted in Figure 1. The algorithm takes two training sequences as input: S, the active set, and T, the union of elements chosen in previous recursive calls.
Algorithm 1: Splitting algorithm S'
Input: Training sequences S, T (X' y)", where |S] 3 for N.
Output: Family of training sequences.
if k 2 6 then
Partition S into S2, S3. with S; being the (i - 1)]S1/3 + 1 to the i|S|/3 training examples of S. Set for each i
Sku = S, 1: 3* return (S Si.n UT), S' (S2,ui S2, LT), S' San LT))
Skn = S - +1 :1:3*-11
else
return S SUT
S
History T
1/3
1/3
1/3
S
Sa
Active
3727
28727
25/27
1/22
20127
New active set
History
S
Sun UT
Sau
Pan UT
Ss.u
San U
New history
Figure 1: The splitting process of algorithm S'. The active set S is split into three disjoint sets Sr. S2, S3. Each of these is then split into new active set (green) and set of previously recursed-on samples (grey), which are passed down to subsequent recursive calls.

---

In comparison to Hanneke's s scheme, we have made two modifications which allow us to control the constant multiplying T, as we will explain shortly. First, we create disjoint splits of the data, in contrast to the overlapping subsets employed by Hanneke. Second, we include more elements in the sets Sin, which are included in all subsequent training subsequences, than in Si,u the set on which we make recursive call.
Let us introduce additional notation. We denote s/1 = nl for St. as defined in Algo- rithm 1. For A an ERM learner and T) the splitting scheme of Algorithm 1, we set TS: == (S thought of as a multiset. For an example (z,, y), we define avg (A' y) EhEA'(S:T) (1(()) * y)/T,'( i.e., the fraction of incorrect hypotheses T) for (z, For a natural number E N. we let (,; be the ran- dom multiset of hypotheses drawn independently and uniformly at random from TT) In a slight overload of notation, we use (i.e.. in bold face) to denote the randomness used to draw the t hypotheses from TT) Intuitively, one can think of Al a bagging algorithm where the subsampled training sequences are restricted to subsets of (S; Similarly, we de- fine (A),
y) EneA((S.T) 1(h(x) # () T. For a distribution D over X' x {-1,1), training sequences S, E (X' x (-1,1))" and a E [0, I]. we let (A: T)) = ((Xy)~ javgz (A'(S; ())
ax. i.e., the probability that at least an o-fraction of the hypothe- in A': T) em on a new example drawn from D. We will overload the notation LD when consid- ering majorities and write (A' T)) (A: T)) the probability of an equal weighte majority vote fails. Similarly, we define (S) = P(xxy)-(aaxg (Ai (S; (x. 2 a] and L (S( = LD (S) Finally, we let A((5) = (S; 0), and (s) =
sign(2 (heAA((S:)) h(x)).
We now describe our first approach, which we break into three steps. The first step relates the error of CD(AA (S)) to Cb C),49 (A'(SS 0)). while the second and third steps bound the error of CD44 (A'(S, 0)). The first step borrows ideas from Larsen (2023) and the last step from Hanneke (2016), but there are several technical bottlenecks in the analysis that do not appear these works, as they consider the realizable setting, for which T = O.
Relating the error of A((S) to A'(S, We will demonstrate how bound the error of the random classifier (S) using the error of A' 0). First, let S ~ D and assume we have shown
(V 7(d + In (1/5)) d In (1/5)
(A)(S:)) S 15T 15T +0
(I)
with probability at least 1 - 5/2.. Consider the event E= E avg (A'(S: (v
49/100]-
By the law of total expectation, we bound the error of (S as LD (D(A S P (x (E)
E(x.y)=D( [1 (LAA * y E]. We see that the first term on the right-hand side is 2 (A(S: 0)). which we have assumed for the moment can be bounded by Equation (1). We now argue that the second term can be bounded by O((d + In (1/8))/ /m). Note that under the event E = {(z y) avg, (A(S; 0) (zr y) < 19/100). strictly more than half of the hypotheses in A(S; 0) - from which the hypotheses of AS) are drawn - are correct. Using this, combined with Hoeffding's 's in- equality and switching the order of expectation (as t and (x,y) are independent), we get that (S)( * y} ET] < exp (t)( Setting = O(n (m/(ó(ln (1/6) + d))) O ((ō(In (1/5) + dd)/m) By an application of Markov's inequality, this implies with probability at least 1 - -5/2 over the draws of hypotheses in # y) E]- = O(dd+h In (1/8))/m) /m). This bounds the second term
Ee [[<()))>> 1
then gives E, (x.))>> [1 (S) * fy} E
At (S) that (L in the error decomposition of Lo (S: 0)) and gives the claimed bound on (S)
Bounding the error of (I, 0)): We now give the proof sketch of Equation (1). To this end, for a training sequence S" and hypothesis h we define (h, S") = E (a 1(h(x) * y). Assume for the moment that for h* E arg min (h) we have demonstrated that with probability at least 1 5/4 over S, and for some numerical constants cb. Cc.
co cd(dlin (4/5)) 145 of (M,S") (m/4f)
C0.49 (A'(S:0)) <
max 1E
+
+
(d(dlnn (4/61) (2)
(S.0)
m/sh
5

---

In order to exploit Equation (2), we first observe that for each i E (1,2,3), we have that
(1t, 5*)
14 S,)
max S' (S.
I 15 (Hr),
(3)
m/sh
[S mm/s/
as S' C S; and /S.ls//m = Is. = 1/01- tion with [S.I/[S.n| is a source of a multiplicative factor trarily close to by making the split between S., and Stn more imbalanced in the direction of S S1, at the cost of larger constants co Ce. Now, by an application of Bernstein's 's inequality on the hypothesis It" (Lemma B.3) for each i E (1, we have that 15 Ls, (It) ) is at most In (1/5)/m m + In (1/6)/m)), with probability at least - 6/4 over S. Invoking the union bound and using that (S.)) = (1.23
-/)1-)) 7)
We briefly remark that the multiplica-
However, it can be made arbi-
maxsres (S...S. we then have that (1/8))/ In (1/6)/m)) with probability at least 36/4 4 over S. Finally, union bounding with the event in Equation (2) yields that both events hold with probability least 1 5 over S, from which the error bound of Equation (1) follows by inserting the bound of ss 14 (lr, 5') s4)) into Equation (2).
SS 1 (It, (')/(m/sh)) =
Relating the error of CO (AA''S, 0)) to the empirical error of It: Here we draw inspiration from the seminal ideas of Hanneke (2016) by analyzing the learner's loss recursively. However, certain aspects of our analysis will diverge from Hanneke's approach, which is tailored to the realizable setting. As in Hanneke (2016), we have the splitting scheme S'(.,.) receive two arguments, the second of which can be thought of the concatenation of all previous training sequences created by the recursive calls of Algorithm 1. As we are in the agnostic case, this second argument can be any training sequence T E (X {-1,1))' We will first demonstrate that with probability at least 1 8 over S,
142g (16,81)
CU.49 Cb (A)(S:T))
<
max S' (S:T)))
(H.S') m/sh
co(d+In (1/8))
(m/sh)
cd(d+In (1/6)) (4)
Setting T T 0 and rescaling d then yields Equation (2).
The first step of our analysis is to relate the error of CD 19 (A4' T)) to that of the previous calls A', LIT) First note that for any (z. y) such that avg (A: (z) y) 2 49/ 100, at least one
of the calls A' Si, Li T) for i E {1, 2, must have , (. (z. v) S JT) that also fail on (I,z). Using these observations, we have that if we draw random index I E (1,2,3) 3} and random hypothesis h E ( A.: Sj.n LT),, then for (z, y) such that avg (A'(S; (T) y) 2 49/100 it holds that PT,n lavg (A(Si,,; St.n L (z, 2 49/100, h((z) * 47
2 49/100.
Further, there must be at least ( 49
110 1) 2 200
47 of the hypotheses in (1
2 13- Hence, we have that 13 E I. (P (a.y)~D(av,, (A(S S1.n L1 (x) 2 49/100, h((x) * y]] 2 (AA(S; T)). Furthermore, by the definition of I E (1,2,3) and
v] 2
3 200
being a random hypothesis from (JE ( LT,, we conclude that
avg (SI,; (I))) 2 49/100, h((x) #x]
(A'(:))
& 13
E I1 (
avg (A Sr, San LIT) 19/100 h(x) # xy]
S 13
P (x
(5)
(1,33). (S,
We will demonstrate Equation (4) by induction on |S| 3* By setting c and ea sufficiently large, we can assume the claim holds for l < 9. By Equation (5) and union bound, it suffices
to bound each of the six terms for different combinations of j. by Equation (4) with probabil-
ity at least 1 - 8/6. Using symmetry, we can consider the case j = 1 and i = 2. Note that 13 maxne (S, St nuTy IP (P Javg (A' S2, (x)) Z 49/100, h(x) A y] equals
LI) 2 0.49] (13 P (x) F (L (x,y)~ ked ied'(S.. (I..
S2,n (.)))))) (6)
max

---

Supposing that (A (. TT) is upper bound by
14
(d In (1/6))
(1,,))))))) (m/sh)
Co (d + In (1/5))
13
max S'ES(S:T)
m/sh
(7)
then Equation (6) is bounded in Equation (4) and done. Using that [S2,ul m/34, the inductive hypothesis gives that with probability at least 6/16 over S2 that ( (A ; T)) is at most
14E S m/(8/h))
cb (d In (16/6)) (166/))))
142 (1,
(m//5)
Ce (d + In (16/0))
max S'ES(S.T)
m/31
m//3
Where we have used that S(S2, S2,n UT) S(S;)). Thus, it suffices to consider the case in
which Cb.49 (A'(S2,u: S LT) lies between the expressions in Equation (7) and Equation (8). Let A = ((x, y) lagg (A'
(z)) y) 2 49/100} and N [St. n A|. Using a Chernoff bound, one has that N 2 13m/(145 C3 (A' S2, UT)) with probability at least 1 - 6/16. As S1.7 D- avg (A' Sg, (x,, 2 49/100). uniform convergence over H (see Lemma B,6) yields that with probability 1 8/16 over S.n Equation (6) is bounded by
(Ssinna(t)+
C(d + 21n (48/5))
13 max (S..
00.49
S (9)
N
Where C >> 0 is universal constant. We now bound each term in Equation (9), considered after multiplying by cp Notably, this component of the analysis diverges considerably from that of Hanneke (2016) for the realizable case, in which one assured that Ls, (a For the first, the definitions of N and LsT.nnA (and abbreviate h A'(S S inn T) h E A') to observe that
1(((x) +
13 max (s) -B.10 ( hEA'
14 max REA'
Σ
(10)
(sty)s m/sh s/
Further, using that for any S' 8' (' we have Sn. n A S and h A(S') is minimizer of (z.g)ess 1f/(x)= & y). combined with that S( = S(S;T), one can invoke Equation (10) to conclude that
Ey S') m/sh
13
max (S.
Cs. (s..nn(h)) (o LT)
< 14
max S'ES(S:1)
(11)
We note that the above step introduces a factor of 13 on т, which can be brought arbitrarily close to 1 by using tighter Chernoff bound for the size of N, at the cost of larger constants C. and cb in Equation (4). For the second term vC(d+ In (48/6)) CD (A' S2, L T)) of Equation (9), we again use that N Z (13m)/ CD (A'' S2,n U T)) to bound it from above by / ((4C(dd + 2n (48/6)) cb (A4'(S S2,1 L /))) (13m/sh) As we are considering the case in which C.. bounded by the expression of Equation (8), one can show that the following upper bound holds for sufficiently large с and ca:
(d + In (1/8)) (K
(m/e/))
Ca (d (n
Combining these bounds on each term of Equation (9) yields upper bound of the form
co (d In (1/8)) 14 ((v.S) (m/sh)
14,,
Ce (d + In (1/6))
max S (S:T)
(12)
m/sh
completing the inductive step and establishing Equation (4), as desired.
7

---

3.2 Improved Approach: Multiplicative Constant 2.1
Roughly speaking, we apply two modifications to the previous approach in order to achieve considerably smaller constant factor on т. First, we use different splitting scheme (Algorithm 2) which recursively splits the dataset into 27 subsamples, rather than Second, rather than taking a majority vote over ERM learners on single instance of the splitting algorithm, we split the training set into three parts, run two independent instances of the voting classifier on the first two parts, and one instance of ERM on subsample of the third part. The subsample we train the ERM on is carefully chosen and depends on a certain "region of disagreement" of the two voting classifiers. The final prediction at a given datapoint is follows: If both voting classifiers agree on the predicted label with certain notion of "margin," " then we output that label, otherwise we output the prediction the tiebreaker ERM. Lastly, we combine our approach with that of Hanneke et al. (2024) to achieve best-of- cest-of-both-wool borldworlds bound. We summarize our approach in the following point form and Figure 2.
1. Split the training set S into three equally sized parts S S2,
2. Split S into three equally-sized parts, 1 S1,2, S1,2,S1,.. S1,3.
2.1 Run the splitting scheme of Algorithm on (Si.1, 0) and (S1.2, 0). Let Si, S2 be the resulting sets of training subsequences.
2.2 Sample L 0 (ō(d + In (1/6)))) sequences from each of S and S2 uni- formly at random. Let Si, S2 be the resulting collections of sequences.
2.3 Train ERM learners on each sequence appearing in Si, S2. Denote by Ar, the resulting collections of classifiers produced by these ERMs, respectively.
2.4 Define the set 5 as follows: for any (I, v) S1,3 if at least 11/243-fraction of the classifiers in A., do not predict the label y for æ, or likewise for Ar then (z, y) E S
Train an ERM on Si producing the classifier /tio-
2.5 Let Ai be the classifier which acts as follows on any given a: if a 232/243-fractins of the classifiers of both A., and Ar, agree on a label for x. then Ai predicts y. Otherwise, it predicts (xr).
3. Use S2 to train the algorithm of Hanneke et al. (2024). Let A be the resulting classifier.
4. Output the classifier among A and A which attains superior performance on Sg.
Split
Split
Algorithm
Sample
Train Majority
S
A
Aggregate
Algorithm
Sample tu
Train Majority
S
A
Filter
Train
ScN
Bise
Train Hanneke al. (2024)
Best Test
Final Classifier
A
Test on 8.
Figure 2: A flowchart of the final algorithm. The initial sample S is split into three parts. S is used to construct our tie-breaking classifier As. S2 is used to train the algorithm of Hanneke et al. (2024), yielding Ag. Finally, Sy is used as hold-out set to select the better of the two classifiers.
Remark 3.1. Intuitively, hie can be seen "stabilizing" the predictions produced by the classifiers in the collections As, and Ad, when at least one collection is judged to have low confidence. However. strictly speaking, we cannot demonstrate that the learner Å₁ described by Step (2.) is stable in the sense of Bousquet and Elisseeff (2002). In particular, the classifiers in each of A and Aeg are trained on overlapping samples, meaning that many classifiers could change by altering even one example in S1,1 or S1,,, thereby altering S as well.
We now derive the generalization error for the steps under points 2.1 2.5. The derivation presented
in bottom-up fashion, starting by examining the failure modes of the approach in Section 3.1 (which leads to the bound with 157), and amending these obtain the approach of 2.1 2.5 bounded by 2.1 2. To this end, let us recall the three sources leading multiplicative factors in Section 3.1. First is

---

in Equation (3). Recall that this constant can be driven down to 1 by considering even more imbalanced splits of the dataset, at the expense of larger constants multiplying the remaining terms of the bound. Second is the error arising from Equation (1 which controls the size of N via a Chernoff bound. This can similarly be driven arbitrarily close to 1. Hence, the primary multiplicative overhead results from the third source: the argument in Equation (5) relating the error of A T) to that of its recursive calls.
the balance between the splits of S; in Algorithm 1, i.. = |
one of its previous iterates erring on 49/100- fo/oo-rraciionn of its classifiers, and one hypothesis from the remaining iterates also erring. Re- call that to get this bound we first observe that, with probability at least 1/s over a randomly drawn index I ~ (1,2,3} avg (AL S1,7 I7 yx) 2 0.49 and a random hypothesis h LijE( (1 (1.2,3))..A A' J.: 5 LT), would, with probability at least 3/2(49/100 1/s), make an error. Thus, we get the inequality in Equation (5), which multiplies 7 by == 13. To decrease this constant we first make the following observation: assume that we have two voting classifiers ,s, 0), (52; 0) (
The constant arises from relating C% (A)(S:T))
and an (I. y) such that avg (A: (x) y) 2 232/243 and avg (S2; (1r y) 2 232/240 243. Using similar analysis in Equation (5), have
P [avg (A ()) y) 2 232/243, avg (A' 0)) 2 282/243]
(13)
(x,y)~D
243
I 232 (S::) (x,))~
max P [h(x) + y, a (A 0)) yx 2 232/243|
(14)
Following a similar approach to that used to obtain Equation (1), we can bound Equation (14) by 1.1r + (( + In (1/8)) m + (d + In /8))mm). Thus, if we could bound the error using the event in Equation (13), we could obtain a better bound for the overall error of our algorithm.
To this end, consider a third independent training sequence S₃ and let S be the training examples (xt, 3) in S3 such that avg (A'(S (: 0) (xx, v) 2 11/243 or avg, (A: (z) y) 2 11/243. Let htii = A(S ). f.e. hiie is the output of ERM-learner trained on S We now introduce our tie-breaking idea. For point x we let Tie 1/243 (A'(S): A'(S; 0): /iie) (x)) = y. where y E {+13 is the unique number for which EnEA(s)::)) 1 11(xx) = () 0)] 2 232/243 and Ene 1 (h(x)) =
(S2, 0) 2 232/243. such a number does not exist, we set y = ltti Thus, this classifier errs on (x, y) if 1) avg (A (((((s))){,,
2 232/243 and avg
(AA (A2(S2; 0)), y) N 232/243, or 2) 232/243 or EhEA(())))) 1h((z)
for all y' E {=1}, EnEd 1(h(z) = (S
y (12; 0)1 < 232/213 and (z) # y. Using the definition of condition 2), we have that LD (Tie 1/243 (Ai(S 0), (S:::: 0); heeie)
P avg e (S 0)) (x. y) 2 avg ( (S2: (x) 2 232/203]
(x
P lavg / (A 0)) y) 2 11/213 or avg (A: 0)) > 1/2113 and hasie (x) + y]. (x-))D
As observed below Equation (13), the first term can be bounded by 1.1 ln (n (1/6))/m+ (d+ In (m)) Thus, if we could bound the second term by 7 + 0( (V(dd((T++ (1/8))/m
(d + In (1/8))m)) we would be done. Proceeding as in Equation (6), let D2 be the conditional
distribution given avg (A'(S ; 0)) (x, y) Z 11/213 or avg (S2; 0)) y) 2 11/213. Then,
P lavg (A' 1 x y) > 11 2213 or avg (A' (S2; 0)) y) 2 11/213 and (ie + yl (x,y)D
IP Thiie (x) + y] (x,y>DD
IP lavg, (x.y)>D
2 11/213 or avg (A2: (x) 2 1/213]
We notice that hic is the output of an ERM learner trained on $ Dj,, thus, by standard guarantees on ERM learners (Theorem C.2), it holds with high probability that
dd + In (1/8) S LD,, + V
(d + In (1/5)
P Thiic (x) * y] S inf Lo (h) (x,y)>Da
hCH
|S/
|S/
where the second inequality follows from that E H. Thus, we have that
IP (x
Javg, y (A'( (x) y) 2 11/243 or avg (S2: ()) v) 2 11/213 and hise (x) + Yy] S
(d+ In (1/0)) P. Fx.x>D [avg, (AT(S) y) 2 11/233 or avg (A((s) y) 2 11/2033
++
|

---

Using a similar argument as in Equation (9), a Chernoff bound yields that |S (m P Px,yD a (x.,)) 2 11/213 or ( 0x) y) 2 1122ss) with high prob- ability. Thus, if the probability term were at most c(T + (d + In (1/0))/m), the above argument would be complete. However, the analysis from Section 3.1 only bounds the probability term when is 49/100, instead of 11/243, which is not sufficient. Thus, we will now remedy this using a different splitting algorithm that allows for showing the more fine-grained error is small.
An approach with more than 3 splits: We have seen that the above argument requires that (avgy (A: (x) y) 2 11/243] S c(T + (d + In (1/8))/m) with high probability. However, attempting to prove this by induction, as in Section 3.1, breaks down in the step at which we derived Equation (5). Recall that this where we relate the condition avg (A'(S: (a) y) 2 11/243 to previous recursive call also erring in the remaining recursive calls erring on (z, y). To see why this argument fails, now consider (z, y) such that avg (A: (S) (z, y) 2 11 11/243. Picking an index I ~ {1, 3 with probability at least 1/3 still returns avg (A' S TU (z.)) v) 2 11/243. However, when picking a random Syn LT), the probability of h erring can only be lower
11/213ffaactio of its voters and one of the hypotheses
hypothesis h E 4 bounded by 9/2("1/213 1/3), which is negative! (all the errors might be in the recursive call I). Thus, we cannot guarantee lower bound on this probability when making only 3 recursive calls in Algorithm 1. However, if we make more recursive calls, e.g., 27 (chosen large enough to make the argument work), we get that with probability at least 1/27 over
fI.....21 27). it holds that A(SI,u; Sin LT) 2 11/243 and with probability at least 27 27/26(11/243 - 1/27) z 0.009 over h E 27)) f. SanuuS,,, LIT, we have that h(xx) + y. By 27 (1/0.009) 3160, this gives
IP (x N'(x) y, (A > 11 243
(A(S:T)) 3160
max 1,50 ( I MEA (uuii
This is precisely the scheme we propose in Algorithm 2, with A(S:T) (A(S*) ('ES(S.T)) Now, defining As) as I. voters drawn from A(S; 0) with / = 0(n (m/(5(d + In (1/5)))),, and mim- icking the analysis of Section 3.1 yields that C2/2415 (Ae) < cl (d In (1/0)) /mm. Finally, roughly following the above arguments for LD (Tie (At (S,). (S2): ),, but now with (Tie 4/248/ (Ae, (Si), Ar, m)e)), we obtain, for the latter, the claimed generalization error of 2.17 + (V 7(d (1/0))) + (d + In (1/6))/m).
Algorithm 2: Splitting algorithm S
Input: Training sequences S, T (X y)", where |S| = =3 for k N. Output: Family of training sequences.
if l 2 6 then
Partition S into Si...., S27. with S. being the (i - 1)|S1/27 + to the i|S)/27 training examples of S. Set for each i
Sku = S : 3- return [S(S),ui Sn,n UT), S(S S27, LT)]
S.n = S, +11: #11:3-31
else return SUT
With the above classifier in hand, we can now, on two new independent training sequences, obtain the classifier of Hanneke et al. (2024) using the first sequences, and then on the second sequences choose the best of our classifier and the classifier of Hanneke et al. (2024) as the final classifier.
4 Conclusion
We study the fundamental problem of agnostic PAC learning and provide improved sample complexity bounds parametrized by т, the error of the best-in- hypothesis. Our results resolve the question of Hanneke et al. (2024) asking for optimal error rates in the regime t R d/m, and make progress on their questions regarding optimal learners for the full range of and efficient learners based upon majority votes of FRMss The most interesting future direction is whether an improved analysis of our voting scheme modification of it can lead to optimal algorithms for the full range of T.
10

---

Acknowledgments and Disclosure of Funding
While this work carried out, Mikael Møller Høgsgaard was supported by DFF Grant No. 9064- 00068B, and the European Union (ERC,TUCLA, 1012203.. Views and opinions expressed are however those of the author(s) 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. Julian Asilis was supported by the NSF CAREER Award CCF-223926 and the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-I84248Y 1842487. Part of the work was done while Grigoris Velegkas was PhD student at Yale University supported in part by the Al Institute for Learning--nnnn Enabled Optimization at Scale (TILOS).
References
Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy. Optimal pac bounds without uniform convergence. In 2023 JEEE 64th Annual Symposium Foundations of Computer Science (FOCS), pages 1203-1223, IEEE, 2023.
Ishaq Aden-Ali, Mikael Møller Høandgsgaard, Kasper Green Larsen, and Nikita Zhivotovskiy. Majority-of-three: The simplest optimal learner? In The Thirty Seventh Annual Conference on Learning Theory, pages 22-45. PMLR, 2024. 3
Martin Anthony and Peter Bartlett. Neural network learning: Theoretical foundations. cambridge university press, 2009. 3
foundiatiooo
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the vapnikkcchervoneniis dimension. Journal of the ACM (JACM), 36(4):929-96 1989.
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. 3
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of machine learning research, 2(Mar):499-526, 2002. 8
Olivier Bousquet, Steve Hanneke, Shay Moran, and Nikita Zhivotovskiy. Proper learning, helly number, and an optimal svm bound. In Conference on Learning Theory, pages PMLR, 2020. 13, 15
Luc Devroye, László Györfi, and Gábor Lugosi. A Probabilistic Theory of Pattern Recognition. Springer, 1996.
Andrzej Ehrenfeucht, David Haussler, Michael Kearns, and Leslie Valiant. A general lower bound on the number of examples needed for learning. Information and Computation, 244322247- 1989.
Steve Hanneke. The optimal sample complexity of pac learning. Journal of Machine Learning Research, 17(38):1-15, 2016. 2, 3, 4, 5, 6,7
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. IEEE, 2024. 2, 3, 8, 10, 34
David Haussler. Decision theoretic generalizations of the pac model for neural net and other learning applications. Information and computation, 100(L):78-150, 1992. 3
Mikael Møller Høgsgaard. Efficient optimal pac learning. arXiv preprint arXivv25022.0362) 2025.
Kasper Green Larsen. Bagging is an optimal PAC learner. In Gergely Neu and Lorenzo Rosasco, editors, The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India, volume 195 of Proceedings of Machine Learning Research, pages 450-468. PMLR, 2023. URL https: /tt/:t/////rrcccdingg.
mlr. mlr wwt.epprressseesssseseeee httmeenmmaa............mm 3,5
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample-variance penalization. In Annual Conference Computational Learning Theory, 2009. URL https:
//api. www.:sseeaaaciciiieeccem org/ /es//oppsID::100002111

---

Shai Shalev-Shwariz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. 17, 20. 26
Hans Simon. An almost optimal pac algorithm. In Conference on Learning Theory, pages 1552-1563. PMLR, 2015. 2,3
Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11):113-1142) 1984.
Vladimir Vapnik and A Ya Chervonenkis. A class of algorithms for pattern recognition learning. Avtomat. i Telemekh, 25(6):937-945, 1964. 3
Vladimir Vapnik and Alexey Chervonenkis. Theory of pattern recognition. 1974. 3
Andrew J Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. First-order regret in reinforcement learning with linear function approximation: A robust estimation approach. In International Conference on Machine Learning, pages 22384-22429, PMLR, 2022. 3
A Preliminaries for Proof
In this section we give the preliminaries for the proof. For the reader's convenience, we restate Algorithm 2.
Algorithm 2: Splitting algorithm S
Input: Training sequences S, 7 E (X' x 3)", where |S| = 3* for k E N.
Output: Family of training sequences.
if k 2 6 then
Partition S into Si....; S27, with S being the (i - 1)|S1/27 to the / training examples of S. Set for each i Sk,u = S: S: 3 return [S(S S1, LT...... S(S27,u S27, UT)]
S.13 +1:36=11.
else return S S
We first observe that for an input training sequence m = |S] 3* the above algorithm makes ( recursive calls where E N satisfies k - 6(1 1) > 6 and k 6/ < 6, that is, / is the largest number such that k 2 I. As is a natural number, we get that = [k/6]. Furthermore, since = log, (m) we get that = [logs (m)/6) For each of the 7 recursive calls 27 recursions are made. Thus, the total number of training sequences created in S is 27' <
ml ((44n((3) > 0.22 In [s] when running S(S;T) with
what follows, we will use the quantity sn, which we define as S1.1l
S; (X 3 such that |S|
3 and k 2 6. We notice that
8n = S
3
3
27
(15)
[1.n
3k 36-6
3 (1 3
27
This ratio 8n will later in the proof show up as constant, S = (1S + |S..n)/|SEnll 1/(1 1/27), multiplied onto т. Thus, from this relation we see that if the split of S, is imbalanced so that [Stml is larger than |S the constant multiplied on to 7 become smaller.
Furthermore, in what follows, for the set of training sequences generated by S(S;T) and ERM- algorithm A, we write A(S; T) for the set of classifiers the ERM-algorithh outputs when run on the training sequences in S(S; T), i.c., A( = (s where this understood as multiset if the output of the FRM-algorithn is the same for different training sequences in S(S; T). Furthermore for an example (x, y) we define (A(s
y) = ExEA(S.T) 1 (h(()) * v}/lA(S; T)), i.e., the average number of incorrect hypotheses in A(S: T). We notice that by the above comment about S(S; 7) having size at least m 0222 we have that A(S; contains just as many hypothesis, each of which is the output of an ERM run training sequence of S(S;T), Thus as
(2) ())::
12

---

allotted to earlier our algorithm do not run on all the sub training sequences created by S(S; T), as it calls the A algorithm OIn (m/(ô(d + In (1/6))))) Which leads us considering the following classifier.
For natural number 1, we let (S; T), be the random collection of hypotheses drawn uniformly with replacement from A(S:T), with the draws being independent, where we see Ae (S: as a multiset so allowing for repetitions. We remark here that we will overload notation and use t (so in bold font) to denote the randomness used to draw the hypotheses from A(S; T') in the following analysis of (5; T). Intuitively one can think of A, as a bagging algorithm where the subsampled training sequences are restricted to subsets of S(S; T) rather than sampling with replacement from the training examples of S and T. In what follows we will consider this algorithm parametrized by t = (In (m/(õ(d + In (1/6))))) leading to a classifier with the same order of call to the ERM as stated in. Similarly to T)) we also define avg, (A:(S)))) v) = En,T( (1((z) +
/ (/
Now, for distribution D over X' x (1,, training sequences S;T E (X x (-1,1)) and a E [0, we will use C3 (A(: = P( ((xyy) lavg
(xxx)) 2 a] i.e., the probability of at least a o-fraction of the hypotheses in A(S:T) erroring on a new example drawn according to D.
a for (S; In the following we will for the case where I' is the empty training sequence 0 us (s) = (S;
As above we also define C (S; ()) ((xx)>>
avg av (S;
A.1 Difficulties of the Proof
Let us take the opportunity briefly describe the challenges associated with settling the sample complexity of agnostic learning in the regime T = Odd/m). In particular, we will demonstrate that a straightforward multiplicatiie Chernoff argument can not yield a result as general Theorem 1.4.
To begin, notice that the true errors of N hypotheses can indeed be confidently estimated to within error T using (loo((N/0)/r) samples, due to multiplicative Chernoff. However, if then the above yields a vacuous bound. An additive Chernoff bound would
T (log(N/66)/m also in this case imply additive Olog N/8) error term. In the paper, consider classes of finite VC dimension d but arbitrary, possibly infinite cardinality N, thereby preventing us from employing this bound. Even if one were to bound N ((m/d))) using Sauer-Shelah, this would imply that multiplicative Chernoff is unhelpful when T = ((d log(m/d) + log(1/8))/m) This is wide regime containing, for instance, T = Old/m), a setting in which demonstrate that our algorithm is optimal. Furthermore, an additive Chernoff bound would incur a suboptimal additive Od Oglogg log(m/ (ndd///////// d)/m) term.
However, let us assume that a Chernoff bound argument for infinite hypothesis classes could yield Theorem B.2 for all (e.g.. using e-covering argument). In this case, one would have demonstrated that an empirical risk minimizer h has error 2.17 + Oly (rdddtn
d+In (1/8). Then, taking m
m
T = 0 (i.e, considering the realizable case), would demonstrate that ERM results in an error of O (+)6) ). However, this is not generally true, owing to the worst-case lower bound on ERM learners of O d (n (1/62), ), due to (Bousquet et al., 2020, Theorem 11). This strongly suggests that Chernoff bound argument using union bound over each function in the hypothesis class (or discretization of it) cannot yield a result as general as Theorem 1.1, which holds across all T.
m
Finally, we remark that our learner for Theorem B.2 is agnostic to T (i.c., is oblivious to the value of T), whereas the previous Chernoff procedure requires knowledge of r. This is notable distinction, as precise knowledge of 7 will typically be unavailable to the learner. In particular, ERM- basee estimates of will be uninformative in the regime o(d/m).
A Preliminaries for Proof
In this section we give the preliminaries for the proof. For the reader's convenience, we restate Algorithm 2.
13

---

Algorithm 2: Splitting algorithm S
Input: Training sequences S 7 E (X' x )),, where |S| = =3 for E N. Output:
Family of training sequences.
if k 2 6 then
Partition S into Si...., S27, with St being the (i 1)|S|/27 + to the i|51/27 training examples of S. Set for each i
Siy S : 3 return [S(S S1,n LT)..... S( L)T)
Sin S, - +1:3+=1)
else
L return SUT
We first observe that for an input training sequence m =S| 3², the above algorithm makes ( recursive calls where E N satisfies h 6(1 - 1) 2 6 and k - 67 < 6, that is, l is the largest number such that k/ 2 1. As is a natural number, we get that | = |k/6]. Furthermore, since k log, (m) we get that = [loga (m))).) For each of the / recursive calls 27 recursions are made. Thus, the total number of training sequences created in S is 27 < (m))2( = m m/(((m((3)) > m m.22 In
when running (S) with what follows, we will use the quantity Sn, which we define as Sr.ml
|S|
S;T E (X 31" such that |S| = 3 and k 2 6. We notice that
S 11n
3
3
27
$n
3k-3 36-6
3
31
(16)
27
This ratio Sn will later in the proof show up as a constant, |S:1/((S)s) = (IS .l + |S. 1/(1 1/27), multiplied onto T. Thus, from this relation we see that if the split of S; is imbalanced so that [SS.n] is larger than |SS.u|] the constant multiplied on to r become smaller.
Furthermore, in what follows, for the set of training sequences generated by S(S;T) and a ERM- algorithm A, we write AASS; T" for the set of classifiers the E'RM-algorithh outputs when run on the training sequences in S(S:T), i.c., T() = ('sS"))s''s(ss)))) where this is understood as a multiset if the output of the ERM-algorithm is the same for different training sequences in S(S: T). Furthermore for an example (x, y) we define avg ()) y) EnEA(S:T) (h(xz) X ()), i.e., the average number of incorrect hypotheses in A(S: T). We notice that by the above comment about TT; having size at least m 0.22, we have that T(); contains just many hypothesis, each of which is the output of an ERM run on a training sequence of S(S; T). Thus as allotted to earlier our algorithm do not run all the sub training sequences created by T(S; as it calls the A algorithm (In (m/ (8(d + In (1/6)))) -timees classifier.
-tmmes. Which leads us considering the following
For natural number 1, we let Ar T), be the random collection of hypotheses drawn uniformly with replacement from A(S:T), with the draws being independent, where we see (S; as a multiset so allowing for repetitions. We remark here that we will overload notation and use (so in bold font) to denote the randomness used to draw the hypotheses from 7() in the following analysis of As; I)). Intuitively one can think of Ar as bagging algorithm where the subsampled training sequences are restricted to subsets of S(S; T') rather than sampling with replacement from the training examples of S and T. In what follows we will consider this algorithm parametrized by ( t= (In (m/(6(d + In (1/6)))) leading to a classifier with the same order of call to the ERM as stated in. Similarly to A(S;T) we also define avg (Ac(( = Ehe ((((z) +
/ (()
Now, for distribution D over X' 1), training sequences S:T (X' (-1, and E [0, 1] we will use CT (AA(; 7)) = ((x,y)< (avg (x)) 2 a) i.e., the probability of at least a a-fraction of the hypotheses in T(S;T) erroring on a new example drawn according to D.
As above we also define L3 (AA
P(XDD)
avg (A. (S; ()) y) 2 a for (S:
In the following will for the where T is the empty training sequence 0 us A.(S) A.(S:)).
14

---

A.1 Difficulties of the Proof
Let us take the opportunity to briefly describe the challenges associated with settling the sample complexity of agnostic learning in the regime O(d/m). In particular, we will demonstrate that straightforward multiplicative Chernoff argument can not yield a result as general as Theorem 1.4.
To begin, notice that the true errors of N hypotheses can indeed be confidently estimated to within error т using (log(N/00)/ samples, due multiplicative Chernoff. However, (log(((()))))) / then the above yields vacuous bound. An additive Chernoff bound would also in this case imply an additive Ollog( (N/6)/ /m) error term. In the paper, we consider classes of finite VC dimension d but arbitrary. possibly infinite cardinality N, thereby preventing us from employing this bound. Even if one were to bound N as O((m/ ) using Sauer-Shelah, this would imply that multiplicative Chernoff is unhelpful when a wide regime containing, for instance, T = O(d/m), a setting which we demonstrate that our algorithm is optimal. Furthermore, additive Chernoff bound would incur a suboptimal additive log(m/ mmmm term.
O (d (og(m/d)
(og(1/6))/m) This is
However, let us assume that a Chernoff bound argument for infinite hypothesis classes could yield Theorem B.2 for all T (e.g., using an e-covering argument). In this case, one would have demonstrated that an empirical risk minimizer h' has error 2.17 + O / (ddddddd (1/6)) d+In (1/6) Then, taking = O (i.e, considering the realizable case), would demonstrate that ERM results in an eπrо of O 0( (( ). However, this is not generally true, owing to the worst-case lower bound on ERM learners of O (In=)))) (1/6)), ), due to (Bousquet et al., 2020, Theorem 11). This strongly suggests that Chernoff bound argument using union bound over each function in the hypothesis class (or discretization of it) cannot yield a result as general as Theorem 1.1, which holds across all т.
Finally, remark that our learner for Theorem B.2 is agnostic to (i.e., is oblivious the value of T), whereas the previous Chernoff procedure requires knowledge of r. This is notable distinction, precise knowledge of will typically be unavailable to the learner. In particular, ERM-hhsed estimates of will be uninformative in the regime = o(d/m).
B Analysis of A.
As described in the proof sketch, we require bound on 110/243 A(S: 0) in order to upper bound c) C11//43/ (A.). Thus, we now present our error bound for Algorithm 2 when running A on each dataset generated on S(S, i). (We assume that S = 3 for k N, at the cost of discarding constant fraction of training points.)
Lemma B.1. There exists a universal constant e 2 such that: For any hypothesis class of VC dimension d, distribution D over X x y failure parameter 0 < 8 < 1, training sequence size m 3h for k 2 6, and training sequence ~ DmT with probability at least 8 over one has that
10/213 (A(S:0)) ct + c(d In (n/8)) C
m
Let us defer the proof of Lemma B.1 for the moment, and proceed with presenting the main theorem of this section, assuming the claim of Lemma B.
Theorem B.2. There exists universal constant 2 1 such that: For any hypothesis class H. of VC dimension d, distribution DD over X' x X' ,.faluure parameter < < 1, training sequence size m = 3h for k 2 6, training sequence S D and sampling size t 2 4 243 In (2m/(ó In (1/8))),, we have with probability at least 1 over and the randomness t used draw As)S) that:
c(d+ c(d+In(e/6))
C 11/213 (A. S
m
Proof. Let (S; = (f,,..., h.). considered as a multiset, and recall that the h, are drawn uniformly at random from A(S;0) (EESs.)) which is likewise treated as multiset. Let
15

---

Es denote the event
14((x) {1}
10
Es
(1,
Σ
IA(S; 6)]
243
hEA(S)))
and
1(h(z) +
10
Es = (x,
Σ
A 0)
243
hEA((S;))
its complement. Now fix realization S of S. Using the fact that IP we have that
[AA]
=
[IA B] +P P [J..].
D 111/213 (A((5:))) = (xN))D
Σ (f) x
Eg
243"
11
P (x
1 (b) # y3/t2
Es
243"
11
< PP Es] (x-)~D
P
Σ (b.(x) f3\112
Es
(17)
(x,y)~
243
We now bound each term in the above, i.e., in Equation (17).
In pursuit of bounding the second term, consider a labeled example (æ, y) E Es. We may assume that Es non-empty, as otherwise the term simply O. Now, for any such labeled example (x,y) Es we have that Ei=1 (xr())) = y) has expectation
=t ( NEAIS)))
14h(z) =
P(z.g) JE
Σ (f.())
v} -
Σ
2 21 (1-10/213 -t) t/2,
IA(S: 0)
where the final inequality follows from the fact that (z Es. (Recall that the boldface symbol t denote the randomness underlying the random variables fig..., h,.) Now, since 1 (x) * y} is collection of i.i.d. {0, 1] random variables, we have by the Chernoff inequality that
((,:(x) (x) = y}
(1-28) 243
M(a.v)
P
t
M(a.y)
S exp
2 243
5(d + In (1/5))
2m
where the final inequality follows from the fact that ((r,)) 2 1/2 and
2m
z 4 243 In
8(d + (n
The above implies that with probability at least
old+In (1/8))
we have
2m
(z) =
1 ) M(a.)) 2 (1 11 10
(1
1
(1
10
11
1
243
243
243
This further implies that Ei=1 1 1(1,(z)) + y)/t 11/243 with probability at most 8(d+In (1/6)) As we demonstrated this fact for any pair (z. y) E Es. an application of Markov's 's inequality yields that
2m
11
(d + In (1/8))
P
(x) # v1/t
Es
(x-y)D
243
m
(d + In (1/6)) E EX
Pt
Σl= (() # fy//z
1[Es}
243
(18)
2'
16

---

Note that the first inequality follows from an application of Markov's inequality and the observation that Es depends only upon (x, and which are independent from one another, meaning we can swap the order of expectation. The final inequality follows from the bound on the probability of Σ 2i-1 1(h,(x) + y / 2
Il happening over t, for x; Es.
213
Thus, we conclude that with probability least 1 8/2 over the random draw of the hypothesis in Ae (S;0) is such that
(x) +y}
d In (L/0)
Es
(x-y)~
243
2m
Furthermore, as we showed this for any realization S of (and and S are independent), we conclude that, with probability at least 1 5/2 over both t and S.
1 (b, xy)
11
+ In (1/0)
P (x
Es
243'
Furthermore, by Lemma B.I, we have that with probability at least 1 - 6/2 over S.
c(d + (2e/6))
Es S cT (x,y)~
(19)
m
Furthermore, as this event does not depend on the randomness employed in drawing hypotheses for A (S), we conclude that the above also holds with probability at least 1 - 6/2 over both and t. Now, applying union bound over the event in Equation (18) and Equation (19), combined with the bound on L (A in Equation (17), we get that, with probability at least 5 over S and it holds that
11/243 (Ae(S) CT + cT (d + (2e/0))
(1 c) (2e/o))
C
m
As is permitted by any absolute constant, this concludes the proof.
We now proceed to give the proof of Lemma B.I. Doing will require two additional results, the first of which relates the empirical error of hypothesis h to its true eπrоr.
Lemma B.3 (Shalev-Shwartz and Ben-David (2014) Lemma B. 10).). Let D a distribution over X x (11,1}, h E 11 be hypothesis, 8 E (0, a failure parameter. and m E N a natural number. Then,
2 (h) In (1/8) Cs(h) S LD(h)
2ln (1/5)
P S-Dm
2 1 1 8,
3m
m
and
2 Ls(h) In (1/8)
4 (1/0)
P SDD
(D(h) s Ls(h) +
2 21-8. 8.
The second result we require one which bounds the error of A(S;T) for arbitrary training sets T (i.e., not merely T = 0. as we have previously considered).
Theorem B.4. There exists, universal constant e 2 1 such that: For any hypothesis class H. of VC dimension d, any distribution D over X' (-1,1), any failure parameter (0, 1), any training sequence size m 3*, any training sequence T E (X x {-1,1}}*, and random training sequence ~ Dm, holds with probability at least 1 - over S that:
(It, c(d In (1/8))
10/2113 10//213 (A(S:T)) <
max S'ES(S,T)
m/sn
m
where
(11)') = Σ (11( #v)
(*.))ES)
17

---

Let us first give the proof of Lemma B.1 assuming Theorem B.4, and subsequently offer the proof of Theorem B.4.
Proof of Lemma B.l. First note that for each E (l,..., 27}.
E (1,)
1 (x) F0} (m/sn)
max S'ES(S..:Snn))
max ('ES(S)))Ssm))
m/sn
(x,y)ES*
US
1 (z) + y)
(m/sn)
S L Stuul
(a.))
= 2 (s,())))
The inequality follows from the fact that any S' E S( Sin) satisfies S' C S U S and
the final equality uses the facts that [S,,n S [uu = [S,] = m/3 and 8n = 32 - 1/27). Thus, invoking Lemma B.3 over S, for i E {l...., 27} with failure parameter 6 6/28, we have by union bound that with probability at least 1 276/28 over S, each E {I...., ,77 satisfies
(1), m/8n
I 2 T+ (v-
(T+((V)
In (28/5) In (28/8)
))
6 In (28/0)
max
< 4
(20)
8 (
3m
where we have used that Va S + Furthermore, by Theorem B.4 we have that with probability at least 1 - 6/28 over S,
(I,( c(d + In (28/6))
10/244 (A(S:0)) <
(S.TT))
m//n 8m
m
Again invoking union bound, we have with probability at least 5 over S that
(xT,
c(d + In (28/8))
C (A(S:
10/243
S'ET(S
max
m//n
6ln (28/0)
c(d + In (28/8))
< 4c
m
7c (d + In (28/0))
< Ter +
m
where the first inequality follows from Equation (20). This concludes the proof.
We now direct our attention to proving Theorem B.4. We will make use of another set of two lemmas, the first which permits us to make a recursive argument over A-calls based on sub-training sequences created in Algorithm 2.
Lemma B.5. Let S,T E (X x 31" with |S| = 3 for k 2 6, and let D be a distribution over X x y
Then,
10/213 (S(S:T)) < 5687 C
max SJE 27) i We ((S v/j
P (x,y)/D
M(x) # y,avg, ( (A(5,,:: 10
243
Proof.
Let (x, y) be an example such that
1((x)) Fッ) 10
Σ
z [A(S)T)
243
NEA(S:T)
As k: 2 6, Algorithm calls itself when called with (S:T). Furthermore, as each of the 27 calls produce an equal number of subtraining sequences, it must be the case that
243 avg (Z)
10
Σ
Σ
1 (1) + y AA(S, S., UT]
27
HEA(S..iS,,
18

---

This in turn implies that there exists an i E [27] satisfying the above inequality, i.e., such that
1 (f(())) # y)
243 S avg avg (A(S), u Si, (x,) =
Σ
LA(S San1 u2)
un
We further observe that for any i E [27].
27
(h(x) + y}
Σ
243
27
[A(S),u Sj, LT)
==1
(1(()) * y} DiS)J:S,,Luu
Σ
Σ
+
27)
hE (E
This implies, again for any arbitrary choice of i [27], that
1 (1(x)) + y} |A(S)ui Sp,n
Σ
Σ
243
27
27)
hEA(S
Simply multiplying both sides by 27/26, we have that
1 11((z) + y} A(S Sj, LTT)
E
Σ
(21)
234
JE(1....2771
REA(S,U:S,,nLTT
10 then Using the above, can conclude that when (x, is such that avg (A(
213
there exists an [27] with (AA(S Skn (x) v) 2 213 Then by Equation (21), at least a //234-fraction of hypotheses in LJ 27) A(S L T) err on (ar, y). Thus, if we
let I be drawn uniformly at random from {1, 27} and be drawn uniformly at random from TT), then by the law of total probability we have that
27
10
P I
hi(r)) # y, y,
243
10
10 243
P
li(x)) * y //av (A LI
(x)
P
avg 1A)
1.6
243
h
1 10
234
243
5687
This implies turn that
10
10
5687 P
l((z) * y, ( (z))))
> avg avg+
(22)
1
243
243
Taking expectations with respect to (x, ~ D, we have
5687 E I.h (x.y)D
h((x) # y, avg (A Sin (x.))xx))
10
2 C
10
(A(S:T)).
243
As h E U.e
Snm UT). it follows that 27/11 27:1 ASS
10
n((x) # y, avg (A A(S Sin (x)))xx,)) 2
(23)
(x,)DD
243
10
< E
We b'EL 27 A (x,yDD N'(x) + (A
max
2
243
And as I E (1,..., 27}. then clearly
10
E
max MEI (eet.....2..111 (S ( (xy))D
1((x) # y, avg (t.
243
10
< max
max
p
1'(x) + y, Li >
(7()....7) N Ne (x.))>
243
(24)
19

---

By combining Equations (22) to (24), we conclude that
10
D (A(S:T))
10
S 5687
max
max
(x.y)aD N'(x) # y, a.a yy.av L
16 16(1....T) N'
243
10
5687
max (J REA( (x 181
max
P 11(x) f ay (,)
243
which completes the proof.
The second lemma employed in the proof of Theorem B.4 is the standard uniform convergence property for VC classes.
Lemma B.6 (Shalev-Shwatzz Shwartz and Ben-David (2014), Theorem 6.8). There exists universal constant C> 1 such that for any distribution over {-1,1} and any hypothesis class H. C 1-1,1} with finite VC-dimension d, it holds with probability at least 1 over S ~ D that for all h E H:
C(d + (e/o))
CD(h) S Ls(h) +
m
We now present the proof Theorem B.4, which concludes the section.
Proof of Theorem B.4. We induct on 2 1. In particular, we will demonstrate that for each k: 2 and S Dm with m 3 and for any 8 (0, T (X 2)",, has with probability least 1 - over S that
12000 EK(, m/8n
C (d (I (e/6))
120000,,
(d + In (e/8))
10/243 D
(A(S:T))
<
max (ES(()
m/ar
Cp
m
m
(25)
where 8n s..l 1-1/27 is the previously defined constant, C 2 1 is the constant from Lemma B.6, and c and c. are the following constants:
= (56872 3. In (24c)sn)²
C. 32 (24e)² Vcb sn
Note that applying Vab S Equation (25) would in fact suffice complete the proof of Theorem B.4.
Thus it remains only to justify Equation (25). For any choice of 8 E (0, 1) and T (X' y)", first observe observe that < 12, the claim follows immediately from the fact that the right hand side of Equation (25) is least (Owing the fact that c. 312)
We now proceed to inductive step. For the sake brevity, we will often suppress the distribution from which random variables are drawn when writing expectations and probabilities, e.g., Ps rather than Psupp. Now fix a choice of E (X x ))), E (0, 1), and > 12. Let as equal the right-hand side of Equation (25), i.e.
12000 Σ EA
C In (e/5))
12000 (Ie,S") m. m/nn
C In (e/8))
ag
c
(S:T))) m/ 5m
m
m
(26)
20

---

Then invoking Lemma B.5 and a union bound, we have that
D
10/2433
(A(S:T)) as
(27)
10
d
5687
max
P As, LnTT (S) x.y
max
avg
2
h(x) # y
50
243
Σ
P
5687
max
P (
>
10
h(x) + y
40
REA(S,, ( (77) x.y
243
(L.......777
(28)
Thus it suffices to show that for i # j [
10 h(x) # y
6
P 5687 AEA S,nLL)))
P avg (I 2 243
as S
26 27
(29)
immediately apply this inequality with Equation (27). Then it remains establish Equation (29). As the pairs (S1.u, Si.n).... (S27.u. S27,n) are all i.i.d., it suffices to demonstrate the inequality for, say. 1 and i = 2. To this end, fix arbitrary realizations (St)agkg27 of the random variables (Sa)3<k<27: we will demonstrate the claim for any such realization.
First note that if we happen to have realizations 1, of S2, S2,n such that
C
10/2443 Se x.y
IP
avg (A (T))
10
S Cc
C (d + In
4g 5687
243
5687m
then we are done by monotonicity of measures,
10
5687
max AE x.y
avg (A(S2,,i S2n (2) 243
h(xx # y
S as.
(30)
Furthermore, consider any realization S2,n of S We note that by = SS = 36 for 1: > 12, and by Algorithm 2, it holds that (S,, 3 m/33. Thus, we may invoke the inductive hypothesis with A(S2,u S2,n L TT) and failure parameter 8/24 in order to conclude that with probability least 1 - 6/24 over S2,u.
120,0
(
max s ('ES(Sp
m/(39sm)
C (d (24e/((2e/0))
(IM,5") m/(39sn)
C In (24e/8))
Cp
+ Co
m/36
m//6
(31)
Furthermore, for any a, b, d > O, we have that
a + Vabe + ed < a + avb + evT ed od= (1 + vb) a (d+ vb) cc
(32)
where the incquality follows from the fact that Vabe S max bba vbc²) S avb + cvb. Now. combining Equation (31) and Equation (32) (with b cb. d ce), obtain
c 10/243 (A(S UT)) (1 vol
12000E SM)
max S'ES(S
mm(35mm)
C In (24e/8))
(ce Vcl)
m/36
12000224
C (d+ + In (24e/0))
< 2
2co
m/(398n)
m/36
(33)
21

---

Note that the second inequality makes use of the fact that O. 2 1 and CD S Cc. We thus conclude that for any realization S2,1 of S2.n. the above inequality holds with probability at least 1 5/24 over S2,u. Further, as S2, and S2 are independent, the inequality also holds with probability at least 1 1-644 over S2,n, S2
We now let
120000, m/(30sn)
Cdd+ In (24e/6))
as 2/c
max (
2ce (m/36)
and consider the following three events over S₂ = (S S2,u):
C In In
E
Ce
CD
220/243
S2, S2nUUI) S asa
5687m
I(d+In
E2
CD
10/2243 (A(S2115 S2, UT))
5687m
E3
LD (A Sa,1 UT)) as.
By Equation (30), we have that for S2.m, S2 E Es, the bound in Equation (25) holds. Furthermore. from the comment below Equation (33), we have that Sy,n. S2,u E E3 happens with probability at most 8/24 over S2,7, Sznu- For brevity, let as denote the right-hand side of Equation (25). Then, using the law of total probability along with independence of $ and S2, we can conclude that
10
IP
5687 max
PP AE (7) x.y
y (A(S2,15 S S2, UT))(
h(xx +
as
(34)
S1.Sa
243
10
E
5687 max he.A(S..:SL,nLLT)) x.y
P avg (A(SS,.: S2. L))
(xx) Fy
> 0g
E1
P [E1]
S.
243'
10
E
5687 max IP
P
avg (A(SS,ui S2.1 (T)))
h(x) fy y
as
E2
IP [6a2]]
82
S1
hEA(S, (S.,. S SI.UT) x.y
243'
10
E
PP
5687 max hEA(S) S (T)
P avg (A(S2) S2,n (T))) >
1((x ty
as
Eg
IP [(Ea]
S2
S1
243'
10
E
5687
max
P x.y
avg
())
(xx)
#
0g
E
+ + 8/24.
St
243
Note that the second inequality follows from Equation (30), Equation (33) and P [Ei] < 1. Thus, if we can bound the first term of the final line by 25/24, it will follow that Equation (29) holds with probability least 1 5/(26- 27), as claimed.
To this end, consider realization S2 of S2 E Fj. For such an S2, we have that
10/243
P x.y
( S2,n U (x),)))) >
10
0.
243
Then, again invoking the law of total probability, we have that
10
5687
max
I x.y
avg, (A(SS,;; (T)) 243 h(x))((xx))))())) +
AEA
10
= 5687
P h(x) + (ASs,u hEA(S hEA(S..US x.
max
>
243
x c/ 10//243 (A(S S2,n UT)).
(35)
Now let A = {(z,1) v) E (X x )) avg (A S2n LTT) 243
10
and N, = =S1,n Al.
As S2 E E1, we have that
C. In
P P = - 10/243 (A(S2,u: S2, S2)))T))
2
5687
22

---

Then, owing to the fact that S1.7 ~ D(m/sn) note that m/sn = [//(S//|SS)) |Sn| - this implies that
E Ni] = P Si.m
x.y-D! [ [A]
(m/sn) 5687 8m
Thus, by multiplicative Chernoff bound, we have
C.Old + In (e/0))
P
N1
E St, Si.nnD(m/an)
N2]/2
2 1 exp
S SLnnD(mm/a))
8. 5687sm
2 1 - 26(() 19
(36)
Note that the second inequality uses the fact that ce = 312 In (24e)² Vebsn. Now let N1 be any realization of 1 such that
N1 2 St Dimmn/m
N1 = 2 CD (2,
C20/243
Notice that Si,n AA D Javg (A(S2,u; L)) 2
Now, combining Equation (35) and Lemma B.6, we have that with probability at least 1 - 5/24 over S A,
10
5687
max P kE x,y
avg (2 2 243'
h(x) + Fy
(37)
+ (d+ (CC In (24e/0)) /N,) 10/2443 (A(S LT))
< 5687
max SEA(SI.
We now bound each of the two terms on the right hand side of Equation (37), considered after multiplying out the term associated with 210/243 -Beginning with the first term, and recalling that N1 = S 17 AI, we have
Ls Ls (1i) -/
10/244 (A(Sq,u; S2n LT))
(1(xx) y}
max
Σ
c10/213 (A(So,
S2,1 LT))
N1 21(h(x) $y}
Σ
<
max
hEA(S..
m//n 21 (A( y)
(s.))S.,nnA
< max
SES
m/sn
(a,y)s.
21 (1(( + y)
Σ
max S'ES(S (I
m/sn
(a.))ES)
2xt,
(38)
m/sn
Note that the first inequality uses the fact that N₂ 2 C 10/243 (A(S2,u: S2, (mT))(m/ss)/2 and the second inequality uses that h e A(SI,L: LT), meaning there exists S' S( LT) such that h A(S"). The third inequality follows from the fact that S n A Š for any Š S(S Si, TT (and especially for S') and the final inequality from both the FRM-property of A on S" and the definition of (tt,
23

---

We now bound the second term of Equation (37). In what follows, let 3 = C' in (24e/6)). We
will in the first inequality use that N1 LD 10/244 (A(S2.u: S2, L (m))m))))
10/2443 (A(S2,Li UT)) (d+ (24e/ /N1 CD
(39)
23 LD
C (A(S2,ui
m/sn
48
Vcb
12000 (Ir,S))
+ Ce
C(d++nn (24e/8))
m/34sn
m//3
m/8n /m
(by definition of F1 and Equation (33))
4/
120,02g((r.5") m/(35mm)
4,8% Ce m/33
m/sn
m/sn
(by + b S Va Vb and definition of 3)
$ / 4- 36
I(d+)((e/0)
S*ES($2LiSAnLLT))
max
22000E,
m//nn
m
+ / ce (In (246))² sn
I(
m
where the last inequality follows from 3 = C(d + In (24e/8)) < In (dd and rearrangement. We now bound each of the constant terms under the square roots. Beginning with the first term, we have
4 36 /ob (24c)sn = (56872 4. 36 /cr (24c) /5687 S VC685687
(40)
where the inequality follows from c = (56872 -4.39 In (24c)sm)* 2 that
For the second term, we have
V 4- 4- (In (24e)) sn = v 568772 4. (In (24c))² 8n /5687 & Cc.
(41)
where the inequality follows by e, 312 (24e)² Veyen and c (56872 .4. 36 (24e)sn)²
Then we conclude from Equation (39) that
C (d + In (24e/0))
CD ((
110/243
(42)
N₂
Cdd+ (Id+In(e/0)) (e/6))
max S'ES(S2.iSa..ur)
120005, (Mt,
m/en
C + In (e/8))
+ Co
5687
m
m
Thus, by applying Equation (38) and Equation (42) to Equation (37), we obtain that for any realization 210/213
Ni of Ni 2 1/2 C/ (A(S2 S2,1 L) (m/a) /sn), it holds with probability at least - 6/24 over
24

---

Sinn ~ (.T.AAADMMMA(SL..L... S2. (z) # 3)² that
10
5687
max (EA. x.Y
P
avg avg (AA Sa,1 L ()) 2
h(x) +
(43)
243'
(H,
In
S'ES($
max
12000 (M.S')
m/an
max
Cb
m/8n
m
C (d (n/0))
+ Ce
m
Cdd+In + (e/6))
220000,
(d
max S'E)(S:T)
V
m//nn 9m
+ Ce
m/sn
m
m
ag
(44)
Note that the second inequality follows from the fact that E S(S., Sun T)) for 1,2,
meaning 5' E S(S; T). The equality follows simply from the definition of as in Equation (26).
Now, combining the above observations, we can conclude that for any realization S2 E Ei of S2.
10
5687
P hEA(S) U LLT) (x.y)
max
avg
>
h(x)
#
S as
Si
243
10
5687
max
P
avg (A(S2,11 S2, (T)))
>
h(x) +
S as
hEA((S S 11. T) (x.y)
243
N1
2 CD
20/2243
(A(Se,L; LTT)(mm/sn)22 12)
x
IP
4/
220/243 (2))
S
1
6 19 (0)
1
24
212
(Note that the first term the right side of the first inequality is distributed across two lines of text.) In particular, the first inequality follows from the law of total expectation, and the second from Equation (36) (see the comment below the equations) and Equation (43). Thus, the above implies that the term in Equation (34) which conditions upon S₂ E E1 is bounded by 8/2"1. Altogether, we can conclude that
10
5687 max S,SS, hEA(ST.US (x.y)
IP
avg (A(S2,ui S2, (7))
h(x) * y
as
243
210
As 6/210 < 6/26.27, arrive Equation (29), which previously argued concludes the proof due to the fact that (Si,u:
S27.n) are i.i.d.
C Augmentation of A, Through Tie-breaking
Let us assume we are given training sequence S of size m = 3 for k > 1. We then take S and split it into three disjoint, equal-size training sequences S,. S2, and S3, We denote the sizes of S S2 and S3 as m' = m//3 On S and S2, we train Ar, (Si) and At, (S2). where we recall that t, and to denote the randomness used to draw the hypothesis in Ae, (Si) and At, (S2) from, respectively, A(S,; 0) and A(S2;0).
We now evaluate Ae, (Si) and Ar, (S2) on S3 and consider all the examples (x, 8) S3. where avg, (z))))z, v) 2 11/243 or avg, (A,, (S2)) (z. y) > 11/243. Denote the set of all such examples as S We now run the ERM-algorithh A on S to obtain /tti = A(S
Le.. the restriction of D to those (s, v) pairs satisfying the given condition.
25

---

For point 2, let Tie 11/43
(Ai, (S)). Ae, (82): Mrle) (a) be equal to the label y if both
Σ
1(h(z) = y) /), (S:)) 232/243
hEAr, (81)
and
Σ
(1(a))=)//1) (S2) 2 232/2433
AE (Sa))
Otherwise, we set (x)). ). In other words, if both Ad, (Si) and At, have least 232/243 of their hypotheses agreeing on the same label we output that label; otherwise, we output the label of (z).
Notice that if there were a true label and point æ, such that we ended up outputting the answer of (x), then at least one of As, (S1) and Ar, (S2) has more than 11/243 incorrect answers, not equal to y on x, which we know by Lemma B. is unlikely. Furthermore, in the former case and the tie erring on (I, y), then both As, (S1) and Ar₃ (S2) err with at least 232 /22/243 fraction of their hypotheses, which again is unlikely by Lemma B.1. Thus, both cases of possible error are unlikely, which we exploit order to demonstrate the following theorem.
Theorem C.I. There exists a universal constant c cZ 1 such that for any hypothesis class H of VC dimension d, distribution DD over X x Y, failure parameter O < 5 < 1, training se- quence size m 3 for k 2 5, training sequence S ~ D and sampling size t1, t2 > 4. 4.24 in (2m/ (86/0)))) we have, with probability at least 1-ô over S1, S1, S3 Dmn33 In
and the randomness tı, t2 used to draw Ae, (S1;0) and Ar, (S2; 0), that:
LD /Ti221/243 (S)) bese)) < 2.0888T +
cr (d + In (c/5)) + cld + In (e/5))
In the proof of Theorem C.I will need the following ERM-theorem. Recall that we take A to be an aalgorttmr,,mm meaning A is proper (i.c., it always emits hypotheses in H), and for any training sequence S that (A())) minNEH (h(h).
Theorem C.2. [Shalev-Shward and DeniDavid (2014) Theorem 6.8] There exists universal constant
C' 1 such that for any distribution D over X x 1), any hypothesis class H. S {-1, 1]* with VC dimension d, and any ERM-algorithn A, it holds with probability least - 8 over S ~ D that for all h E H:
Lo(A(S)) S inf LD(h) + / NEW
C'ld + In (e/0))
m
note that by the definition of 11/23 for Tie 1/243 (S)). (S2), hrie) err on a fixed example (a, v). must be the case that either there exists y/ + E 1-1, 13 such that
Proof of Theorem C.I. First
Σ 1(h(x) = 3/1 A,, (8.)) 2 232/243 and (Si)
Σ
-MM=))='1//A1, (Sa)) 232/243
hEA.,(
232
232
+ avg (Ae, (Si))
avg (S2))
243"
243
or the case that for all y' E 11,
Σ 1(h(x) = y'} 232/243 or
Σ 1(h(x) = 5/} 232/243 and hise +
NE,r,, (St)
(S2)
11
11
aavg, (A,
(SI))(r,)) 2 or avg (Ar, (S2))
2
and hei((z) +
243
243
26

---

Thus, we have that
LD (Tie (A,, (s)), (S2), Mase)
(x) +8)
232
232
S (xy))D
avg (At, (S1))
ava av (S2))
243
243
11
Mrie # yy avg (A,) 2
or avg
2
(xy))
243
243
(45)
We now bound each of these terms separately. The first term we will soon bound by
232
232
P (xy))D
a (Au, (S)))(x,y)
avg
avg (S,)) 2
243"
243
S 1.0888T + 16cCr(d 2 (8))
6cC In (ec./6))
(46)
m
m'
with probability at least 1 826/c,,, over S, S2, t, and tz. Likewise, the second term we will soon bound by
Meie + (e,AA, + Ar, (S2)(x) S v ArOC In (cn/o)) 5c0" In (cue/0)
P (xY)>
ml
(47)
with probability 40/ca at least over S S2, S3, t and tz, where C, C 2 are universal constants and Ca = 86. Applying a union bound over the above two events establishes the claim of the theorem.
Let us begin by pursuing Equation (46). To this end, consider any realizations of S S2, &i and i2 of S, S2, t and 22. We note that for an example (x, y) with avg (At, (Si) (x)))) v) 2 232/243 and avg, (Ar, (z, y) 2 232/243, it must be the case that both Ar, (Si) and Ar, (S2) have at least a 243-fraction of hypotheses which err at (x, y). Now let h be random hypothesis drawn from Ae, (S.). Then with probability at least 232/243, h(x)) y. Thus, for any such example (x, y), conclude that
232
232
232 avg (Sz)))
232
h(x)) # y. avg (A,
> 1
avg (Si))(z,,
243
243
243"
243
Multiplying both sides of the above equation by 243/232 and taking expectation with respect to (x,y) D on both sides, we obtain
232
232
P (x,y)~D
avg (Ag, (8))) 2 avg (A., >
(48)
243
243
243
232
S
E
fi(x) + avg (A,, (x,))
(49)
232 fi
(x.y)>>
243
Now by h being drawn from Asg (S1), which in turn is drawn from A(S; 0), conclude that h is contained in A($1; 0). Thus,
E
P (x
h(()) 4 y, avg (Ar, (S2)) 232/243
can be upper bounded by ((S P Pxx,y)> h(x)) y, avg (Ā,, (S2)) 232/243 Using this observation and substituting it into Equation (48), we obtain that
232
232
avg ( (5))) > avg (Sa))(xx)) >
(x.Y)>D
243
243
243
232
P heA(S,;)) (x
max
h(x) * y. (A)) >
232
243
243
11
h(x) Y y,ava. (A,
max
232 keA((S):) (X,))D
243
27

---

As we demonstrated the above inequality for any realizations of S1, S2, and t2 of S1, S2, t1 and t2, the inequality also holds for the random variables. We now demonstrate that the right-hand side of the above expression can be bounded by
243
11
h(x) + y, ayg (Ar, (S2))
max
232
(()(()))) (x-Y)=
243
16cCT(d+ + 2ln (3ca /)) 6cC + In (ecw/o)) m'
I 1.0888T +
(50)
m'
with probability least 1 - 826/c, Co over Si, S2, and t2. We denote the above event over S S2, and 22 Eg. In pursuit of Equation (50), we now consider the following events over S₂ and t2:
eln (cne/o) m'
E
D
111/233 (S, S
cIn (c,c//)
c(d + In (cne//)))
E2
< cb) C11/243 (S2) S cT
m'
m
> cT + cld + la (cue/ō)) /11/243/ Ar, (S2)) C
Fg =
ml
where c is at least the constant of Theorem B.2 and also greater than c 2 2- 10 We first notice that if S2 and t2 are realizations of S2 and t2 in E1, then by monotonicity of measures, have that
243
11
2c In (cae/o)
max
IP
((x) + y, a (A (S2))
(51)
232 ((,,)) (xy))D
243
ml
which would imply the event EG in Equation (50).
We now consider realizations S2 and t2 of S2 and t2 in Es. Let S1,,7 denote (Si).n and S1,4, (S1)., )a, for E {1, {1,..., 27). Using this notation, we have that
243
11
max P hEA((S))) (x.y)>D
h(x) * avg (Ar (S2))(x,)) 2
232
243
243
11
max 232 ic (E()....77) hEAASS... (x-y)D
max
P h(x) + y, avg (Ai,
>
243
We now bound the max term associated to each E [27]. To this end, fix such an and let A = {(x,v) avg, (A,, v) 2 11/243]. Also, let N, denote the number of examples in Si,.n landing in A, i.e., N; S 7 A/. Now by S2 and l2 being realizations of S₂ and to in (A(A,, 2 cla (cwe/d) Thus, as S1,in ~ DDm'/an Ez, we have that IP [A] -P(x,y>>[[A)
m
we have that E [N.] = P[A]m' [.4mmm/snn.. Furthermore, this implies by Chernoff that with probability at least 1 8/c, over S,,,m,
IN. (1 1/1000) (P[[AAmm/sssss
exp exp (-F[A)m' /(2 1000 s-)) 2 1 58/c
where the last inequality follows by P[[]] > (cwe/)) and e 2 2 10 Let now D(. A) be mn
the conditional distribution of A, i.e., for an event E over X x V, we have that D(E A)
F P(xxy>> (xx E E n A) PP [xx y) E A]. Since S1.mm ~ D, it follows that S 7 A ~ D(- A: Consider now a realization N; of N; with
N 2 (1 1/1000)
(P(Ammm/ (//mm//// 8n = (1 - 1/1000) LD (S)) m'ssn
Then by the law of total probability and definition of D( (AA),), we have that
11
max
IP (X
h(x) y. avg (Ai, (S2)) 2
hEA(S
243
11
11
max hE..(S....S....)
IP (x,y)D
h((z) + avg (A,, (82)) Z
IP
avg
avg
(A,
2
243
(x.y)D
243
I [h(x) + vl Cp (A))
max
AEE.(S..........))
(x.))
28

---

where the last equality follows by the definition of D(-) A). Furthermore, by Lemma B.6, we have with probability at least 8/c, over Si,in 7 A ~ (- A) that
max ( (x.))-((1))) [1(x) + LD (A,,((
Ls ( + Cid+ + (ec./o) he.(SS...u
S (A
max
(52)
N
where C' is the universal constant of Lemma B.6. We now bound each term, starting with the first. Now, max uu..........)) Ls L is equal to uis En (h, S1,in n A)/N, And as any h E A(S I, S (1i,m) is equal to = A(S")) for some S E S((S) I.us S (.i,)), we get that AS.. Eg (h, S1,m 1 A) is equal to S1,in) contains the training sequence SI.in A, get that (A))"),
Eg (A(S"), S1,im n A).
Furthermore, since any S'
max.).s((S...uS...) E (A("), S1.an A) S max.' Ey
Now we have that A(S') is a ERM-algorithm run on S' thus A(S") E H and any other hy- pothesis in H has larger empirical enror on S' than A(S"), including It. We thus have that Ey ( which, since is con- tained in S1,; (Si);, can further be upper bounded by Ey (tt, (1,a). We can thus conclude that
Ey (A(S"), ", S") S
L (S (1) S S1,DN, = m' Ls.. (10)((33) bE A(S.suuiS
max
Note we have used that [S,.l = m /33. Now, using the fact that we have crystallized an event N; with N; 2 (1 1/1000) (A (S2) )ma) )m'/sm, have that the first term of Equation (52) (after factoring out the multiplication) can be bounded as follows:
m CS (a) s (S(,
(S2)) heA(St..nSt.nn)
3N, (kt)
1000sn (s,,(h)
33999
1000 27
Ls.,, (H)
(53)
999 26
where we, in the last inequality, have used that $n
3
This concludes the bound on the first
1-
term in Equation (52).
Now, using that N, 2 (1- (1-1/1000) (S)))m we get that the second term in Equation (52)
can be bound as follows:
C(d + In (ec,/o)) (D(Ar, S
1000C(d+ In (ec,/))) LD (A)
N
999m'
33. 27 -700100 (ec./80)) L (1,
26 909m'
29C(d + (ecu/00)) (A
m'
We now use the assumption that we had In the second inequality we have used that 8n = I realizations S2 and to of S2 and t2 Eg, i.c. such that (D(A), S cr e(d+iu (c.e/6)) allows us to conclude that
This
m
4C(d + In (ecu/5)) (o( ml
cT + 4C(d+ + In (nc.//5)))
e(d+In ((ute((eee6))) (cne/51) mi!
(54)
ml
4cCT(d + In (ec,/5)) m
+ 4cC(d + In (ecm/5))
(55)
m!
29

---

where we have used the inequality va+bs v for a. b 2 0 in the last step.
Then, to summarize, 1 1/1000) (52))mm /n occurs with probability at least 1 8/c,, and that conditioned on this event, Equation (52) holds with probability at least - 8/c,. Consequently, we have that with probability at least 26/ 26/c,, over SI, each of Equation (52), Equation (53) and Equation (54) hold. Then, with probability at least 20/cu. over S1,5 we have that
have seen that the event N: >
1/1000) IP[Ajm'/sn (1
243
11
max (S.......
IP (x.Y)=
h(x) & y, y, (S2))(xx))
232
243
243 1000 27
4cCT(d + In (ECu/OO) 4cC(d + In (ec./o))
232 999 26 Cs (1))
m'
ml
S 1.0888 (1)) + AcCT(d+IInees In (eca/o)) 4cC(d+ (ecx/6))
m'
m'
Now, invoking a union bound over i E {l,..., (,,...,27],, 27). we have that with probability at least - 548/c. over S1, it holds that
243
11
IP Mxx # y, a,a (Ar, 2
max
232 he.((S.:) (x.Y)~D
243
AcC'((d In (ecu/o)) 00)
4cC + In (eca/8))
S 1.0888
max (E(
Ls.. (1)) +
(56)
m'
m'
Furthermore, by Lemma B.3 and another union bound over S1.,,..., S1,27, we have that with probability least 1 276/c, over S₁ Dm' it holds that
max Ls., ( 2r In (ca/8) (E7
In (cn/8)
(57)
3mn
m'
Thus, by applying the union bound over the events in Equation (56) and Equation (57), we get that with probability at least - 818/cu ccu over S1, it holds that
243
11
P kEA(()):)) (x.y)>D
max
h(x) F y, ay (S2))(xx))))
232
243
2r In (cu/0)
2 In (cu/8)
4cC'(d In (ecu/o))
4cC((d + In (ec./6)) mn
< 1.0888
T+
3ml
ml
16cCr(d + 21n (3cu/8))
6cC + In (ecu/8))
< 1.08887
(58)
m'
m'
Note that this suffices to give the event Eg in Equation (50). We remark that demonstrated the above for any realizations S2 and 12 of S2 and t2 in Ezg
We now notice that by Theorem B.2, the fact that t 4 243 In (2m/(5(d In (86/8)))), and the choice of C2 86), we have that Ps [Ea] < 6/cμ- Combining this with the conclusion below Equation (51) and Equation (58), and with the fact that S1, S2 t2 are independent, we have that
P [Ec] S2.
E
T [Ea] 1c
+
E
P EE [E]]
E Sa.ta
P [Eal 1 [Es} Si
Sa,ta
Sa.ta
2 P
Eg + (1 815/cu)
P
[Ea]
Sa
Sz.t2
2 (1 - s16/c,)(1 Sz.ta [Ba])
> 1 825 828/cu.
Note that first equality follows from E1, E2, Ea partitioning the outcomes of S2 and to and the first inequality follows from the conclusions below Equation (51) and Equation (58), which state that Eg holds with probability 1 on Eg and with probability at least 1 - 818/c, Eg. The second
30

---

inequality again follows from E2, Es partitioning the outcomes of S2 and to and the bound Fs [Ea S 6/cu. which shows Equation (46).
We now proceed to show Equation (47), i.e, that with probability at least - 45/ca over S1, S2, S3, t1, t2, it holds that
P (x,))DD
Meio # y, y,ag (Ae, (S,))(x,)) 2 or avg (A (8)))
11
11
243
243
ST+ ATCC' In (cw/ 5c0' In (cue/0)
(59)
m'
m
We denote this event Ep. Towards proving the claim, we consider the following event over S1, S2, t and t2,
11
11
c (cue/0)
E4
P (x-))~
avg
2 or avg, (S)))
S
243
243
m'
As previously mentioned, we take e to be at least the constant of Theorem B.2 and to also satisfy
2 2.2100 10%
Now, if we have realizations S1, S2, t and t2 of S1, S2, t1 and t2 in Es, then by monotonicity of measures, we obtain that
11
11 avg (S)))
cln (cue/8)
P hue F y, avg (S:))(x,)) 2
(x,Y)//
243
243
m'
which would imply the event EF in Equation (59). Now consider a realization of S1, S2, t1 and to of S,. S2, t1 and t2 on the complement E4 of E4. We then have that
cln (G.e/8)
IP (x
avg (A., (s:))(x,)) 2 11/243 or avg (Ar, (S2))(x,)) 11/243
2
ml
We recall that S are the examples in (x, v) E S3 for which
11
11
avg (A, (z,)) Z or avg (S2)) 243
243
In the following, let D x) be the conditional distribution D given that avg, (Ár, (s,)) That is, for an event B over (X' x ))) we have
11 or avg (A,, (S2) (z, v) 2
11
243
243
P(xx)~D (x,y) E B, avg (A,, (Si))
2
11 or 243
11
243
D(B +)
PixyYW avg (An, (s))) N
1l or 243
1
243
Thus we have that S
D(B] F). We now notice by S3 ~ D that
| m
P avg. (A,, (S,))(x,)) 2 or avg (A,, (S2))(x, 2
11
11
(x,y)>D
243
243
Using Chernoff bound, this implies
11
11
P Sa
$ 2 m'
P avg (Ag, (Si))(x,)) 2 (xy))>
or avg (Ar, (X2) Z
/2
243
243
11
11
21 1 - eep
-m'
avg
or avg (Ar,
/8
(x.y)=D
243
243
2 1 5/Ca-
Note that we are also using the facts that
11
c cln (cue/o)
P a (A,, (Si)) 2 243
or avg (A, >
(x,y)D
243
m'
and that > 2 1000 8m. Now consider outcome of N₂ = | where
m'
11
11
N > 2 (x
avg avg (S)))))
or avg (Sa)))
243
243
31

---

Now, by Theorem C.2 we have that since hus A(5 and S ~ D(-1 #), then with probability at least 1 8/cu over S
C'(d In (cu/o))
(x)ee()) x S inf (D()))(1)+
(x,))~D(-1zz)
hE#
N
C" In (c,/8))
S (D)
N
Note that the first inequality uses Theorem C.2 (and C' the universal constant of Theorem C.2), and the second inequality uses that 1 E H so it has error greater than the infimum. Now, using the law of total expectation, we have that
11
11
I (x.y)-
hnie (x) # y. avgy (As, (S))) 2
avg, (A, Z
243
243
11 243
(x,1) (x) y
P
avg (5))((xx))
or avg (S2))()) 243
(x.y)>D
In
(LD(I))(H++ +
N₂
11
11
x P (x
avg (SI) 2 or avg (A,)((,,))))(xx.))
243
243
We now bound each term in the above. First,
(1T)))))
(x,))D avg a (x,)) > 11/243 or avg av (Ag 11/243
(x) + y, A, (si) * (S2)
x.ywD
which is less than T. Furthermore, for the second term, have by
N 2 m' TP
avB (S1)) 11/243 or avg (A,, (S2)) 11/243]
2 (xy)~D
that
C' + In (c./6))
11
11
P (xyy)D
avg (5))) 2 or avg (Ar, (82))
N4
243
243
2C" (cu/5))
(C11/240) (A,, (Si) + -2 211/243 (S,))
m'
where the first inequality follows from plugging in that
m
N
IP avg (S1)) > 11/243 or (A,, y) > 11/243]
(X
in the denominator, and the second inequality follows from a union bound over the event
avgy (A,, (S,)) > 11/243 or avg (A,, (S,)) 11/243.
Thus, we have shown that with probability at least 28/ cu over Sg. it holds that
11
11
P [xso(x) * ava (A,, (Si))(x,)) 2 or avg (S, 2
(x.YDD
243
243
20'(d + (InddIInc//// (c.///)) (A, (Si) + (o(A,,
< T
ml
32

---

which, in particular, also implies that with probability at least 1 - -66//a over S3
11
11
(x)( + y. avg (Ā,, (S:)) 2 or avg (Sz)) 2
(x.y)>
243
243
2C In (Cr(An, (5:)) + (A(
cln cln(c///))
IT+
m
m
Thus, since the above also upper bounds
11
11
T
haso (x) # y, a (Ar, (S,)) 2 or avg (AI,
(x
243
243
for any realization S1, S2: 4 and l2 of S1, S2, L1 and L2, on E,, (with probability 1), we conclude that for any realization S1, S2, 11, and to of S2, and t2, it holds with probability at least 1 - 26/ cu over S3 that
11
11
P
(x) # yv (Ar, (si)) 2 or avg avg (A,, 2
(x,y)>/
243
243
2C In (c) (A, + (o:) ST+
c (c,e/8)
m'
m
Let this event be denoted Eg. Now, let Eg be the event that
Es = LD (A, + (D,A,, (52)) S 2 cT + c(d + In (cnee/))) }
ml
which, by Theorem B.2, the fact that 11, 12 2 4 243 In (2m/(5(d+1)) In (86/5)))), and a union bound, holds with probability at least 1 - -225/c. 26//cu. (We let c > be universal constant at least as large as the universal constant of Theorem B.2, and with c 2 2- 10.)n.) Now, notice that for realizations Si. S2. t and tz of S,, S2, ti and t2, on Eg. it holds with probability at least 1 25/c,. over S3 that
11
11
P
(x) + y, avg (Ān (x,)) Z or avg (Sa)))x,)) 2
(x-))D
243
243
2C' In (cw/8)) CD CD(AA, (5:)) + Lo(AA,
cln (cue/8)
ST+
m'
m
4C' (cw//8) (cT
cld+iu c(dtl((eee/8)) (cve/o)) ml
cln (cwe/0)
ST+
m!
m
(r In (n 5cC' In (c,ee/)
ST+Y
mi' where the first inequality follows by Eg, the second inequality by Es, and the third inequality by Vu+ b < Va + VT. We notice that the above event is Ep in Equation (59). Thus, by the above holding with probability at least 25/c, for any outcome of S1, S2, l and le of S1, S2, t, and to on Eg, and by $1, S2 and S3 being independent we conclude that
m
[Ep] 2
E
P [E Esl 1 [
S2
St.
Sq
E
P [F3]] 1
S. S.
5₁
E
[[1 c,)
Sa.
(1 28/cu)²
> 45/co.
Note that the equality follows from our previous reasoning, i.e., that for outcomes of S1. S2. &1 and to of Si, S2, i and t2 on Eg, and outcomes S3 of S3 on Es. E, holds. The second inequality follows from the fact that Es holds with probability at least 1 - 25/c, over S3 for any realizations S,, S2, 4 and l2 of S,, S2, t and fz. The third inequality follows from the fact that Egg holds with probability at least 1 26/ 26/c, for $1, Sg, t1 and t2, which concludes the proof of Equation (47), desired. L
33

---

D Best-of-both-worlds Learner
In this section we demonstrate that splitting a training sample Dm into {S, Dm/3 he(s)] followed by running the algorithm of Hanneke et al. (2024) on S1, running the algorithm of Theo- rem B.2 on S2, and selecting the one Amio with smallest empirical error S3 gives the following error bound:
r(d ( In (1/8)) m
(d In (n
CD(Iimin) = min 221.T
m
(nd+1((1/0) m
In (m/d) (d + In (1/6))
(1/0))
++0
m
In pursuit of the above, recall the error bound (Hanneke al., 2024, Theorem 3), which establishes the existence of learner Á which with probability at least å over S D incurs error most
Co(A(S)) ST+ v
cridd In (1/8))
d' In (m/d) (d In (1/8))
m
m
for a universal constant d' 2 1. We will in the following use As to denote the algorithm of Theorem C.I. In what follows let m' m\/3
By invoking the previous bounds A. and Á with 6/4, and further employing union bound, we have that with probability at least 8/2 over S and S2, both À and A will emit hypotheses satisfying:
Co(A(S))) s <++ 1 + eln (m' /d) (d In (4/8))
(60)
m'
CD(A((S); 0)) 221 cr(d + In (4/8))
c cld In (4/8)) m'
(61)
where e is the universal constant of Theorem C.I. Let G denote the event that S satisfies the previous condition, which, as we have noted, has probability least 1 5/2.
Now consider realizations S₁ and S2 of S₁ and S2 with (S1, E G. Further, let Amin arg min E (A(S)) (Ls, (h!)). We now invoke Lemma B.3 on S3 with the classifiers A(Si) and A, (S2; 0) (and failure probability 8/8) along with a union bound to see that with probability at least 1 5/2 over Sy, have that both choices of h (A(S)),A(SS 0)) satisfy
Cs, (h) (8/6) m
4ln (8/8) m'
(D(h) < Lsy(h) +
+
(62)
and
2 (h)) In (8/8)
2 (8/5)
4ln (8/5)
(h) < Cb(h) +
ml $ 22Cp(h))
+
(63)
3mm
ml
34

---

Note that the final inequality follows from the fact that Vab I a + b for a, 6 > 0. Then, using the previous inequalities along with the definition of mmnn we have that:
2 L.s (Dain) In (8/6) 4ln (8/6)
(D(mmmi)) S Ls (Amin) + +V
(64)
m'
m'
2 Ls, (h) In (8/0)
4 (8/6) m'
min he ((S)
(h)(h)+ +
(65)
m'
2 (n CD(h)
6 (8/6)
min be ((S)))))
ml
ml
2 (2 + 4lm (8/8)/m') (8/0)
(66)
m'
(D(1)) (CD(M)+ + +3 he ((S))
2 (1))) In (8/0) 9 (8/8)
min
(67)
m'
m
In particular, the first inequality follows from Equation (62) applied to hin. the second from the definition of Mmins the third from Equation (63), and the fourth from the fact that va + + S vā - vb for a b > O. Now using the equations in Equation (60) we have that
(D(((S))) ST crid In (4/6)) m'
c' In (m//d) (d + In (4/0)) 2 + 2d In (m' /d) (d
In (4/6))
ml
m'
(68)
since Vab S a + b for a, b > O. (We are further assuming that [2d), standard condition.)
Then, using Equation (68) and the fact that Va S v for for b > O, we have
2 2T 2 la (m (m' (d (1/8)) In (8/8)
2 In ml
m
m'
4r In (8/5) 2d In (m' (m'/d) (d + In (8/5))
m
m'
Using the previous inequality along with Equation (60), we have that
2 Lo in (8/0)
Co(A(S))) +3
m'
m
C'T(d + In (4/5)) d' (m/ /d) (d + In (4/8)) + +3/
47 In (8/5)
ST
m'
m'
m'
6c In (m'/ /d) + In In m'
(8/8))
9ln (8/8)
+
m'
ST+ c'rld In (8/8)) ml
16c (m' /d) (d In (8/8))
m'
Similarly, using Equation (61) and Vab + b we have that
2c (d + In (4/6))
(o((A(();))) 3.17 +
m'
Again using the fact that Va +b Va + vb for a, b >>> O. have that
2 (A, In (8/6)
6.27 In (8/0)
20(d + In (8/6))
m
ml
mn
35

---

Applying Equation (61) then yields
2 (Ar(((() In 9 (8/6)
(D(AA(S);))) + +31
m
m
cT(d In (4/6))
c(d + In (4/0)) + +3/
6.2r In (8/6)
Go(d + In (8/6))
I (8/6)
2.11 +
+
ml
m'
m'
m
m'
$ 2.17 + // (d (8/6)) 16e(d + In (8/6))
m Now plugging in the above expressions into Equation (64) which exactly the minimum of Á(S))
m'
and (S2; 0) arrive
cr(d + In (1/6))
16c (d + In (1/6))
CD(hmia) min 2.17 + VV
m'
m'
cr(l + In (1/8)) t 7+71
16d In (m' /d) (d + In (1/0))
(69)
m'
m
with probability at least 1 8/2 over S3 for any realizations Si and S2 of S and S2 in G, now let T denote the event Equation (69), then we have by independence of S S2, S3 that
P S-D
[[TT]
[(1 8/2)1((G]
SpnDDm/a S
S Spw/1
where the first inequality follows by independence of S1, S3 and G only depending upon S S2 and the second inequality by Equation (69) holding (the event of T with probability at least 1 - 8/2 over Sy for any S1, S G.. Lastly, note that
E D/
[(1 6/2)1 (1 - 5/2)(1 5/2) 6,
due G having probability least -6/2 over S1, S2 by Equation (60), which concludes the proof.
36

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The error bound of theorem 1.4, presented in the introduction, is the main contribution of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification: We discuss how there is still small gap in the known lower bounds and upper bounds after our new result.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
37

---

Answer: [Yes]
Justification:
Each statement in the paper is proven.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
No experiments are included in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
4.1 If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
4.2 If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
4.3 If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
4.4 We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
38

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
No experiments are included in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //nips.co ctipsscc/publlc//eee http:/ubblc/gguudeeeee guides/ /CodeSubmi ssi agionPllccy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
No experiments are included the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
No experiments are included the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
39

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
No experiments are included in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //teur//s.....//
iineess??
Answer: [Yes]
Justification:
We have no concerns about our work violating the NeurIPS code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
The work theoretical and the results hold under a mathematical model.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
40

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not release any model or datasets.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We do not have any code or dataset.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
41

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do release any code dataset.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We do not have any experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We have not experiments, so it does not apply.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
42

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
We do not employ LLMs for any important original components of the paper.
Justification:
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: : htt///euripppp htt////rips.c//ooeeeeeeeeeeeeeee htt.:////ooeeeeeeee////////111/0 for what should or should be described.
43


Reviews:
[{"review_id": "SU8mMKhZlr", "reviewer": "Reviewer_e2wi", "summary": "This paper studies PAC learning in the agnostic case, where the error is parametrized by \\tau = err(h*_D), the optimal error of a hypothesis in the class H for each particular distribution D. Recent prior work by Hanneke, Larsen, and Zhivotovskiy in FOCS 2024 showed that, when taking \\tau into account, ERM is not an optimal agnostic PAC learner. That paper gave a tight algorithm in the regime where \\tau > d/m, where d = VC(H) and m is the sample complexity. This paper gives an algorithm in the regime where \\tau = O(d/m). This paper's algorithm's correctness guarantee is error \n\nc\\tau + O(\\sqrt term + (d+\\log(1/\\delta))/m) \n\nfor c <= 2.1, whereas the lower bound (e.g. from  L. Devroye, L. Gy¨orfi, and G. Lugosi. A Probabilistic Theory of Pattern Recognition, Chapter 14) the same, but with c = 1 (and Omega(stuff) instead of O(stuff)). The authors leave as an open question to close the gap in the \"c\" parameter. \n\nThis paper's approach is inspired by [Hanneke 2016]. The algorithm splits the sample into subsamples and runs ERM on some randomly chosen fraction of subsamples. More specifically, the algorithm splits the samples into three portions, S1, S2, S3. On S1, it randomly chooses subsamples on which to run ERM, and then aggregates the results into a statistic estimating the proportion of ERM hypotheses that agree on any particular (x,y). On S2, the algorithm does the same. On examples (x_3, y_3) in S3, the algorithm sees if the statistics from the previous steps (using S1 and S2) disagree --- if so, that (x_3, y_3) is not discarded. The final training portion is to run an ERM on the (non-discarded) examples in S3. This final ERM is used to break ties, if the classifiers from using samples S1 and S2 do not have high agreement (on an input x). The authors consider this approach (running the base classifier twice, and using a 3rd ERM classifier for disagreements) as a \"main insight\" (line 107). \n\nIn Appendix E, the paper combines this new algorithm with the learner in [Hanneke et. al. 2024] by running the two algorithms on two separate samples, and using a third to pick the returned hypothesis with lower error. This with high probability achieves the minimum (incomparable) lower error bound from the two algorithms.", "questions": "---The technique referred to on line 111 (running one algorithm A twice on two samples S1, S2, and then using an ERM on sample S3 to break ties) seems like it could be reinterpreted as follows: \nWe run an (overall accurate) algorithm A that isn't stable on all inputs. On stable inputs, accuracy of A implies accuracy of the aggregate algorithm. On non-stable inputs, we train a special classifier (ERM on sample S3) that has good accuracy on these inputs that are \"hard\" for a \"stable\" algorithm. Specifically, I suppose \"stable\" here means \"many ERMs on subsamples will tend to output hypotheses that classify this point correctly\". \n\nDid ideas from the stability literature influence your approach? Are there other high-level connections between this problem/approach and stable algorithms? (For example, work on subsampling?) Are there plausible technical connections between this problem (which isn't overtly about algorithmic stability) and the stable algorithms/learning theory literature?\n\n---I believe the biggest weakness of this paper is the writing (clarity), which may detract from the community's ability to build on the technical contributions of this paper. This seems to stem from \n1) the submission page limit \n2) trying to put fully rigorous arguments in the main body proof sketch (section 3), and \n3) not having enough intuition-explaining paragraphs in the proof sketch. \n\nFor example, something similar to Appendix B's \"summary of approach\" should appear in the main body of the paper (for at least the 15\\tau algorithm). It would make many analysis sections, including the notation section (3.1, line 171) much easier to parse. One can bootstrap the algorithm from the notation, splitting algorithm, and analyses in the main body, but it would probably be easier for everyone if the whole pseudocode (of the 15\\tau algorithm) were present, say at line 170, with an accompanying intuition explanation. \n\n---Minor comments:\n\nLine 81: typo\n\n170: this intuition uses notation that won't be defined until the next page. Maybe it would help to include explanations of the sets represented by the notation, since this is its first use. For example, how does a reader say S_i, |_| out loud?\n\n172: similarly, what is T? Why is it necessary for the algorithm to have T? It would help to explain these when they first appear, rather than differing the explanation until the recursion is mentioned later in the analysis. \n\n186: I don't believe L_D (without alpha superscript) has been defined yet\n\n189: I think Algorithm 1 could be better explained if a picture of a sample, divided up into its pieces, with the notation in the figure, accompanied the pseudocode. Similarly for Algorithm 2's splitting later. I understand that for space/time reasons, this was not important to include, but I think it would add to the final \"full\" paper (perhaps a version without page limits). \n\n208: Was h^* defined somewhere?\n\n210: What does S_i, intersection refer to?\n\n232: maybe more precise to say \"at least\" \n\n533: direction -> direct\n\n691: typo in \"Recall that...\" (A to be)\n\n692: spacing typo", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Quality:\nThe paper's main focus, an agnostic learning algorithm with optimal error asymptotics in the regime where \\tau = d/m, is well supported. The theorems and lemmas in this paper appear to be completely proven and technically sound. \n\nClarity:\nAt a high level, the authors explain the proof approach well. First, the authors consider a simpler algorithmic approach achieving error 15 \\tau + stuff. Next, the authors discuss how to modify the first algorithm to achieve error 2.1 \\tau + stuff. These sections are broken down into subsections. However, at the subsection level, the explanations are dense and can be difficult to parse. The arguments are very notation heavy and it is difficult to see the overall flow of the argument in each subsection. The submission packs a lot of technical content into the main body of the paper, whereas I would prefer moving more technical content to the appendices in favor of additional connecting phrases within proofs, using more space to give intuitions for notable proof steps. As a result, it was difficult for me to verify the correctness of the proofs (line-by-line). \n\nSignificance and originality:\nThe submission addresses an open problem from a recent FOCS 2024 paper, essentially extending those results (when \\tau > d/m) into a different parameter regime (when \\tau = d/m). The paper claims that their idea of running two classifiers, and using an ERM on their disagreement regions to break ties, is a new idea that may find further applications. The particular subsampling used builds on prior work, but may also be interesting for the community. I am optimistic about these techniques being interesting for the community, although I am not familiar enough with the area to affirmatively say that the results (i.e., minus the techniques) are \"4:excellent\".", "was_revised": true, "final_justification": "Having read the other reviews and the authors' rebuttals, I have no further questions, and I continue to recommend my original evaluation.\n\nThe authors responded positively to ideas suggesting improving the clarity of the paper. This is great. In addition, I assume the authors will make a reasonable effort to ensuring their talks/posters/etc. are also clear, as they did with this submission.", "rebuttal": "We thank the reviewer for carefully reading the paper and for their detailed feedback. We now address their questions in turn.\n\n> Did ideas from the stability literature influence your approach? Are there other high-level connections between this problem/approach and stable algorithms? (For example, work on subsampling?) Are there plausible technical connections between this problem (which isn't overtly about algorithmic stability) and the stable algorithms/learning theory literature?\n\nGreat questions. The reinterpretation/restatement of our algorithm is correct, and the “stability” perspective is an interesting manner of interpreting the engine behind the algorithm’s success. In particular, the majority votes (i.e., each algorithm trained on $S_1$ and $S_2$) intuitively serve the dual purposes of “covering each other's mistakes” and of providing a “certainty score” for their predictions (i.e., given by the number of constituent voters which agree with the majority). This certainty score allows the algorithm to identify difficult or uncertain points, for which the third classifier can break the tie. \n\nUnfortunately, we cannot currently demonstrate that our approach is necessary stable in the sense of [1], owing to the fact that the classifiers in the majority vote (trained on $S_1$ and $S_2$), have overlapping samples, meaning that all such classifiers could conceivably change by altering even one example in $S_1$ or $S_2$. Furthermore, the tiebreak classifier trained on $S_3$ could then also change, despite the fact that an example in $S_3$ was not altered.\n\nThat said, we do believe that it is intuitively fair to think of our algorithm as a technique for stabilizing the alternative, which is ERM. We admit that we were not explicitly motivated by ideas from the stability literature, but we appreciate the reviewer bringing our attention to these intriguing connections. We will update the next version of the paper with a remark describing these previous points.\n\n> I believe the biggest weakness of this paper is the writing (clarity), which may detract from the community's ability to build on the technical contributions of this paper. This seems to stem from the submission page limit, trying to put fully rigorous arguments in the main body proof sketch (section 3), and not having enough intuition-explaining paragraphs in the proof sketch.\n\nWe thank the reviewer for the concrete suggestions for improving the readability of Section 3, and we admit that there is certainly room for improvement. We found this section particularly challenging to write, due to the technicality involved in the analysis as well as the page limit. Should the paper be accepted to the conference, we will most definitely use the additional page of the camera ready version to include the full algorithm pseudocode in the main body of the paper (as the reviewer suggests) and to generally improve the motivation, intuition, and pacing of Section 3. \n\nWe also thank the reviewer for the various minor comments/edits which they aptly noted – we will be sure to correct them in the next version of the paper.\n\n[1] Stability and Generalization Olivier Bousquet, André Elisseeff, 2002."}, {"review_id": "yXnC6M2OEq", "reviewer": "Reviewer_1ZdR", "summary": "For binary classification in the setting of agnostic PAC learning, it it shown in Hanneke, Larsen and Zhivotovskiy [HLZ] that ERM algorithm is sub-optimal in the sense that there is an extra factor $\\sqrt{\\log(1/\\tau)}$ comparing to the lower bound on excess risk, where $\\tau$ is the error incurred by optimal hypothesis. [HLZ] proposed a learner that removes factor in the regime where $\\tau > d/m$. This paper also achieves optimal rate when $\\tau = O(d/m)$, thus partially (due to a multiplicative constant in front of $\\tau$) solved unanswered problem.", "questions": "Although the explanations in section 3 are clear, it might be better to present the main steps that lead to the ultimate result and provide some motivation for the quantities in the main step. Since the paper relies on large amount of notation, it is not easy to keep track of the idea while reading through it. Also, in the first approach, have you considered switching the concrete numbers to alphabets so that readers have a better sense which choices of these constants lead to undesired multiplicative factor?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength: the paper clearly presents the problem with necessary preliminaries and the arguments for their claims are logically sequenced. It helps answer the question on complexity of agnostic binary classification problem. While the algorithm is rooted in the previous works, it is well-adapted along with refined analyses, allowing them to obtain the desired rate. \n\nWeakness: there might be a better way to present the section for sketch of the proofs.", "was_revised": true, "final_justification": "I appreciate the authors' commitment to improving the readability of the paper in the future version. The concerns are resolved in their response. My evaluation remains positive, and I keep the rating unchanged.", "rebuttal": "We thank the reviewer for carefully reading the paper and for their thoughtful feedback. \n\nRegarding the readability of Section 3, we admit that there is certainly room for improvement. We found this section particularly challenging to write, due to the technicality involved in the analysis as well as the page limit of the submission. Should the paper be accepted to the conference, we will be sure to use the additional page of the camera ready version to provide additional intuition and motivation in Section 3, at the reviewer’s suggestion, as well as to include the algorithm’s full pseudocode in the main body of the paper. (As opposed to merely in the appendix, where it has currently been deferred.) We believe these various modifications will make the section considerably less dense and more legible for the reader. We thank the reviewer for raising this important point. \n\nWe will also examine replacing some concrete numbers in the analysis with additional variables, while being careful not to unintentionally exacerbate the previous issue by introducing additional notation for the reader to keep in mind."}, {"review_id": "MpnsZEuHKa", "reviewer": "Reviewer_Y9zH", "summary": "This paper investigates the sample complexity of binary classification in the agnostic PAC model, focusing on a fine-grained analysis where the excess error is parameterized by τ, the error of the best-in-class hypothesis. The work directly addresses and resolves a key open question from a recent FOCS https://www.google.com/search?q=2024 paper by Hanneke, Larsen, and Zhivotovskiy, which asked for the optimal error rates in the small error regime where τ is on the order of d/m. The authors propose a novel and computationally efficient learning algorithm based on a sophisticated aggregation of Empirical Risk Minimization (ERM) classifiers. The main result is an algorithm that achieves an error rate of 2.1τ + O(√(τd/m) + d/m), which matches existing lower bounds and is therefore optimal in the τ = O(d/m) regime. The algorithm introduces an innovative tie-breaking mechanism that uses an ERM classifier trained on the \"region of disagreement\" between two independent voting-based classifiers. This work significantly advances our understanding of the fundamental limits of agnostic learning.", "questions": "Questions for Authors:\n\n1. The tie-breaker ERM is trained on a \"hard\" subset of data where the primary classifiers disagree or lack confidence. The analysis shows that this ERM still achieves an error close to the optimal h* on this conditional distribution. Could you provide more intuition for why a standard ERM, known to be suboptimal, performs so well on what seems to be a more difficult data distribution?\n\n2. The switch from 3 recursive calls in the initial approach (Section 3.1) to 27 calls in the improved approach (Algorithm 2) is a critical step in the analysis. Is there a deeper principle behind the number 27, or is it simply \"a number large enough for the probability math to work out\"? How sensitive is the final constant of 2.1 to this choice?\n\n3. The final learner uses a hold-out set to select between your proposed algorithm and the one from Hanneke et al. cite_start. This is a standard and effective method. Did you explore possibilities for a more deeply integrated \"single\" algorithm that smoothly handles all regimes of τ without explicit model selection?", "limitations": "No limitations", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\nHigh Impact and Significance: The paper makes a substantial contribution by resolving a timely and important open problem posed in a paper from a top-tier conference (FOCS https://www.google.com/search?q=2024). Characterizing the optimal sample complexity in this fine-grained agnostic model is fundamental to learning theory, and this work provides a near-complete answer.\n\nTechnical Novelty: The proposed learning algorithm is highly innovative. While it builds on prior techniques like sample splitting  and voting, the introduction of a tie-breaker ERM trained on the region of disagreement is a clever and powerful idea. The analysis required to bound the error of this complex, multi-stage classifier in the agnostic setting is non-trivial and technically deep.\n\n\nAddresses Multiple Open Problems: Beyond resolving the primary question about sample complexity, the paper makes significant progress on two other open problems from Hanneke et al. cite_start. The proposed learner is based on majority voting and is computationally efficient (in terms of ERM oracle calls), demonstrating that such learners can be optimal in this setting.\n\n\nClarity and Presentation: The paper is exceptionally well-written. The introduction provides excellent motivation and clearly situates the work within the existing literature. The proof sketch in Section 3 is detailed and gives the reader strong intuition for the complex analysis that follows in the appendices.\n\nWeaknesses:\n\nThe Multiplicative Constant: The primary limitation, which the authors are commendably upfront about, is that the leading constant on τ is 2.1, not 1. This prevents the result from completely settling the complexity of agnostic learning for the entire range of τ. While this is more of a direction for future work than a flaw, it is the main reason the problem is not fully resolved.\n\nAlgorithm Complexity: The final \"best-of-both-worlds\" algorithm is quite intricate, involving a three-way sample split, multiple recursive splitting schemes via Algorithm 2, two independent voting classifiers, a tie-breaker ERM, and a final model selection step on a hold-out set. A high-level block diagram illustrating this data flow could significantly improve the reader's ability to grasp the overall architecture of the learner.\n\nIntuition Behind Constants: The proof sketch explains that the final 2.1τ term comes from adding the bounds of two different error events, one contributing roughly 1.1τ and the other τ. A bit more intuition in the main text about why the tie-breaking scheme leads to this specific decomposition would be beneficial.", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s time and thoughtful assessment of our paper. Below, we respond to the reviewer’s questions in order:\n\n>Algorithm Complexity: The final \"best-of-both-worlds\" algorithm is quite intricate, involving a three-way sample split, multiple recursive splitting schemes via Algorithm 2, two independent voting classifiers, a tie-breaker ERM, and a final model selection step on a hold-out set. A high-level block diagram illustrating this data flow could significantly improve the reader's ability to grasp the overall architecture of the learner.\nand \n>Intuition Behind Constants: The proof sketch explains that the final 2.1τ term comes from adding the bounds of two different error events, one contributing roughly 1.1τ and the other τ. A bit more intuition in the main text about why the tie-breaking scheme leads to this specific decomposition would be beneficial.\n\nWe thank the reviewer for suggesting the idea of a block diagram to provide a high-level overview of the steps in our final algorithm. Should the paper be accepted to the conference, we will try to find space for it in the final version of the paper (currently it is in Appendix B removed from the main due to space constraints). We will also try to include additional intuition explaining where the factors $1.1\\tau$ and $\\tau$ come from.\n\nWe thank the reviewer for the great question. We take them in order.\n\n>The tie-breaker ERM is trained on a \"hard\" subset of data where the primary classifiers disagree or lack confidence. The analysis shows that this ERM still achieves an error close to the optimal h* on this conditional distribution. Could you provide more intuition for why a standard ERM, known to be suboptimal, performs so well on what seems to be a more difficult data distribution?\n\n\n**Answer:**  \nFirst a high-level explanation and then a more formal explanation. The ERM performance on the \"hard\" subset is actually as one would expect for ERM. However, the probability of it being asked to make a tie-break is small, thus the overall probability of the tie-breaker both being called and failing ends up being smaller than the overall probability of an ERM failing when trained just on the \"plain\" data.\n\nMore formally (omitting the $\\ln{\\left(1/\\delta \\right)}$ factor in the following sketch): The probability of either $\\hat{\\mathcal{A}}\\_{t\\_{1}}$ or $\\hat{\\mathcal{A}}\\_{t_{2}} $ failing to classify with a good margin (more than $ 11/243 $ of their voters being incorrect) is $p:= 1.1\\tau+O(\\sqrt{\\tau\\frac{d}{m}}+\\frac{d}{m})=O(\\tau+\\frac{d}{m})$, and thus the ERM deciding the tie-break $ h_{tie} $  will be trained on $ \\Theta(p m)$ samples. \n\nNow let $ E\\_{\\lnot margin}$ be the event that either  $ \\hat{\\mathcal{A}}\\_{t_{1}}$ or $ \\hat{\\mathcal{A}}\\_{t_{2}} $ fails to classify with a good margin, i.e., the case where the tie-breaker is used, so $ E_{\\lnot margin} $ has probability $ p $. Since, $ h_{tie} $ is trained on $ \\Theta(pm) $ examples from the conditional distribution $ \\mathbf{P}[\\cdot|  E_{\\lnot margin} ] $  it has error $\\mathcal{L}\\_{\\mathbf{P}[\\cdot|  E_{\\lnot margin} ]}(h_{tie})= \\inf_{h\\in\\mathcal{H}} \\mathcal{L}\\_{\\mathbf{P}[\\cdot|  E_{\\lnot margin} ]}(h)+O\\left(\\sqrt{\\frac{d}{pn}}\\right)= \\mathcal{L}\\_{\\mathbf{P}[\\cdot|  E_{\\lnot margin} ]} (h^\\*)+O\\left(\\sqrt{\\frac{d}{pn}}\\right),$ where we use that $ h^{*} $ is not a minimizer of the conditional distribution, so we can use it as an upper bound (we are here using the agnostic learning gaurantee of ERM, see for instance [1] Theorem 6.7).\n\nNow, by the law of conditional probability, we have that the probability of the event that either $ \\hat{\\mathcal{A}}\\_{t_{1}}$ or $\\hat{\\mathcal{A}}\\_{t_{2}} $ has small margin, i.e., $ E_{\\lnot margin} $ happens, and the tie-breaker ERM $ h_{tie} $ fails is \n\n$$ \n \\mathbf{P}\\_{(x,y)}[  E\\_{\\lnot margin} ,h_{tie}(x)\\not=y]\n  \\leq \\underbrace{\\mathbf{P}\\_{(x,y)}[ E\\_{\\lnot margin}]}\\_{=p}\\cdot \\underbrace{\\mathbf{P}\\_{(x,y)}[h_{tie}(x)\\not=y|E_{\\lnot margin}]}\\_{=\\mathcal{L}\\_{\\mathbf{P}[\\cdot|  E\\_{\\lnot margin} ]}(h_{tie})=\\mathcal{L}\\_{\\mathbf{P}[\\cdot|  E_{\\lnot margin} ]}(h^\\*)+O(\\sqrt{\\frac{d}{pn}})}\n$$\n\n$$\n  =p\\cdot \\left(\\mathcal{L}\\_{\\mathbf{P}[\\cdot|  E\\_{\\lnot margin} ]}(h_{tie})+ O\\left(\\sqrt{\\frac{d}{pn}}\\right)\\right)\n  =\\mathcal{L}(h^\\*)+ O\\left(\\sqrt{\\frac{pd}{n}}\\right)= \\tau+ O\\left(\\sqrt{\\frac{\\tau d}{n}}+\\frac{d}{n}\\right)\n  $$\n\n\n\nwhere the second-to-last inequality follows from $ \\mathcal{L}\\_{\\mathbf{P}[\\cdot|  E_{\\lnot margin} ]}(h^\\*)= \\frac{\\mathbf{P}\\_{(x,y)}[E_{\\lnot margin},h^\\*(x)\\not=y]}{\\mathbf{P}\\_{(x,y)}[E_{\\lnot margin}]}\\leq\\frac{\\mathbf{P}\\_{(x,y)}[h^\\*(x)\\not=y]}{\\mathbf{P}\\_{(x,y)}[E_{\\lnot margin}]}=\\frac{\\mathbf{P}\\_{(x,y)}[h^\\*(x)\\not=y]}{p} $ and the last inequality from $ p=O\\left(\\tau \\frac{d}{m}\\right) $.\n\n[1] Shalev-Shwartz, S., Ben-David, S. (2014). Understanding Machine Learning: From Theory to Algorithms.\n\n>The switch from 3 recursive calls in the initial approach (Section 3.1) to 27 calls in the improved approach (Algorithm 2) is a critical step in the analysis. Is there a deeper principle behind the number 27, or is it simply \"a number large enough for the probability math to work out\"? How sensitive is the final constant of 2.1 to this choice?\n\n**Answer 2** The choice of more than $ 3 $ recursive calls is to improve the constant coming from the event contributing  $ 15 \\tau $ in the simple analysis down to $ 2.1 \\tau $, as it enables splitting the error into two events: (1) the event where both classifiers  $ \\hat{\\mathcal{A}}\\_{t_{1}}$ and $\\hat{\\mathcal{A}}\\_{t_{2}} $ fail with a large margin, and (2) the event where one of the classifiers fails with a small margin, and the tie-breaker is called and fails. \n\nFrom this split, we have to be able to say that the probability of one of the classifiers failing with a small margin (more than $ 11/243 $ voters being incorrect) is small (that is, the probability $ p  $ in the answer to Question 1 should be of the order stated in Question 1). Without going into too much detail, this requires a more fine-grained analysis of the margin error of the recursive algorithm $ \\mathcal{A}_{t} $ -  basically we want the number of recursive calls to be such that, given an margin error of $ 11/243 $, one of the recursive calls fails with this margin and some of the voters in the remaining classifiers also fail  - which a larger number of recursive calls guarantees. \n\nThe number 27, as foreseen by the reviewer, was chosen somewhat arbitrarily (just large enough). The general trade-off for a larger number of recursive calls is that the constant in front of the error term of order $ 1.1\\tau $ in the current version of the paper becomes smaller, but at the cost of a larger constant in the $ O\\left(\\sqrt{\\tau\\frac{d}{n}}+\\frac{d}{n}\\right) $ term in the final bound. Implying that we could not just choose the number of splits arbitrarily large to get $ 1.1\\tau $ down to  $o(1) \\tau $, so we chose $ 27 $ as it allowed for a constant fairly close to $ 1 $.\n\n>The final learner uses a hold-out set to select between your proposed algorithm and the one from Hanneke et al. cite_start. This is a standard and effective method. Did you explore possibilities for a more deeply integrated \"single\" algorithm that smoothly handles all regimes of τ without explicit model selection?\n\n**Answer:** We thought a bit about this; however, we did not figure out a better approach than the hold-out set method presented in the paper."}, {"review_id": "H21pD87c6P", "reviewer": "Reviewer_XqN1", "summary": "The paper continues a line of work studying the sample complexity of PAC learning, when it is parameterized by the best achievable (test) loss in the class, thus \"interpolating\" between realizable and agnostic PAC learning.\nThe paper provides an algorithm which improves prior work in the small-yet-positive error regime, thus answering one of the questions posed by Hanneke, Larsen, and Zhivotovskiy (FOCS '24).", "questions": "- The authors mention that a feature of their algorithm is that it does not need to know $\\tau$ in advance. Is this true for prior work on this model as well? This should be clarified.\n\nSome minor comments:\n- Throughout the paper, the grammar is occasionally slightly odd (e.g, the 1st sentence ending abruptly). I suggest the authors revising the writing, and as mentioned earlier, even more so in terms of the math.\n\n- Line 64: what is $n$? Should probably be fixed to $m$.\n\n- The abstract formatting here on openreview has a bug (does not exit math mode appropriately), should be fixed.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper continues an interesting recent line of work in learning theory. The paper makes a clear contribution, though arguably slightly incremental. Nonetheless, it seems that it will be of interest to experts in the relevant related works (which I am *not* quite), and it offers some new ideas in its analysis which are likely applicable in future works on this topic. The authors also do a good job in my opinion explaining where their techniques fall short, thus helping future work possibly overcoming them and fully resolving the open problems posed by Hanneke et al..\n\nThe main drawback of this paper in my opinion is its very dense writing style, which at times makes it a bit hard to read. I recommend the authors spacing out mathematical definitions and nonstandard notation introduced throughout the analysis.\n\nOverall I find this a solid theoretical contribution, based on some new analysis, leading to a slightly incremental result. Therefore I lean towards recommending acceptance.", "was_revised": true, "final_justification": "After taking into consideration the authors' response as well as other reviewers' opinions, I maintain my score.", "rebuttal": "We thank the reviewer for carefully reading the paper and for their detailed feedback. We address their points in turn.\n\n> The authors mention that a feature of their algorithm is that it does not need to know in advance. Is this true for prior work on this model as well?\n\nWe thank the reviewer for raising this important point. Previous algorithms in the literature are indeed also oblivious to the knowledge of $\\tau$. Our intent with our original description was to clarify that our improved algorithm preserves this desirable feature, but is clear that we should have explicitly stated that many previous algorithms do so as well. We will update the next version of the paper to clarify this point. \n\n> The main drawback of this paper in my opinion is its very dense writing style, which at times makes it a bit hard to read. I recommend the authors spacing out mathematical definitions and nonstandard notation introduced throughout the analysis. ... Throughout the paper, the grammar is occasionally slightly odd (e.g, the 1st sentence ending abruptly). I suggest the authors revising the writing, and as mentioned earlier, even more so in terms of the math.\n\nWe admit that there is certainly room for improvement in the readability of the paper, as also noted by reviewers 1ZdR and e2wi. We found the paper somewhat difficult to write, including especially Section 3, owing to the technicality involved in the analysis as well as the page limit of the submission. Should the paper be accepted to the conference, we will be sure to use the additional page of the camera ready version to improve the spacing and presentation of notation throughout the paper, at the reviewer’s suggestion. We also intend to include additional intuition and motivation in Section 3, as well as to include the algorithm’s full pseudocode in the main body of the paper. (As opposed to merely in the appendix, where it has currently been deferred.) We believe these various modifications will make the section considerably less dense and more legible for the reader. We thank the reviewer for raising this important point. \n\n> Line 64: what is $n$? Should probably be fixed to $m$.\n\nCorrect, we will be sure to update this in the next version of the paper.\n\n> The abstract formatting here on openreview has a bug (does not exit math mode appropriately), should be fixed.\n\nWe thank the reviewer for bringing this to our attention. We will fix this mistake once we are permitted to update the abstract on OpenReview (unfortunately, we currently cannot)."}]

Author rebuttal:

Meta-review: This paper studies PAC learning in the agnostic case, where the error is parametrized by a quantity $\tau$ that corresponds to the error of the best hypothesis.  A recent result by Hanneke, Larsen, and Zhivotovskiy [HLZ] showed that empirical risk minimization is suboptimal for agnostic learning if we treat the performance of the best hypothesis as a parameter and moreover they proposed an algorithm that was optimal when $\tau \in \Omega(d/m)$.  This paper complements the [HLZ] result by providing an efficient learner that is optimal when $\tau \in O(d/m)$. The authors make progress on two more questions from [HLZ]. These are important results in learning theory and the paper has merit to be accepted in NeurIPS.

The authors provided good answers to the reviewers' questions and the evaluations continued to be positive.  Three of the reviewers maintained their original "Accept" rating.  Unfortunately, the fourth reviewer (Reviewer Y9zH) did not interact with the authors after their response, but on one hand the author was positive about the paper to begin with, and on the other hand the response by the authors was reasonable.

So, overall, I think the paper stands out as it makes an important and interesting contribution for agnostic learning over the traditional ERM approaches.  There was a good discussion and the authors have clarified several parts that the reviewers asked.  Therefore, I am recommending spotlight acceptance.
Decision: Accept (spotlight)