# How to Boost Any Loss Function

Richard Nock Yishay Mansour
Google Research
<EMAIL_ADDRESS>

###### 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 can 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.

##  1 Introduction

In ML, zeroth order optimization has been devised as an alternative to
techniques that would otherwise require access to $\geq 1$-order information
about the loss to minimize, such as gradient descent (stochastic or not,
constrained or not, etc., see Section 2). Such approaches replace the access
to a so-called oracle providing derivatives for the loss at hand, operations
that can be consuming or not available in exact form in the ML world, by the
access to a cheaper function value oracle, providing loss values at queried
points.

Zeroth order optimization has seen a considerable boost in ML over the past
years, over many settings and algorithms, yet, there is one foundational ML
setting and related algorithms that, to our knowledge, have not yet been the
subject of investigations: boosting [33, 32]. Such a question is very
relevant: boosting has quickly evolved as a technique requiring first-order
information about the loss optimized [6, Section 10.3], [42, Section 7.2.2]
[56]. It is also not uncommon to find boosting reduced to this first-order
setting [10]. 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 at least slightly different from
random guessing [32]. In 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 a weak learner and in fine where boosting
stands with respect to recent formal progress on lifting gradient descent to
zeroth-order optimisation.

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, and in fact not even continuous. 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), Lipschitzness,
etc. . Our trick to avoid the use of derivatives in boosting relies on using
or extending tools from quantum calculus***Calculus ”without limits” [31]
(thus without using derivatives), not to be confounded with calculus on
quantum devices., some of which appear to be standard in the analysis of
zeroth-order optimization. To preserve readability, all proofs and additional
information are postponed to an Appendix.

##  2 Related work

|  $F$ |  $\nabla F$ | main
---|---|---|---
reference  | conv. | diff. | Lip. | smooth | Lb  | diff.  | ML topic
[1] | ✓ |  | ✓ |  |  |  | online ML
[2] | ✓ | ✓ | ✓ | ✓ |  |  | online ML
[3] | ✓ |  | ✓ |  |  |  | distributed ML
[15] | ✓ | ✓ |  | ✓ |  |  ✓ | alt. GD
[16] |  | ✓ |  | ✓ |  |  ✓ | alt. GD
[18] |  |  | ✓ |  |  ✓ |  | alt. GD
[19] |  | ✓ | ✓ |  |  |  | alt. GD
[20] | ✓ | ✓ | ✓ | ✓ |  |  | alt. GD
[21] | ✓ | ✓ |  | ✓ |  |  | alt. GD
[23] | ✓ | ✓ |  |  |  |  | alt. GD
[26] |  | ✓ | ✓ | ✓ |  |  | saddle pt opt
[27] |  | ✓ |  | ✓ |  |  | alt. FW
[28] |  |  | ✓ |  |  |  | online ML
[29] |  | ✓ |  | ✓ |  |  | alt. FW
[30] |  | ✓ |  | ✓ |  |  | deep ML
[36] | ✓ | ✓ |  | ✓ |  |  | alt. GD
[37] |  |  | ✓ |  |  |  | saddle pt opt
[39] | ✓ | ✓ | ✓ | ✓ |  |  | saddle pt opt
[41] |  | ✓ |  | ✓ |  |  ✓ | distributed ML
[49] |  | ✓ | ✓ | ✓ |  |  | federated ML
[50] |  | ✓ |  | ✓ |  |  | alt. GD
[53] |  | ✓ | ✓ | ✓ |  |  ✓ | saddle pt opt
[54] |  | ✓ |  | ✓ |  |  | alt. FW
[55] |  | ✓ | ✓ | ✓ |  |  | alt. GD
[58] |  | ✓ | ✓ | ✓ |  |  ✓ | saddle pt opt
[59] |  | ✓ | ✓ | ✓ |  |  ✓ | saddle pt opt
|  |  |  |  |  |  |
Table 1: Summary of formal assumptions about loss $F$ used to prove
algorithms’ convergence in recent papers on zeroth order optimization, in
different ML settings (see text for details). We use "smoothness" as a
portmanteau for various conditions on the $\geq 1$ order differentiability
condition of $F$. "conv." = convex, "diff." = differentiable, "Lip." =
Lipschitz, "Lb" = 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.

Over the past years, ML has seen a substantial push to get the cheapest
optimisation routines, in general batch [15], online [28], distributed [3],
adversarial [21, 19] or bandits settings [2] or more specific settings like
projection-free [27, 29, 54] or saddle-point optimisation [26, 39]. We
summarize several dozen recent references in Table 1 in terms of assumptions
for the analysis about the loss optimized. 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 1 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 a natural candidate for such
investigations, for two reasons. First, the most widely used boosting
algorithms are first-order information hungry [6, 42, 56]: 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 a first-order information oracle to learn, but rather to a weak
learning oracle which supplies classifiers performing slightly differently
from random guessing [33, 32]. Only few approaches exist to get to "cheaper”
algorithms relying on less assumptions about the loss at hand, and to our
knowledge do not have boosting-compliant convergence proofs, as for example
when alleviating convexity [17, 48] or access to gradients of the loss [57].
Such questions are however important given the early negative results on
boosting convex potentials with first-order information [38] and the role of
the classifiers in the negative results [40].

Finally, we note that a rich literature has developed in mathematics as well
for derivative-free optimisation [35], yet methods would also often rely on
assumptions included in the three above (e.g. [43]). It must be noted however
that derivative-free optimisation has been implemented in computers for more
than seven decades [25].

##  3 Definitions and notations

The following shorthands are used:
$[n]\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\\{1,2,...,n\\}$ for
$n\in\mathbb{N}_{*}$,
$z\cdot[a,b]\stackrel{{\scriptstyle\mathrm{.}}}{{=}}[\min\\{za,zb\\},\max\\{za,zb\\}]$
for $z\in\mathbb{R},a\leq b\in\mathbb{R}$. In the batch supervised learning
setting, one is given a training set of $m$ examples
$S\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\\{({\bm{x}}_{i},y_{i}),i\in[m]\\}$,
where ${\bm{x}}_{i}\in{\mathcal{X}}$ is an observation (${\mathcal{X}}$ is
called the domain: often, ${\mathcal{X}}\subseteq{\mathbb{R}}^{d}$) and
$y_{i}\in\mathcal{Y}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\\{-1,1\\}$ is a
label, or class. We study the empirical convergence of boosting, which
requires fast convergence on training. We do not investigate the questions of
generalization, which would entail specific design choices about the loss at
hand (see e.g. [9]). The objective is to learn a classifier, i.e. a function
$h:\mathcal{X}\rightarrow\mathbb{R}$ which belongs to a given set
$\mathcal{H}$. The goodness of fit of some $h$ on $S$ is evaluated from a
given function $F:\mathbb{R}\rightarrow\mathbb{R}$ called a loss function,
whose expectation on training is sought to be minimized:

$\displaystyle F(S,h)$ $\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$
$\displaystyle\mathsf{E}_{i\sim[m]}[F(y_{i}h(\bm{x}_{i}))].$ (1)

The set of most popular losses comprises convex functions: the exponential
loss
(${F_{\mbox{\tiny{{exp}}}}}(z)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\exp(-z)$),
the logistic loss
(${F^{\mbox{\tiny{{log}}}}}(z)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\log(1+\exp(-z))$),
the square loss
($F_{\mbox{\tiny{{sq}}}}(z)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}(1-z)^{2}$),
the Hinge loss
(${F_{\mbox{\tiny{{h}}}}}(z)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\max\\{0,1-z\\}$).
These losses have fundamental differences in terms of their relationships to
proper losses and surrogate losses, two dual views of losses related to the
fact that Bayes rules is an optimal predictor for the loss [46, 47, 51]. Our
examples are surrogate losses because they all define upperbounds of the
0/1-loss
(${F_{\mbox{\tiny{{0/1}}}}}(z)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}1_{z\leq
0}$, "$1$” being the indicator variable), furthermore calibrated because their
derivative in $z=0$ is negative [8].

##  4 $v$-derivatives, Bregman secant distortions

Unless otherwise stated, in this Section, $F$ is a function defined over
$\mathbb{R}$.

######  Definition 4.1.

[31] For any $z,v\in\mathbb{R}$, we let
$\updelta_{v}F(z)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}(F(z+v)-F(z))/v$
denote the $v$-derivative of $F$ in $z$.

---
Figure 1: Left: value of $S_{F|v}(z^{\prime}\|z)$ for convex $F$,
$v\stackrel{{\scriptstyle\mathrm{.}}}{{=}}z_{4}-z$ and various $z^{\prime}$
(colors), for which the Bregman Secant distortion is positive
($z^{\prime}=z_{1}$, green), negative ($z^{\prime}=z_{2}$, red), minimal
($z^{\prime}=z_{3}$) or null ($z^{\prime}=z_{4},z$). Right: depiction of
$Q_{F}(z,z+v,z^{\prime})$ for non-convex $F$ (Definition 4.6).

