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.
Paper
Similar papers
Peer review
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. The 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}$. Furthermore 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.
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. Quality: 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 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." 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. Significance: 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).
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?). Line 208 is it $- \phi ' ( H_t, h^{*}) $ or what is $H$ in $-\phi '(H,h_t^{*})$? Line 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). 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?) Proof sketch of Theorem 4 questions start 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?) ´ Line 239.5 is $\varepsilon_{gen} \approx \varepsilon$ ? Line 241 is it$\phi'_{D}(H_{t},W_t/\gamma)$ in the last equation? Line 244 is it $-\phi '_{D}(H_{t},-sign(H_t))$ in the last equation? Line 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? Proof sketch of Theorem 4 questions end. Line 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). What is the reason for not comparing to [BCHM20] in the experiments?
Rating
7
Confidence
1
Soundness
2
Presentation
2
Contribution
3
Limitations
Yes.
Summary
This work proposes a new agnostic boosting algorithm whose sample complexity is shown to be polynomially better than that of previous methods. Compared to existing techniques, the advantage of the proposed algorithm comes mainly from the novel concept of reusing samples across multiple rounds of boosting. Through their analysis, the authors offer other theoretical insights that may be of independent interest.
Strengths
1. Good writing style. Well above average, with few typos and overall high signal-to-noise ratio. 2. 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.) 3. 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. 4. Some empirical results are provided. This is a good practice, even if the main focus is theoretical. 5. *(Bonus)* I tend to be sceptical towards citing web links, but [Pin20] was a nice one.
Weaknesses
I will start by the experiments. Note that I can appreciate the work for its theoretical contributions alone and see the experiments as a welcome extra. With that being said: 1. 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): > 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? 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. 2. Without information about the computational cost of the experiments, it is hard to understand the limitation to only three datasets. The 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]. 3. 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. 4. 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. Moving to the theoretical side, I believe the main issues lie in the presentation of the work. To be clear, this does not concern the writing style, which I appreciated, but rather the clarity and contextualization relative to prior works. 5. 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. Still, a criticism such as this is too costly to substantiate, so it will not significantly affect my evaluation (directly). 6. 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. Below, 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. 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). 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. 3. Similarly, I found it necessary to ask the authors about the exact nature of Contribution 3. See question below. 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. 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. 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. 7. The need for $\varepsilon_0$ and $\delta_0$ is worth more discussion than what is offered around 166. >NOTE: I apologize if my attempt to remain objective ended up making me sound harsh. Overall, 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. ### Minor issues and suggestions While reading the paper, I took some notes that the authors may find useful. The authors are free to ignore those. - 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". - [23] missing "it" - "excess of $ε$" is better than "$ε$-excess" in many ways, if you think about it - [Table 1] Put "inefficient" within parentheses - [Table 1] Rephrase the sentence starting with "$\mathscr{B}$ is the base...". It's quite confusing. - [All tables] Use `booktabs` for better tables. Also, the tips in its documentation can be very useful - [41 (and many other places)] In American usage, colons are usually followed by a capital letter - [66] "these" is ambiguous - [67] "A weak learner" $\to$ "A $\gamma$-weak learner" (in particular, solves undefined usage shortly after) - [73] missing hyphen - [85] remove extra comma - Floating objects (figures, tables, etc.) ended up inconveniently far from their first reference in the text - [100] double "of" - [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 - [124] remove extra "to" - Having hyperlinks to algorithm lines would be nice - Number theorems and lemmas by section (e.g., "Theorem 4.2" rather than "Theorem 5") - [138] "MDP" is still undefined - [151] fix "boostng" - [161] A pedantic reader may need a quick definition of $\Delta(\;\cdot\;)$ - [everywhere] use `\colon` rather than `:` to define functions (it gives the right spacing) - 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. Here is a quick draft as an example: ```latex \begin{tikzpicture} \draw[color=gray, thin, dotted] (-3.1, -0.6) grid (4.1, 4.1); \draw[->] (-3.2,0) -- (4.2,0); \draw[->] (0,-0.7) -- (0,4.2); \draw[color=red, domain=-2.075:2.6] plot (\x, {2 - \x}) node[right] {$2 - z$}; \draw[color=blue, domain=-2.075:4, smooth] plot (\x, {(\x + 2) * exp(-\x)}) node[above] {$(z + 2) e^{-z}$}; \end{tikzpicture} ``` - Many mathematical equations are left without proper punctuation. Those are integral part of the text and should be treated as such. - [Definition 1] Consider using $\sup$ rather than $\max$ for robustness - [176] "a functions" $\to$ "a function" - [Algorithm 1] "Agonstic" $\to$ "Agnostic" - [Algorithm 1] Number all lines - [Algorithm 1, first line of line 5] probably missing a "uniform" - [198] Use `\coloneqq` - [208] no need for the apostrophe to pluralize - **This is a bit more important.** $h^*$ only gets defined at 482 but its used many times earlier. - [237] double period - [239] The use of $\pm$ in the next equation is undefined and confusing - [240] "linearity" $\to$ "the linearity" - [Table 3] omit the 0s to save space. E.g., "0.12" $\to$ ".12". This should solve the overfull hbox. - [483] dangling "]" below - [577] "semi norm" $\to$ "seminorm" - [578] "size" is ambiguous in this context - [Theorem 19] Missing `\operatorname` for "corr" - [582 and 583] Inconsistent parenthetization - [598] Missing `\operatorname` for "Cov" - [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. [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.\ [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.
Questions
1. What hardware was used for experiments? How long did them take to run? 2. 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. 3. At 250, what do you mean by "the sign of $\Delta_t$ is indeterminate"? 4. 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.) 5. 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.) 6. 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.
Rating
6
Confidence
3
Soundness
3
Presentation
3
Contribution
3
Limitations
I think my criticisms regarding the experiments (1-4) are pertinent here. Moreover, 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.
Rebuttal by Authors (continued..)
**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.
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.
Strengths
- Well motivated. - 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. - 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 - stochastic branching in Line 5, - sampling $\eta'$ in Line 5.II, - stochastic relabelling in Line 5.II, - branching condition in Line 9, and so on. - Also, the proof sketch (Section 5) could be more streamlined, unifying it with the aforementioned intuitive explanations.
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)$? - Section 6.2: How does it compare to the non-boosting results in the RL literature? - 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? - Also in Section 7: - What is the meaning of $\pm$ in the table? standard deviation? - Did you separate the data for the accuracy estimation and the grid search?
Rating
6
Confidence
3
Soundness
2
Presentation
2
Contribution
3
Limitations
The limitations are adequately addressed.
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).
> 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). Yes, this is what I intended, at least in the last reply. And I am curious how, despite their similarity, do they compare each other in terms for their sample/time complexities. But anyway, it becomes clear that my original concern is not impactful as I saw it. Thanks for your the extended discussion so far. I will update my score.
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.
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. - Overall, I feel that this a nice contribution to the literature on agnostic boosting
Weaknesses
My main issue with this paper is its presentation. - 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. - 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. - 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). - 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.
Questions
- It would also be nice if you empirically compared your algorithm to the agnostic booster from [BCHM20].
Rating
6
Confidence
3
Soundness
3
Presentation
2
Contribution
3
Limitations
No Limitations
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.
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. Generally, 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. Minor points - 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. - In line 97, it seems to me you mean "inevitably" instead of "invariable". - Typo in line 151: "boostng"
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? - 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}|$) - To what degree is the algorithm distribution-specific? The definition of the weak learner asks the sample complexity to be valid for all distributions.
Rating
7
Confidence
3
Soundness
4
Presentation
3
Contribution
4
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.
Thanks for the thoughtful and informative rebuttal. Let me clarify one thing: on the first point, specifically in the setting of Theorem 6, I agree that "ERM + hinge loss + SGD" with the weak hypothesis class does not converge to the optimal weak learner w.r.t. 0-1 loss. However, "ERM + hinge loss + SGD" does converge to the Bayes optimum if we consider stronger hypothesis classes (possibly with regularization) that are convex and **containing the Bayes optimum in their closures**, as the hinge loss is a calibrated surrogate loss function. Since the proposed method also looks for a good hypothesis beyond the weak learners, I think it is interesting to compare it with "ERM + hinge loss + SGD" beyond the weak hypothesis learning.
Thanks for the thoughtful rebuttal. My impression is that the authors got particularly rigorous reviewers (and survived!) and, hence, there should be particularly valuable lessons to be learned from the feedback they got (you should be getting averages closer to 7 given how skilled you appear to be). Keep that in mind. Still, the authors should be proud of their work. Congratulations.
Thank you for your encouraging response. We are confident that incorporating your constructive feedback (which we sincerely value) will enhance both the readability and the appeal of the present work.
Thank you for your prompt acknowledgement. We especially appreciate your fine-grained feedback about the proof sketch and your eye for notational inconsistencies, which we can only assume came at significant expense of your time.
Decision
Accept (poster)