Sample-Efficient Agnostic Boosting

We thank the reviewer for their time, and their positive appraisal of our work. We address the reviewer’s questions below.

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.

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).

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).

Following 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.

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!

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.

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.

We thank the reviewer for their time, and their appreciation of the technical novelties of our work.

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.

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.

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.

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.

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

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.

BHS20: Brukhim, Nataly, Elad Hazan, and Karan Singh. "A boosting approach to reinforcement learning." Advances in Neural Information Processing Systems 35 (2022): 33806-33817.

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.

Thank you for engaging with us. We think it has been helpful in pinpointing the source of disagreements regarding expectations from the present work.

We would like to iterate that our work – applications included – is situated in the agnostic model, to which a substantial fraction of the literature on learning theory is dedicated. While in the realizable case (even with noisy labels) when working with a hypothesis class $\mathcal{H}$, the reviewer’s remarks are undoubtedly correct, and (S)GD + calibrated loss does converge to the best in-class hypothesis with respect to the 0/1 loss (which is also the Bayes-optimal classifier by the realizability assumption). However, the premise of agnostic learning model lies in the desire to compete (up to a vanishing in sample-size error) with the best in-class hypothesis, crucially in absence of any distributional assumptions on y|x whatsoever. Here, the bayes-optimal classifier can be arbitrarily complex (and not approximable by $\mathcal{H}$). Conversely, if the Bayes-optimal classifier were in $\mathcal{H}$ (approximately), the learning problem would belong to the (near, respectively) realizable setting. There are also results that attempt to weaken the realizability assumption. For example, FCG21 (which indeed works by GD on a convex surrogate, as the reviewer suggests) is a recent work of this sort that provides learning guarantees of the form $C \times (\text{best in-class accuracy})^{1/2} + \varepsilon$ with polynomial sample complexity, which is meaningful whenever the best in-class hypothesis has a small error (zero error corresponding to perfect realizability). Nevertheless, these bounds are incomparable to agnostic learning guarantees of the form best in-class accuracy + $\varepsilon$ (whether the learned hypothesis is in-class is an orthogonal matter, that of proper vs. improper learning), a stronger guarantee that also requires substantially more samples. In conclusion, near realizability of the bayes-optimal classifier puts us in a different learning model altogether with incomparable guarantees. However, we are happy to post a remark mirroring this point in the manuscript.

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)$?

Finally, we think there’s very strong evidence to bet against the reviewer’s original hunch (quoted above). There are known statistical query lower bounds (referenced to in e.g FCG21, which apply to a very large class of algorithms including (S)GD regardless of the parameterization) requiring $\exp(poly(\varepsilon^{-1}))$ queries for agnostic learning of halfspaces with Gaussian marginals (we operate with uniform).

FCG21: Frei, Spencer, Yuan Cao, and Quanquan Gu. "Agnostic learning of halfspaces with gradient descent via soft margins." In International Conference on Machine Learning, pp. 3417-3426. PMLR, 2021.

Thanks once again for your time and feedback.

P.S. As a final remark – perhaps this is what the reviewer had intended – one can try to approximate the best in-class (crucially, not the bayes-opt which can be arbitrarily complex) hypothesis by an expressive hypotheses class (e.g., in an orthogonal basis of functions like the Fourier basis). But this is what we (and previous works including KK and KKMS) effectively do. Our proof proceeds by approximating half spaces by low degree terms in the fourier basis to show that parity functions act as a weak learning class for the former (Line 654).

Sign of DeltaT: Given the equation below Line 249, if $\Delta_t$’s were somehow non-negative, then since $\mathbb{E}\_{t-1}[\Delta_t]<\Delta_{t-1}$, it would form a supermartingale sequence, and one could apply supermartingale concentration results. The comment is in place to emphasize that although $\Delta_t$ is martingale-like, by itself, it is not a martingale, supermartingale or submartingale.

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.

BHS20: Brukhim, Nataly, Elad Hazan, and Karan Singh. "A boosting approach to reinforcement learning." Advances in Neural Information Processing Systems 35 (2022): 33806-33817.

AGHM21: Alon, Noga, Alon Gonen, Elad Hazan, and Shay Moran. "Boosting simple learners." In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 481-489. 2021.

We thank the reviewer for their thorough review, and for their positive comments regarding the rigor and the significance of our work.

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.

Following 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.

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.

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.

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.

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.

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.

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.

Parallel Boosting: We are happy to include a pointer to these results. Thanks!

We thank the reviewer for their time, and for their appreciation of the work’s technical contributions.

Technical Presentation: Thanks for the suggestion. We plan to implement the following changes to address your concerns:

• 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.
• 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.
• 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.

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).

Following 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.

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.

We thank the reviewer for their thorough review, and for their positive comments regarding the significance of our work and the presentation.

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.

We address the questions raised by the reviewer below.

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.

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.

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 guarantee 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.

Distribution 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.

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