This expression, which gives the classical derivative when the offset
$v\rightarrow 0$, is called the $h$-derivative in quantum calculus [31,
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 $(z,F(z))$ and $(z+v,F(z+v))$ (Figure 1). Higher
order $v$-derivatives can be defined [31], though we shall need a more general
definition that accommodates for variable offsets.

######  Definition 4.2.

Let $v_{1},v_{2},...,v_{n}\in\mathbb{R}$ and
$\mathcal{V}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\\{v_{1},v_{2},...,v_{n}\\}$
and $z\in\mathbb{R}$. The $\mathcal{V}$-derivative $\updelta_{\mathcal{V}}F$
is:

$\displaystyle\updelta_{\mathcal{V}}F(z)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$
$\displaystyle\left\\{\begin{array}[]{rcl}F(z)&\mbox{ if
}&\mathcal{V}=\emptyset\\\ \updelta_{v_{1}}F(z)&\mbox{ if
}&\mathcal{V}=\\{v_{1}\\}\\\
\updelta_{\\{v_{n}\\}}(\updelta_{\mathcal{V}\backslash\\{v_{n}\\}}F)(z)&\lx@intercol\mbox{
<EMAIL_ADDRESS>(5)

If $v_{i}=v,\forall i\in[n]$ then we write
${\updelta^{(n)}_{v}F}(z)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\updelta_{\mathcal{V}}F(z)$.

In the Appendix, Lemma A computes the unravelled expression of
$\updelta_{\mathcal{V}}F(z)$, showing that the order of the elements in
$\mathcal{V}$ does not matter. $n$ is called the order of the
$\mathcal{V}$-derivative.

We can now define a generalization of Bregman divergences called Bregman
Secant distortions.

######  Definition 4.3.

For any $z,z^{\prime},v\in\mathbb{R}$, the Bregman Secant distortion
$S_{F|v}(z^{\prime}\|z)$ with generator $F$ and offset $v$ is:

$\displaystyle S_{F|v}(z^{\prime}\|z)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$ $\displaystyle
F(z^{\prime})-F(z)-(z^{\prime}-z)\updelta_{v}F(z).$ (6)

Even if $F$ is convex, the distortion is not necessarily positive, though it
is lowerbounded (Figure 1). There is an intimate relationship between the
Bregman Secant distortions and Bregman divergences. We shall use a definition
slightly more general than the original one when $F$ is differentiable [12,
eq. (1.4)], introduced in information geometry [5, Section 3.4] and recently
reintroduced in ML [11].

######  Definition 4.4.

The Bregman divergence with generator $F$ (scalar, convex) between
$z^{\prime}$ and $z$ is
$D_{F}(z^{\prime}\|z)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}F(z^{\prime})+F^{\star}(z)-z^{\prime}z$,
where $F^{\star}(z)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\sup_{t}tz-F(t)$ is
the convex conjugate of $F$.

We state the link between $S_{F|v}$ and $D_{F}$ (proof omitted).

######  Lemma 4.5.

Suppose $F$ strictly convex differentiable. Then $\lim_{v\rightarrow
0}S_{F|v}(z^{\prime}\|z)=D_{F}(z^{\prime}\|F^{\prime}(z))$.

Relaxed forms of Bregman divergences have been introduced in information
geometry [44].

######  Definition 4.6.

For any $a,b,\alpha\in\mathbb{R}$, denote for short
$\mathbb{I}_{a,b}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}[\min\\{a,b\\},\max\\{a,b\\}]$
and $(ab)_{\alpha}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\alpha
a+(1-\alpha)b$. The Optimal Bregman Information (OBI) of $F$ defined by triple
$(a,b,c)\in\mathbb{R}^{3}$ is:

$\displaystyle
Q_{F}(a,b,c)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\max_{\alpha:(ab)_{\alpha}\in\mathbb{I}_{a,c}}\\{\alpha
F(a)+(1-\alpha)F(b)-F((ab)_{\alpha})\\}.$ (7)

As represented in Figure 1 (right), the OBI is obtained by drawing the line
passing through $(a,F(a))$ and $(b,F(b))$ and then, in the interval
$\mathbb{I}_{a,c}$, look for the maximal difference between the line and $F$.
We note that $Q_{F}$ is non negative because $a\in\mathbb{I}_{a,c}$ and for
the choice $\alpha=1$, the RHS in (7) is 0. 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 1 provides a graphical
proof.

######  Lemma 4.7.

For any $F$,

$\displaystyle\forall z,v,z^{\prime}\in\mathbb{R},S_{F|v}(z^{\prime}\|z)$
$\displaystyle\geq$ $\displaystyle-Q_{F}(z,z+v,z^{\prime}).$ (8)

and if $F$ is convex,

$\displaystyle\forall z,v\in\mathbb{R},\forall
z^{\prime}\not\in\mathbb{I}_{z,z+v},S_{F|v}(z^{\prime}\|z)\geq 0,$ (9)
$\displaystyle\forall z,v,z^{\prime}\in\mathbb{R},S_{F|v}(z^{\prime}\|z)\geq-
Q_{F}(z,z+v,z+v).$ (10)

We shall abbreviate the two possible forms of OBI in the RHS of (8), (10) as:

$\displaystyle
Q^{*}_{F}(z,z^{\prime},v)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\left\\{\begin{array}[]{cl}Q_{F}(z,z+v,z+v)&\mbox{
if $F$ convex}\\\ Q_{F}(z,z+v,z^{\prime})&\mbox{
otherwise}\end{array}\right..$ (13)

##  5 Boosting using only queries on the loss

We make the assumption that all training predictions of so-called "weak
classifiers" are finite and non-zero.

######  Assumption 5.1.

$\forall t>0,\forall i\in[m]$, $|h_{t}(\bm{x}_{i})|\in(0,+\infty)$ (we thus
let
$M_{t}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\max_{i}|h_{t}(\bm{x}_{i})|$).

Excluding 0 ensures our algorithm does not make use of derivatives. If
predictions can be zero, there is a simple tweak that still avoids the use of
derivatives (Appendix, Section VIII.2). For short, we define two edge
quantities for $i\in[m]$ and $t=1,2,...$,

$\displaystyle e_{ti}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\alpha_{t}\cdot
y_{i}h_{t}(\bm{x}_{i}),\quad\tilde{e}_{ti}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}y_{i}H_{t}(\bm{x}_{i}),$
(14)

where $\alpha_{t}$ is a leveraging coefficient for the weak classifiers in an
ensemble
$H_{T}(.)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\sum_{t\in[T]}\alpha_{t}h_{t}(.)$.
We observe

$\displaystyle\tilde{e}_{ti}$ $\displaystyle=$
$\displaystyle\tilde{e}_{(t-1)i}+e_{ti}.$ (15)

###  5.1 Algorithm: SecBoost

####  5.1.1 General steps

Algorithm 1 SecBoost($\mathcal{S},T$)

Input sample ${\mathcal{S}}=\\{(\bm{x}_{i},y_{i}),i=1,2,...,m\\}$, number of
iterations $T$, initial $(h_{0},v_{0})$ (constant classification and offset).

Step 1 : let $H_{0}\leftarrow 1\cdot h_{0}$ and
$\bm{w}_{1}=-\updelta_{v_{0}}F(h_{0})\cdot\bm{1}$; // $h_{0},v_{0}\neq 0$
chosen s. t. $\updelta_{v_{0}}F(h_{0})\neq 0$

Step 2 : for $t=1,2,...,T$

Step 2.1 : let $h_{t}\leftarrow\textsc{wl}({\mathcal{S}}_{t},|\bm{w}_{t}|)$
//weak learner call,
${\mathcal{S}}_{t}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\\{(\bm{x}_{i},y_{i}\cdot\mathrm{sign}(w_{ti}))\\}$

Step 2.2 : let
$\eta_{t}\leftarrow(1/m)\cdot\sum_{i}{w_{ti}y_{i}h_{t}(\bm{x}_{i})}$
//unnormalized edge

Step 2.3 :

If bound on $\overline{W}_{2,t}$ available (Section 5.3) otherwise | general procedure pick $\varepsilon_{t}>0,\pi_{t}\in(0,1)$ and $\displaystyle\alpha_{t}\in\frac{\eta_{t}}{2(1+\varepsilon_{t})M_{t}^{2}\overline{W}_{2,t}}\cdot\left[1-\pi_{t},1+\pi_{t}\right];$ (16) $\alpha_{t}\leftarrow$Solveα($\mathcal{S},\bm{w}_{t},h_{t}$) // $\overline{W}_{2,t}>0,\varepsilon_{t}>0,\pi_{t}\in(0,1)$ // Theorem 5.8

Step 2.4 : let $H_{t}\leftarrow H_{t-1}+\alpha_{t}\cdot h_{t}$ //classifier
update

Step 2.5 : if
$\mathbb{I}_{ti}(\varepsilon_{t}\cdot\alpha_{t}^{2}M_{t}^{2}\overline{W}_{2,t})\neq\emptyset,\forall
i\in[m]$ then //new offsets

for $i=1,2,...,m$, let
$\displaystyle\mbox{$v_{ti}\leftarrow\textsc{oo}(t,i,\varepsilon_{t}\cdot\alpha_{t}^{2}M_{t}^{2}\overline{W}_{2,t})$}\>\>;$
(17)

else return $H_{t}$;

Step 2.6 : for $i=1,2,...,m$, let //weight update
$\displaystyle\mbox{\fcolorbox{red}{white}{$w_{(t+1)i} \leftarrow-
\diffloc{v_{ti}}{F}(y_i H_{t}(\ve{x}_i))$}}\>\>;$ (18)

Step 2.7 : if $\bm{w}_{t+1}=\bm{0}$ then break;

Return $H_{T}$.

Without further ado, Algorithm SecBoost presents our approach to boosting
without using derivatives information. The key differences with traditional
boosting algorithms are  red color framed. We summarize its key steps.
Step 1 This is the initialization step. Traditionally in boosting, one would
pick $h_{0}=0$. Note that $\bm{w}$ is not necessarily positive. $v_{0}$ is the
initial offset (Section 4).
Step 2.1 This step calls the weak learner, as in traditional boosting, using
variable "weights" on examples (the absolute value of $\bm{w}$). The key
difference with traditional boosting is that examples labels can switch
between iterations as well.
Step 2.3 This step computes the leveraging coefficient $\alpha_{t}$ of the
weak classifier $h_{t}$. It involves a quantity, $\overline{W}_{2,t}$, which
we define as any strictly positive real satisfying

$\displaystyle\mathbb{E}_{i\sim[m]}\left[\updelta_{\\{e_{ti},v_{(t-1)i}\\}}F(\tilde{e}_{(t-1)i})\cdot\left(\frac{h_{t}(\bm{x}_{i})}{M_{t}}\right)^{2}\right]\leq\overline{W}_{2,t}.$
(19)

For boosting rate’s sake, we should find $\overline{W}_{2,t}$ as small as
possible. We refer to (14) for the $e_{.},\tilde{e}_{.}$ notations; $v_{.}$ is
the current (set of) offset(s) (Section 4 for their definition). The second-
order $\mathcal{V}$-derivative in the LHS plays the same role as the second-
order derivative in classical boosting rates, see for example [47, Appendix,
Section 4]. As offsets $\rightarrow 0$, it converges to a second-order
derivative; otherwise, they still share some properties, such as the sign for
convex functions.

######  Lemma 5.2.

Suppose $F$ convex. For any $a\in\mathbb{R},b,c\in\mathbb{R}_{*}$,
$\updelta_{\\{b,c\\}}F(a)>0$.

(Proof in Appendix, Section VIII.3) We can also see a link with weights
variation since, modulo a slight abuse of notation, we have
$\updelta_{\\{e_{ti},v_{(t-1)i}\\}}F(\tilde{e}_{(t-1)i})=\updelta_{e_{ti}}w_{ti}$.
A substantial difference with traditional boosting algorithms is that we have
two ways to pick the leveraging coefficient $\alpha_{t}$; the first one can be
used when a convenient $\overline{W}_{2,t}$ is directly accessible from the
loss. Otherwise, there is a simple algorithm that provides parameters
(including $\overline{W}_{2,t}$) such that (19) is satisfied. Section 5.3
details those two possibilities and their implementation. In the more
favorable case (the former one), $\alpha_{t}$ can be chosen in an interval,
furthermore defined by flexible parameters
$\varepsilon_{t}>0,\pi_{t}\in(0,1)$. Note that fixing beforehand these
parameters is not mandatory: we can also pick any

$\displaystyle\alpha_{t}$ $\displaystyle\in$
$\displaystyle\eta_{t}\cdot\left(0,1/(M_{t}^{2}\overline{W}_{2,t})\right),$
(20)

and then compute choices for the corresponding $\varepsilon_{t}$ and
$\pi_{t}$. $\varepsilon_{t}$ is important for the algorithm and both
parameters are important for the analysis of the boosting rate. From the
boosting standpoint, a smaller $\varepsilon_{t}$ yields a larger $\alpha_{t}$
and a smaller $\pi_{t}$ reduces the interval of values in which we can pick
$\alpha_{t}$; 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 to boosting, the use of a so-called offset oracle, detailed in
Section 5.1.2.
Step 2.6 The weight update does not rely on a first-order oracle as in
traditional boosting, but uses only loss values through $v$-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
are unusual in the context of boosting can lead to early stopping. A
discussion on early stopping and how to avoid it is in Section 6.

####  5.1.2 The offset oracle, oo

Let us introduce notation

$\displaystyle\mathbb{I}_{ti}(z)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\left\\{v:Q^{*}_{F}(\tilde{e}_{ti},\tilde{e}_{(t-1)i},v)\leq
z\right\\},\forall i\in[m],\forall z>0.$ (21)

(see Figure 3 below to visualize $\mathbb{I}_{ti}(z)$ for a 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 (18) to an offset oracle, which
achieves the following, for iteration $\\#t$, example $\\#i$, limit OBI $z$:

$\textsc{oo}(t,i,z)$ returns some $v\in\mathbb{I}_{ti}(z)$ (22)

Note that the offset oracle has the freedom to pick the offset in a whole set.
Section 5.4 investigates implementations of the offset oracle, so let us make
a few essentially graphical remarks here. oo does not need to build the whole
$\mathbb{I}_{ti}(z)$ to return some $v\in\mathbb{I}_{ti}(z)$ for Step 2.5 in
SecBoost. In the construction steps of Figure 3, as soon as
$\mathcal{O}\neq\emptyset$, one element of $\mathcal{O}$ can be returned.
Figure 4 presents more examples of $\mathbb{I}_{ti}(z)$. One can remark that
the sign of the offset $v_{ti}$ in Step 2.5 of SecBoost is the same as the
sign of $\tilde{e}_{(t-1)i}-\tilde{e}_{ti}=-y_{i}\alpha_{t}h_{t}(\bm{x}_{i})$.
Hence, unless $F$ is derivable or all edges $y_{i}h_{t}(\bm{x}_{i})$ are of
the same sign ($\forall i$), the set of 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 a technical importance for boosting:
$\mathbb{I}_{ti}(z)$ is the set of offsets that limit an OBI for a training
example (Definition 4.6). The importance for boosting comes from Lemma 4.7:
upperbounding an OBI implies lowerbounding a Bregman Secant divergence, which
will also guarantee a sufficient slack between two successive boosting
iterations. This is embedded in a blueprint of a proof technique to show
boosting-compliant convergence which is not new, see e.g. [47]. We now detail
this convergence.

Remark that the expected edge $\eta_{t}$ in Step 2.2 of SecBoost is not
normalized. We define a normalized version of this edge as:

$\displaystyle[-1,1]\ni\tilde{\eta}_{t}$
$\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$
$\displaystyle\sum_{i}\frac{|w_{ti}|}{W_{t}}\cdot\tilde{y}_{ti}\cdot\frac{h_{t}(\bm{x}_{i})}{M_{t}},$
(23)

with$\tilde{y}_{ti}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}y_{i}\cdot\mathrm{sign}(w_{ti})$,
$W_{t}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\sum_{i}|w_{ti}|=\sum_{i}|\updelta_{v_{(t-1)i}}F(\tilde{e}_{(t-1)i})|$.
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:

$\displaystyle\overline{W}_{1,t}$
$\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$
$\displaystyle\left|\mathbb{E}_{i\sim[m]}\left[\updelta_{v_{(t-1)i}}F(\tilde{e}_{(t-1)i})\right]\right|$
(24)

(we indeed observe
$\overline{W}_{1,t}=|\mathbb{E}_{i\sim[m]}\left[w_{ti}\right]|$) In classical
boosting for convex decreasing losses†††This is an important class of losses
since it encompasses the convex surrogates of symmetric proper losses [45,
52], weights are non-negative and converge to a minimum (typically 0) as
examples get the right class with increasing confidence. Thus,
$\overline{W}_{1,t}$ can be an indicator of when classification becomes "good
enough" to stop boosting. In our more general setting, it shall be used in a
similar indicator. We are now in a position to show a first result about
SecBoost.

######  Theorem 5.3.

Suppose assumption 5.1 holds. Let
$F_{0}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}F(S,h_{0})$ in SecBoost and
$z^{*}$ any real such that $F(z^{*})\leq F_{0}$. Then we are guaranteed that
classifier $H_{T}$ output by SecBoost satisfies $F(S,H_{T})\leq F(z^{*})$ when
the number of boosting iterations $T$ yields:

$\displaystyle\sum_{t=1}^{T}\frac{\overline{W}^{2}_{1,t}(1-\pi_{t}^{2})}{\overline{W}_{2,t}(1+\varepsilon_{t})}\cdot\tilde{\eta}^{2}_{t}$
$\displaystyle\geq$ $\displaystyle 4(F_{0}-F(z^{*})),$ (25)

where parameters $\varepsilon_{t},\pi_{t}$ appear in Step 2.3 of SecBoost.

(proof in Appendix, Section VIII.4) We observe the tradeoff between the
freedom in picking parameters and convergence guarantee as exposed by (25): to
get more freedom in picking the leveraging coefficient $\alpha_{t}$, we
typically need $\pi_{t}$ large (Step 2.3) and to get more freedom in picking
the offset $v_{t}\neq 0$, we typically need $\varepsilon_{t}$ large (Step
2.5). However, allowing more freedom in such ways reduces the LHS and thus
impairs the guarantee in (25). Therefore, there is a subtle balance between
"freedom" of choice and convergence. Figure 2 pictures notable regimes for
$\overline{W}_{1,t}$ and $\overline{W}_{2,t}$, leading to varying
contributions in (25).

