How to Boost Any Loss Function
Authors: Richard Nock
Yishay Mansour
Venue: NeurIPS 2024 poster (2024)
Keywords: boosting
loss functions
zeroth-order optimisation
Primary area: learning_theory
TL;DR: An algorithm that essentially provably boosts any loss

Abstract: Boosting is a highly successful ML-born optimization setting in which one is required to computationally efficiently learn arbitrarily good models based on the access to a weak learner oracle, providing classifiers performing at least slightly differently from random guessing. A key difference with gradient-based optimization is that boosting's original model does not requires access to first order information about a loss, yet the decades long history of boosting has quickly evolved it into a first order optimization setting -- sometimes even wrongfully *defining* it as such. Owing to recent progress extending gradient-based optimization to use only a loss' zeroth ($0^{th}$) order information to learn, this begs the question: what loss functions be efficiently optimized with boosting and what is the information really needed for boosting to meet the *original* boosting blueprint's requirements ?

We provide a constructive formal answer essentially showing that *any* loss function can be optimized with boosting and thus boosting can achieve a feat not yet known to be possible in the classical $0^{th}$ order setting, since loss functions are not required to be be convex, nor differentiable or Lipschitz -- and in fact not required to be continuous either. Some tools we use are rooted in quantum calculus, the mathematical field -- not to be confounded with quantum computation -- that studies calculus without passing to the limit, and thus without using first order information.

How to Boost Any Loss Function
Richard Nock Google Research ri chcrrdnockkgooglee... com
Yishay Mansour
Tel Aviv University Google Research nansour@google.c com
Abstract
Boosting is highly successful ML-born optimization setting in which one is required to computationally efficiently learn arbitrarily good models based on the access to weak learner oracle, providing classifiers performing at least slightly dif- ferently from random guessing. A key difference with gradient- gradient-based optimization is that boosting's 's original model does not requires access first order information about a loss, yet the decades long history of boosting has quickly evolved it into a first order optimization setting sometimes Owing to recent progress extending gradient- based optimization to use only a loss' zeroth (0th) order information to lear, this begs the question: what loss functions can be efficiently optimized with boosting and what is the information really needed for boosting meet the original boosting blueprint's requirements?
wrongfully defining it such,
We provide a constructive formal answer essentially showing that any loss function can be optimized with boosting and thus boosting can achieve feat yet known to be possible in the classical 0 order setting, since loss functions are not required to be be convex, nor differentiable to be continuous either. Some tools we use are rooted in quantum calculus, the mathematical field not be confounded with quantum computation that studies calculus without passing to the limit, and thus without using first order information.
Lipschitz and fact not required
1 Introduction
In MI., zeroth order optimization has been devised as an alternative to techniques that would otherwise require access > 1-order information about the loss to minimize, such as gradient descent (stochastic not, constrained not, etc., see S Such approaches replace the access to a so-called oracle providing derivatives for the loss at hand, operations that can consuming or not available in exact form in the ML world, by the access to cheaper function value oracle, providing loss values at queried points.
Zeroth order optimization has seen considerable boost in ML over the past years, over many settings and algorithms, yet, there one foundational ML setting and related algorithms that, to our knowledge, have not yet been the subject of investigations: boosting (32 31.. Such question is very relevant: boosting has quickly evolved as a technique requiring first-order information about the loss optimized [6] Section 10.3], [1] Section 7.2.2] (53] It is also not uncommon to find boosting reduced to this first-order setting D. However, originally, the boosting model did not mandate the access to any first-order information about the loss, rather requiring access to a weak learner providing classifiers least slightly different from random guessing [3I] the context of zeroth-order optimization gaining traction in ML, it becomes crucial to understand not just whether differentiability is necessary for boosting, but more generally what are loss functions that can be boosted with weak learner and in fine where boosting stands with respect to recent formal progress on lifting gradient descent to zeroth-order optimisation.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In this paper, we settle the question: we design a formal boosting algorithm for any loss function whose set of discontinuities has zero Lebesgue measure. With traditional floating point encoding (e.g. float64), any stored loss function would de facto meet this condition; mathematically speaking, we encompass losses that are not necessarily convex, nor differentiable or Lipschitz. This is a key difference with classical zeroth-order optimization results where the algorithms are zeroth-order but their proof of convergence makes various assumptions about the loss at hand, such as convexity, differentiability (once or twice), Lipschitznsss, etc. Our proof technique builds on simple boosting technique for convex functions that relies on an order-one Taylor expansion to bound the progress between iterations [4)]. Using tools from quantum calculu: we replace this progress using u-derivatives and a quantity related to a generalisation of the Bregman information [7]. The boosting rate involves the classical weak learning assumption's 's advantage over random guessing and a new parameter bounding the ratio of the expected weights (squared) over a generalized notion of curvature involving v-derivatives. Our algorithm, which learns linear model, introduces notable generalisations compared to the AdaBoost / gradient boosting lineages, chief among which the computation of acceptable offiets for the v-derivatives used to compute boosting weights, offsets being zero for classical gradient boosting. To preserve readability and save space, all proofs and additional information are postponed to an Appendix.
2 Related work
Over the past years, ML has seen a substantial push to get the cheapest optimisation routines, in general batch [4], online [27]. distributed 3 adversarial [20] or bandits settings 2 more specific settings like projection-free free [26 28,
51 or saddle-poin optimisation 125 38). We summarize
several dozen recent references in Table I in terms of assumptions for the analysis about the loss optimized, provided in Appendix, Section A Zeroth-order optimization reduces the information available to the learner to the "cheapest" one which consists in (loss) function values, usually via a so-called function value oracle. However, as Table [ shows, the loss itself is always assumed to have some form of "niceness" to study the algorithms' convergence, such as differentiability. Lipschitzness, convexity, etc. Another quite remarkable phenomenon is that throughout all their diverse settings and frameworks, not a single one of them addresses boosting. Boosting is however natural candidate for such investigations, for two reasons. First, the most widely used boosting algorithms are first-order information hungry 6 53 : they require access to derivatives to compute examples' weights and classifiers' leveraging coefficients. Second and perhaps most importantly, unlike other optimization techniques like gradient descent, the original boosting model does not mandate the access to first-order information oracle to learn, but rather to weak learning oracle which supplies classifiers performing slightly differently from random guessing 32 31. Only few approaches exist to get to "cheaper" algorithms relying less assumptions about the loss at hand, convergence proofs, as for example when alleviating convexity [16] 46) or access to gradients of the loss [54). Such questions are however important given the early negative results on boosting convex potentials with first-order information 37 and the role of the classifiers in the negative results 3)
and to our knowledge do not have poosting-complinn
Finally, we note that a rich literature has developed in mathematics as well for derivative-fre optimisation [34), yet methods would also often rely assumptions included in the three above (e.g. [42). It must be noted however that derivative-free optimisation has been implemented in computers for more than seven decades [24]
3 Definitions and notations
The following shorthands are used: [n]
(1,2,...nn) for n E N₂. 2. [a, b]
[min(2a, =b), max(2a, =b)] for 2 R, a be E R.. In the batch supervised learning setting, one is given a training set of m examples 5 {( B1), [m]]. where æ; E X is an observation (X is called the domain: often, X = R and yi E = [-1,1] is a label, or class. We study the empirical convergence of boosting, which requires fast convergence training. Such setting is standard in zeroth order optimization [42]. Also, investigating generalization would entail specific design choices about the loss at hand and thus would restrict the scope of result (see e.g. [8]. The objective is to
*Calculus "without limits" quantum devices.
30 (thus without using derivatives), not to be confounded with calculus on
2

---

F
Qr(2, +0,z)
F
1
43
24
21
2
Figure 1: Left: value of (2'12)) for convex F, Bregman Secant distortion is positive (z' 21, green), negative (e' 22, red), minimal (z' 23)
and various a' (colors), for which the
null (z' = 24, 2). Right: depiction of QF(z, 2 + =²=²) for non-convex F (Definition 4.6
learn a classifier, i.e. a function h X - which belongs to a given set H. The goodness of of some h on S is evaluated from given function F IR R called loss function, whose expectation on training is sought to minimized:
h( | [[(]((()
The set of most popular losses comprises convex functions: the exponential loss (FEx((2) = exp(-2)) the logistic loss (F (F))0(2) log(1 exp(-2))), the square loss (Fso(z) - 2)²), the Hinge loss (Fx(2) = ma 1 2)). These are surrogate losses because they all define upperbounds of the 0/1-loss (Fan zg0. "1" being the indicator variable).
Our ML setting is that of boosting [3I] It 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 relatively to the sample over which they were trained. Our goal is to devise a so-called "boosting" " algorithm that can take any loss as input and training sample S and target loss value F4 and after some T calls to the weak learner crafts classifier Hr satisfying FSS, Hr) < Fx, where T depends on various parameters of the ML problem. Our boosting architecture is linear model: HT = E. oghe where each h; is output from the weak learner and leveraging coefficients ae have to be computed during boosting. Notice that this is substantially more general than the classical boosting formulation where the loss would be fixed or belong to a restricted subset functions.
u-derivatives and Bregman secant distortions
Unless otherwise stated, in this Section, F is function defined over IR
Definition 4.1. (30 For any z, E R. we 8 Fz)) o))=+o)=F(a)) denote the v-derivative of F in
This expression, which gives the classical derivative when the offset y O, is called the h-derivative in quantum calculus (30] Chapter 1]. We replaced the notation for the risk of confusion with classifiers. Notice that the v-derivative is just the slope of the secant that passes through points (2, F(z)) and
(z + v, (z + v)) (Figure D. Higher order u-derivatives can be defined with the same offset used several times 30 Here, we shall need a more general definition that accommodates for variable offsets.
Definition 4.2. Let 01, 02, On E IR and V i {UI, U2, vn) and E R. The V-derivative 8 is:
F(z)
if
V Ø
SyF(s) 8( (8r F)()
8,, F(z)
if
v
= (m1
otherwise
If 0 = v, Vie [n] then we write 5 F(z) = 8 F(2).
In the Appendix, Lemma B.1 computes the unravelled expression of 8 F(2), showing that the order of the elements in does not matter; n called the order of the V-derivative.
We now define generalization of Bregman divergences called Bregman Secant distortions.

---

Definition 4.3. For any 2, 2,2',00 u I, the Bregman Secant distortion (F1a(22122) with generator F and offset is:
S//o(21|z) -()))
Even if F is convex, the distortion is not necessarily positive, though it is lowerbounded (Figure I There is an intimate relationship between the Bregman Secant distortions and Bregman divergences. We shall use definition slightly more general than the original one when F' is differentiable [1] eq. (1.4),, introduced in information geometry [5] Section 3.4] and recently reintroduced ML [10]
Definition 4.4. The Bregman divergence with generator F (scalar, convex) between z' and is Dr(='|2z) = F(z') + (2) - z'z, where F" (z) sup, t2 - F(t) is the corvex conjugate of F.
We state the link between SFI and Dr (proof omitted).
Lemma 4.5. Suppose F strictly corvex differentiable. Then (
SFju(z122) = DD(2'11F((2))
Relaxed forms Bregman divergences have been introduced information geometry 43
Definition 4.6. For any a, b, R, denote for short Ia.6 [minfa, b), max(a, bb] and (uv) = ou (1 a)v. The Optimal Bregman Information (OBI) of F defined by triple (a, b, c) R is:
Qrla,b,c) = max as(ab)..Ea..e
((F())(())). F((ab)))))
As represented in Figure I (right), the OBI is obtained by drawing the line passing through (a, F())) and (6, F()) and then, in the interval laa.c. look for the maximal difference between the line and F. We note that QF non negative because a lla.c and for the choice a the RHS in (T) We also note that when F is convex, the RHS is indeed the maximal Bregman information of two points in 7 Definition 2], where maximality is obtained over the probability measure. The following Lemma follows from the definition of the Bregman secant divergence and the OBI. An inspection of the functions in Figure
[ provides graphical proof.
Lemma 4.7. For any F.
Vz, U,, (p)((()))) -Qr(z, v.2')
and if F is convex.
Vz, Vz, Vz' 2, SF/o Uz,u,'' e R, Sr - QF(Z,= +))
(3)
We shall abbreviate the two possible forms of OBI in the RHS of 2 as:
@0(2,'/0)) = Q if F convex otherwise
(4)
Qr(z,2+0,,))
Boosting using only queries on the loss
We make the assumption that predictions of so-called "weak classifiers" are finite and non-zero training without loss of generality (otherwise a simple tweak ensures it without breaking the weak learning framework, Appendix, Section B.2). Excluding ensures algorithm does not make use of derivatives.
Assumption 5.1. > 0, Vi e [m]. (x;() (0, +00) (we thus let M, = max; (xx()))))
For short, we define edge quantities for i e [m]] and 1, 1,2,... Cs - 04 (x:)( ēω = y, (xx,),
(5)
where a is leveraging coefficient for the weak classifiers in ensemble HT()) Ere ashe())
We observe
ēn ē(t-1)e en

