How to Boost Any Loss Function

We thank the reviewer for highlighting that our " [...] main is very well written [...] " and a long strength section that indeed summarizes well some of our contributions. We hope this rebuttal answers the questions to strenghten further the review's polarity.

What does $R_*$ and $N_*$ denote ?

These are the sets of reals / naturals without 0.

can you explain why the sign of any [...]

because the secant is always taken in the interval defined by $\tilde{e}_{t-1}$ and ${\tilde{e}_t}$ (We propose to put more of this information in Fig. 1 right)

Figure 2, is the dotted lines [...]

The slopes of the dotted lines (secants) provide the weights (the information needed for optimisation).

Corollary 5.4, i guess could also be stated with just the weak learning assumption?

We assume the reviewer talks about Corollary 5.6 (there is no Corollary 5.4). No, we need all assumptions. All related parameters indeed appear in the bound, but there is also a rationale for their appearance, see [RA5.4E] [RA5.4.2].

Why does figure 3 and 4 come before figure 2? 

As far as we can tell, Fig. 2 is on page 7, Fig. 3 on page 8, Fig. 4 on page 9 so the statement does not hold. As for where they appear wrt citation, there is probably a bit of LaTeX optimisation that can be done to fix it. We are happy to do it.

Line 176 $\nu_t$ depend on $h_t$ through $M_t$ is this a problem.

We do not use notation $\nu_t$ here. We assume the reviewer means $\tilde{\eta}_t$. Dependence on $M_t$ is a requirement: otherwise it would unfairly penalize the weak learner. Consider for example that a weak learner predicting all classes well but with very little confidence could in fact not satisfy the weak learning assumption if we drop the normalization by $M_t$. In fact, many papers directly assume that $h_t \in [-1,1]$, see for example [ssIB] (our reply to reviewer bfG5).

Why isn't it the case that the weak learner output the hypothesis $h_t$ such that $\nu_t \geq \gamma$ (no absolute value)

(again, we consider that the reviewer talks about $\tilde{\eta}_t$) This is one beautiful feature of boosting: if the weak hypothesis is very bad, say $\tilde{\eta}_t < -\gamma$, then its negation is very good ($\tilde{\eta}_t > \gamma$), which is captured in a $<0$ leveraging coefficient !

What if the weak learning gaurantee was given in terms of the the loss funciton $F$ ?

The weak learning assumption would then be "just about one loss" and thus very restricted. The adopted formulation is much more general.

Can you come up with a setting [...] compare it to the best known bound for that setting?

We assume that the reviewers want to know how close we can come to an optimal, loss-dependent bound ?

Can we be close to the best rates for some losses ? The answer is yes. Consider the logistic loss. It comes from [tAP] (additional bibliography above) that our rate is within a constant factor of the one shown for the logistic loss, which is then shown to be optimal in [tAP].

Are we this good in the general case (i.e. for all losses) ? Certainly not: we do not exploit curvature for strongly convex losses in the same way as Adaboosting does so we are as suboptimal from AdaBoost-type boosting for the exponential loss as logistic gradient boosting is [tAP]. Note that our remark hits at possible improvements of our algorithm to then capture a generalized notion of curvature for better boosting rates, but only for some losses.

The weak learning assumption I know is from "Boosting" Robert E. Schapire and Yoav Freund page 48. "Specifically, we say that the empirical $\gamma$-weak learning assumption holds if for any distribution $D$ on the indices $\{1, \ldots, m\}$ of the training examples, the weak learning algorithm $A$ is able to find a hypothesis $h$ with weighted training error at most $\frac{1}{2}-\gamma$ :

E_{i \sim D}\left[h\left(x_i\right)y_i\right] \geq 2\gamma.

Thanks for taking the time to reply my questions and correcting the $2\gamma$.