##### Boosting-compliant convergence

We characterize convergence in the boosting framework. We define

$\displaystyle\rho_{t}$
$\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$
$\displaystyle\overline{W}^{2}_{1,t}/\overline{W}_{2,t}.$

A small $\overline{W}^{2}_{1,t}$ is an indicator as to whether SecBoost is
close to a minimum, as seen from the left (blue) block in Figure 2. Analysis
of convergence based on a minimal value of $\overline{W}^{2}_{1,t}$ would be
standard with respect to classical non-convex optimisation. In our case, we
construct a criterion involving not just $\overline{W}^{2}_{1,t}$, but also
$\overline{W}_{2,t}$: considering for the illustration a $C^{2}$ loss
function, when $\overline{W}_{2,t}$ is small, it accounts for regions with
"small second-order" variations, more "regularity", which naturally offers
more leeway for minimization, in particular if $\overline{W}_{1,t}$ is large
(see Figure 2). This justifies the following assumption.

######  Assumption 5.4.

($\rho_{*}$-Convergence Regime, $\rho_{*}$-CR) We assume there exists
$\rho_{*}>0$ such that $\forall t\geq 1$, $\rho_{t}>\rho_{*}$.

---
Figure 2: When SecBoost approaches an optimum of the loss (blue + red), we can
expect $\overline{W}_{1,t}$ to be small. At a fixed $\overline{W}_{1,t}$, a
larger $\overline{W}_{2,t}$ indicates, at least locally near the secant
points, a region of higher curvature (green blocks). Since the maximal
difference of abscissae for a secant is proportional to the edge of the last
weak classifier (Figure 1, right, (7) and (21)), the smaller
$\overline{W}_{2,t}$ indicates a greater potential for decrease of the loss
(right green block, $\Delta_{2}>\Delta_{1}$) and leads to a greater
contribution to the sum in (25). When $\overline{W}^{2}_{1,t}$ is small enough
compared to $\overline{W}_{2,t}$, we take it as an indicator of the proximity
of a local optimum, which justifies fixing a lowerbound $\rho_{*}$ to
$\rho_{t}$ to analyze convergence "outside" this regime (best viewed in
color). Bold  gray arrow is discussion in Section 6.

We also rely on boosting’s traditional weak learning assumption.

######  Assumption 5.5.

($\upgamma$-Weak Learning Assumption, $\upgamma$-WLA) We assume the following
on the weak learner: $\exists\upgamma>0$ such that $\forall t>0$,
$|\tilde{\eta}_{t}|\geq\upgamma$.

We are now in a position to state a simple corollary to Theorem 5.3.

######  Corollary 5.6.

Suppose assumptions 5.1, 5.4 and 5.5 hold. Let
$F_{0}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}F(S,h_{0})$ in SecBoost and
$z^{*}$ any real such that $F(z^{*})\leq F_{0}$. If SecBoost is run for a
number $T$ of iterations satisfying

$\displaystyle T$ $\displaystyle\geq$
$\displaystyle\frac{4(F_{0}-F(z^{*}))}{\upgamma^{2}\rho_{*}}\cdot\frac{1+\max_{t\in[T]}\varepsilon_{t}}{1-\max_{t\in[T]}\pi^{2}_{t}},$
(26)

then $F(S,H_{T})\leq F(z^{*})$.

We remark that the dependency in $\upgamma$ is optimal [4].

###  5.3 Finding $\overline{W}_{2,t}$

There is lots of freedom in the choice of $\alpha_{t}$ in Step 2.3 of
SecBoost, and even more if we look at (20). This, however, requires access to
some bound $\overline{W}_{2,t}$. In the general case, the quantity it
upperbounds in (19) also depends on $\alpha_{t}$ because
$e_{ti}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\alpha_{t}\cdot
y_{i}h_{t}(\bm{x}_{i})$. So unless we can obtain such a "simple"
$\overline{W}_{2,t}$ that does not depend on $\alpha_{t}$, (16) – and (20) –
provide a system to solve for $\alpha_{t}$.
$\overline{W}_{2,t}$ via properties of $F$ Classical assumptions on loss
functions for zeroth-order optimization can provide simple expressions for
$\overline{W}_{2,t}$ (Table 1). Consider smoothness: we say that $F$ is
$\beta$-smooth if it is derivable and its derivative satisfies the Lipschitz
condition
$|F^{\prime}(z^{\prime})-F^{\prime}(z)|\leq\beta|z^{\prime}-z|,\forall
z,z^{\prime}$ [13]. Notice that this implies the condition on the
$v$-derivative of the derivative:
$|\updelta_{v}F^{\prime}(z)|\leq\beta,\forall z,v$. This also provides a
straightforward useful expression for $\overline{W}_{2,t}$.

######  Lemma 5.7.

Suppose that the loss $F$ is $\beta$-smooth. Then we can fix
$\overline{W}_{2,t}=2\beta$.

(Proof in Appendix, Section VIII.5) What the Lemma shows is that a bound on
the $v$-derivative of the derivative implies a bound on order-2
$\mathcal{V}$-derivatives (in the quantity that $\overline{W}_{2,t}$ bounds
(19)). Such a condition on $v$-derivatives is thus weaker than a condition on
derivatives, and it is strictly weaker if we impose a strictly positive
lowerbound on the offset’s absolute value, which would be sufficient to
characterize the boosting convergence of SecBoost.
A general algorithm for $\overline{W}_{2,t}$ If we cannot make any assumption
on $F$, there is a simple way to first obtain $\alpha_{t}$ and then
$\overline{W}_{2,t}$, from which all other parameters of Step 2.3 can be
computed.

Algorithm 2 Solveα($\mathcal{S},\bm{w},h$)

Input sample ${\mathcal{S}}=\\{(\bm{x}_{i},y_{i}),i=1,2,...,m\\}$,
$\bm{w}\in\mathbb{R}^{m}$, $h:\mathcal{X}\rightarrow\mathbb{R}$.

Step 1 : find any $a>0$ such that
$\displaystyle\frac{\left|\eta(\bm{w},h)-\eta(\tilde{\bm{w}}(\mathrm{sign}(\eta(\bm{w},h))\cdot
a),h)\right|}{|\eta(\bm{w},h)|}$ $\displaystyle<$ $\displaystyle 1.$ (27)

Return $\mathrm{sign}(\eta(\bm{w},h))\cdot a$.

We first need a few definitions. We first generalize the edge notation
appearing in Step 2.2:

$\displaystyle\eta(\bm{w},h)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$
$\displaystyle\mathbb{E}_{i\sim[m]}\left[w_{i}y_{i}h(\bm{x}_{i})\right],$

so that
$\eta_{t}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\eta(\bm{w}_{t},h_{t})$.
Remind the weight update,
$w_{ti}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}-\updelta_{v_{(t-1)i}}F(y_{i}H_{t-1}(\bm{x}_{i}))$.
We define a "partial" weight update,

$\displaystyle\tilde{w}_{ti}(\alpha)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$
$\displaystyle-\updelta_{v_{(t-1)i}}F(\alpha
y_{i}h_{t}(\bm{x}_{i})+y_{i}H_{t-1}(\bm{x}_{i}))$ (28)

(if we were to replace $v_{(t-1)i}$ by $v_{ti}$ and let
$\alpha\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\alpha_{t}$, then
$\tilde{w}_{ti}(\alpha)$ would be $w_{(t+1)i}$, hence the partial weight
update). Algorithm 2 presents the simple procedure to find $\alpha_{t}$.
Notice that we use $\tilde{\bm{w}}$ 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_{.i}$) needed to
compute (28).

######  Theorem 5.8.

Suppose Assumptions 5.1 and 5.5 hold and $F$ is continuous at all abscissae
$\\{\tilde{e}_{(t-1)i}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}y_{i}H_{t-1}(\bm{x}_{i}),i\in[m]\\}$.
Then there are always solutions to Step 1 of Solveα and if we let
$\alpha_{t}\leftarrow$Solveα($\mathcal{S},\bm{w}_{t},h_{t}$) and then compute

$\displaystyle\overline{W}_{2,t}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\left|\mathbb{E}_{i\sim[m]}\left[\frac{h^{2}_{t}(\bm{x}_{i})}{M^{2}_{t}}\cdot\updelta_{\\{\alpha_{t}y_{i}h_{t}(\bm{x})_{i}),v_{(t-1)i}\\}}F(\tilde{e}_{(t-1)i})\right]\right|,$

then $\overline{W}_{2,t}$ satisfies (19) and $\alpha_{t}$ satisfies (16) for
some $\varepsilon_{t}>0,\pi_{t}\in(0,1)$.

The proof, in Section VIII.6, proceeds by reducing condition (20) to (27). The
Weak Learning Assumption (5.5) is important for the denominator in the LHS of
(27) to be non zero. The continuity assumption at all abscissae is important
to have $\lim_{a\rightarrow 0}\eta(\tilde{\bm{w}}_{t}(a),h_{t})=\eta_{t}$,
which ensures the existence of solutions to (27), also easy to find, e.g. by a
simple dichotomic search starting from an 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 0, 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

|  |  |
---|---|---|---
(a) | (b) | (c) | (d)
|  |  |
Figure 3: A simple way to build $\mathbb{I}_{ti}(z)$ for a discontinuous loss $F$ ($\tilde{e}_{ti}<\tilde{e}_{(t-1)i}$ and $z$ are represented),  $\mathcal{O}$ being the set of solutions as it is built. We rotate two half-lines, one passing through $(\tilde{e}_{ti},F(\tilde{e}_{ti}))$ (thick line, $(\Delta)$) and a parallel one translated by $-z$ (dashed line) (a). As soon as $(\Delta)$ crosses $F$ on any point $(z^{\prime},F(z^{\prime}))$ with $z\neq\tilde{e}_{ti}$ while the dashed line stays below $F$, we obtain a candidate offset $v$ for oo, namely $v=z^{\prime}-\tilde{e}_{ti}$. In (b), we obtain an interval of values. We keep on rotating $(\Delta)$, eventually making appear several intervals for the choice of $v$ if $F$ is not convex (c). Finally, when we reach an angle such that the maximal difference between $(\Delta)$ and $F$ in $[\tilde{e}_{ti},\tilde{e}_{(t-1)i}]$ is $z$ ($z$ can be located at an intersection between $F$ and the dashed line), we stop and obtain the full $\mathbb{I}_{ti}(z)$ (d). |  |
---|---|---
(a) | (b) | (c)
|  |
Figure 4: More examples of ensembles $\mathbb{I}_{ti}(z)$ (in  blue) for the
$F$ in Figure 3. (a): $\mathbb{I}_{ti}(z)$ is the union of two intervals with
all candidate offsets non negative. (b): it is a single interval with non-
positive offsets. (c): at a discontinuity, if $z$ is smaller than the
discontinuity, we have no direct solution for $\mathbb{I}_{ti}(z)$ for at
least one positioning of the edges, but a simple trick bypasses the difficulty
(see text).

Figure 3 explains how to build graphically $\mathbb{I}_{ti}(z)$ for a general
$F$. While it is not hard to 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 VIII.7).

##  6 Discussion

For an 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 as iterations increase (e.g. learning deeper trees), keeping
Assumption 5.5 valid with its advantage over random guessing parameter
$\upgamma>0$. 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.4 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. As an illustration, in Figure 2, the middle  green box shows a local
minimum in which SecBoost can get trapped if offsets are small enough (slopes
of mixed signs, just like in the  blue area; $\overline{W}_{1,t}$ is small,
Assumption 5.4 breaks). However, for larger offsets, many slopes will tip to
being positive with one of their intersection with $F$ in the  blue area,
signalling a better optimum for prediction in this  blue area that SecBoost
can reach with its model update, schematized with a  gray arrow
($\overline{W}_{1,t}$ is large, Assumption 5.4 does not break). Section 5.4
has presented a general blueprint for the offset oracle but more specific
implementation designs can be used; some are discussed in the Appendix,
Section VIII.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 $\bm{w}_{t+1}\neq\bm{0}$. The update rule of $\bm{w}_{t}$ imposes that
the loss must then have non-zero variation for some examples between two
successive edges (14). 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 a different loss with the new model update $H_{.}$. As explained in
Appendix, Section VIII.11, this can be efficiently addressed by specific
designs on Solveα.

In the same way as there is no "1 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 to 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
boosting-compliant convergence, we do not need the loss to meet any of the
assumptions that those analyses usually rely on. Of course, recent advances in
zeroth-order optimization have also achieved substantial design tricks for the
implementation of such algorithms, something that undoubtedly needs to be
adressed in 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.

## Acknowledgments

RN thanks Frank Nielsen for fruitful discussions at an early stage of this
work.

