Revisiting Agnostic Boosting
Authors: Arthur da Cunha
Mikael Møller Høgsgaard
Andrea Paudice
Yuxin Sun
Venue: NeurIPS 2025 poster ()
Keywords: Weak-to-Strong Learning
Agnostic Learning
Sample Complexity
Margin-based Analysis
Boosting
Primary area: theory
TL;DR: We establish the sample complexity of agnostic boosting up to logarithmic factors by providing novel upper and lower bounds.

Abstract: Boosting is a key method in statistical learning, allowing for converting weak learners into strong ones.
While well studied in the realizable case, the statistical properties of weak-to-strong learning remain less understood in the agnostic setting, where there are no assumptions on the distribution of the labels.
In this work, we propose a new agnostic boosting algorithm with substantially improved sample complexity compared to prior works under very general assumptions.
Our approach is based on a reduction to the realizable case, followed by a margin-based filtering of high-quality hypotheses.
Furthermore, we show a nearly-matching lower bound, settling the sample complexity of agnostic boosting up to logarithmic factors.

Revisiting Agnostic Boosting
Arthur da Cunha Aarhus University dac@cs. au dk
Mikael Møller Høgsgaard Aarhus University hogsgaard@cs.. au.dk
Andrea Paudice Aarhus University apaudice@cs. auticcss.uuce au. .u.
Yuxin Sun Aarhus University yxsauêcs au dk
Abstract
Boosting is a key method in statistical learning, allowing for converting weak learners into strong ones. While well studied in the realizable case, the statistical properties of weak-to-strong learning remain less understood in the agnostic setting, where there are no assumptions on the distribution of the labels. In this work, we propose a new agnostic boosting algorithm with substantially improved sample complexity compared to prior works under very general assumptions. Our approach is based on a reduction to the realizable case, followed by a margin- filtering of high-quality hypotheses. Furthermore, we show nearly-matching lower bound, settling the sample complexity of agnostic boosting up to logarithmic factors.
Introduction
Binary classification under the Probably Approximately Correct (PAC) learning model is perhaps the most fundamental paradigm of statistical learning theory.
In the realizable version of the problem, we consider an input space X, a known hypothe- sis class F S {=1]*, an unknown target classifier f F, and training sequence S (x1,)(x (xm; (x)m)) E (X' x {+1))² of independent samples drawn from unknown but fixed distribution D and each labeled according to f. The objective is to ensure that, for any desired accuracy and confidence parameters, 8 >> 0, the algorithm can, with probability least 1- 6, learn from training sequence of size m(e, 8) and find a classifier h with an expected error, Px>D(h(x) [x)), less than A learning algorithm achieving such is called strong learner and the amount of training data m(e, 8) necessary to reach this goal is called its sample complexity.
It is known that in the realizable setting the Empirical Risk Minimization procedure (ERM) of choosing any hypothesis E minimizing the empirical loss E(,.y)es [h(xx) # y). which in the realizable case, yields a strong learner-as as long as F has bounded VC dimension.
An interesting question posed by Kearns and Valiant is whether it is possible to obtain strong learner starting from humbler requirements [Kearns, 1988, Kearns and Valiant, 1989]. Namely, the authors consider y-weak learners that are only guaranteed to produce classifiers from a base class H with error lower than 1/2 - y for some 7 > 0. More precisely, for any distribution Q over X,, the weak leamnrr produces, with probability at least - óg, hypothesis such that
(I) thus having " advantage over random guessing. Answering whether such simple learners could be boosted to achieve arbitrarily good generalization led to intense research and, eventually, to many such weak-to-strong learning algorithms, including the celebrated ADABOOST [Freund and Schapire, 1997].
Px~e[w(x) + [x)] < 1/2-7,
Realizability can, however, be too strong of hypothesis. To capture broader scenario, we consider the agnostic learning model [Haussler, 1992, Kearns et al., 1994], where the samples are generated by an arbitrary distribution D over X x y. Thus, obtaining learner with arbitrarily small error errp (h) == ((xx))>/(/(x) + y]
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

in this setting is not always possible. Accordingly, the goal of the learner is to find classifier h with error close to that of the best classifier in a reference class J. Formally, in the agnostic setting, we say that learning algorithm is strong learner if, for any e, 5 > 0, given m(e, 6) examples from D, with probability least 1 the learner outputs classifier such that erro S inf ser errp (f) e. Hereon, we assume without loss of generality that the infimum error is achieved by some f E F. It is worth noting that ERM is still a strong learner in this setting.
A natural question, first posed by Ben-David et al. [2001], is whether it is possible to boost the performance of weak learners in the agnostic setting. To formalize this question, useful to measure the performance of hypotheses in terms of correlation under the data distribution:
coTrD (h) == B(x.))-Dly h(x)]-
Notice that for binary hypothesis h. corrp(h) equivalent to minimizing the error. With that, we have the following definition.
errp (h) so maximizing the correlation is
Definition 1.1 (Agnostic Weak Learner). Let 7.5u. do E [0. 1], mo E N. ( and H S [-1, learning algorithm W: (X' x {=1))) + H is an agnostic weak learner with advantage parameters 7 and Ep. failure probability dp. sample complexity mo, reference hypothesis class F and base hypothesis class H iff: for any distribution D over X x {=1}, given sample
S ~ Dmno with probability at least 1 - do over S the hypothesis w W(S) satisfies that
(orT 2 7 sup corrD(f) Eo.
feF
For short, we call such algorithm Co, 8p, ma, F, H) agnostic weak learner, and we may omit some those parameters when the context allows for no ambiguity.
At the cost of some verbosity, the definition above is quite general. Indeed, it encompasses the original definition from Ben-David et al. [2001], and, from it, one can readily recover the usual definition of weak learner.' The generality of Definition 1.1 aims to capture as much as possible of the diverse set of alternatives proposed in the literature, thus allowing for a fairer comparison with previous works, as discussed in Section 1.1. Despite the broad definition, we obtain the following lower bound on the sample complexity of learning under the agnostic model stemming from Definition 1.1.
Theorem 1.2. There exist universal constants C1, C2. C3, C4 > O for which the following (0, 1), any ",
holds. Given any mg [C2d In( ( In( In(,+))] there exist domain X, reference class F {+1]*² and base
(0, 1), and any integer d 2 C1 (n(///²)) for
class H. C [+1}* with VC(H) S d, such that there exists a (7, S0, 8n, mo. F,H) agnostic weak learner and, yet, the following also holds. For any learning algorithm A: (X' {=1})* - {+1}*
there exists a distribution 'D over X x {+1} such that corrp(f*) L and for sample size
m 2 C3 O3 LE we have that
d
EgaDm (corr corrp(f") 1-o--l-cc (cll-corrl(f") corrd(f-)) (x- - (m-
We know from classic results that agnostically learning relative to reference class with VC dimension d implies an excess error of (dvdm)). Accordingly, the basic idea behind the bound above is to construct a base class H with VC(H) < that is sufficient to agnostically weak learn a reference class F with VC dimension of at least d//² so that learning relative to F would incur an excess error of S(( /d/(22m)) However, with our construction we were only able to show that VC(F) 2 d In(1/>)). leading the extra logarithmic factor in the bound. Our argument draws inspiration from Alon et al. [2023] and is deferred to Appendix E, which also contains versions the theorem with different trade-offss.
We show that the bound from Theorem 1.2 nearly tight by providing an algorithm that matches up to logarithmic factors. The following summarizes the statistical properties of the method.
'To recover the definition of Ben-David et al. [2001]. it suffices to restrict definition Definition 1.1 to the case 7 1 and H. being binary class. If. instead, D realized by some E F, so that sup corrp(s) 1, use that corrp(h) = 1 2 errp (l) to obtain (2=éa) ) weak learner, as in Eq. (1).

---

Theorem 1.3. There exist universal constants C. > 0 and learning algorithm A such that the following holds. Let W be (Y, op, ma F, H.) agnostic weak learner If > En and 80 1, then, for all ā E (0,1) m E N, and distribution 'D over X x {+1}, given training sequence S ~ 'D we have that A given (S, W, 6, ga, mo), with probability at least - over S and the internal randomness of the algorithm, returns v satisfying that
corTD (oir(siignv)) (v) 2 corrp(s*) - VC( - corr C.
In Imm with Lu(x) = In(max{2, e}) and = (( (H) being the fat-shattering" dimension Hf H at level c(ty 5o).
where B (7- Ln [m-
+
The bound above improves on previous results by a polynomial factor, as detailed Section 1.I. The theorem incorporates the fact that Definition 1.1 allows for non-binary weak hypotheses, expressing the bounds in terms of the tat-shattering dimension of H. which reduces to VC(H) in the binary case. Moreover, the bound in Theorem 1.3 desirably interpolates between the agnostic, corrp(f*) < 1, and the realizable, cO = 1, settings. Lastly, since random guessing leads to correlation 0, the theorem above establishes that any non-trivial weak learner (with Eg ?) can be boosted to a strong learner in the agnostic setting. As discussed in Section 1.1, previous results were not sufficient to ensure this general fact.
We highlight that the method underlying Theorem 1.3 attains the performance ensured by the theorem under remarkably mild assumptions. In addition to leveraging fairly general weak learner (see Definition I.1), the method does not require direct access to the reference class F or the base class H. relying only the weak hypotheses returned by W. The technique also does not require knowledge of the advantage parameters y and Eo, thus preserving the characteristic adaptability of boosting.
As detailed in Section 3, while nearly optimal in terms of sample complexity, the algorithm proposed not computationally efficient. Hence, on this regard, it is comparable to ERM which can be shown to be a strong agnostic learner with near-optimal sample complexity 2014] (albeit, demanding direct access to the reference class F and a way to bound its VC dimension). However, while ERM is bound to be inefficient even for simple classes (unless P NP) [Bartlett and Ben-David, 1999, Ben-David et al., 2000], boosting can, in principle, attain optimal sample complexity within manageable computational cost. By showing that agnostic weak-to-strong learning is possible with nearly optimal sample complexity under minimal assumptions, we take a step towards agnostic boosting algorithms that are both computationally and statistically efficient.
Shhlar-SSwartz and Ben-David,
1.1 Related Works
The work that is closest to ours is the recent contribution by Ghai and Singh [2024]. Notably, employs definition of agnostic weak learner very close to Definition 1.1. The authors devise method requiring ((VC(H))({??))) samples to produce classifier satisfying
250
cvrrp(v) 2 corrp(f")
7
with high probability. Crucially, for their algorithm yield a strong learner, the advantage parameters (7 and éo) must satisfy that en = O(e7). In contrast, Theorem 1.3 shows that as long as 7 > én, that is, for any non-trivial weak learner, it is possible to achieve weak-to-strong learning in the agnostic setting. Under the further mild assumption that 7 2 so/2 we obtain a sample complexity of order Ö(1 corrD d/(s²>?) + d/(e>²), improving on Ghai and Singh [2024] by a polynomial factor, Also, Theorem 1.3 provides bound in terms of the fat-shattering dimension of the base class H. which reduces to the VC dimension when only considering binary classifiers while also allowing more general hypothesis classes.
A body of agnostic boosting literature diverges from the original definition of weak learner from Ben-David et al. [2001]. Most notably, the works Kalai and Kanade [2009], Brukhim et al. [2020], Feldman [2010] propose agnostic boosting methods based on the re-labeling of examples rather than
We recall the definition of the fat-shattering dimension and other notations in Section 2. 'Concurrent work by the same authors shows that with ((CC(H)/("">))) labelled and ((VC(H))(6*+')) unlabelled samples one achieve the bound in Eq. (2). See Ghai and Singh [2025].
3

---

re-weighting, as in traditional boosting and in the method we present here. While those works all introduce different definitions of weak learner, the re-labeling strategy allows those definitions to only require that all distributions have the same marginal over X' as the data distribution 'D. Except for this aspect, we tried to make our definition as general as possible, also to better encompass the alternatives. In the following, we strive to compare our results while accounting for the different definitions used by others. We compile and further discuss the multiple definitions of agnostic weak leamners in Appendix A.
Another recent work, by Brukhim et al. [2020]. proposes, under a different empirical weak learning assumption (cf. Appendix A), an algorithm that after T rounds of boosting produces a classifier with expected empirical correlation satisfying that
m
E vnf((a)) m
m
-
Eo + +o (3
(117
2 sup fEF
m
where Eu plays a similar role as in Definition 1.1. While this is a bound on the empirical performance of the classifier, the authors argue that one can obtain generalization bound up an term with sample complexity of m O(Tmo//E"), where mo is the sample complexity of their weak learner, usually assumed to be e (1/e Overall, this yield be a strong learner one would have to set T = )()((=)))) and assume that so @ implying a sample complexity of m ((L/(=">*))
O(T/ ((TT((e=))) Now, for their algorithm to
The work of Feldman [2010] is the hardest to compare to ours the authors employ definition not encompassed by Definition 1.1. Under a definition parameterized by a and y, they propose a learning algorithm yielding classifier such that
errp(v) inf err + 2a s.. fEF
Our understanding is that the associated sample complexity is of order O(1/7² + 1/E"), where Y S a. As in the previous cases, obtain a strong learning guarantee one has constrain the weak learner non-trivially. For Feldman [2010], the authors require that a = (E)). Moreover, the sample complexity of their proposed method (11/Et) regardless of the weak learning guarantee. In contrast, Theorem 1.3 does not require that 7 S E, so when the advantage theorem ensures a sample complexity of order (dd/=²).
Eo is constant, the
Nonetheless, stress that Ghai and Singh [2024], Brukhim et al. [2020], Feldman [2010]. Kalai and Kanade [2009] propose computationally efficient algorithms, bringing insights both to the computational and statistical aspects of agnostic boosting, while we only consider the latter.
Besides the works mentioned above, the literature on agnostic boosting includes several other with some of the most related to ours being Gavinsky [2003], Kalai and Servedio [2005], Kalai al. [2008], Long and Servedio [2008], Chen et al. [2016].
Additional Notations
We let Ln: IR + [1, oc) be the truncated logarithm, given by x + In(max et). Given a set A, we let A" = U A be the set of all finite sequences of elements of A. The notation A ((A) stands for the set of all probability distributions over A. For a distribution D A(A) and a integer 2 1, we let Dm be the distribution over A obtained by taking m independent samples from D. Given real-valued functions f, and 3 E IR, we denote by of By the mapping a. af(()) (B((z). We represent the set convex combinations of at most T functions from a family F as conv" (F). That is,
conv T(F)
aafi : as (0,1E, (E(T]
Σ
Σ a4 -1 1E(T]
For the entire convex hull, we write conv(F) = U conv' We let sign(x) = 1(x 2 0} 1 f(x < 0} and sfgn(f) denote the mapping + (f Notably, (0) = 1.
For classifier h: X' >> {+1} and a distribution D over X x {+1}, we define D, as the distribution over X' x {=1} such that P(xy))-D,- [A] P(x,y)<D [x. (x)) E A] for all measurable sets
A C X x {11). That is, D, has the same distribution D over X but with the labels given by f.

---

Given an input space X. which for simplicity we always assume to be countable, let D E A x R). For any À 2 0 we let the X-margin loss of a hypothesis g: X + R with respect D be given by
L (g) P(xxy)~Dly 9 x) S A]
with the shorthand Cg(g) == (g) Despite the generality of this definition, we reserve the notation errp(-) ) for the error of binary classifiers.
Given function class H C R and a: > 0 we define the fat-shattering dimension of H. at level a as the largest natural number
fat, (H) such that there exist points T .Td E X' and level sets TI.....77 Td E R satisfying the following: For all E {=1] there exists hG H such that for all e [d] it holds that hu(4;) 2 r; + a if 6, 1; and hz( T; a if b; -1. In words, whenever = fat, (P() there exist a set of points and a set of levels, each of size d, such that the hypotheses in H. can oscillate around those with margin a.
Finally, we adopt the convention that arg min and analogous functions resolve ties arbitrarily so to return a single element even when multiple ones realize the extremum under consideration. Also, whenever we write a set or sequence in place of a distribution, we mean the uniform distribution over that set or sequence. As an example, e refers to the empirical error of hypotheses on the sequence S. As the reader may have noticed, we use boldface letters to denote random variables.
3 Our argument
In this section, we overview the arguments underlying the proof of Theorem 1.3 and the associated method, Algorithm 2. The detailed proof's are deferred to the appendices.
We start, however, with a brief overview of the proof of Theorem 1.2. We know from classic results that agnostically learning relative to a reference class with VC dimension implies an excess error of Ω Φ( \d)m/ Accordingly, the basic idea behind the Theorem 1.2 is to construct a hase class H with VC(H) that is sufficient to agnostically weak learn reference class F with VC dimension of at least d//² so that learning relative to would incur an excess error of 2 ( However, with our construction we were only able show that VC(F) d/(-2 In(1 /7y)), leading the extra logarithmic factor in the bound. Our argument draws inspiration from Alon et al. [2023] and is deferred Appendix E, which also contains versions of the theorem with different trade-offs.
We now turn our attention to Theorem 1.3.
As we shall see, the difference between the advantage parameters and Eg from Definition 1.1 plays a role similar to that of the advantage in the realizable setting. Throughout this section, we let 0 == 7 Eo to both highlight this analogy and simplify the notation.
The argument is based on the abstract framework proposed in the seminal work Hopkins et al. [2024] to derive agnostic learning al algorithms from their realizable counterparts. Their framework can be summarized into two steps:
1. Run the realizable learner on all possible re-labelings of the training set;
2. Among the hypotheses generated in the first step, return the one with the lowest empirical error on a validation dataset.
Some notes about this framework are in order. First, notice that the first step already requires exponential time, thus Hopkins et al. [2024] focuses only on statistical and information theoretic aspects of the problem, forgoing computational considerations, and so does our work. Second, while the framework above is quite abstract and, thus, suites many settings, obtaining concrete results from it usually requires some extensions and adaptations, as illustrated by many of the results in Hopkins et al. [2024]. This note is especially pertinent when aiming for (near) optimal bounds, which the case for our work, and we will detail the adaptations we made to the framework later in the text.
Our proposed method can be decomposed into three steps. Our argument mirrors this separation, being organized as follows:
We first show how to reduce the problem to the realizable boosting setting, which allows us to apply more standard techniques. We leverage those to show that enumeration can produce
5

---

exponentially large set of hypotheses containing, with high probability, a classifier with good generalization guarantees.
Then, we filter those hypotheses to obtain a new set with much smaller size (logarithmic), while preserving least one good hypothesis with high probability.
In the final step, we identify the good classifier via a standard validation procedure over the set of hypotheses obtained in the previous step.
3.1 Reduction to the realizable setting
Consider a training sequence S = ((x1, Ym)) ~ Dm and, given f E F, let S ((x1, (( (xx)),..... (Xm: (xm))) ))) be the re-labeling of S according to f. Notice that for any f E F we have that SE cf)
for any 2 E A(S)). Hence, an agnostic weak learner W as in 60 over a training sequence S' ~ -"o, output a hypothesis with correlation least 7 so under the given distribution. As this is equivalent to having a (realizable) weak learner with advantage 0/2, standard realizable boosting methods can produce, with high probability, a voting classifier that approximates f well-relative the data distribution D.
Definition 1.1 will, with probability at least
Accordingly, we begin by providing a variation of ADABOOST adapted to our settings (see Al- gorithm 1). It starts with confidence amplification step to ensure that the weak learner outputs hypotheses with sufficient correlation with probability of at least 1 - 8/T rather than the 6, ensured by Definition 1.1. Then, the algorithm performs boosting step based correlations to accommodate for weak hypotheses with the continuous range [-1, instead of the usual (=1).
Input :Triining sequence S ((z1,))), (I'm 8m Bm)). weak learner W and its sample complexity mi, number of iterations T, confidence parameters 6, do (0,1) 1)
D1 (1 1.....
for / < 1 to do // Confidence amplification
1: +- 1-
8 In 8
4 for 8 1 to do
Sample S according to D h + (((
// mo i.i.d. samples from D.
h, < arg max (e (CorTD,(h) (h))
// Correlation based boosting step + corTD, (he)
a 1 In l+oz for + 1 to do (i) t De(1) (x((ar
1-c,
10
11
12
Z. + E (1)
13
D411 +
14
return Voting classifier
Σx Er aah
Algorithm 1: Modified ADABOOST
As usual for classic boosting methods, we provide margin-based based argument for the generalization properties of the classifier output by Algorithm 1. Suitably, our first lemma ensures that the algorithm outputs hypothesis with large margins on the input training sequence.
Lemma 3.1 (Realizable Learning Gaurantee of Algorithm 1). Letry, ,6 E (0, 1). and given m. my
N. let S E (X x {+1))m² mm If a learning algorithm W: (X x {+1})* - 7 1- is such that for any E A(S) with probability at least 1 da
sample S' Q the hypothesis
h= h=W(S') satisfies co 2 7. then, for T 2 [32 In(em)/n/2) running Algorithu on input conv (H) such that with probability least 1
(S,W: mo, T,6, 8,,,8n) yields voling classifier
over the random draws from Line 5 it holds that yv(x) > 7' /8 all (x. y) E S.
The proof of Lemma 3.1 based on the standard analysis of ADABOOST (e.g., Schapire and Freund [2012]) and is deferred to the appendix.

---

As we discussed, for re- re-labeli of the training sequence according to function f in the reference class F. (7)50) agnostic weak learner with F as reference class behaves like the weak learner in Lemma 3.1 with 7 corrp(f*) SE corrD (f), with being the true data distribution. So, we will regard f as our target function since approximating it concludes the proof of Theorem 1.3. As we lack direct access to f*, the first step of our proposed method (Algorithm 2) is to run Algorithm on all possible re-labelings of S₁ and accumulate the obtained hypotheses in bag, B1 (cf. for loop starting at Line 3). Let V, be the hypothesis obtained when running Algorithm on the re-labeling Sy.. The subsequent steps of Algorithm 2 are designed to find v within 11.
Eo =: O. We are interested in the re-labeling Syr, where f" is such that
Input Training sequence S E (A's x {+1}) (with m multiple of 3),, weak learner W,, confidence parameters do, 8 E (0, 1)
B1 4,0, 00, B2 +
2 Let S2. and 53 be the first, second, and third thirds of S. respectively
// Reduce to realizable case foreach )/ E [=1]mm/3 do
S' - ((S)]z);, 34 m/3
// Re-label Si with y
1=1
T - [32m In(em)
// Number of rounds
f ALGORITHMI(!!
5,8/10, 6o)
B1 + B1 [(v
// Filter out good hypotheses without knowledge of Y
8 foreach 7' E 1/41 1/2[log, v vml) do
V arg min vEB, (C3, (v)}
// Minimizer of the 7'margin loss
10
B2 B2 (
// Return hypothesis with the lowest validation error
11 return v arg min veB, (Ls, (v)}
Algorithm 2: Agnostic boosting algorithm
Leveraging Lemma 3.1, we have that with probability at least - 6/10 over the randomness used in Algorithm 1, there exists Vg B3 such that
S (Vg) = O.
That is, Vg has zero empirical 0/8-margin loss on St,5*, which is the re-labeling of S₁ according to f* In the following lemma, we convert this into bound on the population loss of Vg.
Lemma 3.2. There exist universal constants C" > 1 and è > 0 for which the following holds. For all margin levels O ST < I 1, hypothesis class H 1-1, 1]x, and distribution D e A(X {+1]).
it holds with probability at least 1 - 8 over S ~ D that for all conv(H)
(b( < 23 (v) C² (z(())
(V
B
3
m
where B = (7'-))² 3/2 (
) + In with d = fata()'=>)(H
The proof of Lemma 3.2 is based on techniques similar to those used in Høgsgaard and Larsen [2025], and it is deferred Appendix C. The argument requires controlling the complexity of conv(H)) Specifically, we show for > 0 that fat,, (conv(?() = (fattea (TTaattaaHH//aa (H)/a²) 2 for some universal constant
> O. Our strategy to achieve that builds Larsen and Ritzert [2022, Lemma 9]. We believe this result could be of independent interest.
Applying Lemma 3.2 with 0/16, >' = 0/8 and any distribution Q, we have that with probability at least 1 - 5/10 over S' ~ Q. it holds simultaneously for all v E conv(H) that
/ c2. (v) + +5(1 c%)
d
m0a
m0=
WWe assume that is multiple of 3 merely for simplicity.
7

---

with d = fatzo/1o (H). Now consider the distribution Dy. associated with Sy,, i.e, obtained by re-labeling samples from D according to f*. Setting Q = D.. S" = f1 and using a union bound have the event associated with Eq. (3) also hold, we obtain that with probability at least 1 26/10 10 over S and the randomness used in Algorithm 1, there exists Vy E B such that
=Ō ( d D. ( (vg)
9/16
m88
(4)
Still, Eq. (4) bounds the loss of v, relative to distribution Dy. while interested in the loss on the data distribution D. We convert between these by noticing that given (x, y) E X x {=1}, if y (2( < 0/16, then either (x) + y. that (x) y S 0/16; or (x) y, so that
I (x) g (z) S 0/16. Thus,
D; (S*) + C ( (v₂) = err Ö( d
(mo)
(5)
where the last equality follows from Eq. (4) which holds with probability at least 1 26/10.
3.2 Filtering the hypotheses
For this step, we use the second independent portion of the training data, S2 ~ Dm/3, We saw that with high probability B, contains good hypothesis Vg. so our goal is to distinguish Vg-or or some hypothesis at least as good-from the other hypotheses in B1. A naive way to do so would be to use S2 as validation set, leveraging its independency. To succeed, we would need ensure that all hypotheses in B, have generalization error close to their error S2. Alas, since |B 2m/3 union bound over the entire bag would lead to an extra term of order ((m(2TT (8) /0)/m/ = (1) in the final bound, making vacuous. Thus, to proceed we must first reduce the size of B while keeping at least one good hypothesis.
Given Eq. (5), know that B2 contains, with high probability, a hypothesis with relatively low generalization loss relative to margin 8/16. However, crucially, we do not assume knowledge of y Eo. and, thus, of / 7 Eo- We overcome this by considering range of possible values for the margin and storing the minimizer of the empirical loss relative to each value. More precisely, we consider each 7 (1, 1/4.,/.... 1/ 1/vm /m) where we can dismiss smaller margin values since the upper bound Theorem 1.3 becomes vacuous greater than 1 I-for 7 Eo < <1//m. Then, in the
for loop starting Line 8 of Algorithm 2, we let
B2 = { arg min C3 (v) : 7 E (1,1/2,1/4, 1/2 Dog2 vml }}. vEB
so that [Ba] = (l) and for some 2 E (0/32, we have vgg = arg min veB, (32(v) E Ba.
From here, we follow chain of inequalities between different losses. We start by applying Lemma 3.2 once more, this time with sample S2 and margin levels y = and y = 7/g. We obtain that, with probability at least 1 - 5/10 over S2 it holds for v'g in particular, that
(v()) +0 ( (VCS.vv) (r))
d' + (r))2m
d'
ColV')) = cb(V)) L3,
(6)
where = fater, (H). Recalling that v' is the minimizer of Cy.y over B, and that v, belongs to B1, we must, then, have that LT,, (v') (3g Now leverage that y E (0/32, 0/ 1666 on the one hand, 7/1 0/32 so, as the fat-shattering dimension is decreasing in its level parameter, d' fateng (H) < fal /32 H)) =: d: on the other hand, 7/ < 0/16, thus C² (v.)) < <32 (v,)) Finally, we use standard concentration bound (Lemma D.1) to ensure that, with probability at least 1 5/10
over Sg, it holds that /3/1 thus, by the chain of inequalities above, that
/ (vg) + Ö(V C ( In(1/8)mm + ln(1/)mmm) and
0/16 (V¹) 2/ (v.) +
co (
In g
1 1 In
8

---

Combining Equations 5, 6 and 7, and taking union bound over the respective events required to hold simultaneously, the appropriate calculations yield the following lemma, which summarizes the progress made so far.
Lemma 3.3. There exist universal constants C 2 1 and è >> foror which the following holds. After the for loop starting Line 8 of Algorithm it holds that [B2] S logz m and with probability at least 1 - 8/2 over S S2 and randommess used in Algorithm I that B3 contains a voting classifier such that
CD(v) errp( VCerrp C.
where B
d_ 8m
Ln3/2
Ln 3/2
+
In
10 o
with d = (Hta)/32(H).
3.3 Extracting the final classifier
For the final step, we use the third and last independent portion of the training data, S3 Dmm/3, as validation set. We saw previously that naïvely using a validation set to extract good hypothesis from B, would not work due the exponential size of B,, In the previous step, we overcame this limitation by reducing the number of hypotheses to (IIn while, with high probability, preserving a hypothesis with good generalization properties. Therefore, we can now use S3 to select the best hypothesis from B2.
Given e B2, we can use standard concentration results (Lemmaa D.1) to bound the probability that the empirical loss of v on S3 is close to its true loss (D))). By the union bound, with probability at least 1 8/2 over S3,
Co(1) = (v)( + (v)
(0) +0({+
L5g (v)
-nn
13
1
[3
171
m
and
(s)(v)= = (D(u) + 0(V CD(U) m
13
B3
In
m
8
for all v E B2, simultaneously. Finally, under the event associated with Lemma 3.3, B₂ contains a hypothesis v' with low generalization error. Leveraging this and the equalities above, we can bound the generalization error of arg min BEB, Ls, (t), which the final classifier output by Algorithm
The complete argument proves our main result, stated here in terms of errors rather than correlations.
Theorem 3.4. There exist universal constants C, c > O such that the following holds. Let W be Ca, 5p. ma, F, H) agnostic weak learner. If
and E A(X x {+1]), given training sequence and dp < 1, then, for all 8 E (0. 1), E N, D we have that Algorithm on inputs (S, W. 6, do mo) returns, with probability at least - 8 over S and the internal randomness of the algorithm, the output of Algorithm satisfies that
C where 3 (7-20) 3/2 (x= + In Inm with d fate((--e))/2(2))
Co(v) S eIrD(f") + (CerrD(f))
To recover Theorem 1.3, the bound terms correlation, we use that LD(v) 2 erro(sign(v)), since 00) 1, and for the binary hypotheses, f and sign(v) we have that errp (sign(())) (1 (o)r(sig())))) and efr (1 c)rr(f"))/2.
Conclusion and Future Work
In this work, we provided a novel algorithm for agnostic weak-to- weak-to-strong learning and proved that it achieves nearly optimal sample complexity under fairly general assumptions. Notoriously, while previous works set varying conditions on the relationships between parameters, Theorem 1.3 recovers the iconic generality of classic boosting by allowing for any non-trivial setting. Furthermore, our algorithm bound incorporates the error of the best hypotheses the reference class, interpolating between the agnostic boosting setting and the realizable boosting setting, which, to the best of

---

our knowledge, is not the case for any previous bounds. This also implies an even better sample complexity when cfrr(f") is large.
As for future work directions, providing efficient algorithms with sample complexity close to the error rates of Theorem 1.2 is the most natural next step. Besides that, we conjecture that the logarithmic factors in our bounds could be removed, as in the realizable case (c.g., Larsen and Ritzert [2022]). Finally, given the line of works stemming from Kalai and Kanade [2009], it also pressing to further improve the sample complexity of agnostic boosting algorithms based on sample re-labelings.
Acknowledgments and Disclosure of Funding
While this work was carried out, Arthur da Cunha, Mikael Møller Høgsgaard, and Yuxin Sun were supported by the European Union (ERC, TUCLA, 101 125203). 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. Arthur Cunha and Mikael Møller Høgsgaard were also supported by Independent Research Fund Denmark (DFF) Sapere Aude Research Leader grant No. 9064-0066BB.
Andrea Paudice is supported by Novo Nordisk Fonden Start Package Grant No. NNF240C0094365
(Actionable Performance Guarantces in Machine Learning).
References
Michael Kearns. Learning boolean formulae or finite automata is as hard as factoring. Technical Report TR- 14-14-88 Harvard University Aikem Computation Laboratory, 1988.
Michael J. Kearns and Leslie G. Valiant. Cryptographic limitations learning boolean formulae and finite automata. In David S. Johnson, editor, Proceedings of the 21st Anmual ACM Symposium on Theory of Computing. May 14-17. 17. 1989, Seattle, Washington, USA. pages 433-444, ACM, 1989. doi: 10.1 00.1145/7307773000 73049. URL /ttttps://ooi.org//////aa 1145/73007 .70499.
/
Yoav Freund and Robert E. Schapire. decision-theooretic generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci., 55(1):119-1))) 1199 1997. doi: D0.1006/JCSS.1997.10
URL https: / doi. org/ 1006 jcss. -
David Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Inf. Comput., 100(1):78- 150, 1992. doi: 12.1016/0890-5401222900000 org/10 /ttp///.001///0000-66110 0000:/000000540112229900000-0000
URL
Michael J. Keams, Robert E. Schapire, and Linda Sellie. Toward efficient agnostic learning. Mach. Learn., 15---1) 1994. doi: 10.1007/BF00993446. URL https://doi. http:///oo.oog/1..1111/ otg/10.1001 BF00993468.
Shai Ben-David, Philip M. Long, and Yishay Mansour. Agnostic boosting. In David P. Helmbold and Robert C. Williamson, editors, Computational Learning Theory, 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Amsterdam, The Netherlands, July 16-19, 2001, Proceedings, volume 2111 of Lecture Notes in Computer Science, pages 507-516. Springer, 2001. doi: 10.1007/ 3400-45444444--11111
3-540-44581-11 33. URL https: /doi. org/ 10
Noga Alon, Alon Gonen, Elad Hazan, and Shay Moran. Boosting simple learners. TheoretiCS, 2, 2023. doi:
233.8 URL http::tt////ee //ooi org/10 (e228//theoretee 23.8.
Shai Shalev-Shwartz and Shai Ben-David. ing From Theory to Algorithms.
Understanding Machine Learn- Cambridge University Press, 2014.
ISBN 978-1-10-705713-5.
URL http://www. cambridge org/de/ hetg/d/accan //a.d/mmc///m/////////////////// wwchinimmciieeeee mac.iinee--eeeingg
sub
dntersstaninngmmccinnet
Peter L. Bartlett and Shai Ben-David. Hardness results for neural network approximation problems. In Paul Fischer and Hans Ulrich Simon, editors, Computational Learning Theory, 4th European Con- ference, EuroCOLT '99, Nordkirchen, Germany, March 29-31, 1999, Proceedings, volume 1572 of
10

---

Lecture Notes in Computer Science, pages 50-62. Springer, 1999. doi: 10.1007/3-340-4499922200 URL https: pttps://doi.. org/10 1000000--000909977711
Shai Ben-David Nadav Eiron, and Philipp M. Long. On the difficulty of approximately maximizing agreements. In Nicolò Scsa-Bianchi and Sally A. Goldman, editors, Proceedings of the Thirteenth Annual Conference Computational Learning Theory (COLT 2000). June 28 July 1, 2000, Palo Alto, California, USA, pages 266-274. Morgan Kaufmann, 2000.
Udaya Ghai and Karan Singh. Sample-efficient agnostic boosting. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Udaya Ghai and Karan Singh. Sample-optimal agnostic boosting with unlabeled data, 2025. URL
https://arxie www.aiiww....aa.....o wrggabs///033 04706.
Adam Kalai and Varun Kanade. Potential-basee agnostic boosting, In Yoshua Bengio, Dale Schuur- mans, John D. Lafferty, Christopher K. I. Williams, and Aron Culotta, editors, Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of meeting held 7-10 December 2009, Vancouver, British Columbia, Canada, pages 880-888. Curran Associates, Inc., 2009, URL http:: http:::///occeeedinggggg////// wew.eeediiiiinnnninn..e.e neurips. html.
2209/
Nataly Brukhim, Xinyi Chen, Elad Hazan, and Shay Moran. Online agnostic boosting via re- gret minimization. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tices Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, Decem- ber 6-12, 2020, virtual, 2020. URL https: http://eeednn...eneeee.e.eeeeee. neurips..rip...o htt.ccccppppppe paperr20200hashl 071 11116affccoofff88aa1111377 0tt.://7788d1111777777225555555 Absttaccbbrr........... html.
Vitaly Feldman. Distribution-specific agnostic boosting. Andrew Chi-Chih Yao, editor, Innova- tions in Computer Science ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings, pages 241-250. Tsinghua University Press, 2010. URLhttp://conferenee iiis. tsinghua. edu. cn/ /ttp/IC220/////// http//////////////////aa wwtttnt/pppprs/////// htmml....
Dmitry Gavinsky. Optimally-smootth adaptive boosting and application to agnostic learning. Journal of Machine Learning Research, 4(May):101-117, 2003.
Adam Tauman Kalai and Rocco A. Servedio. Boosting in the presence of noise. J. Comput. Syst. Sci., 71(3):266-290 2005. doi: 10. 10.10166.JCSS..004.. jcs8.2004.0
URL. https: //dt:p:://ddiii org/10. 10166/
2004. .1.005....
Adam Tauman Kalai, Yishay Mansour, and Elad Verbin. agnostic boosting and parity learning. In Cynthia Dwork, editor, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 629-638. ACM, 2008. doi: 10.1145/
1374376.1374461 URL https://doi. org/ 1145/1374376 1374466.
Phil Long and Rocco Servedio. Adaptive martingale boosting. Advances in Neural Information Processing Systems, 21, 2008
Shang-Tss Tse Chen, Maria- FlorinFlorina Balcan, and Duen Horng Chau. Communication efficient distributed agnostic boosting. Artificial Intelligence and Statistics, pages 1397-1307 PMLR, 2016.
Max Hopkins, Daniel M. Kane, Shachar Lovett, and Gaurav Mahajan. Realizable learning is all you need. TheoretiCS, 3, 2024. doi: 10.46298/THEORETICS..I 24.2. URL https://doi org/10. 46298/theoretico. 24.2.
Robert E. Schapire and Yoav Freund. Boosting: Foundations and Algorithms. The MIT Press, 05 2012, ISBN 9780262301183. doi: 10.7551/mitpress/8911 1.00120001000011...1111111111111 URL https://doi org/ 10. 71551/mmtpress//8211.1.. 001. 201.0001.
Mikael Møller Høgsgaard and Kasper Green Larsen. Improved margin generalization bounds for voting classifiers, 2025. URL https: //tpxv/./vvv///////////////aaavl wwariii.or//aae. arg/abss/555 16462.
11

---

Kasper Green Larsen and Martin Ritzert. Optimal weak to strong learning. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Ad- vances in Neural Information Processing Systems 35: Annual Conference on Neural Infor- mation Processing Systems 2022, NeurlPS 2022, New Orleans, IA, USA, November 28 De- (aaper/2022/haaae Abstract Conference. html.
cember 9, 2022, 2022. URL http: /ttp::/ppapere /wtp//appppeeeeeee/eee nips. cc/ ptpppppperr_ia (3655cdaaee975554111122222222220
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963. ISSN 01621459, 1537274X. URL
http:// http:://wwwww /ttp:///wwwsjtorrr..oo org htgg/saaaeee22229955
Mark Rudelson and Roman Vershynin. Combinatorics of random processes and sections of convex bodies, Annals of Mathematics, 164:603-648, 2006. URL https: ttttpp::/api..smantiic.. semanticscholarr
org/CorpusID 13249751.
Patrick Reheschini. Lecture Notes in Algorithmic Foundations of Learning: Covering Numbers Bounds for Rademacher Complexity. Chaining, December 2021. URL https://www www.stttt..... oz. re..uk//rbbescchi www.reeeessetteeeeeeeeeeeeeeeeee /ttecceeaccnnggeeeeeeeeeeee AF www.///////aeriiraee/eee /t////tteral/eettreeeeeee Department of Statistics, University of Oxford. Version of December 8, 2021.
ac
pdf. Lecture 5 (Chaining),
Luc Devroye, László Györfi, and Gábor Lugosi. A Probubilistic Theory of Puttern Recognition, vol- ume 31 of Stochastic Modelling and Applied Probability. Springer, 1996. 979-9-8---4111-687772 doi: 10.1007/978 10-14-11111----1
URL https: //woi//oiioooooo 101
A Notes on different concepts of agnostic weak learning
A.1 Distribution-Free Boosting
The notion of a weak agnostic learner was introduced by Ben-David et al. [2001]. The following is small extension of their definition, where we added the possibility of failure the weak learner and made explicit the base hypothesis class H.
Definition A.1 (Agnostic Weak Learner Ben-David et al. [2001]). Given Eo, dg [0. 1], learning algorithm W: (X' [+1])* - [+1]* is a (Co, 80)-agnosiic weak learner with sample complexity mo N with respect to reference hypothesis class F C [+1]* and base hypothesis class H C {=1}* iff: For all D E A(X x {+1}), given sample S ~ Dmo with probability at least 1 6g over the randomness of S, the hypothesis v = W(S) E H satisfies that
errp(v) S inf (fr + E0, fef
or, equivalently,
corrp(v) = 1 2 (v)
2 2 inf err (f) -200 FEF
= 1 + 2 sup (- eTI (f)) - 250
fEr
sup corrD(f) 250- fEF
This definition is quite close to that of Ghai and Singh [2024], and to ours. This becomes evident if one employs correlations instead of err, weakens the required correlation between v and F, and lets the weak learner output hypotheses with outputs in [11,
Definition A.2 (Agnostic Weak Learner used in this article). Let 7. 6e E [0, 1]. my E N, F { and 7 C 1| A learning algorithm W: (X' {=1})* H is agnostic weak learner with advantage parameters and so. failure probability 5o. sample complexity mo. reference hypothesis class F, and base hypothesis class H iff: For any distribution D over X' x (+1), given sample S ~ Dma, with probability at least - ón over the randomness of S, the hypothesis w W(S) satisfies that
corr (w) 2 7 sup corrD(f) Eg.
fEF
It is not fully clear whether weak learners in Ghai and Singh [2024] binary real-valued
12

---

If H. is binary-valued H. C {=1}x, the above is equivalent to
1
errp(v) 2 corrp(v))
1
(1
y sup corrp(f) + JEf
2
1
sup corrp(f) + 5g
2
fer
1
+ 7 inf errp(f)
?
2
JEF
This observation shows that the definition captures that of Ben-David et al. [2001] when 7 = 1 and the base hypothesis class is binary.
A.2
Distribationn-Dppndder Boosting
A.2.1 Kalai and Kanade [2009]
Kalai and Kanade [2009] use the following definition of weak learner, where have made the sample complexity a specific parameter. This is an alternative to directly writing "over its random input" in Kalai and Kanade [2009, Definition I].
Definition A.3 (Agnostic Weak Learner [Kalai and Kanade, 2009]). Given E, 6p E (0, 1), and D E ((X), learning algorithm W: (X' x [-1,1]) - 1| is (7, da, D) Da-anostic weak learner with sample complexity my E N with respect to reference hypothesis class F and distribution mo, with probability least 1 - do over the randomness of the hypothesis v = W(S) H satisfies that
D iff: For any re-labeling function g [-1, given sample S Dmm with
ExDD (xND(g(x)v(x)) 2 y sup Exx - Eu-
JeF
The authors mention that one can think of mg as being of the order of 1/e
The above is a distribution-speciiee
notion of weak learning in that the marginal over X' is fixed, while the conditional distribution over the labels can vary. Theorem of Kalai and Kanade [2009] states that there exists an algorithm A which, given access to (7, 6, D)-agnostic weak learner W, produces, with probability at least sup [fxx)))=D[((xx)
48T, hypothesis E {=1} such that IE Dxxx)))))(()) 2 6o/7 /-- - E. Doing so requires = 29/(>22² calls to the weak learner, each requiring my samples. Hence, the total sample complexity is (mmm/(722 which for my 1/2 is of order e
A.2.2 Feldman [2010]
Let D' E A()), and á [| Feldman [2010] defines a distribution A (D', Φ) over examples X' {+1), the following way: First, point X' is drawn according to D', then, is labeled with probability (ω(x) + 1)/2. and labeled - otherwise. With this notation, Feldman [2010] employs the following definition: For 0 < S a < 1/2 and distribution A, an algorithm
W is an (a. 7) -weak agnostic learner iff it produces hypothesis h E H C {+1]* such that
A [x(x) * y] & 1/2 y whenever inf IP Pfx.y)=a[f(x * y] S 1/2 a, where F is a reference hypothesis class. The algorithm proposed by Feldman [2010] works by re-labeling, so weak learning notion.
only requires a distribution-speciin
The weak learning notion used by Kalai and Kanade [2009] implies the definition of Feldman [2010] if, in the definition of Kalai and Kanade [2009], we have H and consisting of binary-valued hypotheses, 7 Ep (the non-trivial case), and &n 0. Specifically, for any a E [0, 1/2), any (7, 0, D)-agnostic weak learner the sense of Kalai and Kanade [2009] (ax, aa - Eo Eo/2)- agnostic learner in the sense of Feldman [2010]. Notice that such learner is only better than random guessing when aa - ea/2 > O, that is, when a > Ea/ The reduction between definitions come from noticing that, for distribution A (D, g) defined in Feldman [2010] but using function
13

---

from the definition of Kalai and Kanade [2009], and for any h E {=1}², we have that
((,))) = Bxwx
( [x(x) +1
h(x) -(11 g(x) +
2 (
h(x)
2
= Exnx ( (xx))/(xx).
Hence, as ((x.y))<(D.. [h(x)y] = coTr (h) = 1- 2 ZerAA (h) for binary-valued h, the condition of
Kalai and Kanade [2009] implies that
Ex-D(g(x)v(x)) n sup Ex Bxx Sp, fet
so
1 1-2crra(V) 29 (1 2 inf err err a EU.
fEF
thus
evr 1/2 + inf err + E0/2.
fef
Hence, if inf (EF err (J) S 1/2- a, then the weak learner returns a hypothesis v such that 1/2 co/2-- ya, as claimed.
s ( (v)
For any 0 < 1, algorithm from Feldman [2010, Theorem 3.1], given access to (a, -eek
learner W, produces classifier v E {+1}* (using at most 1/7² queries to W) such that
errp = inf err + 2a + 6. fEF
That is, to obtain strong learner (i.e., error at most 2s, and then re-scaling & to e/2), one must have 8.
As mentioned, the execution of A queries W at most 1//² times to get an output hypothesis [Feldman, 2010, proof of Theorem 3.1]. After each such query, A checks whether 1 (x..)) [h(x) * y] < 1/2 y, where A, is the distribution at step t. To the best of our knowledge, this check requires 22(179) examples from A, since the threshold could close to 1/2. Furthermore, A also preforms at most 1/e² times a step called "balancing". Each balancing requires checking whether P(x.y)=A,, A y] S 1/2 - s/2 for a hypothesis g. so, by the same reasoning, it should require 0(1/E²) samples. Thus, in total the algorithm needs (11 samples for checking the error of the weak learners output, and O(1/E*) samples for checking the error of the hypothesis returned by the balancing step, yielding a sample complexity of O(1/=* + 1//*). Here, we do not take into account the samples needed for the weak learner calls, which is m if the sample complexity of the weak learner is mo.
Furthermore, if the algorithm by Feldman [2010] is given a (7, 0, D) -gansstttcc weak learner in the sense of Kalai and Kanade [2009], then, to get a strong learner with error at most 2: one So, the weak learner only gives non-trivial guarantee when æ E (2%),
has to set implying that one has to set Eo = (E7)). For Eo = O(sy). this gives a (s, = (ggrr)) weak learner in the setting of Feldman [2010]. which in turn implies that the sample complexity of the weak learner is my = 1/53 = 1/(22²? and that the total sample complexity becomes Ol1/c* 1/(r/)** + ma/7 (2) ()))
A.2.3 Brukhim et al. [2020]
Brukhim et al. [2020] uses the following empirical notion of agnostic weak learning algorithm.
Definition A.4 (Agnostic Weak Learner of Brukhim et al. [2020, Defintion 61). Let F C {==1}* and let X (2i,..., 3mm E xm denote unlabeled sample. A learning algorithm W is (7,50, mp)- agnostic weak learner for F with respect to X if for any labels Y (yi,..., .ymm...,m))) E { {=1m
Est
ye ((())) 2 sup fEF
c0.
where S' = x() y')...., (x Y'ng )) is an independent sample of size mg drawn from the uniform distribution over S = ((x1, v1).- ..., (m vm)).
14

---

The following result states that the correlation of the output hypothesis is competitive with the best hypothesis in the reference class F.
Theorem A.5 (Brukhim al. [2020, Theorem 7]). There exists a boosting algorithm A that given (% co. mo) agnostic weak learner W for F { and sample S = ((z1, Vi),..., (Im Fm as inpua, runs for rounds and returns hypothesis f F satisfying that
m E m
E u.f(xe) -
f(a.))
2
sup SEF
(
m
A where the expectation is taken over the randomness A and W, and the random samples given to W.
In the paragraph following the above theorem (Theorem 7 in their text), Brukhim et al. [2020] argue that one can get a generalization bound up to an additive e term via sample compression, with a sample complexity of m = Ó (CTToo/e"). ) To obtain a bound as in Kalai and Kanade [2009] (setting = 1/(=3²²) and assuming mo = 1/E the sample complexity becomes m = ((L/(=*)==E))
A.2.4 Ghai and Singh [2024]
Ghai and Singh [2024] employs a definition of agnostic weak learner quite close to ours. The only difference is that we assume our weak learner outputs hypothesis W B of range [-1, from base hypothesis class B. They prove the following.
Theorem A.6 (Ghai and Singh [2024, Theorem 4)). Fix e, 5 0. There exist a boosting algorithm
)), 1 O log [B]), A and choice of n, o, T, T, So, S, satisfying T Olog (B)lg[BBB1 /B + ((1/()2())) 2)) such n/7, t = O(ye), S = (1/((re)), So = =O()e²), m = (log
that for any ?-agnostic weak learning oracle for hypothesis class F with finite base class B, fixed
tolerance Eg, and failure probability 6o. algorithm A outputs a hypothesis such that with probability
1 105, 108T,
2e0
corLD 2 sup corr fEr
e,
while making T = (log [B)( calls to the weak learning oracle, and sampling TS + So = O(log (72) labeled examples from DD
For infinite base hypothesis class B, they obtain the analogous result with the VC dimension of B replacing log [3] (Ghai and Singh [2024, Theorem 5)).
B AdaBoost Variation
In the following, we use a slight modification of ADABOOST that, in each boosting round, the weak learner will be run multiple times enlarge the probability of it returning hypothesis with the guaranteed correlation. The last part of the proof below follows directly from Schapire and Freund (2012, page 55, pages 111-112 and pages 277-278] and is included for completeness. Furthermore, we also follow much of the notation from Schapire and Freund [2012].
Lemma B.1 (Restatement of 3.1). Let 1/ E (0, 1), and given m. ma E N, let S E (X' x ( (+1))"
H C [-1,1]x such that for any Q ((S) óg over a sample S' ~ Qmm the hypothesis h = W(S" satisfies (h) 2 2 then, for T 2 [32 (nem))/n/2) running Algorithm I on imput (S. m 5,),)) yields a voting classifier v E conv(H) such that with probability at least 1 - 6 over the random draws from Line 5 it holds that yv(x) > for all (z, v) S.
If learning algorithm W: (X {+1])* with probability at least
Proof. Let Di...., Dr, be the T, random distribution created over the T rounds of boosting in Algorithm 1, where the randomness over S St ..., St. for shorten notation in the following we will for f 1,..., T let S, (S)... ...,... S.). We will show that for f 1,..., T, given any outcome
We concluded the expectation to be over those sources of randomness from the proof of the theorem.
15

---

Di.... Dj of D1. Di..... D, (which is given by a outcome Si...,,1-1 of S1 .i..., St-1) we have that the minimizer h, between ....... h is such that
E B, (y), 2/
S.. Thus, by showing the ahove we get that with probability at least - 8/7 over .!.......
Ss...., V .l,...,77 D. [x)] 7
Es,,....S
[1 E {l,............... T [x (x) 2 r
Es, Sr
Es [1 {1..... T B (x.y (yh, 2 2/]
Es S
Esr (K(x (x) 2 7 1 ( E (I,.... T 1) Blxr) 2 7'}]
Sr.
Psr [x(xx))yyhrl 2 2 1 (1....,
, 7- (xxx))yy((()) 2 7')
2 (1 8/T) Es [ {L...., 1) (xxy)/yh/(e 2 r'}l
(1 6/T) PT. V1 E (1....: 7) (xxx)))yh,xxx) 2
2 (1 8/T)T
2 1 1, 6,
where the first inequality that given ......, , (which determines D,), we have by the above claimed property that Ps, (yh 2 7 I (1 - 5/T) and the last inequality follows by Bernoulli's 's inequality.
Thus, we now show that for 1,.... T. given any outcome Dı,... D2 DI...., Dr we have that the minimizer h, between h ....., h is such that
(x (x)] 2
with probability at least 1 - 8/T, over Sj. We start with the former. To this end let E (1....,7 and D1..... Dt. any outcome of DI...., D., which only depends on S
By Line and Line 13 it follows that D; is such that (z(2, y) > only if (x, v) E S. Thus, it holds for each l = {1..., }} with probability at least 1 - 6, over S that E(xy)>>,, [x)] 2 7'. Now since ,!..., S are sampled independently. it follows that the expected number of hypotheses with y advantages at least
= Esg s!....ss
Σ
BB s 5>> 2 -1-6p (1-50) 1=1
and by the multiplicative Chernoff bound that
k
P Pst.....st
St
1 (Exxy)_, [yh[(x)] 5/} $ 112
< exp
11
8
(1 - 60)
I exp
Vn
T
where the last inequality follows by A = [ (1- This implies that with probability least 1 - 8//T over S, we have that
1 (xxx)) s 5 > #
2
(1 6o)1
2 8 8In(eT/5)
2
1,
16

---

which implies that h, satisfies
E (x [yb,, 2 y
and concludes the first claim.
We for now consider outcomes S1..... ST of ...... ST such that r, = (x,))) [x),(x)] 2 7 for all [T). In the following, we closely follow Schapire and Freund [2012, page 55, page 111-112. and page 277-278). We first notice that for any (I, y) E S we have that
D 1141(1,11) v) Dr(a, y) exp (- (-aryhr(z))
Zr
Di(2, exp exp - - aryh)
II Ze
exp (->ie anyb)(z))
IT== Zr
where the first equality follows from the definition of DI+1, and similarly for the thirds equality using the definition of Dr,... D2, and the last equality by D1 = 1/m. Now using that Dr+1 is probability distribution get that
exp (-yET- arp((ar)
m I Zi
(2,y)ES
So
T
T - -y
II Z,
Σ exp
(anh(())
(8)
t=1
(B.
1=1
Furthermore, we notice that for any E (I....,T) we have that
Z, Σ (1 exp
(x.N)ES
1+yb((I)
1+ yha(I)
1 - yha(a)
Σ
Dr(2,y) exp
-0x
+ az
2
2
(M.))S
1+ (y)(()
1 1 ybo(x)
Σ
D2(I,y)
exp (-a;)) +
exp (at)
2
2
(o.))S
+ Ct
exp (-a:) + (1-
Cz
exp (at),
2
where the inequality uses that (h)(a) E [-1, implying that (+)h,(*) and 1-gh.(#) is scalars between [0, 1] summing to and since the function exp (-) is convex, the function value exp(A(-ax) - (1 A)a,) for any convex combination of aa, and a, (1 2 A 2 0 is upper bounded by the convex combination eexp (-a,) + +(1 exp (at). Furthermore, by inserting the value of ax in
1tes) in the above, get that c-
1 + C2
11- C₁
Z, <
exp (aaz)
exp (ar)
2
ct
+
V
c/
2
2
c
(9)
17

---

Using the relation in Eq. (8) and Eq. (9) we get that, for B = 78/8
T
(2)
T
T
Σ
1=
S 8
Σ exp
Σ
a4
y
Σ
(1))(())
Ei=1 ai
(Z
(o.N))
1=1
1=1
T
T
S exp
8
Z
1=1
t=1
Z exp (Bas)
c+ 0
II (=1
V cτ
(1 1-c
II V (1 c.) --) (1 + ct)
T
c)) 1+9
(10)
where the first inequality follows by a S b implying that 1 - exp(b a). and the second by Eq. (8). the third inequality by Eq. (9) and the last equality by 1 c c = (1 c,)(1 + c,). Now if c, = 1 then the above is and we are done, so assume this is not the case for any c. Now consider the
2(a-z) (1 + x)", thus function f(x)= = (1 - 2²) (-1))""111101 + x) for 0 < x < 1 which has derivative (1 (1-x)-
is decreasing for x 2 a. Now we assumed that we considered a realization of Si...., ST such that C 2 7, for any 1 E [1,.... T} and furthermore, we have that / = 7//8 < 7/. whereby we conclude by the above argued monotonicity that (1 - c.)² - c,) plugging this into Eq. (10) we get that
(1+ 1+3 S (1 -0)1-1/11100 21 + 2 Now
Σ { 1
Σ (E.Y)E
y
E (= o1h((1)
$
Eta ate
m
m
(2.))ES
(111)))--111 (1+)))++
= exp (T/2((1 - 3) In (1 73) (1+ 3) In (1 +7))))
Furthermore, since we soon show that for 8 = 7 holds that
- B) >)) + (1 + 3) In (1 + +2)) S 12/6/
(11)
we conclude that with probability at least 1 - over ,,...., ST we have that
Σ
1(v(x) </v(=)>>>/888 < exp [-Th/2/32) < 1,
(E.))S
where the last inequality follows for T N 32 In (em) / and Eq. (11).
We now show that for 3 = 7 /8 it holds that ((1 - 3) In (1 - >") + (1 + 3) in < 2/116
To this end we consider the function f(x) x² /16 (1 z/ /8)
(1+ +
for 0 S x < 1. We first notice that
f(x) dx (
d
log(1 r) + (1 3) log(1 + x))
x²
16
1
/ 1xx22 +13 In x) In (1 (l+z))
8 x²
and
d
1
[x(22 + 13)
+hhhnnh (1 +l(1+)))) ))
f"(x)
In (1 x1
dx 8 x² -1
x² 18x - 11
8(02 1)2
18

---

Consider the values of x in [0.1). We notice that (x) < O. implying that f" is decreasing
function. Thus, (1=)) +x/8)
(z), f is non-inereasing function. Hence, 0 = f(0) 2 f(x). ie.. s 0 for 0 I < 1/22, which implies
f(x:) = =²
/ /16 + (1 2/ (1))+++
that - 2/ In (1
+ --x /16+ which give use that for B Y
holds that - (11
()) --/2/1 / since 0 < 7 <1.
L
C Margin bound
In this section we derive the following lemma.
Lemma C.1 (Restatement of 3.2). There exist universal constants C' 2 1 and è 0 for which the following holds. For all margin levels & < < L, hypothesis class HH [- and distribution D e ( x {=13), it holds with probability at least 1 ô over S D that for all E conv(H)
)) B + )
(b))s S (v) + C
[z(()-
m
where
L/3/2 (7/ 7) 7/ 7 g
7
In 1
and d d= fat
(---7) - 7)²
To show Lemma 3.2 we need the following two lemmas Lemma C.2 and Lemma C.3. We now present theses two lemmas and show how they imply Lemma 3.2, after we have shown how they imply Lemma 3.2 we give their proof.
Lemma C.2. There exist universal constants c 128 such that: For 0 S < o 1, distribution D over X x {+1}, hypothesis class H [-1, it holds with probability at least m Noo (o,,c,,,(()))a) [27/1 2/=2)0 over Dmm that for all e & conv(H) either
(0)
or
( In(e/0) m
In(e/0)
(b(1) ST+C
m
Lemma C.3. There exists universal constants C 2 1, C and > 0 such that: For margin levels
0 2 < < 1, hypothesis class H C 1| and X E xm, where m 2 Ô C
17'-
[No conv 12y1 Y ~'33 CÔ fat 3/2 (1' 7))- 8n' (V' - 7)2
() 7/ - -7
With Lemma C.2 and Lemma C.3 stated, we now prove Lemma 3.2.
Proof of Lemma 3.2. Let C, C > 1 and è be the universal constants from Lemma C.3 and e 2 1 the universal constant from Lemma C.2. Moreover, let
A 3-= 7.
In the following, we will show that with probability at least 1 8 over S it holds that: For all E conv(H)
3CÕ fates, (H) 3/2
243 T fatea, (H)) B.
8
In (1/0)
(b(1) < C3 (0) +e
(g(())
A3m
(H) (H)
3/2
2m3m fatza, (H) B.
8y'
2ln (1/6)
A3
19

---

CC fatea, (R) since else the right hand side of above is
We notice that we may assume that m 2 greater than 1 and the left hand side most Furthermore, we may also assume that m so large 2
A
that CÒ fates, (7))
Ln 3/2
8 Catea, (H) 3,)
< 1, where Cò (HL
(H)
and C' 2 implies
AG
A4
that the Ln term is equal to In3/2, Now let N exp
CC Cataa, (H) In3/2
C 24 m
8r
A
Catza (72 2,
1 (by the just argued size of m) and define T; lu (N) for i I {1, (1...... ing that the above conditions on m imply that [N] 1, we have that | -
In (N) }. Notic-
m
In (MV
+ S In (N)
(N)
Furthermore, let 8' = å In (N)/(3Nm) Now for each by the union bound that with probability at least 1-11 supxex2" |N (X, conv(H)) over S ~ Dm it holds for all E 7 and all v E conv(H) that
we invoke Lemma 3.2 with 7. and get
A. )18'
[g (v) > zi
or
(b( S sTt (
In (e/8")
In (e/8')
+
Now by Lemma C.3 we have
D
CC fataa, (H) 3/2 3/2
242m 87() Cfazz (H) D,, )
sup X
NNoo (X, conv 2
S exp
N
and we concluded carlier that [ I
3m (N)
thus by = 8 (3N)m, we get that
A )|0" < 5,
7 sup Xexxm
No (X, conv 12>/1
whereby we conclude that probability at least 1 - 8 over D holds for all and all E conv(H) that:
(g) >
(b(1) S44C t (V7 (v71 In (e/8")
In (e/8')
Now on this event, we notice that since L3 (v) E [0, for any o and Uies(Ti, = [ln) 1] it must be the case that for any u E conv (H) there exists an largest E I such that T--1 S 23 $ T. with To 0. Now for this i it must be the case that
(x(( S S + (VZ In (e/8") In (e/8')
and since S T--1 + (N) < C3 (v) + (N) the above implies that
In (e/0") In (e/5")
(b(1) S Tc 1
I < (v) + In (N) +c c | (b)
In (e/8")
In In (N)
In (e/8')
m
m
m
< < (v) +c (V In (E/8")
In (N) (NV + In (e/8")
(12)
20

---

where the second incquality follows from T-- C3 (v) + [n and by va+b S vā vb for a, and the third by Va I a b for a, > and 2 1. Furthermore, as 8'
CC fates, 3
(H) 3/3/2 2 8Y
Cates (H) 2. ))
ò Il (N)/33Nm), and N = exp exp
get that
In (3/6) In (em/ (N)) + 21n (N) In (N) In (e/8')
m
m
Am
In (3/6) +
+ (N))
cÒ fataa, (90) ln
202
C Ciiia (N) Bry
In (3/6) + Ln
+ 2
cc futna, (H)
Ln
247, 8r2 Ö fatra, (H) Bn
CC fatta,, (Ht)
m
3CC fates, (Hl 3/2
8Y Ô fateoy (7) A7
2
In (3/0)
(13)
where the first inequality follows in Ln, and by us considering the case where m is such that In3/2 2 82 Clates, (H) A, 2 1, and Ln being an increasing function and the definition of N the last
inequality follows by 167 A, 2 1, and Lemma C.3, where we start with the former.
CC fatna, 2 and C' 2 1 We now give the proof of Lemma C.2
(A.)*
Now plugging the upper bound on In (e/8')/m of Eq. (13) into Eq. (12) we conclude that
()(0) - 2g(())) - (v c3' (v) In (e/8')
In (N) + (e/8')
3CÒ Fatzs (H) 3/2
2A3m 83 C Fatea, (H) B,
In (3/8)
5 Cs (v)
Cz((1) (v)
A2
(oCfatts,(H) (H) Ln
2 Cates (H) A.,
82
2n (3/8)
m
2mm
Proof of Lemma C.2. In the following we consider the event Ee conv(?() such that
(e) ST
and
(V- In(e/0) m
Cb(v) r
and show that this happens with probability at most 6. Let 3 - v r (e/8) /m In(e/8)/m and E {3v E conv(H) <3((v)
(v) < t, C3 > r cß} denote the above event. We notice that cln(e/6) > 1 then the above holds with probability at most O, since (z) for any conv(H). Thus, we from now on consider the case that cl((e/)) 1.
Observation C.4. what follows we will use that for we have that the function æ v ar in is increasing for 2 a/4, since it has derivative 2/0z'
21

---

We now show that
PS (E) s (1-8/e))P....... (Iv E conv(Hl) (t) (3) 2 cc/2)
Let S be a realization of S in E and let v E conv(H) be hypothesis realizing the above condition of the event E. Since now fixed conclude by the multiplicative Chernoff bound and (D) 2 c (m(e/6) for outcomes implying that 2ln(e/6) 2 (v)m
< 1, since e 2 4, we have that
m
PS (Ez((0)
2 2 (3(1)) s 8/c.
V ()())
Thus with probability at least 1 5/e we have that
(g)(1) 2 Cb(1) (b(1)2mn(e/0)
m
Now using that Cb(v) 2 r + (V Inf//00 In(e//))
it follows from Observation C.4 with
m
a = 2lm(e/6) and x = (1) and e 2 1/2 that,
(b)(0) 2 (Z()) (D(2)2 In(//))
m
r
(V
In(e/6)
In(e/5)
2ln(e/6)
In(e//0)
In(e/0)
m
2T+c
m
m
m
(14)
Now using that e 2 I, a + b+ vab s 2( and Va b va+ + vb we get that the second term in the above is at most
+
In(e/d)
In(e/8)
2ln(e/0)
+
In(e/8)
In(e/d)
ln(e//)
m
m
2 2ln(e/0) T + In(e/6)
$ 2c
m
rin(e/0)
In(e/5)
S Vc2
+
m
m
Thus, we conclude that Eq. (14) is lower bounded by
(1))) (c V22)
V
T In(e/6)
In(e/8)
771
Tln(e/0)
In(e/0) +
2 c/2
m
m
= + + c3/2,
where the last inequality follows by by the law of total probability that
164 and
V22 c/2 0 for c > 16. Thus we conclude
Ps.S'- (3u E conv(H): L3 (v) S T, Cz (0)
> Psss'' (3u E conv(H)) L3 (v) < T, Cz 2 c3/2 B) PS-D (E)
5
2 (1 - PP (E).
22

---

We now show that the term in the first line of the above inequalities is at most
3 - 100ee
sup X
(X, 12711
2
which implies that
7/ ~'~3>10 )10,
PS-D" (E) S (on())))))))))))))))))))))))))))
1271 2
and would conclude the proof
To this end we notice that since S,S' D are i..d. samples we may view them as drawn in the following way: First we draw S ~ Damm and then S is formed by drawing m times without replacement from S, and S' is set equal to the remaining elements in S, S' SSS. We will write drawing S and S' from S as S, S' ~ S. We then have that
Ps..:DDm (3u E conv(H) Lg (v) =. 2++
= S Ps..'' Tu E conv(H) L3 (v) (T c8/2)
S sup PS..'Z (3u conv(H) f3 (1) s (3) 2 +c/12).
We now show that for any E (X' x {+1])= 2m the probability over S. Z in the last line of the above is at most [Nx (X, conv(H)) p2y1 > )//e as claimed, which would conclude the proof. To this end let now Z = (X, E (X x { 2m where X E 22 are the points in Z and Y E {=13m the labels in Z. We recall that for E conv(H)
a
if v(x)) 2
UTa
(x)
v(z)
if < v(z)
-
if v() < a
Furthermore, we notice that for 0 S < a' < v conv(H) and (I, y) such that v(z)y > a' then we also have that 2/20/ (z)y a and (z. such that v(x)y S a then we also have that "12a' (x)y a. Thus, since < < < < and conv(H) {v' o' =12,7,0 o E conv(H)) we conclude that
Ps.S'~ (Bu E conv(H): C3 (v) S (e) 2 +
< Ps (Eu E conv(H)) 1211 C (v) $ T, T (v) 2 r + cB/2).
Let No. = No, conv 12 و22 be - -over for conv (H) | in infinity norm on X ie., Ve conv(H)) |21 there exists v' E No such that max (u(x) dx(x) S "-7 We now notice that for o E conv(HH) o' E No the closest element in No. to v in infinity norm and (x, v) E Z be such that o(zyy > y then v'(x)y = Furthermore, for (Ir,)) y) E Z such that u(r)y S 7 we have that e/ <(x) (z((x)
v(x)y - ztz
( u()))
v(x)y + 2 < 7' +2 Thus, we conclude that
Ps.5'z (3u E conv conv(H)) (21) 1 (b) (,
< Ps,s'z WUEN No: LL :3' (0)
+
Cs (v) E +t (v) (0)2
T In(e/8) (
In(e/6)
Ps,8'z
m
m
No
23

---

where the last inequality follows by the union bound over No.. and the definition of 3. We now show that each term in the sum over V E No is bounded by 8/e which would give that the above is most co (X, conv(H) / as claimed earlier and conclude the proof.
To this end consider E No., and let (Lgg (e) Lgg (v)) i.e., the fraction of points in X that has less than (>' + + m2amminnn We first notice that for the above sum such that
x' 2p L (w) + Ls (v) <T/22
(v FIn(e/0)
In(e/5)
جب (v) Lg (v)
the term is 0. Thus, consider for now being such that 2p We notice that is the expectation of Ls (v). Furthermore,
Ls
+ c/2 rine//0) In(e/d)
since Lgg is samples without replacement from [1(()) S z multiplicative Chernoff bound without replacement [Hoeffding, 1963, Section 6] and μ 2 clafe/6) lln(e/8) (since e 64) that,
2 HiwwEs it follows by the
4m
m
P C
(v) S 1 (1-V
2 Ii((e/0)
S
8
pm
Thus, we conclude that with probability at least 1 - 8/e we have that,
+' Lg
(v) 2 1 v 2uln(e/5)
(15)
which since
Lg (v)
L
(w)
5 12 and that Va + S Va + vb gives that
1 1/7
- V
1 Ls (o)
Ls (v) 2 Lg (v) + Lss
(0) 12
- Ls (v)
m
so
Lss x (n))n(e/)) 2 Lz²
Lg (u) +
(v)
V m Ls' (v) In(e/6).
m
We now show that for outcomes of S and S' such that Lg (0) S t and L
(v) 2 +
(V ll(e//0) la(e/5)
c/2
it holds that
4 f (v) < Ls (v) V fg. (n)//())))
S (1) +
which combined with the conclusion below Eq. (15) implies that S and S' such that Ls
ST
and L.S (w) 2T
(V la(e/8) /rlate/0)
In(e/8) happens with probability at most 8/e concluding
the proof.
Thus consider outcomes S, of S and S' such that L (w) S and L.
> T
c/2 (V /m(e//6) In(e/8) ). We first notice that since for a > 0. x + var is increasing in x
we have that
s L
(v)ln(e/0) ST+ / / Iu(e/()))
L (v) +
(16)
m
24

---

Furthermore, since by Observation C.4 we have that 2 Vax is increasing for 2 a/4, which +
I = Lg (v) and a 4lm(e/8) and Lg
(v) 2 r + e/2 (V in(e//))
In(e/8)
2 32 we
conclude that
C
Ls. (n)
m
T Lu(e//0
In(e/0) m
4
T
Tin(e/0)
i
))
2
2 0/2
T + c/2
V
In(e/0).
m
m
m
(17)
Using that c/2 2 and that + b + vab s 2(a + b) for a, b and that va+bs va+ we get that the last term in the above can be upper bounded by.
T In
(
In(e/0)
)
2c
In(e/d)
In(e/6)
T
V m
+
In
+
+
In
m
2
m
m
m
4c
In(e/5)
1 V
In
m
m
rIn(e/5)
In(e/8)
s 2 2Vo
m
Thus, plugging back into Eq. (17) we conclude that
/ - ب (v) V (n)
(
2 r (c/2-2Ve) 2Ve)
(
Tln(e/0)
In(e/o)
8
T rl((e/0)
In(e/5)
2 + c/4
(18)
where the last inequality follows by c/2 2 2 c/4 since 2 128. Furthermore since c/4 2 32 we conclude by the above Eq. (18) and Eq. (16) that
Cg
(v)
In
< Lg. (v)
m Ss
(v)
8
8
m
We now move on to show Lemma C.3. For that, we need Rudelson and Vershynin [2006, Theorem 4.4] bounding the minimal infinity cover of function class in terms of its fat shattering dimension Lemma C.5. There exists universal constants C' > and c > O such that: For a function class F and a point set X {a1...... Fm of size m, such that for any E holds that Σ [o(x)l/m S Then for 0 < 1, and < 1/2 holds that for d fabioza (F) that
m dd In
2m
a))) I Cd
Furthermore, to show Lemma C.3 we need the following lemma upper bounding the fat shattering dimension of convex combinations of hypothesis class H. truncated to [r]. by the fat shattering dimension of the hypothesis class H.
Lemma C.6. There exists universal constants C" 2 and 1 12 > O such that: For hypothesis class H. [-1,1] 7 and >> O we have that
C' (H)
fak, (conv (conv(H)))))
a²
We now show how the above two lemmas combined give Lemma C.3.
25

---

Proof of Lemma C.3. Let in the following C 2 1 and e > 0 denote the universal constants of Lemma C.5, Furthermore let C² > 1 and denote the universal constants of Lemma C.6, and lastly let è E and Ć max o
We first consider the function class conv(H) [2 /22/) = f/(2n)) f E conv (2) J. i.., the functions in conv(H) scaled by 1/(27)) We notice that the functions conv(H))227) 12y11 /(27), has absolute value at most 1, thus it if we consider a minimal '' 2cover in infinity norm of conv(H) [2/1] (2) (27)), denote it No = No (X, cony conv(H) (22"), 2 77,, i.c.
[2
for all v E conv (2) (22)) there exists ê E No such that for
max)v(z)= 6(x)) 7'-7 zEX
47'
and any other cover with this property has size less than equal Noo We notice that since for any E conv (H) (20 [2y]] we have that w/(2"') E conv(H) [2y7 ((2"), we have that there exists i E No such that
--7
max (o(x)/(27)) - -(x)] s 44y
ZEX
which further implies that
max (27))))))) -7 =
2
whereby we conclude that (2 (v' (2T))o Noc the functions in Nox scaled by (2r"), is a 2 7 cover for conv 1271]- Thus, we can bound that size of No we also get an upper bound on the size minimal d-x- cover for conv(H)(2y7)) where we denote such a minimal cover No conv [2 -==")
We notice that fat -t (conv(H)) (2-1 (27/)) = fat (aterrym (conv (Conv(H))pp)) (271)) ), where we have used
that for scalars a, > 0 and function class F have that fat, FF: fat (FF), where b F is the function class obtained from FF by scaling all the functions in JF by Further- more by Lemma C.6 we have that ay'-a (conv (2x7)
((7')) fat ann (conv (277) s
By
0'16fat-acr (H)
è Cattrry- (70)
S m, by m fat fataayy-n) c d'c and C max(1, o (ザ'
(1y--)3²
(-'-
1
ie.. 1 S mm/ fat (('-)) (conv (H) (27')) and we may thus invoke Lemma C.5 with the function
class conv(HH) 127'1 (27'), 1/2 and y/م7 (which is less than 1/2) to get that
In (INs 127/1
12717 -'3331
(27'), 2' 2ー13ン)
<in (X, conv 129) 1207
4"'
47'
(27') SC fat (conv(H)) 127'1 /(27)))n In
fat aat
(conv (H) (conv(H) 1291 (H) (227)) 7 -7
87
2m
1/2
[ab co) 877
(conv (H) (2>'))
12-11
47
< C ((/=))) (conv(?t) (271 /(27)))In37 Byy
fat fate///>>) (conv(H) 271 1(271) 7 -7
8%/
< C fat - (conv(?L) p2-7 /(27))
m
fat (conv 24, /(27)) -7
87'
26

---

where we in the second to last inequality have used that ب 2 2, and in the last we make an upper bound need in the following to argue for the monotonicity of a function. To this end consider a number
0 and the function f(x) = In (a/x), for a/e > We notice that has derivative ('(x) &V (2 (9) 3), which is non-negative when 2 In
3 0 our equivalently exp (3)
x, thus increasing for such values. Now consider
Byy m Y --
We have that m 2
(a (H) fat ut 87" (3'-7)"
(conv(H) [2y1) ((22)), implying that 8Y > exp (2) Thus
8-
Cangey (H) fat clriom) (conv 2-11 ((27)), since
m
exp ()
(r'-))²
7'
using this observation, with the above argued monotonicity of In 3/2 (a/z) for exp > 2. where
e
By' and x fatess ( (conv(H)) 1297 ((27)) we conclude that --ク
m
By"
In (on,( y -ー31
2
< C'tat (conv 127'1 (27 (271))|n3/2 3/3
m (conv (271 (2 7 -7
8%/
fat
"7"
CÔ fatarrr->21 3/2
(0' - mm
8//
(7' 7)2
((al)(y=)))))) -
To prove Lemma C.6, we will drive a lower and a upper bound on the Rademacher complexity in terms of the fat shattering dimension of conv (H) and H. From this relation we can bound the fat shattering dimension of conv (H) in terms of H. To the end of showing the upper bound we need the following two lemmas. The first results gives a bound on the Rademacher complexity of a function class F in terms the size of a minimal e-cover of F R. over point set S { 1P1--... Fm } in L22 To this end we let (S, e), denote the size of the smallest set of functions N C R with the
property that for any f E F, there exists f' E N such that V (z; fzx //m S..
Lemma C.7 (Dudley's 's Entropy Integral Bound. E.g., Rebeschini [2021, Proposition 5.3]). Let F be class of real- functions, S = {x1,.... [m be a point sel of points, and N2,S, be the size of minimal e-cover of F. Assuming SuP ( E (x(x))) 1/2 c, then we have
12
re/2
(++(+))
sup Σ (x;) m FEF
S inf cE(0.e/2]
4E +
v In (I,(NN(,,F,
V
From the above lemma we see that having a bound on (2 F, E). implies an upper bound on the Rademacher complexity. To the end of bounding (2, E), we present the following lemma (it is special case of Rudelson and Vershynin [2006, Corollary 5.4] with for instance p 2 and 3.).
Lemma C.S. Let F be hypothesis set bounded in absolute value by 1. Let S = {x1..... Jm be set of m points. There exists universal constants C > 0 and 0 < c such that for any < 1/2. we have that
In ((,,(S)F,))) S C' faties (F) In (1/(cE))
We now combine the above lemmas to derive an upper bound on the Rademacher complexity in terms of the fat shattering dimension of conv(H) and H. Furthermore, using the definition of fat shattering dimension we also derive and lower bound on the Rademacher complexity. Solving for the fat shattering dimension of conv(H) in this relation give the claim of Lemma C.6.
Proof of Lemma C.6. Shattering of conv (H) implies shattering of conv(H): We first recall the definition of
27

---

conv(H) =1pp1 : v conv(H)), where the operation (-) was
Y if [()) 2 7
e(z) if -2 7 < v(x) <>
-f S -y
We notice that by this definition we always have that 1ry) (ar) implies 211 2 v(x) and -Y < Upy] (z) implies U/>] I v(x).
Now consider sequence of points æ1, #1....;2a Fd and levels ri....,pd ra which is shattered by conv(H) i.e., we have that for any b E {+1]", there exists up1 E conv(H) where
E conv(H), such that for i [d] it holds that
(2,) 2 + a if = (14) S if -.
We notice that since U[y] only attains values in |->,7] it must be the case that ? for d not to be O(and S since conv conv(H) [ is bounded in absolute value by 1) where by the claim holds. Thus, assume from
on that attaining values in [-y,7], 7). that it must be the case that r; E [a Y al, stated equivalently that -Y S r; 0, r; S % otherwise no function p5>] E conv(H( below r; since in this case either r; a < -7 or ri + a > 7-
y and a
We further notice, again by Up>l
[=] in can either be above or a
Now for r; E [a [a--7 7, 7 earlier conclude that 7 2T11 implies Up1 2 v(z) and - < (z)( implies Up> S v(x), we get that if r, also have that r;
a] we notice that have that -7 < + a and that y > ri-ma a thus since we
v(x,), and if + S Upy] (2) then v(2)). This shows, by Z1...., Zd and fi. .d. shattering conv(H) that Td and ri..... Td, is also a-shattering cHnv(H).
U/1] (2:)) then also have that r;
Bounds on the Rademacher complexity of conv(H) in terms of (at,,,, d, and a: Since cOnv(H) is a-shattered by .i..... Fi and Fi, ri.....,' Ta this implies that for any b E {+1} we have that there exists conv(H) such that (1(zz) r;)) 2 of (3)(11)) lower bounded as follows
Thus, we conclude by the expectation
Σ o. = 0 that the Rademacher complexity of conv(H) on 21....; Zd can be
E (111)
sup (EC)nv(H)) 1=1
Eow(ax)) (111 sup Σ (1(x() - 2 (19) (EL) 1=1
Furthermore, we notice that the Rademacher complexity of conv(H), the same as the Rademacher complexity of H. since conv(H) are convex combinations of hypothesis in H. To see this con- sider realization a of a, then for any v E conv conv(H), which can be written as v ΣnER and have that Σ 0,0(2,) = ΣnER On E o,h(2,) I SuPдEи Ei= a;h(I;), where the last inequality follows by ΣnEN On = 1. The opposite direction of the inequality follows from H S conv(H) thus we have that
where ΣRER OA 1 and an 2
E
sup Σ Co:o(zs) Bow1=1
sup (εu())) DEH i=1
(20)
PEconv (H)
i=1
Now since E (H)v(H) is bounded absolute value by 1 follows by Applying Lemma C.7 yields
E Eow(+1)
sup Σ wEH 1=1
d
< inf e0(0.1/2)
4
12
1/2
VIn((Na(X,HH,)) H, du du): (21)
Vā
where [N2 H, v) is the size of a minimal llover of H on X that is, for any h E H. there exists an h (X, H, v) such that / VEL (h(x;) (E - h(z:)) < Now applying Lemma C.8 yields In (N2 H. e)]) < C fates (H) In (I/(c))) for universal constants C 2 1 and 1 2 0.
28

---

Now setting E = a/8 in Eq. (21) (recall we are in the case that a S 1) and plugging in the above bound on in (INV((X, H. =)))
12 1/2
E [=
sup Σ 0,0(2a) DEH 1=1
S 5a/2+
VC fatee Catace (H) In (I/(c())) de,
vd a/8
12 CV /a (H)
2
< a +
Vin (1/e") de'
c/d
co/8
/ /at
- 5a/2+ +
(22)
c/d
where the second inequality follows from integration by substitution with cs = E', and the last by So vin (1/E") de' < 1. Now combining the upper bound of Eq. (22), lower bound of Eq. (19) and the relation Eq. (20) we get that
12 C Cfttca//(H))
S a/2+
cvd
which implies that
24 ca (H)
s
aa²
Thus, we conclude that conv (H)v(H) [-] can not be a-shattered by point set X = (xi,..., va) and level
sets ri...., ra of more than 24 (89E) points, and we can conclude that (con (conn(H)) s
c²a?
2 (a() and setting C' = max (1, 24'C) and c' c/8 this concludes the proof.
D Agnostic boosting proof
In this section we give the proof of Theorem 3.4, which impies Theorem 1.3. To keep notation concise in the following we will let 0 y Eg.
Lemma D.1 E (0, 1), m N, and D A(X x {=1}). Then,
and Ben-David [2014, Lemma B.10)). Let u E [-1, e [-1,1]
2 Cg (v) lm(1/)) 4lm(1/8)
Ps ()(() s (z)
2 1 1 8,
and
2 2% (v) 21n(1/8)
Ps
s ( +1
2 21-6
3m
Lemma D.2. There exists universal constants C' 2 1 and è such that: Letting d = cataty-ea)/ 16. after the for loop starting at Line 3, with probability least 1 Algorithm 1, Bi contains a voting classifier Vg such that
28 over S₁ and randomness used in
20/3 (vg)
3C'
16
3/2
3/2
20 m
In
10c
(23)
m
g²
3 162d
Proof. We first notice that may assume that
10c
3 C6
m > 3C' In
and
m 2
(24)
5
8²
as otherwise the right hand side Eq. (23) greater than 1 and the result follows by noting that 22/1 (vg) < 1.
29

---

Without loss of generality. let
arg max corro(J) fer
To the end of making an observation about Algorithm 2 let S₁ be realization of St. The execution of Algorithm 2 runs Algorithm I with all possible labelings of Si ((x1, v1),.... .... (Tm/3 Um/a)). In partieular, letting
S1,- == (( m/3
and denoting Algorithm by A. it must be the case that A(S Bi. Moreover, correctly classifies all points in Si,f, and f F, we have that ser corr (f) = for any distribution DD' over St.r- Therefore, for such 'D', the weak-learning guarantee becomes that with probability at least 1 dg over 5 (D it holds that
corrD (W(5") 2 7 sup corT (f) Eo
fer
ED 8.
Accordingly, to leverage Lemma 3.1, let
Ei(Si,r)) = { ( (A(S),)))) -0).
be an event over the randomness used in Algorithm and notice that Line 6 runs A on St,5 for
T 32mm In(em)]
32 In(mm)
(by Eq. (24))
g²
with k = [8 ( - [.]]] Thus, applying Lemma 3.1 with 7 = ensures that
P(E
10"
Notice we showed the above for any realization S1 of Sj. Let in the following E₁ ES(,,.)))
Invoking Lemma 3.2 with Si,5- ~ DT. and margin levels 0/16 < 0/8 ensures that, with probability at least 1 - 6/ 10, the event (over S1,5-)
Es (oo conv(HH):
L.p
-0/10 (v)
20/8 (v) C²
(V (v) 100m3m3300 9m/33,0 }
holds, where fatag/16 (H()) and
1
16 L/2
2nd 162d
10e
pn,
+ In
n
X2
8
In the following, we will use A refer to the randomness used in all calls to Algorithm during the exccution Algorithm 2. Namely, the randomness used in Line 6 to draw from Dr, where assume all the (2) 1) h draws to be mutually independent.
Compiling the above, we have that
PSI. Ee E B, 10/30 (v) S C² (m/3.8
2 PSAA
C0/16 D.. (A(SI.5-)) < C' C'Bm/3.0
(as A(S),,-) E Bi) (by independence of S and .A)
Es,
EA 1f
8/11 (A(S,,)))))))) C" C'Bmm/3.0
I1
D.,
2 Es
EA
of -2/100 (A(S
1[Fi}] 1(Fa)]
2 (1 5/10)²
(25)
(by Bernoulli's inequality) where Eq. (25) holds the events F, and Eg each hold with probability least 5/10 and their simultaneous occurence implying that ( (A(S),,))) s C' C'3m/3.0
28/10,
30

---

Lemma D.3 (Restatement of 3.3). There exists universal constants C' 2 1 and è > 0 such that: Letting d = fata(y-so)/3z) (H), after the for loop starting at Line of Algoritim 2, with probability at least 1 - 6/2 over S1, S2 and randomness used in Algorithm 1, that Bg contains a voting classifier By such that
CD(Pg) S eIrp(f*+ +
CerrD(f*)
d
Ln
1/2
6m d
10 + In
02
8
+ C
d
(02m d
10
Ln
3/2
+
In
(26)
m
Proof. It will be useful to consider the function Ç: Ry0 Rx given by
((x)= x- 1/3/2 3/2 ( 22z, e²)))
which is decreasing for any 0.
To see this, let f(x) = x In 222))22) for x > 1/2, so that f'(x) = in) thus f(x) is decreasing for x In (max(2x, {²}) is decreasing for > We shall also implicitly use that Ln(x) =
2n
exp(3/2)/2. As 1/2 is decreasing for
we conclude that
In(max{a, e}) S In(max{a, e²)).
We will prove Eq. (26) for 2 3072e². Thus, we may assume that
3072.ad
02
as otherwise the right hand side of Eq. (26) is greater than and the result follows trivially.
By Lemma D.2, with probability at least 1 26
i0 over S ~ Dm/3 and the randomness used in
Algorithm there exists voting classifier Vg E B1 such that
C, C² (
pm
3
10
162d
(27)
m
with fatza/16 and C' 1. Since the fat-shattering dimension is decreasing in its level parameter, fat,g/16 < fatar/32 d, thus, by the monotonic decrease of and the above,
cc((( I'm
3 10
Dj. (va)
3.22d
3 162
+
(28)
m
Consider realization 81 of S and the randomness of Algorithm for which the above holds, and let 2g B1 be the associated classifier. Then, by Lemma D.1, with probability at least 1 5 over S2,
0/16
2 (v,) S 0 (v,) +
(vg)
10
10
In
(29)
m
6
m
2-6 To see that 2 E (1,1/2,1/4,.. ... 1/2 1/22/11/ (o2)s)))) so that it is considered in Line 6 of Algorithm 2, recall that we are in the case m 2 307222 thus 0/16 2 /24/m.
Let ig be the natural number such that 0/16 [2 [2- 2-, and let Y/
Letting d' = fatér, (H), Lemma 3.2 with sample S2 and margin levels 0 and 7/ ensures that, with probability least 1 5/ over S2 ~ Dm/3 holds that for all v E conv(H)
Co(v) < (z) + C²
(7g)²m) 3d'
3
10
(7g) 2 m
3 10
+
In
In
m
3d
m
Furthermore, the choice Ng implies that 7g > 0/32, and by the fat-shattering dimension being decreasing its level parameter implies that d' fater; (H) S fates/ /32 (H) d. Applying this in
31

---

the inequality above, combined with the monotonic decrease of Ç yields that, with probabilities at least 1 5/10 over 22.
CD(D) S C3. (v) + C"
( (5)
(
3 322 3-322
fm
+
m
3
10 8
+
3 322 d
0m
+ m7
In
10 6
for all E conv(H). In particular, the above holds for o/g = arg min wEB, L (v). With that,
as Ug E Bi, we have that (o)( S C (1g). Additionally, as 7/ _ 0/16, it must be that
(1g).. (3)(1g) (1g) S 2/16 (())))))) Altogether, we obtain that with probability at least 1 8/10 over S2.
Co(1') & Ss
2/16 (1²) (r,)
+
+
CS2
c0/10 (10)
(<({
3-
8
32
+ In
m 8
3 10
c(
m2m
3
10
In
3. 323
m
8
Using the union bound to also have Eq. (29) hold, we obtain that with probability at least 1 - 28/10 over S2,
CD((g)) S (vg) +
2 co (Ug)
In
10
6
In
10
C'
c
0'm
3
In
10
m
m
8
3.
322
m
(2)10(1))
2 co (vn)
10
10
02m
10
+ C'y
(wg) +
In
In
+ In
m
5
3 32
5
(30)
To bound C6 CB/16 (Ug). we make the following observation. Given function ʃ E {+1)* example
(z, v) X {=1} and voting classifier u E conv(H), if y v(x) < 0/16, then either f(x) = y. so that f(x) v(x) < 0/16; or f(x) = y.. so that y fxx) & 0/16. Applying this for f and ugg we conclude that
c / (wg) S crr f*) + 2% (Vg),
(31)
where we have used the definition of Dy.
With Eq. (30) in mind, Eq. (31) yields that
0/16
c co (vg) +
2
(Ug)
10
6
10
In
m
8
m
2 2//0//0 (vg)
I <errp(s*) +
2 (errp(s*)
In
10
+
2/16
(1g) +
In
10
+
6
In
m
8
m
8
m
8
(as Va +
S Va
+
Vb for a, b 0)
< <erro( +
2 (f+
In
10
+ 2
Dy, (Ug) +
0/16
1
+
6
lu
10
(32)
m
2m
m
(as 2/ ab < a + b for a, > 0 (AM-GN inequality)
7 In
10
2eerrp(f*) + 2 (1²)
(33)
8
where the last inequality follows again from the AM-GM inequality. Using Eq. (28) and that C' 2 1, the two last inequalities (Eq. (33) and Eq. (32)) yield the two upper bounds, respectively:
0/16 2 c
2 2011 +
(vg)
In
10
6
In
10
m
8
m
< <emll( +1
2 2errp (f+)
In
10
+ 2C 5(
Pm
+ 7
In
10
m
5
3. 362,1
8
32

---

and
2 (0g) + S 22crr + 2C
LCD 16 (vg))
In
10
+
6
In
8
m
8
Pm m
10
5
+
In
162d
m
8
Applying both of these to Eq. (30), we conclude that
2 (erra(f*)
10
LD(1))) S errp(
+
In 8
0
10 5
+ 5(( (c(c(
0.m
3 10
20"
In
+
3 162
m
3. 322
m
(5(
((_02mm
O'
+ 7 In
10
)
0mm
3
10
+ +C",
2eIrD(f*) + 20
3 162d)
8
3 322
+
In
6
{erp((*)+
2 (err
10
30
c(
0
In
10
m
3 323 d
m
8
+C²
(( 33.
02m
+ In
10
3.32
6
+C'V20" (
I'm
7
+
(34)
3 322d
m
0.m
10
< Serro(]*) + (1 0n) (
In 6
3 33322
I'm
10
+
In
3. 322d
5
[
0.m
3
10
<erro([*)+ VONY (2err
In
3 32
m
8
(<( I'm
7 In
10
+33C' + C' C2V20')
Cerrd(S*)
d
(pmm
10
ccrp(f*)
In
In
m
02
d
d g
I'
10 In 5
In
3/2
where in Eq. (34) we used that va + S Va + Vb for a, > 0, that C" 2 1, and that Ç is decreasing, and in the last inequality we used the definition of Ç and that m 2 3072e"d such that 02m/(3 3222)= 2 e². Finally, since we show the above with probability at least S2 and for any realization S₁ of S and the randomness of Algorithm 1 satisfying Eq. (27), which happens with probability at least
26
10 over
25 it follows by independence that the bound on en holds with Tn probability least 1 45/10- 1 8/2. Since vy E Bz, this concludes the proof.
Theorem D.4 (Restatement of 3.4). There exist universal constants C, O such that the following
holds. Let W be (7, Eo, do. mo. F. H) agnostic weak learner. If > Eg and dn < 1, then, for all 8 E (0, 1). m E N. and D E A(X (+1)), given training sequence S D we have that Algorithm on inputs (S, W, Sn, mo) returns, with probability at least 1 - 5 over S and the internal randomness of the algorithm, the output v of Algorithm 2 satisfies that
Lo(v) S cfrp(f* + - C.
33

---

where
(7 ((--E))
E0)
In
8 = (7 En) 2m
Ln 3/2
3/2
+
Iu
d
m
with d = falc(7-20)/322 (H).
Proof. We will now show that with probability atleast 1 d over S and the randomness of Algorithm we have that
11Cerrp(f*)
02m
28 In (m)
(D(r) S (
Ln
3/2
3/2
In
+
0
14C
d
8 m
28 In (m)
-L
3/2
1n +
m
d
with d = fat /32 (H), C 2 and è 0 being the universal constant of Lemma 3.3. Thus, it suffices
consider 2 14 else the right hand-side of the inequality is greater than and we are done by the left hand-side being at most 1. Now by Lemma 3.3 we have that with probability at least 1 - 6/2 over S and S2, and the randomness of Algorithm it holds that there exists Un E B2 such that
3C (CrrD((ft
(
Ln (82m) +
10e
CD(wg) S errp((") +
m
02
5
3C
d
Ln
3/2
0m
+ In
10e 8
(35)
m B2
d
with à = Tat (H), 2 and being the universal constant of Lemma 3.3, call this event Ej. Now consider any realization S1, S2 of S1, S2 and the randomness used in Algorithm such that the above holds (so, within event E1) and let V, denote an arbitrary v E B2 such that the above holds.
We now invoke both equations of Lemma D. with 5 = 6/(4/B2)) (abusing notation of 6) 7 0 for each B2 which combined with union bound give that it holds with probability least 1 6/2 over S3 Dm/3 that
Lss (v) (4
(2 (21/8)
CD(u) s (s.(o)+ +
m
m
and
6 (n
6 6 (l
(s,(u) S
(36)
3m
77
Consider such realization S3 of S3. and denote event where the above inequalities hold by Eg. Now v be the voting classifier B, with the smallest empirical O-margin loss -
argmin (v), with ties broken arbitrary (i.e., the output of Algorithm 2). Now by Eq. (36)
and v B2, we have that
6 Ls, (V) In (M44B2)) B21/8)
12 (2In(4/B2//4
LD(v)= S (v) +
m
m
L.s (1g) In(4 B2//2 /0)
12 (2 B2l/5) +
s L.) +
6 (D)g)) l2(48
Cs.
(v.
In (n(4//2/0)
18 (4/22//0)
<Lo(yg)) +
3m
(37)
where the first inequality follows from Eq. (36) and e E B2, the second inequality from v being a empirical minimizer of Ls,, so Ls, (v) < Ls, (v,) and the last Eq. (36). Now by Eq. (36) we have
(s, 22 + 12 (4) (2)5)
(38)
34

---

where the inequality follows by vab S + b for a, 6 > 0. This implies that
6 L (1g) (2
6 22 (2Lg(v)) 12 (4/
(2)4)
77
m
12 (vg)) In(4 B2)/6)
18 (4
(39)
m where the first inequality follows from Eq. (38) and the second by Va va+b= vā vb. Whereby plugging Eq. (39) into Eq. (37) gives that
m
CD(l)= S CD(L,) + / (6L((v) In 12(4/8) +
12 LD 1n ( ln(41B2105)
3m
m
18 (41B21/8)
18 (4/44/22/88)
m
m
36 L (1g)
Inf (2l/5)
36 In (4(
s CD(()) +
3m
m
36 LD (Eg) In(16 In (m)/6)
36 (16 In (ma)/0)
(D(()) +
(40)
3m
m
where the first inequality follows by Eq. (39), and the last by [8 S [log2 (og)(v/)] = 2 s 4 In (m).
since we consider the case m 2 14. Now by using Eq. (35) and Vab S a + we get that
6C
0 m
10c
(D(wg) 2eerr((f))
Ln
3/2
In
(41)
m
d
8
Thus, we have that
36 CD())) In(12 (m)/8)
m
36 (2erpp(ft++ + &C
Ln3/2
3/2
92 d
+ 10c]
In In
In(12In (m)
72 (2errp(()) (m)/6)
14C
d
3/2 Ln3/2
( (Pm) + 12 (88 (m)
(81n(m)) )
(42)
0
where the first inequality follows from Eq. (41), and the second by va +b s va + vb. Now
plugging in Eq. (35) and Eq. (42) into Eq. (40) we get that
36 CD (v,) In(16 (m)/0)
36 In (16 In (m)/6)
(D(v)= < (D(),) +
3m
S (erp(("))
3C 3CerrD(J*)
3/2
P2 d
+ In
10e
m
B2
5
3C
2m
10e
In 3/2
+ In
g
8
72 errp f*)
In (12 In (m)/8)
14C
d
3/2 p0
28 In (m)
Ln3/2
12
g
8
36 In (m)/5)
11Cerrp(f*)
à
(f)))
28 In (m)
<erD(ft)+
Ln3/2
In
m
82
14C
d
12
28 In (m)
Lu
3/2
16
(43)
m
0
35

---

Let the above event be denoted Ez. Thus, we have shown the above for any realization S1 and S2 of S and 2 and the randomness of Algorithm which are in E,, and S3 on event Eg the output of Algorithm 2 achieves the error bound of Eq. (43). Thus, since the randomness of S1, S2, S3 and the randomness over Algorithm are independent and E. and Eg both happened with probability at least 1 8/2 over respectively $ S2 and the randomness of Algorithm and $3, the proof follows by (Iet r denote the randomness Algorithm 1)
PSwD" [Es] 2 S2-D//3
T Syn Dm/a
[E] 1[E:}]
2 S.nD//3
I' DynDmm
E2, Eg] [[E1]]
M Es S2mm//3
[P's S Dm/a
[g] [[Ei}]
2 (1 - 8/2)²
2 1 6,
where the third inequality follows from E₁ and E2 implying E3 and the fourth inequality by Ez given E, happens holds with probability at least 1 5/2 over S3 and that E₁ holds with probability least 1 8/2 over Si, S2 and the randomness r over Algorithm which concludes the proof the theorem.
E Lower Bound
In this section, we present the proof of our lower bound on the sample complexity of agnostic weak-to-strong learning. We first re-state the result in a more general form than that in Section 1.
Theorem E.1. For all inleger d 0 and (0, 1) such that d 2 (2/g(2//²) and all eo, do (0, 1]. there exist a universe X, a base class B C {+1]* with VC dimension at most d, a reference class
[dIn(4/ such F (=1,*, and a (7,, d0, Eu, mo, F, F) agnostic weak learner with my = that for any E (0,1/2) and any learner A, holds that there exists data distribution D such that fer(er 1m that
6o
and for m 2 2111 we have with probability at least 1/50 over
d
2
i jer crrp(f)
ES (erT 2 inf errD(f)
+
fEF
50 32 12g (2/22)
Furthermore, for all E E (0, 2/2), 5 E (0. 1), and any learning algorithm A, there exists data distribution D such that m In(1/(4)))/(22)) then with probability at least ó over S ~ Dm have that
errd(A(()) 2 inf errp(f) + JeT
and for any E (0, /2/16), and any learning algorithm A: (X x {+1})* + {=1)* there exists data distribution D such that if m < 20087" (2gg(2/ then with probability at least 1/8 over 1m we have that
eTTD(A(S)) 2 inf err +
JEF
To prove Theorem E. we need the following lemma giving the construction of a hard instance.
Lemma E.2. Let n, > be integers, and Eg. E (0, 1]. In a power 2, then there exists universe X |n s). base class B C [+1]* with [B] (2n)*, a reference class F {+1}*
(all possible mappings X + (=1)), and a (1/ VT, do, Eo, ma F, B) agnostic weak learner for any
8 (22
mo
IV
We postpone the proof of Lemma E.2 to the end of this section, and now show how to combine it with the following classic results to obtain the claimed bounds.
Lemma F.3 (Devroye et al. [1996, Theorem 14.5)). Let X be a universe and F C X (+1) be function class with VC(F) d > 2. Then, for any L 10.1, and any learning algorithu
36

---

A: (X' {=1])) + {=1} there exists data distribution D such that inf feffferffrr( L and for m 2 d-1 max (1-21ş²) } we have that
EL
Bg (orr) 2 inf err + (d- 1) inf /EF eITD FEF
24m
By slightly modifying the proof of Devroye et al. [1996]. we conclude that the above lower bound holds with constant probability, result provided in the next lemma. For completeness, we provide its proof in the end of this appendix.
Lemma E.4. Let be universe and F - {=1} be a function class with VC(F) d Then, for any L E (0, 1/2), and any learning algorithm A: (X x (+1})* {+1)* there exists data distribution D such that inf fer [eF(crr((f) L and for 101/2-132 1.ya
it holds with probability at
least 1/50 over S T that
2
inf inf
erTp(A(S)) 2 inf err fEF
50
16m
We furthermore need the following lower bound on the sample complexity of agnostic learning.
Lemma E.5 (Shalev-Shwartz and Ben-David [2014, Section 28.2, pgs. 393-398]). Let X be universe and F S [+1]* be function class with VC(F) d d Then, for any (0, 1/vl. 5e E (0, 1), and any learning algorithm A: (X x {+1))² + {+1]* there exists a data distribution D such that m & ln(11(45))/ (2?²), then with probability at least ó over S Dm we have that
(Ars(A(S)) 2 inf errp(f)+ +
FEF
Furthermore, for any & E (0, (8)2) and any learning algorithm A: (X x (+1))* - {+1)* d
there exists data distribution 'D such that if m < 512g2, then with probability at least 1/8 over D we have that
err (A(()) 2 inf esr + JEF
With the above lemmas in place give the proof of Theorem E.1.
Proof of Theorem E.I. We start by applying Lemma E.2 with parameters Ey, 80, n = for r E Zzo such that
= 2" s 1/72 < 2
(44)
and s (2n)J. Notice that is positive integer since n S 1/7?, and, by hypothesis,
d 2 1ogz(2/?²).
d
2
(by Eq. (44))
(0gg(2))
logg (2/72)
1.
(as, by hypothesis, d d log, (2g7(2/)2)
The base class B ensured by Lemma E.2 satisfies [B] = (2m)*, (on)",s0 so
VC(B) < loge (l3
logg (2n)
d
log, (2n)
(by the choice of s)
logg (2n)
< d,
as desired.
Moreover, Lemma E.2 guarantees the existence of a (2,00, da Eo, mo, F,B) agnostic weak learner, denoted W, for the reference class F {+1)* for any mo [8lm(11B)/66)/e} For later use,
37

---

choose mo [8d In
which is a valid choice since
8 (n(22B/660)
[8 (n2n(22)))00 /60)
c
E
88s (2(()2
(as 8 2 1)
c
[ddn(4/(6072))
(as 8 = [d/log2 and, by choice, n Σ 1//²)
(2
(d(o(4/(
(as 2 1)
o
We claim that W is also (7, do, Eo, F, B) agnostic weak learner. Indeed, given any D' E A(Xx {+1]), as consists of all possible mappings from X to {+1}, we have that sup ((xy) (y.
fx))] 2 0. Thus, it holds that I vo sup (x ly f(x) 2 ysu (xxy) ly f(x)],
since 1/Vū 2 7, by Eq. (44).
Finally, since F is the set of all possible mappings from X' = [n s] to {=1}, we have that
VC(F) 8
2"
(by the choice of n and s)
logg (2r+1)
d
2"
r r++
d
x
(by Eq. (44))
72
On the other hand,
VC(F) 2
(2
d
(by Eq. (44))
2/
loga (2/72)
(as, by hypothesis, d/ logz (2/7²) 2 8)
2,
(as, by hypothesis, 7 2S1 1)
allowing us to apply Lemma E.4 and Lemma E.5, respectively, to obtain the thesis.
With the proof of Theorem E.1 done, we now prove Lemma E.2.
Proof of Lemma E.2. We start by considering [n] as our universe for a power of 2. Let (1()) be set of pairwise orthogonal vectors in (+1) 1 which can be chosen the of Hadamard matrix of size n x n.?
(n)
Let now D be probability distribution over [n], which can be seen as vector in [0, 1J" with E D, 1. Scaling (1), ...., (()) by 1/v/ obtain orthonormal basis, whereby
D
(45)
Vn
We assume be power of 2 this suffices ensure the existence of such Hadamard matrix.
38

---

Moreover, we have that
D:)²
D2
(by
1=1
|
v10
(by Eq. (45))
Vnl
vni 2
(D. 0 v00
where the last equality follows from (v(+) (0) being 0 for i + j and n for i = j. By averaging, the above implies that for any D E ([n]]) there exists i E [n]] such that (D, v(0))2 1/n, so that either (0)) 2 1/Vn or - (D,, o(0) 2 1/vn. Similarly, denoting by @ the entry-wise product, we have that for any y E {+1}", the vectors y C w(1), /i/n//n.....
@ v(m) //n form an orthonormal basis of R.. Thus, an analogous implies that for any E A(nl)) and y E {=1}" there exists i E [r]] such that either (D,y v( 2 1/vli or (D.y 2 (-u(9)) 1/vn. Overall, we can conclude that for
any D E A(n)) and any labeling y {+1)" there exists v E (r(()) ,..., v(n), -0(1)
(n))
such that
Ej-o ( 2g] = Σ Dz0joj
1=1
(D,y O1)
1
(46)
Vni
Consider the base class B: [n
- {11} consisting of the possible concatenations of vec- (1)),
tors in V = {u(1), ...., -(1), ..... -0 _ That is, B {(w(1) ...., w(+)) {=1]ms w(1),, ...., w(() VJ. We claim that for any D A[n s]) and y E [#1]"* there exists h E B such that Ey-Dlyghy] 2 1/v7. To see this, consider h (w(1), ...., w()) such that each w()
satisfies Σj 1)= 20 1- 2 1 iin
vn 2)=(t-1) Dj. There must exist such w(() as this
is trivially the case when Σ 2)=((-1)n41 Dj 0 and, otherwise, we have that
Dj
Pyyru 3-(-1)-
Dj
Σ
Ek=((-1)n+1 Dj
(=(1-1)-++1
-=(1- 1)++1
==(t-1)-++1
with (i= Dk)) Dz))) im (=(- being a probability distribution, so the existence of the desired (1) follows from Fq. (46).
So far, for any n integer power and s E N we have constructed a universe X' [n s] and base class B E {+1}² such that for any D E ( and f: X + {=1} there exists h E B such that
1
(a-D(h(x)f())) N Vn"
(47)
To conclude, we show the existence of reference class == {=1}* the set of all functions from X' to {+1}, as long mo > [8
VT. 80, Eo. mo. F, B) agnostic weak learner, for the
of
Concretely, we shall prove that there exists mapping W: (X' x { + {+1}* (from training sequences to classifiers), such that for all D' A(X x (+1)), when W provided a sample S ~ Dm we have that W(S) = h E B and with probability at least 1 - dg over S it holds that
E Exyyy (x(x)) 2
sup E( [f(x))] - Eg- feF
Vn
39

---

To this end, it suffices to show that for any D
sup ((x [f(x)) arg max [B (h [x)y]] 2
(48)
vn fer
hEB
and to let W(S) = arg max BEB E (xx)))s((((x))) To see why this is a (T 6v, Eu. mu, F, ()) agnostic weak learner for any mo 2 181(2111/k)) notice that, by Hoeffding's inequality, for any it holds by the choice of mo that
moË
Ps [x [[)xx()))))))) - F(x.))ss((()))) S 66//2 2 1 2exp
8
2 - 60/1B))
So, by the union bound, it holds with probability at least 6o over S Dmmo that for all
[(xxy)>D (hxx))))((((xy] (sxx))=s((((xx)) S E0/2.
(49)
and, thus,
(xx)))>((M())))) 2 B(x.)- - Eo/2
(by Eq. (49))
sup B (xx (x)x)] Eo/2
heB
sup R2 (x)) [x(y)) EO heB
(by Eq. (49))
sup E. (x.)) [f(x) EO. vn JEF
where last inequality follows as long as for any distribution D' E A(X x (+1}) there exists h E B satisfying Eq. (48).
To see why Eq. (49) holds let now DD' be a probability distribution over X x {+1). We then have that for any h: X {+1} that
E (xx.))~x((((())))
Σ
Mxxy D'(,,
(x))) Σ TEX
-((xx,11))
(50)
If D' 1) - D',z, 1) = 0 for all a E X, then Exx,y)/D'' [ = 0 for any / E (+1)*, so the claim holds for any h E B. If (z, 1) - (z -1 & 0 for some æ E X, we further write that
E (xx))) [h(x)y] Σ
h(x) sign (D' (æ. - (' 11) [D 1) D'
xEX
(D 1) D' D'x,, -1)1
Σ h(x) (D' (x, - (z, -1))
Exex D1,,, 1) - D' -1)1
WEX
ΣID'(z,)) - -)D(2, (zx-1))l.
(51)
FEX
where we recall that we define sign(0) indeed mapping from X' to [+1], and that [D' 1) D' 1))/ En D (z. 1) D' (z, 11) defines a probability distribution over X. Thus, by Eq. (47), there exists
We now notice that sign(D'
(D' (z. 1) D' (1) is
such that
(D' 1) (i
Σ sigu())) (x, D' - 1)) FEX
Exex D' -D'(s, Vn
Also, by Eq. (50), have that sign (Dgg(D'(xx11) - D'(xx, -1)) is maximizer of E lf (x)x) over f E F and is such that
E (xx)) (Dggn( D', -x)) Σ (D'(,, ('xx,-11))
xEx
sup Exx [f(x)y]
feF
40

---

Combining these two observations we conclude from Eq. (51) that there exists h E B such that
E(xx)))D(((((x)) 2 sup ((x,))D-(f(xxx))
vn FEF
as claimed, which combined with the case where (z 1) - D' (z, -1) 0 for all æ E A' concludes the proof.
With the proof of Lemma E.2 done we now give the proof of Lemma E.3, for completeness. To this end we need the following two technical lemmas.
Lemma E.6 (Shalev-Shwartz and Ben-David [2014], page 422, Lemma B.1). Let Z be random variable that takes values [0, 1]. Assume that E|Z] μ.. Then, for any a E (0, 1),
# (1-a)
P > 1 a)
a
This also implies that for every a E (0, 1),
P a] >
Lemma E.7 (Shalev-Shwarte Shwartz and Ben-David [2014], page 428, Lemma B.11). Let X a (m. p) binomial variable, i.e., X i== Z, where Z; {0, } are i.dd. with E|Z,] p. and assume that p - <2/ Then,
mc²
P m/2
1- 1 exp
1 6²
We now give the proof of Lemma E.4.
Proof of Lemma E.4. Consider sequence T1, .1,..., Fd which is shattered by the function class F, will the following, for convenience consider, the enumeration of these points as the universe [d]. i.e., [d] v,. Furthermore, let [+1]4, and for each such consider a distribution D, on [d] x {+1}, where y in the following is strictly less than 1/(d - 1),
(1/2 c)p if y b,, x E [d (d-1) (1/2 - c)p if = bb, [d - -]
Do(x,y) v)
1 1 y
that is any point i in [d is chosen with probability p and with probability 1/2 + it gets the same label as b; or with probability 1/2 e gets the label -b. We can see drawing sample from the above distribution as follows: We first draw random point X from [d], where X is equal to for [d - 1] with probability p and is equal with probability (d - 1)p, (for later convince let this distribution over [d] be denoted by D). Furthermore, draw uniform random variable U, in [o, 1] and let
d-1
Y d = d} + Σ e i)( dfU s 1/2++bb,} -12)
Ø=1
fx(X, U).
We notice the loss of any f is given by
(D.()) Σ
i=1 (E(+1)
Σ (1/2+
c)- d(f(i) # -b,)
+ (1 (d 1)-) d(f(d) #1}.
(52)
41

---

Thus, we see that hypothesis in F that evaluates to b on [d - 1] and 1 on will have the smallest possible loss (notice that such hypothesis F exists since the hypothesis class shatters 2..... ,z)). being equal to p(d- - 1)(1/2 c), thus let fs be such a hypothesis in F, for given b E {+1]% minimizing the loss function LD. We will set
(d-1)(1/2-c) such that the loss of fa is equal
L. We notice that this implies that we have to set small enough such that p < 1/(d 1).
that we have to have that < L/(1/2 c) 1. this end, we will set V 64mL. which
satisfies the condition < 1/2 since m 2 d/(L(1/2 (.))), implying that L/(1/2 c)
equivalent to < 1/2 - c 1/2 V B4mL. since m 2 d/(L(1/2 1)) we have that LVV 32 > L, thus for these values of c, and m 2 -
1/2 V GimL 2
we have that p < 1/(d ((d--)). 1). Now using the expression of Eq. (52) we get that the excess risk of any f to fo is lower bounded as follows,
d-1
(f. - CDb(f) 2 2pc
Σ E d(f(i)
this also implies that given a sample S (X1, Yi),..., (Xm: y,) drawn from D, we have for any learning algorithm A that
d-1
(D(()))) - LD, 2 2pc Σ E d(A(()))) + MO)
(53)
We will now show that
Eb-(+
2pe ES
E d(A(s)()) + {b)))
d(A(S)()+()0))
2ped
(54)
25
We notice that since 2pc for < 2ped an application Lemma E.6 gives us that
Ei1 E ({) + fb(1)} < 2ped, and is non negative, we have that
d-1
Eb-
PSWDn
2pc
((A(S)(1) fb(1) 2
iml
2pc E E d(A(S)()) + fb(1)}
PS
2ped
2ped
ES
2pc
d(A(S)(1) # f000)
(2ped)
a 2ped
25
2ped"
where we in the last inequality have used the lower bound of Eq. (54), thus setting a 2ped/50 we get that
Eb-(+13 [PSSRD [Co, (A(()) - LD. (fb) 2 2ped/50]]
d-1
> Eb-(t
PSNDT
2pc
Σ E d(((()(()) # sn(1)) 2 2pcd/50
im1
1
1
2
25
50
1
50
implying that there exists E [=1]d such that
1
PSWDT (A(S)) LD. 2 2pcd /0] 2
50"
42

---

Now using that = (d-1)(1/2-c}
1
c V 6dmL
we get that
L
d
ped
(d 1)(1/2 -
V
64mL
d
dL
16n'
where the first incquality follows from 2 2 so 1/(d - 1) 2 1/d and 1/(1/2 - c) 2 2. Thus, we conclude that there exists E [=1]d such that
PS-DI (o.(A(S)) LDD (bb) 2
2
dL
1
z
50
16n
50'
claimed.
Thus, we now show Eq. (54) that is
dd((()()) + m0(0)
2ped
+=1dd
ESSID
2pc
25
We now use that Din has the same distribution
S = ((X1, Y1). ...,, (Xms m))
distribution
((X1, (Xx, U.))...., (Xm. (Xm, U,))) = (X, (X,
where X ~ D and U ~ [0, 1]"h. and we use the above entrywise notation for (X, ls (X(, U)). Using the above and Eq. (53) we have that
DD (CD, LDD (f6)] d-1
2pc EX-Dm Bu-10.111 IE d d(A((,, 4(X, ()))(() + f60H]
and taking expectation over b ~ { 1 we get that
Eb-(11)e (113d
ESSDy [CD, (A(S)) - CD. (fb)]]
(55)
d-1
2 2pc
Ex BBonsipa [B (E (AA((
# S(OH]]
1=1
d-1
2pc
Σ
EX~Dm
ED (-1)e-1 [Bi-(=1) Eu--oo'' JE d d(A((X, (X,, U))) # b.lll]],
where use b, denote the hhh entry of b and b the remaining entries. We now bound each term in this sum.
To that end we now consider any realization of X
and b = b... Furthermore let the indexes where x equal to i.
J4 = "fi....,Jf such that jí <... < Jt and I p............................. Fzz
We recall that (I, & (x, U)) = ((x1, bor be....bell (21, UI))... (xm, beo,...
(Ims U ))), ((z L b......... 3 U U)))...... (Ims b (2 U be the remaining entries of (x, (b, U)). In words, (r, lz U)), are and (x, bb(a, U)) are the remaining en- tries of (x, (2, U)) that are not equal to i. By the definition of ((b.........bbb)) we have that
and let (x,4n (x, U)),,
and (xx (zx
the entries of (x, (x, U)) that are has xy equal
1/2) l'U n b,) for t 1, only function of U and b; Furthermore by the definition of bor...., du) (x, U)-J, e (U_.)) is only function of U_J. (the coordinates of U not with index in J and b_g. Using these observa-
(b......b........
(z U,;) 2(E d {U, I 1/2 }b.}
so
43

---

tion we get that
[E d(A((z, be (t))(i) + b,}l
Σ Pu-[a,1]m [[ (z. U)) = n) E ddfA((.,)))( + #b,}
(E(+1]"
E Pu- 2e (e b,) ys.l Pu- E dd( (U (U,,)} }} yy-.
ME(#1)"
E Ed(A((<, ()) # bi}
E
Pu-Nu.J 1411 1% (U-J.) = v-
V. ((
Σ
Pu-p.1uu
b,) (" (U, yn.l ((,(((,,))0) + b.j.
(56)
UA E4
We notice that the first sum in the above expression is independent of b; thus we focus on the sum over yJ,, To this end consider any y-J, we then have when taking expectation of b, over the second sum in the above that
[b
Σ E(=1)4
Po-onn (',, b.) vnll e d(A((z, x))(1) + bb}
1
Σ
Pomoojua (C(,,, 1) v..] d(A((<, v))(( 11
2
1
Σ
Po (U,,, = dd(A((>,))) (1) 1}
2
94 E
We have by independence of U f1: ...... 1 that
Pu~1o.1j1 [L,,, 1) v., II
Pu , [0.1] [C(U, 1) =vi]
1=1
c1/ Ed(Uy -1] 1) (1/2 - c) Ed(usp --1)
Σt Eddye (1/2 c) Ed(,
= (1/2 + c)
and similarly we have that
Pu-jo.nua [e((U.. -1) = y..1
Pu [0.1]
[(U -1) = Uμ
A=1
(1/2 c) Ed( (1/2 + c) Edlu,==11)
1=1
Eim Ed(v, =1 (1/2 +c) Ed Ed(;
(1/2 c)
implying that if - Di=1 d(v;; = 1} > Σ E dl =11 equivalently sign ( 1i;) = 1
(we take (0 = 1) then
Pu~|o.11141 [L, 1) = y,.} > PP Po ((U,,,,1) yv.]
and if Σi= dly 1) Σt= E d'y -1} equivalently sign sign(E== My;)) -1 then
P Pu jo.1j4 [e' 1) = yu. < IP Pu-oon1 [U,, -1) = yu.l
44

---

whereby we conclude that
(b)
Σ
Pu- = y E(A(((E))) bb}
Lu,, El=1po
Σ
Po-om1ii (U,,, 1) = 1) w.] ddA((<, 8))(1) #
2
y4, E(11)14
+ 2
Σ
P Pu-1o.1 (U, [e( -1) un. E (( + -13
y4, E(=1)iP1
2
Σ
Po-oaajua ("(U,, 1) vn.] d sign Σ Vit
#1}
11:E(+))144
N4;
#
+ 2
Σ
Pu- (U,, Pu -1) y..1 E d sign
Σ
# --1
VJ, 11,E(+1)iad
1=1
k Σuu²
(+11
Σ
P Pu~ [e(U,,, b,) vv,1 d sign
# b
which furthermore by Eq. (56) implies that
Eb (b.-(11) [E d {A((z, beb..........bbaa (z) Ui)) # b.Hl
}
Eb.=f=11
Σ
Po-1o.111 (e vv.l E d sign
Σ Uo
* bi
99., 11#11111
k bi) # *bi }1
= =bb,
E EU
E dl sign
Σ ((,,,
where the sum over y-J, becomes one since E sign and thus we can take it out of the over y-J;
EEiz M3:)) * b; does not depend on y-J.
Now in the case that [J/] 0 we have that sign El l'U ((U,,bb)) = sign(0) 1 and thus we
have the above is 1/2. Now in the case that |JA] > we have that
de
Eb E 1o-aaani
E d sign
Σ
(U, # b;
( f -1,, + (0+11)) -1)
1 Pu-jo.juu sign Σ
El ( (UU 11) # 1
+ P UU110.11141 sign
-D)
2
1=1
1=1
By the definition of (" 5/. by) = 2(E d(U;; s 1/2 + cb,} - 1/2) we have that the event sign - -1) #
happens when k/2 < [tt: ((U);,-1) = 17/, where the less than equal to is due us taking (0) 1. We notice that [[t (U, -1) = 1}| has binomial distribution with trials and success probability 1/2 c. Thus, we have by Lemma E.6
P UuJjoaj141 sign Σ e' CUU -1) +-1
PUM1o1n1 1 k/2
1 [ 11-Viiexp(-Mu112/((----0-3
2
1
(1- V11112009/11(200))
2
45

---

where the last inequality follows from exp(x) 2 1+ x for all x E R. Which furthermore implies that
Ebr Bu-1o.1144
E d sign Σ e' ((U ((),,,,))
+ bi
4 vIJi((2)) - (2c)?)),
which also holds for [J:] = 0 since P (o- sign E 1=1 (U // -1)) * -1] = 1/2 in this case.
Thus, by the above we showed that for any realization b-, of b and a of X we have that
I ( [R [E (A((X, (X,, (1)) + b,
Eb (Lu) [E d (A((z, bi............b ba) (z. ())) # b.Hl
(1
(2c)²)).
Now using this and plugging into Eq. (55) we get the following lower bounded
[n-(+ [EswDy [LDp (A(S)) Cp,(ff)] (fb)]
(57)
2pe
Ex (1-V1J](200001
where we recall that J. is the indexes of X that are equal to i. Now using that v is a concave function and Jensen's 's inequality have that
E Ex-Dm 1 (1 - V13.12209/1--2260)
(2c)²
2 4
E ExwDm [J
(1 - (2c)2)
(2c)2 .m.p
4 (1 -(2c)2)
where the last inequality follows from that [J.
Σド= f= E d (X, i) and PX [ i|
for i E [d - 1], and E [m]. Recalling that we had (d-1)(1/~o}- and c = V 64mb which by
d
d ky implies S v1/64, we make the following calculations on the right hand side of
the above to get that
d
(2c)² m 22
m (d - 1)(1/2 c)
64mL
1
d
16 (d
(1(12-cc)
1 1
8 1/2
VI/64
where the last inequality follows from d 2 so d/(d - 1) < 2 and e I /1/64, furthermore since
we have that 1/(1 (2e)²) S I-4704 implying that
(2c)² m P
1
1
2 v 3
- (2c)2
8 1/2 V1/64
1 1- -//64
so that
Ex~Dm H 11- -
( (1-V2/3) 2 1/25, 4
1
(2c))))
2
implying by Eq. (57) that we have shown that
Eb-(+1) [ES-DD [LD, (A(S)) LD, (f6)]] 2 2ped
25
which was the claim of Eq. (54), concluding the proof of Lemma E.4,
46

---

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 merits of the paper is stated in the abstract and introduction.
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 in 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.
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 make it clear that we solve up to log factor the statistical problem of agnostic boosting, but that do solve the computational problem.
Guidelines:
The answer NA means that the paper has no 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 separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect 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 the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
47

---

The results are stated with the assumptions and the proofs are provided in the appendix.
Justification:
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 proof's 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 be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
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)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, 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 novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make 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 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 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
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe 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
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
48

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
Stapii//uides//ooeeeeee wew.ommsssioooooiiiooooooooooooe Ponnc)lly) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /Codeeeooiissseeeeeee
/ //iips.coo. wttpccccpppccceeee.cecccccccccct sute cetpuummmsssoonnii wswinnolll onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how 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. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information 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 (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
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, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support 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, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
49

---

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 enrors 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 range (e.g. negative error 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 to reproduce the experiments?
Question:
Answer: [NA]
Justification:
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 of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: : http///eerrpp..eeee cc
Answer: [Yes]
Justification:
We do any ethical issues with the research conducted in this paper.
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 cireumstances 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:
We do any direct societal impact of the work performed in this paper.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or 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.
The conference expects that many papers will be foundational research and not tied to 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 improvement in the quality of generative models could be used to
50

---

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 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
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:
Guidelines:
The answer NA means that the paper poses no 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 to 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 challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators 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:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.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 sepporswithood thcode 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 has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
51

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing 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:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information 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 to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
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 equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on 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 we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
52

---

Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https: http:/uuiip..ce//eeeeeeeeeeeeeee /0tpa////.//oooaaeeraa/////////0 for what should or should not be described.
53


Reviews:
[{"review_id": "euMf32YFD3", "reviewer": "Reviewer_aHg7", "summary": "This paper introduces a new boosting algorithm in the agnostic setting where labels are arbitrary, with no realizability assumption. Their method reduces agnostic boosting to the realizable case through a margin‑based filtering step that selects high‑quality hypotheses, achieving near-optimal sample complexity (up to logarithmic factors). This paper focuses only on statistical and information-theoretic\naspects of the problem, without constructing a computationally efficient algorithm.", "questions": "1. The proposed algorithm is acknowledged to be computationally inefficient. To what extent can the current theoretical results be extended to efficient algorithms without significant degradation in sample complexity?\n2. The lower bound (Theorem 1.2) includes an extra logarithmic factor. Is this believed to be an artifact of the proof, or is there any evidence that it reflects an actual complexity barrier?\n3. I suggest that the authors put a table summarizing the existing works and the proposed method. The table can include sample complexity, whether it is computationally efficient, and any other notable things, so that the readers can more easily understand the current status of this problem.\n4. What is $D_t^{m_0}$ in Algorithm 1? It is not clearly defined.", "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": "**Strengths**\n\n- Boosting in the agnostic setting is a problem known to be challenging. The proposed boosting algorithm, using the technique from a recent work to reduce the agnostic problem to the realizable one, is a fresh approach, offering tighter sample complexity guarantees in the agnostic setting.\n- The authors adopt a highly general notion of agnostic weak learners that encompasses many variants from prior literature, providing a unifying framework and fair comparison.\n- This paper also proves a lower bound on the problem, demonstrating that the proposed method achieves the optimal sample complexity bound up to logarithmic factors.\n- The paper is clearly written with enough information about the background and existing results. The mathematical notations are a bit dense, but the authors did a good job explaining the intuitions.\n\n**Weakness**\n- The proposed algorithm is not computationally efficient due to the exhaustive relabeling step and enumeration over exponentially many hypotheses. While the authors acknowledge this, some discussion on possible heuristics or approximations would be helpful.\n- While the bounds are tight asymptotically, the constants hidden in the big-O notation may be large due to the fat-shattering terms. There is no discussion on this.", "was_revised": true, "final_justification": "The authors addressed most of my questions. I will keep my original positive rating.", "rebuttal": "We thank the reviewer for taking the time to read our paper and provide feedback.\n\nWe address the reviewer's comments in order:\n\n> The proposed algorithm is acknowledged to be computationally inefficient. To what extent can the current theoretical results be extended to efficient algorithms without significant degradation in sample complexity?\n\n**[TAG1]** (just a reference for other reviewers)\n\n**Answer:** (This is also addressing the first point under the weakness section of the review)\nWe thank the reviewer for raising this important point.\nCurrently, it is unclear to us how to extend the algorithm to be computationally efficient while preserving the same theoretical guarantees on the sample complexity.\nHowever, our algorithm and analysis do suggest several heuristic directions worth exploring.\n\nOne possible approach is to divide the training data into smaller subsets and run AdaBoost separately on each subset.\nIf the resulting classifier achieves good margins on its respective subset, one could then iteratively merge it with it's neighboring subset (which also has good margins), re-run AdaBoost on this merged subset, and continue this procedure until all the sets are merged or removed.\nHowever, this method does not come with any guarantees and may not work reliably in general.\n\nAnother potential heuristic is to run AdaBoost on the full dataset for a fixed number of iterations, then identify the points with the most negative margins and flip their label.\nAdaBoost could then be trained again on this altered data set.\nThis process can then be repeated for a fixed number of rounds.\nWhile intuitive, this approach also lacks a formal guarantees.\n\nFinally, one might consider a modification of Algorithm 2 in which lines 3–7 are replaced by a parametrized re-labeling strategy, where the user specifies the number of re-labelings to consider.\nThis could make the algorithm more scalable in practice.\nHowever, to make such an approach effective, one would need a reliable mechanism for selecting promising re-labelings, a component we currently do not have.\nAs such, this alternative too would lack theoretical guarantees.\n\nIn summary, while several heuristics can be inspired by our algorithm, their sample complexity remain open questions.\nWe hope our work provides a foundation for further research in this direction.\n\n\n> While the bounds are tight asymptotically, the constants hidden in the big-O notation may be large due to the fat-shattering terms. There is no discussion on this.\n\n**Answer:**\nWe thank the reviewer.\nThis is a good point.\nWe will add a discussion of this nuance to the text making it clear that the constants in the O-notation are large and that we did not try to optimize for them.\n\n\n> The lower bound (Theorem 1.2) includes an extra logarithmic factor. Is this believed to be an artifact of the proof, or is there any evidence that it reflects an actual complexity barrier?\n\n**Answer:**\nWe strongly believe this is an artifact of the proof.\nThe reasoning is that one would expect a tight bound to hold for all values of $\\mathrm{err}_{\\mathcal{D}}(f^{\\star})$, including 0 (the realizable case).\nHowever, adapting our Lemma E.2 to the realizable setting would still yield that $\\mathcal{F}$ has VC-dimension $\\Theta(\\frac{d}{\\ln(1/\\delta) \\gamma^{2}})$, so one could obtain (e.g., from Theorem 6.8 in [1]) the lower bound of $\\Omega\\left(\\frac{d}{\\ln(1/\\delta) \\gamma^{2}\\varepsilon} + \\frac{\\ln(1/\\delta)}{\\varepsilon}\\right)$ on the sample complexity of realizable boosting.\nIf this was tight, it would contradict the known optimal bound of $\\Theta\\left(\\frac{d}{\\gamma^{2}\\varepsilon} + \\frac{\\ln(1/\\delta)}{\\varepsilon}\\right)$ (no extra logarithmic factor) by [2].\n\n\n\n> I suggest that the authors put a table summarizing the existing works and the proposed method. The table can include sample complexity, whether it is computationally efficient, and any other notable things, so that the readers can more easily understand the current status of this problem.\n\n**Answer:**\nWe see the point in the reviewer's suggestion.\nIn fact, we considered adding such a table but decided against it as we thought it could be misleading with regard to the different definitions of weak learner.\nGiven that the situation is, rigorously, quite nuanced, we preferred to keep only explicit and detailed discussions in Section 1.1 (Related Works) and, more thoroughly, in Appendix A.\n\nNonetheless, as you and Reviewer tVkc have suggested this, if you maintain your preference after taking our reply into account, we would not object to adding such a table (accompanied by a clear remark of its limitations).\n\n\n> What is $\\mathbf{D}_{t}^{m_{0}}$ in Algorithm 1? It is not clearly defined\n\n**Answer:**\nWe thank the reviewer for pointing this out.\nWe indeed overlooked this notation in our definitions.\nWe'll add to Section 2 that given a distribution $\\mathcal{D}$ and an integer $m$, sampling according to $\\mathcal{D}^m$ means taking $m$ i.i.d. samples from $\\mathcal{D}$.\nIn this specific case $m_0$ is the number of samples required by the weak learner to produce a good hypothesis (cf. Definition 1.1) and $\\mathcal{D}_t$ is the $t^\\text{th}$ distribution generated by Algorithm 1.\n\n\n[1] Understanding Machine Learning: From Theory to Algorithms. Shai Shalev-Shwartz and Shai Ben-David. 2014.\n\n[2] Optimal Weak to Strong Learning. Kasper Green Larsen and Martin Ritzert. 2022."}, {"review_id": "nahTuGKoxY", "reviewer": "Reviewer_tFLU", "summary": "The paper introduces a novel agnostic boosting algorithm that significantly improves sample complexity under general assumptions. The proposed method reduces the problem to the realizable case and employs a margin-based filtering step to select high-quality hypotheses. Additionally, the paper establishes a lower bound on the sample complexity of agnostic boosting, matching the upper bound up to logarithmic factors.", "questions": "see my comments above.", "limitations": "no", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:  \n(1) The paper presents a new agnostic boosting algorithm that offers substantial improvements in sample complexity compared to previous works, which is a novel contribution to the community.\n\n(2) The authors provide thorough and solid theoretical analysis, including a lower bound on the sample complexity that aligns closely with the upper bound.\n\n(3) The approach is based on very general assumptions, making it broadly applicable across different scenarios, which is indeed an advantage of the paper.\n\n(4) The paper includes detailed proofs and theoretical justifications for the proposed algorithm and its properties, which facilitates people's understanding of the proposed method.\n\n**Weaknesses**:  \n(1) While the algorithm is statistically near-optimal, I am not sure about its computationally efficiency, which may limit its practical applicability.\n\n(2) I understand this paper is mainly focused on the theory. Although not always required, it might be a bit beneficial if the paper also provides empirical results or experiments to validate the theoretical findings and demonstrate the algorithm's performance in practice. For example, some other boosting-related theoretical papers also have some (though not too many) experiments included in their papers (see references 1-3 from the list below).\n\n**Reference**:   \n[1] Ghai, et al. \"Sample-Efficient Agnostic Boosting.\" arXiv preprint arXiv:2410.23632 (2024).   \n[2] Liu, et al. \"An analysis of boosted linear classifiers on noisy data with applications to multiple-instance learning.\" 2017 IEEE International Conference on Data Mining (ICDM). IEEE, 2017.   \n[3] Bootkrajang, et al. \"Boosting in the presence of label noise.\" arXiv preprint arXiv:1309.6818 (2013).", "was_revised": true, "final_justification": "Thanks for the efforts in rebuttal. I remain my support to this paper :)", "rebuttal": "We thank the reviewer for taking the time to read our paper and provide feedback.\n\nWe address the reviewers questions/comments below:\n\n> While the algorithm is statistically near-optimal, I am not sure about its computationally efficiency, which may limit its practical applicability.\n\n**Answer:**\nWe thank the reviewer for raising this important point.\nIndeed, our primary focus is not on computational efficiency, but rather on the statistical aspects of agnostic boosting.\nOur main contribution is to demonstrate that it is possible to achieve near-optimal sample complexity even under the very general assumption of black-box access to a weak learner, without requiring knowledge of the reference class or any additional structural assumptions on the problem.\nThis level of generality is not only theoretically appealing: in typical boosting applications, one runs algorithms such as AdaBoost with a fixed base class (e.g., decision stumps), without knowing which reference class is effectively being weak learned by the combination of base learner and data.\nOur results show that strong statistical guarantees are achievable even in this practically realistic setting, where the reference class remains implicit.\n\nWhile we acknowledge that the resulting algorithm may not yet be computationally efficient or practical in all settings, we view our work as an important theoretical step that clarifies what is statistically achievable in principle.\nWe hope it will inspire further research aimed at developing computationally efficient instantiations or approximations guided by these insights.\n\n\n> I understand this paper is mainly focused on the theory. Although not always required, it might be a bit beneficial if the paper also provides empirical results or experiments to validate the theoretical findings and demonstrate the algorithm's performance in practice. For example, some other boosting-related theoretical papers also have some (though not too many) experiments included in their papers (see references 1-3 from the list below).\n\n**Answer:**\nWe appreciate the reviewer’s thoughtful suggestion regarding the inclusion of empirical results.\nHowever, our paper is intentionally focused on the theoretical aspects of boosting, specifically on the sample complexity of the problem.\nWhile we acknowledge that certain heuristics could be derived from our theoretical insights (see answer to **Reviewer aHg7** (search for `[TAG1]`)), we currently lack a rigorous understanding of their behavior.\nAs such, incorporating empirical results at this stage risks being ad hoc and could distract from the rigorous and theoretical nature of our contribution.\n\nWe agree that a meaningful empirical evaluation is, in principle, valuable and feasible.\nHowever, designing such experiments carefully, especially in a way that faithfully reflects the theoretical framework and explores the appropriate range of algorithmic instantiations, requires a non-trivial amount of time and effort.\nGiven the scope and time constraints of the rebuttal phase, we believe it would not be appropriate to rush this process or include preliminary experiments that may not do justice to the theoretical foundation we aim to establish.\n\nWe hope the reviewer will understand our decision to prioritize a focused theoretical exposition, and see potential for future work to build on our results with a careful experimental study."}, {"review_id": "eTKZdMZ7vb", "reviewer": "Reviewer_jF1w", "summary": "This paper presents a new agnostic boosting method with comprehensive theoretical analysis. The new algorithm can convert any non-trivial agnostic weak learner into a strong learner. The core contributions are (1) the proposed algorithm achieves a significantly improved sample complexity upper bound compared to prior work under very general assumptions. (2) the paper establishes a nearly matching lower bound on the sample complexity for agnostic boosting, effectively settling the statistical complexity of the problem up to logarithmic factors.", "questions": "1. Do you have any experiments, including synthetic ones, to show the proposed modified Adaboost in Algorithm 1 works in practice?\n\n2. Can you further discuss how this work relates to / extends Hopkins et al. (2024) (in line 195)?\n\n3. As one limitation is the algorithm's computational inefficiency steming from iterating over all possible re-labelings. Are there any foreseeable approaches or heuristics to make this algorithm (or a similar one) computationally feasible while substantially preserving its strong statistical guarantees?", "limitations": "yes", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. Establishes nearly tight upper and lower bounds on the sample complexity of agnostic weak-to-strong learning, which advances the fundamental understanding of boosting in the challenging agnostic setting\n2. The proposed algorithm and its analysis operate under remarkably mild and general assumptions\n\nWeakness:\n1. The proposed algorithm is computationally inefficient and could be hard to implement in practice.\n2. There is a lack of experiments to demonstrate the practice usefulness of this method.", "was_revised": true, "final_justification": "I have read the author rebuttal and decided to keep the original score.", "rebuttal": "We thank the reviewer for taking the time to read our paper and provide feedback.\n\nWe address the reviewers questions in order:\n> There is a lack of experiments to demonstrate the practice usefulness of this method.\n\nand\n\n> Do you have any experiments, including synthetic ones, to show the proposed modified AdaBoost in Algorithm 1 works in practice?\n\n**Answer:**\nWe thank the reviewer for the suggestion.\nAs Algorithm 1 was just a subroutine of our main algorithm, we did not consider evaluating it empirically.\nMoreover, Algorithm 1 closely resembles AdaBoost as the minor changes were meant only to ensure desirable theoretical properties and ease our analysis.\nWe believe this similarity would translate into good empirical performance, though a thorough experimental investigation is an interesting direction for future work.\n\n\n> Can you further discuss how this work relates to / extends Hopkins et al. (2024) (in line 195)?\n\n**Answer:**\nThe seminal work of Hopkins et al. (2024) develops methods for several learning settings, including malicious noise, semi private-learning, and partial learning.\nOur work focuses on the agnostic boosting setting, which compared to their baseline algorithm for agnostic learning, does not assume access to the reference class $\\mathcal{F}$ (or the base class $\\mathcal{B}$), but  merely access to a weak learner that can learn from the base class $\\mathcal{B}$.\nThe agnostic algorithm of Hopkins et al. generates all possible labellings that the reference class $\\mathcal{F}$ could have produced, which as **Reviewer tVkc** also pointed out (see the reply to **Reviewer tVkc** for further details) would yield a bag in the first step ($\\mathcal{B}\\_{1}$) of size would be $O((d'/m)^{d'})$.\nFrom this, one could use the guarantee that $\\mathcal{B}\\_{1}$ contains a good hypothesis together with a Hoeffding and union bound to conclude that the empirical risk minimizer in $\\mathcal{B}\\_1$, $v\\_g$, has error $\\mathcal{L}\\_{\\mathcal{D}}(v\\_{g}) = \\mathrm{err}\\_{\\mathcal{D}}(f^{\\star}) + O\\left(\\sqrt{\\frac{d'\\ln(m/d') + \\ln(\\delta)}{m}}\\right) + \\tilde{O}\\left(\\frac{d}{\\gamma^2 m} + \\frac{\\ln(1/\\delta)}{n}\\right)$.\nYet, as we do not assume access to a way to generate all possible labellings of the training set by $\\mathcal{F}$---in fact, we don't assume any access to $\\mathcal{F}$---we instead generate all possible labellings of the training data.\nAn alternative we also considered was to take all possible subsets of the training set, but that would lead to the same number of runs, but with a smaller effective sample size.\nHopkins et al. also consider the approach of calling the realizable learning algorithm on all the training subsets.\nFor instance, in their Theorem 54 for partial concept classes, where the upper bound on the sample complexity is $O\\left(\\frac{n(\\Theta(\\varepsilon), \\Theta(\\delta)) + \\ln(1/\\delta)}{\\varepsilon^{2}}\\right)$ (omitting $\\ln(1/\\delta)$), where $n(\\varepsilon, \\delta)$ is the sample complexity of learning the partial concept class $\\mathcal{F}$.\nThe best known bound for learning partial classes is $\\tilde{O}(d/\\varepsilon)$ ([3]) which yields a bound of order $\\tilde{O}\\left(\\frac{d}{\\varepsilon^{3}}\\right)$.\nThe strategy of obtaining a learner by running the realizable learner on all subsets and picking the best one is also used in recent work by [4] in the multiclass agnostic setting, which yields a sample complexity of $O(1/\\varepsilon^{3})$ in terms of the dependency of $\\varepsilon$ (cf. Corollary 4.3).\n\n\n> The proposed algorithm is computationally inefficient and could be hard to implement in practice.\n\nand\n\n> As one limitation is the algorithm's computational inefficiency steming from iterating over all possible re-labelings. Are there any foreseeable approaches or heuristics to make this algorithm (or a similar one) computationally feasible while substantially preserving its strong statistical guarantees?\n\n**Answer:**\nWe thank the reviewer for raising this important point.\nCurrently, it is unclear to us how to extend the algorithm to be computationally efficient while preserving the same theoretical guarantees on the sample complexity.\nHowever, our algorithm and analysis do suggest several heuristic directions worth exploring.\n\nOne possible approach is to divide the training data into smaller subsets and run AdaBoost separately on each subset.\nIf the resulting classifier achieves good margins on its respective subset, one could then iteratively merge it with it's neighboring subset (which also has good margins), re-run AdaBoost on this merged subset, and continue this procedure until all the sets are merged or removed.\nHowever, this method does not come with any guarantees and may not work reliably in general.\n\nAnother potential heuristic is to run AdaBoost on the full dataset for a fixed number of iterations, then identify the points with the most negative margins and flip their label.\nAdaBoost could then be trained again on this altered data set.\nThis process can then be repeated for a fixed number of rounds.\nWhile intuitive, this approach also lacks a formal guarantees.\n\nFinally, one might consider a modification of Algorithm 2 in which lines 3–7 are replaced by a parametrized re-labeling strategy, where the user specifies the number of re-labelings to consider.\nThis could make the algorithm more scalable in practice.\nHowever, to make such an approach effective, one would need a reliable mechanism for selecting promising re-labelings, a component we currently do not have.\nAs such, this alternative too would lack theoretical guarantees.\n\nIn summary, while several heuristics can be inspired by our algorithm, their sample complexity remain open questions.\nWe hope our work provides a foundation for further research in this direction.\n\n\n[3] Optimal PAC Bounds Without Uniform Convergence Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, Nikita Zhivotovskiy 2023\n\n[4] Representation Preserving Multiclass Agnostic to Realizable Reduction Steve Hanneke, Qinglin Meng, Amirreza Shaeiri 2025"}, {"review_id": "PxaDi4Png7", "reviewer": "Reviewer_tVkc", "summary": "This paper revisits the classic problem of agnostic boosting. Leveraging recent techniques by Hopkins et al. [2024] , the authors propose a new agnostic boosting algorithm which, under some general assumptions, improves on the sample complexity of existing algorithms. Finally, the authors complement their upper bound with a near matching lower bound.", "questions": "In line 270, the authors justify the need for the filtering step by arguing that the size of $B_1$ is exponential in the sample size. However, instead of taking *all* possible labels of the training sample, it seems to me that one can just loop over all possible behaviors of the class $F$ on $x_1, ..., x_m$. If $F$ has finite VC, $B_1$ now has size polynomial in $m$ (compared to exponential). It would be great if the authors could comment on this and what sort of upper bounds this approach would yield.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths: \n- This paper is extremely well-written and organized. The authors do a great job at explaining their algorithm and providing the right balance between intuition and technical details. \n- The results seem novel and provide a clear contribution to the literature on agnostic boosting. To the best of my knowledge, this is the first time that the \"all possible labelings\" approach of Hopkins et al. [2024] has been used for agnostic boosting. \n\nWeaknesses: I don't have much to say beyond a few presentational choices. \n\n- The Theorem statements in the introduction are a bit dense. I think it would be better to replace these with informal Theorem statements that capture only the point that is trying to be made, perhaps by dropping some of the quantifiers. \n- The majority of the main text is dedicated to proving the upper bound in Theorem 1.3. However, in the introduction, Theorem 1.2 is presented before Theorem 1.3. I think it would be better to swap the order of these two Theorems and place more emphasis on Theorem 1.3. Or, I think it would be beneficial to include more intuition about Theorem 1.2 in the main text. \n- As written, it is a bit difficult to contextualize the results of this paper with existing results in agnostic boosting. The authors attempt to do this in Section 1.1. I think it might be nice to include a table that compares your upper/lower bounds with existing results when the assumptions and weak learning definitions line up.", "was_revised": true, "final_justification": "I maintain my positive score as the authors have adequately answered my questions.", "rebuttal": "We thank the reviewer for taking the time to read our work carefully.\n\nWe appreciate the reviewers feedback on the presentation (Weaknesses section of the review), we address the comments in order.\n\n> The Theorem statements in the introduction are a bit dense. I think it would be better to replace these with informal Theorem statements that capture only the point that is trying to be made, perhaps by dropping some of the quantifiers.\n\n**Answer:** We will revisit our formulation to try to improve the clarity.\n\n> The majority of the main text is dedicated to proving the upper bound in Theorem 1.3. However, in the introduction, Theorem 1.2 is presented before Theorem 1.3. I think it would be better to swap the order of these two Theorems and place more emphasis on Theorem 1.3. Or, I think it would be beneficial to include more intuition about Theorem 1.2 in the main text.\n\n**Answer:**\nWe actually switched the order of the two theorems.\nThe idea was to have our Theorem 1.2 (sample complexity lower bound) immediately after the definition of agnostic weak learner since the main challenge of proving lower bounds in weak learning is to construct the weak learner itself.\nSo, stating the lower bound right after the definition felt natural to us.\nHowever, with your feedback we will reconsider this decision.\n\n> As written, it is a bit difficult to contextualize the results of this paper with existing results in agnostic boosting. The authors attempt to do this in Section 1.1. I think it might be nice to include a table that compares your upper/lower bounds with existing results when the assumptions and weak learning definitions line up.\n\n**Answer:**\nThe addition of a table summarizing the existing results was also suggested by **Reviewer aHg7**.\nAs mentioned there, we deliberately avoided it to highlight the nuances that arise if one is fully rigorous when comparing the works.\nThe goal was to sidestep even slight misinterpretations by keeping only explicit and detailed discussions in Section 1.1 (Related Works) and, more thoroughly, in Appendix A.\nStill, since both you and **Reviewer aHg7** have suggested the addition, if you maintain the preference after taking our reply into account, we would not object to adding such a table (accompanied by a clear remark of its limitations).\n\nTurning to the reviewer's (particularly thoughtful) question,\n> In line 270, the authors justify the need for the filtering step by arguing that the size of $B_1$ is exponential in the sample size. However, instead of taking all possible labels of the training sample, it seems to me that one can just loop over all possible behaviors of the class $F$ on $x_1, ..., x_m$. If $F$ has finite VC, $B_1$ now has size polynomial in $m$ (compared to exponential). It would be great if the authors could comment on this and what sort of upper bounds this approach would yield.\n\nwe do not do this because the weak learning setup only assumes access to the hypothesis provided by the weak learner from the base class $\\mathcal{B}$.\nSo, neither $\\mathcal{B}$ nor the reference class $\\mathcal{F}$ is known to the learner, making it a powerful setup as, in particular, $\\mathcal{F}$ needs only to exist.\n\nNow, if we granted the learner knowledge of $\\mathcal{F}$, we could---as the reviewer pointed out---label the training set with all possible behaviors of the class $\\mathcal{F}$ on the training set.\nBy Sauer-Shelah, there are at most $O((m/d')^{d'})$ such possible patterns, where $d' = \\mathrm{VC}(\\mathcal{F})$ (notice that in our bounds use instead $\\mathrm{VC}(\\mathcal{B})$).\nThus, the size of the bag $\\mathcal{B}_1$ considered in the first step would also be $O((m/d')^{d'})$, and the argument in section 3.1 guaranteeing the existence of a classifier $v\\_g$ in $\\mathcal{B}\\_1$ with loss close to the optimal classifier in $\\mathcal{F}$ would still hold.\nWith $\\lvert\\mathcal{B}\\_1\\rvert$ polynomial in the sample size, we would not need the next filtering step as foreseen of the reviewer: we could use a Hoeffding bound (or a Bernstein bound if wanting $\\sqrt{\\mathrm{err}(f^\\star) \\ldots}$) plus a union bound to guarantee that the classifiers in the bag $\\mathcal{B}\\_1$ has generalization error close to their empirical error up to $\\pm \\Theta\\left(\\sqrt{\\frac{\\ln(|\\mathcal{B}\\_{1}|/\\delta)}{m}}\\right) = \\pm \\Theta\\left(\\sqrt{\\frac{d'\\ln(m/d') + \\ln(\\delta)}{m}}\\right)$,\nso the classifier $v\\_{g}$ with the smallest empirical loss in $\\mathcal{B}\\_1$ would satisfy $\\mathcal{L}\\_{\\mathcal{D}}(v\\_{g}) = \\mathrm{err}\\_{\\mathcal{D}}(f^{\\star}) + O\\left(\\sqrt{\\frac{d'\\ln(m/d') + \\ln(\\delta)}{m}}\\right) + \\tilde{O}\\left(\\frac{d}{\\gamma^2 m}\\right)$.\n\nAlso, even if $\\mathcal{F}$ is known, there is no general way to efficiently obtain all possible labellings associated with it.\nIndeed, if there was, the work of Hopkins et al. (2024) would yield a general efficient agnostic learner, which is not possible.\n\n\nRealizable Learning is All You Need. Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan. 2024"}]

Author rebuttal:

Meta-review: (a) Summary: The paper studies the sample complexity of the agnostic boosting problem under general assumptions. There are two main contributions: a sample complexity lower bound for agnostic boosting, and a nearly matching upper bound achieved by an inefficient algorithm. The upper bound significantly improves upon prior works, and the proposed algorithm is novel, incorporating recent results that reduce agnostic learning to realizable learning. The paper's focus is entirely on the statistical and information-theoretic aspects, not on computational efficiency.

(b) Strengths:
- Significant theoretical contribution: The paper establishes nearly matching upper and lower bounds on the sample complexity of agnostic boosting. As noted by Reviewers aHg7, tFLU, and jF1w, this is a major advance in the fundamental understanding of a classic and challenging machine learning problem.
- Novelty and soundness: The approach of using an "all possible labelings" technique based on recent work to reduce the agnostic case to the realizable one is novel. All reviewers consider the theoretical analysis sound and of high quality.
- The paper is very well-written and organized.

(c) Weaknesses:
- Computational inefficiency: The proposed algorithm is exponential time and hence not practical. The algorithm requires iterating over all possible re-labelings of the training data, which is exponential time in the sample size. All reviewers considered this as a major limitation.

(d) Reasons for recommendation: This paper makes valuable theoretical contributions to studying the sample complexity of agnostic boosting. Even though the algorithm is inefficient, the sample complexity improvements are notable and the technique is novel. I recommend acceptance. 

(e) Summary of rebuttal discussion: The authors provided detailed responses to the reviewers in the rebuttal period, and the reviewers have positive or borderline final scores.
- On computational inefficiency: the authors agreed their algorithm is inefficient and clarified that their goal was to establish statistical results, not to propose a practical algorithm. They suggested several heuristics for future work but acknowledged these do not have theoretical guarantees.
- On lack of experiments: the authors emphasized the paper's theoretical focus, stating that adding ad-hoc experiments could detract from their contribution. They stated that a meaningful empirical study would be non-trivial and out of scope for the rebuttal.
Decision: Accept (poster)