Sample-Efficient Agnostic Boosting
Authors: Udaya Ghai
Karan Singh
Venue: NeurIPS 2024 poster (2024)
Keywords: boosting; sample complexity; learning theory; reinforcement learning
Primary area: learning_theory
TL;DR: Improved sample complexity for agnostic boosting

Abstract: The theory of boosting provides a computational framework for aggregating approximate weak learning algorithms, which perform marginally better than a random predictor, into an accurate strong learner. In the realizable case, the success of the boosting approach is underscored by a remarkable fact that the resultant sample complexity matches that of a computationally demanding alternative, namely Empirical Risk Minimization (ERM). This in particular implies that the realizable boosting methodology has the potential to offer computational relief without compromising on sample efficiency.

Despite recent progress, in agnostic boosting, where assumptions on the conditional distribution of labels given feature descriptions are absent, ERM outstrips the agnostic boosting methodology in being quadratically more sample efficient than all known agnostic boosting algorithms. In this paper, we make progress on closing this gap, and give a substantially more sample efficient agnostic boosting algorithm than those known, without compromising on the computational (or oracle) complexity. A key feature of our algorithm is that it leverages the ability to reuse samples across multiple rounds of boosting, while guaranteeing a generalization error strictly better than those obtained by blackbox applications of uniform convergence arguments. We also apply our approach to other previously studied learning problems, including boosting for reinforcement learning, and demonstrate improved results.