## References

  * [1] A. Akhavan, E. Chzhen, M. Pontil, and A.-B. Tsybakov.  A gradient estimator via l1-randomization for online zero-order optimization with two point feedback.  In NeurIPS*35, 2022.
  * [2] A. Akhavan, M. Pontil, and A.-B. Tsybakov.  Exploiting higher order smoothness in derivative-free optimization and continuous bandits.  In NeurIPS*33, 2020.
  * [3] A. Akhavan, M. Pontil, and A.-B. Tsybakov.  Distributed zero-order optimisation under adversarial noise.  In NeurIPS*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 $4^{th}$ SIAM International Conference on Data Mining, pages 234–245, 2004.
  * [8] P. Bartlett, M. Jordan, and J. D. McAuliffe.  Convexity, classification, and risk bounds.  J. of the Am. Stat. Assoc., 101:138–156, 2006.
  * [9] P.-L. Bartlett and S. Mendelson.  Rademacher and gaussian complexities: Risk bounds and structural results.  JMLR, 3:463–482, 2002.
  * [10] G. Biau, B. Cadre, and L. Rouvière.  Accelerated gradient boosting.  Mach. Learn., 108(6):971–992, 2019.
  * [11] M. Blondel, A.-F. T. Martins, and V. Niculae.  Learning with Fenchel-Young losses.  J. Mach. Learn. Res., 21:35:1–35:69, 2020.
  * [12] 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.
  * [13] S. Bubeck.  Convex optimization: Algorithms and complexity.  Found. Trends Mach. Learn., 8(3-4):231–357, 2015.
  * [14] P.-S. Bullen.  Handbook of means and their inequalities.  Kluwer Academic Publishers, 2003.
  * [15] 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.
  * [16] C. Cartis and L. Roberts.  Scalable subspace methods for derivative-free nonlinear least-squares optimization.  Math. Prog., 199:461–524, 2023.
  * [17] S. Cheamanunkul, E. Ettinger, and Y. Freund.  Non-convex boosting overcomes random label noise.  CoRR, abs/1409.2905, 2014.
  * [18] L. Chen, J. Xu, and L. Luo.  Faster gradient-free algorithms for nonsmooth nonconvex stochastic optimization.  In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 5219–5233. PMLR, 2023.
  * [19] X. Chen, S. Liu, K. Xu, X. Li, X. Lin, M. Hong, and D. Cox.  ZO-AdaMM: Zeroth-order adaptive momentum method for black-box optimization.  In NeurIPS*32, 2019.
  * [20] X. Chen, Y. Tang, and N. Li.  Improve single-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.
  * [21] S. Cheng, G. Wu, and J. Zhu.  On the convergence of prior-guided zeroth-order optimisation algorithms.  In NeurIPS*34, 2021.
  * [22] Z. Cranko and R. Nock.  Boosted density estimation remastered.  In 36th ICML, pages 1416–1425, 2019.
  * [23] W. de Vazelhes, H. Zhang, H. Wu, X. Yuan, and B. Gu.  Zeroth-order hard-thresholding: Gradient error vs. expansivity.  In NeurIPS*35, 2022.
  * [24] D. Dua and C. Graff.  UCI machine learning repository, 2021.
  * [25] 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.
  * [26] L. Flokas, E.-V. Vlatakis-Gkaragkounis, and G. Piliouras.  Efficiently avoiding saddle points with zero order methods: No gradients required.  In NeurIPS*32, 2019.
  * [27] 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.
  * [28] A. Héliou, M. Martin, P. Mertikopoulos, and T. Rahier.  Zeroth-order non-convex learning via hierarchical dual averaging.  In 38th ICML, pages 4192–4202, 2021.
  * [29] F. Huang, L. Tao, and S. Chen.  Accelerated stochastic gradient-free and projection-free methods.  In 37th ICML, pages 4519–4530, 2020.
  * [30] 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 of Machine Learning Research, pages 14376–14389. PMLR, 2023.
  * [31] V. Kac and P. Cheung.  Quantum calculus.  Springer, 2002.
  * [32] M. J. Kearns and U. V. Vazirani.  An Introduction to Computational Learning Theory.  M.I.T. Press, 1994.
  * [33] M.J. Kearns.  Thoughts on hypothesis boosting, 1988.  ML class project.
  * [34] M.J. Kearns and Y. Mansour.  On the boosting ability of top-down decision tree learning algorithms.  J. Comp. Syst. Sc., 58:109–128, 1999.
  * [35] J. Larson, M. Menickelly, and S.-M. Wild.  Derivative-free optimization methods.  Acta Numerica, pages 287–404, 2019.
  * [36] 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 7453–7461. AAAI Press, 2022.
  * [37] T. Lin, Z. Zheng, and M.-I. Jordan.  Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization.  In NeurIPS*35, 2022.
  * [38] P.-M. Long and R.-A. Servedio.  Random classification noise defeats all convex potential boosters.  MLJ, 78(3):287–304, 2010.
  * [39] C. Maheshwari, C.-Y. Chiu, E. Mazumdar, S. Shankar Sastry, and L.-J. Ratliff.  Zeroth-order methods for convex-concave minmax problems: applications to decision-dependent risk minimization.  In 25th AISTATS, 2022.
  * [40] Y. Mansour, R. Nock, and R.-C. Williamson.  Random classification noise does not defeat all convex potential boosters irrespective of model choice.  In 40th ICML, 2023.
  * [41] E. Mhanna and M. Assaad.  Single point-based distributed zeroth-order optimization with a non-convex stochastic objective function.  In 40th ICML, volume 202 of Proceedings of Machine Learning Research, pages 24701–24719. PMLR, 2023.
  * [42] M. Mohri, A. Rostamizadeh, and A. Talwalkar.  Foundations of Machine Learning.  MIT Press, 2018.
  * [43] Y. Nesterov and V. Spokoiny.  Random gradient-free optimization of convex functions.  Foundations of Computational Mathematics, 17:527–566, 2017.
  * [44] F. Nielsen and R. Nock.  The Bregman chord divergence.  In Geometric Science of Information - 4th International Conference, 2019, pages 299–308, 2019.
  * [45] R. Nock and A. K. Menon.  Supervised learning: No loss no cry.  In 37th ICML, 2020.
  * [46] R. Nock and F. Nielsen.  Bregman divergences and surrogates for learning.  IEEE Trans.PAMI, 31:2048–2059, 2009.
  * [47] R. Nock and R.-C. Williamson.  Lossless or quantized boosting with integer arithmetic.  In 36th ICML, pages 4829–4838, 2019.
  * [48] N.-E. Pfetsch and Sebastian Pokutta.  IPBoost - non-convex boosting via integer programming.  In 37th ICML, volume 119, pages 7663–7672, 2020.
  * [49] Y. Qiu, U.-V. Shanbhag, and F. Yousefian.  Zeroth-order methods for nondifferentiable, nonconvex and hierarchical federated optimization.  In NeurIPS*36, 2023.
  * [50] M. Rando, C. Molinari, L. Rosasco, and S. Villa.  Structured zeroth-order for non-smooth optimization.  In NeurIPS*36, 2023.
  * [51] M.-D. Reid and R.-C. Williamson.  Composite binary losses.  JMLR, 11:2387–2422, 2010.
  * [52] M.-D. Reid and R.-C. Williamson.  Information, divergence and risk for binary experiments.  JMLR, 12:731–817, 2011.
  * [53] Z. Ren, Y. Tang, and N. Li.  Escaping saddle points in zeroth-order optimization: the power of two-point estimators.  In 40th ICML, volume 202 of Proceedings of Machine Learning Research, pages 28914–28975. PMLR, 2023.
  * [54] A.-K. Sahu, M. Zaheer, and S. Kar.  Towards gradient free and projection free stochastic optimization.  In 22nd AISTATS, pages 3468–3477, 2019.
  * [55] W. Shi, H. Gao, and B. Gu.  Gradient-free method for heavily constrained nonconvex optimization.  In 39th ICML, volume 162 of Proceedings of Machine Learning Research, pages 19935–19955. PMLR, 2022.
  * [56] M.-K. Warmuth and S. V. N. Vishwanathan.  Tutorial: Survey of boosting from an optimization perspective.  In 26th ICML, 2009.
  * [57] T. Werner and P. Ruckdeschel.  The column measure and gradient-free gradient boosting, 2019.
  * [58] H. Zhang and B. Gu.  Faster gradient-free methods for escaping saddle points.  In ICLR’23. OpenReview.net, 2023.
  * [59] H. Zhang, H. Xiong, and B. Gu.  Zeroth-order negative curvature finding: Escaping saddle points without gradients.  In NeurIPS*35, 2022.

Appendix

To differentiate with the numberings in the main file, the numbering of
Theorems, etc. is letter-based (A, B, …).

## Table of contents

Proofs Pg VIII

$\hookrightarrow$ Helper results Pg VIII.1
$\hookrightarrow$ Removing the $\neq 0$ part in Assumption 5.1 Pg VIII.2
$\hookrightarrow$ Proof of Lemma 5.2 Pg VIII.3
$\hookrightarrow$ Proof of Theorem 5.3 Pg VIII.4
$\hookrightarrow$ Proof of Lemma 5.7 Pg VIII.5
$\hookrightarrow$ Proof of Theorem 5.8 Pg VIII.6
$\hookrightarrow$ Implementation of the offset oraclePg VIII.7
$\hookrightarrow$ Proof of Lemma E Pg VIII.8
$\hookrightarrow$ Handling discontinuities in the offset oracle to prevent
stopping in Step 2.5 of SecBoostPg VIII.9
$\hookrightarrow$ A boosting pattern that can "survive" above
differentiability Pg VIII.10
$\hookrightarrow$ The case of piecewise constant losses for SolveαPg VIII.11

Algorithms detailed, implementation tricks and a toy experiment Pg IX

##  VIII Supplementary material on proofs

###  VIII.1 Helper results

We now show that the order of the elements of $\mathcal{V}$ does not matter to
compute the $\mathcal{V}$-derivative as in Definition 4.2. For any
$\bm{\sigma}\in\\{0,1\\}^{n}$, we let
$1_{\bm{\sigma}}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\sum_{i}\sigma_{i}$.

######  Lemma A.

For any $z\in\mathbb{R}$, any $n\in\mathbb{N}_{*}$ and any
$\mathcal{V}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\\{v_{1},v_{2},...,v_{n}\\}\subset\mathbb{R}$,

$\displaystyle\updelta_{\mathcal{V}}F(z)$ $\displaystyle=$
$\displaystyle\frac{\sum_{\bm{\sigma}\in\\{0,1\\}^{n}}(-1)^{n-1_{\sigma}}F(z+\sum_{i=1}^{n}\sigma_{i}v_{i})}{\prod_{i=1}^{n}v_{i}}.$
(29)

Hence, $\updelta_{\mathcal{V}}F$ is invariant to permutations of the elements
of $\mathcal{V}$.

###### Proof.

We show the result by induction on the size of $\mathcal{V}$, first noting
that

$\displaystyle\updelta_{\\{v_{1}\\}}F(z)=\updelta_{v_{1}}F(z)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$
$\displaystyle\frac{F(z+v_{1})-F(z)}{v_{1}}=\frac{1}{\prod_{i=1}^{1}v_{i}}\cdot\sum_{\sigma\in\\{0,1\\}}(-1)^{1-1_{\sigma}}F(z+\sigma
v_{1}).$ (30)

We then assume that (29) holds for
$\mathcal{V}_{n}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\\{v_{1},v_{2},...,v_{n}\\}$
and show the result for
$\mathcal{V}_{n+1}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\mathcal{V}_{n}\cup\\{v_{n+1}\\}$,
writing (induction hypothesis used in the second identity):

$\displaystyle\updelta_{\mathcal{V}_{n+1}}F(z)$ (33)
$\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$
$\displaystyle\frac{\updelta_{\mathcal{V}_{n}}F(z+v_{n+1})-\updelta_{\mathcal{V}_{n}}F(z)}{v_{n+1}}$
$\displaystyle=$
$\displaystyle\frac{\sum_{\bm{\sigma}\in\\{0,1\\}^{n}}(-1)^{n-1_{\bm{\sigma}}}F(z+\sum_{i=1}^{n}\sigma_{i}v_{i}+v_{n+1})-\sum_{\bm{\sigma}\in\\{0,1\\}^{n}}(-1)^{n-1_{\bm{\sigma}}}F(z+\sum_{i=1}^{n}\sigma_{i}v_{i})}{\prod_{i=1}^{n+1}v_{i}}$
$\displaystyle=$
$\displaystyle\frac{\sum_{\bm{\sigma}\in\\{0,1\\}^{n}}(-1)^{n-1_{\bm{\sigma}}}F(z+\sum_{i=1}^{n}\sigma_{i}v_{i}+v_{n+1})+\sum_{\bm{\sigma}\in\\{0,1\\}^{n}}(-1)^{n-1_{\bm{\sigma}}+1}F(z+\sum_{i=1}^{n}\sigma_{i}v_{i})}{\prod_{i=1}^{n+1}v_{i}}$
$\displaystyle=$
$\displaystyle\frac{\left\\{\begin{array}[]{l}\sum_{\bm{\sigma^{\prime}}\in\\{0,1\\}^{n+1}:\sigma^{\prime}_{n+1}=1}(-1)^{n-(1_{\bm{\sigma^{\prime}}}-1)}F(z+\sum_{i=1}^{n+1}\sigma^{\prime}_{i}v_{i})\\\
+\sum_{\bm{\sigma^{\prime}}\in\\{0,1\\}^{n+1}:\sigma^{\prime}_{n+1}=0}(-1)^{n+1-1_{\bm{\sigma^{\prime}}}}F(z+\sum_{i=1}^{n+1}\sigma^{\prime}_{i}v_{i})\end{array}\right.}{v^{n+1}}$
$\displaystyle=$
$\displaystyle\frac{\sum_{\bm{\sigma^{\prime}}\in\\{0,1\\}^{n+1}}(-1)^{n+1-1_{\bm{\sigma^{\prime}}}}F(z+\sum_{i=1}^{n+1}\sigma^{\prime}_{i}v_{i})}{\prod_{i=1}^{n+1}v_{i}},$
(34)

as claimed. ∎

We also have the following simple Lemma, which is a direct consequence of
Lemma A.

######  Lemma B.

For all $z,\in\mathbb{R},v,z^{\prime}\in\mathbb{R}_{*}$, we have

$\displaystyle\updelta_{v}F(z+z^{\prime})$ $\displaystyle=$
$\displaystyle\updelta_{v}F(z)+z^{\prime}\cdot\updelta_{\\{z^{\prime},v\\}}F(z).$
(35)

###### Proof.

It comes from Lemma A that
$\updelta_{\\{z^{\prime},v\\}}F(z)=\updelta_{\\{v,z^{\prime}\\}}F(z)=(\updelta_{v}F(z+z^{\prime})-\updelta_{v}F(z))/z^{\prime}$
(and we reorder terms). ∎

###  VIII.2 Removing the $\neq 0$ 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_{t}$ zeroes on some training
examples. The training sample being finite, there exists an open neighborhood
$\mathbb{I}$ in 0 such that
$h^{\prime}_{t}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}h_{t}+\delta$ does not
zero anymore on training examples, for any $\delta\in\mathbb{I}$. This changes
the advantage $\upgamma$ in the WLA (Definition 5.5) to some
$\upgamma^{\prime}$ satisfying (we assume $\delta>0$ wlog)