Regarding: "$h_t/M_t \in [-1,1]$ that satisfies Assumption 5.5. Classifier $h'_t = \mathrm{sign}(h_t/M_t)$ would then satisfy [fsAD]'s weak learning assumption with $\gamma'=\gamma/2$" could you show this derivation - thanks for pointing out the other implication it was insightful for understanding/drawing the connection of/the motivation of Assumption 5.5. better for a person only knowing boosting from the point of view that is presented in "Boosting" Robert E. Schapire and Yoav Freund page 48. If you could also add some more intuition of why the labels in the assumption is allowed to change it would be good (from you comment it seems to not allowed in the setup of "Boosting" Robert E. Schapire and Yoav Freund where the surrogate lose is exp-loss - and if the learner is allowed to change them totally as pleased or what is allowed? .

We thank the reviewer for the whole content of the strength section, which summarizes the key strengths of our approach.

I would connect more to real-world applications.

Even when we deliberately formatted our paper for a theory report, we understand the reviewer's standpoint. We in fact ran experiments (see our supplementary information) but these were really just meant as a "trial of fire" for our theory, using eventually some very "nasty" losses (see the spring loss). We were please that it works but beyond that, the test of real-world applications is important but would deserve separate consideration, because of the potential that offers our algorithm to deal with very complex settings: consider for example adversarial learning. In this case a "robust" empirical loss is trained with the objective to yield good models on the "actual" domain. The mainstream consists in designing the empirical "robust" loss using data modifications. One could also think of adding the possibility (or replacing data modifications with) designing the loss itself to prevent bad outcomes on generalization (e.g. to prevent categories of large margins). This could be computationally much more efficient. Regardless of the loss' design, it could be used in our algorithm as is, which we believe shows a strong benefit of our approach.

In addition, sometimes the loss function is differentiable yet getting the derivative could be expensive. 

The reviewer is right. We suggest to put [RGRI] (answers to reviewer 8gCx) in the camera ready using the additional page.

Some of the material in appendix III are actually insightful and helpful

We understand the reviewer would like some details (at least about implementation tricks) to be put in the main file. We would be happy to oblige using part of the +1 page camera ready.

We thank the reviewer for writing that our contribution is "[...] potentially very important [...]" and hope to give here the arguments sought by the reviewer to enforce further this claim.

First, Assumption 5.4, is this easy to verify for some given learners? [...]

[RA5.4E] This assumption is indeed technical and comes from the nature of the losses that we minimize (for another set of arguments to explain it, see [RA5.4.2]). There is in fact no "super bad" losses but only locations on the loss landscape that prevent further optimization. In classical non-convex optimization, these are just local minima, which explains that a measure of convergence is the expected gradient's norm in such works. The equivalent in our case is the numerator of $\rho_t$. If it is zero, there is barely anything we can do to get to a better solution and assumption 5.4 breaks. if however it is not the case and our numerator is strictly positive, then we can guarantee a >0 rate.

Why do we need to include the denominator of $\rho_t$ ? It appears to be necessary because we consider v-derivatives: the variation of the function is thus not exactly local like for a derivative and we need to factor in the possibility for the loss to "jiggle a lot" locally, which blurs the information of the secants for convergence. The denominator of $\rho_t$ factors in second-order v-derivatives. The reviewer may think of classical curvature in differentiable optimisation. A small denominator prevents lots of jiggling where the current solution stands, and thus better rates. See also [RA5.4] above.

Is this a limitation of the use of v-derivatives ? Quite the opposite in fact: our algorithm includes the possibility to escape local minima ! This feat somehow comes from the use of the v-derivatives (and their higher orders) that authorise "seeing past local minima" [RA5.4.2]. To get such a guaranteed feast would however necessitate to optimize further the offset oracle, which delivers the local "horizons" the strong learner can look for better solutions. Such would surely necessitate a work / paper of its own.

Then, Assumption 5.5, this is not the standard weak learning assumption [...]

[RA5.5E] It is in fact the standard assumption, we refer to [RWL3] for a parallel discussion. The standard weak learning assumption includes the weights as a distribution and are thus normalized. If the reviewer means normalization for the hypotheses, then this became standard from [ssIB] since convergence does not depend anymore on the normalization constraint. See for example [mnwRC] (bibliographical references above).

And I am not sure why the condition is imposed for all $t$ and requires condition for the subsequent $h_t$ beyond the initial weak learner [...]

[RA5.5F] There might be a misunderstanding here: the weak learner is not assumed to change. Only the weak hypotheses it returns can change. It is standard to assume that each of them needs to satisfy the weak learning assumption because otherwise the weak learning assumption is so weak that the weak learner could just return an unbiased coin as predictor, which would obviously be useless to improve the ensemble.

We would be happy to add some additional content to make [RA5.5E] [RA5.5F] clear.

There are some inconsistent notations and definitions

We indeed have overloaded some notations (like $F$, which is indeed used both for the pointwise loss and for the population loss) in the hope of limiting notational inflation. If the reviewer feels like it is not good for readability, we are happy to reverse the trend.

What are examples of the strict benefits of the boosting for any loss function beyond those requiring gradient information? [...]

[RGRI] This is an excellent question. One answer, which we hope will have become more clear at this point thanks to [RA5.4E], is that our algorithm comes with the possibility to escape local minima, which cannot "naturally" be escaped for gradient approaches because a gradient just provides variation information at the exact point where the solution stands.

Another answer is the one that has motivated the field of 0th order optimisation: computing gradients can be expensive compared to loss values (think "green AI"). This of course assumes in general that gradients are "estimated" (e.g. using autodiff), but even when they are not, remark that this then requires the computation of another function than the loss, which, regardless of how it is done, always require at some point some additional calculus / computation.

A last answer comes from the one that has originally motivated the Ada-boosting field: non-differentiable losses are difficult to optimize (first and foremost because the gradient "trick" is not accessible) and so one can instead optimize a "nice" surrogate loss (the exponential loss in the case of AdaBoost). But this comes at a price, which is that we just do not optimize the "ideal" loss anymore directly (the 0/1 loss in the case of AdaBoost). There is thus less that can be told for the optimization of this "ideal" loss. Our algorithm offers the possibility to directly target the optimization of this ideal loss without resorting to surrogates, with guaranteed rates. Of course, as we write in L235-L237, this may come with additional design choices for the oracles.

We hope the limitations section in the review is now adequately addressed.

I acknowledge and thank the author for their response.

Btw, do the authors forget to put [RWL3] [ssIB][RDRF] in their response to the Reviewer bfG5? I still cannot find them even searching them by command + F...

And one rebuttal suggestion related to that is to put the parts of some common responses to the Global response instead of letting each reviewer search where it is. Thanks a lot!

We thank reviewer bfG5 for a passionate review. We particularly appreciate that reviewer bfG5 put the key strength of our paper in bold faces. This is rarely seen in reviews in general and in our case for example, none of our 6-6-7 other reviews use bold faces to describe the strengths of our paper.

We hope the length of the rebuttal does not discourage the reviewer to dig (it is split in several comments below) -- it should rather serve as a token of our appreciation of the review’s content, disregarding whether the statements made actually hold or our potentially divergent opinions. The review can be split in 3 parts, first discussing the positioning of our paper, then summarising our objective and technical “value” and finally digging into specifics. This rebuttal uses simple tags like [RTB] to point to the relevant parts located elsewhere via a browser’s search.

Our reply contains several points that would add to the paper content. We made sure that this content, alongside the one proposed for the other reviews, would fit in the additional camera-ready page: [RDML][RNT2] [R4.3].

This rebuttal part contains two sub-parts: a reply to the positioning of our paper and a reply to the questions asked in the review.

On the the positioning of our paper.

The choice of primary area for this paper (learning theory) was poor. This work is far better placed within the area of optimisation than in learning theory […] the most appropriate reviewers […] I did my best to make my review useful to the authors and the community as a whole.

[ROLT] We believe we understand where the reviewer comes from, and we do not share the reviewer's opinion. One can argue that submission "strategies" do not have a clear path, in particular for targetting the humans in the review loop. It is not just about targeting reviewers, ideally the best and most dynamic ACs have the most influential role in the game and this year, some allocation algorithms were different. Factor in the number of submissions and the number submitted in each primary area (unknown in advance, of course) with the risk of "overflowing": the choice of the primary area is then far from being a best bet on getting the best "humans in the loop". So we sticked to a "logical" primary area [RTB]. We may remark that our choice of primary area at least did get us a dynamic reviewer clearly open to discussing our points of disagreements -- we do not know a strategy that grants this automatically :).

Questions

Up to the simplifying assumption of a finite weak hypothesis class, do you agree with the reformulation [...]

De do not, for reasons explained above [RDRF]. However, the reviewer's comments helped us realize a simple improvement that would hopefully alleviate misunderstandings and oversimplifications [RDML]

Why do you believe "optimisation" is not a more appropriate primary area for this work than "learning theory"?

We explain it in [ROLT] and [RTB]. In one word: history.

What happens to Definition 4.1 [...]

The v-derivative becomes a conventional derivative and our algorithm then becomes a more classical gradient boosting algorithm (albeit with explicit rates, which again is usually not stated in the state of the art)

Sorry if I simply missed this one, but what is your actual claim about Assumption 5.4? 

[RA5.4.2] It is a very legitimate question ! And perhaps we should have made this part more explicit or formulated in another way. What we mean is that since the rate essentially behaves as $1/\min_t \rho_t$ and is thus vacuous if $\rho_t=0$, we must ensure a strictly positive value for this minimal value, $\rho_*$ (however small it may be). Note that this is not restrictive: we explain in L165-L166 that $\rho_t=0$ means that the algorithm converges to what looks like a (local) minimum. We also explain in L217-L227 that the offset oracle has in fact the "ability" to have the strong learner move to a better minimum. We would like to emphasize that this cannot be achieved with gradient-based algorithms, since the gradient information just gives information at exactly where the algorithm stands and thus leaves it "trapped" if it is a local minimum. Note that we have not investigated optimizing the offset oracle for such tasks since it would probably require a following work/paper of its own. See also [RA5.4E].

We hope the reviewer will find the answers to their questions and the information to fill the gaps they wanted to see filled in their comment "[...] I would lean towards acceptance provided the authors do a good job in establishing the relevance [...]".

[RDRF] The formulation proposed by the reviewer is reminiscent of the game theory formulation for boosting [fsGT] where the full information available for training fits in a matrix or a set of predefined fixed vectors. The issue with the formulation in our case is that the analysis is then implicitly carried knowing the weak classifiers that are going to be chosen by the weak learner (because the weak learner may well learn in a set of unbounded size !). This forgets that in our case boosting has to be nested also with (i) the computation of the leveraging coefficients (second option Step 2.3) and (ii) the interaction with the offset oracle (Step 2.5) and would render a clean convergence proof definitely a lot more challenging.

[RDML] This being said, the comment helped us realize that we perhaps forgot to complete section 3 by adding a standard ML part at the end ! This part would read as follows (after L81).

"Our ML setting consists in having primary access to a weak learner WL that when called, provides so-called weak hypotheses, weak because barely anything is assumed in terms of classification performance for each of them separately. The goal is to devise a so-called "boosting" algorithm that can take any loss $F$ as input and training sample $S$ and a target loss value $F_0$ and after some $T$ calls to WL returning classifiers $h_1, h_2, ..., h_T$, returns classifier $H_T = \sum_t {\alpha_t} h_t$ with $F(H_T,S) \leq F_0$, where the leveraging coefficients are computed by the algorithm. Notice that this is substantially more general than the classical boosting formulation where the loss would be fixed or belong to a restricted subset of functions."

(We comment on the $\gamma$-weak learner below [RWL1][RWL2][RWL3])

In particular, my understanding is that [...] The authors do not claim any new techniques used to obtain their results […] the authors do not claim the problem is particularly challenging under the light of the usual frameworks used for this kind of problem.

[RNT] It takes a full reading of the review to see that the rest of the review contradicts these statements in places -- and we disagree with them. We however attribute these statements to several things:

the reviewer is clearly knowledgeable about AdaBoost but “reduces boosting” to AdaBoost-ing and never mentions nor discusses our contributions with respect to the gradient boosting current, which is a lot more productive nowadays [RTB]. By definition, gradient boosting exclusively relies on computing gradients (and in fact, some versions of AdaBoost does also rely on such computations [ssIB]). From the standpoint of gradient boosting, it is clear that our paper needs to rely on different tools to achieve boosting. Since most of the gradient boosting literature does not have convergence proofs (even less so with explicit rates, even less so in the weak-strong framework) and neither do the sparse boosting results on non-differentiable / non-convex losses (see our L66-L68), it would make sense that original tools needed to be used in our case. In fact, it is quite implicit from our L90: to achieve our goal, we need higher-order v-derivatives that are not even defined in a bedside book of quantum calculus ! We also relied on the inference that since the state of the art 0th optimisation relies up to some extent on additional assumption about the loss, there is either something we make possible with boosting that is not yet known to be possible in the classical 0th order setting OR (non exclusive) we pulled new tools to achieve our objectives. Given the sheer amount of work in 0th order optimisation, it would somehow be conceited to claim the former, but we surely can claim the latter, and we believe the reviewer in fact agrees with us (see the points below)

• at this point, we hope the reviewer agrees that there no such thing as a “usual framework” for “this kind of problem”… because there was in fact no framework at all yet defined to properly analyse such problems, because no such result existed before ours. We are the first to provide one, and in fact the reviewers surely agrees with us when they press us to comment on this new parameter $\rho$ that perfectly captures the rate in our case [RA5.4]

(continued below)

(continued from above)

from the very first comment of the review (Note on the choice of primary area), we in fact suspect that the main reason for [RNT] is that we did not format our paper like a “conventional” (if there exist one) learning theory paper, where the introduction or a special section right afterwards usually frames the technical contribution per se in terms of tools used and key results achieved, eventually disregarding the problem solved in fine. From here they perhaps concluded that there was nothing worth mentioning and got to the conclusion above that we rebute here. Perhaps they got additionally confused by the statement we make in L46 that “some [tools from quantum calculus] appear to be standard in the analysis of 0th order optimisation”. The “some” mentioned is in fact the basic secant information (we have never seen the higher-order v-derivative information used; in fact, it has never been defined in quantum calculus either, see above).

If this is the reason for the reviewer’s comments, then we deeply apologise. We in fact chose not to present our paper this way for space reasons and left the numerous implicit implications of our claims (see the first point above) to “speak for themselves". Since there is one additional page in the camera-ready, should our paper be accepted, it would be trivial to include the following statement in the second part of the introduction (would replace “some of which” and what follows in L45):

“[RNT2] Our proof technique builds on a classical boosting technique for convex functions that relies on an order-one Taylor expansion to bound the progress between iterations [nwLO]. In this technique, boosting weights depend on the gradient and thus the sample expectation of Taylor’s remainder becomes a function of the weak learner’s advantage over random guessing, which is guaranteed to have strictly positive value by virtue of the weak learning assumption, leading to a strict decrease of the loss. In our case, we change the Taylor expansion by a more general bounding involving v-derivatives and a quantity related to a generalisation of the Bregman information [bmdgCW]. Getting the boosting rate involves the classical weak learning assumption’s advantage and a new parameter bounding the ratio of the expected weights (squared) over a generalised notion of curvature relying on second-order v-derivatives, quantifying the local potential “jiggling” of the loss (an uncertainty measure, smaller being better). Our algorithm, which learns a linear combination of weak classifiers, introduces notable generalisations compared to the AdaBoost / gradient boosting lineages, chief among which the computation of acceptable ranges for the v-derivatives used to compute boosting weights (which are always zero for classical gradient boosting).”

At this point, we hope to have clarified our claimed contributions, the technical nature of our work and the novelty of some tools we use and the fact that there is indeed no such thing as a "usual framework" for our problem. We also hope that after reading [RA5.4.2], the reviewer will be convinced that our approach brings substantially more than "just" solving a technical problem.

We understand the reviewer would like us to claim that the problem is challenging: such is a matter of personal perception and understanding; claiming it could be seen as somehow pretentious. We are happy to let the reviewer conclude based on the above but we think it is worth mentioning that a problem should just be worth solving, regardless of its technical nature. If the statement were true indeed, then an influential boosting paper would probably not have appeared — or at least not in its form, [ssIB], whose empirical convergence proofs are arguably elementary (given or not the back-then state of the art) but have been instrumental in both the design and convergence proofs of boosting algorithms for numerous settings.

5. I am confused by the authors' concept of what constitutes "traditional" boosting. To me, AdaBoost is the most prototypical and traditional boosting algorithm.

[RTB] We would be happy to agree with the reviewer as this would simplify a lot our arguments, but this is unfortunately factually untrue, as e.g. recently debated in PNAS [nnTP]. AdaBoost [fsAD] was the (learning theory’s) first boosting algorithm in the sense of Kearns/Valiant’s weak/strong learning model. After AdaBoost, a sizeable current in statistics started its own boosting “phylum”: gradient boosting, with the works of Jerome Friedman (et al.), remarking that Adaboost could be framed as a gradient optimiser and then “generalising" gradient AdaBoosting to any differentiable loss.

To grasp the importance of this statistical current, consider that Friedman’s founding paper [fGF] is now cited more than twice as much each year compared to Freund and Schapire’s founding paper [fsAD] (source: Google Scholar).

Now, two key differences between the statistical current and learning theory’s AdaBoost are (i) statistics broadened the scope of boosting to any differentiable loss, but (ii) very few of such works have convergence proofs (even less so convergence rates, even less so in the weak-strong model). This is where our work finds its place and justification: we considerably broaden the applicable losses of the statistical approach to any loss while proposing explicit convergence rates in AdaBoost’s weak/strong learning setting in all cases.

This also explains why we ultimately picked learning theory instead of optimisation as primary area: this field grounds the rich history of boosting and roots boosting’s “phylogenetic tree” [nnTP]; progress in optimisation has been orthogonal to this history. This is not a criticism: a lot of our references (all of Table A1) are on 0th order optimisation, which has been hugely productive on this topic while learning theory’s boosting has been mostly “deaf” to these advances. This is not surprising: the weak-strong learning setting does not explicitly call to the use of the loss’ derivatives to learn (unlike, of course, gradient descent). Given Friedman’s (et al.) take on boosting that “reduces it” to gradient descent, it was expectable and justified to try to alleviate the gradient dependence, which is our contribution. It came as a pleasant surprise that we had to make no functional assumptions to get there (unlike the state of the art 0th order optimisation).

2. Theorem 5.3 fails to provide a reasonably self-contained statement [...]

What we propose to put in the introduction [RNT2] and at the end of Section 3 [RDML] is also aimed at clarifying this result. If the reviewer also means that it also takes a re-read of the manuscript to grasp some parameters in (20), we are happy to make this summary of what the key parameters are just before the theorem's statement, following a custom often seen in theory papers.

3. The authors do not provide an exact statement for the optimisation problem [...]

We conjecture that this comes from the lacking ML part at the end of Section 3 [RDML]

4.1 On the theoretical side 0th order optimal weak to strong learners are known to exist: see [1]

[R4.1] This reference is irrelevant for two reasons: [1] (which needs to be combined with [lrOW]) leads to sample optimal “AdAboost-ing”. Sample optimality is not our focus. Second, a 0th order optimisation algorithm takes a loss as input and has to work for large sets of of losses, not just 1 or a few. All references we put in Table A1 operate on large sets of losses, and the set is even wider for our algorithm, as the reviewer accurately noticed. AdaBoost does not qualify (AdaBoost optimises directly the exponential loss, indirectly the 0/1 loss).

4.2 On a more practical side, in general, the performance of boosting methods does not really come from the minimisation of the associated loss function

[R4.2] We wholeheartedly disagree: this statement overgeneralises from [2]’s Section 7.3 and puts it out of its very specific context: performance = 0/1 loss, associated loss = exponential loss (the “surrogate” loss).

[2]’s Section 7.3’s “raison d’être” is the fact that there is more to just minimising the exponential loss that brings good performance on the 0/1 loss: margin maximisation (AdaBoost’s “dynamics”) is crucial to get there. In fact, in this very specific case, it is not even enough to get good performance: early stopping for AdaBoost is crucial to get statistical consistency [btAI]. Not early stopping would grant boosting statistical consistency if the loss is Lipschitz [tBW], which is not the case for the exponential loss. Hence, one can get rid of this early stopping design constraint by just choosing a different loss (but then, on an orthogonal performance measure, one faces slower rates [tBW,wvTS]).

Could we remove this additional margin maximisation property for the associated loss minimisation to lead to good performance on the 0/1 loss ? It is indeed possible, and simple: just clip the exponential loss by replacing it by $F(z) = \exp(-\max\{z,u\})$ with $u>0$. It is trivial to show that any algorithm substantially beating the trivial max loss $\exp(-u)$ on average would in fact guarantee large margins — and thus good generalisation on the 0/1 loss via standard large margin classification results, e.g. [sfblBT]. Note however that minimisation would have to be carried out using a 0th order algorithm — or our approach !

4.3 I recognise that the authors explicitly dismiss matters of generalisation, but […] the authors may consider bringing up these points in some form.

[R4.3] We dismissed generalisation for 2 reasons: (1) it was hard to discuss in the page limit but more importantly, (2) classical matters relevant to generalisation would amount to restricting the set of losses OR putting additional constraints on our algorithm, and we chose to stick to the most general setting, thus only focusing on the empirical boosting of any loss. As examples, to get statistical consistency, we would “just” have to restrict the set of losses to Lipschitz losses [tBW]; to get statistical consistency with a strongly convex loss, we would have to consider early stopping; to learn in an adversarial setting in the simplest way with our algorithm, we would probably not consider Lipschitz losses because of the then “easiness" of an adversary to play against the learner [cmnowMB]. In all these settings, there would be no fundamental modification to our algorithm. We could put a few lines using the additional page to discuss such matters informally.

General minor issues and suggestions

We proceed through bullet order

In the technical summary above [...]

The suggestion seems to suggest a continuous version of boosting in the vein of [awWW] for continuous EG. It is a very interesting question !

(2 following bullets) [...] it is not even fully clear how novel the concepts introduced are.

Section 4 introduces concepts related to v-derivatives, with 4 definitions, 4.1, 4.2, 4.3, 4.4, 4.6. It is absolutely explicit in the text that 4.1 comes from another work, 4.2 is new, 4.3 is new, 4.4 comes from another work and 4.6 is new. For all new concepts, we link them to their closest relative published.

I suspect you require less from the hypotheses returned by the weak learner [...]

The reviewer is right but somehow this would risk "hiding" the fact that on training, an hypothesis needs to have finite values (or we just cannot compute the objective). Our formulation perhaps look less general but was formulated as is on purpose.

Consider stating more explicitly [...]

We will do.

[Eq. (4)] Consider using [...]

Excellent suggestion.

Number only the equations that are referenced in the text

We will do.

Consider a version of Figure 1

Just to confirm, we see it as a Figure where dim1 would e.g. be the difference between $z$ and $z'$ (say $z$ is fixed) and dim2 would be the offset ? That would be easy and a good idea.

Avoid starting sentences with mathematical symbols

Agreed, though L93 does not start like this (typo ?)

[122] the reference to [47, Appendix, Section 4] has a bit too much packed

Agreed. Note that from [RNT2], part of the "unpacking" would directly start from the introduction

Adding hyperlinks to the steps of the algorithm

Easy. We will do.

Algorithm 1 can be made significantly tidier. 

We believe we can simplify Step 2.5 and replace the table in Step 2.3 by a more conventional algorithmic convention

6. The discussion around Assumption 5.4 is too loose […]

[RA5.4] We understand the reviewer would like a discussion about the significance of the assumption. The discussion that grounds the assumption, in L165-L171, is meant to explain why such an assumption is in fact necessary in our setting. Our work is the first on boosting exploiting 0th order information about the loss and we have not seen before high-order v-derivatives with different offsets being used so we assume it is the first time $\rho$ indeed appears. To strengthen the discussion, we shall make a parallel with stochastic gradient descent (SGD) on strongly convex losses. We are happy to push some of what follows in the camera-ready, should our paper be accepted.

When investigated on general strongly convex differentiable losses, the rate of SGD depends on some real that quantifies the “niceness” of the loss. A prominent such real is the condition number $\kappa$, the ratio between the largest and smallest eigenvalues of the Hessian (a second order loss parameter) of the loss [bsSO]. The convergence rate of SGD can be summarised as $\mathrm{Loss}(H_T) - \mathrm{Opt} \leq O (\kappa / T)$. This makes sense: the smaller $\kappa$, the more the loss resembles a 1D strongly convex curve rotated around a revolution axis and so any gradient step has to point to a large extent towards the global optimum (Slide 29 in [bsSO]). Hence, a rough “nice picture” for a loss to grant fast SGD convergence is that of a paraboloid of revolution.

Consider our case: what is the nice picture when the loss can be arbitrary for boosting ? This picture becomes more complicated and there are reasons to believe that an additional "degree of complexity" is necessary:

• Our weights depend on a quantity that generalises the first order derivative (Step 2.6) and pretty much like in ordinary boosting, large weights in absolute value point to examples for which substantial loss variation is possible via the weak learner. We write “loss variation” and not “loss decrease” because labels can be flipped (compared with AdaBoost for example, Step 2.1) so having a good weak learner is not sufficient anymore for good convergence. It makes sense thus that convergence would include an aggregator of “how nice are the weights”. Perhaps surprisingly, a relevant aggregator is trivial: it is a quadratic function of the average weight, the numerator of $\rho$. In the loss space, it is just the quadratic expectation of secants’ slopes (19) ! If this expectation is large in absolute value, there is leeway for better models. This picture is particularly clear in the convex case with the exponential loss for example, as in this case it just means that we are far from the minima of the loss.

• But unfortunately in the general case of an arbitrary loss, it just gives a partial view of what is sufficient for good convergence ! Indeed, we could be optimising a loss function that jiggles a lot locally (consider Griewank’s function as an example). In this case, all slopes could be located around different basins, with different local minima nearby, and the information of a large $|\overline{W}_{1,t}|$ would then be not sufficient to ensure a better overall loss afterwards. Read: while in SGD first-order information is intuitively not enough for the best characterisation of convergence, just ensuring convergence in our case requires higher order v-derivative information (than just the secants’).

We were pleased to realise that order-two v-derivative information is in fact sufficient, and this fits in the denominator of $\rho$. From a parallel with the Hessian in SGD, one can see that a small denominator yields smaller local “curvature” (i.e. less potential for local "jiggling") and with a large enough numerator, sufficient information is then collected in a single real to grant good, guaranteed boosting rate. We are sure the reviewer grasps at this point the subtleties of our approach that surely do not follow from any state of the art boosting analysis [RNT].

1. The authors, unfortunately, do not define it in Section 3 [...]

[RWL1] Doing so would imply defining the notion of edge, normalized edge; it seems however that it would indeed find a legitimate place there after our proposal [RDML].

2. The definition is not self-contained [...]

[RWL2] after [RDML] [RWL1], it would be straightforward to make it so, directly in Section 3

3. Honestly, I do not recognise that definition as "the traditional" one [...] To me, that would be a  $\gamma$-weak learner [...] whose average error is at most $1/2-\gamma$.

[RWL3] This is the original definition [fsAD]. However it rapidly got even weaker and generalized: the paper [fhtAL] shows that we can in fact require that the average error be slightly different from 1/2 instead of slightly smaller (polarity-reversal argument after their equation (20): if the weak classifier $h$ does worse than 1/2 accuracy then $-h$ does better than 1/2 accuracy). This is however still for $f = -1,1$. The paper [ssIB] generalizes the measure to $f \in [-1,1]$: their $r_t$ (Corollary 1) is our $\tilde{\eta}_t$ and the discussion relating it to the error is right after (page 303, par. 1). From here many papers started to adopt the edge / margin notion directly in the weak learning assumption, see for example [mnwRC] for a definition that looks just like ours.

Assumption 5.5 might be less "global" than one could expect [...]

[RWL4] Misunderstanding: it would not be a good idea to present the assumption the way proposed by the reviewer because then we risk losing sight of the fact that $h$ is normalized by its maximal empirical value. Our definition in fact coincides with [ssIB] (Corollary 1).

The proposition made later in the bullet points to instead divide by a global term (we assume it is a term computed over all weak hypotheses) could in fact break the purpose of the weak learning framework: suppose that one $h$ has a huge $M^* = 10000$ while the others have $M=1$. Then satisfying the weak learning assumption by all those hypotheses imposes, instead of having our $|\tilde{\eta}| \geq \gamma$, to have $|\tilde{\eta}| \geq \gamma \cdot M^*/M = 10 000 \gamma$, imposing the weak classifiers to be in fact strong in disguise.

At this point, we hope we have clarified the misunderstandings and our simple rewriting proposal would make it even easier to grasp the idea of the $\gamma$-weak learner.

Bullet points

$|**w**|$ is indeed the componentwise absolute value (we will put it in Section 3)

notation X is a bug -- it should have been noted $**wl**$. We shall fix it.

$\mathcal{S}_t$ is the set of examples that our algorithm uses. We have defined it in the algorithm itself.

See [RWL4] for the last bullet point.

[awWW] E. Ahmid and M. Warmuth. Winnowing with gradient descent. COLT 2020

[bsSO] F. Bach and S. Sra. Stochastic optimization: Beyond stochastic gradients and convexity. Tutorial at NeurIPS 2016

[bmdgCW] A. Banerjee, S. Merugu, I. Dhillon and J. Ghosh. Clustering with Bergman divergences. JMLR 2005

[btAI] P. L. Bartlett and M. Traskin. AdaBoost is consistent. JMLR 2007

[cmnowMB] Cranko, Menon, Nock, Ong and Walder. Monge blunts Bayes: Hardness Results for Adversarial Training. ICML 2019.

[fGF] J. Friedman. Greedy function approximation: a gradient boosting machine. Annals of Statistics 2001 (emphasis ours)

[fhtAL] J. Friedman, T. Hastie and R. Tibshirani. Additive logistic regression: a statistical view of boosting. AoS 2000

[fsAD] Y. Freund and R. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. JCSS 1997 (early version in EuroCOLT 1995).

[fsGT] Y. Freund and R. Schapire. Game theory, on-line prediction and boosting. COLT 1996

[ksNO] M. Kearns and S. Singh. Near-optimal reinforcement learning in polynomial time. ICML 1998.

[lrOW] K. G. Larsen and M. Ritzert. Optimal weak to strong learning. NeurIPS 2022

[mnwRC] Y. Mansour, R. Nock and R.C. Williamson. Random classification noise does not defeat all convex potential boosters irrespective of model choice. ICML 2023

[nnTP] R. Nock and F. Nielsen. The Phylogenetic Tree of Boosting has a Bushy Carriage but a Single Trunk. PNAS 2020.

[nwLO] R. Nock and R.C. Williamson. Lossless or quantised boosting with integer arithmetic. ICML 2019..

[sfblBT] R. Schapire, Y. Freund, P. Bartlett and W.S. Lee. Boosting the margin: a new explanation for the effectiveness of voting methods. ICML 1997.

[ssIB] R. Schapire and Y. Singer. Improved boosting algorithms using confidence-rated predictions. MLJ 1999.

[tAP] M. Telgarsky. A primal-dual convergence analysis of boosting. JMLR 2012

[tBW] M. Telgarsky. Boosting with the logistic loss is consistent. COLT 2013

[wvTS] M.K. Warmuth and S.V.N. Vishwanathan, Survey of boosting from an optimization perspective. Tutorial at ICML 2009

Of course. I will also update my scores as that is sure to remove much burden from the authors.

In short, my position on this work is

Looks like a nice contribution, but the presentation did not allow me to fully understand how nice it is. I will assume it is an OK contribution, but I am confident it was poorly presented (not just due to the mismatch of expertise). That amounts to a score of 5 (borderline accept). Moreover, I know that I could not detect if this contribution was some sort of sham. Among other reasons, this motivates me to lower my confidence score to 1 as "The submission is not in (my) area or the submission was difficult to understand".

On noteworthy technical matters

We did not quite finish much. For example, I attempted to reframe the problem to better contextualize it, further shaving any learning theory taste in it. However, I felt that the authors' reply was not very helpful, so I give up on that.

As a last quick note about the AC's reminder that this discussion will become public (it could help the authors understand my position)

This is what is giving me energy. To me, I am fighting FOR the authors (there might even be (talented!) students among them). I do believe they are skilled researchers and, thus, it would not be worth for them to risk tarnishing their reputation even if the risk was small. Again, I do not think they are malicious, as I mentioned, but my personal opinion is that others could suspect.

Thank you.