Sample-Efficient Agnostic Boosting
Udaya Ghai Amazon ighai@amazona com
Karan Singh Tepper School of Business Carnegie Mellon University karans irrransinghemm... edu
Abstract
The theory of boosting provides computational framework for aggregating approx- imate weak learning algorithms, which perform marginally better than a random predictor, into an accurate strong learner. In the realizable case, the success of the boosting approach is underscored by a remarkable fact that the resultant sam- ple complexity matches that of computationally demanding alternative, namely Empirical Risk Minimization (ERM). This in particular implies that the realiz- able boosting methodology has the potential to offer computational relief without compromising on sample efficiency.
Despite recent progress, in agnostic boosting, where assumptions the conditional distribution of labels given feature descriptions are absent, ERM outstrips the agnostic boosting methodology in being quadratically more sample efficient than all known agnostic boosting algorithms. In this paper, we make progress on closing this gap, and give a substantially more sample efficient agnostic boosting algorithm than those known, without compromising on the computational (or oracle) complexity. A key feature of our algorithm is that it leverages the ability to reuse samples across multiple rounds of boosting, while guaranteeing generalization error strictly better than those obtained by blackbox applications of uniform convergence arguments. We also apply our approach to other previously studied learning problems, including boosting for reinforcement learning, and demonstrate improved results.
Introduction
striking observation in statistical learning that given small number of samples it is possible to learn the best classifier from almost exponentially large class of predictors. In fact, it is possible to do using a conceptually straightforward procedure Empirical Risk Minimization (ERM) - that finds classifier that is maximally consistent with the collected samples. Substantiating this observation, the fundamental theorem of statistical learning (e.g.. [SSBD14] 14)) states that with high probability ERM can guarantee excess population error with respect to the best classifier from finite, but large hypothesis class H. given merely Magnostic &s (log / identically distributed and independent (IID) samples of pairs of features and labels from the population distribution. Under an additional assumption- that of realizability guaranteeing that there exists a perfect classifier in the hypothesis class achieving zero error, yet quadratically smaller number Mreatizable (log ['Hl)/e of samples suffice. In the absence of such assumption, the learning problem is said to take place in the agnostic setting, i.e., under of lack of belief in the ability of any hypothesis perfectly fit the observed data.
This ability to generalize to the population distribution and successfully (PAC) learn from an almost exponentially large, and hence expressive, hypothesis class given limited number of examples suggests that the primary bottleneck for efficient learning is computational. Indeed, even with modest sample requirements, finding maximally consistent hypothesis within an almost exponentially large class via, say, enumeration or global search, is generally computationally intractable.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Sample Complexity
Oracle Complexity
[KK09]
(log [B1)/7A4
1/7882
[BCHM20]
(log [B1)//A=
1/725²
Theorem 4
(log [8]
(log [B1)//98²
Theorem 9 (in Appendix B)
(log [81)//8** + (log [B1) /72=²
1/72=²
ERM (no boosting)
(log 1B1)//22²
+00 (inefficient)
Table 1: A comparison between sample and oracle complexities (i.e., number of weak learning calls) of the present results and previous works, in each case to achieve e-excess population error. Here we suppress polylogarithmic factors. We make progress on closing the sample complexity gap between ERM, which is computationally inefficient, and boosting- based approaches. The 7-weak leaner outputs a hypothesis from the base class B, which is usually substantially smaller than H against which the final agnostic learning guarantee holds. In practice, boosting is used with learners with small values of log [B. See Definition for details. See the paragraph following Theorem in [KK09] and Section 3.3 in [BCHM20] for derivation of these bounds. See also Theorem 2.14 in [AGHM21] for bound on the expressivity of the boosted class to derive ERM's sample complexity.
is against this backdrop that the theory of boosting offers a compelling alternative. The starting point is the realization that often, both in practice and in theory, it is easy to construct simple, yet inaccurate rules-of-thumbe (or weak leurners) that perform ever so slightly better than a random classifier. A natural question then arises (paraphrased from [Sch90]'s abstract): can one convert such mediocre learning rules into one that performs extremely well? Boosting algorithms offer a positive resolution to this question by providing convenient and computationally efficient reductions that aggregate such weak learners into a proficient learner with an arbitrarily high accuracy.
Realizable Boosting. Consider the celebrated Adaboost algorithm [FS97] which operates in the (noiseless) realizable binary classification setting. On any distribution consistent with fixed labeling function (or concept), a weak learner here promises an accuracy strictly better than half, since guessing labels randomly gets any example correct with probability half. Given access to such weak learner and miraaizzble boosting Rs (log HH))/ samples', Adaboost makes s log 1/E calls to the weak learner produce classifier with (absolute) error at most any distribution consistent with the same labeling function. Thus, not only is Adaboost computationally efficient provided, of course, such weak learners can be found, but also its sample complexity is no worse than that of ERM. This underscores the fact that the realizable boosting methodology has the potential to offer computational relief, without compromising on sample efficiency.
Agnostic Boosting. In practice, realizability is an onerous assumption; it is too limiting for the observed feature values alone to determine the label completely and deterministically. and that such a relation can be perfectly captured by in-class hypothesis. Agnostic learning forgoes such assumptions. In their absence, bounds on absolute error are unachievable, e.g., when labels are uniformly random irrespective of features, in agnostic learning, the goal of the learner is to output a hypothesis with small excess error with respect to the best in-class classifier. If an in-class hypothesis is perfect a given distribution, this relative error translates to an absolute error bound, thus generalizing the realizable case perfectly. Indeed, such model agnosticism has come be lasting hallmark of modern machine learning.
classifier can achieve accuracy better than half. Instead,
Early attempts at realizing the promise of boosting in the agnostic setting were met with limited success: while they did boost the weak learner's accuracy, the final hypothesis produced was not competitive with the best in-class hypothesis. We survey some of these in the related work section. A later result, and the work most related to ours, is due [KK09]. A weak learner in this setting returns a classifier with a correlation against the true labels that is y (say 0.1) times that of the best in-class
In the introduction, for simplicity, we suppress polynomial dependencies in the weak learner's edge 7, and polylogarithmic terms. A recent sample complexity lower bound due to [GLR22] implies that this equivalence continues hold even taking into account poly(?) dependencies long is not exponentially small.

---

Episodic model
Rollouts w. v-resets
[BHS22]
1/7485
1//A80
Theorem 7
1/7884
1/79:5
Table 2: Sample complexity of reinforcement learning given y-weak learner over the policy class, for two different modes of accessing the underlying MDP, in terms of E and 7, suppressing other terms.
hypothesis. Random guesses of the labels produce a correlation of zero; hence, weak classifier interpolates the performance of the best in-class hypothesis with that a random one. Given access to such weak learner, the boosting algorithm of [KK09] makes R 1/s² calls to the weak learner and draws Magnostic boosting & (log [Hl)/=* samples to produce a learning rule (not necessarily in the hypotheses class, hence improper) with E-excess error. The dependency of the sample complexity in the target accuracy is thus quadratically worse than that of ERM. This gap persists untarnished for other known agnostic boosting algorithms too. In this work, seek to diminish this fundamental gap and construct a more sample-efficien agnostic boosting algorithm.
Our main result is an efficient boosting algorithm that upon receiving (log (H()/e² samples produces an improper learning rule with E-excess error on the population loss. This is accomplished by the careful reuse of samples across rounds of boosting. We also extend these guarantees to infinite function classes, and give applications of our main result in reinforcement learning, and in agnostically learning halfspaces, in each case improving known results. We detail key contributions and technical challenges in achieving them next.
1.1 Contributions and technical innovations
Contribution 1: Sample-effccient Agnostic Booster. We provide a new potential-based agnostic boosting algorithm (Algorithm 1) that achieves E-excess error when given a y-weak learner operating with base class B. In Theorem 4, we prove that the sample complexity of this new algorithm scales as (log /B1)/> /00////"" =0, improving upon all known approaches to agnostic boosting. See Table 1.
A key innovation in our algorithm design and the source of our sample efficiency is the careful recursive reuse of samples between rounds of boosting, via second-order estimator the potential in Line 5.II. In contrast, [KK09] draws fresh samples for every round of boosting.
A second coupled innovation, this time in our analysis, is to circumvent uniform convergence argument on the boosted hypothesis class, which would otherwise result in a sample complexity that scales as x 1/E². Indeed, the algorithm in [BCHM20] reuses the entire training dataset across all rounds of boosting. This approach succeeds in boosting the accuracy on the empirical distribution; however, success on the population distribution now relies on a uniform convergence (or sample compression) argument on the boosted class, the complexity of which grows linearly with the number of rounds of boosting since boosting algorithms are inevitably improper (i.e., output a final hypothesis by aggregating weak learners, hence outside the base class). Instead, we use a martingale argument on the smaller base hypothesis class show that the empirical distributions constructed by our data reuse scheme and fed to the weak learner track the performance of any base hypothesis on the population distribution. This is encapsulated in Lemma
Finally, while we follow the potential-basee framework laid in [KK09], we find it necessary to alter the branching logic dictating what gets added the ensemble every step. At each step, the algorithm makes progress via including the weak hypothesis or making a step "backward" via adding in negation of the sign of the current ensemble. We note that there a subtle error in [KK09] (see Appendix A), that although for their purposes is rectifiable without change in the claimed sample complexity, leads to 1/c* sample complexity here spite of the above modifications. At the leisure of 1/E* sample complexity, the fix is to test which of these alternatives fares better by drawing fresh samples every round. However, given a smaller budget, the error of the negation of the sign of the ensemble, which lies outside the base class, is not efficiently estimable. Instead, in Line 9 we give different branching criteria that can be evaluated using the performance of the weak hypothesis on past data alone.
3

---

Contribution 2: Trading off Sample and Oracle Complexity. Although Theorem 4 offers an unconditional improvement on the sample complexity. makes more calls the weak learners than previous works. To rectify this, we give a second guarantee on the performance of Algorithm 1 in Theorem (in Appendix B), with the oracle complexity matching that of known results. The resultant sample complexity improves known results for all practical (i.e., sub-constant) regimes of e. This is made possible by less well known variant of Freedman's 's inequality [Pin94, Pin20] that applies to random variables bounded with high probability.
Contribution 3: Extension Infinite Classes. Although in our algorithm the samples fed to the weak leaner are independent conditioned on past sources of randomness, our relabeling and data reuse across rounds introduces complicated inter-dependencies between samples. For example, a sample drawn in the past can simultaneously be used as is in the present round (i.e., in Line 5.1). in addition to implicitly being used to modify the label of a different sample via the weak hypothesis induced in the past (i.e., in Line 5.I1). Thus, the textbook machinery of extending finite hypothesis results to infinite class applicable to IID samples via symmetrization and Rademacher complexity (see, e-g.. (SSBD14, 14, MRTI8, 18, BBLO5]) is unavailable to us. Instead, we first derive Lı covering number based bounds in Theorem 19 (in Appendix F). Through a result empirical process theory [VDVW97], we translate these to VC(B)/7"² sample complexity bound, where VC(B) is the VC dimension of class B, in Theorem 5.
Contribution 4: Applications in Reinforcement Learning and Agnostic Learning of Halfspaces. Building on earlier reductions from reinforcement learning to supervised learning [KL02], [BHS22] initiated the study of dunciionaaproxxmmatio a weak learner over the policy class. By applying our agnostic booster to this setting, we improve their sample complexity by poly(s, 7) factors for binary-action MDPs, as detailed in Table 2. Also, following [KK09], we apply our agnostic boosting algorithm to the problem of learning halfspaces over the Boolean hypercube and exhibit improved boosting- results in Theorem 8.
compatible reinforcement learning, given access to
Contribution 5: Experiments. In preliminary experiments in Section 7, we demonstrate that the sample complexity improvements of our approach do indeed manifest in the form of improved empirical performance over previous agnostic boosting approaches on commonly used datasets.
2
Related work
The possibility of boosting was first posed in [KV94], and was resolved positively in a remarkable result due [Sch90] for the realizable case. The Adaboost algorithm [FS97] paved the way for its practical applications (notably in [VJO1]). We refer the reader to [SF13] for a comprehensive text that surveys the many facets of boosting, including its connections game theory and online learning. See also [HLR23, GLR22, AGHM21] for recent developments.
The fact that Adaboost and its natural variants are brittle in presence of label noise and lack of realizability [LS08] prompted the search for boosting algorithms in the realizable plus label noise [DIK 21, KS03] and agnostic learning models [BDLM01, MM02, KMV08, Kal07, CBC16]. In general, these boosting models are incomparable: although agnostic learning implies success in the random noise model, agnostic weak learning also constitutes stronger assumption. Early agnostic boosting results could not boost the learner's accuracy to match that of the best in-class hypothesis; this limitation tied their notion of agnostic weak learning. Our work is most closely related to [KK09, Fel10]; we use the same notion of agnostic weak learning.
Boosting has also been extended to the online setting. [BKL15, CLL12, JGT17] [7] study boosting in the mistake bound (realizable) model, while [BCHM20, RT22, HS21] focus on regret minimization. Our scheme of data reuse is inspired by variance reduction techniques [SLRB] 17, JZ13, FLLZI8, ABS23] in convex optimization, although there considerations of uniform convergence and generalization are absent, and our algorithm does not admit natural gradient descent interpretation.
3 Problem setting
Let D E A(X' (XXx(++1) be the joint population distribution over features, chosen from X,, and (signed) binary labels with respect which a classifier's h X {+1) performance may be assessed. The

---

2)e
2
Figure I: The two components the piecewise potential function ((2), with (a + 2)e plotted in blue, and 2 in red. Note that ((z) is the posnt-wise maximum of the two.
performance criterion we consider the 0-1 loss over the true labels and the classifier's predictions.
(h) IE (a.))/ [1 (h(x) * y)] P((x)))D(b(()) * y]
Relatedly, one may measure the correlation between the classifier's predictions and the labels.
corr (h)
E (a,))> [yh(())]
Note that for signed binary labels, we have that (h) = {1 corrp(h) (h)). Therefore, these notions equivalent in that classifier that maximizes the correlation with true labels also minimizes the (-1 loss, and vice versa, even in a relative error sense.
Definition (Agnostic Weak Learner). learning algorithm called a 7-agnostic weak learner with sample complexity
RR R N { with respect to hypothesis class H. and a base hypothesis class if, for any Ep, 6g > O, upon being given m(Eo, dg) independently and identically distributed samples from any distribution D' e A(X x {#1}), it can output base? hypothesis
W E B such that with probability - 6y we have
corr (W) 2 7 max corr (h) 6n- NEH
As remarked in [KK09], typically m(e, 8) ((log |B /0)/=²), and this fact in compiling Table 1. However, following [KK09, BCHM20], we state our main result for fixed Eo, 8, in Theorem 4, where necessary and irreducible Eo term shows up in final accuracy.
Although not explicitly mentioned in our weak learning definition, our algorithm falls within the distribution--peccffe boosting framework [KK09, Fel10]. In particular, like previous work agnostic boosting, Algorithm can be implemented by relabeling examples, instead of adaptively reweighing them. Thus, the overall marginal distribution of any D' fed to the learner on the feature space A the same as that induced by the population distribution on X. Under such promise on inputs, distribution-specificc weak learners may be easier to find.
4 The algorithm and main results
Notations. Given two functions f,g X + IR and generic scalars 3 E R, we use af to denote
function such that (af (z) af((x) 3g(x) for all X. Given function f X - R.
we take sign(f) (f to be function such that for all æ E X. (ign(f))z) = 1[f(z) 2 0) 1(f((z) < 0). Define filtration sequence {F, : N2o). where F, capture all source of randomness the algorithm is subject to in the first iterations. For brevity, we define E.[.] = E[-[F]]. For any feature-label dataset D, use E and corr to denote the empirical average and empirical correlation over D.
Potential function. Define the potential function - as
6(2) (2 -
if < 0, 22+2)
(I)
if > 0.
'Typically, the base class B is (often substantially) smaller than H. For example, decision stumps are common example of the base class.
5

---

Algorithm 1 Agnostic Boosting via Sample Reuse
Inputs: Sampling oracle for supported on X' {=1}, 7-agnostic weak learning oracle W, step-size 7) mixing parameter number of iterations T, per-iteration sample size S, resampling parameter m, branching tolerance т, post-selection sample size Sy. potential Φ R R.
2: Initialize a zero hypothesis H1 0.
3: fort 1 to T do
4: Sample S IID examples from the distribution DD to create a dataset D..
5: Construct sampling distribution D, that samples (z, y) uniformly from Dj if = 1, and for t > produces IID samples (æz, ý) as follows:
I
With probability o, return sample (z, ()) from Di-1-
With remaining probability o, draw r/' ~ Unif(0, 77), piek (a, v) uniformly from Dr.
construct a pscudo label ÿ = +1 with probability pr (,
with probability (,,
and return (z, 9). where
pr(a, U. r/) oe rd((HH--(())) + no (y + 1
2(1 +
6: Sample m samples from De to create another dataset D'.
7: Call the weak learning oracle on D to get W; = W (2).
8: Measure the empirical correlation of W, D as corr B: (W.) = E(EDED (W((2).
9: Set h4 /y if corr (W₂) > T else h = sign
10: Update H++1 = H, + 1/h..
11: end for
12: Sample So IID examples from the distribution D to create a dataset Do.
13: Output the hypothesis h = arg max Σ ((mn)e n, yh(x).
We this assign a population potential any real-valued hypothesis H X IR as P H)) = (x (x))]
To maximize correlation between true labels and the hypothesis H's outputs, one wants Hxx) > whenever y +1 for most samples drawn from the underlying distribution. Since ó is monoton- ically decreasing function, equivalently, higher classifier accuracy typically corresponds to lower values of population potential. However, there are limits to the utility of this argument: low value of the potential alone does not translate to successful learning. In agnostic learning, one is concerned not with the error of the learned classifier per se, but with its excess error over the best in-class hypothesis. We will provide precise relation between the potential and the excess error in Lemma 3.
We will use the following properties of ø (proved in Appendix C). Going forward, these will be the sole characteristics of & we will appeal to. The potential we use similar to the one used in [KK09, Dom00), but has been modified to remove jump discontinuity in the second derivative at 2 = 0 as our approach requires a twice continuously differentiable potential.
Lemma 2. We make the following elementary observations about 6:
ó is convex and in C²2 i.e., it is two-times continuossly differentiable everywhere. II. ò is non-negative on E. and ((0) =
III. For all z E R. o' (z) E [-1, 0). Further, for any z < 0, (2) =
IV. ó is 1-smooth, i.e., Vz E P. (z) 1
For any real-valued hypotheses H, h and on X. to case analysis, we introduce
4' h) E (yll (z))
3% (1, h) E( (v]{(=))(()))(()))
Equivalently, (H,HH,) can be characterized as the D-induced semi inner product between the functional derivative aD H)) /aH and h. But for ease of presentation, we forgo this formal interpretation in favor of the literal one stated above.

---

A key property of the above potential is stated in the next lemma (proved in Appendix C). It gives us a strategy control the relative error of the learned hypothesis. the quantity on the right, by individually minimizing both terms on the left, as we discuss next.
For any distribution D E ( x {+1)), real-valued hypothesis H X - R, and binary hypothesis h² -X- + {=1}. we have
Lemma 3.
HH.HHsign(
(H, H 2 corrD(h") - (sign(s))(H))
Description of the algorithm. Each round of Algorithm 1 adds some multiple of either the weak hypothesis W, or ) to the current ensemble H4: this choice is dictated by the empirical correlation of the weak hypothesis on the dataset it was fed. The construction of the relabeled distribution D, via our data reuse scheme ensures that if any hypothesis in the base class B produces sufficient correlation on it, its addition to the ensemble must decrease the potential d associated with the ensemble. Concretely, as we prove in Lemma 6, for all h B, corp, (h) closely tracks (H,, h). The key to our improved sample complexity is the fact that this invariant can be maintained while sampling only S = 1/ye fresh samples each round, by repurposing samples from earlier rounds to construct the dataset fed to the weak learner. The mixing parameter a controls the proportion of these two sources of samples used construct Dj.
However, this explanation is opaque when comes to motivating the need for -sign( Let's rectify that: let h" E arg minkER corro (h) be the best in-class hypothesis. If (Ht,, h²) is sufficiently large, so is corrp, (h*) by Lemma 6, which assures us a non-negligible weak learning edge. As such - ( H,, W,) is large and the potential drops. If the weak hypothesis fails to make sufficient progress, the algorithms adds - sign( H₁) to the ensemble, which, again by Lemma 6 corresponds to decreasing the potential value by some function of - 2 (He sign sign(H.)) using linearity of ' in its second argument. Thus, when run for sufficiently many iterations, because the potential is bounded above initialization both the terms on the left side of Lemma 3 must become small. This then implies a bounded correlation gap between the best in-class hypothesis, and the majority vote of the ensembles considered in some iteration; the last line picks the best of these.
O'p (H, sign ().)).
4.1 Main result for finite hypotheses classes
The key feature of our algorithm is that it is designed to reuse samples across successive rounds of boosting. The soundness of this scheme, which Lemma 6 substantiates, is based on the observation that in each round He changes by a small amount, thereby inducing an incremental change in the distribution fed to the weak learner. Although our algorithm needs total number of iterations comparable to [KK09], this data reuse lowers the number of fresh samples needed every iteration to just 1/>e,, instead of 1/?2=?, resulting in improved sample complexity, as show next.
Theorem 4 (Main result for finite hypotheses class). Choose any E, ò > O. There exists a choice O(22e/log [B)), = n/7,5 O O11/TE), = ) m m[E0, 6o) + 0(1-~²=²) such that for any 7-agnostic weak learning oracle (as defined in Definition 1) with fixed tolerance Sy and failure probability oo Algorithm 1 when run with the potential defined in (1) produces a hypothesis ho such that with probubility 1 - 105, 105T,
of n, o, T, T, So, S, m satisfying T = ( BBI)/>²²²)
250
coTl (T) Z max mOrT (h) hEH
-
7
while making T = O(log (B2) calls the weak learning oracle, and sampling TS So ((log 33)//3²²) labeled examples from D.
In Appendix B, we provide a different result (Theorem 9), also using Algorithm where the learner makes (11/22g² 2) call to weak learner, exactly matching the oracle complexity of existing results, while drawing O [ (log (B))3/7225 samples.
4.2 Extensions to infinite classes
As mentioned in Section 1.1, the reuse of samples prohibits us from appealing to symmetrization and Rademacher complexity based arguments. Instead, our generalization to infinite classes is based
è Here, the O notation suppresses polylogarithmic factors.
7

---

on L1 covering numbers. Using empirical process theory [VDVW97], we upper bound L1 covering number by suitable function of VC dimension, yielding the following result (proved in Appendix F).
Theorem 5 (Main result for VC Dimension). There exists setling of parameters such that for any for any "i-agnostic weak learning oracle with fixed tolerance Eo and failure probability do Algorithm I produces a hypothesis such that with probability 1 106 T 105T,
25u
COIT (h)
maxxoorpy (h) bEH
E.
while making T O(VC(B)/>²²²) calls to the weak learning oracle, and sampling TS + So O(VC(B)/>9$3) labeled examples from D.
5 Sketch of the analysis
In this section, we provide brief sketch of the analysis outlined in the proof of Theorem 4. Our intent is to convey the plausibility of a 1/e² sample complexity result, up to the exclusion of other factors. Hence, x and K inequalities below only hold up to constants and polynomial factors in other paramters, c.g., in y, log BB. Formal proofs are reserved for Appendix D.
Bounding the correlation gap (Theorem 4). A central tool in bounding the correlation gap is Lemma 3. We want to ensure for some i, since our algorithm at the end picks the best one, that
B/ (igg((H)) (- V (HH,,, 2 corrp(h") coirp
want Se
want Se
On the other hand, using 1-smoothness of Ø. we can upper bound dD on successive iterates as PD (DDH++1) & PD(H,) + m/p He h4) + + /27/2 Rearranging this to telescope the sum produces
Σ
V (H h4) I (l - (
2
+ ")
nT
272
nT
27²
Hence, by setting n 1/VT, know that there exists f where - (H,, h4) S 1/VVT.
In Lemma we establish that the core guarantee our data resue scheme provides: that for all in the base class B and for h", the correlation on the resampled distribution D, constructed by the algorithm tracks the previously stated quantity of interest (H,,),
Lemma 6. There exists > O such that with probability 1 for all t [T] and h E BU { we have
1 (Hi, (1 (1+2 2) coRLD (1b) sC cc(+²))
()
(vas)
1
BT 8
log
log
Vos
8
Using the definition of weak learner, we know that compD, (h") $ corrD, (W:)/7, Now, using Lemma 6 twice and the linearity of (H,-), we get
(H,, h²) S corpp, (h") + Eden S corTD, (Wi)/r + EGea X (H Ws/7) + 2
Now, if each step we could choose for {- sign (H)), W./7}, which ever maximized 2' we would have for some ł that
max ( T/D He, sign( H.)), - V H,, h1*) - 26 E - T 12),,,))11111 S1/VT
Alas, - sign(Hg not in B, thus corr (- sign( (H)) can be really far from (H,, sign H,)). i.e. Lemma does not apply to signn( H.). To cireumvent this, instead of choosing the maximizer, in the algorithm and in the actual proof, we use a relaxed criteria for choosing between W and -sign (H)) that depends on the correlation of W, on D, alone, and hence can be efficiently evaluated. The spirit of this modification is adopt -sign(Fl, H..) only if W, by itself fails to make enough progress, the threshold for which can be stated in the terms of target accuracy.
8

---

Generalization over B via sample reuse (Lemma 6). Here, we sketch a proof of Lemma 6 that ties the previous proof sketch together, and forms the basis of our sample reuse scheme. Our starting point is the following claim (Claim 10) that uses the fact that & is second-order differentiably continuous to arrive at the fact that for any and h X' R. we have
(H h) ~ D + + ( hz-1).
Simultaneously, using E,- to condition on the randomness in the first t rounds, by construction, our data reuse and relabeling scheme gives us
o² T (comVD, (h)) x (1 a corrrr. (h) o +
(H,-1,,))))
110 a a+ +
(H h,,
Thus, suitably scaling and adding the two together, we get the identity that
E, Ex-1[Ae]= = =/ (HH,, h) + (1 + ? ) Ex-1 (corTD, (h)]
(1-o))%/(l--- h) (1 o) H) coMPD
where A, = 8 () + (1 2) corp,, (h). Thus, A, forms a martingale-like sequence; the sign of A, is indeterminate. To establish concentration, we apply Freedman's 's inequality, noting that the conditional variance of the associated martingale difference sequence scales as 1/vS. A union bound over B U {h*} yields the claim. Relatedly, to reach a better oracle complexity in Theorem 9, we show a uniform high-probabblnn of Freedman's 's inequality [Pin94, Pin20] that adapt to martingale difference sequences that are bounded with high probability instead of almost surely.
on the martingale difference sequence, and then apply a variant
Applications
In this section, we detail the implications of our results for previously studied learning problems.
6.1 Boosting for reinforcement learning
[BHS22] initiated the approach of boosting weak learners to construct a near-optimal policy for reinforcement learning. Plugging Algorithm into their meta-algorithm yields the following result for binary-action MDPs, improving upon the sample complexity in [BHS22]. Here, V is the expected discounted reward of policy
V* is its maximum. 3 is the discount factor of the underlying MDP, and Coo, Doc and E, 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 v as a means to exploration. See Appendix G for complete statement of results and details of the setting.
Theorem 7 (Informal; stated formally in Theorem 22). Let W be a "y-weak learner for the policy class II operating with base class B, with sample complexity m(E0, 6g) (log /8) Fix tolerance S and failure probability 5. In the episodic access model, there is an algorithm using that uses the weak learner W to produce a policy ग. such that with probability 1- 5, we have V*-V* < (CxoE)/L (1-3)))111)))))) In the v-reset access model, there is setting of parameters such that Algorithum when given access to W produces policy गे such that with probability 1- --ô, we have V - -V- S (DocEv) 2)
3) +e, while sampling O(log /B)//33e =+) episodes of length (((13))
while sampling ((log (B) (/73)//2))) episodes of length O(11 -1-
6.2 Agnostically learning halfspaces
We apply our algorithm in black-box manner to agnostically learn halfspaces over the ni-dimensiona boolean hypercube when the data distribution has uniform marginals on features. The aim is this section is not to obtain the best known bounds, but rather to provide an example illustrating that agnostic boosting is both a viable and flexible approach to construct agnostic learners, and where our improvements carry over. Following [KK09], we use ERM over the parities of degree at most d. for d ss 1/e², as our weak learners; the the weak learner's edge here 7 d An application of our boosting algorithm (proved in Appendix I) to this problem improves the sample complexity of (8 80s ") indicated in [KK09].

---

Theorem 8. Let D be any distribution over {+1}" X {=1} with uniform distribution over features. By H = {sign(w x- (5-0) 0) (w, E [Rn+I), denote the class of halfspaces. There exists some d such that running Algorithm 1 with ERM over parities of degree at most d produces a classifier h such that (h) S (D(n) + E, while using Ole-2 000 samples in noob((14)) time.
Note that ERM over the class of halfspaces directly, although considerably more sample efficient, takes (1/e) time, i.e., is exponentially slower for moderate values of e. There are known statistical query lower bounds [DKZ20] requiring n= queries for agnostic learning of halfspaces with Gaussian marginals, suggesting that broad class of algorithms, regardless of the underlying parametrization, might not fare any better. For completeness, we note that a better sample complexity attainable by direct Ln-approximations of halfspaces via low-degree polynomials [DGJ* 10], instead of the approach taken in [KK09, KOS04] and mirrored here which first constructs an L2- approximation, but such structural improvements apply equally to presented and compared results.
7 Experiments
In Table 3, we report the results of preliminary experiments with Algorithm 1 against the ag- nostic boosting algorithms in [KK09] and [BCHM20] as baselines on UCI classification datasets (SWHB89,, HRRS99, SED+ 88], using decision stumps [PVG* 11] as weak learners. We also in- troduce classification noise of 5%, 10% and 20% during training to measure the robustness of the algorithms to label noise. Accuracy is estimated using 30-fold cross validation with grid search over the mixing weight a and the number of boosters T. The algorithm in [KK09] does not reuse samples between rounds, while [BCHM20] uses the same set of samples across all rounds. In contrast, Algorithm 1 blends fresh and old samples every round, with a controlling the proportion of each. See Appendix J for additional details. We note that the lonsphere dataset includes 351 samples, while Diabetes contains 768, and Spambase contains 4601. The benefits of sample reuse are less stark in data-rich regime. This could explain some of the under-performanee on Spambase, disregarding which the proposed algorithm substantially outperforms the alternatives.
Dataset
Added Noisc
5% Noise
[KK09]
[BCHM20]
Ours
[KK]
[RCHM20]
Ours
lunosphere
0.92 1: 0.02
0.89 1 0.03
0.97 1: 0.02
0,90
0.03
0.88 1 0.03
0.97 :: 0.03
Diahetes
0.83 1 0.03
0.78 1. 0.02
0.87 0.03
0.83
0.03
0.77 1 0.02
0.88 1 0.03
Spambase
0.69 4 0.02
0.79 0.01
0.78
0.02
0.81 0.02
0.79 1 0.01
0.78
0.02
German
0.77 + 0.02
0.75 = 0.02
0,83
+ 0.02
0.78
0.02
0.75 = 0.02
0.85 = 0.02
Sonar
0.66 +: 0.07
0.91 + 0.03
0.88 1: 0.07
0.84 0.05
0.88 + 0.03
0.94 +: 0.05
Waveforn
+ 0.01
0.78 0.01
0.91 0.01
0.88 0.01
0.77 0.01
0.90 0.01
Daraset
10% Noise
20% Noise
[KK09]
[8CHM20]
Ours
[KK09]
[BCHM20]
Ours
Ionosphere
0.93 +: 0.02
0.89 0.02
0.97 0.02
0.92 0.03
0.90 0.03
0.96 0.03
Diahetes
0.83 1: 0.03
0.78 1: 0.02
0.88 1: 0.03
0.82 1 0.02
0.78 1: 0.02
0.88 1 0.02
Spambase
0,83 + 0.02
0.80 = 0.01
0.79 0.02
0.84 0.01
0.79 = 0.01
0.79 = 0.01
German
0.78 4 0.02
0.75 0.02
0.84 0.02
0.78 0.02
0.74 0.02
0.84 0.02
Sonar
0.85 + 0.04
0,91 = 0.03
0.88
= 0.04
0.88
0.04
0.88 = 0.04
0.93 = 0.04
Waveform
0.88 1 0.01
0.77 + 0.01
0.91 + 0.01
0.88 0.01
0.77
+: 0.01
0.90 + 0.01
Table 3: Cross-validatee
accuracies of Algorithm I compared to the agnostic boosting algorithms
from [KK09] and [BCHM20] on datasets. The first column reports accuracy on the original datasets, and the next three report performance with 5%, 10% and 20% label noise added during training. The proposed algorithm simultaneously outperforms both the alternatives on 18 out of 24 instances.
8 Conclusion
We give an agnostic boosting algorithm with a substantially lower sample requirement than ones known, enabled by efficient recency-awan data reuse between boosting iterations. Improving our oracle complexity or proving its optimality, and closing the sample complexity gap to ERM are interesting directions for future work.
10

---

References
[ABS23] Naman Agarwal, Brian Bullins, and Karan Singh. Variance-reduced conservative policy iteration. In Shipra Agrawal and Francesco Orabona, editors, Proceedings of The 34th International Conference on Algorithmic Learning Theory, volume 201 of Proceedings of Machine Learning Research, pages 3-33, PMLR, 20 Feb-23 Feb 2023.
[AGHM21] Noga Alon, Alon Gonen, Elad Hazan, and Shay Moran. Boosting simple learners. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 481 189,, 2021.
[BBL05] Stéphane Boucheron, Olivier Bousquet, and Gábor Lugosi. Theory of classification: A survey of some recent advances. ESAIM: probability and statistics, 9:323-375, 2005.
[BCHM20] Nataly Brukhim, Xinyi Chen, Elad Hazan, and Shay Moran. Online agnostic boosting via regret minimization. Advances in Neural Information Processing Systems, 33:644- 654, 2020.
[BDLM01] Shai Ben-David, Philip M Long, and Yishay Mansour. Agnostic boosting. In Com- putational Learning Theory: 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference Computational Learning Theory, EuroCOLT 2001 Amsterdam, The Netherlands, July 16-19, 2001 Proceedings 14, pages 507-516. Springer, 2001.
[BHS22] Nataly Brukhim, Elad Hazan, and Karan Singh. A boosting approach to reinforcement learning. Advances in Neural Information Processing Systems, 25:33806-33317,,222.
[BKL15] Alina Beygelzimer, Satyen Kale, and Haipeng Luo. Optimal and adaptive algorithms for online boosting. In International Conference on Machine Learning, pages 2323-2331.
PMLR, 2015.
(CBC16) Shang-Tse Chen, Maria-Florina Balcan, and Duen Horng Chau. Communication efficient distributed agnostic boosting. In Artificial Intelligence and Statistics, pages 1299-1307. PMLR, 2016.
[CLL12] Shang-Tse Chen, Hsuan-Ties Lin, and Chi-Jen Lu. An online boosting algorithm with thcoretical justifications. Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 1873-1880, 2012.
[DGJ+10] Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A Servedio, and Emanuele Viola. Bounded independence fools halfspaces. SIAM Journal on Computing, 39(8):3441 3462, 2010.
DDK+ Ilias Diakonikolas, Russell Impagliazzo, Daniel M Kane, Rex Lei, Jessica Sorrell, and Christos Tzamos. Boosting the presence massart noise. In Conference on Learning Theory, pages 1585-1644, PMLR, 2021.
[DKZ20] Ilias Diakonikolas, Daniel Kane, and Nikos Zarifis. Near-optimal sq lower bounds for agnostically learning halfspaces and relus under gaussian marginals. Advances in Neural Information Processing Systems, 33:13586-11596, 2020.
[Dom00] Domingo. Madaboost: modification of adaboost. In Proc. of the 13th Conference
Computational Learning Theory, COLT'00, 2000.
[Dud74] Richard M Dudley. Metric entropy of some classes of sets with differentiable boundaries. Journal of Approximation Theory, 10(3):227-236, 1974.
[Fel10] Vitaly Feldman. Distribution-speciife agnostic boosting. Innovations in Theoretical Computer Science (IFCS), pages 241-250, 2010.
[FLLZ18] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. Advances in neural information processing systems, 31, 2018.

---

[Fre75] David A Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100-118, 1975.
[FS97] Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and application to boosting. Journal of compuler and system sciences, 19-1)91 1997.
[GLR22] Kasper Green Larsen and Martin Ritzert. Optimal weak to strong learning. Advances in Neural Information Processing Systems,
2022.
[Hau95] David Haussler. Sphere packing numbers for subsets of the boolean n-cube with bounded vapnik-chervonenki dimension. Journal of Combinatorial Theory, Series A, 69(2):217-232, 1995.
[HLR23] Mikael Moller Høgsgaard, Kasper Green Larsen, and Martin Ritzert. AdaBoost is an optimal weak to strong learner. In Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research, pages 13140. PMLR, 2023.
[HRFS99] Mark Hopkins, Erik Reeber, George Forman, and Jaap Suermondt. Spambase. UCI Machine Learning Repository, 1999. DOI: https://bb..org/10222333//33
[HS21] Elad Hazan and Karan Singh. Boosting for online convex optimization. In International Conference on Machine Learning, pages 4140-4149 4149. PMLR, 2021.
[JGT17] Young Hun Jung, Jack Goetz, and Ambuj Tewari. Online multiclass boosting. Advances neural information processing systems, 30, 2017.
[JZ13] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26, 2013.
[Kl07]] Satyen Kale. Boosting and hard-core set constructions: simplified approach. In Electronic Colloquium Computational Complexity (ECCC), volume 14. Citeseer, 2007.
[KK09] Varun Kanade and Adam Kalai. Potential- based agnostic boosting. Advances in neural information processing systems, 22, 2009.
[KL02] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings the Nineteenth International Conference on Machine Learning, pages 267-274, 2002.
[KMV08] Adam Tauman Kalai, Yishay Mansour, and Elad Verbin. On agnostic boosting and parity learning. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 629-638, 2008
[KOS04] Adam R Klivans, Ryan O'Donnell, and Rocco A Servedio. Learning intersections and thresholds of halfspaces. Journal of Computer and System Sciences, 6884):808-840 2004.
[KS03] Adam Kalai and Rocco A Servedio. Boosting in the presence of noise. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 205-205, 2003.
[KV94] Michael Kearns and Leslie Valiant. Cryptographic limitations on learning boolean formulae and finite automata. Journal of the ACM (JACM), 41(1):67-95, 1994.
[LS08] Philip M Long and Roceo A Servedio. Random classification noise defeats all convex potential boosters. Proceedings of the 25th international conference on Machine learning, pages 608-615,4 2008
[MM02] Yishay Mansour and David McAllester. Boosting using branching programs. Journal of Computer and System Sciences, 64(1):103-112, 2002. 2002.
12

---

[MRT18] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[Pin94] Iosif Pinelis. Optimum bounds for the distributions martingales in banach spaces. The Annals of Probubility, pages 1679-1706, 1994.
[Pin20] Iosif Pinelis. Extension of bernstein's 's inequality when the random variable is bounded with large probability. MathOverflow, 2020. URL.hups//maathverfooveee////// (version: 2020-09-11).
[Put14] Martin L Puterman. Markov decision processes: discrete stochastic dynamic program- ming. John Wiley & Sons, 2014.
[PVG 11] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blon- del, P. Prettenhofer, Weiss, V. Dubourg, J. Vanderplas, A. Passos, Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825 22300, 2011.
[RT22] Vinod Raman and Ambuj Tewari. Online agmostic multiclass boosting. Advances in Neural Information Processing Systems, 35:25908-2599 2022.
[Sch90] Robert E Schapire. The strength of weak learnability. Machine learning, 5:197-227,
1990.
[SED 88] Jack W Smith, James E Everhart, WC Dickson, William C Knowler, and Robert Scott Johannes. Using the adap learning algorithm forecast the onset of diabetes mellitus. In Proceedings of the annual symposium on computer application in medical care, page 261. American Medical Informatics Association, 1988.
[SF13] Robert Schapire and Yoav Freund. Boosting: Foundations and algorithms. Kybernetes, 42(1):164-166, 2013.
[SLRB17] Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162:83-112, 2017
[SSBD14] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory algorithms. Cambridge university press, 2014.
[SWHB89] Sigillito, Wing, L. Hutton, and K. Baker. Ionosphere. UCI Machine Learning Repository, 1989. DOI:
[VDVW97] Aad W Van Der Vaart and Jon A Wellner. Weak convergence and empirical processes: with applications to statistics. Springer New York, 1997.
[VJ01] Paul Viola and Michael Jones. Rapid object detection using a boosted cascade of simple features. In Proceedings of the 2001 IEEE computer society conference computer vision and pattern recognition. CVPR 2001, volume 1, pages I-I. leee, 2001.
13

---

Appendix
Limitations. The primary contribution of this work is theoretical. Extensively demonstrating the empirical efficacy of the proposed approach and fully characterizing when it fares best is left to future work. Further, in comparison to realizable boosting (with or without label noise), the existence of an agnostic weak leaner here is a stronger assumption. Nevertheless, we believe, especially given the recent interest in agnostic boosting, the current work presents a substantial and concrete improvement over the state of the art, and is first step in making agnostic boosting practical.
Organization of the appendix. In Appendix A, we point out an error in the branching criteria in [KK09]. Next, in Appendix B, we give second guarantee on our algorithm that improves the oracle complexity at vanishing (in e) cost to the sample complexity. In Appendices C and D, we prove the main result and the lemmas leading up it. Appendix E provides prrvvdddeeoviiisss a proof of the improved result in Appendix B. Appendix F furnishes proof for the claims concerning extensions to infinite classes. In Appendices G and H. we define the reinforcement learning setup, formally state the RI. boosting result along with accompanying algorithms, and prove it. Appendix substantiates our improved sample complexity bound for learning halfspaces. Finally, in Appendix J, we provide additional experimental details, and Appendix K provides practical guide for adapting the proposed algorithm.
A Branching criteria in [KK09]
At high level, the boosting algorithm in [KK09] is iterative one, that adds either the weak hypothesis or the negation of the sign of the present ensemble to the ensemble mixture in each of the T x 1/e² rounds. The algorithm makes use of samples to fulfill two objectives: (a) provide m = 1/E² samples to the weak learner to obtain a weak hypothesis that generalizes, (b) use s zs 1/E² samples to decide whether to add the weak hypothesis or the voting classifier to the current mixture, by comparing the empirical performance on both on said samples. The algorithm uses fresh samples for part (a) every round; this is sound and contributes T'm x 1/5² to the net sample complexity.
However, as described in [KK09], the algorithm reuses the same s samples for part (b) across all rounds. This means these samples determine which of the two choices gets added to the mixture at the end of the first step, and hence H1 In the next step, however, because H[, through relabelling of new samples determines the weak hypothesis, these samples are no longer IID with respect to the weak hypothesis or - sign( H1), since they have already played a demonstrable part in determining it. This effects occur and compound at all time steps, not just the first. In the analysis, on top of page 7, the analysis in [KK09] uses a Chemoof--ocffding Hoeffding bound to say that the performance of the weak hypothesis and sign(HH on these samples transfers approximately to the population. However, this incquality may only be applied to IID random variables.
In the case of [KK09], there is simple and satisfactory fix: resample these s examples from the population distribution every round. The sample complexity. now T (m + s) instead of Tm + s, remains (1/5"), and no change to the performance gurantee needs to be made.
In our adaptation, this highlights an additional challenge. Even if one were to sate the weak learner with a total fewer number of samples, i.e., perform part (a) with fewer samples, through a uniform convergence result on the base hypothesis (crucially, not the boosted hypothesis, whose complexity grows with number of iterations), part (b) requires fresh samples, and hence 1/E" samples in total, in determining which of the weak hypothesis or -sign of the ensemble provides greater magnitude of descent. Here, note that sign(H, lies outside the base class. To circumvent this, we give branching criteria to decide which component add to the present mixture, based on the performance of the weak hypothesis, the only component whose performance is estimable with bounded generalization error, alone on the reused data. Concretely, we introduce threshold 7 to choose the weak hypothesis, if it makes at least 7 progress, and otherwise, choose - -igu( (H,) even truth it is worse than the weak hypothesis. This deviation requires careful handling in the proof.
B Improved oracle complexity
Here, we provide a different result where Algorithm makes O(1/?²²2) call to weak learner, matching exatcly the oracle complexity of existing results, while drawing O(log &
14

---

(log />))/ samples. Notice that the second term in the sample complexity has a smaller order, whenever is sub-constant. The proof may be found in Appendix
Theorem 9 (Improved oracle complexity for finite hypotheses class). Choose any e, 8 > There exists a choice of a. T. So. S. m satisfying T = ((1/n"="),
((72E), = n/7.T = m(E0. 6g) + -(L/7722) such that for any y-agnostic weak learning oracle (as defined in Definition 1) with fixed tolerance so and failure probability dg. Algorithm I when run with the potential defined in (1) produces a hypothesis such that with probability 1 10 108T,
O(je), (log [B))/T= + (log BI) S. O(1)E²).
2Eu
corrD (h) 2 max COTT (h) bEH
7
while making T = (11/72²²) calls to the weak learning oracle, and sampling TS + So ((log {))) + (log [81)) (?>2=2)) labeled examples from 'D.
C Proof of auxiliary lemmas
Proof of Lemma 2. Part 2 is evident from the definition. Taking care that right and left first (and second) derivatives exist and are equal at z = 0, by explicit computation, we have
if S 0, ('(:) [-1 (((++1)e if = 0,
0 if $ 0,
x²(2)
ze== if 0.
From this, one may immediately verify Part 1, since ø" is non-negative. Non-negativity of ø" also implies that o' is non-decreasing, and hence, being clearly non-positive, is between [-1, 0]; this is Part 3. By elementary calculus, ø² is maximize at 2 = 1 where it equals 1/c implying the conclusion in Part 4.
Proof of Lemma 3. By the definition of D' we have (ign()))))))))))))))) D (H,
(2)) - (x))
=E -B 1 2 ( h² h²(x))
(ey) (y) < (y)))((( (H) h (z))
Note that whenever (x) < 0, ((()(x)) = 1, which Lemma 2.11I attests to. On the other hand, if (x 2 0, since h" is a binary classifier, usign(H)) = 1 2 yh"(z)) (x), and since, again by Lemma 2.I1I, (x)())) 1, have in this
d'yy (z) (sign(((()((()) h² 2 (() hx))))
Plugging these into the previous derivation, we arrive at
(H,, sign((1) 4% h²) > B ([(H 2 0)v(h" (x) sign sign(()((z))
+ E 11 (x) < 0)v(h((x) (gg(H)(())
= =B - sign/f (x))
-orrp(hi) (oonossign(nnn))
finishing the proof of the claim.
D Proofs for the main result
Proof of Theorem 4. Let h+ arg minngw corp (h). Using the update rule for H441 and the fact that o is 1-smooth (Lemma 2.IV), we arrive at
( =
+ n)h(())))
< B(rn)~D (0lyl1, (z)) + nyo' (yIl (nha(z)u)²/22 /2]
< d (1)) + t H, h4) + /222
15

---

using the definition of l/D, and that h is either binary classifier, or a 1/y-scalld version of it. Rearranging this to telescope the sum produces
(i +D (bD(He+1)) + "
V (He, ha)
T
n/T
272
7 n/T 2y
(2)
where we use the fact that @D( 2, and that it is non-negative (Lemma 2.11).
Hence, 31 E [T], such that - he) is small. Our proof strategy going forward to use this fact to imply that both the terms on left side of inequality in Lemma 3, namely, ( (-sign(HH,) (),) and - l(),, are small for some t, implying a small correlation gap on the population distribution.
Note that if co (W)) 2 the algorithm sets h2 = We/r, else it chooses h2 signn H2). We analyze these cases separately. For both, Lemma which relates the empirical correlation on Dr with &'D will prove indispensable. Going forward, we will define EGen as indicated above to capture the generalization error over the base hypothesis class.
For brevity of notation, we condition the analysis going forward on three events. Let & be that event that for all t, coorp, (W,) co (Wa) S e//10. Since D', is constructed from IID samples from
Dr, setting m 2 100/s²² Vlog T/6, Pr(EA) 2 1 -, by an application of Hoeffding's 's inequality and union bound over Here, note that unlike S setting a higher value of m doesn't increase the number of points sampled from DD since D is resampled from already collected data. Similarly, denote by ε the event that for all L, (corr(ssign) H.)) corr D. (sign( H.)) S e" 31/ Again, by Hoeffding's
inequality and union bound over choosing Sn 100/="² / /lo T/ō, we have Pr(En) 2 8,
since the samples in Dy were chosen independently of those used to compute Hy's. s. Finally, we will take the success of Lemma 6 (call this Ec) for granted in the analysis below, for brevity of notation, conditioning our analysis on all three events.
Case A: When h1 = We/7. When this happens, corPD, (W)) 2 co (W.) - E + EE'/10. Applying Lemma 6 and noting that (H,,), is linear in its argument, we have
W. ) = /b(( (H, Wi)
T
H 7
1 ? ) CorTD (W,)
EGn Y
2 7
1
[1 + 2)
(T
E'
&Gn
> ア
10
Rearranging this
T/D He. We
1 + 7) - ạ
6'
EGen
+
10
?
Case B: When h4 sign(HH He). Here compD (W) I coIT (W)) + //110001 S T e//10. Applying
Lemma 6, and using the weak learning condition (Definition 1), we have that
(1+ ")
(
e'
[ ") corp,, (W;)
10
2 & 1 + " ") corLD, (h*) - (1 " ") eu
2 - 2 He h²) - (1+ ")
σ) Eu YEuen
Now, we invoke the linearity of 4% HH,) -) and Lemma observe that V/ (H,, -iign(H.)
= - D He, (H.)
< (He, h²)) (horrp(h") corr corro (H.))
S --corro - (sirn (H.))) + (1 (1+ 2) (
T+ E
+ +00
+ GGen
10
(4)
16

---

Combining the two.
In either case, combining Equations (3) and (4), we have
1 (1 ") (T E'
(HH max
Gen
7
10
7
(coTTo(h") - coITD (sign H()) + 1 (1 (1+ ") (++
&
+ E0 + EGen
7
10
or using the identity max(-f(x))) min f(x).
1 - ") (7
EGen
- ( 2 min
10
(corrp(h") corrp(sign (Hr)) (1+ /) (T-
E'
+ +
-Gen
10
Now, set
-= 1
-1
+
+
SGnn
7 10'
s'
1/T
72
7
Now, either there exists some / such
corrp(h") - corr (sign( (H.)) S
-
1
(1
?
(2r +
60)
+ (1- 1 7
(1-
EGn
7
8
2m
+
1
Gen + (1+ 2
E0
+ (5)
e'
nT
x2
?
5y
or the minimum operator in the last expression always accepts the first clause, in which case for all t,
(HD, ht) 2 (1+ (T (T-
5'
EGen
4
y
10
7
(n/T)
722
which contradicts Equation (2). Henceforth let be the iteration for which Equation (5) holds.
Finally, given the event εB, we have
2 (sirn(sig((H,))) E"
corp (h) COIT Do hh)
corr Do (sign (H()))
10
10
5
Compiling this with the inequality in Equation (5), we get
2nj 722
26Gen
1 (1
5² 8" ") co
corr-(h")) corr (h) -
+
T/
7
5
Setting 5' E/57, E" e/5 and plugging in the proposed hyper-paramett with appropriate constants yields the claimed result.
Proof of Lemma 6. Fix any hypothesis h E B. For any T/ 2 define H Hr + 1/ he, and
A, = (H, + 1 ") ELn.WwDD [uh(x)].
First, we derive recursive expansions of / ( He, ht) and D., the two quantities wish relate.
Claim 10. For any and R, we have
(H,, h) (H,,,,,, h) + um (%% h, hz-1)).
Claim 11. For any t,
[y][
o² 2 (11-111)
(1 - σ) () [uh(z)]
110
Ey Uni un) (H h,, (2- 1)],
+
+
17

---

Adding (1 + t/oo) times the last expression to the expansion of D h), we have
E (HH,, /) - [ (B..))) [bh[))]]
(1 σ) / ( (H + (1 σ) (1+ ? ") B (( [yh(x))
= (1 A-1
Using this, we conclude that A = (1 0) '' " forms martingale sequence with respect to the {Fr :t N20} filtration sequence, A Et-1 [[1 " o) A A The associated martingale difference sequence 8/ A A can be bounded both in worst-case and second-moment terms show next.
Claim 12. For all t. 18,1 < (1 - o) '2(0 + n/7) and E.-1 s a11a)22'
8lo2+1
Now, we ready apply Freedman's 's inequality for martingales.
Theorem 13 (Freedman's 's incquality [Fre75]). Consider real-valued martingale {Yx k Zzo} with respect to some filtration sequence {Ex k E Zzoh, and let {Xx: E ZZ be the associated difference sequence. Assume that the difference sequence is uniformly bounded: [X S R almost
surely for k E Z20. Define the predictable quadratic variation process: Wa = Σ3 Ej (X3)
for k E Zso. where 1.) = EE)))) Then, for all t 2 O and 0² 0.
Pr Ek 2 0: Y 2 and Wx I o0) I exp {
- 0² + Rt/3
Applying Freedman's inequality to A since the total conditional variance of our martingale differ- ence sequence is bounded almost surely as shown before, we get for any
4(1 4(1 -0) (a 1
2
2 8
log
log
Vos
that
2
8(0² + /22)
2( + /////r
}
Pr(A/ 2 r) & exp
+
$
2
a(1 0)20
(1 (1-o)² o)¹
Hence, using 4 = -),, with probability 1 5, have
A o 7)
( Vos
2 + log 2 8
log 8 V
Taking a union bound over the choice of h from {h*} and over t, along with repeating the argument the martingale A, furnish the promised two-sided bound, concludes the claim. Li
Proof of Claim 10. Using the fundamental theorem of calculus and that C², which Lemma 2.1 certifies, we get
h),
= =E (())(())))))(
= E (6' (y(y((,- the
= (I 06 (z)) ("
= ( (6' (0(yy Fean (yHH)
= (H(--11) +y (*% H h, h+-1)]
where use the fact that for binary labels y { 1, 1}, y² 1, and the definitions of 4 and 4%
18

---

Proof of Claim 11. First, we establish recursive structure on the random random distribution D, without any conditional expectation in place.
Claim 14. For any 1, we have
((aa))DD, [yh(æ)) (LN [yh(x)] 0o (odl)l + (0d
o 0+ 16 (ax))
Using the fact that D. identically samples data points from D, we arrive at
E (z_ [yh(2)]]
= B ((.))) [gh(z))
+ n7
Ey Lni (
17 E -
o²
-(1 - 0 ( [0((z)]
a+ V H h))
110
Eny Uniroii (0' h, h2-1)].
o +
Proof of Claim 14. By the definition of D., we have
(x,,)) [19(())]
=(1 ((E))))) [yh(x)]
oB (aw)~ M(x)
(-i x+
- o Eyy Uoitoo ("OF)
=(1 -()) lyh(x)]
0o (yHH- + "o"" (ddp 0 +1 E (aN)
where in the first equality we use the fact that for any binary random variable Y supported on 11, with Pr(Y 1) p. have Y| 2p 1.
Proof of Claim 12. Using the recursive expansion of V'P (Claim 10) and D, (Claim 14), we have
8, ( o)
(1 (/
+ (1 -² (1+ ") (B(z,g)~ - (1- -11- loh(x)))
=(1 -) (7 (T h1) + By / (+% ( h bb-1))
(1 - BB (o. 0 (y'ly (I) + Bl 10 (())
-(1 -o
h) -E (a, (6 (yH+-
(1 -) (Ey/uuatjo.n) (% h, (. 16" (11T"
Using Lemma 2, Φ'. x" are uniformly bounded in magnitude by one, (H,,,) .) and 4% (H, are uniformly bounded magnitude by one for any X IR and 1/7-uniformly bounded function Hence, [8]] < (1 a) -220 + n/7)). To bound the conditional variance, we use the identity
19

---

(a la2 - 2a + 2b2 in the first line below to show
Ex-1[6,-]
<2(1 - oo) E (' (.,))- (aan)),,o'((HHaao... [d((H(-
+ +1 E Byy Buy'-Unif m/ [8' ( h 11-1) E (m (0 )
-2(1 - 21 (' (o/ 11, h) 0'
Ey ( + B(
( h1-1) - -0" (0
8 + /
(1-0)2t5
where we use the fact that the S samples consisting Dr are independent and identically sampled from DD conditioned on Fi-1 in the second equality, and that the expectation of any function over Dr is the equivalent sample average. Finally, using an identity on geometric sums, we get
8(0² + 12//22 -1-)) -)- - 8(0² 11 S
Σ F. 18:9
1
S
(1 (1-0)-2-
a - 2
where we appeal to the inequality 1 - (1- 0)² = 20 - o² 2 a for any E [0,1].
E Proofs for improved oracle complexity
Proof of Theorem 9. The overall proof is similar to that of Theorem 4, with the exception of the following bound Gen, which state now (and prove next) in lemma relating the empirical correlation on D, with 4 The principal difference between Lemma 6 and Lemma 15 is the presence of a 1/V5 in both terms the right in Lemma 15, however this comes at the cost of higher polynomial dependence in log [B] in the second term on the right side of Lemma 15.
Lemma 15. There exists 0 such that with probability for all E [T] and h E BU {h*}. we have
/ (H,, h) (1+ ") corLD, (1) sC
cc (o+"))
( Vos
1
B
1
B
3/2
log
log
Vs
8
From here, with the new definition SGen as defined above, identically following the steps in the proof of Theorem 4, which we skip to avoid repetition, arrive at
2n
28Gen
1 (1 (1-")
2) Eo
s" 5
(h") comp (h) I
T/
7 7
Setting E' E/5%, e" e/5 and plugging in the proposed hyper with appropriate constants yields the claimed result.
Proof of Lemma 15. The proof of the present lemma is largely similar to that of Lemma 6, with two exceptions: (a) we use variant of Freedman's inequality that applies when the martingale difference sequences (for us, 8 are bounded with high probability, instead of admitting an almost sure absolute bound; (b) to apply this result, we establish high probability upper bound on & that scales as 1/ 1/Vs.
Fix any hypothesis
B. For any n¹ 2 O. define H. He + n/ and
A, T'D (H.
H..h) h1) + (1+ ") E B. [yh(2))]
20

---

As before, adding (1+ n/o) times the expression in Claim 11 to the the expansion of 4 (0,,,),)))) in Claim 10, we observe that E
o) م and hence conclude that A (1 - forms martingale sequence with respect to the (Fa E N2o) filtration sequence. As shown in Claim 12, the associated martingale difference sequence 8 ب - admits a total variance
bound of E'= F [
[
8(o*+n"//²) alI-0)='
Now, we state a variant Freedman's inequality that applies when martingale difference sequences are bounded with high probability.
Theorem 16 (Freedman's inequality with high probability bounds [Pin94, Pin20]). Fix a positive integer n. Consider real-valued martingale {Yı l E Zz0} with respect to some filtration sequence {Ex: : k Zzoh. and let {Xx k E Z be the associated difference sequence. Assume that the difference sequence is uniformly bounded with high probability for some R, 8':
Pr
max kEIn
X&l > R
S
Define the predictable quadratic variation process: W, == Σj=1 E)= Ba-1Ej-1 Ex-((X3). where Ez-1(.) = B( (E))) Then. for all t 0 and o² 0,
-12/2 0² + Rt/3
Pr (Y, 2 and W, s S exp
{
+ +
To apply this variant of Freedman's 's inequality, we establish a high probability bound on A, that is,
ignoring logarithmic terms, substantially better than the almost sure bound in Claim 12.
Claim 17. There exists a universal constant C, such that for any t, we have
Pr
max
6 2 [1 - o²
a +
7
log
S 5.
sE(H
VS
Combining this with the almost sure bound on the total conditional variance of our martingale difference sequence, we get for any
C
2/ 3/2 8
2 4(1 o)- 0
max
log
log
(vas
8" vs
that
Pr(A/ 2 r) < exp {- 1.2) (1²)
{ ((/)
88 +7/22)
+ (1 -1-08 o' V log
C(o + n/7)r
}
+ 5 28.
a(1 011-5)
Hence, using = = - o) A,
'A,, with probability 1 - 28, have
A, $4 a (o+")) (visV log
(5((0+))
V
2 C
21 3/2) 5
+
log
8 VS
Taking a union bound over the choice of h from BU ( and over I, along with repeating the argument on the martingale -A, to furnish the promised two-sided bound, concludes the claim. D
21

---

Proof of Claim 17. The proof begins similarly to the one for Claim 12. Using the recursive expansion of D (Claim 10) and D, (Claim 14), we have
5 o) ( (H h) - -1--0) (HHb
+ (1- (1+ 2) ((c2,))>,.lubll)) - -1- (atp::aaaphitt)0000------------ ()
-(1 o)
(0 (o (H,-1: + By 1y ( Me,,,,1111 me-1))]
(H
(1 1 -) (ay)) -o0' ( n - lo (1)))
-(1 o ('D(H--111)) -B (.,) D. (d(1
+ (1 o1- Un h, hw-1) B (a.)) (t)"
However, this time, we note that, conditioned on Ft-1. An and A₂ are averages of S zero-mean IID random variables, where each constituent is absolutely bounded by one in magnitude (Lemma 2).
Hence, by Hoeffding's 's inequality, with 1 - -25, we have that
100
2 8
max (|A1), |22 S
V
log
VS
Note that since this statement holds true for all realizations Fi-1 in words, it a statement about the randomness in the present round alone- - it remains true when not subject to such filtration's 's, i.c. by marginalizing over Ft-1. A union bound over now yields the claim
F Proofs for extensions to infinite classes
Definition 18 (Covering number). Given a set F in linear space V, a semi norm ||-|| on V. V.N((,, F, II-II) the size of the smallest set 9 such that for all f F, there exists a g E 9 such that [|. gll S..
Proof of Theorem 5. First, we state (and subsequently prove) the following sample complexity result using L1 covering numbers. We note that may be possible improve this result for specific classes of functions, i.e., monotonic functions, by applying chaining techniques [Dud74] to L2 distances.
Theorem 19 (Main result for Covering Number). Define TA TA, RE l1(( g(=))),, for any two functions f,g X -> IR, where x is the marginal distribution of on the features set X. There exists a setting of parameters such that for any for any 7-agnostic weak learning oracle with fixed tolerance Eu and failure probability 8u. Algorithm I produces hypothesis h such that with probability - 108,T 105T,
2Eu E;
coTTD (h) 2 max COLT 4EH
while making T = O(logN(ee/10; B, Tn, ))/-2²)))))))))))))))))))))))) calls to the weak learning oracle, and sampling TS So N(Ee00, B, ))²) labeled examples from D.
The claim follows immediately by the application of the following result from [VDVW97] to place an upper bound of the L, covering in terms of the VC dimension in Theorem 19. This result originally due to [Hau95] was established for distances defined by n-point empirical measures, for some finite n. The version in [VDVW97] works on arbitrary distributions, by first proving that by result proven for empirical-type measures transfers without loss to any distribution.
Theorem 20 (Theorem 2.6.4 in [VDVW97J) There exists universal constant C such that for any VC class B, any probability measure Dx, and 0 < S 1,
Nie, L,, S C. VC(B)- (
4e
vC(B)
22

---

This concludes the proof.
Proof of Theorem 19. We first invoke Lemma 6 but on minimal Ecovr (say Beov) of with respect the L, semi norm to get that there exists C' > 0 such that with probability 1 6, for all & E [T] and h E Bo U Uhh". we have
4 (HH + (1+ ? ") comp,, (h)
3 C + 2)
1
log T FlogN((ECo ( B, L1
T Tlog N( B, L1.Dx)
log
Vos!
6
Fix any 9 B. Now, by virtue of the Cover, there exists h B such that L1 (ewDx(l/(x)) g(x)l] & &Co- Now, using the definition of T and uniform (absolute) upper bound on o' (Lemma 2.III), we get
1 ( h) T (Hi =
g()))]
I (yH((() (h(x) s(x)
3 B(e,))>Dl((()) 9(x)]
$ BZ~Dx [1((z) - g(+)]l I Ecov-
Similarly, using the fact that the marginal distribution of Dj on X is the same as Dx we get
Ioomp, (h) comp, (g) < EE | [(() - g(=)ll I ECov
Combining these, have that with probability for all (7) and h Boov U (h*), we have
(H,,,, + (1 + ") corp,, (ni) S E + 22cov-
From here, proceeding identically as the steps the proof of Theorem yields
1 2n 2(E Ecor) + ト 1 (1+ ") (co (co+ 7/2
8' E"
corpp corr S
+
nT
3
5
Setting E' =//5,, e" e/5, coov = e/ 10y and plugging in the proposed hyper-parameters with appropriate constants yields the claimed result.
G Boosting for reinforcement learning
MDP. In this section, we consider a Markov Decision Process M = A,, po). where S is set of states, AA (=1} is a binary set of actions,
A - [0, determines the (expected) reward at any state-action pair, P S x A + S captures the transition dynamics of the MDP, ie.. P(s'|s, |s. a) is the probability of moving to state s' upon taking action at state s, [0, 1) is the discount factor, and μı is the initial state distribution. Without any loss, one may restrict their consideration Markovian policies [Put14] of the form S - A(A), where an agent at each point in time chooses action at state independently with probability x (a|s).
For any state s E S, action A, and distribution μ state-value functions as
A(S) over states, define state-action and
Q" (8, E
g'r at) n. 0.
V=(s)= E
8'r(se ad)
T..
V/2 = E Earny (s)
23

---

Algorithm 2 RL Boosting adapted from [BHS22]
1: Input: iteration budget T, state distribution μ4, step sizes 7]t, post-selection sample size P
2: Initialize a policy To E II arbitrarily.
3: for t = 1 to T do
4: Run Algorithm to get o/,, while using Algorithm to produce a distribution over state-actions
(ignore Q) by executing the current policy π--1 starting from the initial state distribution 5: Update 7e (1 17 = + 7/
6: end for
7: Run each policy ni for P rollouts to compute an empirical estimate V of the expected return.
8:
return क. == Te where 1' = arg max; V
We will abbreviate no0 V* since it captures the value of any policy starting from the canonical starting state distribution. Finally, the occupancy measure 1/ induced by policy starting from an initial state distribution j is stated below. We will take μ²' Mig matter of convention.
Accessing the MDP. Following [BHS22], we consider two models of accessing the MDP; we will furnish different result for each. In the episodic model, the learner interacts with the MDP in limited number of episodes of reasonable length (i.e., = (1 3) })) and the starting state of MDP is always drawn from /40- In the second, termed rollouts with v-resets, the learner's 's interaction is still limited small number of episodes, however, the MDP now samples starting state from v. is important to stress that in both cases, the learner's 's objective is the same, to maximize V starting from fo- However, could be more spread out over the state space than Mgg, and provide an implicit source of explanation, and the learner's guarantee as shown next benefits from its dependence milder notion of distribution mismatch in this case.
Weak Leaner. For convenience, we restate our weak learning definition, this time using π to denote policies, instead of Note that our definition is equivalent to that used by [BHS22], because for binary actions a random policy induces an accuracy of half regardless of the distribution over features and labels. One may use the identity comp (α) 1 2/p (TT) to observe this. In fact, our assumption of weak learning might ostensibly seem weaker, since it operates with 0/1 losses (equivalently, correlations), whereas the losses in previous work are assumed general linear. However, for binary actions, this difference is insubstantial and purely stylistic.
Definition 21 (Agnostic Weak Learner). A learning algorithm is called y-agnostic weak learner with sample complexity m : R4 x I - N U (+oo) with respect policy class II and base policy class B if, for any &a, 6n > 0, upon being given m(5o, 5o) independently and identically distributed samples from any distribution D' E A(X {=1]), can output base policy W E B
such that with probability 1 1- 6o we have
corpp (W) 2 7 max COIT (T) - ED-
sEnl
Policy Completeness and Distribution Mismatch. x' E arg max, V be reward maximizing policy, and V be its value. Let 01 be the convex hull of the boosted policy class, i.e., the outputs of the boosting algorithm. For any state distribution μL, define the policy completeness E, term as
En/ = max min E Esnpy, mmx (* Enw Q" (" as) TEn T'ElI
"E.A
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 IT. Finally, we define distribution mismatch coefficients below.
Cos = max || /p= Dxo = / nEll
Theorem 22. Let W be a w-we learner for the policy class II operating with base class B, with sample complexity m(Eo. ôu) (log [ / Fix tolerance and failure probability 5. In the episodic access model, there is a setting of parameters such that Algorithm 2 when given access to W produces a policy n such that with probability 8, we have
CooE
4"- " <
+
24

---

Algorithm 3 Trajectory Sampler adapted from [BHS22]
Sample state sg ~ I and action a' Unif([A).
2: Sample ~ 4 as follows: at every step h, with probability 3. execute и,; else, accept Sy.-
3: Take action a' at state 84, then continue execute 9, and use termination probability of Upon termination, set R(s), a') as the sum of rewards from time h onwards.
4: Define the vector Q such that for all A, (aa) 2R(8h; a') Ila=a'-
5: With probability CQ(a'), set y = a' else set A - {a'}, where = =1 (1-3)/2.
6: return (sh, v.
while sampling
( C log [B]
31923 (1-9)
episodes of length (((1- - 1) In the y-reset access model, there is setting of parameters such that Algorithm 2 when given access to W produces a policy a such that with probability we have
EooEv 81-
V V
+ t,,
while sampling
D3 log [B] 00
(1 15335
episodes of length O((1-3)
(01 1)
H Proofs for boosting for reinforcement learning
Proof of Theorem 22. The proof here closely follows that of Theorem 7 in [BHS22], and we only indicate the necessary departures. Since utilize the outer algorithm from previous work, the associated guarantees naturally carry over. The departure comes from our substitution the internal boosting procedure in Algorithm with Algorithm 1; in fact, in its place [BHS22] use result of [HS21] which can be seen as a generalization of [KK09], e.g., it uses fresh samples for every round of boosting, to other non-binary action preserving its 1/e* sample complexity. In this view, the improvement in sample complexity by using the present paper's apprach seems natural.
For the episodic model, applying the second part of Theorem in [BHS22), while noting the smoothness of V", and combining the result with Lemma 18 and Lemma 11 in [BHS22], we have with probability 1 - 78
CooE V v
+ 402
Coo ( max (... (#(+1s) ( =(((1s)) (ELLLEETT 1-
1- B (1 (1- 3)3
where n. is the output of the internal boosting algorithm in Line of Algorithm 2, and D, is the distribution produced by Algorithm with π; selected as the policy for execution. Here, by explicit calculation, noting a' ~ Un) one may verify for any that
E Le [uls] 1-3
(.. ((-1)-@((1111)))
Recall that = (+1), and hence π S (0->((+1)))) (((+1)). Hence, for any policy pair Tı, T2 we have
(1-3)B, (x. (L. QQ (TT(- (2(+(s)) E B..
(x) (a az)].
Therefore, all we need to ensure is that output of Algorithm I as instantiated in Algorithm 2 every round has an excess correlation gap over the best policy 1I no more that (1 // which samples. The total number of
Ca log [8] Algorithm assures us can be accomplished with [1 (1-3)"76"
C2
samples = (
times greater.
25

---

Similarly, for the v-reset model, applying the first part of Theorem 9 in [BHS22], and combining the result with Lemma 19 and Lemma 11 in [BHS22], we have
Doo
2Dx0
Doo
v* x
(2 - (EIILE(TT]
max
(1 B)2
(1 1 33VVT
(1-
96Do0
1
log
(1 (1-3)3VP
Again, need to ensure is that output of Algorithm as instantiated in Algorithm 2 every round has an excess correlation gap over the best policy II no more that (1 (1-38 // which Algorithm assures us can be accomplished with O D log [B]
samples. The total number of samples is (1-80"
D2 By0E
T
times greater.
I Proofs for agnostic learning of halfspaces
Proof of Theorem 8. Using an approximation result of [KOS04], we observe that ERM on the Fourier basis (=) = lies Vi, namely parities on subsets S, can be used produce weak learner. This result guarantees that an n-diimensional halfspace can be approximated with uniform weighting on the hypercube =² -2-error using degree-limited B, = {=xs |S| S d} as a basis, where d 20s As result, at least one h E Bu,d must have high correlation.
Lemma 23 (Lemma 5 in [KMV08]). Let D be any data distribution over [=1}" (-1, with marginal distribution Bndd such
on the features. For any fixed and d = 20s there exists some
corTD maX.EH corr
nd
The result follows directly from the preceding lemma, which provides a weak learner for the task, and Theorem We that [Bn,d] < nd and 7 -d so
log |n.al
dn 3d log(n)
J Additional experimental details
For all algorithms, we perform a grid search on the number of boosting rounds with T E {25, 50, 100). For Algorithm we search over E {0.1, 0.25, 0.5} as well. Rather than using fixed 77, imple- mentation uses an adaptive step-size scheme proportional to the empirical correlation on the current re- labeled distribution. Our experiments [KK09), intended to reduce the stochasticity the algorithm is subject to. In particular, rather than sam-
performed using the fractional relabeling scheme stated in
pling labels, provide both (xr, y) and (sr, -y) in dataset with weights 14 and 1-w"(ar)) respectively. For the baselines, w' (zz y) the Madaboost potential [Dom00]. For the implementation of the proposed algorithm, for greater reproducibility, we use the weighting function w w0(x, v) (1 o) (H, (x)y) ()) which is analytically equivalent to computing the expectation of Pt (x, v.7/) in Algorithm I over n Unif(0, r).. The runtime used for all experiments was Google Cloud Engine VM instance with 2 vCPUs (Intel Xeon bit @ 2.20 GHz) and 12 GB RAM.
2
((1,))))11)) min(1,
where Pmad is
K
Guide for practical adaptation of Algorithm 1
For many hyperparamters, our theory provides strong clues (the link between y and ar). Briefly, in practice, given fixed dataset with Mesal data points, there are two parameters we think practitioner should concern herself with: the mixing parameter a and the number of rounds boosting T, while the rest can be determined, or at least guessed well, given these. The first choice dictates the relative
26

---

weight ascribed to reused samples across rounds of boosting, while T, apart from determining the running time and generalization error, implicitly limits the algorithm using Mooal /T' fresh samples each round. For one may use the adaptive step-size schedule suggested in the previous section, which also obviates the difficulty of selecting y. Similarly, our branching criteria, whose necessity explained in Appendix A, although theoretically both sound and necesssary, is overly conservative. In practice, we believe choosing the better of -sign( (He) and W2 whichever produces the greatest empirical distribution the relabeled distribution will perform best.
27

---

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

---

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

---

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

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please see the appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: : /ttp//eerrip..e// cc httppbiiieetiiiccceieeeieeeeeeee
Question:
Answer: [Yes]
Justification: does.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The present work falls within the realm of foundational research, and is in its basic nature theoretical.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
31

---

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

---

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


Reviews:
[{"review_id": "bNnDG5Ubws", "reviewer": "Reviewer_3oUn", "summary": "The paper proposes a new agnostic boosting algorithm that improves the sample complexity of a previous algorithm by a factor of $\\gamma^{-1}\\epsilon^{-1}$ at the expense of an increase in the computational (oracle) complexity by a factor of logarithmic size or VC dimension of the base learning class. Here, $\\epsilon$ is the desired additive closeness to a risk minimiser and $\\gamma$ the multiplicative approximation ratio to a risk minimiser provided by the weak learner. Alternatively, the oracle complexity can be reduced to that of the previous algorithm at the expense of an increased sample complexity that is not directly comparable to that of previous algorithms.", "questions": "- Why do the main results in the table focus on the finite base learning class when the extension to the infinite case via VC dimensions are available?\n- What exactly is the ERM baseline? The identification of an empirical risk minimiser in $\\mathcal{B}$? If so, is it correct to give its complexity as $\\infty$ in the table (at least for the case of finite $|\\mathcal{B}|$)\n- To what degree is the algorithm distribution-specific? The definition of the weak learner asks the sample complexity to be valid for all distributions.", "limitations": "The limitations of the proposed procedure that go beyond those that are usually present in this branch of literature are the trade-off between sample and oracle complexity as well as a larger number of parameters. The first is discussed very explicitly while the second seems to be mostly a presentation issue as mentioned above.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The theoretical contribution of a rate improvement in sample complexity for agnostic boosting is significant. This is achieved by a sophisticated procedure and corresponding analysis that draws from a range of theoretical insights, especially the extension to infinite base learning classes. The inherent complexity of this contribution is managed by a very rigorous and mature presentation.", "weaknesses": "The proposed procedure has a very large number of parameters. I believe the proofs provide concrete valid settings for those parameters as a function of the desired PAC guarantees. However, it seems that the practical accessibility / usability of the procedure would benefit from a a more explicit treatment of those choices and/or the elimination of some degrees of freedom at least in the main text version of the algorithm.\n\nGenerally, despite the rigorous and detailed presentation, the authors should be aware that their paper is still a very challenging read and I have some worry that the boosting literature becomes increasingly in-penetrable for the wider machine learning community. Any improvement of the general state of affairs that the authors can provide here would be strongly appreciated.\n\nMinor points\n- The references in the first sentence should be revised. It does not make sense that the 1990 boosting article resolves a question first posed in work from 1994.\n- In line 97, it seems to me you mean \"inevitably\" instead of \"invariable\".\n- Typo in line 151: \"boostng\"", "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, and for their positive comments regarding the significance of our work and the presentation.\n\n**Large number of parameters:** Our current presentation is set up to prioritize clean statements of learning guarantees; having independently denoted constants reduces the chances of conflating the impact of each in the proof. The reviewer is *absolutely correct* in identifying that this exposes too many knobs in the algorithm to a practitioner. To rectify this, we will include a guide to practical adaptations of the algorithm. As the reviewer notes, for many of these, the theory does provide strong clues (the link between $\\eta$ and $\\sigma$). Briefly, in practice, given a fixed dataset with $m$ data points, there are two parameters we think a practitioner should concern herself with: the mixing parameter $\\sigma$ and the number of rounds of boosting $T$, while the rest can be determined (or at least guess well) given these. The first choice $\\sigma$ dictates the relative weight ascribed to reused samples across rounds of boosting, while $T$, apart from determining the running time and generalization error, implicitly limits the algorithm to using $m/T$ fresh samples each round. \n\nWe address the questions raised by the reviewer below.\n\n**Ostensible error in chronological order:** This apparent mismatch was indeed well sighted. However, the 1990 paper resolving a question of the 1994 article is correct in that it is an artifact of the journal publication process.\n\n**Finite classes in Table 1:** Our decision to present the results for finite classes in Table 1 was primarily motivated by the desire to cause the least disruption of flow given that we state the fundamental theorem of statistical learning in its simplest form for finite classes too in the introduction (and Table 1 follows immediately after), and closely follow the precedent set by earlier work (e.g., the boosting for reinforcement learning we build and improve upon). We are happy to include the variants for infinite classes instead.\n\n**ERM:** We take ERM to be a procedure that picks the best hypothesis in the hypothesis class $\\mathcal{H}$, the same class against which our boosting algorithm’s agnostic learning\nguarantee holds. As noted in the caption of Table 1, the base class $\\mathcal{B}$, the class the weak learner outputs from, can in general be quite a bit smaller (e.g., decision *stumps* when the class $\\mathcal{H}$ consists of decision trees); we account for this factor in the stated sample complexity. Given a weak learner for the class $\\mathcal{B}$, it’s not clear how an ERM oracle for $\\mathcal{H}$ might be constructed, and hence, the *oracle* complexity is marked as ``inefficient/infinity''. Alternatively, here we could list a *running* time of $\\mathcal{H}$, but that’s distinct from *oracle* complexity. Since, boosting is motivated by settings where direct ERM is computationally intractable, we think the current attribution is fair. Thanks for raising this; this deserves a more explicit note.\n\nDistribution specificity: As noted on Line 168, our boosting algorithm falls within the distribution-specific boosting framework put forward by KK08, since it does not modify the marginal distribution on feature vectors. We avoid this deliberation in the definition itself for simplicity of presentation, i.e., to avoid stating a \"weak learner for feature distribution $\\mathcal{D}\\_{\\mathcal{X}} $\" every time and ''for any distribution $\\mathcal{D}$ with marginal $\\mathcal{D}_\\mathcal{X}$'' in the learning guarantees. In this, we also follow Kalai-Kanade’s lead.\n\n**KK08:** Kanade, Varun, and Adam Kalai. \"Potential-based agnostic boosting.\" Advances in Neural Information Processing Systems 22 (2009).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "kxoT5XuWzJ", "reviewer": "Reviewer_3LK5", "summary": "This paper continues the study of agnostic boosting for binary classification tasks. They provide a new agnostic boosting algorithm that, by re-using samples across multiple rounds of boosting, is more sample-efficient than existing algorithms. As corollaries,  they derive improved sample complexities for agnostically learning half-spaces and boosting for RL. Finally, the authors run experiments and show that their agnostic boosting algorithm outperforms existing algorithms on commonly used datasets.", "questions": "-  It would also be nice if you empirically compared your algorithm to the agnostic booster from [BCHM20].", "limitations": "No Limitations", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The technical contributions are solid, the algorithmic ideas are interesting, and the proof techniques are non-trivial. In particular, I liked the idea of sample reuse across boosting steps. \n-  Overall, I feel that this a nice contribution to the literature on agnostic boosting", "weaknesses": "My main issue with this paper is its presentation. \n\n-  Lemma 9 is referenced/linked a lot in the main text, however it is in the Appendix. I think it would be a good idea to put at least an informal version of Lemma 9 in the main text if it is that important. \n- In my opinion, Section 5 (sketch of analysis) is very dense. I feel that the sketch was a bit too detailed for it to be a sketch but also not  detailed enough for it to be a full proof. I think it would be better to move Lemma 2 to the Appendix, expand more on the description of the algorithm (lines 205 - 216), make Section 5 more high-level and pointing out the exact techniques used to prove Theorem 4, and expand more on the implications of your results for half spaces and RL. \n- Since the proposed agnostic boosting algorithm follows the potential-based framework of [KK09], I think it would be nice to give the readers how these algorithms work in general. For example, it would be nice to elaborate in the main text what the \"potential-based framework\" for agnostic boosting mentioned in Line 102 actually is (providing an algorithmic template would be even better). \n- As is, Section 5 doesn't provide me much intuition about: (1) where/how sample reuse is saving me and (2) why the author's chose the potential function they chose. Overall, I think it would be better to make Section 5 less technical, but provide the reader with more intuition about the algorithmic choices.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time, and for their appreciation of the work’s technical contributions.\n\n**Technical Presentation:** Thanks for the suggestion. We plan to implement the following changes to address your concerns:\n+ Lemma 9 is indeed important both for understanding the algorithm and the analysis in that it outlines the invariant the sample reuse scheme maintains. In our current presentation, its informal statement comes too late: in equation (2) below line 239, and briefly on line 208. We’ll include an informal version of the same early in the paper, as you recommend.\n+ We agree that Lines 205-216 are too dense. We’ll meticulously carry out readability improvements for this section that motivates the algorithm’s design. The current rendition effectively lays out our proof strategy, instead we will reframe it to explain and motivate the algorithmic choices we make in a top-down manner, along with a description of the potential-based framework.\n+ Apart from those listed in Lines 182-192, the principal motivation of the potential lies in its second-order differential continuity and that through it Lemma 3 is true. We’ll work to include the proof of Lemma 3 in the main body. Regarding sample reuse, briefly, the algorithm in Kalai-Kanade performs $T=1/\\varepsilon^2$ rounds of boosting, and uses $1/\\varepsilon^2$ fresh samples for each (as is standard in learning theory), totalling to $1/\\varepsilon^4$. Also, we note an indiscriminate use of all past samples results in a bound no better than that in Kalai-Kanade; this is effectively the recipe in BCHM. In contrast, while we serve $1/\\varepsilon^2$ samples to the weak learner, due to a careful sample reuse scheme, only $1/\\varepsilon$ of these need to be fresh. We were severely space-constrained, and in expanding these descriptions, we hope an additional page available post acceptance will aid us.\n\n**Comparisons to BCHM:** We note that the primary contribution in BCHM was a unifying theoretical framework connecting the online-statistical and realizable-agnostic divides. For individual cases (i.e., for the realizable or the statistical agnostic case), BCHM acknowledges the bounds obtained do not match the best known ones. Similarly, given the nature of the work, BCHM does not provide any experiments nor a reference implementation, and it was not clear to us whether the algorithmic framework is a practically viable one. This was our rationale comparing our approach exclusively to Kalai-Kanade, which is also the state of the art in theory (as mentioned in Table 1). \n\nFollowing the reviewer’s suggestion, we have now added comparisons to BCHM too, and expanded our benchmarking to 6 datasets. The algorithm outperforms both KK and BCHM on 18 of 24 instances. The results can be found in the PDF attached to the common response to all reviewers.\n\n**KK08:** Kanade, Varun, and Adam Kalai. \"Potential-based agnostic boosting.\" Advances in Neural Information Processing Systems 22 (2009).\n\n**BCHM20:** Brukhim, Nataly, Xinyi Chen, Elad Hazan, and Shay Moran. \"Online agnostic boosting via regret minimization.\" Advances in Neural Information Processing Systems 33 (2020): 644-654.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "kvBVMfdy35", "reviewer": "Reviewer_P9SH", "summary": "The authors propose a method of classifier boosting that improves the sample complexity bound in agnostic settings. To achieve it, they propose an algorithm carefully reusing the sample across iteration for updating pseudo labels. They also demonstrate the usefulness of the method with the agnostic halfspace learning and the reinforcement learning, as well as experimental results.", "questions": "- On the note right after Theorem 6, the time complexity of ERM: Can we just employ an SGD-like algorithm + hinge loss to achieve the same order of the sample complexity as ERM with a manageable time complexity, like $O(n /\\epsilon^2)$?\n- Section 6.2: How does it compare to the non-boosting results in the RL literature?\n- Section 7: The baseline accuracy in Table 3 barely degrades as the label noise increases. Even far from that, it goes **up** with the Spambase data. How do you explain this phenomenon?\n- Also in Section 7:\n  - What is the meaning of $\\pm$ in the table? standard deviation?\n  - Did you separate the data for the accuracy estimation and the grid search?", "limitations": "The limitations are adequately addressed.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- Well motivated.\n- Having significant technical novelties.", "weaknesses": "- It lacks discussions on the comparison with prominent competitors in terms of the trade off between the sample- and time- complexities: SGD-like implementations of ERM.\n- Hard to follow the technical part and understand which portion of the algorithm is new and important for the improvement in the sample complexity. In particular, one could use the intuitive explanation on the role of each nontrivial step in the algorithm such as \n  - stochastic branching in Line 5,\n  - sampling $\\eta'$ in Line 5.II,\n  - stochastic relabelling in Line 5.II,\n  - branching condition in Line 9, and so on.\n- Also, the proof sketch (Section 5) could be more streamlined, unifying it with the aforementioned intuitive explanations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time, and their appreciation of the technical novelties of our work.\n\n**Comparisons to ERM via SGD:** The boosting framework (including the celebrated Adaboost algorithm) is founded on the premise that it is often easy to construct weak learners both in theory and practice, crucially in the absence of a computationally efficient ERM oracle. Indeed, when ERM is efficiently implementable for a given hypothesis classes (i.e., logistic regression with cross-entropy loss), the boosting methodology (not just our work) offers no advantages; e.g., ERM has a better sample complexity as Table 1 (or nearly matching in the realizable/Adaboost’s case). Note that the corresponding applications of boosting also follow this, i.e., routinely used weak learner classes are non-convex and not amenable to SGD, e.g., decision stumps, binary parity function. Similarly, for the classic problem of agnostically learning halfspaces (notice the 0/1 loss), neither our results nor those in KK08 and KKMS08 are achievable via SGD + hinge loss on linear classifiers. In fact, no fully polynomial time algorithm is known for this problem. Hence, we find this comparison not fully relevant to the problem at hand, and we sincerely request the reviewer to consider raising their score.\n\n**Motivating the algorithm design:** Thanks for bringing this up. Following your suggestion, we’ll meticulously carry out readability improvements for the section that motivates the algorithm’s design. We will reframe it to explain and motivate the algorithmic choices we make in a top-down manner, along with a description of the potential-based framework. This way the changes we make will be easier to highlight. Currently, we highlight the new components (including the data reuse scheme using relabelling and the new branching scheme, both crucial) of our approach in the contributions section (notably, Lines 84-141), but we understand that the description may be too dense and perhaps too early. \n\n**Non-boosting RL results:** The closest point of comparison for RL using a supervised learning oracle (a stronger assumption that assuming a weak learning oracle as we do) over the policy space comes from the Conservative Policy Iteration Algorithm due to Kakade and Langford (KL02). It needs $1/\\varepsilon^3$ samples in the episodic model and $1/\\varepsilon^4$ samples in the $\\nu$-rollout model; both of these are better than our results by a factor of $\\varepsilon$ albeit in a stronger oracle model. Notice this ERM-to-boosting gap is larger in BHS20, where the boosting results are worse by a factor of $\\varepsilon^2$. In this sense, our results improve upon the best known results for boosting for RL, and reduces the boosting methodology’s gap for RL to supervised learning.\n\n**Section 7:** A key point, as stated in the caption of Table 3, is that the label noise is only added during training. Hence, the bayes-optimal classifier remains equally effective on the original dataset regardless of label noise. The fact that the ML classifier barely degrades with as much as 20% label noise is a testament to the strength of the agnostic boosting approach. The case of Spambase is an anomaly we do not fully understand. We suspect that this effect may be due to the regularization effect of label noise; the feature vectors in Spambase are notably sparse. The numbers following $\\pm$ indeed represent the endpoints of a 95% confidence interval for each entry, each estimated using out-of-sample data. \n\n**KK08:** Kanade, Varun, and Adam Kalai. \"Potential-based agnostic boosting.\" Advances in Neural Information Processing Systems 22 (2009).\n\n**KL02:** Kakade, Sham, and John Langford. \"Approximately optimal approximate reinforcement learning.\" In Proceedings of the Nineteenth International Conference on Machine Learning, pp. 267-274. 2002.\n\n**BHS20:** Brukhim, Nataly, Elad Hazan, and Karan Singh. \"A boosting approach to reinforcement learning.\" Advances in Neural Information Processing Systems 35 (2022): 33806-33817.\n\n**KKMS08:** Kalai, Adam Tauman, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio. \"Agnostically learning halfspaces.\" SIAM Journal on Computing 37, no. 6 (2008): 1777-1805.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "vjmdexPG9o", "reviewer": "Reviewer_m6d1", "summary": "This work proposes a new agnostic boosting algorithm whose sample complexity is shown to be polynomially better than that of previous methods.\nCompared to existing techniques, the advantage of the proposed algorithm comes mainly from the novel concept of reusing samples across multiple rounds of boosting.\nThrough their analysis, the authors offer other theoretical insights that may be of independent interest.", "questions": "1. What hardware was used for experiments? How long did them take to run?\n2. Why include $T$ in the grid search of the experiments? Wouldn't it suffice to fix the highest value? The fact that the proposed method, in some sense, \"rolls back to the best model\" (see last line of Algorithm 1) makes that seem even more reasonable.\n3. At 250, what do you mean by \"the sign of $\\Delta_t$ is indeterminate\"?\n4. How original is Contribution 5? How much of it is present in previous works? How much effort is needed to fit your results into existing frameworks to obtain Theorem 7? (I already had a look at appendices G and H, but I am still not totally sure.)\n5. Similarly, how original is Contribution 3? Are the authors aware of any previous works applying similar strategies ($L_1$ covering number based bounds $\\to$ Theorem 20)? (To be clear, I do value the nice connection. I am simply trying to size precisely its originality.)\n6. At 116, what do you mean by \"The resultant sample complexity improves known results for all practical (i.e., sub-constant) regimes of ε\"? I would imagine that applications are actually prone to employ larger values of ε; above, say, the machine precision.", "limitations": "I think my criticisms regarding the experiments (1-4) are pertinent here.\nMoreover, I got the impression that the authors are particularly capable of tackling the presentation issues. They demonstrated to have a good grasp of the subject and a good writing skills. I suspect that, with some effort, they can make this and future papers excel in clarity and appeal.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Good writing style. Well above average, with few typos and overall high signal-to-noise ratio.\n2. Noteworthy rigour in the theoretical analysis. Catching the subtle stochastic dependencies missed by [KK09] is good sign of diligence. (I did not check details exhaustively, though. Specially those in the appendices.)\n3. Substantial contribution. Up to some caveats, this work improves the sample complexity of agnostic boosting by factor of $εγ$, which is particularly valuable considering that it leaves the SOTA only another $εγ$ factor away from ERM's complexity.\n4. Some empirical results are provided. This is a good practice, even if the main focus is theoretical.\n5. *(Bonus)* I tend to be sceptical towards citing web links, but [Pin20] was a nice one.", "weaknesses": "I will start by the experiments.\nNote that I can appreciate the work for its theoretical contributions alone and see the experiments as a welcome extra.\nWith that being said:\n1. Information on the computer resources used for the experiments seems to be missing. This is in contrast with Question 8 of the paper checklist (at 840):\n    > For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?\n\n    To that, the authors reply \"Yes. Please see the appendix.\" (at 843 and 844), but I could not find this information in the appendix, the main text, or the supplementary material.\n2. Without information about the computational cost of the experiments, it is hard to understand the limitation to only three datasets.\nThe experiments in [KK09] include 5 more datasets and, even though I can see the experiments brought by the authors here are larger (e.g., 30-fold rather than 10-fold cross-validation), hardware has got much better since [KK09].\n3. From the description of the experiments, it is clear that they generated much more data than what is present in the text. More of this data should be available, even if only in the supplementary material.\n4. At line 296, \"less stark\" is a bit too generous. The baseline performed consistently and significantly better than the proposed method in the presence of the noise. While I praise the authors for being upfront about this, the phenomenon should be sufficient to motivate further experimentation and a deeper discussion.\n\nMoving to the theoretical side, I believe the main issues lie in the presentation of the work.\nTo be clear, this does not concern the writing style, which I appreciated, but rather the clarity and contextualization relative to prior works.\n\n5. While the intro is clear at almost all points, clarity seems to progressively decrease up to (the crucial!) section 5. I understand that much of this comes from the complexity of the subject itself. I understand the big challenge, but given the absolute importance of section 5, I believe the authors underperformed there. A similar note applies to the paragraph starting at 205: I am confident there is some significant \"curse of knowledge\" at play there.\nStill, a criticism such as this is too costly to substantiate, so it will not significantly affect my evaluation (directly).\n6. The contextualization should be better. A paper not only **ought** to make it *possible* for the reader to infer precisely what parts of the contributions are original, it **should** make the delineation *easy*. Specially for a paper that demands heavier background, it is crucial to be very clear about the extent of your contributions, not only by stating them explicitly, with absolute clarity but also by explicitly indicating which ideas come from previous works.\nBelow, I list the reasons why I believe what the authors offer (most notably the explicit enumeration of contributions in Section 1.1) is insufficient in this regard.\n    1. I believe that the implications for agnostic learning for halfspaces should be presented as a case for the relevance of the problem, rather than as a contribution. The translation of results in the setting of the paper to that of agnostically learning halfspaces is already present in [KK09] and seems to require minimal extra effort. Still, the authors promote it as a contribution quite strongly, with multiple occurrences of the claim in the text and its highlight as Contribution 4 (at 131).\n    2. A similar note may apply to the application to boosting for reinforcement learning (Contribution 5 at 134). I preferred to ask the authors directly about this.\n    3. Similarly, I found it necessary to ask the authors about the exact nature of Contribution 3. See question below.\n    4. The point mentioned in Contribution 2 (113) should be further discussed. If I understand correctly, when taking the oracle complexity into account, the bound from Theorem 8 remains incomparable to the one from [KK09] (see, e.g., Table 1) given the cubic dependence on $\\log \\lvert \\mathscr{B} \\rvert$. The authors should elaborate on this matter. For example, on one hand, understanding this logarithmic factor to be negligible (as the authors suggest in the caption of Table 1) weakens the case for Contribution 2, since it only improves the oracle complexity by this exact factor. On the other hand, taking it as important jeopardizes the contribution of Theorem 8 as the factor shows up (twice) in the final sample complexity bound.\n    5. The authors should highlight more the main technical challenges arising from modifying the algorithm by [KK09]. In my opinion, the contribution would be fair even if the challenges were minor so, if authors thought this was the case (and I am not saying it is), they could be explicit about it and still make a good case for the paper.\n    6. [BCHM20] looks a bit off within in Table 1 since its bound is strictly worse than that of [KK09]. This is not a serious issue, but it is worth a brief comment.\n7. The need for $\\varepsilon_0$ and $\\delta_0$ is worth more discussion than what is offered around 166.\n\n>NOTE: I apologize if my attempt to remain objective ended up making me sound harsh.\n\nOverall, I tend towards acceptance, but with reservations. I find it quite feasible that I misunderstood some point, and that the authors can clarify important points in the rebuttal, so there is a fair chance I end up raising my initial score.\n\n\n### Minor issues and suggestions\nWhile reading the paper, I took some notes that the authors may find useful. The authors are free to ignore those.\n\n- You may want to have a look at the (very recent) works on parallel boosting [1] and [2]. I'm not sure the connection is deep, but they also employ some notion of \"sample reuse\".\n- [23] missing \"it\"\n- \"excess of $ε$\" is better than \"$ε$-excess\" in many ways, if you think about it\n- [Table 1] Put \"inefficient\" within parentheses\n- [Table 1] Rephrase the sentence starting with \"$\\mathscr{B}$ is the base...\". It's quite confusing.\n- [All tables] Use `booktabs` for better tables. Also, the tips in its documentation can be very useful\n- [41 (and many other places)] In American usage, colons are usually followed by a capital letter\n- [66] \"these\" is ambiguous\n- [67] \"A weak learner\" $\\to$ \"A $\\gamma$-weak learner\" (in particular, solves undefined usage shortly after)\n- [73] missing hyphen\n- [85] remove extra comma\n- Floating objects (figures, tables, etc.) ended up inconveniently far from their first reference in the text\n- [100] double \"of\"\n- [103] \"making a step “backward” via adding in a negation of the sign of the current ensemble\" is a bit too heavy to get this early in the text\n- [124] remove extra \"to\"\n- Having hyperlinks to algorithm lines would be nice\n- Number theorems and lemmas by section (e.g., \"Theorem 4.2\" rather than \"Theorem 5\")\n- [138] \"MDP\" is still undefined\n- [151] fix \"boostng\"\n- [161] A pedantic reader may need a quick definition of $\\Delta(\\;\\cdot\\;)$\n- [everywhere] use `\\colon` rather than `:` to define functions (it gives the right spacing)\n- Consider TikZ for Figure 1 to have better control over the appearance (compared to GeoGebra) and vector graphics by default. Perhaps this extra control to can save some space.\nHere is a quick draft as an example:\n```latex\n\\begin{tikzpicture}\n    \\draw[color=gray, thin, dotted] (-3.1, -0.6) grid (4.1, 4.1);\n\n    \\draw[->] (-3.2,0) -- (4.2,0);\n    \\draw[->] (0,-0.7) -- (0,4.2);\n\n    \\draw[color=red, domain=-2.075:2.6] plot (\\x, {2 - \\x}) node[right] {$2 - z$};\n    \\draw[color=blue, domain=-2.075:4, smooth] plot (\\x, {(\\x + 2) * exp(-\\x)}) node[above] {$(z + 2) e^{-z}$};\n\\end{tikzpicture}\n```\n- Many mathematical equations are left without proper punctuation. Those are integral part of the text and should be treated as such.\n- [Definition 1] Consider using $\\sup$ rather than $\\max$ for robustness\n- [176] \"a functions\" $\\to$ \"a function\"\n- [Algorithm 1] \"Agonstic\" $\\to$ \"Agnostic\"\n- [Algorithm 1] Number all lines\n- [Algorithm 1, first line of line 5] probably missing a \"uniform\"\n- [198] Use `\\coloneqq`\n- [208] no need for the apostrophe to pluralize\n- **This is a bit more important.** $h^*$ only gets defined at 482 but its used many times earlier.\n- [237] double period\n- [239] The use of $\\pm$ in the next equation is undefined and confusing\n- [240] \"linearity\" $\\to$ \"the linearity\"\n- [Table 3] omit the 0s to save space. E.g., \"0.12\" $\\to$ \".12\". This should solve the overfull hbox.\n- [483] dangling \"]\" below\n- [577] \"semi norm\" $\\to$ \"seminorm\"\n- [578] \"size\" is ambiguous in this context\n- [Theorem 19] Missing `\\operatorname` for \"corr\"\n- [582 and 583] Inconsistent parenthetization\n- [598] Missing `\\operatorname` for \"Cov\"\n- [Random] In my humble opinion, this work would be better presented by first focusing on the method by [KK09] and building up from there, gradually discussing the modifications and their implications. Of course, this is also a matter of style, and the change could be quite costly at this point.\n\n[1] Karbasi, A. and Larsen, K.G., 2024, March. The impossibility of parallelizing boosting. In International Conference on Algorithmic Learning Theory (pp. 635-653). PMLR.\\\n[2] Lyu, X., Wu, H. and Yang, J., 2024. The Cost of Parallelizing Boosting. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 3140-3155). Society for Industrial and Applied Mathematics.", "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, and for their positive comments regarding the rigor and the significance of our work.\n\n**Experiments:** The runtime used for all experiments was a Google Cloud Engine VM instance with 2 vCPUs (Intel Xeon 64-bit @ 2.20 GHz) and 12 GB RAM. The python code takes a bit under 2 hours to reproduce the results as presented in the table. Here, we would like to note that the code for experiments and reference implementations of the algorithms in KK are not available publicly. Hence, for some datasets (e.g., pendigits, letters), we are unsure how KK converts these multiclass datasets (as listed on UCI repo) to binary classification tasks. Given that a description of the same is missing in the text of KK and its appendices, we skipped these. Within the remaining options, we chose datasets that were moderate sized, on which we could iterate fast to get a working version of the algorithm in KK. Similarly, BCHM is a more recent work on the subject, but does not report experimental results. We are happy to include the complete log obtained from cross-validation trails. Finally, the case of Spambase is an anomaly we do not fully understand. We suspect that this effect may be due to the regularization effect of label noise; the feature vectors in Spambase are notably sparse. \n\nFollowing the reviewer’s suggestion, we have now expanded our benchmarking to 6 datasets, and added comparisons to the algorithm from BCHM too. The algorithm outperforms both KK and BCHM on 18 of 24 instances. The results can be found in the PDF attached to the common response to all reviewers.\n\n**Variable T:** If $S$, the number of fresh samples sampled every round, were a constant, the reviewer’s comment would be unreservedly true. However, given a fixed size dataset of size $m$, the choice of $T$, the number of rounds of boosting, also implicitly dictates $S$, the number of fresh samples one can draw every round, since $S\\approx m/T$. Hence, given a fixed data budget, versions of the algorithm run for longer $T$’s aren’t simply versions with smaller $T$’s subject to more rounds of boosting. This is true for the algorithm in KK too.\n\n**Contributions vs Implications:** This point is well made. We are happy to list the results on agnostic learning of halfspaces and boosting for reinforcement learning as implications of the improved agnostic boosting result instead of contributions, although here we must note that the result as presented in BHS is not entirely black-box. That this interpretation was intended originally too can be evidenced in ‘we apply’ and ‘by applying’ on lines 131 and 137, along with citations to works that first sketched out the connection.\n\n**Sample-complexity Oracle Complexity Tradeoff in Contribution 2:** We think each bound in Theorems 4 and 8 make their mathematical/theoretical utility evident. To make a case for their practical relevance, Here’s our interpretation of the presented results: almost invariably both in practice and in theory, boosting is used with simple base hypotheses classes with small value of $\\log |\\mathcal{B}|$ (see AGHM21 for cases and examples). With a modest inflation in running time – which is still polynomial in PAC learning terms – Theorem 4 guarantees an unconditionally better sample complexity. We certainly think of Theorem 4 as the main contribution of the present work (and hence, it’s positioned in the main paper). Now, let’s fix $\\gamma=\\Theta(1)$ for simplicity of argument. If, however, this inflation is running time is unacceptable for some reason (due to, say, binding computational constraints, large datasets), Theorem 8 is offers the same oracle complexity and running time as the previous works, yet an improved sample complexity as long as $\\varepsilon \\leq 1/\\log |\\mathcal{B}|$. With large datasets at hand, one is presumably aiming for small $\\varepsilon$, and this condition is met. Similarly, in resource-constrained settings, where $\\mathcal{B}$ is not very expressive to save on computation, $\\log |\\mathcal{B}|$ is small, making this truth value of this condition very plausible, if not probable. This is what we mean by sub-constant $\\varepsilon$; it’s a relative statement about the magnitude of $\\varepsilon$ in comparison to other problem parameters – here, $\\log |\\mathcal{B}$| – not an absolute one.\n\n**Technical Presentation:** We agree that Lines 205-216 and Section 5 are too dense. We’ll meticulously carry out readability improvements for this section that motivates the algorithm’s design. The current rendition effectively lays out our proof strategy, instead we will reframe it to explain and motivate the algorithmic choices we make in a top-down manner, along with a description of the potential-based framework. We were severely space-constrained, and in expanding these descriptions, we hope an additional page available post acceptance will aid us.\n\n**Technical Challenges:** Currently, we highlight the new components (including the data reuse scheme using relabelling, avoiding uniform convergence on the boosted class ala BCHM, and the new branching scheme, all crucial) of our approach in the contributions section (notably, Lines 84-141) along with their necessity, but we understand that the description may be too dense and perhaps too early.\n\n**BCHM vs KK:** We note that the primary contribution in BCHM was a unifying theoretical framework connecting the online-statistical and realizable-agnostic divides, including the first result for online agnostic boosting. For individual cases (i.e., for the realizable or the statistical agnostic case), BCHM acknowledges the bounds obtained do not match the best known ones.\n\n**Parallel Boosting:** We are happy to include a pointer to these results. Thanks!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "LY0xgkahq4", "reviewer": "Reviewer_xmA9", "summary": "The paper studies the agnostic boosting problem. That is the learner is given access to a weak learner that given $m_0$ samples form any distribution $D'$ returns a hypothesis $h$ from some baseset $\\mathcal{B}$ such that it is $corr_{D'}(h)\\geq \\gamma corr_{D'}(h^*)-\\varepsilon_0$ with probabilty $\\delta_0$, where $h^*$ is the hypothesis in a hypothesis set $\\mathcal{H}$ with the largest $corr_{D'}$. Furthermore the learner is given access to samples from a unknown target distribution $D$. The goal of the learner is now to create a hypothesis $\\bar{h}$ (not necessary in $\\mathcal{B}$ or $\\mathcal{H}$) such that  $corr_{D}(\\bar{h})\\geq \\max_{h\\in\\mathcal{H}}corr_{D}(h)-\\varepsilon$ with probabiilty $1-\\delta$, with as few samples from $D$ and calls to the weak learner. \nThe paper present a new  learning algorithm for solving this problem, which uses (with log factors not included) $O(\\log(|B|)/(\\gamma^3\\varepsilon^3))$ many samples and $O(\\log(|B|)/(\\gamma^2\\varepsilon^2))$ many calls to the weak learner. This is an improvement in the number of samples need from $D$ of a factor at least $O(\\gamma\\varepsilon)$ over previous know results, this improvment cost a factor of $\\log(|B|)$ more calls to the weak learner compared to the best know which uses $O(1/(\\gamma^2\\varepsilon^2))$. However they also have a second algorithm that uses $O(\\log(|B|)/(\\gamma^3\\varepsilon^3)+\\log^3(|B|)/(\\gamma^2\\varepsilon^2))$ many samples from $D$ and $O(1/(\\gamma^2\\varepsilon^2))$ many calls to the weak learner. The highlevel explanation of this better bound on the sample complexity is that the best previous known algorithm was running $O(1/\\gamma^2\\varepsilon^2)$ rounds and in each round using $O(\\log(|B|)/(\\gamma^2\\varepsilon^2)$ new samples from $D$. However by reusing samples from previous rounds an agumentening the samples they are able to only use $O(1/(\\gamma\\varepsilon))$ samples per round and in $O(\\log(|B|)/(\\gamma^2\\varepsilon^2))$ rounds. They also extend there results to infinite classes $\\mathcal{B}$. \nFurthermore the paper show how there new algorithms also have implications for Agnostic learning halfspaces and Boosting for reinformencment learning. They also evaluate their first algorithm against the previous best known algorithm and claim that they demonstrate a improvement empirically.", "questions": "The comment given below Definition 1, do [KK09] and [BCHM20] also have the additive $\\varepsilon_0$ term so they have to set $\\varepsilon_0 = \\varepsilon$? (So my question is: is the comment \"necessary\" also meant for [KK09] and [BCHM20] as well?).\n\n Line 208 is it $-  \\phi ' ( H_t,  h^{*}) $ or what is $H$ in $-\\phi '(H,h_t^{*})$?\n\n\nLine 8 algorithm 1, what is  $D^{'}_t$ - I guess nevermind the line 9 says $\\hat{D}^{'}_{t}$ is that also the case for Line 8? And on line 8 to me the \"with as\" sounds a bit off (disclaimer: I'm not a native english speaker so please take this into considerations for this suggestion).\n\n\n Theorem 4:  Is there no dependence on $\\delta$ or $\\delta_{0}$ in the sample complexity? Or are they suppressed in the notation as the footnote suggests?(if this is the case why is $\\log|B|$ not suppressed in the notation as well?) \n\n\nProof sketch of Theorem 4 questions start\n\n\n Line 238 why $\\eta \\approx 1/\\sqrt{T}$? (So $\\eta = O(\\sqrt{1/T})=O(\\gamma\\varepsilon/\\sqrt{\\log|B|})$ is in the statement of Theorem 4?)\n    ´\n   Line 239.5 is $\\varepsilon_{gen} \\approx \\varepsilon$  ?\n\nLine 241 is it$\\phi'_{D}(H_{t},W_t/\\gamma)$ in the last equation?\n\n Line 244 is it $-\\phi '_{D}(H_{t},-sign(H_t))$ in the last equation?\n  \nLine 245-246 why is this relaxed criteria sufficient for the proof of Theorem 4? And could that be explained in stead in line 240-244 instead of the thing which is not atractable?\n Proof sketch of Theorem 4 questions end.\n\nLine 281-282 \"there is an algorithm using that uses the weak learner $\\mathcal{W}$\" sounds off to me (disclaimer: I'm not a native english speaker so please take this into considerations for this suggestion).\n\nWhat is the reason for not comparing to [BCHM20] in the experiments?", "limitations": "Yes.", "rating": 7, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "Originality: They claim the paper has three innovations, reusing samples from previous rounds by argumenting them smartly, using a martingal argument to not use a uniform convergence results that they claim would result in a $O(1/(\\varepsilon^4))$ sample bound, and using  a different branching idea compared to previous work when. Given the discrebtion of the previous work they the authors provide the ideas seems novel and different from previous approaches. \n\nQuality: The main contains no full proofs so I have not checked the technical soundness of the paper this is also my reason for my confidence score. I have included questions below on the proof sketch. In the introduction it is said that \"Finally, in preliminary experiments in Section 7, we demonstrate that\n     the sample complexity improvements of our approach do indeed manifest in the form of improved\n     empirical performance over previous agnostic boosting approaches on commonly used datasets.\" do you compare to more than one previous approach? Is it exactly the algorithm 1 you run? As the experiments are preliminary I would also suggest maybe using a word like \"suggest\" instead of \"demonstrate\" in the sentence above. As also mentioned in the limitations the theoretical work is the primary contribution of the paper.\n\nSignificance: The theoretical results seems significant and a nice improvment over previous work in the sample complexity and a interresting step towards \"matching\" the samples complexity of agnostic learning which has dependency  $O(1/\\varepsilon^2)$ instead of now $O(1/\\varepsilon^3)$ (if it is possible to achieve a sample complexity $O(1/(\\varepsilon^2 \\gamma^2))$ in the agnostic boosting case). As they state the experiments are preliminary and I also personally think that the theoretical results are more than enough to make the paper significant in it self.", "weaknesses": "The only small weakness I can come up with is the $log(|B|)$ factor in the oracle sample complexity of the algorithm 1 (and they mention themself)  which is taken care of in algorithm 2 for most parameters of $log(|B|),\\varepsilon,\\gamma$ (not considering hidden $log$ factors in the notation).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time, and their positive appraisal of our work. We address the reviewer’s questions below.\n\n**Epsilon0:** Here essentially following the precedent set by KK and BCHM, we state our main results (e.g., Theorem 4) for a fixed value of weak learner’s tolerance $\\varepsilon_0$. This term is also present in KK (see Theorem 1 therein) and BCHM (see Theorem 8 therein). Only for the purpose of compiling the results in Table 1, we set $\\varepsilon_0=\\gamma \\varepsilon$ so that the results stated correspond to the standard agnostic learning notion of $\\varepsilon$ excess error, and that all algorithms including ERM may be compared.\n\n**Delta0/Delta in Theorem 4:** $\\delta_0$ does appear additively in the failure probability in Theorem 4. We suppress a $\\log 1/\\delta$ factor in the sample complexity bounds. The reason for displaying $\\log |\\mathcal{B}|$ prominently stems from this quantity being the capacity of the hypothesis class. Although written with a logarithm, this quantity is not small since in applications the hypothesis class is routinely chosen to be at least moderately expressive (say, with cardinality exponential in the feature space dimension).\n\n**Comparisons to BCHM:** We note that the primary contribution in BCHM was a unifying theoretical framework connecting the online-statistical and realizable-agnostic divides. For individual cases (i.e., for the realizable or the statistical agnostic case), BCHM acknowledges the bounds obtained do not match the best known ones. Similarly, given the nature of the work, BCHM does not provide any experiments nor a reference implementation, and it was not clear to us whether the algorithmic framework is a practically viable one. This was our rationale comparing our approach exclusively to Kalai-Kanade, which is also the state of the art in theory (as mentioned in Table 1). \n\nFollowing the reviewer’s suggestion, we have now added comparisons to BCHM too, and expanded our benchmarking to 6 datasets. The algorithm outperforms both KK and BCHM on 18 of 24 instances. The results can be found in the PDF attached to the common response to all reviewers.\n\n**Remaining points:** We will switch to ‘suggests’ as you recommend; this is a good suggestion. Lines 208, 241 and 244 should be indeed as you suggest; should include $H_t$ as the first argument. Line 8 in the algorithm should also be $\\widehat{D}^{'}\\_t$, as you point out. Thanks!\n\n**Proof Sketch:** Our intent for the proof sketch was to convey the plausibility of a $1/\\varepsilon^3$ result, upto the exclusion of other factors. Hence, $\\lesssim$ inequalities only hold up to constants and polynomial factors in $\\gamma, \\log |\\mathcal{B}|$. Hence, while in the proof sketch $\\eta\\approx\\frac{1}{\\sqrt{T}}\\approx\\varepsilon$, the formal theorem and proof specify them correctly including dependencies in $\\gamma, \\log |\\mathcal{B}|$. We should have been explicit about this expectation. (Indeed, $\\varepsilon_{Gen} \\approx \\varepsilon$, as you note.) The relaxed branching criteria to accommodate the challenge mentioned in Line 244 is not straightforward in terms of logical flow (requires case work in Lines 504-513), although it is entirely elementary in terms of its mathematical content. Hence, we were reluctant to dive into it, but we’ll attempt to frame this argument with the extra page available post acceptance to sketch the argument succinctly.\n\n**KK08:** Kanade, Varun, and Adam Kalai. \"Potential-based agnostic boosting.\" Advances in Neural Information Processing Systems 22 (2009).\n\n**BCHM20:** Brukhim, Nataly, Xinyi Chen, Elad Hazan, and Shay Moran. \"Online agnostic boosting via regret minimization.\" Advances in Neural Information Processing Systems 33 (2020): 644-654.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:
We thank all the reviewers for their comments and editorial suggestions. We hope that we have adequately addressed each reviewer’s questions in the space for one-to-one responses. In this unified response, we hope to highlight two changes of common interest.

**Experiments:** Following Reviewer 3LK5 and m6d1, and xmA9’s suggestions, we have now expanded our benchmarking to 6 datasets, and added comparisons to the algorithm from BCHM too. The algorithm outperforms both KK and BCHM on 18 of 24 instances. The results can be found in the attached PDF. 

Here, we would like to briefly highlight that neither the benchmarking suite nor a reference implementation is publicly available for KK08, and that BCHM20 does not report on experiments altogether. The typical focus of agnostic boosting results has been on the theory. *While our result also falls in this camp, we hope that the reference implementations we make available (including those of previous algorithms) will be of use to the community.*

**Readability Improvements:** Upon revision:
+ We plan to add a guide to practical adaptations of the algorithm. For many hyperparamters, the theory does provide strong clues (the link between $\eta$ and $\sigma$). Briefly, in practice, given a fixed dataset with $m$ data points, there are two parameters we think a practitioner should concern herself with: the mixing parameter $\sigma$ and the number of rounds of boosting $T$, while the rest can be determined (or at least guess well) given these. The first choice $\sigma$ dictates the relative weight ascribed to reused samples across rounds of boosting, while $T$, apart from determining the running time and generalization error, implicitly limits the algorithm to using $m/T$ fresh samples each round.  
+ We agree that Lines 205-216 are too dense. We’ll meticulously carry out readability improvements for this section that motivates the algorithm’s design. The current rendition effectively lays out our proof strategy, instead we will reframe it to explain and motivate the algorithmic choices we make in a top-down manner, along with a description of the potential-based framework.
+ Currently, we highlight the new components (including the data reuse scheme using relabelling, avoid uniform convergence arguments on the boosted class, and the new branching scheme, all crucial) of our approach in the contributions section (notably, Lines 84-141), but we understand that the description may be too dense and perhaps too early. We were severely space-constrained, and in expanding these descriptions, we hope an additional page available post acceptance will aid us.

**KK08:** Kanade, Varun, and Adam Kalai. "Potential-based agnostic boosting." Advances in Neural Information Processing Systems 22 (2009).

**BCHM20:** Brukhim, Nataly, Xinyi Chen, Elad Hazan, and Shay Moran. "Online agnostic boosting via regret minimization." Advances in Neural Information Processing Systems 33 (2020): 644-654.

Meta-review: A nice paper with a worthy contribution, with all reviewers unanimously judging its contribution as good or excellent and recommending acceptance. I suggest to add the new experiments using the +1 page.

Reading the paper, it looked very much to me that the idea could be used not just for the convex surrogate used, but perhaps for the convex surrogate of any proper loss (in the theory of losses for class probability estimation, see the work of Reid and Williamson in several JMLR). It would be interesting to see how the sample demands evolve as a function of the property of the partial losses (intuitively, there should be one, but I could not see it). It is interesting because this trick to reuse examples could be very useful not just in the context of the paper.
Decision: Accept (poster)