$\displaystyle\upgamma^{\prime}$ $\displaystyle\geq$
$\displaystyle\frac{\upgamma M_{t}}{M_{t}+\delta}-\frac{\delta}{M_{t}+\delta}$
$\displaystyle\geq$
$\displaystyle\upgamma-\frac{\delta}{M_{t}}\cdot(1+\upgamma),$

from which it is enough to pick $\delta\leq\varepsilon\upgamma
M_{t}/(1+\upgamma)$ to guarantee advantage
$\gamma^{\prime}\geq(1-\varepsilon)\gamma$. If $\varepsilon$ is a constant,
this translates in a number of boosting iterations in Corollary 5.6 affected
by a constant factor that we can choose as close to 1 as desired.

###  VIII.3 Proof of Lemma 5.2

Figure 5: Left: representation of the difference of averages in (36). Each of
the secants $(\Delta_{1})$ and $(\Delta_{2})$ can take either the red or black
segment. Which one is which depends on the signs of $c$ and $b$, but the
general configuration is always the same. Note that if $F$ is convex, one
necessarily sits above 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\rightarrow
0$. As $c$ converges to 0 but $b$ remains $>0$, $\updelta_{\\{b,c\\}}F(a)$
becomes proportional to the variation of the average secant midpoint; the
then-convergence of $b$ to 0 makes $\updelta_{\\{b,c\\}}F(a)$ converge to the
second-order derivative of $F$ at $a$. Right: in the special case where $F$ is
convex, one of the secants always sits above the other.

We reformulate

$\displaystyle\updelta_{\\{b,c\\}}F(a)$ $\displaystyle=$
$\displaystyle\frac{2}{b}\cdot\frac{1}{c}\cdot\left(\underbrace{\frac{F(a+b+c)+F(a)}{2}}_{\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\mu_{2}}-\underbrace{\frac{F(a+b)+F(a+c)}{2}}_{\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\mu_{1}}\right).$
(36)

Both $\mu_{1}$ and $\mu_{2}$ are averages that can be computed from the
midpoints of two secants (respectively):

$\displaystyle(\Delta_{1})$
$\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$
$\displaystyle[(a+c,F(a+c)),(a+b,F(a+b))],$ $\displaystyle(\Delta_{2})$
$\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$
$\displaystyle[(a,F(a)),(a+b+c,F(a+b+c))].$

Also, the midpoints of both secants have the same abscissa (and the ordinates
are $\mu_{1}$ and $\mu_{2}$), so to study the sign of
$\updelta_{\\{b,c\\}}F(a)$, we 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 in the abscissae of the other, this being sufficient to
give the position of both secants with respect to each other. We distinguish
four cases.

Case 1: $c>0,b>0$. We have $a+b+c>\max\\{a+b,a+c\\}$ and
$a<\min\\{a+b,a+c\\}$. $F$ being convex, $(\Delta_{2})$ sits above
$(\Delta_{1})$. So, $\mu_{2}\geq\mu_{1}$ and finally
$\updelta_{\\{b,c\\}}F(a)\geq 0$.

Case 2: $c<0,b<0$. We now have $a+b+c<\min\\{a+b,a+c\\}$ while
$a>\max\\{a+b,a+c\\}$, so $(\Delta_{2})$ sits above $(\Delta_{1})$. Again,
$\mu_{2}\geq\mu_{1}$ and finally $\updelta_{\\{b,c\\}}F(a)\geq 0$.

Case 3: $c>0,b<0$. We have $a+b<a$ and $a+b<a+b+c$. Also
$a+c>\max\\{a+b+c,a\\}$, so this time $(\Delta_{2})$ sits below $(\Delta_{1})$
but $cb<0$, so $\updelta_{\\{b,c\\}}F(a)\geq 0$ again.

Case 4: $c<0,b>0$. So $a+c<a<a+b$ and $a+c<a+b+c$. So $a+c<\min\\{a,a+b+c\\}$
and $a+b>\max\\{a,a+c\\}$, so $(\Delta_{2})$ sits below $(\Delta_{1})$. Since
$cb<0$, so $\updelta_{\\{b,c\\}}F(a)\geq 0$ again.

###  VIII.4 Proof of Theorem 5.3

Let us remind key simplified notations about edges, $\forall t\geq 0$:

$\displaystyle\tilde{e}_{ti}$
$\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$ $\displaystyle
y_{i}\cdot H_{t}(\bm{x}_{i}),$ (37) $\displaystyle e_{ti}$
$\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$ $\displaystyle
y_{i}\cdot\alpha_{t}h_{t}(\bm{x}_{i})=\tilde{e}_{ti}-\tilde{e}_{(t-1)i}.$ (38)

For short, we also let:

$\displaystyle Q^{*}_{ti}$
$\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$ $\displaystyle
Q^{*}_{F}(\tilde{e}_{ti},\tilde{e}_{(t-1)i},v_{i(t-1)}),$ (39)
$\displaystyle\Delta_{ti}$
$\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$
$\displaystyle\updelta_{v_{i(t-1)}}F(\tilde{e}_{ti})-\updelta_{v_{i(t-1)}}F(\tilde{e}_{(t-1)i}),$
(40)

where $Q^{*}_{..}$ is defined in (13). We also split the computation of the
leveraging coefficient $\alpha_{t}$ in SecBoostin two parts, the first
computing a real $a_{t}$ as:

$\displaystyle a_{t}$ $\displaystyle\in$
$\displaystyle\frac{1}{2(1+\varepsilon_{t})M_{t}^{2}\overline{W}_{2,t}}\cdot\left[1-\pi_{t},1+\pi_{t}\right],$
(41)

and then using $\alpha_{t}\leftarrow a_{t}\eta_{t}$. We now use Lemma 4.7
(main file) and get

$\displaystyle\mathbb{E}_{i\sim[m]}\left[S_{F|v_{ti}}(\tilde{e}_{ti}\|\tilde{e}_{(t+1)i})\right]$
$\displaystyle\geq$ $\displaystyle-\mathbb{E}_{i\sim
D}\left[Q^{*}_{(t+1)i}\right],\forall t\geq 0.$ (42)

If we reorganise (42) using the definition of $S_{F|.}(.\|.)$, we get:

$\displaystyle\mathbb{E}_{i\sim[m]}\left[F(\tilde{e}_{(t+1)i})\right]$ (43)
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{i\sim[m]}\left[F(\tilde{e}_{ti})\right]-\mathbb{E}_{i\sim[m]}\left[(\tilde{e}_{ti}-\tilde{e}_{(t+1)i})\cdot\updelta_{v_{ti}}F(\tilde{e}_{(t+1)i})\right]+\mathbb{E}_{i\sim[m]}\left[Q^{*}_{(t+1)i}\right]$
$\displaystyle=\mathbb{E}_{i\sim[m]}\left[F(\tilde{e}_{ti})\right]-\mathbb{E}_{i\sim[m]}\left[-e_{(t+1)i}\cdot\updelta_{v_{ti}}F(\tilde{e}_{(t+1)i})\right]+\mathbb{E}_{i\sim[m]}\left[Q^{*}_{(t+1)i}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{i\sim[m]}\left[F(\tilde{e}_{ti})\right]+\alpha_{t+1}\cdot\mathbb{E}_{i\sim[m]}\left[y_{i}h_{t+1}(\bm{x}_{i})\cdot\updelta_{v_{ti}}F(\tilde{e}_{(t+1)i})\right]+\mathbb{E}_{i\sim[m]}\left[Q^{*}_{(t+1)i}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{i\sim[m]}\left[F(\tilde{e}_{ti})\right]+a_{t+1}\eta_{t+1}\cdot\mathbb{E}_{i\sim[m]}\left[y_{i}h_{t+1}(\bm{x}_{i})\cdot\updelta_{v_{ti}}F(\tilde{e}_{ti})\right]$
$\displaystyle+a_{t+1}\eta_{t+1}\cdot\mathbb{E}_{i\sim[m]}\left[y_{i}h_{t+1}(\bm{x}_{i})\cdot\Delta_{(t+1)i}\right]+\mathbb{E}_{i\sim[m]}\left[Q^{*}_{(t+1)i}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{i\sim[m]}\left[F(\tilde{e}_{ti})\right]-a_{t+1}\eta_{t+1}\cdot\underbrace{\mathbb{E}_{i\sim[m]}\left[w_{(t+1)i}y_{i}h_{t+1}(\bm{x}_{i})\right]}_{=\eta_{t+1}}+a_{t+1}\eta_{t+1}\cdot\mathbb{E}_{i\sim[m]}\left[y_{i}h_{t+1}(\bm{x}_{i})\cdot\Delta_{(t+1)i}\right]$
$\displaystyle+\mathbb{E}_{i\sim[m]}\left[Q^{*}_{(t+1)i}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{i\sim[m]}\left[F(\tilde{e}_{ti})\right]-a_{t+1}\eta^{2}_{t+1}+a_{t+1}\eta_{t+1}\cdot\mathbb{E}_{i\sim[m]}\left[y_{i}h_{t+1}(\bm{x}_{i})\cdot\Delta_{(t+1)i}\right]+\mathbb{E}_{i\sim[m]}\left[Q^{*}_{(t+1)i}\right].$
(46)

(43) – (VIII.4) make use of definitions (38) (twice) and (40) as well as the
decomposition of the leveraging coefficient in (41).

Looking at (46), we see that we can have a boosting-compliant decrease of the
loss if the two quantities depending on $\Delta_{(t+1).}$ and $Q^{*}_{(t+1).}$
can be made small enough compared to $a_{t+1}\eta^{2}_{t+1}$. This is what we
investigate.

Bounding the term depending on $\Delta_{(t+1).}$ – We use Lemma B with
$z\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\tilde{e}_{ti},z^{\prime}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}e_{(t+1)i},v\stackrel{{\scriptstyle\mathrm{.}}}{{=}}v_{t}$,
which yields (also using (38) and the assumption that $h_{t+1}(\bm{x}_{i})\neq
0$):

$\displaystyle\Delta_{(t+1)i}$
$\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$
$\displaystyle\updelta_{v_{ti}}F(\tilde{e}_{(t+1)i})-\updelta_{v_{ti}}F(\tilde{e}_{ti})$
(47) $\displaystyle=$
$\displaystyle\updelta_{v_{ti}}F(\tilde{e}_{ti}+e_{(t+1)i})-\updelta_{v_{ti}}F(\tilde{e}_{ti})$
$\displaystyle=$ $\displaystyle
e_{(t+1)i}\cdot\updelta_{\\{e_{(t+1)i},v_{ti}\\}}F(\tilde{e}_{ti})$
$\displaystyle=$ $\displaystyle
y_{i}\cdot\alpha_{t+1}h_{t+1}(\bm{x}_{i})\cdot\updelta_{\\{e_{(t+1)i},v_{ti}\\}}F(\tilde{e}_{ti}),$

and so we get:

$\displaystyle
a_{t+1}\eta_{t+1}\cdot\mathbb{E}_{i\sim[m]}\left[y_{i}h_{t+1}(\bm{x}_{i})\cdot\Delta_{(t+1)i}\right]$
(48) $\displaystyle=$ $\displaystyle
a_{t+1}\eta_{t+1}\cdot\mathbb{E}_{i\sim[m]}\left[\alpha_{t+1}(y_{i}h_{t+1}(\bm{x}_{i}))^{2}\cdot\updelta_{\\{e_{(t+1)i},v_{ti}\\}}F(\tilde{e}_{ti})\right]$
$\displaystyle=$ $\displaystyle
a_{t+1}^{2}\eta_{t+1}^{2}\cdot\mathbb{E}_{i\sim[m]}\left[(h_{t+1}(\bm{x}_{i}))^{2}\cdot\updelta_{\\{e_{(t+1)i},v_{ti}\\}}F(\tilde{e}_{ti})\right]$
$\displaystyle\leq$ $\displaystyle
a_{t+1}^{2}\eta_{t+1}^{2}M^{2}_{t+1}\cdot\overline{W}_{2,t+1}.$

Bounding the term depending on $Q^{*}_{.(t+1)}$ – We immediately get from the
value picked in argument of $\mathbb{I}_{t+1}$ in step 2.5 of SecBoost, the
definition of $\mathbb{I}_{ti}(.)$ in (21) and our decomposition
$\alpha_{t}\leftarrow a_{t}\eta_{t}$ that
$Q^{*}_{(t+1)i}\leq\varepsilon_{t+1}\cdot
a_{t+1}^{2}\eta_{t+1}^{2}M_{t+1}^{2}\cdot\overline{W}_{2,t+1},\forall
i\in[m]$, so that:

$\displaystyle\mathbb{E}_{i\sim[m]}\left[Q^{*}_{(t+1)i}\right]$
$\displaystyle\leq$ $\displaystyle\varepsilon_{t+1}\cdot
a_{t+1}^{2}\eta_{t+1}^{2}M_{t+1}^{2}\cdot\overline{W}_{2,t+1}.$ (49)

Finishing up with the proof – Suppose that we choose $\varepsilon_{t+1}>0$,
$\pi_{t+1}\in(0,1)$ and $a_{t+1}$ as in (41). We then get from (46), (48),
(49) that for any choice of $v_{ti}$ in Step 2.5 of SecBoost,

$\displaystyle\mathbb{E}_{i\sim[m]}\left[F(\tilde{e}_{(t+1)i})\right]$ (50)
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{i\sim[m]}\left[F(\tilde{e}_{ti})\right]-a_{t+1}\eta^{2}_{t+1}+a_{t+1}^{2}\eta_{t+1}^{2}M^{2}_{t+1}\cdot\overline{W}_{2,t+1}+\varepsilon_{t+1}\cdot
a_{t+1}^{2}\eta_{t+1}^{2}M_{t+1}^{2}\cdot\overline{W}_{2,t+1}$
$\displaystyle=\mathbb{E}_{i\sim[m]}\left[F(\tilde{e}_{ti})\right]-a_{t+1}\eta^{2}_{t+1}\cdot\left(1-a_{t+1}\left(1+\varepsilon_{t+1}\right)M_{t+1}^{2}\cdot\overline{W}_{2,t+1}\right)$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{i\sim[m]}\left[F(\tilde{e}_{ti})\right]-\frac{\eta^{2}_{t+1}(1-\pi_{t+1}^{2})}{4\left(1+\varepsilon_{t+1}\right)M_{t+1}^{2}\cdot\overline{W}_{2,t+1}},$

where the last inequality is a consequence of (41). Suppose we pick
$H_{0}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}h_{0}\in\mathbb{R}$ a constant
and $v_{0}>0$ such that

$\displaystyle\updelta_{v_{0}}F(h_{0})$ $\displaystyle\neq$ $\displaystyle 0.$
(51)

The final classifier $H_{T}$ of SecBoost satisfies:

$\displaystyle\mathbb{E}_{i\sim[m]}\left[F(y_{i}H_{T}(\bm{x}_{i}))\right]$
$\displaystyle\leq$ $\displaystyle
F_{0}-\frac{1}{4}\cdot\sum_{t=1}^{T}\frac{\eta^{2}_{t}(1-\pi_{t}^{2})}{(1+\varepsilon_{t})M_{t}^{2}\overline{W}_{2,t}},$
(52)

with
$F_{0}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\mathbb{E}_{i\sim[m]}\left[F(\tilde{e}_{i0})\right]\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\mathbb{E}_{i\sim[m]}\left[F(y_{i}H_{0})\right]=\mathbb{E}_{i\sim[m]}\left[F(y_{i}h_{0})\right]$.
If we want $\mathbb{E}_{i\sim[m]}\left[F(y_{i}H_{T}(\bm{x}_{i}))\right]\leq
F(z^{*})$, assuming wlog $F(z^{*})\leq F_{0}$, then it suffices to iterate
until:

$\displaystyle\sum_{t=1}^{T}\frac{1-\pi_{t}^{2}}{\overline{W}_{2,t}(1+\varepsilon_{t})}\cdot\frac{\eta^{2}_{t}}{M_{t}^{2}}$
$\displaystyle\geq$ $\displaystyle 4(F_{0}-F(z^{*})).$ (53)

Remind that the edge $\eta_{t}$ is not normalized. We have defined a
normalized edge,

$\displaystyle[-1,1]\ni\tilde{\eta}_{t}$
$\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$
$\displaystyle\sum_{i}\frac{|w_{ti}|}{W_{t}}\cdot\tilde{y}_{ti}\cdot\frac{h_{t}(\bm{x}_{i})}{M_{t}},$
(54)

with
$\tilde{y}_{ti}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}y_{i}\cdot\mathrm{sign}(w_{ti})$
and
$W_{t}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\sum_{i}|w_{ti}|=\sum_{i}|\updelta_{v_{(t-1)i}}F(\tilde{e}_{(t-1)i})|$.
We have the simple relationship between $\eta_{t}$ and $\tilde{\eta}_{t}$:

$\displaystyle\tilde{\eta}_{t}$ $\displaystyle=$
$\displaystyle\sum_{i}\frac{|w_{ti}|}{W_{t}}\cdot(y_{i}\cdot\mathrm{sign}(w_{ti}))\cdot\frac{h_{t}(\bm{x}_{i})}{M_{t}}$
(55) $\displaystyle=$
$\displaystyle\frac{1}{W_{t}M_{t}}\cdot\sum_{i}w_{ti}y_{i}h_{t}(\bm{x}_{i})$
$\displaystyle=$ $\displaystyle\frac{m}{W_{t}M_{t}}\cdot\eta_{t},$

resulting in ($\forall t\geq 1$),

$\displaystyle\frac{\eta^{2}_{t}}{M_{t}^{2}}$ $\displaystyle=$
$\displaystyle\tilde{\eta}^{2}_{t}\cdot\left(\frac{W_{t}}{m}\right)^{2}$ (56)
$\displaystyle=$
$\displaystyle\tilde{\eta}^{2}_{t}\cdot\left(\mathbb{E}_{i\sim[m]}\left[|\updelta_{v_{(t-1)i}}F(\tilde{e}_{(t-1)i})|\right]\right)^{2}$
$\displaystyle\geq$
$\displaystyle\tilde{\eta}^{2}_{t}\cdot\left(\left|\mathbb{E}_{i\sim[m]}\left[\updelta_{v_{(t-1)i}}F(\tilde{e}_{(t-1)i})\right]\right|\right)^{2}$
$\displaystyle=\tilde{\eta}^{2}_{t}\cdot\overline{W}_{1,t}^{2},$

recalling
$\overline{W}_{1,t}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\left|\mathbb{E}_{i\sim
D}\left[\updelta_{v_{(t-1)i}}F(\tilde{e}_{(t-1)i})\right]\right|$. It comes
from (56) that a sufficient condition for (53) to hold is:

$\displaystyle\sum_{t=1}^{T}\frac{\overline{W}^{2}_{1,t}(1-\pi_{t}^{2})}{\overline{W}_{2,t}(1+\varepsilon_{t})}\cdot\tilde{\eta}^{2}_{t}$
$\displaystyle\geq$ $\displaystyle 4(F_{0}-F(z^{*})),$ (57)

which is the statement of Theorem 5.3.

###  VIII.5 Proof of Lemma 5.7

We first observe that for any $a\in\mathbb{R},b,c\in\mathbb{R}_{*}$,

$\displaystyle|\updelta_{\\{b,c\\}}F(a)|$ $\displaystyle=$
$\displaystyle\frac{1}{|bc|}\cdot\left|\begin{array}[]{c}F(a+b+c)-F(a+c)-bF^{\prime}(a+c)\\\
-(F(a+b)-F(a)-bF^{\prime}(a))\\\
+b(F^{\prime}(a+c)-F^{\prime}(a))\end{array}\right|$ (61) $\displaystyle\leq$
$\displaystyle\frac{1}{|bc|}\cdot\left(\begin{array}[]{c}|F(a+b+c)-F(a+c)-bF^{\prime}(a+c)|\\\
+|(F(a+b)-F(a)-bF^{\prime}(a))|\\\
+|b(F^{\prime}(a+c)-F^{\prime}(a))|\end{array}\right)$ (65)
$\displaystyle\leq$
$\displaystyle\frac{1}{|bc|}\cdot\left(\frac{\beta}{2}\cdot
b^{2}+\frac{\beta}{2}\cdot
b^{2}+\beta|bc|\right)=\beta+\beta\cdot\frac{b^{2}}{|bc|},$ (66)

where we used the $\beta$-smoothness of $F$ and twice [13, Lemma 3.4]. We can
also make a permutation in the expression of $\updelta_{\\{b,c\\}}F(a)$ and
instead write

$\displaystyle|\updelta_{\\{b,c\\}}F(a)|$ $\displaystyle=$
$\displaystyle\frac{1}{|bc|}\cdot\left|\begin{array}[]{c}F(a+b+c)-F(a+b)-cF^{\prime}(a+b)\\\
-(F(a+c)-F(a)-cF^{\prime}(a))\\\
+c(F^{\prime}(a+b)-F^{\prime}(a))\end{array}\right|$ (70) $\displaystyle\leq$
$\displaystyle\frac{1}{|bc|}\cdot\left(\begin{array}[]{c}|F(a+b+c)-F(a+b)-cF^{\prime}(a+b)|\\\
+|(F(a+c)-F(a)-cF^{\prime}(a))|\\\
+|c(F^{\prime}(a+b)-F^{\prime}(a))|\end{array}\right)$ (74)
$\displaystyle\leq$
$\displaystyle\frac{1}{|bc|}\cdot\left(\frac{\beta}{2}\cdot
c^{2}+\frac{\beta}{2}\cdot
c^{2}+\beta|bc|\right)=\beta+\beta\cdot\frac{c^{2}}{|bc|}.$ (75)

We thus have

$\displaystyle|\updelta_{\\{b,c\\}}F(a)|$ $\displaystyle\leq$
$\displaystyle\beta+\beta\cdot\left(\frac{\min\\{|b|,|c|\\}}{\sqrt{|bc|}}\right)^{2}$
$\displaystyle\leq$ $\displaystyle 2\beta,$

by the power mean inequality [14, Chapter III, Theorem 2]. Since
$|h_{t}(\bm{x}_{i})|\leq M_{t}$ by definition, we thus have

$\displaystyle\left|\mathbb{E}_{i\sim[m]}\left[\updelta_{\\{e_{ti},v_{(t-1)i}\\}}F(\tilde{e}_{(t-1)i})\cdot\left(\frac{h_{t}(\bm{x}_{i})}{M_{t}}\right)^{2}\right]\right|$
$\displaystyle\leq$ $\displaystyle 2\beta,$ (77)

which allows us to fix $\overline{W}_{2,t}=2\beta$ and completes the proof of
Lemma 5.7.

######  Remark C.

Our result is optimal in the sense that if we make one offset (say $b$) go to
zero, then the ratio in (VIII.5) goes to zero and we recover the condition on
the $v$-derivative of the derivative, $|\updelta_{c}F^{\prime}(z)|\leq\beta$.

###  VIII.6 Proof of Theorem 5.8

We consider the upperbound::

$\displaystyle\overline{W}_{2,t}$ (78)
$\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$
$\displaystyle\left|\mathbb{E}_{i\sim[m]}\left[\frac{h^{2}_{t}(\bm{x}_{i})}{M^{2}_{t}}\cdot\updelta_{\\{e_{ti},v_{(t-1)i}\\}}F(\tilde{e}_{(t-1)i})\right]\right|$
$\displaystyle=$
$\displaystyle\left|\mathbb{E}_{i\sim[m]}\left[\frac{h^{2}_{t}(\bm{x}_{i})}{M^{2}_{t}}\cdot\frac{1}{\tilde{e}_{ti}}\cdot\left(\frac{F(\tilde{e}_{ti}+v_{(t-1)i})-F(\tilde{e}_{ti})}{v_{(t-1)i}}-\frac{F(\tilde{e}_{(t-1)i}+v_{(t-1)i})-F(\tilde{e}_{(t-1)i})}{v_{(t-1)i}}\right)\right]\right|$
$\displaystyle=$
$\displaystyle\left|\frac{1}{\alpha_{t}}\cdot\mathbb{E}_{i\sim[m]}\left[\frac{h_{t}(\bm{x}_{i})}{y_{i}M^{2}_{t}}\cdot\left(\frac{F(\tilde{e}_{ti}+v_{(t-1)i})-F(\tilde{e}_{ti})}{v_{(t-1)i}}-\frac{F(\tilde{e}_{(t-1)i}+v_{(t-1)i})-F(\tilde{e}_{(t-1)i})}{v_{(t-1)i}}\right)\right]\right|$
$\displaystyle=$
$\displaystyle\left|\frac{1}{\alpha_{t}}\cdot\mathbb{E}_{i\sim[m]}\left[\frac{y_{i}h_{t}(\bm{x}_{i})}{M^{2}_{t}}\cdot\left(\updelta_{v_{(t-1)i}}F(\tilde{e}_{ti})-\updelta_{v_{(t-1)i}}F(\tilde{e}_{(t-1)i})\right)\right]\right|$

(The last identity uses the fact that $y_{i}\in\\{-1,1\\}$). Remark that we
have extracted $\alpha_{t}$ from the denominator but it is still present in
the arguments $\tilde{e}_{ti}$. For any classifier $h$, we introduce notation

$\displaystyle\eta(\bm{w},h)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$
$\displaystyle\mathbb{E}_{i\sim[m]}\left[w_{i}y_{i}h(\bm{x}_{i})\right],$

and so $\eta_{t}$ (Step 2.2 in SecBoost) is also $\eta(\bm{w}_{t},h_{t})$,
which is guaranteed to be non-zero by the Weak Learning Assumption (5.5). We
want, for some $\varepsilon_{t}>0,\pi_{t}\in[0,1)$,

$\displaystyle\alpha_{t}$ $\displaystyle\in$
$\displaystyle\frac{\eta_{t}}{2(1+\varepsilon_{t})M_{t}^{2}\overline{W}_{2,t}}\cdot\left[1-\pi_{t},1+\pi_{t}\right].$
(79)

This says that the sign of $\alpha_{t}$ is the same as the sign of
$\eta(\bm{w}_{t},h_{t})=\eta_{t}$. Since we know its sign, let us look for its
absolute value:

$\displaystyle|\alpha_{t}|$ $\displaystyle\in$
$\displaystyle\frac{|\eta_{t}|}{2(1+\varepsilon_{t})M_{t}^{2}\overline{W}_{2,t}}\cdot\left[1-\pi_{t},1+\pi_{t}\right].$
(80)

From (20) (main file), we can in fact search $\alpha_{t}$ in the union of all
such intervals for $\varepsilon_{t}>0,\pi_{t}\in[0,1)$, which amounts to find
first:

$\displaystyle|\alpha_{t}|$ $\displaystyle\in$
$\displaystyle\left(0,\frac{|\eta_{t}|}{M_{t}^{2}\overline{W}_{2,t}}\right),$

and then find any $\varepsilon_{t}>0,\pi_{t}\in[0,1)$ such that (80) holds.
Using (78) and simplifying the external dependency on $\alpha_{t}$, we then
need

$\displaystyle 1$ $\displaystyle\in$
$\displaystyle\left(0,\underbrace{\frac{|\eta_{t}|}{|\mathbb{E}_{i\sim[m]}\left[y_{i}h_{t}(\bm{x}_{i})\cdot\left(\updelta_{v_{(t-1)i}}F(\alpha_{t}y_{i}h_{t}(\bm{x}_{i})+\tilde{e}_{(t-1)i})-\updelta_{v_{(t-1)i}}F(\tilde{e}_{(t-1)i})\right)\right]|}}_{\stackrel{{\scriptstyle\mathrm{.}}}{{=}}B(\alpha_{t})}\right),$
(81)

under the constraint that the sign of $\alpha_{t}$ be the same as that of
$\eta_{t}$. But, using notation (28) (main file), we have

$\displaystyle B(\alpha_{t})$ $\displaystyle=$
$\displaystyle|\eta(\bm{w}_{t},h_{t})-\eta(\tilde{\bm{w}}_{t}(\alpha_{t}),h_{t})|,$

and so to get (81) satisfied, it is sufficient that

$\displaystyle\frac{|\eta_{t}-\eta(\tilde{\bm{w}}_{t}(\alpha_{t}),h_{t})|}{|\eta_{t}|}$
$\displaystyle<$ $\displaystyle 1,$ (82)

which is Step 1 in Solveα. The Weak Learning Assumption (5.5) guarantees that
the denominator is $\neq 0$ so this can always be evaluated. The continuity of
$F$ in all $\tilde{e}_{(t-1)i}$ guarantees $\lim_{\alpha_{t}\rightarrow
0}\eta(\tilde{\bm{w}}_{t}(\alpha_{t}),h_{t})=\eta_{t}$, and thus guarantees
the existence of solutions to (82) for some $|\alpha_{t}|>0$.

To summarize, finding $\alpha_{t}$ can be done in two steps, (i) solve

$\displaystyle\frac{\left|\eta_{t}-\eta(\tilde{\bm{w}}_{t}(\mathrm{sign}(\eta_{t})\cdot
a),h_{t})\right|}{|\eta_{t}|}$ $\displaystyle<$ $\displaystyle 1$

for some $a>0$ and (ii) let
$\alpha_{t}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\mathrm{sign}(\eta_{t})\cdot
a$. This is the output of Solveα($\mathcal{S},\bm{w}_{t},h_{t}$), which ends
the proof of Theorem 5.8.

###  VIII.7 Implementation of the offset oracle: particular cases

Consider the "spring loss" that we define, for $[.]$ denoting the nearest
integer, as:

$\displaystyle
F_{\mbox{\tiny{{sl}}}}(z)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\log(1+\exp(-z))+1-\sqrt{1-4\left(z-[z]\right)^{2}}.$
(83)

Figure 6 plots this loss, which composes the logistic loss with a
"$\mathsf{U}$"-shaped term. This loss would escape all optimization algorithms
of Table 1 (Appendix), yet there is a trivial implementation of our offset
oracle, as explained in Figure 6:

  1. 1.

if the interval $\mathbb{I}$ defined by $\tilde{e}_{(t-1)i}$ and
$\tilde{e}_{ti}$ contains at least one peak, compute the tangence point
($z_{t}$) at the closest local "$\mathsf{U}$" that passes through
$(\tilde{e}_{(t-1)i},F(\tilde{e}_{(t-1)i}))$; then if $z_{t}\in\mathbb{I}$
then $v_{ti}\leftarrow z_{t}-\tilde{e}_{(t-1)i}$, else
$v_{ti}\leftarrow\tilde{e}_{ti}-\tilde{e}_{(t-1)i}$;

  2. 2.

otherwise $F$ in $\mathbb{I}$ is strictly convex and differentiable: a simple
dichotomic search can retrieve a feasible $v_{ti}$ (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|$ ($a,b$ belonging to
the abscissae of the same "$\mathsf{U}$") decreasing by a fixed factor,
choosing $v_{ti}\leftarrow v$ of the largest tabulated $|a-b|$ no larger than
$|\tilde{e}_{ti}-\tilde{e}_{(t-1)i}|$.
Discontinuities discontinuities do not represent issues if the argument $z$ of
$\mathbb{I}_{ti}(z)$ is large enough, as shown from the following simple
Lemma.

######  Lemma D.

Define the discontinuity of $F$ as:

$\displaystyle\mathrm{disc}(F)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\max\left\\{\begin{array}[]{l}\sup_{z}|F(z)-\lim_{z^{-}}F(z)|,\\\
\sup_{z}|F(z)-\lim_{z^{+}}F(z)|\end{array}\right\\}.$ (86)

For any $z\geq 0$, if $\mathrm{disc}(F)\leq z$ then
$\mathbb{I}_{ti}(z)\neq\emptyset,\forall t\geq 1,\forall i\in[m]$.

Figure 4 (c) shows a case where the discontinuity is larger than $z$. In this
case, an issue eventually happens for computing the next weight happens, only
when the current edge is at the discontinuity. We note that as iterations
increase and the weak learner finds it eventually more difficult to return
weak hypotheses with $\eta_{.}$ large enough, the discontinuities may become
an 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
$\alpha_{t}$: this is described in the Appendix, Section VIII.9.
The case of convex losses If $F$ is convex (not necessarily differentiable nor
strictly convex), there is a simple way to find a valid output for the offset
oracle, which relies on the following Lemma.

######  Lemma E.

Suppose $F$ convex. Then for any $z,z^{\prime}\in\mathbb{R},v\neq 0$,

$\displaystyle\\{v>0:Q^{*}_{F}(z,z^{\prime},v)=r\\}$ (87) $\displaystyle=$
$\displaystyle\left\\{v>0:D_{F}\left(z\left\|\frac{F(z+v)-F(z)}{v}\right.\right)=r\right\\}.$

(proof in Appendix, Section VIII.8) By definition,
$\mathbb{I}_{ti}(z^{\prime})\subseteq\mathbb{I}_{ti}(z)$ for any
$z^{\prime}\leq z$, so a simple way to implement the offset oracle’s output
$\textsc{oo}(t,i,z)$ is, for some $0<r<z$, to solve the Bregman identity in
the RHS of (87) and then return any relevant $v$. If $F$ is strictly convex,
there is just one choice.

If solving the Bregman identity is tedious but $F$ is strictly convex, there a
simple dichotomic search that is guaranteed to find a feasible $v$. It
exploits the fact that the abscissa maximizing the difference between any
secant of $F$ and $F$ has a simple closed form (see [22, Supplement, Figure
13]) and so the OBI in (7) (Definition 4.6) has a closed form as well. In this
case, it is enough, after taking a first non-zero guess for $v$ (either
positive or negative), to divide it by a constant $>1$ until the corresponding
OBI is no larger than the $z$ in the query $\textsc{oo}(t,i,z)$.

Figure 6: The spring loss in (83) 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 oo can be
obtained from the computation of a single tangent point (here, the orange $v$,
see text; best viewed in color).

###  VIII.8 Proof of Lemma E

Figure 7: Computing the OBI $Q_{F}(z,z+v,z+v)$ for $F$ convex, $(z,v)$ being
given and $v>0$. We compute the line $(\Delta_{t})$ crossing $F$ at any point
$t$, with slope equal to the secant $[(z,F(z)),(z+v,F(z+v))]$ and then the
difference between $F$ at $z+v$ and this line at $z+v$. We move $t$ so as to
maximize this difference. The optimal $t$ (in green) gives the corresponding
OBI. In (90), we are interested in finding $v$ given this difference, $r$. We
also need to replicate this computation for $v<0$.

$F$ being convex, we first want to compute the set

$\displaystyle\mathbb{I}_{z,v,r}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\\{v>0:Q_{F}(z,z+v,z+v)=r\\},$
(88)

where $r$ is supposed small enough for $\mathbb{I}_{z,v,r}$ to be non-empty.
There is a simple graphical solution to this which, as Figure 7 explains,
consists in finding $v$ solution of

$\displaystyle\sup_{t}F(z+v)-\left(F(t)+\left(\frac{F(z+v)-F(z)}{v}\right)\cdot(z+v-t)\right)$
$\displaystyle=$ $\displaystyle r.$ (89)

The LHS simplifies:

$\displaystyle\sup_{t}F(z+v)-\left(F(t)+\left(\frac{F(z+v)-F(z)}{v}\right)\cdot(z+v-t)\right)$
$\displaystyle=$
$\displaystyle\frac{(z+v)F(z)-zF(z+v)}{v}+\sup_{t}\left\\{t\cdot\frac{F(z+v)-F(z)}{v}-F(t)\right\\}$
$\displaystyle=$
$\displaystyle\frac{(z+v)F(z)-zF(z+v)}{v}+F^{\star}\left(\frac{F(z+v)-F(z)}{v}\right)$
$\displaystyle=$ $\displaystyle
F(z)+F^{\star}\left(\frac{F(z+v)-F(z)}{v}\right)-z\cdot\frac{F(z+v)-F(z)}{v}$
$\displaystyle=$ $\displaystyle
D_{F}\left(z\left\|\frac{F(z+v)-F(z)}{v}\right.\right),$

so we end up with an equivalent but more readable definition for
$\mathbb{I}_{z,v,r}$:

$\displaystyle\mathbb{I}_{z,v,r}$ $\displaystyle=$
$\displaystyle\left\\{v>0:D_{F}\left(z\left\|\frac{F(z+v)-F(z)}{v}\right.\right)=r\right\\},$
(90)

which yields the statement of the Lemma.

###  VIII.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 in Step 2.5. Lemma D shows that
early stopping can only be triggered by too large local discontinuities at the
edges. This is a weak requirement on running SecBoost, but there exists a 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 $\alpha_{t}$ in Step 2.3.

######  Lemma F.

Suppose $F$ is any function defined over $\mathbb{R}$ discontinuities of zero
Lebesgue measure. Then Corollary 5.6 holds for boosting $F$ with its
inequality strict while never triggering early stopping in Step 2.5 of
SecBoost.

###### Proof.

To show that we never trigger stopping in Step 2.5, it is sufficient to show
that we can run SecBoostwhile ensuring $F$ is continuous in an open
neighborhood around all edges $y_{i}H_{t}(\bm{x}_{i}),\forall i\in[m],\forall
t\geq 0$ (by letting $H_{0}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}h_{0}$).
Remind that
$\tilde{e}_{ti}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\tilde{e}_{(t-1)i}+\alpha_{t}\cdot
y_{t}h_{t}(\bm{x}_{i})$, so changing $\alpha_{t}$ changes all edges. We just
have to show that either computing $\alpha_{t}$ ensures such a continuity, or
$\alpha_{t}$ can be slightly modified to do so. We have two ways to compute
$\alpha_{t}$:

  1. 1.

using a value for $\overline{W}_{2,t}$ that represents an "absolute"
upperbound in the sense of (19) (e.g. Lemma 5.7) and then compute $\alpha_{t}$
as in Step 2.3 of SecBoost;

  2. 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 to a
straightforward choice for $h_{0}$). This proves the Lemma for [2.].

