Sample-Optimal Agnostic Boosting with Unlabeled Data
Authors: Udaya Ghai
Karan Singh
Venue: ICML 2025 poster (2025)
Keywords: boosting
agnostic learning
weak learning
sample complexity
semi supervised
Primary area: theory->learning_theory
TL;DR: Agnostic Boosting algorithms with sample complexity matching that of ERM, given additional unlabeled data (often this is free!)

Abstract: Boosting provides a practical and provably effective framework for constructing accurate learning algorithms from inaccurate rules of thumb. It extends the promise of sample-efficient learning to settings where direct Empirical Risk Minimization (ERM) may not be implementable efficiently. In the realizable setting, boosting is known to offer this computational reprieve without compromising on sample efficiency. However, in the agnostic case, existing boosting algorithms fall short of achieving the optimal sample complexity. 

We highlight a previously unexplored avenue of improvement: unlabeled samples. We design a computationally efficient agnostic boosting algorithm that matches the sample complexity of ERM, given polynomially many additional unlabeled samples. In fact, we show that the total number of samples needed, unlabeled and labeled inclusive, is never more than that for the best known agnostic boosting algorithm -- so this result is never worse -- while only a vanishing fraction of these need to be labeled for the algorithm to succeed. This is particularly fortuitous for learning-theoretic applications of agnostic boosting, which often take place in the distribution-specific setting, where unlabeled samples can be availed for free. We also prove that the resultant guarantee is resilient against mismatch between the distributions governing the labeled and unlabeled samples. Finally, we detail an application of this result in reinforcement learning.