---

Algorithm SECBOOST(S, T) red boxes pinpoint substantial differences with "classical" boosting
Input sample 5 (m;, i 1,2,,..,m,. number of iterations T, initial (ho, vo) (constant classification and offset).
Step 1 let Hg < 1- ho and W1 uup F(ha)
I/ hu, Uo # 0 chosen s. t. 8 F(hu) * 0
Step 2: for 1, ..,,
Step 2.1 let h; WL(S:, ( wel)
//weak learner call, S = { sign( wn))
Step 2.2 let T/: + (1/m) E, weyyshee ( (c))
//unnormalized edge
bound W available (Section 5.3
otherwise general procedure
pick m 1) and
Step 2.3
41 211 +1++0 k.)
n. md) (6)
Du (S,VE, w.) W 2.1 0,5, 0, (0, || Theorem
Step 2.4: let 11, < H1-1 ar he
/classifier update
Step 2.5 if [e 0z MfW 2,1) A Ø, ViE E [m] then
//nww offsets
for i = 1,2, ... m, let
U/s - 00(1,,, 0f M2W2.. 2,)
else return Hy: Step 2.6 for i 1, 2, m, let
//weight update
Wi - Ser ((y:H((x:)
(7)
Step 2.7 if w 0 then break;
Return Hr.
5.1
Algorithm: SECBoOST
5.1.1
General steps
Without further ado, Algorithm SECBoOST presents our approach to boosting without using deriva- tives information. The key differences with traditional boosting algorithms red color framed. We summarize its key steps.
Step 1 This is the initialization step. Traditionally in boosting, would pick he 0. Note that w1 is not necessarily positive. Up is the initial offset (Section[4) 4
Step This step calls the weak learner, as in traditional boosting, using variable "weights" examples (the coordinate-wise absolute value of w, denoted ww,)). The key difference with tradi- tional boosting is that examples labels can switch between iterations well, which explains that the training sample, St, is indexed by the iteration number.
Step 2.3 This step computes the leveraging coefficient a of the weak classifier h, It involves quantity, W2,,,
2.1, which we define as any strictly positive real satisfying
hr (xx()))) (MM,
Es-pmi
< W2.--
(8)
M2
For boosting rate's sake, we should find Wa, as small as possible. We refer to (5) for the e, notations; is the current (set of) offset(s) (Section 4 for their definition). The second-order V- derivative in the LHS plays the same role as the second-order derivative in classical boosting rates, for example 45 Appendix, eq. 29]. As offsets - 0. it converges second-order derivative; otherwise, they still share some properties, such as the sign for convex functions.
Lemma 5.2. Suppose F convex. For any R. c R. S(b.c)
0.
(Proof in Appendix, Section B.3) We can also see a link with weights variation since, modulo a slight abuse of notation, have (ees b(e F(ērr1)))
So,, WH. A substantial difference with traditional boosting algorithms is that we have two ways to pick the leveraging coefficient the first one can be used when convenient W2, is directly accessible from the loss. Otherwise, there is simple algorithm that provides parameters (including Wo,) such that ( is satisfied. Section 5.3
5

---

details those two possibilities and their implementation. In the more favorable case (the former one), a can be chosen in an interval, furthermore defined by flexible parameters E, 0, Re. (0, 1). Note that fixing beforehand these parameters is not mandatory: we can also pick any
ar Tu (o.
1
(9)
MM 2,4
and then compute choices for the corresponding E and Te. Et is important for the algorithm and both parameters are important for the analysis of the boosting rate. From the boosting standpoint, smaller E, yields a larger at and a smaller ne reduces the interval of values in which we can pick azy both cases tend to favor better convergence rates as seen in Theorem 5.3
Step 2.4 is just the crafting of the final model.
Step 2.5 is new boosting, the use of so-called offset oracle, detailed in Section 5.1.2
The weight update does not rely on a first-order oracle as in traditional boosting, but uses only loss values through u-derivatives. The finiteness of F implies the finiteness of weights. Step 2.7 Early stopping happens if all weights are null. While this would never happen with traditional (e.g. strictly convex) losses, some losses that unusual in the context of boosting can lead to early stopping. A discussion on early stopping and how to avoid it is in Section
Step 2.6
5.1.2 The offset oracle, 00
Let us introduce notation
TT((2) = (v: @p(et, (1-1), & 2), ViE [m]] V= 0.
(10)
(see Figure 3 below to visualize (z) for non-convex F) The offset oracle is used in Step 2.5, which is new to boosting. It requests the offsets to carry out weight update in (7) to an offset oracle, which achieves the following, for iteration #1, example #i, limit OBI
oo(t, 2) returns some (2)
(11)
Note that the offset oracle has the freedom pick the offset in whole set. Section 5.4 investigates implementations of the offset oracle, so let us make few essentially graphical remarks here. 00 does not need to build the whole [z) to return some E (z)(z) for Step 2.5 in SECBOOST. In the construction steps of Figure 3, as soon as O * Ø. one element of O can be returned. Figure 4
presents more examples of (z). One can remark that the sign of the offset Un in Step 2.5 of
SEcBoOST is the same as the sign of ê(t-1); ēτs
hy Hence, unless F is derivable or all edges yeha( are of the same sign (Vi), the set offsets returned in Step 2.5 always contain at least two different offsets, one non-negative and one non-positive (Figure 4 (a-b)).
5.2
Convergence of SECBoOST
The offset oracle has technical importance for boosting: (=x(=) is the set of offsets that limit an OBI for a training example (Definition [.6). The importance for boosting comes from Lemma OBI implies lowerbounding a Bregman Secant divergence, which will also guarantee a sufficient slack between two successive boosting iterations. This is embedded a blueprint of proof technique to show woosting-compliann convergence which is not new, e.g. We now detail this convergence.
4.7 upperbounding
45..
Remark that the expected edge 7) in Step 2.2 of SECBoOST is not nonmalized. We define a normalized version of this edge as:
[-1, th = Σ Weel he(x::)
Tts
(12)
We
M,
with Tt: = y4 sign(ww), W. Σg |wwl E, 18 (()(-11)))-- Remark that the labels are corrected by the weight sign and thus may switch between iterations. In the particular case where the loss is non-increasing (such as with traditional convex surrogates), the labels do not switch. We need also a quantity which is, in absolute value, the expected weight:
W 1. [E/[m [m] (8 F(((
(we indeed observe W 1,t = [Eq-[m]] [ I). (13)

---

In classical boosting for convex decreasing losse: weights are non non-negative and converge to minimum (typically 0) as examples get the right class with increasing confidence. Thus, W I, can he an indicator of when classification becomes "good enough" to stop boosting. In our more general setting, it shall be used in similar indicator. We are now in a position to show first result about SECBOOST.
Theorem 5.3. Suppose assumption 5.1 holds. Let Fu = F(S, ho) in SECBoOST and z" any real such that F(2*) & Fo- Then we are guaranteed that classifier Hy output by SECBoOST satisfies HT) & F(=*) when the number of boosting iterations yields:
T
W -
T²)
4(F0-
(14)
W (21 + +e))
where parameters Ct,, Tt appear in Step 2.3 of SECBOOST
(proof in Appendix, Section B.4 We observe the tradeoff between the freedom in picking parameters and convergence guarantee as exposed by (14): to get more freedom in picking the leveraging coefficient du, we typically need n. large (Step 2.3) and to get more freedom in picking the offset 2 # O, we typically need E, large (Step 2.5). However, allowing more freedom in such ways reduces the LHS and thus impairs the guarantee in (14). Therefore, there is a subtle balance between "freedom" of choice and convergence. This balance becomes more clear as boosting compliance formally enters convergence requirement.
convergence We characterize convergence in the boosting framework, which shall include the traditional weak learning assumption.
Assumption 5.4. (y- week Learning Assumption, y-WIA) We assume the following on the weak learner: By > O such that Vt > 0, |ix >> Y
As is usually the case in boosting, the weights are normalized in the weak learning assumption (1) So the minimization "potential" of the loss does not depend on the absolute scale of weight. This is not surprising because the loss is "nice" in classical boosting: a large y guarantees most examples' edges moving to the right of the r-axis after the classifier update which, because the loss strictly decreasing (exponential loss, logistic loss, etc.), is sufficient to yield smaller expected loss. In our case it is not true anymore as for example there could be a local bump the loss that would have it increase after the update. This is not even a pathological example: one may imagine that instead of a single bump the loss jiggles a lot locally. How can we keep boosting operating such cases ? A sufficient condition takes the form of a second assumption that also integrates weights, ensuring that the variation of weights is locally not too large compared to (unnormalized) weights, which is akin to comparing local first- and second-order variations of the loss in the differentiable case. We encapsulate this notion in what we call a weight regularity assumption.
Assumption 5.5. (p- Weight Regularity Assumption, p- p-WRA) Let Pt W Wi./W. 2.1. We assume there exists p such that Vt 1, Pt > p.
W2,1
In Figure 2 we present a(n overly) simplified depiction of the cases where W₂ 2,c is large for "not nice" losses, and two workarounds on how to keep it small enough for the WRA to hold. Keep in mind that WT. I.e an expected local variation of the loss (3). (5) so as goes to zero, boosting converges to local minimum and it is reasonable to expect that the WRA breaks. Otherwise, there are two strategies that keep W2, relatively small enough for WRA to hold: either we pick small enough offsets, which essentially works for most losses but make us converge in general to local minimum (this is in essence our experimental choice) or we optimize the offset oracle so that it sometimes "passes" local jiggling (Figure[(cd)) While this eventually requires to tune the weak learner jointly with the offset oracle and fine-tune that latter algorithm on loss-dependent basis, such a strategy can be used to eventually pass local minima of the loss. To do so, "larger" offsets directly translate into corresponding requests for larger magnitude classification for the next weak classifier, for the related examples. We are now position to state a simple corollary to Theorem 5.3
This is an important class of losses since it encompasses the convex surrogates of symmetric proper losses
4
49
7

---

"nice" loss
"not nice" loss
A
Bi
(a) W 2, small
(b) W can be large
(c) workaround 1
(d) workaround 2
Figure 2: Simplified depiction of Wa 2, "regimes" (Assumption 5.5). We only plot the components of the u-derivative part in (8): removing index i for readability, we get 8 (e, F(ē--1) = (B, A,)/(yH,( (2) yH(-1(2) with A, = s. ((yH;-1(z)) = -w; and B, S (()H(()) (=-4 iff V Ut). the loss is "nice" like the exponential or logistic losses, we always have small 2,2 (a). Place bump in the loss (b-d) and the risk happens that W2,r too large for the WRA to hold. Workarounds include two strategies: picking small enough offsets (b) or fit offsets
large enough to pass the bump (c). The blue arrow in (d) is discussed in Section
Algorithm 2 SSLVE, w.
Input sample S ((ar,, yi), 1,2, ur Rm, : X - TR.
Step : find any > such that
In(w, h) m ((igisign) h)) a), a)] 1.
(16)
(n(w,
Return sign(1)( w. h)) a.
Corollary 5.6. Suppose assumptions 5.1 5.5 and 5.4 hold. Let = h() in SECBooST and
any real such that F(2) & Fo. If SEC is run for number T of iterations satisfying
T> 4FFo F(z))
1 max Ex
(15)
Y2p
1 maX4e[T] n?
then F(S, & F()).
We remark that the dependency in y is optimal 4
5.3 Finding 2,4
There is lots of freedom in the choice of a₁ in Step 2.3 of SECBOOST, and even more if we look (9). This, however, requires access to some bound W 2.t- In the general case, the quantity it upperbounds in (8) also depends on because eti ar, (x:). So unless we can obtain such "simple" Wa. that does not depend on at, 6 and 9 provide a system to solve for at-
W2,t via properties of Classical assumptions on loss functions for zeroth-order optimization can
provide simple expressions for 2.c (Table l}. Consider smoothness: we say that F is 3-smooth if is derivable and its derivative satisfies the Lipschitz condition [='(2'== [=)) < 3/ - 2/, Vz,
[1]. Notice that this implies the condition on the v-derivative of the derivative: F'()) < B,V
This also provides straightforward useful expression for W 2,t-
Lemma 5.7. Suppose that the loss F 8-smooth. Then we can fix W = 23.
(Proof in Appendix, Section B.5 What the Lemma shows is that bound on the u-derivative of the derivative implies a bound on order-2 V-derivatives (in the quantity that W bounds (8)). Such condition on u-derivatives is thus weaker than condition on derivatives, and it strictly weaker we impose strictly positive lowerbound on the offset's 's absolute value, which would be sufficient to characterize the boosting convergence of SECBOOST.
A general algorithm for W2, If cannot make any assumption on F, there is simple way to first obtain a and then W 2.,, from which all other parameters of Step 2.3 can be computed. We first need a few definitions, We first generalize the edge notation appearing in Step 2.2:
17( w. h)) = E,-[m] [w,):h(<;)],

---

Tu(e)
Tu(e)
Tu[B]
12.
61
(d)
Figure 3: A simple way to build (2) for a discontinuous loss F (êts < étt-1)e 1)e and are represented), being the set of solutions as it built. We rotate two half-lines, one passing through (ēts, F();))
(thick line. (A)) and parallel one translated by (dashed line) (a). As soon (A) crosses F on any point (z' ((z)) with 2 & Eqs while the dashed line stays below F. we obtain a candidate offset for 0O, namely
z' éu.. In (b). we obtain interval of values. We keep rotating (4), eventually making appear several intervals for the choice of F is not convex (c). Finally, when reach angle such that the maximal difference between (A) and F in [ētr -()-)))]] is (2 can be located an intersection between F and the dashed line), we stop and obtain the full (=) (d).
F
ipp
di
(a)
(b)
(c)
Figure 4: More examples of ensembles (2) (in blue) for the F in Figure 3 (a): [2(2) the union
of two intervals with all candidate offsets non negative. (b): it is a single interval with non-positive offsets. (c): at discontinuity, 2 is smaller than the discontinuity, we have no direct solution for (z)(z) for least one positioning of the edges, but simple trick bypasses the difficulty (see text).
Fly: H(y:H)))( We define so that f) 17((r, ht). Remind the weight update, Wh: -d 1>5 "partial" weight update,
(a(aa = -n Flay,hi + y1
(17)
(if we were to replace -11-111 by Ur and let a a, then (a)(a)) would be w(++1)s. hence the partial weight update). Algorithm presents the simple procedure find aạ, Notice that we use with sole dependency on the prospective leveraging coefficient; we omit for clarity the dependences in the current ensemble (H.), weak classifier (h) and offsets (v,)) needed compute [T]..
Theorem 5.8. Suppose Assumptiins 5.7 and 5.4 hold and F is continuous at all abscissae (ē(-11) y; H. (æ:), E [m]]. Then there are always solutions to Step of SOLVE,, and if we let SOLVE. w. hi) and then compute
(ar,).
W 2,
[i-[m]]
((ocrdh (( F(
M2
then W W2, 2,t satisfies
8 and or satisfies (6) for some &t 0, (0,
The proof, in Section B.6 proceeds by reducing condition 9 to T6p. The Weak Learning Assumption (.44) is important for the denominator in the LHS of (66 be non zero. The continuity assumption at all abscissae is important to have lim.--0 17( ( hy) = 17, which ensures the existence of solutions to (16), also easy to find, e.g. by simple dichotomic search starting from initial guess for a. Note the necessity of being continuous only at abscissae defined by the training sample, which is finite in size. Hence, if this condition is not satisfied but discontinuities of F are of Lebesgue measure O, it is easy to add an infinitesimal constant to the current weak classifier, ensuring the conditions of Theorem 5.8 and keeping the boosting rates.
5.4 Implementation of the offset oracle
Figure explains how to build graphically Tz=(2) for a general F. While not hard implement a general procedure following the blueprint (i.e. accepting the loss function as input), it would be far

---

from achieving computational optimality: a much better choice consists in specializing it to the (set of) loss(es) at hand via hardcoding specific optimization features of the desired loss(es). This would not prevent "loss oddities" to get absolutely trivial oracles (see Appendix, Section B.7].
6 Discussion
For efficient implementation, boosting requires specific design choices to make sure the weak learning assumption stands for as long as necessary; experimentally. it is thus a good idea to adapt the weak learner to build more complex models iterations increase (e.g. learning deeper trees), keeping Assumption 5.4] valid with its advantage over random guessing parameter Y > O. In our more general setting, our algorithm SECBooST pinpoints two more locations that can make use of specific design choices to keep assumptions stand for a larger number of iterations.
The first is related to handling local minima. When Assumption 5.5 breaks, it means we are close to a local optimum of the loss. One possible way of escaping those local minima is to adapt the offset oracle to output larger offsets (Step 2.5) that get weights computed outside the domain of the local minimum. Such offsets can be used to inform the weak learner of the specific examples that then need to receive larger magnitude in classification, something
have already discussed in Section S
There is also more: the sign of the weight indicates the polarity of the next edge (cc., (5) needed
to decrease the loss in the interval spanned by the last offset. To simplify, suppose substantial
fraction of examples have an edge é, in the vicinity of the blue dotted line in Figure 2 (d) so that the
loss value is indicated by the big arrow and suppose their current offset u4-1 so that their weight (positive) signals that to minimize further the loss, the weak learner's 's next weak classifier has to have positive edge over these examples. Such is the polarity constraint which essentially comes to satisfy the WLA, but there is a magnitude constraint that comes from the WRA: indeed, if the positive edge too small so that the loss ends up in the "bump" region, then there is risk that the WRA breaks because the loss around the bump is quite flat, so the numerator of pr. in Assumption 3.5] can be small. Passing the bump implies escaping the local minimum at which the loss would otherwise be trapped. Section (.44 has presented a general blucprint for the offset oracle but more specific implementation designs can be used; some are discussed in the Appendix, Section B.7
The second is related to handling losses that take on constant values over parts of their domain. To prevent early stopping in Step 2.7 of SECBoOST, one needs W++1 * O. The update rule of we imposes that the loss must then have non-zero variation for some examples between two successive edges (5. If the loss F is constant, then clearly the algorithm obviously stops without learning anything. If F is piecewise-constant, this constrain the design of the weak learner to make sure that some examples receive different loss with the new model update H. As explained in Appendix, Section I. this can be efficiently addressed by specific designs on SOLVE..
In the same way as there is no "I size fits all" weak learner for all domains in traditional boosting, we expect specific design choices to be instrumental in better handling specific losses in our more general setting. Our theory points two locations further work can focus on.
7 Conclusion
Boosting has rapidly moved an optimization setting involving first-order information about the loss optimized, rejoining, in terms of information needed, that of the hugely popular (stochastic) gradient descent. But this was not a formal requirement of the initial setting and in this paper, we show that essentially any loss function can be boosted without this requirement. From this standpoint, our results put boosting in a slightly more favorable light than recent development on zeroth-order optimization since, to get of the assumptions that those analyses usually rely on. Of course, recent advances in saroth-order optimization have also achieved substantial design tricks for the implementation of such algorithms, something that undoubtedly needs to be adressed our case, such as for the efficient optimization of the offset oracle. We leave this as an open problem but provide in Appendix some toy experiments that a straightforward implementation achieves, hinting that SECBoOST can indeed optimize very "exotic" losses.
convergence, we do not need the loss to meet any
10

---

References
[1] A. Akhavan, E. Chzhen, M. Pontil, and A.-B. Tsybakov. A gradient estimator via 11- randomization for online zero-order optimization with two point feedback. In Neur 2022.
[2] A. Akhavan, M. Pontil, and A.-B. Tsybakov. Exploiting higher order smoothness in derivative- free optimization and continuous bandits. In NeurlPS 33,, 2020.
[3] A. Akhavan, M. Pontil, and A.-B. Tsybakov. Distributed zero-order optimisation under adver- sarial noise. In NeurlPS#34, 2021.
[4] N. Alon, A. Gonen, E. Hazan, and S. Moran. Boosting simple learners. In STOC'21, 2021.
[5] S.-I. Amari and H. Nagaoka. Methods of Information Geometry. Oxford University Press, 2000.
[6] F. Bach. Learning Theory from First Principles. Course notes, MIT press (to appear), 2023.
[7] A. Banerjee, S. Merugu, I. Dhillon, and J. Ghosh. Clustering with bregman divergences. In Proc. of the 4th SIAM International Conference on Data Mining, pages 234-245, 2004.
[8] P.-L. Bartlett and Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. JMLR, 3:463-4822 2002.
[9] G. Biau, B. Cadre, and L. Rouvière. Accelerated gradient boosting. Mach. Leam.., 108(6))971- 992, 2019.
[10] M. Blondel, A.-F. T. Martins, and V. Niculae. Learning with Fenchel-Young losses. J. Mach. Learn. Res., 21:35:1-35:69, 2020.
[11] L. M. Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Comp. Math. and Math. Phys., 7:200-217, 1967.
[12] S. Bubeck. Convex optimization: Algorithms and complexity. Found. Trends Mach. Learn., 8(3-4):231-357 2015.
[13] P.-S. Bullen. Handbook of means and their inequalities. Kluwer Academic Publishers, 2003.
[14] H. Cai, Y. Lou, D. McKenzie, and W. Yin. A zeroth-order block coordinate descent algorithm for huge-scale black- box optimization. In 38th ICML, pages 1193-1203, 2021.
[15] C. Cartis and L. Roberts. Scalable subspace methods for derivative-free nonlinear least-squares optimization. Math. Prog., 199:461-933 2023.
[16] S. Cheamanunkul, E. Ettinger, and Y. Freund. Non-convex boosting overcomes random label noise. CORR, abs/1409 0atx//449.299... 2905, 2014.
[17] L. Chen, J. Xu, and L. Luo. Faster gradient-free algorithms for nonsmooth nonconvex stochastic optimization. In International Conference Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 5219-5233. PMLR, 2023.
[18] X. Chen, S. Liu, K. Xu, X. Li, X. Lin, M. Hong, and D. Cox. Z0-AdaMM: Zeroth-order adaptive momentum method for black-box optimization. In NeurlPS*32, 2019.
[19] X. Chen, Y. Tang, and N. Li. Improve single-poing point zeroth-order optimization using high-pass and low-pass filters. In 39th ICML, volume 162 of Proceedings of Machine Learning Research, pages 3603-3620. PMLR, 2022.
[20] S. Cheng, G. Wu, and J. Zhu. On the convergence of prior-guided zeroth-order optimisation algorithms. N44r 2021.
[21] Z. Cranko and Nock. Boosted density estimation remastered. In 36th ICML, pages 1416 1425, 2019.
[22] W. de Vazelhes, H. Zhang, H. Wu, X. Yuan, and B. Gu. Zeroth-order hard hard-thresholding: Gradient enror vs. expansivity. In N55. 2022.
[23] D. Dua and Graff. UCI machine learning repository, 2021.
[24] E. Fermi and N. Metropolis. Numerical solutions of a minimum problem. Technical Report TR
LA- 1492, Los Alamos Scientific Laboratory of the University of California, 1952.

---

[25] L. Flokas, E.-V. Vlatakis- Gkaragkounis, and G. Piliouras. Efficiently avoiding saddle points with zero order methods: No gradients required. In NeurlPS432. 2019.
[26] H. Gao and H. Huang. Can stochastic zeroth- order frank-wolfe method converge faster for non-convex problems? In 37th ICML, pages 3377-3386, 2020.
[27] A. Héliou, M. Martin, P. Mertikopoulos, and T. Rahier. Zeroth-order non-convex learning via hierarchical dual averaging. In 38 ICML, pages 4192-4202, 2021.
[28] F. Huang, L. Tao, and S. Chen. Accelerated stochastic gradient-free and projection-free methods. In 37th ICML, pages 4519-4530, 2020.
[29] B. Irwin, E. Haber, R. Gal, and A. Ziv. Neural network accelerated implicit filtering: Integrating
neural network surrogates with provably convergent derivative free optimization methods. In 40th ICML, volume 202 of Proceedings Machine Learning Research, pages 44376-14389, PMLR, 2023.
[30] V. Kac and Cheung. Quantum calculus. Springer, 2002.
[31] M. J. Kearns and U. V. Vazirani. An Introduction to Computational Learning Theory. M.I.T. Press, 1994.
[32] M.J. Kearns. Thoughts on hypothesis boosting, 1988. ML class project.
[33] M.J. Kearns and Y. Mansour. On the boosting ability of top-down decision tree learning algorithms. J. Comp. Syst. Sc., 109-128, 1999.
[34] J. Larson, M. Menickelly, and S.-M. Wild. Derivative-free optimization methods. Acta Numerica, pages 287-404, 2019.
[35] Z. Li, P.-Y. Chen, S. Liu, S. Lu, and Y. Xu. Zeroth-order optimization for composite problems with functional constraints. In AAAI'22, pages 1453-7461. AAAI Press, 2022.
[36] T. Lin, Z. Zheng, and M.-I. Jordan. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. In NewrlPS 2022.
[37] P.-M. Long and R.-A Servedio. Random classification noise defeats all convex potential boosters. MLJ, 78(3):887-304 2010.
[38] C. Maheshwari, C.-Y. Chiu, E. Mazumdar, S. Shankar Sastry, and L.-.. Ratliff. Zeroth- order methods for convex-concave minmax problems: applications decision-dependent risk minimization. In 25th AISTATS, 2022.
[39] Y. Mansour, R. Nock, and R.-C. Williamson. Random elassification noise does not defeat all convex potential boosters irrespective of model choice. In 40 ICML, 2023.
[40] E. Mhanna and M. Assaad. Single point-based distributed zeroth-order optimization with non-convex stochastic objective function. 40th ICML, volume 202 of Proceedings of Machine Learning Research, pages
PMLR, 2023.
[41] M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning. MIT Press, 2018.
[42] Y. Nesterov and V. Spokoiny. Random gradient-free free optimization of convex functions. Founda- tions of Computational Mathematics, 17:527-566, 2017.
[43] Nielsen and R. Nock. The Bregman chord divergence. In Geometric Science of Information 4th International Conference, 2019, pages 299-308, 2019.
[44] R. Nock and A. K. Menon. Supervised learning: No loss no cry. In 37th ICML, 2020.
[45] R. Nock and R.-C Williamson. Lossless or quantized boosting with integer arithmetic. 36th ICML, pages 4829-4838, 2019.
[46] N.-E. Pfetsch and Sebastian Pokutta. IPBoost non-convex boosting via integer programming.
In 37th ICML., volume 119, pages 7663-7672, 2020.
[47] Y. Qiu, U.-V. Shanbhag, and F. Yousefian. Zeroth-order methods for nondifferentiable, noncon- vex and hierarchical federated optimization. N6 2023.
[48] M. Rando, C. Molinari, L. Rosasco, and S. Villa. Structured zeroth-order for non-smooth optimization. In Ne, 2023.
[49] M.-D. Reid and R.-C Williamson. Information, divergence and risk for binary experiments. JMLR, 12:731-811 2011.
12

---

[50] Z. Ren, Y. Tang, and N. Li. Escaping saddle points in zeroth-order optimization: the power of two-point estimators. 40th ICML, volume 202 of Proceedings of Machine Learning Research, pages
PMLR, 2023.
[51] A.-K. Sahu, M. Zaheer, and S. Kar. Towards gradient free and projection free stochastic 2019.
optimization. In 22nd AISTATS, pages
[52] W. Shi, H. Gao, and B. Gu. Gradient-free method for heavily constrained nonconvex opti- mization. 39th ICML, volume 162 of Proceedings of Machine Learning Research, pages 19935-19955. PMLR, 2022.
[53] M.-K. Warmuth and S. V.N. Vishwanathan. Tutorial: Survey of boosting from an optimization perspective. In 26th JCMI., 2009.
[54] T. Werner and P. Ruckdeschel. The column measure and gradient-free gradient boosting, 2019.
[55] H. Zhang and B. Gu. Faster gradient-free methods for escaping saddle points. In ICLR OpenReview.net, 2023.
[56] H. Zhang, Xiong, and B. Gu. Zeroth-order negative curvature finding: Escaping saddle points without gradients. In NeurlPS*35, 2022.
13

---

Appendix
To differentiate with the numberings in the main file, the numbering of Theorems, etc. is letter-based (A, B...
Table of contents
A quick summary of recent zeroth-order optimization approachess
Supplementary material on proofs
Pg
L5
Helper results
Pg 15
+
Removing the * 0 part in Assumption 5.1
Pg 16
Proof of Lemma 5.2
Pg
16
Proof of Theorem
5.3
Pg
Proof of Lemma 5.7
Pg
20
Proof of Theorem 5.8
Pg
20
Implementation of the offset oracle
Pg
21
Proof of Lemma B.5
Pg
22
Handling discontinuities in the offset oracle to prevent stopping in Step 2.5 of SECBOOSTPg
24
A boosting pattern that can "survive" above differentiability
Pg
24
- The case of piecewise constant losses for SOLVE,
Pg 26
Supplementary material on algorithms, implementation tricks and a toy experiment
Pg 26
14

---

F
V
main
reference
conv.
diff.
Lip.
smooth
Lb
diff.
ML topic
online MI.
distributed ML
online ML
S ETTAE ITT
alt. GD
alt. GD
alt. GD
alt. GD
alt. GD
20
alt. GD saddle pt opt alt. FW
25
26
28
alt. FW
22
alt. GD
27
online ML.
29
deep ML
35
alt. GD
36
saddle pt opt saddle pt opt distributed ML alt. GD federated ML saddle pt opt alt. FW alt. GD saddle pt opt saddle pt opt
38
40
48
47
IS
50
.51
52
55
[56
Table 1: Summary of formal assumptions about loss F used to prove algorithms' convergence in recent papers on zeroth order optimization, different ML settings (see text for details). We use "smoothness" as a portmanteau for various conditions on the > 1 order differentiabilliy condition of F. "conv." convex, "diff." " differentiable, "Lip." Lipschitz, "L.b" = lower-bounded, "alt. GD" general alternative to gradient descent (stochastic or not), "alt. FW" = idem for Frank-Wolfe. Our paper relies on no such assumptions.
A A quick summary of recent zeroth-order optimization approaches
a few dozens of recent approaches that can be related to zeroth-order optimization in various topies of MI.. Note that such approaches foeus boosting.
B
Supplementary material on proofs
B.1 Helper results
We now show that the order of the elements V does matter compute the V-derivative in Definition 4.2 For any a e {0, 13", we let 1, = Σ; di.
Lemma B.1. For any 2 E R. any n N2 and any {U1, U2..... vn c
IR,
F()) (-1) F(z
(-1)n-1o
En Ei E4=1
(18)
Hence, F is invariant to permutations of the elements V.
15

---

Proof. We show the result by induction on the size of V. first noting that
((m) F()) P()) F(2 + 11) F(2)
Σ (-1) F( + ovi). (19)
01
U2 oc(0,1)
We then assume that (18) holds for V, = (ol ...... Un. and show the result for for Vn+1 = Vn Vniufnt1). writing (induction hypothesis used in the second identity):
W..+F((6
Sv. F(, Un+1) Fv,,F(z)
en+1
(-1) F(z Lo
Ei= i 0aty + on+1) - Eoe 2o F(= + Ei= 0.0))
[++1 1/2
--e(0.pa--1)0-1 F(z Σx= 044, Un+1) + +E -Zoe(0.pp(--1)- FF (2 Σ 0.u))
n+1
i=1 V
20'E(0.))-- -(1)))) F(z + 2===1 0.04)
Eo -o(-1) (-1)mt1-1, l F(: EuT div)
(- F(z + 2i-1 d(u))
m++
(20)
0
as claimed.
We also have the following simple Lemma, which a direct consequence of Lemma B.T Lemma B.2. For all z, R, v, z' E Rn,, we have
F2 + z') 8,)(2) z' 8(2
(21)
Proof. It comes from Lemma B.1 that sisr,e (and we reorder terms).
(p, F(z) (6. (xF))/)
B.2 Removing the part in Assumption 5.1
Because everything needs to be encoded, finiteness is not really an assumption. However, the non-zero assumption may be seen as limiting (unless we are happy to use first-order information about the loss (Section 5). There is a simple trick to remove it. Suppose h zeroes on some training examples. The training sample being finite, there exists an open neighborhood II in 0 such that hī h4 + does not zero anymore on training examples, for any 5 E T. This changes the advantage in the WI.A (Definition 5.4) some y' satisfying (we assume
wlog)
MMc
5
Y
M
+
5
M, +
8
Y
(1+Y).
M₁
from which it is enough to pick d & MyMM((1 + y) to guarantee advantage 7 (1 E)y. I is constant, this translates in number of boosting iterations in Corollary 5.6 affected by constant factor that we can choose as close to I as desired.
B.3 Proof of Lemma 5.2
We reformulate
2 1 8 (brc) F(a) = b
Pla+b+de + F(a)
F(a + b) + F(a+d)
(22)
2
-p2
m
16

---

F
(Ai)
(A2).
Pi)
F
Figure 5: Left: representation of the difference of averages in (2 Each of the secants (A1) and (Az) can take either the red or black segment. Which one is which depends on the signs of and b, but the general configuration is always the same. Note that if F is convex, the other, which is the crux of the proof of Lemma 5.2 For the sake of illustration, suppose we can analytically have b, c 0. As converges to 0 but b remains 0, dp.c) [(a) becomes proportional to the variation of the average secant midpoint; the then-convergence of b to 0 makes ((b.c) ((a) converge to the second-order derivative of at a. Right: in the special case where F is convex, one of the secants always sits above the other.
necessarily sits above
Both ii and μ2 are averages that can be computed from the midpoints of two secants (respectively): (A1) = [(a + F(a c)). (a+ b, F(a + b])]. (A2) = F(a)), (a b+ F(a 6 c))]
Also, the midpoints of both secants have the same abscissa (and the ordinates are Yl and p2), so to study the sign of ((h.c) F(a), can study the position of both secants with respect to each other. F being convex, we show that the abscissae of one secant are included the abscissae of the other, this being sufficient give the position of both secants with respect each other. We distinguish four cases.
Case 1: <>> 0,b 0. We have a + +b+c> max(a + b, + ct and a < min(a + 6, a + c). F being convex, (A2) sits above (Ai). So, u2 i μı and finally dtb.e) F(a) > 0.
Case 2: < 0, < 0. We now have a + b + c < minfa + b, a + c} while > maxfa b, + c). so (Ag) sits above (A1). Again, #2 ir and finally F(a) >
Case 3: 0, < O. We have b < a and so this time (A2) sits below (A,) but ob < O, so ((b,c) F(a) > again.
+ b + Also + c> max(a + b c,a).
Case 4: c < 0, 0. S a a + b and a + < a b + Soa + c < minfa, a + b c) and b> max a c), so (Az) sits below (A1). Since cb < 0, so (p.c) F(a) 2 0 again.
B.4 Proof of Theorem
Let us remind key simplified notations about edges, Vt. 3/r 0:
ėts = Y4 He(a))); eu - y . a.hl(()) = Eei - ê((--1)i-
(23)
(24)
For short, we also let:
Q (T E(-
(25)
A 8 F(en) 6 F(ē(e-1ja);
(26)
where Q* is defined in SECBoOSTin two parts, the first computing real a, as:
We also split the computation of the leveraging coefficient a, in
1
at E 2(1 +& [1 Te, 1 + me].
(27)
17

---

and then using - a.hr, We now use Lemma 4.7 (main file) and get
[m-[m] [ (ēu ( (eulé(t
- EE .11 0.
(28)
If we reorganise 28
using the definition of SFi. (.l1.,, we get:
[m-[m] [(((++1)))]
[m][m]] [F(ts)) - [m] [(es - ((e+1)s) den F(((e+1)))) + [a-[m] [Qi+zx)]
=B [F(t:)] - |m (-E(e+1)) d (((+(()))))))) Bs-[ma [tttir)
(29)
-Ba-(m] [(()))] + 04+1 [Ba-(()) [m] [1ch dod ((((++)))]] + [m-[m]] (ic+ave
(30)
- -Be[(m] [F(es)) + d++17/+11 [m]] [vi he
(2:)) 80. F(e(i)
+a++17++1 [m] (1 A 1)+1)) + [m-[m]] Q
(31)
[m-[m]] [F({t)]] 4++17 [m]] w 1131 +a++176+1 [m-[m) (uch+t1 ((+
M++
+mm-[ml 07++
[m)] [F())))] 44417 a1417]+11 [.-[m] [1,h++1 1ut1)) + E,-(m)
[
(32)
(29 31
make use of definitions 24 (twice) and (26 as well the decomposition of the leveraging
coefficient in (27).
that we have boosting-compliant decrease of the loss if the two quantities depending on ((+1). and ((+1). can be made small enough compared to 02+1%/-4 This is what we investigate.
Looking at 32)..
Bounding the term depending on A(+1). We use Lemma B.2 with = = ē x' = ece+1)ss v + U..
which yields (also using (24) and the assumption that h++ (z:) * 0):
((++))= Sea, ((((++)))))) 8e,, F(êts)
S F(n + e((+1))) - d F(eu))
C(++)) (((eeTmAi))) F(ér)
Di (141)142(13) ((eatmeva)) F(en))
(33)
and so we get:
0++19++1 (Bappm) [Bihet ( (x.)) [[41))]]
-1-171+11 . [i-[m]]
( F(eu)
a BB, [m]]
(M++1 ((eatneee F((())
< a mz: M W 2,+1.
(34)
Bounding the term depending on (*(+1) We immediately get from the value picked in argument of [4 in step 2.5 of SECBoOST, the definition of Ls(.) in (10p and our decomposition a₁ - a.7 that Qut1ys & Er41 7 M W W2.41, Vi [m], so that:
B,-[m] ( & E111 2
2 M4n W W24+1-
(35)
18

---

Finishing up with the proof Suppose that we choose E1+1 > 0, Me+1 E (0, 1) and a++1 as in 22
We then get from 32.
34
35
that for any choice of Uy Step 2.5 of SECBOOST,
[x-[m] [((((+I))]
& [m]] [F((e))] - 0041 + ai+1 Mh 1 M2+1 W + Ei+1 2411 M2+1 W2.4 W2,+11
[m] [F(éx)]] a+11/++1 (1 a++1 (1 + E+t1) Ma+1 W2,41)
nft1 m(+1)
< Bm [F(E+)] 4 (1 + E(4) M/+1 22
(36)
where the last inequality consequence of Suppose we pick Hu = ho constant and Vo such that
Sep F(ho) * 0.
(37)
The final classifier Hr of SECBoOST satisfies:
T [m] [F(y:Hr(23))) Po Σ
1 mt)
(38)
(1 + Ex) M W 2.0
1=1
with Fo [i-[m] [F(E,)] [n [F(y: = [i-[m] [F(ysho)] If we want
[/.//m] (7(2,))( & F(z*), assuming wlog F(2*) Fo. then it suffices iterate until:
1 1-
n M2
4(Fo - F(z*)).
(39)
W 21 + E4)
Remind that the edge n not normalized. We have defined a normalized edge,
Well
he(x);)
[-1,1] 3 Th Σ
(40)
We
M
with UN = y: sign(w;s) and We = Σ, loccl = E, 18 seea- ny F relationship between ne and ip:
We have the simple
πe Σ Wasl
(x,))
(y) (ign(ww))
W,
M,
W,Me D westnho(x.))
m W,M
m.
(41)
resulting in (AL > 1),
vi2 M2
W
vit
[Eq-[m) [Dom un F 11))
> 1/
[Er-(m] 1omm F F(((=)))]))
0/2
W 1.:7
(42)
recalling W 1, EEnD se ())( comes from 42 that a sufficient condition for to hold is:
39
W (1 m²)
vht > 4(Fo F(x
(43)
W2 + Ex)
which is the statement of Theorem 5.3
19

---

B.5 Proof of Lemma 5.7
We first observe that for any a R, CE R..
1
18 fb.c) (bbcc)F(a))
(F(a+b) F(a) -(a) bF)
[bc]
-
) bF c)
1
+[([(a+b) F(a)) - aa)
|bc|
+ +bb(F((a F(a)))
1
B
B
6²
ba
b² + B|bc|
3
(44)
[cl
2
bbc
where we used the 3-smoothness of and twice 12 Lemma 3.4). We can also make permutation in the expression of ((b.c) (a) and instead write
Fla+b++ F(a
-F cF'laa+) - (F(a+ - cF
1
16 (b,c) F(a))
bcl
+c(F"(a F)(F)())))
[)(o+b+))=F(c++ F(a b) cF (a + b)l
1
+[(F(a+c] F(a) - ca))
bcl
+|c(F F'(a))
1
B
8
$
c2
c² + A|bel]
(45)
bcl
2
|cc
We thus have
2
min |c]
18
((b.c) < 3 3-
(46)
bcl
< 2,3
by the power mean inequality 11 Chapter III, Theorem 2). Since [1+(())) M, by definition, thus have
(ha(as))
2
[m-
8 Stenin net net (()(-1)))
23,
(47)
M₁
which allows us to fix W 2, = 2,3 and completes the proof of Lemma 5.7
Remark B.3. Our result is optimal in the sense that if we make one offset (say b) go to zero, then the ratio in 416) goes to zero and we recover the condition on the v-derivative of the derivative, F² 3.
B.6 Proof of Theorem 5.8
We consider the upperbound:
W2.
(xx(s))
E Ex-[m [m]]
S Sees (
MM
(xx())
1
F(eri + (((1-13)) F((x)
F(e + v1e-11))
F(E ((E
E/ [m]
M2
ēti
1((-1))i
U(t-1)i
1
(as))
F(êri 1(1-1))) F((n))
F(ē (((-1)))) F(e(e-1)))
E+a [i-[m)]
[m]]
ar
y.M
((t-1)e
U(t-1);
1
[4-[m]]
(8 (Ber F(eei) - S Sen- F(C(o-)i))
(48)
M2
20

---

(The last identity uses the fact that {)), Remark that we have extracted ae from the denominator but is still present in the arguments ézz. For any classifier h. introduce notation
n h)) = Bi- [w,gsh(z;)]
and so 7)t (Step 2.2 in SECBOOST) is also n,,,, h4), which is guaranteed to non-zero by the Weak Learning Assumption (5.4). We want, for some &t 0, Tee 1),
an 2(1 + MP 2,
[1 1 me).
(49)
This says that the sign of ar is the same as the sign of (ww,, h4) nh. Since know its sign, let us look for its absolute value:
m
lavl
Te. 1 me]
(50)
2(1 + M2 2,c
From (9) (main file), we can in fact search at in the union of such intervals for 6t > 0, n. E [0. 1), which amounts to find first:
lael (o,
1nd
M2W
and then find any & > O, Te e [0, 1) such that (50) holds. Using 48 dependency on Oe,, then need
and simplifying the external
[mll
e
0,
(51)
[iimm (Bcle((xs)) (dea-ny
((a ((t- d F(e(--1))))
B((a))
under the constraint that the sign of a be the same that of m) But, using notation we have
(main file),
B(ag) (n(w,, h2) - ((())(a)),h)))
and so to get (51 satisfied, it sufficient that
Me ()))) he] 1,
(52)
17
which Step in SOLVE,, The Weak Learning Assumption (5.4) guarantees that the denom- inator is * 0 so this can always be evaluated. The continuity of F in all ê(c-1); guarantees li 17( (o:)) ht) nt. and thus guarantees the existence solutions to (52) for some |a,| > 0.
To summarize, finding a, can be done in two steps, (i) solve
Me 17( Ü. (sign(T))) a),, hx))
m
for some 0 and (ii) let a, = sign(n.) This is the output of SOLVE, w., h4), which ends proof Theorem 5.8
B.7 Implementation the offset oracle: particular cases
Consider the "spring loss" that we define, for denoting the nearest integer, as:
(z) log(1 + exp( =)) + v - (( (=])
(53)
Figure 6 plots this loss, which composes the logistic loss with "U"-shaped term. This loss would escape all optimization algorithms Table [T (Appendix), yet there trivial implementation of our offset oracle, explained in Figure
21

---

1. if the interval I defined by ē(x-1) 1) and ên contains at least one peak, compute the tangence point (z²) at the closest local "U" that passes through F(ét-)) then if 2 E I then Uti 2 1(e- else Uta - E - 11-
2. otherwise F in Il is strictly convex and differentiable: a simple dichotomic search can retrieve feasible Uti (see convex losses below);
Notice that one can alleviate the repetitive dichotomic search by pre-tabulating a feasible v for a set of differences
(a, b belonging to the abscissae of the same "U") decreasing by fixed factor, choosing By - of the largest tabulated |a b) no larger than lê ē(t-1)al- Discontinuities discontinuities do not represent issues the argument of Tea(2) is large enough, as shown from the following simple Lemma.
Lemma B.4. Define the discontinuity of F as:
sup; [F()) lim, F(2),, sup; [F(2) lim F(z) }
disc(F) max
(54)
For any 2 32 0, if F) = then T=(=) * Ø AA 1, Vi [m]]
Figure (c) shows case where the discontinuity is larger than 2. In this case, an issue eventually happens for computing the next weight happens, only when the current edge at the discontinuity. We note that as iterations increase and the weak learner finds it eventually more difficult to return weak hypotheses with v, large enough, the discontinuities may become issue for SECBoOST to not stop at Step 2.5. Or one can always use a simple trick to avoid stopping and which relies on the leveraging coefficient Ozg: this is described in the Appendix, Section [B.9
The case of convex losses If F' is convex (not necessarily differentiable nor strictly convex), there is simple way find a valid output for the offset oracle, which relies on the following Lemma.
Lemma B.S, Suppose F convex. Then for any z' R, v * 0,
f0
r} F(z + 1)++0-FF0 F(z) 05(2,
v 0>0: Dr
=r]
(55)
v
By definition, [=,('') = [1())) for any 2' و 2, so simple way to implement the offset oracle's output oo(t, i, 2) is, for some r < 2, solve the Bregman identity in the RHS of (55) and then return any relevant v. If F is strictly convex, there is just one choice.
(proof in Appendix, Section B.8
If solving the Bregman identity is tedious but F is strictly convex, there a simple dichotomic search that is guaranteed to find feasible v. It exploits the fact that the abscissa maximizing the difference between any secant of F and has simple closed form (see [21] Supplement, Figure 13]) and so the OBI in (I) (Definition 4.6) has a closed form as well. In this case, it is enough, after taking first non-zero guess for v (either positive or negative), divide it by a constant > until the corresponding OBI is no larger than the in the query oo(t, i, 2).
B.8 Proof of Lemma B.5
F being convex, we first want to compute the set
I,,, = {u> 0: QF(2, +,22,,20,2220 v)= =r)
(56)
where is supposed small enough for ue.. to be non-empty. There is simple graphical solution to this which, Figure 7 exxllains, consists in finding v solution of
sup F) -((1) + F(2 (f(2+0) v) - -(()) (2 (=+
(57)
22

---

AF
(1
eti
{u: Q7 (ers 10e- v) S 5z}
Figure 6: The spring loss in (53) is neither convex, nor Lipschitz or differentiable and has an infinite number of local minima. Yet, an implementation of the offset oracle is trivial as an output for 0o can be obtained from the computation of single tangent point (here, the orange v, see text; best viewed in color).
(At)
F
U
r
2
Figure 7: Computing the OBI (2, 2 v, + v) for convex, (2, v) being given and e > 0. We
compute the line (At) crossing F at any point with slope equal to the secant [(z, F(2)), (2 + v, F(2 + v))] and then the difference between at + v and this line at & + v. We move so as maximize this difference. The optimal (in green) gives the corresponding OBI. In (56) and 58 we are interested in finding v given this difference, r. We also need to replicate this computation for
The LHS simplifies:
sup F(= + (F()) +
[F(z+ (F(())
(2 ((+v-11)
(2 (=+ - -zF(= +v)
+sup 1. F(z F(2+ vv) F(()) - F(()
(2 (2+2) - Fz + +u)
F(z + v) - FF(z)
F*
v. F(z + v) - F(2)
F(2 + v) -F(=)
F(2) + F.
F(z + - F(2) 23
DF

---

so we end up with an equivalent but more readable definition for u..
F(z + v) -F(+)
F(z)
un, = =
=r).
(58)
which yields the statement of the Lemma.
B.9 Handling discontinuities in the offset oracle to prevent stopping in Step 2.5
Theorem 5.3 and Lemma 5.6 require to run SECBoOST for as many iterations are required. This implies not early stopping Step 2.5. Lemma B.4 shows that early stopping can only he triggered by too large local discontinuities at the edges, This is a weak requirement on running SECBoOST, but there exists weak assumption on the discontinuities of the loss itself that simply prevent any early stopping and does not degrade the boosting rates. The result exploits the freedom in choosing a, in Step 2.3.
Lemma B.6. Suppose F' is any function defined over I discontinuities zero Lebesgue measure. for boosting F with its inequality strict while never triggering early stopping
Then Covollary in Step 2.5 of SEC
Proof. To show that we never trigger stopping Step 2.5, it is sufficient to show that we can run SEcBoosTwhie ensuring F is continuous in an open neighborhood around all edges y, (a;),, Vi [ma], Vt > 0 (by letting Ho ho). Remind that és f)e + ar ye (1;)), so changing ag changes all edges. We just have to show that either computing ensures such continuity, or a, can be slightly modified to do so. We have two ways to compute ay:
1. using value for Wa 2, that represents "absolute" upperbound in the sense of 8 (e.g. Lemma 5.7) and then compute a as in Step 2.3 of SECBoOST;
2. using algorithm SOLVE,
Because of the assumption on F, we can always ensure that F is continuous in an open neighborhood of all edges (the basis of the induction amounts straightforward choice for ho). This proves the Lemma for [2.].
If we rely on [1.] and the at computed leads to some discontinuities, then we have complete control to change at;: any continuous change of E, induces a continuous change in a and thus a continuous change of all edges as well. So, starting from the initial e, chosen in Step 2.3, we increase it to value et > Et. which we want to keep as small as possible, We can define for each E [m]] an open set (a,, by) which is the interval spanned by the new (,,(E( using ef (Et, =²). Since there are only finitely many discontinuities on F, there exists a small et > E, such that
Vi [m], E (a:, bi), F is continuous on 2.
This means that VE E (E.,ef), we end up with loss without any discontinuities on the new edges. Now comes the reason why we want = E, small: we can check that there always exist small enough of > E, such that for any E we choose, the boosting rate in Corollary [.6 affected by at most additional iteration. Indeed, while we slightly change parameter E, land all new edges outside of discontinuities of F, we also increase the contribution of the boosting iteration in the RHS of (15) by a quantity > which can be made as small required hence we can just replace the inequality in (T5) by a strict inequality. This proves the statement of the Lemma if we rely on [1.] above.
This completes the proof of Lemma B.6
B.10 A boosting pattern that can "survive" above differentiability
Suppose is strictly convex and strictly decreasing for classical convex surrogates (e.g. logistic
loss). Assuming wlog all a. > and example has both y=h)( > 0 and y > 0, as long as is small enough, we are guaranteed that any choice 0 [({=))=(=)) and lz)(() results in 0 < W(++1) < Wti which follows the classical boosting pattern that examples receiving the right class by weak hypotheses have their weight decreased (See Figure g If z' is large enough, then this does not hold anymore seen from Figure g
24

---

F
( (2 20 m) <z}
{is 17 6) 5.
parallel
A e(t (t-2))
eti
{v: Q1 v) 5z}
Figure 8: Case F strictly convex, with two cases of limit OBI and x' in I.(()). Example has en and f(t-1j 0 (??) large enough (hence, edges with respect weak classifiers h, and h4-1 large enough) so that (2) o ())-))(=)) = ()=)) o ((-2))(>>) [T((2) o (x))) = Ø. In this case, regardless of the offsets chosen by 00, we are guaranteed that its weights satisfy W(t+1) Wh w(t-1)x- which follows the boosting pattern that examples receiving the right
classification by weak classifiers have their weights decreasing. If however the limit OBI changes from z to larger z', this not guaranteed anymore: this case, may be the case that ((+41)s > Wr--
25

---

B.11
The case of piecewise constant losses for SOLVE
Initialization
Step 2.6, iteration t
Moet
(A)
yH,
(20
11.(20)
g
6
F
P(h))
Un
hg
(8)
v. F y H
y.H.
Figure 9: How our algorithm works with the 0/1 loss (in red): the initialization stage, assuming we pick ho 0 for simplicity and some bo < O, all training examples get the same weight, given by negative the slope of the thick blue dashed line. All weights are thus 0. At iteration when we update the weights (Step 2.6), one of two cases can happen on some training example (æ, y). In (A), the edge of the strong model remains the same: either both are positive (blue) or both negative (olive green) (the ordering of edges is not important). In this case, regardless of the offset, the new weight will be O. In (B), both edges have different sign (again, the ordering of edges is not important). In this case, the examples will keep non-zero weight over the next iteration. See text below for details.
of algorithm when training loss 0/1 loss. At the initialization, is easy to get all examples to have non-zero weight. The weight update for example (æ: y) of our algorithm in Step 2.3 is (negative) the slope of a secant that crosses the loss in two points, both being in between y HH, 1 (x) and yz) Hence, if the predicted label does not change (sign( (x)) = sign(H,
Figure 9 schematizes
H. 1 ()))), then the next weight (W+4-1) of the example will be zero (Figure 9. case (A)). However, if the predicted label does change (sign(H{(z)) * sign( Hz)1( then the example may get a non-zero weight depending on the offset chosen.
Hence, our generic implementation Algorithms and 4 may completely fail at providing non-zen weights for the next iteration, which makes the algorithm stop in step 2.7. And even when not all weights are zero, there may be just too small subset of those, that would break the Weak Learning Assumption for boosting compliance of the next iteration (Assumption 5.5).
C Supplementary material on algorithms, implementation tricks and toy experiment
C.1 Algorithm and implementation of SOLVE, and how to find parameters from Theorem
5.8
As Thcorem 5.8 explains, SOLVE, can easily get to not just the leveraging coefficient a; but also other parameters that are necessary to implement SECBOOST: Wa 2, and e, (both used in Step 2.5). We now provide simple pseudo code on how to implement SOLVE, amnd get, on top of it, the two other parameters. We do not seek n. since proposal implementation is optimized for complexity (because of the geometric updating of 6, W their respective loops) but much less so for for accuracy. Algorithm SOLYE extedded explains the overall procedure.
useful only the convergence analysis. Also, our
26

---

Algorithm 3 SOLVE_mtenool S, w. M)
Input sample S { Vi), 1, 1,2, ...,.
... m). w E Rm h: X R. M * 0.
our case, w - wy; h h,; M M, (current weights, weak hypothesis and max confidence, see Step 2.3 in SECBoOST and Assumption 5.1 Step 1:
// all initializations
Mhii 1,,,, h);;
(59)
- 1.0;
(60)
W init 1.0;
(61)
Step 2 do
I/ Step 2 computes the leveraging coefficient ar
a - ô sign()hmi); Mimi))
Nhow n (a))))))...))) h);
if Meew - Mhmi < Mad then found_ alpha + true else + 8/2:
while found alpha false;
Step 3 W Left Hand Side of (8) (main file)
// Step 3 computes W2. 2, we can use (main file) because we know a
if W machine 0 then
the LHS of (8) is (machine) O: just need to find W such that (
holds
W W
while la > M MWW 2 do W - W/2:
endif
Step 4: Dap < //aall/(1 (W M2;;
I/ Step 4 computes e
(Dupp/a) /a) 1;
Return (o, e)e);
F
12
êti
e e 1)i
t
Uti
Figure 10: How to find some u E [za(z): parse the interval [Rn, 1x-1xx] with a regular step d, seek the secant with minimal slope (because éxs é otherwise, we would seek the secant with maximal slope). It is necessarily the one minimizing the OBI among all regularly spaced choices, If the OBI is still too large, decrease the step and start the search again.
C.2 Algorithm and implementation of the offset oracle
There exists very simple trick to get some adequate offset to satisfy 11 (main file), explained in
Figure TO In short, we seek the optimally bended secant and check that the OBI is no more than
required This can be done via parsing the interval [érs é((-1))) using regularly spaced values. If the OBI too large, we can start again with a smaller step size. Algorithm 00 siple details the key part of the search.
27

---

Algorithm 4 O0_simpi(F, Et, 1,-1, 2)
Input loss F, two last edges Et, - maximal OBI 2, precision Z.
in our case, 6s + Eci ê - e(t- (for training example index i [m]] // all initializations
Step 1:
6 ét Et
(62)
Z
2c < é + 6;
(63)
i - 0;
(64)
Step 2 do
SLOPE( ze);
// returns the slope of the secant passing through (ē,, F(2)) and (2er F(2e))
if (i 0) v ((6 > 0) ^ (se 8x)) v ((6 < 0) (sc 54])) then 8* Soi Fi Ze
endif
Ze
2c + ō;
i + i + 1;
while (ze ēt) (Ze él-1) <
checks that ze is still in the interval // this is the offset
Return 2z
Clipped logistic loss, q = 2
Spring loss, Q = 500
Figure 11: Crops the two losses whose optimization has been experimentally tested with SEC- BooST, in addition the logistic loss. See text for details.
C.3 toy experiments
We provide here few toy experiments using SECBOOST. These are just meant display that simple implementation of the algorithm, following the blueprints given above, can indeed manage to optimize various losses. These are not meant to explain how to pick the best hyperparameters (e.g. (60p) nor how to choose the best loss given domain, a problem that is far beyond the scope of our paper.
In this implementation, the weak learner learns decision trees and minimize Matushita's loss at the leaves of decision trees to learn fixed size trees, see 33 for the criterion and induction scheme, which is standard for decision trees. SECBoOST is implemented as is given in the paper, and so are the implementation of SOLVE,, and the offset oracle provided above. We have made no optimization whatsoever, with one exception: when numerical approximation errors lead to an offset that is machine O, we replace it by small random value to prevent the use of derivatives in SECBOOST.
We have investigated three losses. The first is the well known logistic loss:
(2) = log(1 + exp(-z)).
(65)
The other two are tweaks of the logistic loss. We have investigated clipped version of the logistic loss,
F (2) min(log(1 + exp(-2)), log(1 exp(-q))}.
(66)
28

---

with 9 R, which clips the logistic loss above a certain value. This loss is non-convex and non- differentiable, but it Lipschitz. We have also investigated generalization of the spring loss (main file):
F Q() = log(1 + exp(-2)) 1 V 4 [zol))
(67)
Q
with 2Q = 1 ([-] is the closest integer), which adds to the logistic loss regularly spaced peaks of variable width. This loss is non-convex, non-differentiable, non-Lipschitz. Figure [1 provides a crop of the clipped logistic loss and spring loss have used in our test. Notice the "hardness" that the spring loss intuitively represents for ML.
We provide experiment on public domain UCI tictactoe 223 (using a 10-fold stratified cross- validation to estimate test errors). In addition the three losses, we have crossed them with several other variables: the size of the trees (either they have a single internal node stumps at most 20 nodes) and, to give one example how changing (key) hyperparameter can change the result, we have tested for a scale of changes
the initial value of 8 in (60) Finally, we have crossed all these variables with the existence of symmetric label noise in the training data, following the setup of [37 39). We flip each label in the training sample with probability 7). Table [2 summarizes the results obtained. One can see that SECBoOST manages to optimize all losses in pretty much all settings, with an eventual early stopping required for the spring loss if d is too large. Note that the best initial value for depends on the loss optimized in these experiments: for 0.1, test error from the spring loss decreases much faster than for the other losses, yet remind that the spring loss is just the logistic loss plus regularly spaced peaks. This could signal interesting avenues for the best possible implementation of SECBOOST, a further understanding of the best formal ways to fix those paramaters, all of which are out of the scope of this paper.
29

---

Stumps
Max size 20
Stumps
Max size 20
0300
038
3.00
0.16
0.16
2.10
3.05
0%
1:45
0.00
0.4
0.2
1:35
0.15
3.25
0.
0.35
055
3.16
0.19
2.05
5%
0.5
0.30
0.50
0.6
0.5
0.05
0.15
0.15
0.00
100
100
100
20%0
Figure 12: Experiments UCI tictactoe showing estimated test emrors after minimizing each of the three losses we consider, with varying training noise level 17. max tree size and initial hyperparameter 5 value in (60). See text.
30

---

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

---

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

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: Our paper is a theory paper. All algorithms we introduce are either in the main file or the appendix.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
Polmcylllyyyyyyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.cc/public /otic///udiee/ooeuuuuiiiiii sroodeSubiissiii wwiiiissssiiiyyyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Our paper is theory paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[NA]
Justification: Our paper is a theory paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
33

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the enror bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA].
Justification: Our paper is a theory paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The research of the paper follows the code of ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Our paper is a theory paper.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
34

---

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

---

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


Reviews:
[{"review_id": "yw652JqwJQ", "reviewer": "Reviewer_bfG5", "summary": "Boosting can be regarded as a general optimization problem, and most of the currently popular Boosting techniques tend to do so, and do it by using $1^\\text{st}$ order (gradient) information to minimise a loss function.\nThis work proposes an algorithm to minimise an arbitrary loss function using only $0^\\text{th}$ order information.\nThe authors prove that this method converges for essentially any loss function, which is unprecedented in the field.", "questions": "1. Up to the simplifying assumption of a finite weak hypothesis class, do you agree with the reformulation of the problem I provided above (see NOTE 2)? Naturally, conveying all nuances would require more space. Still, the goal was to provide a fair summary.\n2. Why do you believe \"optimisation\" is not a more appropriate primary area for this work than \"learning theory\"?\n3. What happens to Definition 4.1 when considering $v = 0$?\n4. Sorry if I simply missed this one, but what is your actual claim about Assumption 5.4? Is it that you expect it to always hold in practice, that there is an easy way to overcome it, or something else?", "limitations": "I am not sure this really applies to the work, but adding something like what I suggested in weakness 4.3 should make some relevant limitations of the work significantly clearer to many readers.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "1. The writing style is quite acceptable. I could understand the local meaning of pretty much every sentence.\n2. The result covers a **very** wide class of functions. I agree with the authors that putting it as \"essentially all functions\" is a fair claim.\n3. The use of quantum calculus is interesting and adds flavour to the work.\n4. The authors are upfront about disregarding generalisation aspects.", "weaknesses": "### **Note on the choice of primary area:** This is much more of an *optimisation* than a *learning theory* paper\nThe choice of primary area for this paper (learning theory) was poor.\nThis work is far better placed within the area of optimisation than in learning theory.\nThis is quite clear throughout the technical parts of the paper, and the authors even write \"We do not investigate the questions of generalisation, which would entail specific design choices about the loss at hand\" (within the paragraph after line 74), so I expect the authors to agree with this assessment.\nGiven that, I honestly fail to see how the authors judged their choice of primary area to be the one that would lead their work toward the most appropriate reviewers.\n\nThis issue could have been significantly mitigated by an especially strong presentation of the work.\nInstead, I found the presentation to be, at the very best, fair (I elaborate on this below).\n\nOverall, this work turned out to be laborious to review.\nIt is not that the technical side is particularly complex, but there are many moving parts and nested concepts, making it laborious to keep track of everything without a clear roadmap.\nEspecially when coming from a learning theory background (which, again, seems to be the authors' target audience), overcoming the weak presentation requires an amount of effort that I am not sure is reasonable for the authors to demand from the reader.\n\nUltimately, this matter ended up lowering my confidence score since, for example, it is definitely \"possible I am unfamiliar with some pieces of related work\".\nStill, within the resources I had at my disposal, I did my best to make my review useful to the authors and the community as a whole.\n\n\n### A technical (reformulated) summary of the work's contribution\n\nTo help clarify my understanding of the work, I will start with an abstract of the paper in more technical terms than what I offered in the \"summary\" field above.\nThe goal is to make it easier for the authors to point out and correct potential misunderstandings.\n(It is based on the definitions from Section 3 starting at line 74)\n\nAs mentioned in the note above, the authors completely disregard generalisation.\nThus, only the training set $S = \\{(\\mathbf{x}_1, y_1), \\ldots, (\\mathbf{x}_m, y_m)\\}$ is relevant to the work.\nIn particular, given a hypothesis $h\\colon \\mathcal{X} \\to \\mathbb{R}$ (not the binary $\\{-1, 1\\}$-range as in the classical setting), we may simply consider\n$$f_i \\coloneqq h(\\mathbf{x}_i),$$\ndefining a vector $\\mathbf{f} = (f_1, \\ldots, f_m) \\in \\mathbb{R}^m$,\nsince, again, **the work is oblivious to any evaluation of hypotheses outside of the $m$ points in the training set**.\n\nLet $\\mathcal{G}$ be the hypothesis class of the weak learner, i.e., the set of all hypotheses that the weak learner can output.\n> NOTE 1: Not to be confused with the set $\\mathcal{H}$ defined by the authors to be that of all classifiers attainable via linear combinations of hypotheses in $\\mathcal{G}$.\nI am highlighting this as it is a bit unusual in the context of classical boosting, where one typically argues in terms of the class of weak hypotheses $\\mathcal{G}$ rather than the class of ensemble classifiers $\\mathcal{H}$.\n\nFor simplicity, let us assume that $\\mathcal{G}$ is finite:\nLet $n = \\lvert \\mathcal{G} \\rvert$ and, employing the notation above, consider the enumeration $\\mathcal{G} = \\{\\mathbf{f}^{(1)}, \\ldots, \\mathbf{f}^{(n)}\\}$.\n\nFinally, consider a generic loss function $F\\colon \\mathbb{R} \\to \\mathbb{R}$.\n\nThe problem attacked by the paper then becomes\n\n**Target Problem (reformulated):**\nGiven **fixed vectors** $\\mathbf{f}^{(1)}, \\ldots, \\mathbf{f}^{(n)} \\in \\mathbb{R}^m$\nand associated labels $y_1, \\ldots, y_m \\in \\{-1, 1\\}$,\nand a loss function $F\\colon \\mathbb{R} \\to \\mathbb{R}$,\nfind coefficients $\\alpha_1, \\ldots, \\alpha_n \\in \\mathbb{R}$ to minimise\n$$\\sum_{i=1}^m F\\left(y_i \\sum_{j=1}^n \\alpha_j f^{(j)}_i\\right).$$\n\n> NOTE 2: In my first question below, I've explicitly asked the authors to confirm that this formulation is an accurate summary of the problem.\n\nNaturally, the difficulty of the problem depends on the properties of $F$.\nThe central claim of the paper is to provide an algorithm to effectively find such a set of coefficients while requiring very little from $F$:\nThat its points of discontinuity form a set of measure zero.\nMoreover, the authors provide guarantees on the sparsity of the solution as at most $T$ coefficients are non-zero, where $T$ is the number of boosting steps performed by the algorithm.\n\n> Notice that I omitted the $\\gamma$-weak learner from the reformulation above because I had some issues with the authors' definition.\nI dedicated a subsection to this matter below.\n\n### Weaknesses\n\n> My goal is to be objective and direct, but I acknowledge this can give the text a bitter-like tone. I apologise if I sound too harsh in the review.\n\n\nThe most pervasive weakness of the work is that, while the writing style itself is acceptable, the overall presentation is poor when considering more global aspects.\nAll the following points stem from this issue to some extent.\n\n1. The authors are not sufficiently clear and explicit in enumerating the claimed contributions.\n    The closest to that would be the paragraph starting at line 38, however, one cannot conclude that the claimed contribution is restricted to the contents of that paragraph.\n\nAfter reading the paper, I suspect that the claimed contribution boils down to (put roughly)\n> We provide the first study on the convergence of $0^\\text{th}$ order optimisation methods for boosting under a general loss function.\nMoreover, we ensure convergence for the widest class of loss functions seen so far in the field of $0^\\text{th}$ order optimisation in the ML setting.\nNamely, we cover all functions whose points of discontinuity form a set of measure zero.\n\nIn particular, my understanding is that\n- The authors do not claim any new techniques used to obtain their results.\n    In fact, very little emphasis is given to the proofs, with all of them being left to the appendices and no sketches being provided.\n- As the text does not provide explicit insights into the difficulty of the problem they are solving, the authors do not claim the problem is particularly challenging under the light of the usual frameworks used for this kind of problem.\n\nThis is a fair setting for a paper and I would lean towards acceptance provided the authors do a good job in\nestablishing the relevance of filling the gap in the literature that they claim to have filled.\nTo make this point clearer, an informal and exaggerated version of it would be \"Totally convincing the reader that others weren't aware of the gap and ignored it out of disinterest\" (I am not suggesting this was the case).\nAlternatively, but preferably both, the authors could solidly establish the significance of the uniquely wide class of loss functions they cover.\nI believe that the authors failed to do either, and this is the main reason why I recommend rejection.\n\nWhile the following points are not minor, the authors can regard them as less critical than what I have discussed above.\n\n2. Theorem 5.3 fails to provide a reasonably self-contained statement that leads to something close to what is claimed in the paragraph starting at line 38.\n    Instead, the authors' phrasing of the statement resembles more that of a lemma, in that it requires multiple logical steps and the reference to other results to properly grasp its significance.\n    I can see a good formal rephrasing of the statement can be hard to achieve, so the authors could consider adding a less formal version of result to the introduction.\n    That would also help greatly with the former point.\n\n3. The authors do not provide an exact statement for the optimisation problem at hand (something in the direction of the *Target problem* above).\n    It is important to know early and with absolute certainty what the authors are attacking.\n\n4. **From the perspective of learning theory**, some of the motivation provided for $0^\\text{th}$ order methods seems misplaced:\n    1. On the theoretical side, $0^\\text{th}$ order optimal weak to strong learners are known to exist: see [1].\n    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.\n        See, for example, the discussion in [2, Section 7.3: \"Loss Minimization Cannot Explain Generalization\"].\n    3. I recognise that the authors explicitly dismiss matters of generalisation, but I still believe the remarks above are relevant in assessing the motivation for the work.\n    The authors may consider bringing up these points in some form, perhaps by mentioning how the related works compare to their results in this regard.\n\n5. I am confused by the authors' concept of what constitutes \"traditional\" boosting.\n    To me, AdaBoost is the most prototypical and traditional boosting algorithm.\n    However, for example, in line 131 it is clear that the authors believe that \"traditional\" boosting requires first-order information, which is not the case for AdaBoost.\n\n6. The discussion around Assumption 5.4 is too loose to fully justify an assumption that seems to be quite relevant (see the role of $\\rho_*$ in Corollary 5.6).\n    I understand the point made just above the assumption, but I believe that would only suffice to fully justify some special treatment of arbitrary small $\\rho_t\\text{s}$.\n    I expected a formal or at least deeper discussion of the significance of the assumption.\n\n\n### References\n\n[1]: Larsen, K. G. (2023, July). Bagging is an optimal PAC learner. In The Thirty Sixth Annual Conference on Learning Theory (pp. 450-468). PMLR.\\\n[2]: Schapire, R.E. and Freund, Y., 2013. Boosting: Foundations and algorithms. Kybernetes, 42(1), pp.164-166.\n\n\n### Minor issues and suggestions\n\n#### Issues with the definition of $\\gamma$-weak learner\n\n1. The authors, unfortunately, do not define it in Section 3, \"Definitions and notations\", delaying it to page 7 (Assumption 5.5 at line 175).\n2. The definition is not self-contained, as it depends on $\\tilde{\\eta}_t$ which itself depends on other parameters (see Eq. 18).\n3. Honestly, I do not recognise that definition as \"the traditional\" one (see line 174).\n    To me, that would be a $\\gamma$-weak learner that, for any distribution over the training set, outputs a (binary) hypothesis whose average error is at most $1/2 - \\gamma$.\n    Of course, the paper discusses non-binary hypotheses so that a definition in terms of edges is natural.\n    Still, I do not think the equivalence/analogy is immediate enough, and, regardless, the authors should provide a self-contained and formal definition of $\\gamma$-weak learner, ideally in Section 3.\n    Step 2.1 of Algorithm 1 does not make it totally clear what are the inputs and outputs of the $\\gamma$-weak learner.\n4. Assumption 5.5 might be less \"global\" than one could expect.\n    It depends on the definition of $\\tilde{\\eta}\\_t$, which depends on $M\\_t \\coloneqq \\max\\_i \\lvert h\\_t(\\mathbf{x}\\_i) \\rvert$, making Assumption 5.5 have a different strength at each round if one parses Eq. 18 as\n    $$\\tilde{\\eta}\\_t = \\frac{1}{M\\_t} \\sum_{i=1}^m \\frac{\\lvert w\\_{ti} \\rvert}{\\sum\\_i \\lvert w\\_{ti} \\rvert} \\cdot \\tilde{y}\\_{ti} h\\_t(\\mathbf{x}\\_i) = \\frac{1}{M\\_t} \\cdot \\text{``edge of $h_t$ relative to a normalised version of the weights $\\mathbf{w}\\_t$\"}.$$\n\n> NOTE 3: Despite the difficulties, I believe to have eventually understood what the authors meant by $\\gamma$-weak learner. At Step 2.1,\n- the notation $\\lvert \\mathbf{w}\\_t \\rvert$ refers to the vector $(\\lvert w\\_{t1} \\rvert, \\ldots, \\lvert w\\_{tm} \\rvert)$ (I do not recall whether this was defined);\n- the notation $⨉$ denotes the weak learner (why not something clear like $\\mathrm{WeakLeaner}$?);\n- the definition of $\\mathbf{S}\\_t$ in the comment (why there?) sets the pseudo-labels;\n- the weak learner $⨉$ operates on the training points $\\mathbf{x}\\_i$ with the pseudo-labels $\\tilde{y}\\_{ti}$ and weights $w\\_{ti}/\\lVert \\mathbf{w}\\_t \\rVert\\_1$;\n- $⨉$ provides a hypothesis $h_t$ with an edge of at least $\\gamma$, where the concept of edge needs a normalisation to contemplate hypotheses with unbounded range; (The authors chose a normalisation factor that is a function of $h_t$ while in points 3 and 4 above I remark that a global factor could be more natural).\n\n> My point is not that it is impossible to retrieve what the authors had in mind, but that they made it significantly harder to do so than what is necessary.\nAlso, one needs explicit formal definitions to fully appreciate contributions.\n\n\n#### General minor issues and suggestions\n\n- In the technical summary above, one could cover infinite $\\mathcal{G}$ by considering a suitable measure and employing a (Lebesgue) integral in the objective function.\n    I haven't thought much about this, but it's too much of a coincidence that the weak regularity assumption on $F$ that the authors found resembles the conditions for integrability so closely.\n\n- The other theorem statements also suffer from the \"lemma-like\" issue I mentioned above\n\n- Section 4 is somewhat representative of the general issue with the presentation.\n    Ideally, a section like this should go along the lines of\n    - What is the goal;\n    - What are the original concepts;\n    - Why they do not suit the current setting;\n    - How you modified them;\n    - How the change fixes the issue.\n\n    Instead, the definitions introduced are left insufficiently motivated and, indeed, it is not even fully clear how novel the concepts introduced are.\n\n- I suspect you require less from the hypotheses returned by the weak learner than it may appear at line 113 and the subsequent Assumption 5.1.\n    As the next note highlights, you don't really need it to be non-zero.\n    Finally, since the training set is finite, to have that $\\forall i \\in [m],\\, \\lvert h(\\mathbf{x}_i) \\rvert < \\infty$ we only need $h$ to be a real-valued function defined in $\\{\\mathbf{x}_1, \\ldots, \\mathbf{x}_m, \\ldots\\}\\subseteq \\mathcal{X}$.\n    Long story short, I think you only need to consider a weak learner returning functions $h\\colon \\mathcal{X} \\to \\mathbb{R}$, which is a very mild assumption.\n    (The central point here is that real-valued functions are always bounded on finite sets. Unless one is working with the extended reals, something like $f(x) = 1/\\lvert x \\rvert$ is not defined at 0.)\n\n- Consider stating more explicitly that the assumption of non-zero predictions (line 113) sacrifices no generality (I was only sure this was the case after checking Section II.2 from the Appendix)\n\n- [Eq. (4)] Consider using $(F(a)F(b))_\\alpha$\n\n- Number only the equations that are referenced in the text\n\n- Consider a version of Figure 1 with an extra dimension (a surface plot) as, after all, the Bregman Secant distortion behaves as taking 2 arguments\n\n- Avoid starting sentences with mathematical symbols (e.g., line 93)\n\n- [122] the reference to [47, Appendix, Section 4] has a bit too much packed in it. The authors should consider adding some further guidance or explanation. That should be feasible since the reference tags almost all equations in that section.\n\n- Adding hyperlinks to the steps of the algorithm (e.g., Step 2.1) would make it meaningfully more convenient to navigate the text.\n\n- Algorithm 1 can be made significantly tidier. Doing so would be a considerable improvement in the presentation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nWe 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.\n\nOur 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].\n\nThis rebuttal part contains two sub-parts: a reply to the positioning of our paper and a reply to the questions asked in the review.\n\n## On the the positioning of our paper.\n\n> 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.\n\n[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 :).\n\n## Questions\n\n> Up to the simplifying assumption of a finite weak hypothesis class, do you agree with the reformulation [...]\n\nDe 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]\n\n> Why do you believe \"optimisation\" is not a more appropriate primary area for this work than \"learning theory\"?\n\nWe explain it in [ROLT] and [RTB]. In one word: history.\n\n> What happens to Definition 4.1 [...]\n\nThe 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)\n\n> Sorry if I simply missed this one, but what is your actual claim about Assumption 5.4? \n\n[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].\n\nWe 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 [...]\".", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xy5peq5ngW", "reviewer": "Reviewer_8gCx", "summary": "-\tThis paper discusses an alternative boost algorithm by using the zeroth-order optimization technique. The key benefit by using such technique is that it does not require the loss function to be convex, differentiable or Lipschitz. They provide theoretical results and validate them with experiments.", "questions": "-\tWhat are examples of the strict benefits of the boosting for any loss function beyond those requiring gradient information? That is, the true computational / generalizability benefit of SECBOOST over existing first-order boosting methods with function approximations.  I am not super familiar with all first-order boosting methods, however, I guess for those non-smooth loss objectives, we can smooth the original non-smooth loss objectives and do boosting for these surrogate loss. Please correct me if this is not case or quite nontrivial for some general losses.", "limitations": "The authors mention some limitations related to their Assumption 5.4 and 5.5. However, I still feel like more discussions related to the scope of these assumptions in terms of the loss function (like the weakness and question I pointed out) to increase the accessibility of the paper and help readers understand better.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "-\tThe contributions from this paper in terms of the generalizability are clear and interesting.\n-\tIf the authors’ claims are proper and assumptions are not hard to satisfy, their contributions are definitely very important in extending the loss function class to be as general as we know in the loss properties.", "weaknesses": "-\tI do not understand some assumptions well, which makes me a bit confused on the strength of the algorithms and subsequent theoretical contributions. And I think more descriptions related to the condition should be provided:\n\nFirst, Assumption 5.4, is this easy to verify for some given learners? Since it is quite convoluted and from my perspective, it seems more like an intermediate result which requires some efforts to analyze; Furthermore, will some structure properties of the loss function depend on $\\rho$. If the loss is super bad, would not the associated Assumption 5.4 fail? How restricted is such Assumption 5.4?\n\nThen, Assumption 5.5, this is not the standard weak learning assumption in literature, since the standard weak learning condition is the unweighted version with taking expectation for the predictor and labels. And I am not sure why the condition is imposed for all $t$ and requires conditions for the subsequent $h_t$ beyond the initial weak learner. I am not sure whether it is the traditional weak learning assumption in boosting literature. If so, more reference and / or  related discussions should be provided. \n\n-\tThere are some inconsistent notations and definitions that appear here and there in the paper, which causes readers confusion, e.g., 1-order and first-order, zero-order and zeroth-order. And in Page 2, both $F(S, h)$ and $F(\\cdot)$ appear as well as its use subscript or superscript alternatively for different losses, which can be improved. Therefore, it is very confusing in Theorem 5.3 and Corollary 5.6 when both of them appear at the same time. Besides, there are some typos and grammar mistakes around the paper and the paper needs some rewritten to improve the writing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> First, Assumption 5.4, is this easy to verify for some given learners? [...]\n\n[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.\n\nWhy 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.\n\nIs 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.\n\n> Then, Assumption 5.5, this is not the standard weak learning assumption [...]\n\n[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).\n\n> 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 [...]\n\n[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.\n\nWe would be happy to add some additional content to make [RA5.5E] [RA5.5F] clear.\n\n> There are some inconsistent notations and definitions\n\nWe 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.\n\n> What are examples of the strict benefits of the boosting for any loss function beyond those requiring gradient information? [...]\n\n[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.\n\nAnother 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.\n\nA 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.\n\nWe hope the limitations section in the review is now adequately addressed.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nZGC1zOfD8", "reviewer": "Reviewer_XK3t", "summary": "The paper investigates the theoretical aspect of boosting algorithms in machine learning. The authors propose a new algorithm, SECBOOST, which aims to optimize any loss function using zeroth-order information. This approach dis different from traditional boosting methods that require first-order information such as gradients. By leveraging tools from quantum calculus, the paper claims to extend the applicability of boosting to loss functions that are not necessarily convex, differentiable, or even continuous. The core contribution is the demonstration that boosting can be effectively performed without relying on derivative information.\n\n--\n\nI have read the rebuttal and other reviews. Rating unchanged.", "questions": "Please see the strength/weakness section.", "limitations": "n/a", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I like this paper which is somewhat different from the majority of boosting related work. Though the outbreak of deep learning methods generally comes with derivative info, a vast variety of problems don't. This paper provides theoretical contributions of designing boosting algorithm for any loss function whose set of discontinuities has zero Lebesgue measure which is a pretty general setting. It feels like a piece missing for boosting algorithm literatures and it's nice to have that eventually.", "weaknesses": "I would connect more to real-world applications. This doesn't necessarily mean to run experiments, but at least providing examples about such kind of loss functions and their importance in real world would be helpful. \n\nIn addition, sometimes the loss function is differentiable yet getting the derivative could be expensive. Some discussion around performance vs. cost will be very helpful. This part is optional but would make the paper much stronger. \n\nSome of the material in appendix III are actually insightful and helpful. Suggest to move some to the main body.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the whole content of the strength section, which summarizes the key strengths of our approach.\n\n> I would connect more to real-world applications.\n\nEven 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.\n\n> In addition, sometimes the loss function is differentiable yet getting the derivative could be expensive. \n\nThe reviewer is right. We suggest to put [RGRI] (answers to reviewer 8gCx) in the camera ready using the additional page.\n\n> Some of the material in appendix III are actually insightful and helpful\n\nWe 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VI7doUeLCn", "reviewer": "Reviewer_TGRx", "summary": "The paper presents a framework for boosting any (bounded) loss function given access to a weak learner. The authors present how recent developments in boosting have involved turning the boosting problem into an optimization problem, where different combinations of assumptions on the loss such as convexity, lipschitcness, differential, etc. are assumed to be true to obtain bounds on the error. The authors then point to the origin of the boosting idea which was that one had access to a weak learner who given a weighted sample produced a hypothesis that was slightly better than guessing on the weighted sample and by using the access to query this weak learner produce a final classifier which performed arbitrarily well compared to just slightly better than guessing. I.e. there were no assumptions on the loss function itself. Thus the authors want to consider this more general setting where no extra information on the loss $F$ (other than a bound on the loss in the hypothesis returned by the weak learner on the sample is bounded). To construct boosting for such general $F$ they look to a zero'th order optimization (only access to losses) and find that they can't find any previous work on boosting using zero'th order optimization. The authors then present a new boosting algorithm SECBOOST that uses zero'th order optimization to boost any loss function. With the before mentioned boundedness assumption on $F$ they are able to show a in-sample error guarantee, which if SECBOOST is successful and run sufficiently long can be made arbitrarily close to the minimum of the loss function $\\inf_{x\\in R}F(x)$. Noted by the authors this guarantee holds when the number of iterations is large enough - they also comment on which problem can arrise in terms of SECBOOST stopping to early  - and how they can be alleviated.", "questions": "What does $R_{\\star}$ and $N_{\\star}$ denote?\n\n Line 142 can you explain why the sign of any $v$ in $I_{ti}(z)$ is always the sign of $-y_{i}\\alpha_{t}h_{t}(x_i)$? \n\n Figure 2, is the dotted lines $w_{t,1},\\ldots,w_{t,m}$\n \n Corollary 5.4, i guess could also be stated with just the weak learning assumption? so with 5.1 and 5.4?\n \n Why does figure 3 and 4 come before figure 2? And why are the figures not on the pages where they are used to discripe the setup?\n \n Line 176 $\\nu_{t}$ depend on $h_{t }$ thorough $M_t$ is this a problem, when we assume that the weak learner find the hypothesis $h_t$ such that $|\\nu_{t}|\\geq \\gamma$. Why isn't it the case that the weak learner output the hypothesis $h_t$ such that $\\nu_{t}\\geq \\gamma$(no absolute value)? \n \n What if the weak learning gaurantee was given in terms of the the loss funciton  $F$?\n \n Can you come up with a setting of $F$ where the algorithm gives a bound on the number of iterations need and compare it to the best known bound for that setting?", "limitations": "Yes.", "rating": 6, "confidence": 1, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Originality:\n\nThe authors couldn't find previous work on zero'th order optimzation and boosting so it is original in that sense. The authors also points out how SECBOOST may differ from traditional boosting algorithms by for instance, possibly chaning signs, and using emperical quantaties relating v-first and second order derivatives.  \n\nQuality:\n\n The main doesn't contain any proof so I will not comment on the theoretical analysis soundness and is also my reason for my confidence score. The authors seems to be honest about the limitations of SECBOOST and clearly state the assumptions made in the paper.\n\nClarity: \nThe main is very well written and the authors give an intuitive description of SECBOOST and the different concepts that it used - here also using figures to illustrate the concepts. \n\nSignificance: \n As the problem of combinding boosting and zero'th order optimization is presented as new it seems like a interesting problem to look at. The framework is presented very generally which makes it applicable in many places. Also, this new perspective on using zero'th order optimization in boosting may also inspire new ideas for boosting algorithms in problem-specific settings.", "weaknesses": "As also asked in the questions, to highlight the applicability of the framework it could be nice with and example of a loss $F$ where one could compare SECBOOST to the best-known algorithms for that specific loss in the boosting setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> What does $R_*$ and $N_*$ denote ?\n\nThese are the sets of reals / naturals without 0.\n\n> can you explain why the sign of any [...]\n\nbecause 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)\n\n> Figure 2, is the dotted lines [...]\n\nThe *slopes* of the dotted lines (secants) provide the weights (the information needed for optimisation).\n\n> Corollary 5.4, i guess could also be stated with just the weak learning assumption?\n\nWe 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].\n\n> Why does figure 3 and 4 come before figure 2? \n\nAs 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.\n\n> Line 176 $\\nu_t$ depend on $h_t$ through $M_t$ is this a problem.\n\nWe 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).\n\n> Why isn't it the case that the weak learner output the hypothesis $h_t$ such that $\\nu_t \\geq \\gamma$ (no absolute value)\n\n(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 !\n\n> What if the weak learning gaurantee was given in terms of the the loss funciton $F$ ?\n\nThe weak learning assumption would then be \"just about one loss\" and thus very restricted. The adopted formulation is much more general.\n\n> Can you come up with a setting [...] compare it to the best known bound for that setting?\n\nWe assume that the reviewers want to know how close we can come to an optimal, *loss-dependent* bound ? \n\nCan 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]. \n\nAre 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: After a long discussion, all reviewers suggested acceptance, although overall they found the paper hard to understand and their confidence was very low. Personally, I like to see this new approach to boosting, an area that has seen so much work in past decades. Based on all this, I suggest acceptance. I advice the authors to take the reviewers' comments into consideration in order to make the paper more clear.
Decision: Accept (poster)