If we rely on [1.] and the $\alpha_{t}$ computed leads to some
discontinuities, then we have complete control to change $\alpha_{t}$: any
continuous change of $\varepsilon_{t}$ induces a continuous change in
$\alpha_{t}$ and thus a continuous change of all edges as well. So, starting
from the initial $\varepsilon_{t}$ chosen in Step 2.3, we increase it to a
value $\varepsilon_{t}^{*}>\varepsilon_{t}$, which we want to keep as small as
possible. We can define for each $i\in[m]$ an open set $(a_{i},b_{i})$ which
is the interval spanned by the new $\tilde{e}_{ti}(\varepsilon^{\prime}_{t})$
using $\varepsilon^{\prime}_{t}\in(\varepsilon_{t},\varepsilon_{t}^{*})$.
Since there are only finitely many discontinuities on $F$, there exists a
small $\varepsilon_{t}^{*}>\varepsilon_{t}$ such that

$\displaystyle\forall i\in[m],\forall z\in(a_{i},b_{i}),F\mbox{ is continuous
on }z.$

This means that
$\forall\varepsilon^{\prime}_{t}\in(\varepsilon_{t},\varepsilon_{t}^{*})$, we
end up with a loss without any discontinuities on the new edges. Now comes the
reason why we want $\varepsilon_{t}^{*}-\varepsilon_{t}$ small: we can check
that there always exist a small enough $\varepsilon_{t}^{*}>\varepsilon_{t}$
such that for any $\varepsilon^{\prime}_{t}$ we choose, the boosting rate in
Corollary 5.6 is affected by at most 1 additional iteration. Indeed, while we
slightly change parameter $\varepsilon_{t}$ to land all new edges outside of
discontinuities of $F$, we also increase the contribution of the boosting
iteration in the RHS of (26) by a quantity $\delta>0$ which can be made as
small as required — hence we can just replace the inequality in (26) by a
strict inequality. This proves the statement of the Lemma if we rely on [1.]
above.

This completes the proof of Lemma F. ∎