Sample-Optimal Agnostic Boosting with Unlabeled Data
Udaya Ghai Karan Singh 2
Abstract
theory of machine learning. In practice, combining classi- fiers trained adaptively weighted data points to highlight past mistakes has proven to be powerful idea. In theory, boosting provides a highly general and provably efficient framework to convert learning algorithms that are ever so slightly better than random into accurate learners. The his- torical origins of boosting began with the realization that although Empirical Risk Minimization (ERM), that is, the act of choosing the hypothesis that best fits the observed data, provides general scheme for statistical learning, for many hypothesis classes it may not be approachable in terms of computational efficiency. Often instead, in theory and practice, it is possible to quickly construct weakly accu- rate rules-of-thumb (or weak learners). Can one use such weak learners to construct an accurate learning algorithm? Boosting provides affirmative answer to this question by giving principled way of combining many weak learn- ers, each incrementally focusing on regions of the sample space where others have failed. Part of the original moti- vation here, as laid out by Kearns & Valiant (1994), was that such an aggregation of hypotheses would no longer be in-class (in modern parlance, improper) and hence could potentially circumvent the computational hardness of direct ERM. Interestingly, Kearns& & Valiant (1994) were interested in the pppreeetaaiion-ineepeeddd is, the hardness that persists independently of algorithmic parameterization. However, the main impact of the boost- ing methodology has been as a positive theory, that is, in constructing powerful new learning algorithms, a view that the present work also takes. A natural follow-up question is: Does the computational reprieve that boosting provides come at cost?
Boosting provides a practical and provably effec- tive framework for constructing accurate learning algorithms from inaccurate rules of thumb. It ex- tends the promise of sample-efficiet learning to settings where direct Empirical Risk Minimiza- tion (ERM) may not be implementable efficiently. In the realizable setting. boosting is known to offer this computational reprieve without com- promising sample efficiency. However, in the agnostic case, existing boosting algorithms fall short of achieving the optimal sample complexity.
We highlight previously unexplored avenue of improvement: unlabeled samples. We design computationally efficient agnostic boosting al- gorithm that matches the sample complexity of ERM. given polynomially many additional unla- beled samples. In fact, we show that the total number of samples needed, unlabeled and labeled inclusive, is never more than that for the best known agnostic boosting algorithm so this result is never worse while only vanishing fraction of these need to be labeled for the algorithm to suc- ceed. This is particularly fortuitous for learning- theoretic applications of agnostic boosting, which often take place in the distribution-sped where unlabeled samples can be availed for free. We also prove that the resultant guarantee is re- silient against mismatch between the distributions governing the labeled and unlabeled samples. Fi- nally, we detail an application of this result in reinforcement learning.
hardness of learning, that
setting,
Here, we are primarily concerned with sample efficiency. In the realizable case, that is, when a perfect classifier exists, the general answer is no. This serves to reaffirm our faith in the realizable boosting framework. The celebrated Adaboost algorithm (Freund & Schapire, 1997), for instance, achieves the same (near-optimal) sample complexity as ERM for VC classes ! In fact, Green Larsen & Ritzert (2022) recently showed that for a carefully designed variant the equivalence holds even up to logarithmic terms.
1. Introduction
The methodology of boosting, starting with the work of Schapire (1990), has deep roots both in the practice and
'Equal contribution 'Amazon, NYC TTepper School of Busi- ness, Carnegie Mellon University. Correspondence to: Karan Singh <karansingg@@ Saaransinghecmu.ddu.>..
But also see the note in Section 2.1 in Blanc et al. (2024) for potentially gap given arbitrary weak learners.
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Sample-Optimal Agnostic Boosting with Unlabeled Data
Let now move to the agnostic case, where we make no assumptions about the conditional distribution of labels given features; in many ways, this has become the default stance in machine learning. Firstly, the classical notion of realizable weak learning requires that weak learners attain a 0/1 loss strictly better than half, or equivalently, a corre- lation strictly better than zero on signed labels. However, such notions are unattainable in the agnostic setting. Early works agnostic boosting using weak learning definitions that mended this issue did not produce results that were additively competitive with the underlying hypothesis class, thus a direct comparison to ERM remained clusive. Fol- lowing this, Kanade& & Kalai (2009) gave a computationally efficient agnostic boosting that in fact achieves e-excess population loss compared to the best-in-class hypothesis, mirroring the guarantee ERM provides when coupled with generalization bounds (for example, in -hwwar-Shwatzz & Ben-David (2014)). However, the sample complexity of their boosting algorithm scales as (log /s4) where H is the (Iet us say for now, finite?.) hypothesis class. A recent re- sult of Ghai & Singh (2024) provides a booster that requires (log /H))/e² samples. However, both exhibit significantly higher sample complexity than the familiar (log e required for ERM, which is also optimal.
(2)2
OMADDA 1)
O1 1)/2
Figure I. The potential 6(2, 1)/2 compared against the Madaboost potential (MADX (Domingo, 2000), along with the the Huber loss (z).
parsimonious, for example, uniformly distributed or Gaus- sian, guarantee that simple classifiers can act as weak learners for the hypothesis class of interest, utilizing tools from Zx-approximation theory. Since in these settings, the feature distributions are explicitly noted, even closing the aforementioned gap will obtain results that are no better than what we get. We offer further refinements and applications of our main result, as we detail next.
1.1. Overview of contributions and techniques
Sample-optimal boosting with unlabeled data. Our first and main result is a computationally efficient agnostic boost- ing algorithm that produces a classifier with e excess error, given (log ///) labeled and (log /=1)/=* unlabeled sam- ples. Our labeled sample complexity is essentially optimal.
Although agnostic boosting has seen considerable recent progress both in methodology, for example, through ex- tensions to online (Brukhim et al., 2020) and multiclass (Raman & Tewari, 2022) settings, and in finding new appli- cations (Brukhim et al., 2022; Kothari & Livni, 2018), this limitation persists.
Using unlabeled data to accelerate boosting is novel idea. Our work also differs qualitatively, in that it does not require additional assumptions, compared to semi-supervised learn- ing methods (Chapelle al., 2006), which often require a tight clustering of data or smoothness of labels.
In this work, we highlight an unexplored avenue of im- provement: unlabeled samples. As usual, to measure the statistical efficiency of the learner, we shall keep track of the number of labeled samples it needs. However, we also imbue the learner with the ability to additionally draw poly- nomially many unlabeled samples from the underlying fea- ture distribution. Under this stipulation, our main result is computationally efficient agnostic boosting algorithm with (labeled) sample complexity scaling as (log [H())E?, and therefore for the first time matching that of ERM.
Despite differing in algorithmic techniques, previous works (Kanade & Kalai, 2009; Ghai & Singh, 2024) on agnos- tic boosting almost invariably use the Madaboost potential (Domingo, 2000) or a closely related variant:
e BM
if ay 2 0,
(MADA(Z,)) v)
1 zy
if zy < 0,
This is fortuitous and relevant both on practical and theoret- ical fronts. In practice, is widely acknowledged that, in many domains, unlabeled samples are substantially cheaper to collect than labeled ones. Furthermore, as exemplified by previous works, many applications of agnostic boosting in learning theory take place in distribution settings where unlabeled samples can be drawn for free. Here, we expressly utilize the fact that the distribution on features is
where 2 is a real-valued prediction of the discrete label y. Our key innovation to design a new bivariate potential
|2| 2
1
if 1,
p(2.y) = yz +
2
if +
whose derivative (with respect to 2) is decomposable as one term exclusively dependent on the label, and the other exclu- sive involving the features. Thus, by linearity of expectation, the population analogues of these parts can be estimated separately with labeled and unlabeled data. Furthermore, it is essential that the labeled data part, or formally its deriva- tive, does not depend on the ensemble whose value being
Purrly for ease of presentation, in the introduction, we stick to finite classes and drop dependencics in the weak learning edge and the failure probability, later denoted by y and 5 respectivey. In fact, our results hold for infinite VC classes. See Theorem 3.1
2

---

Sample-Optimal Agnostic Boosting with Unlabeled Data
assessed; this allows us reuse the same set of labeled data across all rounds of boosting unlike Kanade & Kalai (2009), without needing uniform convergence argument as in Brukhim et al. (2020), or a martingale argument as in Ghai & Singh (2024).
first among which is that the potential function is no longer the population (expectation) version of scalar potential. We keep track of the progress on the labeled and unlabeled distributions separately.
Applications. We apply our results to boosting for rein- forcement learning, where we reduce the required number of reward-annotated episodes, and learning halfspaces.
This non-conforming potential function violates some key tenets of prior work. For example, the centerpiece of the Madaboost potential is that it, or formally, its functional derivative, does not downweight points that misclassi- fied by the ensemble. This property is best captured in the definition of a conservative relabeling in Kanade & Kalai (2009). Intuitively, it makes sense; one wants not to with- draw any focus from wrongly classified data points. Not only is this false for us, is incompatible with the require- ment of having a (smooth) separable potential function of the manner have just described. This can be seen in Fig- ure I: the negative slope of the potential, always between 0 and 1, specifies the weight of each sample. The derivative of Madaboost for the negative domain is always -1, but for us this is not true, and our potential curves upward between -1 and 0.
1.2. Related work
The early theory of boosting was developed in a sequence of papers (Freund, 1995; Schapire & Singer, 1998; Bartlett et al., 1998) starting with Schapire (1990) leading to break- through in the form of Adaboost (Freund & Schapire, 1997). Even earlier the possibility of boosting was posed in Kearns (1988); Kearns & Valiant (1994). A comprehensive survey can be found in Schapire & Freund (2013). Early boosting algoritms were quite sensitive to noise (Long & Servedio, 2008; Domingo, 2000). To mitigate this, boosting was then studied in the random classification noise model (Diakoniko- las et al., 2021; Kalai & Servedio, 2003). Agnostic boosting started with Ben-David et al. (2001); Mansour & McAllester (2002); Kalai et al. (2008); Kale (2007); Chen et al. (2016) where new types of weak learners suitable for the agnos- tic setting were defined. Kanade & Kalai (2009) (see also Feldman (2010)) gave weak learning definition that led to additive excess error guarantees. Boosting in online set- ting is also well studied (Beygelzimer et al., 2015; Chen et al., 2012; Jung et al., 2017; Brukhim et al., 2020; Raman & Tewari, 2022; Hazan & Singh, 2021). See Alon et al. 1);21); Green Larsen& & Ritzert (2022); Lyu et al. (2024) for more recent work.
Improved unlabeled sample efficiency. Since our main innovation, described above, is orthogonal to previous approaches, it can be layered on top of existing algorithmic techniques.
Specifically, applying techniques from Ghai & Singh (2024) selectively to the part of potential that arises from unlabeled data, we further reduce the number of unlabeled samples needed to log((?(l))ee" With this result, our total number of samples (labeled and unlabeled) matches the number of labeled samples needed by the previous best result, yet for us, only a vanishing, concretely e, fraction of these needs to be labeled.
An ostensible alternative to our approach, especially given that realizable boosting achieves a near-optimal sample com- plexity, is to reduce agnostic boosting to the realizable case à la Hopkins et al. (2022). The concurrent work of da Cunha et al. (2025) pursues this and, in fact, obtains much more refined fat-shattering bounds. Although statistically opti- mal, this reduction requires pruning the hypothesis class by enumeration while considering all possible labelings of samples. and hence takes exponential time, rivaling ERM. In contrast, the present work offers computationally efficient algorithms that run in polynomial time, requirement that has been central to the theory of boosting since its origin in computational learning theory.
Resilience to covariate shift. Since, in addition to the labeled dataset, our algorithm has access to a stream of unla- beled examples, natural practical concern may be that the underlying law governing the latter's generation may not exactly match the distribution of features in labeled exam- ples. Unlike realizable learning where every sample helps to narrow down to the correct classifier, agnostic learning is often brittle against changes in the covariate distribution, since no classifier is the best in all regions of the feature space. However, we show that if there is a mismatch be- tween the labeled and unlabeled distributions available to learner, our learner still succeeds in learning an arbitrarily accurate classifier as long as these distributions have the same support on the feature space. Moreover, the labeled sample complexity is unaffected by such a mismatch.
2. Problem setting
We consider the fundamental setting of binary classification where X' represents the set of feature descriptions, and the possible labels are (+1). ). There is an underlying joint dis- tribution D over X' x {+1}, which, while unknown to the learner, is crucial to determining its performance. Let Dx
We point out that for the covariate shift setting, one must suitably generalize the measure of the progress being made in each round of boosting. This requires few changes, the
3

---

Sample-Optimal Agnostic Boosting with Unlabeled Data
be the marginal distribution D induces on the feature space X. Given any binary classifier h X' + {+1], its success on D can be measured as
3. The algorithm and the main result
Our main result and its proof are completely contained in this section. We describe some notation and essential algo- rithmic ingredients in the following.
corTD(h)=
= E (z.g)/
[y((r]]
Notation. Let h- arg nex corrp(h) be the best- in-class hypothesis. For brevity of notation, for any finite set D C X' x {+1}, we denote the empirical average over it by E. D = 2 and - otherwise. For a real-valued function S. we take sign f to mean its precomposition with sign.
Correlation can readily be translated to the more commonly used metric, the 0/1-loss (9)1 (h) = E( [1
| Σ (n)))))())) We define sign(z) 1 if
as (h)r = -12111110 (h). (h).
Consider hypothesis class H S X {+1} against which the learner aims to be competitive. The objective
Potential function. Consider the potential function
of the learner is to produce a hypothesis h X + {+1} such that with probability at least - 6, chrr Z max ch) - E, where E, ô are pre- pre-specified error tolerances. A crucial remark here is that this final hypothesis may not belong to the hypotheses class H. The learners who given such flexibility are called improper, and all known boosting algorithms fall into this class.
6(2. v) = (=) - yz
where (2) is the Huber loss (Huber, 1992):
2
if > 1, if if S 1.
++2)
1.2
2
Definition 2.1 (Agnostic Weak Learner). For any Eo, do > 0, a >-agmostic weak learner for a hypothesis class H. and base class B draws m(50, 5n) independently and identically distributed samples from any distribution D' supported X x } and outputs base hypothesis W E B such that with probability at least 1- -go.
Since we never differentiate ((2,8) y) with respect to y, let o' (2. v) 80(2.y) and oz y) &e((.))) To measure dz
the progress of any real-valued H X + R. consider the population potential
E. (o(H()))))) (a.)~D
corLD (W) 2 7 max corro: 80.
heH
(H,
E (ay))
1s' (H (z), (x)) v))(
This definition of agnostic weak learning was introduced in Kanade & Kalai (2009), where it is noted that typically m(=,6) 6) (log( /8))) Mirroring the presentation of results in Kanade & Kalai (2009); Brukhim et al. (2020);
The quantity 4 (H, is the directional derivative of Φ (H) on h.
Description of the Algorithm. Algorithm 1 roughly fol- lows the potential based boosting framework of Kanade & Kalai (2009). The algorithm simulates the process where the true label is kept with probability -(((((()), y)/2 and chosen randomly otherwise. As can be seen in Figure 1, the probability of flipping increases monotonically in the mag- nitude of (x)), the more certain H; is of the correct label, the closer to uniformly random the label will be in D, for the weak learner. Since predicting on random labels is impossible, this randomized relabeling increases the relative importance of data that H2 does not predict accurately.
Ghai & Singh (2024), we present the formal statement of results for fixed Ea; 6g. In this way, the magnitudes of con- tribution to the final error for the boosting algorithm and the weak learner are made distinct.
Finally, further refinement of the agnostic boosting frame- work is the Distributionnsppccij setting (Kanade & Kalai, 2009; Feldman, 2010), in which the set of input distributions to the weak learner are constrained so that their marginals on the feature space match that of the true underlying distribu- tion. Thus, any regularity present in the feature distribution Dx. e.g., if it follows a uniform or a Gaussian distribution, also made available to the weak learner, which makes the design of such weak learners easier. Our results will also apply under this restriction. Like in previous work, our main algorithm works by relabeling examples; there is no need to adaptively reweigh them. This ensures that, for any sample fed to the weak learner, the overall marginal distribution follows Dxx-
The main trick we employ in this work is that the potential ((2, y) in (1) is split into two parts such that the first part (=2) has dependence estimated via unlabeled examples. The second part -y= is linear in 2, hence the derivative has no dependence on z. As a result estimating this does not depend on H,, but just a weak hypothesis. Since this is a simple class, the samples required for this estimation are small and we can
the label, and hence can be
4

---

Sample-Optimal Agnostic Boosting with Unlabeled Data
use uniform convergence to assure concentration across all boosting rounds. The formal concentration argument can be seen in Lemma 3.3. One interesting observation, is that in this construction, samples from the labeled part of the distribution are never relabeled. Line 6 of Algorithm I can be interpreted as providing a regularization, wherein predic- tions on the unlabeled data are pushed towards O because Pa(x) I 2/2 if and only if (x) O.
Algorithm 1 Agnostic Boosting with Unlabeled Data
1: Inputs: Samplers for labeled data from D and unla- beled data from xx, 7-agnostic weak learning oracle W, parameters 7,, T, S, USS, m.
2: Initialize zero hypothesis H1 = =.
3: Sample S labeled examples to create dataset D.
4: for t = 1 to T do
5: Sample U unlabeled examples to create dataset D..
6: Construct a resampling distribution D, that chooses between steps and B with equal probability.
The relabeling is designed correlation the relabeled distribution corresponds to the derivative of population po- tential (see Lemma 3.3). As such, weak learner produces a hypothesis that has nonnegligeable correlation with the (negative) functional gradient of the population potential @D Ht). With properly chosen 7/, this assures descent in potential as long as the weak learner has sufficient edge on the current distribution (Case A of Theorem 3.1 and line 10 of Algorithm 1). However, this need not be the case because we have access to an agnostic weak learner, and it's possible that no h E B performs well on D, If this is the case and if D (H, (i)) 2 E we are in Case of Theorem 3.1. this case, this condition on the derivative as- sures us that h2 = sign H4 also a descent direction (line 12 of Algorithm 1). Now, because the potential is bounded from below, only certain number of such descent steps can occur. Eventually, we must reach point where neither
A. Return (z, y) picked uniformly from D.
B. Pick I uniformly from Dr, and return (z, 1), where the pseudo-label y is chosen as
T +1 with probability (x( = 1 1- (HH.()))
with remaining probability.
7: Sample times from D. to create dataset D/
Call the weak learner on Dj to get Wi (D)). if Do DO = Ee (Wa(x) > then
10: Update He+1 = H, + w//
11:
else
12: Update Hi+1 = H, - r) sign H.)).
13: end if
14: end for
15: Sample So labeled examples to create dataset Do-
Case A nor Case B holds. Here (H(ee sign( He)) is small and there is no E B that performs well on D,. Stitching these together with Lemma 3.5 relating the correlations to the potential gradient can be used to provide the result.
16: Output h
arg max he (ssig(((.):)ttTT) (x.
Σ yh(x).
3.1. Main result on sample-optimal agnostic boosting
Proof of Proposition 3.2. Let us begin by noting that v'(s) sign(2) min |=]} from which the first two prop- erties be seen. From this, all but the last properties follow. The last part can be verified by elementary calcula- tions.
Theorem 3.1 (Main thcorem). For any e, > 0, there an instantiation of parameters such that 1) = On)²)), T 0(1//262), T O(ys), S = O(VC(B) /7² U O(VC(B))/ /223)) So = O(1==)), 0(1/7²=²) for which Algorithm I guarantees with proba- bility 1 - 5 - TTo that
m(Eo, do) +
We show that (H h) can be estimated efficiently on the base class B.
250 7
Lemma 3.3. There exists universal constant C >>> 0 such that with probability 1 - ö. for all t E [T], h E B U {
(T) Z max COLLD (h) NEW
E.
During its execution, Algorithm 1 makes T O(L/?2=?) calls to the weak learner, and samples S + So ((VC(B) /-262) labeled samples and TU = O(VC(B) (AA unlabeled samples.
1 4/ (He coLDD, (h) S EGen == CV 2
1
VC(B) log 1 min(S,U}
Proof of Lemma 3.3. By the definition of De, we have that
3.2. Proof of the main result
1 corrp, (h) 2 _ [x((((aa]]
1 E 16' (H(()))))())
To maintain the continuity of presentation, our organization and notation closely mirror Kanade & Kalai (2009). We will use the following properties of @ and th.
where we use the fact that Line 6.B in Algorithm 1 ensures [ (x))). Since D and Dr are composed of IID draws from D and Dx respectively, we use the follow- ing uniform convergence result (c.g., see Anthony & Bartlett (2009)), originally due to Talagrand (1994).
Proposition 3.2. [1((2)) < 1 and 24/ (2) 2 ffrrr all z E IR. For all E [+1], o(. y) is continuously differentiable, 1 smoooth and satisfies (00, y) - min, 6(2,8) $ 1/2.
5

---

Sample-Optimal Agnostic Boosting with Unlabeled Data
Theorem 3.4 ((Talagrand, 1994)). Fix a hypothesis class B C X - {+1), and distribution D over X x {+ There is universal constant C 2 0 such that with probability 1 - 6, for all h E B, it holds
This wraps up the lemma.
We are now ready to prove the main result.
Proof of Theorem 3.1. Let us dispense with the random events at once. The success of Lemma 3.3, the event that (rX |ooT Dy (sign and max | corr (W) - corpp, (W,) I 7e/10 can be ensured with probability 1 5 by simple application of Hoeffing's 's inequality and union bound given the set- ting of m and So in the statement of the theorem. Sim- ilarly, EGen S 72/10 holds in Lemma 3.3 for S,U Q((VC(B) + log 8 8-1))/22))
1 Σ
m wh(z)) S SCV
VC(B) + log 8
[uh(t)]
(x.))
m
(sign Hi) S <//10,
where {1z Vi) hie(m! are sampled IID from D.
Hence, for some constant C 2 0 we have with probability 1 8 that [Ezly([z]] - corrp(h)] and E. (HL((())))())) most EGen. Since 02(2. = d2)2 - y. and hence [el (H(()))))
EN W (())))) are at
Let hr (H++1 H2)/n. Since ø is 1-smooth by Proposi- tion 3.2:
&b(He, h) = E I~Dx
E
[yh(
(w.N)~
completes the proof. Including ht changes the VC dimen- sion by constant (Eisenstat & Angluin, 2007).
LD (H(H++1) - -Hi(H)
(2)
no' () + of ()(()))))
< E
(a.0)~D
2
Finally, we will use the following lemma that upper bounds the correlation gap, which is our ultimate concern, by the difference in the directional derivative of the potential.
S / (He 11))
Lemma 3.5. For any real-valued classifier H X - R, we have corr - corr H)) S O sign (H)) 2 (H, h²).
Case A: Consider any step t where corr D. (W₂) r. Here
h = Wa/y. It follows from Lemma 3.3 that
1 ho) S 2CoTTD, (he)
25Gen
Proof.
We start by noting that
7 2 2corr (he))
7
sig, (1)) - h1),
25
+
E [( (H())) - (((sssgg((())))))))))))))(()((() h" (x))
5
(z.g)~D
S --
E [11 10111111 (1-yé' ye' (H(()))))) (x) sign( H (x) )
where we set T = YE and = 7²E. By Equation (2), the potential drops as (D(H+1)) (H,)) S -7262 /2.
(x.0)~D
where in the last line we use the fact that y²² ===1 =1 1.
Case B: Consider any step t where co (W,) S T and
Consider any (x. y) such that yH (x) > O: Here y(h"(x)) sign(H(x:) (x))) < O. Furthermore, since y and (xx) have the same sign, so do y and v' (x))) by Proposition 3.2, and hence (1- (H (z))) < 1. Similarly, whenever (x) < (x)))) 0, and y and v/ (Hx)) have opposite signs that imply (1 yy (x()) 2 1.
crucially D'p (HH, sign H,) > E. Here h4 sign H.) < -c, by Equa-
sign Hy.
Since V (H,,, ht) = - tion (2), we have 4D(H.+) - (D. S 222222.
O: Then y(h"(>)
By Proposition 3.2, at initialization, Lp is at most a half away from the minimum. Thus, setting T T= 2/????, there must arise an iterate such that neither Case A nor Case B hold. That is, there is some E [T] such that corr (W.) S and (Ht, HI.) S E. Now using Lemma 3.3 and that the weak learner a-aproxximately max- imizes correlation (Definition 2.1), we have
Now the claim follows as
4'D (H, sign(H)) - (H,,²))
= E
(1- 1yH(a)20 (1 - yo' (H(x))) (hh sign((
-bb (H, h²) S 2 corTp, (h*) + 2E
2 corrD, (Ws)
280
+
+ 2eGen
+ 1y (1- (1-yy' (H((() y(h' (z) (z)
Y
2 corr D. (W.)
250
2z
21
20
2 E [u(('(z)) (x) - sign H (x)) (2.))DD
?
γ
280 <
12c
+
= corro(h)) ) (sirn(sign(()) (H).
7 5
6

---

Sample-Optimal Agnostic Boosting with Unlabeled Data
where in the last line we recall e7 and égen = =7/10.
Algorithm 2 Agnostic Boosting with Selcetive Reuse of Unlabeled Data
By Lemma 3.5, we have
1: Inputs: Samplers for labeled data from 'D and unla- beled data from xx. 7-agnostie weak learning oracle W. parameters 7), T. S, U,S.S. m, a.
chrr - corrp(sign(H.))
I 4/2l [M, sign - (H,,,
Initialize zero hypothesis H1 0.
250 17s
3: Sample S labeled examples to create dataset D.
_ 5
4: for 1 = 1 to 7 do
5: Sample U unlabeled examples to create dataset Di
To complete the proof, we observe that
6: Construct a resampling distribution Dj that picks æ uniformly from D., picks 7 E [+1] uniformly and returns (z, 0) if t = 1; for t > 1, do:
corrD ( v corr Bo (1) + E/10
s corr Do (iign H₂) + =/10
A. With probability
o, return sample (z, 9)
from D/-1-
< corrD (sign H)) + e/5
B. Else return (z, 0) where x is uniformly chosen from D., n/ ~ Unif(O, n]. and ÿ is created as
s 250/7 18:/5,
where we use the fact that 5t maximizes the empirical corre- lation on the dataset Dy. Substituting e appropriately yields the claim.
+1
with probability (r with remaining probability, where
--1
4. Improving unlabeled sample efficiency
(H)((((((z))
Pc(x,1/)
2(1 + 0) mpb" (H(-1 (x) + +ny 1 (x)))(1116
2
In this section, we reduce the number of unlabeled samples needed to 1/700²3, using the data reuse scheme from Ghai & Singh (2024), which is crucially only applied to unlabeled data. The key idea behind the scheme is that since H, changes by a small amount each time, the change it induces on any twice-continuously differentiable potential is also small. Therefore, the desired relabeling distributions are not too different across rounds, and one may be able to reuse the distribution of past rounds to some extent. This difference is reflected in Algorithm 2 in Line which allows recursive use of unlabeled data from past rounds. To do this, we first construct twice-come continoooti differentiable potential using Pseudo-Huber loss.
2(1 + σ)
Construct a resampling distribution D, that chooses between steps A and B with equal probability.
A. Return (x, v) picked uniformly from D.
B. Return (x, 7) sampled uniformly from Dj.
8:
Sample times from Dr to create dataset D
Call the weak learner on Dj to get W.- - W(D). if co (W.) = E(. De TW.(x) > 7 then
10:
11: Update He+1 = H, + W///.
12: else
602, v) xx2) ye, and (=) 2 1.
(4)
13: Update H = H; - ") sign (H)).
14: end if
Theorem 4.1 (Main theorem with unlabeled data reuse).
15: end for
For any 5 > 0, there is an instantiation of parameters
16: Sample So labeled examples to create dataset Do-
such that ?) = 0(728/ log [B), T Ollog (1/22 T = O(TE), S = (VVC / /=2=²), U = O(1/nE), So = O m = m(Eo. 5n) + ) for which Algorithm 2 guarantees with probability 1 8- Tôg that
17: Output h arg max he (H..) (x.))),
Σ yh(x).
350 E.
( 2 max (h) NCH
increased oracle complexity, that is, the number of calls to the weak learner, which now has a log [B] factor un- like Theorem 3.1. Again mirroring techniques in Ghai & Singh (2024) provides some mitigation. In particu- lar, in Appendix A.2, we provide a different guarantee for the same algorithm that makes ((1/)²e²) calls to the weak learner, while needing Olog 2=) labeled and (log /B1/73e3 + (log | //222//?))) unlabeled samples.
During its execution, Algorithm 2 mukes T (log B))) calls to the weak learner, and needs S + So = Olog (B)/>²=²) labeled samples and TU = Olog 8²) unlabeled samples.
Although the above result is always better in terms of the demand for unlabeled samples, comes at the cost of
7

---

Sample-Optimal Agnostic Boosting with Unlabeled Data
5. Resiliency against covariate shift
denote the class of halfspaces. There exists degree d d= O such that running Algorithm I with ERM over parities of degree at most d produces classifier h satisfying
We consider the setting when the learner has access to a distribution D supported over X' x {+1} and a different, possibly unrelated, distribution Q supported over features X. We show that under mild conditions the learner can still produce an arbitrarily accurate classifier. To measure how different Q and Dx are, we define Cx = |dDx/dQlla /dQll oc" which is a uniform upper bound on the Radon-Nikodym derivative of Dx with respect to Q.
ID (F)
S minn (b(h) + e,
heHt
while using only OiE (===)) labeled samples in ppoly(1/e) time.
6.2. Boosting for reinforcement learning
Theorem 5.1 (Main theorem for covariate shift). For any E, > O, there is an algorithm that makes OCxx/ calls to the weak learner, samples (VVC(B) /n2e²) la- beled samples from D and TU = O((Cx) x VC(B) //te*t unlabeled samples from 2, and outputs h such that with probability 1 5 - Too that
The construction of near-optimal policy for reinforcement learning (RL) via boosting was first pursued in Brukhim et al. (2022). Ghai & Singh (2024) improve on these results. Modifying the RL setting to include the ability to sample trajectories without observing reward, we can apply our results to reduce the number of samples that require reward feedback. Such a feedback model could be useful where rollouts are cheap but reward feedback is not because it comes from human labeling or expensive processes (Finn et al., 2016). In Appendix E, we provide a formal description of this modified setting.
(1 + (1+Cx)Eo Cx)=O
COLTD 2 max (orr NEW
Y
Recall that Eo can be made arbitrarily small by feeding more samples the weak learner from the empirical distribu- tion. Although this comes at (polynomial) computational cost, in particular, the weak learner now needs to be more accurate, the sample complexity remains unaffected.
Plugging Algorithm 1 into a modified meta-algorithm of Brukhim et al. (2022) in a manner that allows for trajectories without reward yields the following result for binary- MDPs. Our result improves upon Ghai & Singh (2024) in that it requires fewer with-reward episodes. Here, V is the expected discounted reward of a policy π, V is its maximum. , is the discount factor of the underlying MDP, and Coc, Doc and & E, are distribution mismatch and policy completeness terms (related to the inherent Bellman error). In the episodic model, the learner interacts with the MDP in episodes. In the v-reset model, the learner can seed the initial state with fixed well dispersed distribution as means to exploration. See Appendix E for complete statement of results and details of the setting.
The key step is in Lemma B.3; it proves an analogue of Lemma 3.5 implying that oversampling the part of the poten- tial connected to the Huber loss does not hurt the correlation gap. From there, we set up a non-scalar potential measure to keep track of the progress of the learner.
6. Applications
6.1. Agnostic learning of halfspaces
We illustrate how our method, when used as a black box, ag- nostically learns halfspaces over the n-dimensional Boolean hypercube under uniform marginals the features. Since unlabeled samples can be drawn from the uniform distribu- tion at essentially no statistical cost, the added complexity of acquiring unlabeled data becomes solely computational concern.
Theorem 6.2 (Informal; stated formally in Theorem E. Let W be a 7-weak learner for the policy class I1 op- erating with a base class B, with sample complexity m(Eo. 56) (log /B)/ Fix tolerance E and fail- ure probability 8. In the episodic access model, there is an algorithm using that uses the weak learner W to produce policy π such that with probability 1 1-5, 5, we have V - -- < (CoeE)/(1 3) + E, while sampling ((log (B))/=²²t) episodes of length - ((11-1)-)) with- out reward feedback and ( [B1)/"²=²) episodes of length O (0-3)-- 1)-1) with reward feedback. In the v-reset access model, there is setting of parameters such that Algorithm 4 when given access to W produces policy т such that with probability 1 1 8, we huve V - -V* < E. while sampling ((log (B1))~3²3> episodes of length O(11 - 11) without reward feedback and O BB))/~2+*) episodes of length O(11 - -1) with reward feedbackk
This procedure improves upon existing boosting-basse ap- proaches. In particular, building on Kanade & Kalai (2009), we rely on empirical risk minimization (ERM) over all pari- ties of degree at most d x 1/s². Such an ERM rule achieves weak learner advantage = ndd, As shown in Theo- rem 6.1 below (proved in Appendix D), this instantiation of our boosting framework reduces the labeled sample com- plexity from O -7 to OE ").
ED) -3)²+ +E,
Theorem 6.1. Let D be any distribution over {+1}" x } with uniform feature marginals, and let
H- = {sign(w] - 8) (w. 0) E 1Rt11]
8

---

Sample-Optimal Agnostic Boosting with Unlabeled Data
Dataset
No Added Noise
5% Noise
10% Noise
% Noise
PAB
Ours
PAB
Ours
PAB
Ours
PAB
Ours
Ionosphere
0.87 + 0.05
0.91 + 0.04
0.88 + 0.05
0.90 + 0.04
0.84 :: 0.06
0.90 + 0.04
0.81 + 0.06
0.83 0.06
Diabetes
0.84 + 0.09
0.89 + 0.07
0.86 = 0.08
0.86 + 0.09
0.79 + 0.09
0.79 + 0.10
0.76 - 0.10
0.80 - 0.10
Spambase
0.91 + 0.02
0.94 = 0.02
0.90 + 0.03
0.92 + 0.03
0.89 + 0.03
0.90 = 0.02
0.83 Σ 0.04
0.87 = 0.03
German
0.79 + 0.07
0.86 + 0.07
0.84 + 0.08
0.84 + 0.08
0.76 +: 0.08
0.87 + 0.07
0.75 + 0.08
0.77 0.08
Sonar
0.78 + 0.08
0.92 + 0.05
0.68 + 0.09
0.89 + 0.06
0.84 + 0.08
0.87 = 0.07
0.69 + 0.10
0.77 = 0.08
Waveform
0.89 + 0.02
0.89 + 0.02
0.88 + 0.03
0.87 +: 0.03
0.86 + 0.03
0.86 + 0.03
0.83 + 0.03
0.83 + 0.03
Average 0.84
0.89
0.84
0.88
0.81
0.84
0.78
0.81
Table 1. 50-fold cross-validated accuracies of the Potential based Agnostic Booster (PAB) (Kanade Kalai, 2009) and our proposed boosting algorithm on six datasets with 0%, 5%, 10%, and 20% added label noise (during training). Sonar and Tonosphere have 50%
of labels dropped while the remaining datasets have 90% of labels dropped. A final row is included for the average accuracy (evenly weighted) over all 6 datasets.
7. Experiments
independently by labeled and unlabeled data, respectively.
In this section, we demonstrate the empirical viability of our approach. Table showcases the results from our ini- tial experiments comparing Algorithm I with the agnostic boosting method introduced by Kanade & Kalai (2009), herein referred to as the Potential-based Agnostic Booster (PAB). These evaluations were performed on various UCI classification datasets (Sigillito et al., 1989; Hopkins et al., 1999; Smith et al., 1988; Hofmann, 1994; Sejnowski & Gor- man, 1988; Breiman Stone, 1984), employing decision stumps (Pedregosa et al., 2011) as the weak learners. No- tably, Algorithm 1 extends PAB to handle unlabeled data by incorporating our newly defined potential function, defined in Equation (1).
We end with few concrete directions for future work. The possibility of achieving an optimal sample complexity for agnostic boosting in polynomial time without any conces- sion remains open. In our view, an equally important and likely fruitful direction is to improve the oracle complexity of agnostic boosting where known results scale as 1/E², which substantially worse than log I/s for the realizable case. Developing algorithms that adapt, sis, to the weak learning edge "/t is key unresolved step to making agnostic boosting practical. Finally, it would be worthwhile to extend the sample complexity improvements in recent works to the filtering framework (cf. sub-sampling; see, for example, the discussion in Domingo (2000)), which essentially treats the weak learners as black-box learning al- gorithms and hence avoids appeals to uniform convergence arguments on the weak hypothesis class.
per-round ba-
To evaluate the robustness of all algorithms against label noise, we introduced noise levels of 5%, 10%. and 20% during the training phase. We randomly remove certain percentage of labels from each dataset to create scenarios with both labeled and unlabeled instances. Specifically, we omitted 50% of labels for smaller datasets (Sonar and Iono- sphere) and 90% for the other datasets. Our findings indicate that incorporating unlabeled examples leads to improved performance. This enhancement is likely attributed to the limitation of PAB in reusing samples, which consequently restricts the number of boosting iterations when the sample size is constrained. For comprehensive overview of the experimental setup, please refer to Appendix C.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
References
Alon, N., Gonen, A., Hazan, E., and Moran, S. Boosting simple learners. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 481- 489, 2021.
8. Conclusion
This paper aims to leverage unlabeled data to reduce the sample complexity of agnostic boosting. The theoretical improvements are stark. When given as much unlabeled data as the amount of labeled data required for existing ap- proaches, the resultant sample complexity reduces to that of ERM, becoming essentially optimal. This is accom- plished by a novel decomposbbl potential function, whose derivative naturally splits into two parts that are estimable
Anthony, M. and Bartlett, P. L. Neural network learn- ing: Theoretical foundations. cambridge university press, 2009. Bartlett, P., Freund, Y., Lee, W. S., and Schapire, R. E. Boosting the margin: A new explanation for the effective- ness of voting methods. The annals of statistics, 26(5): 1651-1686, 1998.

---

Sample-Optimal Agnostic Boosting with Unlabeled Data
Ben-David, S., Long, M., and Mansour, Y. Agnos- tic boosting. In Computational Learning Theory: 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Compu- tational Learning Theory, FurCCOLI 2001 Amsterdam, The Netherlands, July 16-19, 2001 Proceedings 14, pp.
Eisenstat, D. and Angluin, D. The ve dimension of k-fold union. Information Processing Letters, 101(5):181-184 2007.
Feldman, V. Distribution-specifie agnostic boosting. In- novations in Theoretical Computer Science (ITCS), pp. 241-250, 2010.
507-516. Springer, 2001.
Beygelzimer, A., Kale, S., and Luo, H. Optimal and adap- tive algorithms for online boosting. In International Con- ference Machine Learning, pp. 2323-2331. PMLR, 2015.
Finn, C., Yu, T., Fu, Abbeel, P., and Levine, S. General- izing skills with semi-supervised reinforcement learning. arXiv preprint 1w 2016.
Freund, Y. Boosting weak learning algorithm by majority. Information and computation, 121(2):256-255 1995.
Blanc, G., Hayderi, A., Koch, C., and Tan, L.-Y. The sample complexity of smooth boosting and the tightness of the hardcore theorem. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1431- 1450. IEEE, 2024.
Freund, Y. and Schapire, R. E. decision-theoreth general-
ization of on-line learning and application to boosting. Journal of computer and system sciences, 55(1):119-139 1997.
Breiman, I.. and Stone, C. Waveform Database Generator (Version 1). UCI Machine Learning Repository, 1984. DOI:
Ghai, U. and Singh, K. Sample-efficient agnostic boost- ing. In The Thirty-eighth Annuul Conference on Neural Information Processing Systems, 2024. URL https:
Brukhim, N., Chen, X., Hazan, E.,, and Moran, S. Online agnostic boosting via regret minimization. Advances in Neural Information Processing Systems, 33:644-654 2020.
/ / openreview net/ f
Green Larsen, K. and Ritzert, M. Optimal weak to strong learning. Advances in Neural Information Processing Systems, (122830-32841 2022.
Brukhim, N.. Hazan, E., and Singh, K. A boosting ap- proach to reinforcement learning. Advances in Neural Information Processing Systems, 35:33806-33817, 2022.
Hazan, E. and Singh, K. Boosting for online convex opti- mization. In International Conference on Machine Learn- ing. pp. 4149-4149, PMLR, 2021.
Chapelle, O., Scholkopf, B., and Zien, A. Semi-supervised learning. 2006. Cambridge, Massachusettes: The MIT Press View Article, 2:1, 2006.
Hofmann, H. Statlog (German Credit Data). UCI Machine Learning Repository, 1994. DOI: https///bi.org//0.2444222333
Chen, S.-T., Lin, H.-T., and Lu, C.-J. An online boosting algorithm with theoretical justifications. In Proceedings of the 29th International Coference on International Con- ference on Machine Learning, pp. 1873-1880, 2012.
Hopkins, M., Reeber, E., Forman, G., and Suermondt, J. Spambase. UCI Machine Learning Repository, 1999. DOI: http:///bi.rr//0224445/5533
Chen, S.-T., Balcan, M.-F., and Chau, D. H. Communica- tion efficient distributed agnostic boosting. In Artificial Intelligence and Statistics, pp. 1299-1307. PMLR, 2016.
Hopkins, M., Kane, D. M., Lovett, S., and Mahajan, G. Realizable learning is all you need. In Conference on Learning Theory, pp. 3015-3069. PMLR, 2022.
da Cunha, A., Høgsgaard, M. M., Paudice, A., and Sun, Y. Revisiting agnostic boosting. arXiv preprint 093334, 2025.
Huber, J. Robust estimation of a location parameter. In Breakthroughs statistics: Methodology and distribu- tion, pp. 492-518. Springer, 1992.
Diakonikolas, I., Impagliazzo, R., Kane, D. M., Lei, R., Sorrell, J., and Tzamos, C. Boosting in the presence of massart noise. In Conference Learning Theory, pp. 1585-1644 PMLR, 2021.
Jung, Y. H., Goetz, J., and Tewari, A. Online multiclass boosting. Advances in neural information processing systems, 30, 2017.
Domingo, C. Madaboost: a modification of adaboost. In Proc. of the 13th Conference on Computational Learning Theory, COLT'00, 2000.
Kalai, A. and Servedio, R. Boosting in the presence noise. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pp. 195-205. 2003.
10

---

Sample-Optimal Agnostic Boosting with Unlabeled Data
Kalai, A. T., Mansour, Y., and Verbin, E. On agnostic boost- ing and parity learning- In Proceedings of the fortieth annual ACM symposium Theory of computing, pp. 039-638,220 2008.
Schapire, R. E. and Freund, Y. Boosting: Foundations and algorithms. Kybernetes, 42(1): 2013.
Schapire, R. E. and Singer, Y. Improved boosting algorithms using confidence-ratee predictions. In Proceedings of the eleventh annual conference on Computational learning theory, pp. 80-91, 1998.
Kale, S. Boosting and hard-core set constructions: a sim- plified approach. In Electronic Colloquium on Computa- tional Complexity (ECCC), volume 14. Citeseer, 2007.
Sejnowski, T. and Gorman, R. Connectionist Bench (Sonar, Mines vs. Rocks). UCI Machine Learning Repository, 1988. DOI: hutps///oo.orrl10044444//55000
Kanade, V. and Kalai, Potential-base agnostic boosting. Advances in neural information processing systems, 22, 2009.
Shalev-Shwartz S. and Ben-David, S. Understanding ma- chine learning: From theory to algorithms. Cambridge university press, 2014.
Kearns, M. Learning boolean formulae or finite automata is as hard as factoring. Technical Report TR-14-88 Harvard University Aikem Computation Laboratory, 1988.
Sigillito, V., Wing, S., Hutton, L., and Baker, K. Iono- sphere. UCI Machine Learning Repository, 1989, DOI: htpps//ddi.org/10.24442/2
Kearns, M. and Valiant, L. Cryptographic limitations on learning boolean formulae and finite automata. Journal of the ACM (JACM), (1(1:677-95 1994.
Smith, J. W. Everhart, J. E., Dickson, W., Knowler, W. C., and Johannes, R. S. Using the adap learning algorithm to forecast the onset of diabetes mellitus. In Proceedings of the annual symposium on computer application in medical care, pp. 261. American Medical Informatics Association, 1988.
Klivans, A. R., O' Donnelll R., and Servedio, R. A. Learning intersections and thresholds of halfspaces. Journal of Computer and System Sciences, 68(4):808 -408008080 2004.
Kothari, P. K. and Livni, R. Improper learning by refuting. In 9th Innovations in Theoretical Computer Science Con- ference (ITCS 2018). Schloss fuer Informatik, 2018
Talagrand, M. Sharper bounds for gaussian and empirical processes. The Annals of Probability, pp. 28-76, 1994.
Long, P. M. and Servedio. R. Random classification noise defeats all convex potential boosters. In Proceedings of the 25th international conference on Machine learning, pp. 608-615, 2008.
Lyu, X., Wu, H., and Yang. J. The cost of parallelizing boosting. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp- 3140- 3155. SIAM, 2024.
Mansour, Y. and McAllester, D. Boosting using branching programs. Journal of Computer and System Sciences, 64 (1):103-112, 2002.
Pedregosa, F,, Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cour- napeau, D., Brucher, M., Perrot, M., and Duchesnay, E. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-283 22-00, 2011.
Raman, V. and Tewari, A. Online agnostic multiclass boost- ing, Advances in Neural Information Processing Systems, 35:25908 259000, 2022.
Schapire, R. E. The strength of weak learnability. Machine learning, 5:197-227, 1990.

---

Sample-Optimal Agnostic Boosting with Unlabeled Data
Appendix
Map of the appendix. Appendix A, we complete the proofs for results concerning improved unlabeled sample efficiency. Appendix B discusses the proofs for covariate shift. In Appendix C are provided experimental details not found in the main paper. Appendix and Appendix E provide further details on applications of boosting learning halfspace and reinforcement learning, respectively.
A. Improving unlabeled sample efficiency
A.1. Proofs for the result
Notice that this section we use different choices of & and t) those stated Equation (4). However, Lemma 3.5 continues to hold. In fact, the latter only requires that 2x) 2 0 for all z. To maintain the continuity of presentation, our organization and notation closely mirror Ghai Singh (2024). Throughout this section, we will always set = n//..
Define (H) ((a.))-(V((())) and D (H. h)) (
Proof of Theorem 4.1. This proof is almost identical to that of Theorem 4 in Ghai & Singh (2024). We reproduce it for completeness. In fact, the only change stems from the new upper bound on EGen in Lemma A.1, which unlike the previous work makes distinction between labeled and unlabeled samples.
Lemma A.1. There exists universal constant C such that with probability 1 for all (T), BU (h*)
(H,, h) + corLD, (h)) SC C
log [ + log
7
log B
log [8///8
5
7
oU
But before that let us dispense with the random events once. The success of Lemma A.I, the event that
max+e|T] coTT D, (sign H,) csin H,) < E"/10, and max4e(T] corr (W,) corrp, (W)l < e'/10 can be ensured with probability 1 - 5 by simple application of Hoeffing's inequality and union bound given the setting of m and So appropriately. We will soon set precise values of e' and e".
Recall that h = nHHH+ H²). Equation (2) can be rearranged to get
(D(H)+1))
T Σ (l1,,,,
7
<
n 2-
T/T
2n
1/T
where we use the fact that @00 v) - min, 0(2, y) 1.
Case A: If h4 W./n, observe that CoITD, (W,) 2 coNTD; (W;) - 5'/110 2 E//10. Now apply Lemma A.l to get
4'D (Hi,hi) 2 ?
3 cOIPD, (Wi)
5Gen
3
EGen 10
5'
7
Y
Case B: If he -iign(H.), then comP,, (W,) - coMpD (W;) + 6//10 10 S r + s//10. Applying Lemma A. we get
3 r
3corrp, (W.) 2 3ycorrd, ( -e0 2 (H,,(H,,h 3E0 Gen
10
Using Lemma 3.5, this translates to
(H,, sign( H.)) - T (H,, sign(HH.)) < (H,,,))) (corrD(h") (sinr H.)))
< (corrr((h") (o)))ssgg((4..)) + 7
r + Eg
EGen-
10
12

---

Sample-Optimal Agnostic Boosting with Unlabeled Data
In either case, we have
(lHl,, 2 min-
7 T
EGon
(corTD corro(sign) (sign(HH.)))
3
T
5'
+
60
EGen
10
7
7
10
Now, set
4
EGen
5'
7
+
+
? +
3
1/
?2
?
10
Hereafter let s be the time step satisfying
comp (h*) (oggo H.)) S (2r + t0) + (1-
21
1
80
e¹
GGnn
+
1+
EGen
+3
1/T
72
57
Such choice must exists, since otherwise get for all that
(HH, hx) 2 7 10
3 e'
EGen
+
" 722
(1/T)
which contradicts Equation (2). Combining this with the observation that h minimizes the correlation on Do we get
8
2m
2E
3
E"
comrp(h") comrD (h) <
Eo +
1/
7/
Setting s' = 7=/100, E" = 7e/1100 and plugging in the proposed claimed result.
with appropriate constants yields the
Proof of Lemma A.I. By the definition of Dr, we have that
corp,, (h) 1 F blub(a))
2 [x((((())))
= _ F [bu((()))]+ corro;
2
Since Dt is composed of IID draws from D, the standard uniform convergence result via union bound gets that for some
constant C' we have with probability 1 that [x)) - corro (h) is most Vlog [ + log 0-1)/S.
By inspecting Line 6 in Algorithm here and Line 5 in Algorithm in Ghai & Singh (2024) with the substitution that 1, we note that the two are identical. Therefore, we can apply the following result from Ghai & Singh (2024).
Lemma A.2 (Lemma 6 in Ghai & Singh (2024)). Setting n/7. There exists universal constant C >> O such that with all
probability 1 - 5. for all t E [2], B J {
(V [8/T/8
(H,,,, + C (h) s Cn
oU + log 1BTT/6
Since @D()) WD(H)) - corrp(H), we get
/ (H,,) h) + corro, (h) S BBbuh(x)) corr +
1 WD h) + 2corpp(())
1 (H,
E (=)((())))) z~Dx
(R.))~ [yh(x))]
completing the proof.
13

---

Sample-Optimal Agnostic Boosting with Unlabeled Data
A.2. Trading off oracle Complexity and unlabeled sample complexity
Theorem A.3 (Main theorem with unlabeled data reuse). For any E, ò > there is an instantiation of parameters for which Algorithm 2 guarantees with probability 1 5 - Tôg that
350
corr (h) 2 max COIT (h) hEH
During its execulion, Algorithm 2 makes O (11/72=2) calls to the weak learner, and samples S + So = Olog (B1/>2=²) labeled samples and TU Olog / + (log [B)) //2=2) unlabeled samples.
Proof. The proof is identical to that of Theorem 4.1, except crucially to the substitution of the following bound on EGen
There exists universal constant C > such that with probability 8, for any E [T] Bu
// (H,.h) + corrD, (1) so
log [ +
log B
a ")
(V
log BB/T0
(log (8)3/8)8/2
S
oU
VU
To prove this claim itself, we follow the same recipe as the proof of Lemma A.1. Once again we observe that By Line in Algorithm here identical Line 5 in Algorithm in Ghai & Singh (2024) with the substitution that y 1. Therefore, apply the following result from Ghai & Singh (2024).
Lemma A.4 (Lemma 15 in Ghai & Singh (2024)). Setting n/%, There exists a universal constant C >>> 0 such that with probability - 6, for all E [T], E B }
(H,,,) corrp; S Cn
(Vies
|o8 |BTT/8 oU + log T/
B. Resiliency against covariate shift
Let (z)) be the Huber loss. Instead of definite a scalar potential, this time we will directly define the population potential measure that involves both D and Q. Recall that Cx xdDx/dQ] has be least one.
Φ(H) Cx E [+((())
E
[x)
x~
[a.y)~
d' Cx
E (= ang
E [yh(z)]
(2,0)>
We describe a variant of Algorithm 1 that can tolerate a mismatch between Dx and Q. The key modification happens in Line 6 of Algorithm where lsbule-labeled samples created from the unlabeled distribution Q are sampled a higher rate than labeled samples.
The uniform convergence still applies after some minor adjustment.
Lemma B.1. There exists universal constant C such that with probability
8, for all t Bu (M))
/CC(B) + log
VC(B) + log
(HH + (1 Cx) corrp, S EGen = C'
+ +xx
S
U
Proof of Lemma B.I. By the definition of D,, we have that
corrp, (h) I Cx
- Cx (H(())))))
14

---

Sample-Optimal Agnostic Boosting with Unlabeled Data
Algorithm 3 Covariate-shift Resistant Agnostic Boosting with Unlabeled Data
1: Inputs: Samplers for labeled data from and unlabeled data from 2, 7-agnostic weak learning oracle W, parameters
7), T, U, Sg. m.
2: Initialize zero hypothesis H1 0.
3: Sample $ labeled examples to create dataset D.
4: for t- 1 to 7 do
5: Sample U unlabeled examples to create dataset Dr.
6: Construct a resampling distribution D, that:
A. With probability ox returns (I, picked uniformly from D.
B.
With remaining probability, picks æ uniformly from D. and returns (xr, 7). where y is chosen as
+1 with probability pe(x) (H,
2
with remaining probability.
7: Sample m times from D; create dataset Dj.
8:
Call the weak learner on D' to get W = (DD). if corr bJ (Wa) e (x)) then Update Hz+1 = H, + w/a.
9:
10:
11: else
12: Update H4+1 = He- 17 sign H.).
13:
end if
end for
Sample Sn labeled examples to create dataset Do-
15:
16: Output h= arg max he (sig (..))ED.
Σ yh(x).
where we use the fact that Line 6.B in Algorithm 3 ensures >Øp - (z)( Since D and D, are composed of IID draws from D and Q respectively, we have that, for some constant C 2 we have with probability 1- 5 that Bølyh(z)] co)r-phh) S (VVC(B) + log 8/1) and [E, (z)) (F==)(l((((() V(VC(B) + log 8- I)/U.
[(1 + Cx) corrD, (h) + (HH,, m) < Cx ET W (H.))))(
L (H((())( + [B]bb(>) corr corr (1))
The decomposition above completes the proof.
We will need the following well-known property of Random-Nikodym derivatives.
Lemma B.2. For any non-negative function fuuctioooiiv X -> R22. it is true that Cx Ex- 2 (fWDx(((x))
Proof. Since Cx 2 |dDx /dQ], have Cx F. [a F [f(x) (v) [r
The key idea in the analysis occurs in the following lemma. Essentially, it says oversampling the part from unlabeled data does not hurt the correlation gap.
Lemma B.3. For any real-valued classifier H X R. we have
sign(H)) (H, h²) corrp(h") - (sinn(sig((H))..
Proof. Using Lemma B.2 below, we arrive at
4' ('(H,sign(H)) 4' (HH = Cx E ( h²)))) - E (ssign(H(()) h (*()))
aNQ
(a.v)>
> E (i((( 11 (x))
E
(H())(((()))) M())))
z>Dx
(x.0)~D
E (a.v~D
[(v'((())) ([(((()))>w((se((((((()) (sign((( +²(x)))
15

---

Sample-Optimal Agnostic Boosting with Unlabeled Data
Recall that and (z) always have the same sign, and hence so do (=) and sign(z). This ensures non-negativity as since h² (a:) is restricted to (+1).
(((H()))ssign((( h" (x:) = (/ (H))) ~/'
-()))))))) (F))
From here onward, our original proof strategy work. In particular since y² = 1, we get
HH, sign(H)) HH) (r.0)~
[(1 ya ( (H ((i)))
h (x)).
As before, consider any (a, y) such that yH (x) 0: Here y(h (a) sign (z))) < 0. Furthermore, since y and (x) have the same sign, so do y and & (H (x)), and hence (1 ye (x))) I Similarly, whenever yd) 0: Then y(h" (x:) (x))) O, and y and (H (z)) have opposite signs that imply (1 yy (H)())))) 2 1.
Now the claim follows as
/ (H, sign H)) - (HH,1²))
E (x.
1 19H(6)20 (1 yi (x())) y(h (x) sign(H (x))) + +1 (H())< (1 yi (H(x)) (x))) (1h((())))))))))((()(()(()) - sign( ( H (xx)))
50
21
20
2
sign sign (x.0)D
= (h*) corrp(sign( ())
We are finally ready to prove the main result.
Proof of Theurem 3.1. Let us dispense with the random events at once. The success of Lemma B.1, the event that m corr D. (sign H,) coir He)l I e/10, and max corr (Wi) corpD, (W)) S ye/20Cx can be ensured with probability 1- 5 by a simple application of Hoeffing's inequality and union bound given the set- ting of m m(Eg, 6g) + (((2)))/e²)²) and So 0(1/~2=2) Similarly, 6Gn S 78/10 /10 holds in Lemma 3.3 for S= 2(VVC(B) + (olog-1))/// and U ((((x)) + log 1))2)222
Let h, (H++1 H.)/n. Since & is 1-smooth, we have
17Cx 2²2
@ +D.HH) S / (H;,
(5)
Case Consider any step where coir by (W.) > Here hr W,/7. y. follows from Lemma B. that
('HH, < (1 + Cx) corLD, (ha)
EGen
+
7
Y
(1 + Cx) corr Dj (h+)
22Gen
E
+ +
7
5
where r 2ye/(1
Cx) and 1 7"e/Cx. By Equation (5), the potential drops xHH++1) - (HH,) S -7262 -22x2/2Cxx
Case B: Consider any step t where corr (W;) < J and crucially 4 (Ht sign Hi) 2 E. Here he = - sign Hy. Since &' 6HH,, h.) (H, sign H.) < -8, by Equation (5), we have (HH+-)) - (HH,) S 282 /2Cx.
At initialization, (0) Further for any H. X I, using non-negativity of vi have
(x)) 1
i (H) = Cx =~
[+(((((
E [1) (a.))-
Z [v(H()))) - (a.))
I~Dx
Thus, at initialization + is at most half away from minimum. Thus, setting = 2Cx/22=" there must arise an iterate such that neither Case A nor Case hold, That is, there is some E [I] such that corr D. (W,) and Φ (H,, sign H,)
16

---

Sample-Optimal Agnostic Boosting with Unlabeled Data
Now using Lemma B.1 and that the weak learner 7-approximately maximizes correlation (Definition 2.1), we have
4 (Hs, h*) - (1 Cx) corrp, (h*) + 26
+ Cx) corID, (W&). +
(1 + Cx)e0
28Gen
?
7
(1 + Cx)
corr Dú (W,)
(1 Cx E
E
5
(1 + Cx)e0 12c
5
where in the last line we recall = 211/(1 + Cx) and Ecien = EY/10.
By Lemma 3.5, we have
COrTD(h") corro(sign(H.) s 1 sign (H,)) (H,,,h")
(1 Cx)
17s
7
To complete the proof, we observe that
corr (h) S corr D. (h) + E/10
S corr D. (sign H.) + E/10
- (sign H.) + e/5
$ (1 + 0x) + 18=/5,
where we use the fact that Ji maximizes the empirical correlation on the dataset Do-
C. Additional experimental details
For PAB, the number of samples that can be fed to a week learner in a round scales inversely with the number of boosting rounds, as the algorithm requires fresh samples each round.As such, we perform grid search on the number of boosting rounds with T {25, 50, 100), while we just 100 for implementation of Algorithm 1. In both algorithms we search over the parameter m, the number of samples feed the weak learner each round with a grid of (5, 20, 50, 100), though if such setting is invalid for PAB, we continue until all samples are used.
Our experiments were performed using the fractional relabeling scheme stated in (Kanade & Kalai, 2009), intended to reduce the stochasticity the algorithm subject to. In particular, rather than sampling labels, we provide both (I, y) and (x,, y) in our dataset with weights equal to their sampling probabilities. Experiments are all run on an M1 Macbook Pro and complete within an hour. Multiclass datasets are converted binary.
D. Proof of Theorem 6.1
Proof. We observe that ERM on the Fourier basis Xs(x) IIves T,, namely parities on subsets S, can be used to produce a weak learnrr (Klivans et al., 2004). As such, an n-dimensional halfspace can be approximated with uniform weighting on the hypercube to g² fz-error using degree-limited Ba,d = (+xx= : |S| S d} as a basis, where d = 20c-4, 4 As result, at least one Badd must have high correlation.
Lemma D.1 (Lemmaa 5 in (Kalai et al., 2008)). Let 'D be any data distribution over {=1}" 1-1,1) with marginal distribution Unif( )*) on the features. For any fixed and d = 20, there exists some h E B,,d such
corrp(h) 2 max.sH ccr -E
nd
The result follows directly from the preceding lemma, which provides weak learner for the task, and Theorem 3.1. We note that [Bnaal nd and 7 n-dd so
log [Bn.a
< dn 2d log(n)
22E2
g2
17

---

Sample-Optimal Agnostic Boosting with Unlabeled Data
The unlabeled samples used in Algorithm can be produced by sampling from the hypercube adding the nooly(1/e) runtime, but not the sample complexity.
E. Boosting for reinforcement learning
In this section, we consider boosting in the reinforcement learning setting. We wish to separately consider the number of reward-annotated episodes against the number of reward-free episodes needed to learn a near-optimal policy.
Consider a Markov Decision Process M (S,A,r, B, no), where is set of states, A {=1} is a binary set of actions, S x A + [0, 1] determines the (expected) reward at any state-action pair (which is sometimes available), P: x A + S captures the transition dynamics of the MDP, i.e., P(s||s, a) is the probability of moving to state s' upon taking action at state s, B E [0, 1) is the discount factor, and is the initial state distribution. Let Q= a) and (*(s) be the state-action and state value functions. Let V = EB-n_VV (s)] be the expected total reward when starting from the start state distribution J4, and we will say V = V Finally, the occupancy measure P7 induced by a policy æ starting from an initial state distribution pl is stated below. We will take μ² = 1 as a matter of convention.
In the episodic model, the learner interacts with the MDP in a limited number of episodes of reasonable length (i.e., (1- and the starting state of MDP is always drawn from μo- In the second, termed rollouts with v-resets, the learner's 's interaction is still limited to small number of episodes, however, the MDP now samples its starting state from v. It is important to stress that in both cases, the learner's 's objective is the same, to maximize V starting from foo However, e could be more spread out over the state space than No. and provide an implicit source of explanation, and the learner's guarantee as shown next benefits from its dependence on a milder notion of distribution mismatch in this case. In this setting, we do not always assume the reward revealed. We consider a model where we can rollout a policy and observe rewards or alternatively can just observe the state trajectories.
Since have binary actions, our weak learners are policies, which denote instead of h. This notion is equivalent to that used by Brukhim et al. (2022) and Ghai & Singh (2024), because for binary actions, a random policy induces an accuracy of half regardless of the distribution over features and labels.
Say x¹ E arg max, V be reward maximizing policy, and V be its value. Let U1 the convex hull of the boosted policy class, i.e., the outputs of the boosting algorithm. For any state distribution μí, define the policy completeness E,r term as
Ege
aEA max min Benay [max (" a) - Q1))
Ell s'ell
In words, this term captures how well the greedy policy improvement operator is approximated by II in an state-averaged sense over the distribution induces by any policy in Π.. Finally, we define distribution mismatch coefficients below.
max 1| /M- Dx =1p= /vlloo. C.c
*ENl
Theorem E.1. Let W be a q-wek learner for the policy class II operating with a base class B, with sample complexity m[Ea, 60) (log [B)/80)/e3 Ee) Fix tolerance and failure probability 5. In the episodic access model, there is a setting of parameters such that Algorithm 4 when given access W produces a policy ग. such that with probability 1 - 8, we have
E
F V. < 1 13
+
while sampling
o ( (1- 3)9733
0 log [B|]
episodes of length (((1-9))1) without reward feedback (via Algorithm 6) and
o ( 317
00 log B
episodes of length ((1 - -1) with reward feedback (via Algorithm 5).
18

---

Sample-Optimal Agnostic Boosting with Unlabeled Data
Algorithm 4 RL Boosting adapted from (Brukhim al., 2022)
1: Input: iteration budget T', state distribution μ4, step sizes Th, post-selection sample size
2: Initialize a policy To arbitrarily.
3: for | = 1 to 7 do
4: Run Algorithm 2 to get my. using
Algorithm 5 to produce a distribution over state-actions (ignore @) by executing the current policy dz-1 starting from the initial state distribution j as the labeled samples.
Algorithm 6 produce distribution over states by executing the current policy mh- starting from the initial state distribution μ as the unlabeled samples.
5: Update nे = 7/s - + T
6: end for
7: Run each policy ne for P' rollouts to compute an empirical estimate V of the expected return.
8: return = ne. where L' arg max, V
Algorithm Trajectory Sampler adapted from (Brukhim et al., 2022)
1: Sample state Sq f and action a' Unif(.A).
2: Sample ~ μ² as follows: at every step h, with probability 3, execute else, accept 8/.
3: Take action a' at state Sh, then continue to execute ı,, and use termination probability of - B. Upon termination, set R(sh, d') as the sum of rewards from time h onwards.
4: Define the vector Q, such that for all A, ((a) 2R(ss, d') Ila=a'.
5: With probability (a()), set y a' else set A {a'), where C C= -11-33/2
6: return (8), Q.y).
In the v-reset access model, there is setting of parameters such that Algorithm 4 when given access W produces policy ग. such that with probability 1 - 8, we have
V V 5 Ex
+
11 3)2
while sampling
o 0 D5 log B
(1 B) 157335
episodes length O((1 -3) without reward feedback (via Algorithm 6) and
D log B
[1 8)
12
episodes of length O((1 - 11) with reward feedback (via Algorithm 5).
Proof. The proof follows by applying the result in Theorem 4.1 within the proof of Theorem 22 from Ghai & Singh (2024).
For the episodic model, applying the second part of Theorem in (Brukhim et al., 2022), while noting the smoothness of V", and combining the result with Lemma 18 and Lemma 11 in (Brukhim al., 2022). we have with probability -78
Following the logic of Theorem 22 from Ghai & Singh (2024), need to ensure is that output of Algorithm 2 as instantiated in Algorithm 4 every round has excess correlation gap the best policy 11 no more that (1 -8)2e/Co.. which
C log [8] SE
unlabeled samples and O C2 log [B] labeled samples. (1-8))7722
Algorithm 2 assures us can be accomplished with O
The total number of samples is T O [I-
times greater.
Similarly, for the v-reset model, we need to ensure is that output of Algorithm 2 as instantiated in Algorithm every round has an excess correlation gap over the best policy no more that - / Dzo. which Algorithm 2 assures us can be
19

---

Sample-Optimal Agnostic Boosting with Unlabeled Data
Algorithm 6 Reward-free Trajectory Sampler
1: Sample state ~ and action a' ~ Un..(.A.
2: Sample 8 ~ 4*" as follows: at every step h, with probability B, execute म. else, accept S/-
Take action a' at state 8h, then continue to execute и, and use termination probability of 8.
4: return S/.
accomplished with O
D2 log [8] unlabeled samples and O (1-8)
D log [8] labeled samples. The total number of samples (1 (1-8))n2c2
= = (11-3)
D
times greater.
20


Reviews:
[{"review_id": "qSerBKfRK7", "reviewer": "Reviewer_yiBa", "summary": "This work designs boosting algorithms in the agnostic setting. Their main contribution are novel algorithms in a previously unexplored direction: Can unlabeled samples reduce the number of labeled samples required for boosting? This paper gives a positive result by providing several algorithms that achieve different trade-offs between the number of labeled and unlabeled samples required. The first algorithm requires $VC/\\varepsilon^2$ labeled samples and $VC/\\varepsilon^4$ unlabeled samples and makes $1/\\varepsilon^2$ calls to the weak learner (Theorem 3.1). The second algorithm includes this to $\\log(B)/\\varepsilon^2$ and $\\log(B)/\\varepsilon^3$ respectively while making $\\log(B)/\\varepsilon^2$ calls to the weak learner (Theorem 4.1). The final algorithm retains this sample complexity while reducing the number of weak-learner calls to $1/\\varepsilon^2$ as in Theorem 3.1.\n\nThe authors also explore the implications of their results in (1) efficiently learning half spaces (following similar observations by Kanade and Kalai (2009)) – leading to a faster running time provided unlabeled samples are available) and in reinforcement learning (where they reduce the number of reward-annotated episodes required).\n\n## Post rebuttal update\nI read the authors response, maintain my original rating, and support acceptance.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review. Both the suggestions – introducing $\\gamma$ early and defining the VC dimension – are well noted, and we will execute these upon revision.", "claims_and_evidence": "Yes, the proofs in the paper are supported by formal proofs.", "methods_and_evaluation_criteria": "Yes, the proposed methods and evaluation criteria seem meaningful.", "theoretical_claims": "I skimmed all the proofs, but did not carefully verify their correctness.", "experimental_designs_or_analyses": "No, I did not check the soundness of the experimental design, except checking that the baselines they use are meaningful.", "relation_to_broader_scientific_literature": "The most closely related prior works to this paper are Ghai and Singh (2024) and Kanade and Kalai (2009). The key innovation in this work is to use unlabeled samples in boosting and, as a consequence, reduce the number of labeled samples required. This tradeoff is not explored by either prior work, and to the best of my knowledge has not been explored earlier in the literature.  In terms of the number of labeled samples used, this paper improves the previous state-of-the-art guarantee from $1/\\varepsilon^3$ to $1/\\varepsilon^2$. While at the same time, ensuring that the total number of labeled and unlabeled samples matches the total number of labeled samples required by the previous state-of-the-art guarantee.", "essential_references_not_discussed": "To the best of my knowledge, no essential references were missing. Although, I am not an expert on boosting methods.", "other_strengths_and_weaknesses": "None", "other_comments_or_suggestions": "The paper is generally well-written and easy to follow. A couple of suggestions are: First, it would be good to introduce $\\gamma$ somewhere in the introduction. Currently, it is used in Section 1.1 but only defined later. Second, while they are very common, I think it would still be good to define the VC dimension and other technical terms either in the paper or the appendix.\n\nTypos:\n1. In Theorem 3.1, the value of “T” has a typo. Missing 1 in the numerator.\n2. Theorem 4.1 has a typo around “calls to the weak learner, and samples”", "questions_for_authors": "None", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "09Qn9P0jo0", "reviewer": "Reviewer_sPrw", "summary": "The main contribution of this paper is presenting a new agnostic boosting algorithm. In particular, this algorithm is computationally efficient assuming an oracle access to weak learners and improves the sample complexity of previous algorithms in a certain way. Moreover, the authors demonstrated an application of their new result in learning of half-spaces and reinforcement learning. Further, their theoretical results are supported by a few experiments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments.\n\n**Statistical Gains over Realizable-Agnostic Reduction:** At the outset, we find this to be a loaded question (i.e., one that in our view has an unfair presupposition built in). If one were to discard computational constraints, one can perform ERM on the target class with $VC(\\mathcal{H})/\\varepsilon^2$ samples, and achieve an optimal sample complexity. This, via classical VC results, is unimprovable; for each $\\mathcal{H}$, there’s a distribution for which this is tight. The reduction outlined by the reviewer – which we are certainly happy to cite and highlight – also gets $\\propto 1/\\varepsilon^2$ sample complexity. Getting the class-specific dependencies right via this approach takes additional work and has been pursued in a recent preprint that we have been recently made aware of (which we can not link here because they cite our work). However, note that this reduction requires pruning the hypothesis class by enumeration while considering all possible labellings of $VC(\\mathcal{H})/\\varepsilon^2$ samples, and hence takes exponential time.\n\nOver such computationally inefficient, and in the case of ERM, also statistically optimal, exponential time approaches, we offer no statistical improvements. *But here we remark that neither does the celebrated Adaboost algorithm.* Boosting is a question that arose in computational learning theory (i.e., in Valiant-lore as opposed to statistical learning aka Vapnik-land), and its primary purpose has since its origin been and continues to be computationally efficient reductions, which we also pursue. Like all known boosting results, and unlike exponential time approaches, our results make a polynomial number of calls to the weak learning oracle – in fact we are no worse than any other agnostic booster in this regard quantitatively – and perform polynomial work. Now it is natural to ask if these computational benefits come at a statistical cost, and this is the question we make progress on.\n\nTo summarize, *the purpose of our work is to give computationally efficient boosting algorithms that are yet better than known ones in terms of sample requirements.* It is thus unsurprising that we are no better statistically than exponential time approaches (such as ERM or exponential time agnostic-realizable reductions). \n\n**Novelty:** Our intention was always to say that the consideration of unlabeled samples is new in the agnostic boosting context. Indeed outside it, there’s a massive body of work on semi-supervised learning. Here, we also thank the reviewer. The works of Hopkin et al and David et al are definitely worth pointing out in the broader statistical learning context; we will add a discussion on this line of work. However, both our context and our techniques owing to mandates of computational efficiency are disjoint from Hopkins et al, to the best of our reading. Unlike Hopkins et al, we do not coarsen the hypothesis space by considering all possible labellings of some set of points. Our intuition and proof is based on synthesizing a potential function in the framework of Kanade et al, whose parts can be independently estimated on labeled and unlabeled data, respectively.\n\nIn light of this clarification regarding the positioning of our paper (and of boosting broadly), we would like to gently petition the reviewer to consider raising their score.\n\nPS. This is a minor point in the grand scheme of things. But the realizable-boosting reduction, to the best of our reading, would also break the distribution-specific nature of the weak learners (discussed on page 3), since Adaboost does not preserve the marginal distribution over features.", "claims_and_evidence": "I verified the correctness of the proof of their main theorem. Moreover, the improvement of their main result, findings about the covariate shift, applications, and experiments make sense to me.", "methods_and_evaluation_criteria": "The evaluation criteria are natural.", "theoretical_claims": "I verified the correctness of the proof of their main theorem.", "experimental_designs_or_analyses": "The experimental results make sense to me.", "relation_to_broader_scientific_literature": "Boosting is a well-known learning theoretic technique. Any good result in this context will be valuable. This paper improves upon the previous results in terms of sample complexity.", "essential_references_not_discussed": "I think the paper contains most of the primary references. However, listing the references in the related work section is not the best way to discuss the related works. I suggest explaining a few more related ones in more depth. Additionally, I think it is good to cite https://proceedings.mlr.press/v178/hopkins22a.html as they have also used unlabeled data to prove their theorem in the agnostic regime.", "other_strengths_and_weaknesses": "Consider the following way of thinking: (1) Definition 2.1 implies the existence of the weak learner in the realizable setting. (2) We can boost weak learners in the realizable setting to get a PAC learner in the realizable setting. (3) We can now apply any agnostic to realizable reduction. For instance, we have: https://proceedings.mlr.press/v178/hopkins22a.html and https://arxiv.org/abs/1610.03592. What is the *statistical* advantage of your method? In terms of the novelty of using unlabeled data in proving theorems for the agnostic regime, while I agree that it is a new idea in this context, I do not consider it an \"unexpected\" result.", "other_comments_or_suggestions": "I think it is good to discuss the limitations of your approach in other settings, such as multiclass with an unbounded label space.", "questions_for_authors": "I will happily increase my score if the authors can clarify my previous question. In addition, do you think there is any connection between your method and the reduction of https://proceedings.mlr.press/v178/hopkins22a.html that also uses unlabeled data?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "-"}}, {"review_id": "FHbQJ05X9C", "reviewer": "Reviewer_P5aa", "summary": "This paper explores how unlabeled samples can be useful in the task of agnostic boosting, in which access to a weak learner must be leveraged to construct a more accurate learning algorithm. The task of agnostic boosting has previously been considered only in settings with access to labeled samples, and the state-of-the-art algorithms have a sample complexity that scales with $1/\\epsilon^3$, significantly behind the $1/\\epsilon^2$ dependence achieved by standard ERM. \n\nThe authors present an algorithm that still has a $1/\\epsilon^3$ dependence on the number of _unlabeled_ samples, but only a $1/\\epsilon^2$ dependence on the number of _labeled_ examples, matching the sample complexity of ERM in terms of the number of labeled samples. This improvement is achieved through careful analysis and targeted modifications to existing potential-based agnostic boosting algorithms found in the literature.\n\nIn many settings, unlabeled samples can be obtained at a much lower cost than labeled data. From this point of view, this new algorithm represents a substantial advancement in our understanding of the sample complexity of agnostic boosting.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful comments and thorough review. We will execute all the suggested editorial suggestions upon revision.\n\n**Experimental setup:** Each dataset is split into a labeled sample pool and an unlabeled sample pool; the labels for the unlabeled sample pool are discarded. The precise ratio of this split is given in the footnote on page 8. The contract in our comparison is that Algorithm 1 and PAB across the course of entire execution have access to the same pool of labeled samples. Algorithm 1 additionally can access the unlabeled pool. Our experimental setup thus is an ablation study meant to verify the hypothesis that additional unlabeled samples can enhance the learning performance in agnostic boosting. The ability to achieve lower error when given access to the same pool of labeled samples indicates that the learning is now more label-sample-efficient.\n\nThrough its execution PAB, the algorithm from Kanade et al, has access to only the labeled pool. PAB is an iterative boosting algorithm that does not reuse samples between its rounds. Hence, the number of samples available in each round of boosting in PAB is the number of labeled samples / number of rounds of iterations. In contrast, following the description in Algorithm 1, our algorithm via subsampling can reuse the same set of labeled samples across multiple rounds, although unlabeled samples used every round must be fresh.", "claims_and_evidence": "The paper is primarily a theory paper, and all theorems and claims are backed up with rigorous proofs.", "methods_and_evaluation_criteria": "I was a bit confused by the description of the experimental setup, in particular how the samples were allocated for the two algorithms (did PAB receive fewer samples per round, or did it have fewer rounds of boosting, but the same number of samples per round?) I would appreciate if the authors could clarify exactly how the two algorithms use the labeled and unlabeled examples.", "theoretical_claims": "I examined the proof of Theorem 3.1 and found it sound. While I didn't scrutinize all proofs in detail, the other results appear convincing due to their clear links to established techniques and findings in the boosting literature. However, I would defer to another reviewer who has read the remaining proofs thoroughly.", "experimental_designs_or_analyses": "I did not carefully check the soundness of the experiments beyond reading the method description, so would defer to other reviewers on this point. I think that the paper is still quite strong without these experiments.", "relation_to_broader_scientific_literature": "This paper contributes to the extensive literature on agnostic boosting, a topic that has garnered significant interest in the ML community from both theoretical and practical perspectives. In my view, the paper offers a fresh perspective by demonstrating the substantial benefits that can be derived from unlabeled samples. To the best of my knowledge, this observation is novel in the context of agnostic boosting and has the potential to open up new avenues of research in the field.", "essential_references_not_discussed": "I'm not aware of any missing references that need to be discussed.", "other_strengths_and_weaknesses": "- Strengths: The novel use of unlabeled data and the surprising power drawn from it offers a fresh perspective to the boosting literature, and possibly other areas as well.\n- Weaknesses: The paper was quite dense to read through. While much of this is due to the technical argument, I think there are some small notational and expositional changes that could be made to improve the reader experience. I've made a few notes on small notational changes in the \"other comments or suggestions\" section.", "other_comments_or_suggestions": "Some minor typos/comments\n- italicized question in first paragraph of introduction (provide -> provides)\n- line 55: \"agnostic boosting __algorithm__\"?\n- line 206: \"nonnegligeable\" -> \"non-negligible\"\n- Typo in statement of Thm 3.1 (\"T = O(/...)\")\n- It is unclear from the statement of theorem 3.1 that $\\epsilon_0$ and $\\delta_0$ are parameters for the weak learner. This should be restated explicitly. \n- I feel that the hidden log factors should be more explicitly presented. I suggest:\n    - Adding parenthetical clarifications in the introduction.\n    - Replacing the current $\\mathcal{O}$ notation with $\\tilde O$, as the current symbol is easily mistaken for standard O, which caused initial confusion in interpreting the statements and proofs.\n- The identical titles for Algorithms 1 and 2 are confusing. Distinct, descriptive titles for each would improve clarity and readability.\n- In Section B of the appendix, I think there is an incorrect theorem reference on line 795, i.e. it should be Proof of Theorem 5.1", "questions_for_authors": "1. I'd appreciate an explanation of the experimental setup that addresses my confusion described above in the Methods and Evaluation section.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xeXS3vwd2t", "reviewer": "Reviewer_TPBa", "summary": "This work proposes an agnostic boosting algorithm that seeks to improve sample complexity by incorporating unlabeled data. The central idea is to design a potential function whose gradient can be split into two distinct parts—one that depends only on the model’s output (reflecting the feature information) and another that depends solely on the labels. This separation enables the algorithm to use a large amount of unlabeled data to estimate the feature-related component, while relying on a smaller set of labeled data to estimate the label-related component. The authors provide a theoretical analysis showing that, under certain conditions and with the availability of additional unlabeled data, the number of labeled examples required can be reduced to levels comparable to those achieved by standard empirical risk minimization techniques. They also discuss extensions to improve the efficiency of unlabeled data usage and address challenges such as distribution shifts between labeled and unlabeled data. Experimental results on several datasets are presented to demonstrate the practical performance of the method.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments.\n\n**Runtime overhead over PAB:** We remark that both in theory and in practice, our algorithm is no slower than the PAB algorithm of Kanade et al. To achieve $\\varepsilon$-excess error, the PAB algorithm performs $1/\\gamma^2 \\varepsilon^2$ rounds of boosting in each of which the weak learner is fed $VC(\\mathcal{B})/\\gamma^2 \\varepsilon^2$ samples; the same is true for us (see the setting of parameters in the theorem statement). In terms of implementation, the PAB algorithm samples $VC(\\mathcal{B})/\\gamma^2 \\varepsilon^2$ samples fresh from the population distribution; we sample half this number from a pool of previously sampled labeled data points, and the other half from freshly sampled unlabeled data points. Therefore, the running times of PAB and Algorithm 1 are remarkably similar.\n\n**Novelty of results and techniques:** While our proof techniques build upon prior work (and the exposition is carried out so that this is as clear as possible, and so that our changes are conspicuous), we believe our contribution goes beyond incremental improvements. The conception that unlabeled data can specifically ameliorate the sample complexity gap in agnostic boosting is novel and opens new directions for semi-supervised boosting research. This connection wasn't previously recognized despite its simplicity in hindsight.\n\nNext, we come to techniques: Despite employing a variety of other techniques, agnostic boosting algorithms (e.g., Kanade et al, Ghai et al) almost invariably use the Madaboost potential (Domingo et al), and in fact so do hundreds of other *robust* boosting algorithms. Our key innovation is orthogonal to other existing algorithmic techniques, which is why it can be layered on top of Kanade et al and Ghai et al. We introduce a new potential function, crucially which via linearity of expectation, can be written so that it decomposes into two parts, one estimable based on labeled data, and the other based on unlabeled data. Furthermore, it is essential the first labeled data part (formally, its derivative) does not depend on the ensemble whose value is being assessed; this allows us to reuse the same set of labeled data across all rounds of boosting (unlike Kanade et al) without needing a uniform convergence argument (as in BCHM) or a martingale argument (in Ghai et al).\n\nThis new potential function violates some key tenets of prior work. For example, the centerpiece of the Madaboost potential is that it (formally, its functional derivative) does not downweight points that are misclassified by the ensemble. This property is best captured in the definition of a conservative relabeling in Kanade et al. Intuitively, it makes sense; one wants not to withdraw any focus from wrongly classified data points. Not only is this false for us, it is incompatible with the requirement of having a separable potential function, which we have just described. This can be seen in Figure 1– the derivative of Madaboost for negative domain is always -1, but for us this is not true, and our potential curves upward between [-1, 0]. Here, our proof technique, despite seeming syntactic similarity, has been modified to handle this.\n\nFinally, it is worth pointing out that the setting of covariate shift requires a number of changes to keep track of the progress being made in each round of boosting. Foremost among these is the potential function, which is no longer the population (expectation) version of a scalar potential. We keep track of the progress on the labeled and unlabeled distributions separately.\n\n**Range of experiments:** The primary contribution of our work is theoretical, as Reviewer P5aa also notes. Our main innovation is the design of a potential function whose use in the potential based boosting framework permits the use of unlabeled samples to make learning more sample-efficient. Since this is an improvement that can be composed with other innovations, like the sample reuse scheme in Ghai et al, our experiment setup thus is an ablation study meant to verify the hypothesis that additional unlabeled samples can enhance the learning performance in agnostic boosting. And in it, Algorithm 1 which is a close modification of PAB from Kanade et al is compared to PAB. We strongly feel such ablation studies which measure the improvement induced by individual algorithmic techniques is the right way to make and measure progress on foundational problems, as opposed to a leaderboard approach. Finally, we remark that our datasets are of comparable sizes to ones considered in Kanade et al.\n\n**Intuition:** We hope that our self contained 1.5 page proof can aid future readers. But crudely, the potential is such that for unlabeled data, the relabel distribution shifts towards negative examples when $H_t(x)$ is positive and positive examples when $H_t(x)$ is negative.  This acts as a regularizer against high certainty predictions on data without labels.", "claims_and_evidence": "The paper’s claims are supported by its theoretical analysis. However, although some experiments are provided, they do not include comparisons with the latest agnostic boosting methods.", "methods_and_evaluation_criteria": "The evaluation criterion is well-suited for the problem, similarly to previous studies [Kanade & Kalai, 2009; Ghai & Singh, 2024].", "theoretical_claims": "In the review process, I examined several key proofs in the paper to ensure their correctness. Overall, the proofs are written clearly, and I did not find any obvious errors.", "experimental_designs_or_analyses": "The experimental section only compares against the method from [Kanade & Kalai, 2009] and does not consider other agnostic boosting approaches such as [Brukhim et. al. , 2020] and [Ghai & Singh, 2024]. Moreover, the experiments are conducted on only a few simple datasets, which is insufficient to demonstrate the effectiveness of the proposed method. Additionally, the proposed approach appears to incur higher computational overhead, yet the experiments do not include any running-time comparison.", "relation_to_broader_scientific_literature": "The paper builds on established potential-based boosting [Kanade & Kalai, 2009]. Its key innovation—decomposing the potential function’s gradient into label-dependent and feature-dependent components to leverage unlabeled data—aligns with ideas from semi-supervised learning. In doing so, it extends prior work by showing how unlabeled data can be used to improve sample efficiency in the agnostic setting. However, most of the proof techniques in this work build upon previous studies, resulting in relatively incremental contributions from a theoretical view.", "essential_references_not_discussed": "Given that the paper appears to cite a comprehensive range of related works in the field, it is likely that the authors have covered the essential literature in agnostic boosting approaches.", "other_strengths_and_weaknesses": "Strength：\nThis paper presents a modification of the potential-based agnostic boosting method by incorporating unlabeled samples, achieving improved complexity for labeled samples. The idea of leveraging unlabeled data is interesting and could offer valuable insights for further research in the field.\n\nWeakness：\nThe paper’s contribution is rather limited. Its main framework and proof techniques are based on the previous work of Potential-based Agnostic Boosting [Kanade & Kalai, 2009] and leverage data reuse from [Ghai & Singh, 2024] to improve sample complexity. In terms of proof methodology, no novel techniques are introduced. Although the work achieves improvements in the complexity for labeled samples, it does not provide enough experimental evidence to demonstrate the advantages of such semi-supervised approach in terms of effectiveness or efficiency.", "other_comments_or_suggestions": "The paper’s formatting could be further refined. For instance, Algorithm 2 is placed in the middle of page 7, which leaves excessive blank space at both the top and bottom of the page.", "questions_for_authors": "Could you explain intuitively what role unlabeled samples play in the algorithm (rather than just from the perspective of optimizing the potential function), and why their use helps reduce the reliance on labeled data? Besides, the experimental evaluation appears somewhat limited. Could you include further empirical comparisons with some recent boosting approaches?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies agnostic boosting with a focus on improving the label complexity. In particular, it leverages unlabeled samples for that purpose. The authors give an algorithm with improved label complexity, whose unlabeled sample complexity is similar to prior algorithms.  
To achieve this, the authors carefully combine existing potential-based agnostic boosting algorithms from prior work. Two applications are presented (though the one on halfspace learning over the hypercube does not improve the state-of-the-art). Most reviewers agreed that this is a solid contribution. One reviewer argued that the technical contribution may not be sufficient, as both high-level ingredients of the result pre-existed in prior work. In summary, this appears to be a contribution that meets the bar for ICML.
Decision: Accept (poster)