###  VIII.10 A boosting pattern that can "survive" above differentiability

Figure 8: Case $F$ strictly convex, with two cases of limit OBI $z$ and
$z^{\prime}$ in $\mathbb{I}_{.i}(.)$. Example $i$ has $e_{ti}>0$ and
$e_{(t-1)i}>0$ (14) large enough (hence, edges with respect to weak
classifiers $h_{t}$ and $h_{t-1}$ large enough) so that
$\mathbb{I}_{ti}(z)\cap\mathbb{I}_{(t-1)i}(z)=\mathbb{I}_{(t-1)i}(z)\cap\mathbb{I}_{(t-2)i}(z)=\mathbb{I}_{ti}(z)\cap\mathbb{I}_{(t-2)i}(z)=\emptyset$.
In this case, regardless of the offsets chosen by oo, we are guaranteed that
its weights satisfy $w_{(t+1)i}<w_{ti}<w_{(t-1)i}$, 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 a
larger $z^{\prime}$, this is not guaranteed anymore: in this case, it may be
the case that $w_{(t+1)i}>w_{ti}$.

Suppose $F$ is strictly convex and strictly decreasing as for classical convex
surrogates (e.g. logistic loss). Assuming wlog all $\alpha_{.}>0$ and example
$i$ has both $y_{i}h_{t}(\bm{x}_{i})>0$ and $y_{i}h_{t-1}(\bm{x}_{i})>0$, as
long as $z$ is small enough, we are guaranteed that any choice
$v_{t-1}\in\mathbb{I}_{(t-1)i}(z)$ and $v_{t}\in\mathbb{I}_{ti}(z)$ results in
$0<w_{(t+1)i}<w_{ti}$, which follows the classical boosting pattern that
examples receiving the right class by weak hypotheses have their weight
decreased (See Figure 8). If $z=z^{\prime}$ is large enough, then this does
not hold anymore as seen from Figure 8.

###  VIII.11 The case of piecewise constant losses for Solveα

Figure 9: How our algorithm works with the 0/1 loss (in red): at the
initialization stage, assuming we pick $h_{0}=0$ for simplicity and some
$v_{0}<0$, 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
$t$ when we update the weights (Step 2.6), one of two cases can happen on some
training example $(\bm{x},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 0. 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.

Figure 9 schematizes a run of our algorithm when training loss = 0/1 loss. At
the initialization, it is easy to get all examples to have non-zero weight.
The weight update for example $(\bm{x},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 $yH_{t-1}(\bm{x})$ and $yH_{t}(\bm{x})$. Hence, if the
predicted label does not change
($\mathrm{sign}(H_{t}(\bm{x}))=\mathrm{sign}(H_{t-1}(\bm{x}))$), then the next
weight ($w_{t+1}$) of the example will be zero (Figure 9, case (A)). However,
if the predicted label does change
($\mathrm{sign}(H_{t}(\bm{x}))\neq\mathrm{sign}(H_{t-1}(\bm{x}))$) then the
example may get a non-zero weight depending on the offset chosen.

Hence, our generic implementation of Algorithms 3 and 4 may completely fail at
providing non-zero 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 a
too small subset of those, that would break the Weak Learning Assumption for
boosting compliance of the next iteration (Assumption 5.5). One way to
overcome this issue is to change Step 2 in Algorithm Solve$\\_{\mbox{\tiny
extended}}$, which finds $\alpha$, by a more informed procedure that uses the
knowledge that 0 is the discontinuity of the loss, instead of the current Step
2 which builds a geometrically decreasing sequence of $|\alpha|$ (until an
acceptable one is found). Each example for which $H_{t-1}(\bm{x})\cdot
h_{t}(\bm{x})<0$ is a candidate for case (B) in Figure 9 – call them "good
examples". One can compute a candidate $\alpha$ for each good example that
would put it in case (B) and then pick one "good" $\alpha$ in this list. this
simple procedure can prevent early stopping and bring substantial improvement
in test error – even when the algorithm operates for several iterations with a
small fraction of non-zero weights –; more sophisticated choices also exist on
such particular losses, displaying that there is no "1 size fits all" solution
as we emphasize in Section 6.

##  IX Supplementary material on algorithms, implementation tricks and a toy
experiment

###  IX.1 Algorithm and implementation of Solveα and how to find parameters
from Theorem 5.8

As Theorem 5.8 explains, Solveα can easily get to not just the leveraging
coefficient $\alpha_{t}$, but also other parameters that are necessary to
implement SecBoost: $\overline{W}_{2,t}$ and $\varepsilon_{t}$ (both used in
Step 2.5). We now provide a simple pseudo code on how to implement Solveα amnd
get, on top of it, the two other parameters. We do not seek $\pi_{t}$ since it
is useful only in the convergence analysis. Also, our proposal implementation
is optimized for complexity (because of the geometric updating of $\delta,W$
in their respective loops) but much less so for for accuracy. Algorithm
Solve$\\_{\mbox{\tiny extended}}$ explains the overall procedure.

Algorithm 3 Solve$\\_{\mbox{\tiny extended}}$($\mathcal{S},\bm{w},h,M$)

Input sample ${\mathcal{S}}=\\{(\bm{x}_{i},y_{i}),i=1,2,...,m\\}$,
$\bm{w}\in\mathbb{R}^{m}$, $h:\mathcal{X}\rightarrow\mathbb{R}$, $M\neq 0$.

// in our case, $\bm{w}\leftarrow\bm{w}_{t};h\leftarrow h_{t};M\leftarrow
M_{t}$ (current weights, weak hypothesis and max confidence, see Step 2.3 in
SecBoost and Assumption 5.1)

Step 1 : // all initializations  $\displaystyle\eta_{\mbox{\tiny init}}$
$\displaystyle\leftarrow$ $\displaystyle\eta(\bm{w},h);$ (91)
$\displaystyle\delta$ $\displaystyle\leftarrow$ $\displaystyle 1.0;$ (92)
$\displaystyle W_{\mbox{\tiny init}}$ $\displaystyle\leftarrow$ $\displaystyle
1.0;$ (93)

Step 2 : do // Step 2 computes the leveraging coefficient $\alpha_{t}$

$\alpha\leftarrow\delta\cdot\mathrm{sign}(\eta_{\mbox{\tiny init}})$;

$\eta_{\mbox{\tiny new}}\leftarrow\eta(\tilde{\bm{w}}(\alpha),h)$;

if $\left|\eta_{\mbox{\tiny new}}-\eta_{\mbox{\tiny
init}}\right|<|\eta_{\mbox{\tiny init}}|$ then
$\texttt{found$\\_$alpha}\leftarrow\texttt{true}$ else
$\delta\leftarrow\delta/2$;

while $\texttt{found$\\_$alpha}=\texttt{false}$;

Step 3 : $W\leftarrow$ Left Hand Side of (19) (main file) // Step 3 computes
$\overline{W}_{2,t}$

// we can use (19) (main file) because we know $\alpha$

if $W=_{\mbox{\tiny machine}}0$ then

// the LHS of (19) is (machine) 0: just need to find $W$ such that (20) holds
!

$W\leftarrow W_{\mbox{\tiny init}}$;

while $|\alpha|>|\eta_{\mbox{\tiny init}}|/(W\cdot M^{2})$ do $W\leftarrow
W/2$;

endif

Step 4 : $b_{\mbox{\tiny sup}}\leftarrow|\eta_{\mbox{\tiny init}}|/(W\cdot
M^{2})$;// Step 4 computes $\varepsilon_{t}$

$\varepsilon\leftarrow(b_{\mbox{\tiny sup}}/\alpha)-1$;

Return $(\alpha,W,\varepsilon)$;

###  IX.2 Algorithm and implementation of the offset oracle

There exists a very simple trick to get some adequate offset $v$ to satisfy
(22) (main file), explained in Figure 10. In short, we seek the optimally
bended secant and check that the OBI is no more than a required $z$. This can
be done via parsing the interval $[\tilde{e}_{ti},\tilde{e}_{(t-1)i}]$ using
regularly spaced values. If the OBI is too large, we can start again with a
smaller step size. Algorithm oo$\\_{\mbox{\tiny simple}}$ details the key part
of the search.

Figure 10: How to find some $v\in\mathbb{I}_{ti}(z)$: parse the interval
$[\tilde{e}_{ti},\tilde{e}_{(t-1)i}]$ with a regular step $\delta$, seek the
secant with minimal slope (because $\tilde{e}_{ti}<\tilde{e}_{(t-1)i}$;
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 $\delta$ and start the search again. Algorithm 4
oo$\\_{\mbox{\tiny simple}}$($F,\tilde{e}_{t},\tilde{e}_{t-1},z,Z$)

Input loss $F$, two last edges $\tilde{e}_{t},\tilde{e}_{t-1}$, maximal OBI
$z$, precision $Z$.

// in our case,
$\tilde{e}_{t}\leftarrow\tilde{e}_{ti};\tilde{e}_{t-1}\leftarrow\tilde{e}_{(t-1)i};$
(for training example index $i\in[m]$)

Step 1 : // all initializations  $\displaystyle\delta$
$\displaystyle\leftarrow$
$\displaystyle\frac{\tilde{e}_{t-1}-\tilde{e}_{t}}{Z};$ (94) $\displaystyle
z_{c}$ $\displaystyle\leftarrow$ $\displaystyle\tilde{e}_{t}+\delta;$ (95)
$\displaystyle i$ $\displaystyle\leftarrow$ $\displaystyle 0;$ (96)

Step 2 : do

$s_{c}\leftarrow\textsc{slope}(F,\tilde{e}_{t},z_{c})$;

// returns the slope of the secant passing through
$(\tilde{e}_{t},F(\tilde{e}_{t}))$ and $(z_{c},F(z_{c}))$

if
$(i=0)\vee((\delta>0)\wedge(s_{c}<s_{*}))\vee((\delta<0)\wedge(s_{c}>s_{*})))$
then $s_{*}\leftarrow s_{c}$; $z_{*}\leftarrow z_{c}$

endif

$z_{c}\leftarrow z_{c}+\delta$;

$i\leftarrow i+1$;

while $(z_{c}-\tilde{e}_{t})\cdot(z_{c}-\tilde{e}_{t-1})<0$; // checks that
$z_{c}$ is still in the interval

Return $z_{*}-\tilde{e}_{t}$;// this is the offset $v$

###  IX.3 A toy experiments

We provide here a few toy experiments using SecBoost. These are just meant to
display that a 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. (92)) nor
how to choose the best loss given a domain, a problem that is far beyond the
scope of our paper.

In this implementation, the weak learner learns decision trees and we minimize
Matushita’s loss at the leaves of decision trees to learn fixed size trees,
see [34] 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 0, we replace it by a
small random value to prevent the use of derivatives in SecBoost.

|
---|---
Clipped logistic loss, $q=-2$ | Spring loss, $Q=500$
|
Figure 11: Crops of the two losses whose optimization has been experimentally
tested with SecBoost, in addition to the logistic loss. See text for details.

We have investigated three losses. The first is the well known logistic loss:

$\displaystyle F_{\mbox{\tiny{{log}}}}(z)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$
$\displaystyle\log(1+\exp(-z)).$ (97)

The other two are tweaks of the logistic loss. We have investigated a clipped
version of the logistic loss,

$\displaystyle F_{\mbox{\tiny{{cl}}},q}(z)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$
$\displaystyle\min\\{\log(1+\exp(-z)),\log(1+\exp(-q))\\},$ (98)

with $q\in\mathbb{R}$, which clips the logistic loss above a certain value.
This loss is non-convex and non-differentiable, but it is Lipschitz. We have
also investigated a loss we call the spring loss:

$\displaystyle F_{\mbox{\tiny{{sl}}},Q}(z)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{.}}}{{=}}$
$\displaystyle\log(1+\exp(-z))+\frac{1-\sqrt{1-4\left(z_{Q}-[z_{Q}]\right)^{2}}}{Q},$
(99)

with $z_{Q}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}Qz-1/2$ ($[.]$ is the
closest integer), which adds to the logistic loss regularly spaced peaks of
variable width. Being non-convex, non-differentiable, non-Lipschitz, this loss
would escape the framework of the state of the art zeroth-order optimization
techniques. Figure 11 provides a crop of the clipped logistic loss and spring
loss we have used in our test. Notice the “hardness” that the spring loss
intuitively represents for ML.

We provide an experiment on public domain UCI tictactoe [24] (using a 10-fold
stratified cross-validation to estimate test errors). In addition to the three
losses, we have crossed them with several other variables: the size of the
trees (either they have a single internal node = stumps or at most 20 nodes)
and, to give one example of how changing a (key) hyperparameter can change the
result, we have tested for a scale of changes on the initial value of $\delta$
in (92). Finally, we have crossed all these variables with the existence of
symmetric label noise in the training data, following the setup of [38, 40].
We flip each label in the training sample with probability $\eta$. Table 12
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 $\delta$ is too large. Note that the best
initial value for $\delta$ depends on the loss optimized in these experiments:
for $\delta=0.1$, test error from the spring loss decreases much faster than
for the other losses, yet we 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, or a further understanding of
the best formal ways to fix those parameters, all of which are out of the
scope of this paper.

|  $\delta=0.1$ | $\delta=1.0$
---|---|---
$\eta$ | Stumps | Max size = 20  | Stumps | Max size = 20
$0\%$ |  |  |  |
$5\%$ |  |  |  |
$10\%$ |  |  |  |
$20\%$ |  |  |  |
|  |  |  |

Figure 12: Experiments on UCI tictactoe showing estimated test errors after
minimizing each of the three losses we consider, with varying training noise
level $\eta$, max tree size and initial hyperparameter $\delta$ value in (92).
See text.