Boosting with Tempered Exponential Measures
Authors: Richard Nock
Ehsan Amid
Manfred K Warmuth
Venue: NeurIPS 2023 poster (2023)
Keywords: Boosting
optimization
exponential families
TL;DR: The recently introduced Tempered Exponential Measures allow to generalise AdaBoost "above" its classical entropic optimisation framework -- while keeping exponential convergence

Abstract: One of the most popular ML algorithms, AdaBoost, can be
derived from the dual of a relative entropy
minimization problem subject to the fact that the positive weights
on the examples sum to one. Essentially, harder examples receive higher probabilities. We generalize this setup to the recently introduced *tempered
exponential measure*s (TEMs) where normalization is enforced on a specific power of the measure and not the measure itself.
TEMs are indexed by a parameter $t$ and generalize exponential families ($t=1$). Our algorithm, $t$-AdaBoost, recovers AdaBoost as a special case ($t=1$). We show that $t$-AdaBoost retains AdaBoost's celebrated exponential convergence rate when $t\in [0,1)$ while allowing a slight improvement of the rate's hidden constant compared to $t=1$. $t$-AdaBoost partially computes on a generalization of classical arithmetic over the reals and brings notable properties like guaranteed bounded leveraging coefficients for $t\in [0,1)$. From the loss that $t$-AdaBoost minimizes (a generalization of the exponential loss), we show how to derive a new family of *tempered* losses for the induction of domain-partitioning classifiers like decision trees. Crucially, strict properness is ensured for all while their boosting rates span the full known spectrum. Experiments using $t$-AdaBoost+trees display that significant leverage can be achieved by tuning $t$.

Boosting with Tempered Exponential Measures
Richard Nock Google Research ri richardnockkgoogle.cco com
Ehsan Amid Google DeepMind eamidggoogle com
Manfred K. Warmuth Google Research manfred@google. com
Abstract
One of the most popular MI. algorithms, ADABOOST, can be derived from the dual of relative entropy minimization problem subject the fact that the positive weights on the examples sum to one. Essentially, harder examples receive higher probabilities. We generalize this setup to the recently introduced tempered expo- nential measures (TEMS) where normalization is enforced on a specific power of the measure and the measure itself. TEMS
indexed by parameter and generalize exponential families (L = 1). Our algorithm, L-ADA BOOST, recovers ADABOOST special case (t 1). We show that t-ADABOOST retains AD- ABOOST's celebrated exponential convergence rate on margins when t [0. 1) while allowing slight improvement of the rate's hidden constant compared t t 1. BOOST partially computes generalization of classical arithmetic over the reals and brings notable properties like guaranteed bounded leveraging coefficients for f e [o, 1). From the loss that t-ADABoOST minimizes (a general- ization of the exponential loss), we show how to derive new family of tempered losses for the induction of domain-partitioning classifiers like decision trees. Cru- cially, strict properness ensured for all while their boosting rates span the full known spectrum of boosting rates. Experiments using I-ADABOOST display that significant leverage can be achieved by tuning t.
Introduction
30 It efficiently aggregates weak hypotheses into a highly accurate linear combination [10]. The common motivations of boosting algorithms focus on choosing good linear weights (the leveraging coefficients) for combining the weak hypotheses. A dual view of boosting highlights the dual parameters, which are the weights on the examples. These weights define a distribution, and ADABoOST can be viewed as minimizing relative entropy to the last distribution subject to a linear constraint introduced by the current hypothesis 12 For this reason (more
ADABoOST is one of the most popular ML algorithms
2
ADABOOST's weights define an exponential family.
In this paper, we go beyond weighing the examples with a discrete exponential family distribution, relaxing the constraint that the total mass be unit but instead requiring for the measure's 's 1/(2-t) 'th power, where is temperature parameter. Such measures, called tempered exponential measures (TEMS), have been recently introduced 44. Here we apply the discrete version of these TEMS for deriving a novel boosting algorithm called t-ADABOOST. Again the measures are solutions to relative entropy minimization problem, but the relative entropy built from Tsallis entropy and "tempered" by parameter t. As t - 1 TEMs become standard exponential family distributions and our new algorithm merges into ADABOOST. As much as ADA minimizes the exponential loss, t-ADA BOOST minimizes generalization of this loss we denote as the tempered exponential loss.
TEMS were introduced in the context of clustering, where they were shown to improve the robustness to outliers of clustering's 's population minimizers [4. They have also been shown to bring low-level sparsity features to optimal transport (3. Boosting is high-precision machinery: ADABOOST is
known to achieve near-optimal boosting rates under the weak learning assumption M. but it has
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

long been known that numerical issues can derail it, in particular, because of the unbounded weight update rule [1]. So the question of what the TEM setting can bring for boosting is of primordial importance. As we show, E-ADABOOSS can suffer no rate setback as boosting's 8 exponential rate of convergence on margins can preserved for all E [O, 1). Several interesting features emerge: the weight update becomes bounded, margin optimization can be tuned with ż to focus on examples with very low margin and besides linear separators, the algorithm can also learn progressively clipped model Finally, the weight update makes appear new regime whereby weights can "switch off and on an example's ss weight can become zero if too well classified by the current linear separator, and later revert to non-zero if badly classified by next iterate. t-ADABOOST makes use of generalization of classical arithmetic over the reals introduced decades ago [8].
Boosting algorithms for linear models like ADABOOST bring more than just learning good linear separators: it known that (ada)boosting linear models can be used to emulate the training of decision frees (DT) [66. which are models known to lead to some of the best of-the-shelf classifiers when linearly combined (9. Unsurprisingly, the algorithm obtained emulates the classical top-down induction of tree found in major packages like CART 66 and C4.5 123 The loss equivalently minimized, which is, e.g., Matusita's loss for ADABOOST 30 Section 4. is lot more consequen- tial. Contrary to losses for real-valued classification, losses to train DTs rely on the estimates of the posterior learned by the model; they are usually called losses for Class Probability Estimation (CPE (25). The CPE loss is crucial to elicit because (i) is possible to check whether is "good" from the standpoint of properness (Bayes rule is optimal for the loss (28). and (ii) it conditions boosting rates, only a handful of them being known, for the most popular CPE losses
22 31
In this paper, we show that this emulation scheme on f-ADABOOST provides a new family of CPE losses with remarkable constancy with respect to properness: losses are strictly proper (Bayes rule is the sole optimum) for any t E (-20, 2) and proper for = -0. Furthermore, over the range tE [-00, IJ. the range of boosting rates spans the full spectrum of known boosting rates (..
We provide experiments displaying the boosting ability of (-ADABOOST over a range of encom- passing potentially more than the set of values covered by our theory, and highlight the potential of using t as a parameter for efficient tuning the loss (25] Section 8]. Due to lack of space, proofs are relegated to the appendix (APP.). A primer on TEMS is also given in APP., Section
2 Related work
Boosting refers to the ability of an algorithm to combine the outputs of moderately accurate, "weak" hypotheses into highly accurate, "strong" ensemble. Originally, boosting was introduced in the context of Valiant's PAC learning model as a way to circumvent the then-existing amount of
related negative results IO 34). After the first formal proof that boosting is indeed achievable (29). ADABOOST became the first practical and proof-checked boosting algorithm [8] 30). Boosting was thus born in machine learning context, but later on, it also emerged in statistics as a way to learn from class residuals computed using the gradient of the loss 99 21), resulting this time in a flurry of computationally efficient algorithms, still called boosting algorithms, but for which the connection with the original weak/strong learning framework is in general not known.
Our paper draws its boosting connections with ADABOOST's formal lineage. ADA has spurred a long line of work alongside different directions, including statistical consistency [5), noise handling [6). low-resource optimization (22). etc. The starting point of our work is fascinating result in convex optimization establishing a duality between the algorithm and its memory of past iteration's 's performances, a probability distribution of so-called weights over examples (2]. From this standpoint, ADABOOST solves the dual of the optimization of a Bregman divergence (constructed from the negative Shannon entropy as the generator) between weights subject to zero correlation with the last weak classifier's 's performance. As a consequence, weights define an exponential family. Indeed, whenever a relative entropy minimized subject linear constraints, then the solution is member of an exponential family of distributions (see e.g. (2] Section 1) for an axiomatization of exponential families). ADA BOOST's distribution on the examples is member of a discrete exponential family where the training examples are the finite support of the distribution, sufficient statistics are defined from the weak learners, and the leveraging coefficients are the natural parameters. In summary, there
Tradiiionally, clipping sum is done after it has been fully computed. In our case, it is clipped after each new summand is added.

---

is an intimate relationship between boosting s-la-ADABoOSS, exponential families, and Bregman divergences [2 20 and our work "elevates" these methods above exponential families.
Definitions
We define the I-logarithm and I-exponential 17
Chapter 7],
log, (2)
(z' exp, [1+ (1 - t)={+ (0-+)
([=]+ max z)), (1)
where the case 1 is supposed to be the extension by continuity to the log and exp functions, respectively. To preserve the concavity log, and the convexity of exp,, we need > 0. In the general case, also note the asymmetry of the composition: while exp, loge(z) 2, Vt IR, have log, (x), = z for t = (V2 R), but
log, (z) = max 2- (t< 1) and log, exp,(z) min
(t > 1).
Comparisons between vectors and real-valued functions written on vectors are assumed component- wise. We assume /. and define notation 1 = 1/(2 -)). We now define the key set in which model our weights (boldfaces denote vector notation).
Definition 3.1. The co-simplex of RT, Åm is defined as Åm = {qe R -
1 1/ g 1}.
The letters q will be used to denote TEMS in Am while p denote the co-density q or any element of the probability simplex. We define the general tempered relative entropy as
De(q'll4) =
Σ df (log, of log, 9.) logg 9 + log,-1 4s. se[m
(2)
where [m]] - (1,...,..) m]. The tempered relative entropy is a Bregman divergence with convex
generator (=) =/t log, (z) (for e IR) and (p)(2) log, As - 1, Di(g,
becomes the relative entropy with generator up (x) = x log(#)
x.
4 Tempered boosting as tempered entropy projection
We start with a fixed sample 8 ((x;, y/) [m]] where observations æ; lie some domain X and labels y are +1. ADABoOST maintains a distribution p the sample. At the current iteration, this distribution updated based on a current weak hypothesis E IR using an exponential update:
14 Pt exp(-
where u, y.h(m)),
Σg Ps (xp(--1uz))
In 12] this update is motivated as minimizing a relative entropy subject to the constraint that p' is distribution summing and p' u 0. Following this blueprint, we create boosting algorithm maintaining a discrete TEM over the sample which is motivated as a constrained minimization of the tempered relative entropy, with a normalization constraint on the co-simplex of "=
d' = arg
min q A
De(ğ q), with R
(3)
q u u==
We now show that the solution d' is a tempered generalization of ADABOOST's exponential update. Theorem 1. For all & E IR. (2), all solutions
have the form
(log, q: pmu))
(=
9: Ei exp,( (xp:(-puu) with Er b (t [a'-+ b' -1 (4)
Z+
where Z₁ ensures co-simplex normalization of the co-density. Furthermore, the unknown μ satisfies c arg max log, (Z(())) (= arg min Zz(4)),
(5)
3

---

Algorithm 1 (-ADABOOST(4,
Input: / [0, 1]. training sample 8, #iterations J;
Output: classifiers H,, HH (see ());
Step 1 initialize tempered weights: 91 (1/m²*) ). (E Am);
Step 2: for j 1, 1.?,
Step 2.1 get weak classifier h2 weak Jeane_eearergg,..00
Step 2.2 choose weight update coefficient E R;
Step 2.3 Vi [m], for Uja = ya,,( update the tempered weights as
fj Oe exp,( expı(-Mzūı))
9(+1)) 1)
where Zι ||q Zr exp,(-11ı 21)
(8)
Ztj
Step 2.4 choose leveraging coefficient aj
or equivalently is solution the nonlinear equation
d'(x)
Finally, either (i) Rso12) (ii) 0 and q is not collinear to u, then Ze(p) is strictly convex: the solution to (3) is thus unique, and can be found from expression 44) by finding the unique minimizer of (5) or (equivalently) the unique solution (6)
(Proof in APP., Section I1.1 The I-product St, which satisfies exp, b) exp, 8r exp, was introduced in [8]. Collinerrity never happens in ML setting because u contains the edges of weak classifier: > and collinearity would imply that + the weak classifier performs perfect classification, and thus defeats the purpose of training an ensemble. Vt (2),), we have the simplified expression for the normalization coefficient of the TEM and the co-density p' of q':
Z+ |lexp, (log, J1- uu-2)lla 111 F/
8i exP;*
Mug **
with Z - Z //1
(7)
Zi
Tempered boosting for linear classifiers and clipped linear classifiers
Models A model (or classifier) is an element of Rx For any model H, its empirical risk over is Foy (H, = (1/m). E,I # (æx))) where [[-] Iverson's 's bracket [13), is the Boolean value of the inner predicate. We learn linear separators and clipped linear separators. Let (1y)j² 1 be the terms of a series and > 0. The clipped sum of the series is:
(6)
2 jE
min
max
8, UJ
+
Uy "J
(e [--,,]],, for 1,
5)
JE[J-1]
and we define the base case J = 1 by replacing the inner clipped sum with O. Note that clipped summation is con-tmmmutaaive, and is different from clipping in [-ô, ö] the whole sum itself Given set of so-called weak hypotheses h, R and leveraging coefficients aj e IR (for j [J]) the corresponding linear separators and clipped linear separators are
H)(z) = Σ azh((z)
(x)
(6)
Σ (z) jElo
(9)
(-8)
je[M]
Tempered boosting and its general convergence Our algorithm, AAAABBSS,, is presented in Algorithm using presentation conventions from 30) Before analyzing its convergence, several properties to be noted for t-OST: first, it keeps the appealing property, introduced by ADABoOS that examples receiving the wrong class by the current weak classifier are reweighted
Fix for example -1, 6 3 = 2. For
b. the clipped sum is 2 = -1 + 3, but for
b, U2 the clipped becomes = 2 1.

---

higher (if μ4 > 0). Second, the leveraging coefficients for weak classifiers in the final classifier (ays) are not the same as the ones used update the weights (12s), unless of the definition of exp, (T). if < 1, tempered weights can switch off and on, í.e., become 0 if an example is "too well classified" and then revert back to being
Third and last, because
if the example becomes wrongly classified by the current weak classifier (if Hij > 0). To take into account those zeroing weights, we denote [ml] = {i qjz 03 and mj- = Card([ml)) (vj E [J] and Card denotes the cardinal). Let R3- = x ( (z:)1/qj4 and o] = max [mm)] (ych (2000-//5) R/R/ //R//100) noting that oj is homogeneous to tempered weight.
worth
Theorem 2. At iteration j. define the weight function dfz = 43s if [m]] and of otherwise; set
Pj (1 m)aaj
Σ (asnhy(a)) (E [=]-1,1]). ie(m)
(10)
In algorithm t-ADABOOST, consider the choices (with the convention
I Uk = 1)
j-1
1-t
1 B1 Rj
llgg
1 Pj M Ps. p.))
0g
t*
Zzk
(11)
where My(a,b) b) = ((a" + b/) is the q-power mean. Then for any H E {H,, H its empirical risk is upperbounded as:
Fo/ (H,8) &
11 j=1
2
2-1
11 f=1
(1
[1+m)] 1m, 1)) Ke(ps)
K2(=) = M1- 2, 1 (12)
2²
(Proof in APP., Section II.2 We jointly comment t-ADABOOST and Theorem in two parts.
2 to its convergence analysis: t-ADABOOST converges to ADABOOST as presented in (30 Figure IJ: the tempered simplex be- comes the probability simplex, &, converges to regular multiplication, weight update (8) becomes ADABOOST's, 0 - (4y in (T] and finally the expression of (4 converges to ADA BOOST's leverag- ing coefficient in 30 (lim--1 M1-1(a, b) = Vab). Even guarantee
Case t - 1 t-ADABOOST converges to ADABOOST and Theorem
(12 converges to ADABOOST's popular guarantee of (30 Corollary 1] (lim;-1 Ke(z) v1 2², m = 0), Also, in this case, we learn only the unclipped classifier since lim,-1 Hf H,
Case 1: Let first comment on the convergence rate. The proof of Theorem shows that K2(2) & exp(-22/(21+)) Suppose there no weight switching, so m Vj (see Section 7) and, as in the boosting model, suppose there exists 7 > such that |pyl > 7, Vj. Then t- ADABOOST is guaranteed to attain empirical risk below some 0 after a number of iterations equal to = (2I*/7²) log(1/e). &* being an increasing function of E [0. 1]. we see that L- ADABOOST is able to slightly improve upon ADABOOST's celebrated rate [32] However, t* 1/2 for = 0 so the improvement is just on the hidden constant. This analysis is suited for small values of |py] and does not reveal an interesting phenomenon for better weak hypotheses. Figure compares (=) curves (K) = lim,-1 K=(z) = vI 11 2² for ADABOOST,
(30 Corollary IJ). showing
the case 1 < 1 can be substantially better, especially when weak hypotheses are not "too weak". If m! > 0, switching weights can impede our convergence analysis, though exponential convergence is
always possible if m m/q; 22-t is small enough; also, when it is not, we may in fact have converged to good model (see APP., Remark A good criterion to train weak hypotheses is then the optimization of the edge Pj. thus using d' normalized in the simplex. Other key features of t- ADAAAAASSS are as follows. First, the weight update and leveraging coefficients of weak classifiers are bounded because |p51 < (1 t)) (APP., Lemma H) (this is not the case for t - 17). This guarantees that new weights are bounded before normalization (unlike for /. 1 1-). Second, we remark that μj * aj if t # Factor m!! 1- is added for convergence analysis purposes: we can discard it train the unclipped classifier: it does not change its empirical risk. This is, however, different for factor
[ Ze: from 12 conclude that this is an indication of how well the past ensemble performs.
5

---

1=1 (AdaBoost)
0.8
0.6
1=0
0.1
0.4
0.05
0.2
0.98
-0.75
-0.5
-0.25
0.25
0.5
0.75
Figure I: Plot of (z)=) in (12) L E [0. 1] (the smaller, the better for convergence).
As it gets better and better, progressively dampens the leverage of the next weak classifiers, phenomenon that does not occur in boosting, where an excellent weak hypothesis on the current weights can have a leveraging coefficient so large that it wipes out the classification of the past ones. This can be useful to control numerical instabilities.
Extension margins A key property of boosting algorithms like ADABOOST to be able to boost not just the empirical risk but more generally margins [9 30), where margin integrates both the accuracy of label prediction but also the confidence in prediction (say HD. We generalize the margin notion of [19] to the tempered arithmetic and let (1 y), H) = tanh, (z) denote the margin of on example (æ. y), where (anh,(=) (1 (-p,(-22))) 221))(1 + exp,( (-2)) [-1, 1])
is the tempered hyperbolic tangent. The objective of minimizing the empirical risk is generalized to minimizing the margin risk, FH,
(1/m) [,, M/), H) < 0]. where 0 (-1, 1). Guarantees on the empirical risk are guarantees on the margin risk for 0 0 only. In just a few steps, we can generalize Theorem to all 0 E (-1, 1). For space reason, we state the core part of the generalization, from which extending
generalization of Theorem i simple.
Theorem 3. For any f E (-1,1) and t E [o, 11, the guarantee of algorithmm t- ADA in Theorem 2 extends the margin risk, with notations from Theorem [
via:
(H, &
1 (1-0)
11 j=1
(13)
At high level, t-ADABOOST brings similar margin maximization properties as ADABOOST. Digging a bit in (13) reveals an interesting phenomenon for t on how margins are optimized compared to /. 1. Pick 0 < O, we focus those examples for which the classifier H has high confidence in its wrong classification. In this case, factor ((1 + 0)/(1 - 2-) increasing function of / [0. 1] (and this pattern is reversed for 0 > 0). In words, the smaller we pick E [0, 1] and the better is the bound in [13, suggesting increased "focus" of t-ADABoOST on increasing the margins of examples with low negative margin (e.g. the most difficult ones) compared to the case
(Proof in APP., Section I1.3
The tempered exponential loss In the same way ADABOOST introduced the now famous exponential loss, (12 recommends to minimize the normalization coefficient, following 77.
(M) = |lex,, (log, q, - μ u,) l (with uys y,hy(z:)).
(14)
We cannot easily unravel the normalization coefficient to make appear an equivalent generalization of the exponential loss, unless we make several assumptions, one being max, (mx)) is small enough for any j [J]. In this case, end up with equivalent criterion to minimize which looks like
F) =
1 m
Σ 2- (-,,H((),,))
(15)

---

where we have absorbed in H the factor m 1-1* appearing in the exp, (scaling H by positive value does not change its empirical risk). This defines generalization of the exponential loss which we call the tempered exponential loss. Notice that one can choose to minimize F₂ H, 8) disregarding any constraint on |
6 A broad family of boosting-compliann proper losses for decision trees
Losses for class probability estimation When it comes to tabular data, it has long been known that some of the best models to linearly combine with boosting decision trees (DT, (9).. Decision trees, like other domain- domain-partitionn partitioning classifiers, are not trained by minimizing a surrogate loss defined over
real-valued predictions, but defined over class probability estimation (CPE, (26)). those estimators
being posterior estimation computed at the leaves. Let us introduce a few definitions for those. A
CPE loss é: [-1,1) x [0. 1] - is
E(y.u) = ly= 1] (1()) + Iv = = | -
(16)
Functions e, f-1 are called partial losses. The pointwise conditional risk of local guess u e [0, 1] with respect to a ground truth e [0, 1] is:
L(u, v) = V- (u) + (1-0)-
(17)
[0, 1]. L(u,t) inf,, L (u, v),, and strietly proper iff u = e is the sole minimizer [26]. The (pointwise) Bayes risk is L(v) inf [u, v). The lgg/eooss-entrooylloss,,, square-loss, Matusita loss examples of CPE losses. One then trains DT minimizing the expectation of this loss over leaves' posteriors, E3 [[xA)] px being the local proportion of positive examples at leaf X or equivalently, the local posterior.
A loss is proper iff for any ground truth
Deriving CPE losses from (ada Jbossinng Recently, it was shown how to derive a general way CPE loss to train DT from the minimization of surrogate loss with boosting algorithm [16). In case, the surrogate would be Zz, (14) and the boosting algorithm, t-ADABOOST. The principle is simple and fits in four steps: (i) show that a DT can equivalently perform simple linear classifications, (ii) use a weak learner that designs splits and the boosting algorithm to fit the leveraging coefficient and compute those in closed form, (iii) simplify the expression of the loss using those, (iv) show that the expression simplified is, in fact, CPE loss. To get (i), we remark that a DT contains a tree (graph). One can associate to each node a real value. To classify an observation, we sum all reals from the root to leaf and decide real-valued predictor. Suppose we are at a leaf. What kind of weak hypotheses can create splits "in disguise"? Those can be of the form
the class based on the sign of the prediction, just like for any
hx(x) I [m az] bj.
by. e
where the observation variable Iy is assumed real valued for simplicity and the test [IA >> a,] splits the leaf's domain in two non-empty subsets. This creates half of the split. (x) = [ a,] -b; creates the other half of the split. Remarkably hy satisfies the weak learning assumption iff h, does [6] So we get the split design part of (ii). We compute the leveraging coefficients at the new leaves from the surrogate's 's minimization/ boosting algorithm, end up with new real predictions the new leaves (instead of the original bj. -b;), push those predictions in the surrogate loss for (iii), simplify it and, quite remarkably end up with loss of the form E, [px)] where L turns to be the pointwise Bayes risk L of proper loss [I6] (notation from 26)).
In the case of [16), it is, in fact, granted that we end up with such "nice" CPE loss because of the choice of the surrogates at the start. In our case, however, nothing grants this a priori if we start from the tempered exponential loss Zez (14) so it is legitimate to wonder whether such a chain of derivations (summarized) can happen to reverse engineer an interesting CPE loss:
Zig 1 3 (1) 2. e() (proper ? strictly proper for which ts ?....)
(18)
When such complete derivation happens until the partial losses L l_ and their properties, we shall write that minimizing Zn, elicits the corresponding loss and partial losses.
Theorem 4. Minimizing Zoz elicits the CPE loss we define as the tempered loss, with partial losses:
2-1
(() ( u)
1-
(0)( =f) u). (t 21)
(19)
The tempered loss is symmetric, differentiable, strictly for t (-00, 2) and proper -00.
7

---

perr (not clipped)
perr (clipped)
min weight
max weight
0,0002
0.21
0.0022
abalone. 1. D.00g
2200
10,00015
00001
2.0
0.0000
0.207
0.000
0.200
0.806
tx124
0.2044
2200
2.204
0.0000
#0203
Adbioood
29T
0.185
0:004
6.77
0.9
0.8
0.9
0.000
09
[gear, (.25 0.66
0:16
0,0000
B3005
0.139
0.189
0.0002
0.149
04
0.15
0.6
0.000
0. 0.0015
08
0:170
9.74
Adidicosi (PP
1.1
2:178
0.58
Kialosal (-11))
0.092220
6.093328
0.000331
2.002222
Adsesci: 2-1
T 200011
0.00011
0.00011
Ababbomt (191
adult. 0.6,30
192
0.8
08g
2.122
2:103
0:17
0.0
10,0001
00002200
000007
0
0.
20055
00
0:100
8.184
5,0000
2162
10 12 11
10 13 14
10 1012211 14
10 14
2.30
Table 1: Experiments on (rows), displaying from left to right the estimated true eπтоr of non- con-clipped and clipped models, and the min and max codensity weights. These domains were chosen to give an example of three different situations: small values of t perform well (abalone), the best performance is achieved by the largest t (e.g. ADABOOST, qsar), and the worst performance achieved by the largest (adult). Topmost row is without noise (1) 0) while the others are with 10% training noise; t scale displayed with varying color and width (colormap indicated on each plot). Averages shown for readability: see Table for exhaustive statistical tests.
comparing with ADABOOST
1, bullets) on three domains
Differentiability means the partial losses are differentiable, and symmetry follows from the re- lationship between partial losses [20] (the proof, in APP., Section [I.4] derives the infinite case, e 00) (u) 2 [u & 1/2l) Let us explicit the Bayes risk of the tempered loss and a key property.
Lemma 1. The Bayes risk of the tempered loss is (M₂ defined in Theorem 2
2u(1 - u)
I. (w)
(20)
M1 M u)
and it satisfies Vu E [0, 1]. V2 E [2- minfu, 1 u), 11, 3t 1- 2] such that I (u)
Lemma] I whose proof is trivial, allows to show key boosting result: t = 1 retrieves Matusita's loss, for which a near-optimal boosting rate known III while = 00 retrieves the empirical risk, which yields the worst possible guarantee [I]] In between, have, for example, CART's Gini criterion for t = 0, which yields an intermediate boosting guarantee. Continuity with respect to t of the Bayes risks in between the empirical risk and Matusita' loss means the boosting ranges of the tempered loss cover the full known spectrum of boosting rates for t E [-o0, 1]. We know of no (differentiable and) proper CPE loss with such coverage. Note that (i) this non-constructive result as we do not associate a specific for a specific rate, and (ii) the state-of-the-a boosting rates for DT induction do not seem to cover the case E 21, thus left as open question.
7 Experiments
We have performed experiments on a testbed 10 UCI domains, whose details are given APP, (Sec- tion A3 Experiments were carried out using 10-fold stratified cross- validaaiio procedure.
8

---

To compare t- ADADBOSST with ADABOOST, we ran t- t-ADABBOSS with first range of values of t E {0.0, 0.4, 0.6, 0.8, 0.9). This is in the range of values covered by our convergence result for linear separators in Theorem 2 Our results on decision tree induction cover much wider range, in particular for / E (1. To assess whether this can be an interesting range to study, we added t = 1.1 to the set of tested Ê values. When t > 1, some extra care is to be put into computations because the weight update becomes unbounded, in a way that is worse than ADABOOST. Indeed, as can be seen from (8) if 113thh (x:)) & -1/(t- 1) (the example is badly classified by the current weak hypothesis, assuming wlog 24 > 0), the weight becomes infinity before renormalization. In our experiments, picking a value of f close to 2 clearly shows this problem, so to be able to still explore whether t >> 1 can be useful, we picked a value close to 1, namely = 1.1, and checked that in our experiments this produced no such numerical issue. We also considered training clipped and not clipped models.
All boosting models were trained for a number of J - 20 decision trees (The appendix provides experiments on training bigger sets). Each decision tree is induced using the tempered loss with the corresponding value of (see Theorem[4) following the classical top-down template, which consists in growing the current heaviest leaf in the tree and picking the best split for the leaf chosen. We implemented b-ADABOOST exactly as in Section [S] including computing leveraging coefficients as suggested. Thus, we do not scale models. More details are provided in the appendix. In our experiments, we also included experiments [T] and fine-tuned more recently [16]. the fact that a convex booster's s model is the weakest link when it has to deal with noise in training data. This is important task because while the tempered exponential loss is convex, it does not fit into the blueprint loss of 15 Definition 1] because it is not C¹ if 1. One might thus wonder how t-ADABOOST behaves when training data is affected by noise. Letting denote the proportion of noisy data in the training sample, we tried E {0.0, 0.1) (The appendix provides experiments on more noise levels). We follow the noise model of [1] and thus independently flip the true label of each example with probability y).
phenomenon highlighted more than a decade ago
For each run, we recorded the average test error and the average maximum and minimum co-density weight. Table presennss a subset of the results obtained on three domains. Table 2 presents a more synthetic view in terms of statistical significance of the results for t # 1 vs. t 1 (ADABoOST). The table reports only results for t ? 0.6 for synthesis purposes. Values t < 0.6 performed on average slightly worse than the others but some domains, the example of abalone suggests in Table 2 (the plots include all values of tested in [0. 1.1]), we clearly got above-par results for such small values of t, both in terms of final test error but also fast early convergence to low test error. This comment can be generalized to all values tf
The weights reveal interesting patterns as well. First, perhaps surprisingly, we never encountered the case where weights switch off, regardless of the value of I. The average minimum weight curves of Table[[]eneraalin to all our tests (see the appendix). This does not rule out the fact that boosting for much longer number of iterations might lead to weights switching off/on, but the fact that this does not happen at least early during boosting probably comes from the fact that the leveraging coefficients for weights (f.) are bounded. Furthermore, their maximal absolute value is all the smaller as f decreases to O. Second, there is a pattern that also repeats the maximum weights, not all domains but on a large majority of them and can be seen in abalone and adult in Table [ the maximum weight of ADABOOS tends to increase much more rapidly compared to A-ADABOO latter case, we almost systematically observe that the maximum weight tends to be upperbounded, which is not the case for ADABOOST (the growth of the maximal weight looks almost linear). Having bounded weights could be of help to handle numerical issues of (ada)boosting 14].
with 1. In the
Our experiments certainly confirm the boosting nature of t- ADABBOST if we compare its convergence to that of ADABOOST: more often than not, it is in fact comparable to that of ADABOOST. While this applies broadly for t > 0.6, we observed examples where much smaller values (even = 0.0) could yield such fast convergence. Importantly, this applies to clipped models as well and it is important to notice because it means attaining low "boosted" error does not come the price of learning models with large range. This is an interesting property: for L = 0.0, we would be guaranteed that the computation of the elipped prediction is always in [-1, 1J. Generalizing our comment on small values of above, we observed that an efficient tuning algorithm for l could be able to get very substantial leverage over ADA BooST. Table 2 was crafted for standard limit p-val of 0. and "blurs" the best results that can be obtained. On several domains (winered, abalone, eeg, credi tcard, adult), applicable p-vauues for which we would conclude that some * performs better than t drop in

---

1
0.0
0.1
t
0.6
0.8
0.9
1.1
0.6
0.8
0.9
1.1
[clipped]
0
1
0
0
0
0
1
0
1
0
0
#better
2
3
1
2
1
3
1
1
2
2
1
#equivalent
5
5
6
6
7
7
6
7
4
8
8
7
8
9
8
10
# worse
2
3
2
2
4
3
5
1
2
Table 2: Outcomes of student paired I-tests over 10 UCI domains, with training noise v {0.0, 0.1}, for / E (0.6, 0.8, 0.9, 1.0, 1.13 and with / without clipped models. For each triple (n, 4, [clipped]], ) we give the number of domains for which the corresponding setting of L-ADABOOST is statistically better than ADABOOST (O better), the number for which it is statistically worse (#wors) and the number for which we cannot reject the assumption of identical performances. Threshold p-val = 0.1.
between 7E and 0.05. Unsurprisingly, ADABOOST also manages to beat significantly alternative values of in several cases, Our experiments with training noise (1) = 0.1) go in the same direction. Looking at Table one could eventually be tempted conclude that t slightly smaller than 1.0 may be a better choice than adaboosting (t = 1), as suggested by our results for t = 0.9, but we do not think this produces general "rule-of-thumb There is also no apparent noise-dependent" pattern that would obviously separate the cases t < from t = 1 even when the tempered exponential loss does not to [5] 's theory. Finally, looking at the results for > 1 also yields the same basic conclusions, which suggests that boosting can be attainable outside the range covered by our theory (in particular Theorem 2)
All this brings us to the experimental conclusion that the question does not reside on opposing the case the case / 1. Rather, our experiments suggest pretty much like our theory does that the actual question resides in how to efficiently learn & on a domain-dependent basis. Our experiments indeed demonstrate that substantial gains could be obtained, to handle overfitting or noise.
8 Discussion, limitations and conclusion
ADA BOASOOST is one of the original and simplest Boosting algorithms. In this paper we generalized ADA BoOST maintaining tempered measure over the examples by minimizing tempered relative entropy. We kept the setup as simple as possible and therefore focused on generalizing ADABOOST, However more advanced boosting algorithms have been designed based on relative entropy minimization subject to linear constraints. There are versions that constrain the edges of all past hypotheses to be zero (36). Also, when the maximum margin of the game is larger than zero, then ADABOOST cycles over non-optimal solutions (27). Later Boosting algorithms provably optimize the margin of the solution by adjusting the constraint value on the dual edge away from zero (see e.g. 24). Finally, the ELRP- Boost algorithm optimizes trade off between relative entropy and the edge 35). We conjecture that all of these orthogonal direction have generalizations to the tempered case as well and are worth exploring.
These are theoretical directions that, if successful, would contribute bring more tools the design of rigorous boosting algorithms. This is important because boosting suffers several impediments, not all of which we have mentioned: for example, to get statistical consistency for ADABOOST, is known that early stopping is mandatory (5). More generally, Lon-Liischitz losses like the exponential loss seem to be harder handle compared to Lipschitz losses 333 (but they yield in general better convergence rates). The validity of the weak learning assumption of boosting can also be discussed, in particular regarding the negative result of [I5] which advocates, beyond just better (aoasioos for boosting for more classes of models/ architectures [16]. Alongside this direction, we feel that our experiments on noise handling give a preliminary account of the fact that there no "one / fits all" case, but a much more in depth analysis is required to elicit/ / tune a "good" L. This is a crucial issue for noise handling [16, but as we explain in Section 7 this could bring benefits in much wider contexts as well.
10

---

Acknowledgments
The authors thank the reviewers for numerous comments that helped improving the paper's content.
References
[1] N. Alon, A. Gonen, E. Hazan, and Moran. Boosting simple learners. STOC'21, 2021.
[2] S.-I. Amari, Information Geometry and Its Applications. Springer-Veriie Berlin, 2016.
[3] E. Amid, F. Nielsen, R. Nock, and M.-K. Warmuth. Optimal transport with tempered exponential measures. CoRR, abs/2309.0400 0.001, 2023.
[4] E. Amid, Nock, and M.-K. Warmuth, Clustering above exponential families with tempered exponential measures. In 26th AISTATS, 2023.
[5] P. Bartlett and M. Traskin. Adaboost is consistent. In NIPS*19, 2006.
[6] I.. Breiman, H. Freidman, R. A. Olshen, and C. J. Stone. Classification and regression trees. Wadsworth, 1984.
[7] M. Collins, R. Schapire, and Y. Singer. Logistic regression, adaboost and Bregman distances. In Proc. of the 13 th International Conference on Computational Learning Theory. pages 158-169, 2000.
[8] Y. Freund and R. E. Schapire. A Decision-Theoreete generalization of on-line learning and an application to Boosting. Comp. Syst. Sc., 55:1 19-1,9, 1997.
[9] Friedman, Hastie, and Tibshirani. Additive Logistic Regression a Statistical View of Boosting. Ann. of Stat., 28:337-374, 2000.
[10] M.J. Kearns. Thoughts on hypothesis boosting, 1988. ML class project.
[11] M.J. Kearns and Y. Mansour. On the boosting ability of top-down decision tree learning algorithms. In Proc. of the 28 ACM STOC, pages 459-468, 1996.
[12] J. Kivinen and M.-K. Warmuth. Boosting entropy projection. In COLT'99, pages 134-144,
1999.
[13] D.-E. Knuth. Two notes on notation. The American Mathematical Monthly, 99(5):403 422, 1992.
[14] R. Kohavi. Improving accuracy by voting classification algorithms: Boosting, bagging, and
variants. In Workshop on Computation-Intensse Machine Learning Techniques, 1998.
[15] P.-.. Long and R.-A. Servedio. Random classification noise defeats all convex potential boosters. MLJ, 78(3):287-300 2010.
[16] Y. Mansour, R. Nock, and R.-C. Williamson. Random classification noise does not defcat all convex potential boosters irrespective of model choice. In 40th ICML, 2023.
[17] J. Naudts. Generalized thermostatistics. Springer, 2011.
[18] L. Nivanen, A. Le Méhauté, and Q.-.. Wang. Generalized algebra within nonextensive statisties. Reports on Mathematical Physies, 52:437-444, 2003.
[19] R. Nock and F. Nielsen. A Real Generalization of discrete AdaBoost. Artificial Intelligence, 171:25-41 41, 2007.
[20] R. Nock and F. Nielsen. On the efficient minimization of Elassification-caiibuud surrogates. In NIPS#2/, pages 1201-1208, 2008.
[21] R. Nock and F. Nielsen. The phylogenetic tree of Boosting has bushy carriage but a single trunk. PNAS, 11:86922-8693, 2020.
[22] R. Nock and R.-C. Williamson. Lossless or quantized boosting with integer arithmetic. In 36th ICML, pages 4829-4834 2019.
[23] J. R. Quinlan. C4.5: programs for machine learning. Morgan Kaufmann, 1993,
[24] G. Rätsch and M.-K. Warmuth. Efficient margin maximizing with boosting. JMLR, pages 2131-2152, december 2005.
[25] M.-D. Reid and R.-C. Williamson. Composite binary losses. JMLR, 11:2387-2422, 2010.

---

[26] M.-D. Reid and R.-C. Williamson. Information, divergence and risk for binary experiments. JMLR, 12:731-817, 2011.
[27] C. Rudin, Daubechies, and R.-E. Schapire. Dynamics of adaboost: cyclic behavior and convergence of margins. JMLR, pages 1557-1595, December 2004.
[28] L.-J. Savage. Elicitation of personal probabilities and expectations. J. of the Am. Stat. Assoc., pages 783-801, 1971.
[29] R. E. Schapire. The strength of weak learnability. MLJ, pages 197-227, 1990.
[30] R. E. Schapire and Y. Singer. Improved boosting algorithms using confidence-rated predictions.
MLJ, 37:297-336, 1999.
[31] T. Sypherd, R. Nock, and L. Sankar. Being properly improper. In 39th ICML, 2022.
[32] M. Telgarsky. A primal-dum convergence analysis of boosting. JMLR, 13:561-606, 2012.
[33] M. Telgarsky. Boosting with the logistic loss is consistent. In 26 th COLT, pages 91 911-9
2013.
[34] L. G. Valiant. A theory of the learnable. Communications of the ACM, 27:1 1142 1984.
[35] M.-K. Warmuth, K.-A. Glocer, and S. S.-V.N, Vishwanathan. Entropy regularized LPBoost, In Algorithmic Learning Theory, pages 256-271. Springer Berlin Heidelberg, 2008.
[36] M.-K. Warmuth, Liao, and G. Rätsch. Totally corrective boosting algorithms that maximize the margin. In icml '06: proceedings of the 23rd international conference on machine learning. pages 1001-1008, 2006.
12

---

Appendix
Abstract
This is the Appendix to Paper "Boosting with Tempered Exponential Measures". To differentiate with the numberings in the main file, the numbering of Theorems, Lemmata, Definitions is etter- (A, .....
Table of contents
A short primer Tempered Exponential Measures
Pg 14
Supplementary material on proofs
Pg
15
Proof of Theorem
Pg
15
-
Proof of Theorem
Pg
T8
Proof of Theorem
P
Proof of Theorem
Pg
Supplementary material on experiments
13

---

I A short primer on Tempered Exponential Measures
We describe here the minimal amount of material necessary to understand how our approach to boosting connects to these measures. We refer to
4 for more details. With a slight abuse of notation,
we define the perspective transforms (log,) (()) 12o.: and (cxp,)" "()) = t txxxx (2/t*).
Recall that t = 1/(2- t).
Definition A. [4] A tempered exponential measure (TEM) family is a set of unnormalized densities in which each element admits the following canonical expression:
where 0 is the element's 's natural parameter, (p(x: is the sufficient statistics and (ASiD=
expx (0' (p(x)) exp, (G)
a-b
11b)
Qrja( (x)
cxp, (00T)(())))) b G(())
(21)
1 (+(1- (1- - t)b
G.(0)
(loge)* (exp,) (((=)))
is the (convex) cumulant, & being base measure (implicit).
Except for = 1 (which reduces a TEM family to a classical exponential family), the total mass of (but it has an elegant closed form expression 44). However, the exponentiated q:jo does sum to In the discrete case, this justifies extending the classical simplex to what we denote as the co-simplex.
1/t*
Definition B. The co-simplex of IR", Åm defined as Åm E
1 2// = 1}.
The connection between t-ADABOOST'S update and TEM's is immediate from the equation's 's update in MF). We can show that Åm also be represented TEMs. Lemma A. Åm famet of tempered exponential measures.
Proof. We proceed in Section 2.2.2] for exponential families: let q e Åm. which we write
(())
= Σ qi Ii li= n1], E [m].
(22)
xE|m]
[<] the Iverson bracket [3]. takes value if Boolean predicate a true (and 0 otherwise). We create natural parameters and the cumulant,
0, log, l: i [m 1] GG(()) log,
4m
4m
and end up with (22 also matching the atom mass function
exp, (Eietm-1) 0, [ m]
((n)
exp, (.)
which clearly defines a tempered exponential measure over [m]. This ends the proof of Lemma
14

---

II Supplementary material on proofs
II.1 Proof of Theorem
To improve readability, remove dependency in é in normalization coefficient Z. We use notations from 4 proof of Theorem 3.2] and denote the Lagrangian
ΣΦa 1/1* -1
-
-
& = =A(ql4) + A
nith + μ Σ qruss
(23)
which yields 2L/00; log, Ø: - log, Ag; (absorbing factor 1 in 14),
+ pui (A absorbs factor 2 2 (), and, rearranging
+ (1- ()))
u 1+ (1 (log, qi pume), Vi [m]]
(24)
We see that o 11((1-0) t) otherwise the Lagrangian drops its dependence in the unknown. In fact, the solution necessarily has + (1 t) > O. To see this, we distinguish two cases: (i) some uk O, then since log, q) -1/(1
there would be solution (2 if 1 (1 t) 0 because of the KKT conditions v4 2 0, vi [m]; (ii) otherwise, if all u * O. Ak E [m]] then there must be two coordinates of different signs otherwise there is no solution to problem (3) (main file, we must have indeed ? > 0 because of the co-simplex constraint). Thus, there exists at least one coordinate & [m]] for which -(1 puy and since log, Qu 11((1 (definition of log,) and Vi > 0 (KKT conditions), the RHS of (24) for i is > 0. preventing + (1 - t) < in the
LHS.
thus have 1+ (+-1)))A > 0. The KKT conditions (M, 3 0, v.q. = 0, e [m]] yield the following:
1 + (1 1) (log, di juu) imply vs = 0 and (1 ()og di - pmus) < 0 imply -.- 0 so
we get the necessary form for the optimum:
exp, (log, qi pm))))
q.
exp;
9 8y exp, (-pA,)))
(25)
Ze
where À Z, exp, ensures normalisation for the co-density. Note that we have simplified expression for the co-density:
Pji 8₁* cxP,4 (-pu4(uuut/t" pu,/t*)
(26)
Z
with 2 = 221 E, Psi Oi* exp,e (=puttt) For the analytic form in
25
can simplify the
Lagrangian to a dual form that depends on μ solely:
D(w) ((q()))g)) +
(27)
The proof of (5) (main file) is based on a key Lemma.
Lemma B. For any q having form 25 such that q qou u
0, D(u) - llog, Zz()).
Proof. For any having form 25 denote
[m] =
(e q. * 0).
(28)
15

---

We first compute (still using À log, Ze( for short):
A
Σ
log, di
(exp, (log, qi puu;))
Z loge
exp; x
[m]+
Σ %
1
1 + (1 (log 95 pms)))
-11
1
1 1-t
1 (1 - t)
[m]
1-1 - (1 - 1)
q:
1 (1 t
XE [m]
ie [m *
1
Σ
Lilli (1- (1-t)(1 + (1- -)))
q:
1 (1 x)
1
ve(m)
de te[m)+
(1 (1-t) (1 +) u
Σ
q
(29)
1 1 (1 x
t
[m]]
sel [m
C
Remark that in the last identity, we have put back summations over the complete set [m] of indices. We note that B because q u We then remark that without replacing the expression of q. we have in general for any q E Åm:
E =
Σ
d (loge q: - loge gi)
se
[m]
Σ
(0) 1- 1)
--- -11--11)
d
t
ve m
2-
Σ q 1-t
4:
ie[m)
1
Σ
ब.
sE(ms
and we can check that for any q. E replacement q by its expression:
Å m. E = A(qlg). We then develop A(ğllg) with partial
A(ālg)
A
Σ qe log, di
Σ
Σ qi
1 1
C
Σ 7:91
1-t
1
(
11 (1 t)A -1) Σ gn!
1
1-t
Σ
9:9. 1-
1+ (1 t)x
(1-(1-)) A(q))))
(1 1)X
Rearranging gives that for any q, E Åm such that (i) q has the form 25) for some E R and (ii)
uu= 0,
A(qlg) = -
log, (Z)),
16

---

as claimed. This ends the proof of Lemma B
We thus get from the definition of the dual that μ arg max have the explicit form for Z,
log, Zo(H) arg min (z)). We
Z((p) =
Σ expt (log, 9i pmu;)
Σ
exp; ? 2-1 (log, 9: - prws)
de Ne[m)
where [m] is defined in 28
We remark that the last expression is differentiable in μa, and get
Z((A) =
Σ
exp; 2- (log, - pmsss
2 - t
88 {m(m]
(2 - t)
Σ
exp;
--t (log, di pas) expx (loge qi puu))
[m] s
Z
Σ
exp, (log, q: puu) u4
ie [m *
-7:- Σ
g:us
s [m]
- - Σ g:uls
r5(m]
- 4/ q u,
(30)
SO
a log, (Z;)
-Z," %
Ōp
q(1) u.
and we get that any critical point of (z) satisfies q(u) Tu = O. A sufficient condition to have just one critical point, being the minimum sought is the striet convexity of Z((p). The next Lemma provides the proof that is for all t > 0.
Lemma C. (m) > t ( T u)
Proof. After simplifications, we have
77-21. 2t, Z = (1-1)
Σ ic(ml
exp, (loge qi - pms) us
(31)
+
Σ
exp; 2-1 (log, 9: pmi))
Σ
expi (log, q: pma) ut
(32)
[mm
[e[m]
= (t - 1) QiQuuu +
(33)
[m)
[.
where we have let Qi = exp; (log, d: pmu)) > 0. Since a² + 62 > 2ab, we note that for any * k.
2 + Φ '/ > 27 - Quuuu
=2Q,Quuue
(34)
17

---

so we split 33 in two terms and get
2 26 z
(1- 1)
Σ
Qu Σ
[m[m]
im/m
Σ
2(t 1)QiQuum +
Σ
Q + Q%-
k,ke (m] lick
Ak([m]
1.
Q 2
m
Σ
2(t - QuQiQuu
E
Qi Q0
kk[mm].sc kick
Akelmaack
Qu
Σ
QiQuuen
(35)
mm(m]
=
exp, (loge 0i (res)) 14
t (q u)²
(36)
where we have used
34
in
35
Since (((n) > O, we get the statement of Lemma
C after
reorganising (36).
Lemma shows the strict convexity of (() for any t > 0. The case 0 follows by direct differentiation: we get after simplification
(1) (Zie(m) ui)) (Ziefmp(ai pm)))) (Eie(m peus)
[Eremm]9: pu,)))
Cauchy-Schwartz inequality allows to conclude that (() and in fact 0 unless ğ collinear to u. This completes the proof of Theorem
I1.2 Proof of Theorem
The proof involves several arguments, organized into several subsections. Some general than what is strictly needed for the proof of the Theorem, on purpose.
IIII1..11 Clipped summations
For any 8 O, we define clipped summations of the sequence of ordered elements U1, U2 ... Uyt
J >>> 1,
J-1 Uy
J-1
(8) Σ
min
+
(8)
Σ
Σe U max Bs + (-8)
Σ Uj 8 (37)
(-8)
/=1
and the base case (J 1) is obtained by replacing the inner sum by 0. We also define the doubly clipped summation:
J-1
(8)
min
UJ +
(6)
Σ 0g,8
8
(-8)
(-6) j-1
with the same convention for the base case. We prove series of simple but useful properties of the clipped summation.
Lemma D. The following properties hold true for clipped summation:
1. (doubly) clipped summations noncommutative:
18

---

2. (doubly) clipped summations are ordinary summatton in the limit: for any J z 1 and any sequence v1, U2,..., JJ.
J
lim 6-+400
(8) Σ 1/
lim 600
Σ j=1
lim 8-+00
Σ 1j
(-6)
(-5)
j=1
3. clipped summattion sandwich ordinary summation and the doubly clipped summation: for any 2 any J > 1 and any sequence U1, 02 ..y UJ,
J
J
J
J
Us (-6) Σ
(-8)_
(-8
Proof. Noncommutativity follows from simple counterexamples: for example, for - and
= 2, if we fix U1 = 0, = w, then (0) " " while
(0) Σ | 03-j 1. 1. Property [2.] is
trivial. The set of leftmost inequalities of property [3.] can be shown by induction, noting the base case is trivial and otherwise, using the induction hypothesis in the leftmost inequality.
J+1
Σ Bj = min
UJ+++ +
(8)
Ug. 8 & min UJ+1 +
Uz. 8 1=1
& UJ+1 +
Σ
Σ
1=1
j=1
and similarly
J+1
8)
max
UJ+I+ +
(-8)
Σ
Uj: -
1=1
j=1
J
J41
Σ
Σ
max
UJ+1
U/
UJ+1
0/
ry.
A similar argument holds for the set of rightmost inequalities: for example, the induction's 's general case holds
(6)
Uj
min
0s41
5
1=1
(8)
min
0J41 +
0j 8
(-6)
j=1
(6)
(8)
max
min
UJ+1
U/
8
Dj.
(-5)
8)
j-1
1-1
for the leftmost inequality. This ends the proof of Lemma
I1.11.2.2 Unravelling weights
Lemma E. Define
U
|
Zek
Mi
convention
uk = 1
(38)
k=1
Then VJ 1, weights unravel as:
(1/11) Σ i=1 Uj4li
m
# [T] Zzs
expx
if t<1
((+1)) =
m 1T5ma Zog
exp:
(-111 c) +)
1- 0z4ji
if t>
19

---

Proof. We start for the case t < 1. We proceed by induction, noting first that the normalization
constraint for the initial weights imposes qıi L/m 1/m and so (using (1-t)t* = 1-t*)
exp, (log, 914 mmmle)
Q2i
71
1 (1 (1-1). 1) -
1)
Mnnli
Z
m
1
m In (1 - t)
Z1
- (1 t)m 2- -- P1
m²
Z1
(1/1 1)
expt
Ujuji
m Z1
completing the base case. Using the induction hypothesis, we unravel at iteration +
((J-1)
exp;(log, qsi pyuJss)
ZJ
(V/-1) Σ j=1
J-1
yy )) mruss
exp:
10gg
m
115-1 203
expt
Zj
expt
log, expt
(4/2
J-1
VjUli
2e logg m' 11 Z1z) pruJi
Z,
(/1-))
2 j=1
J-1
logg mm IT Zes)
max
1-
exp;
ZJ
1+ (1- loge
11 Zzs) mtt
J-1
(3/1 J-1
T
1
(1-t)-max) -
nyase
- (1- lone (m" [T5=1 Zis)
ZJ
1
1+(1- log, log.loo +* 11/=1 21s)
-(1 t)uaus
(1-f)mmxx) "I-
(/1-1)
Σ
0g - 1((m
11/=t Zes) (=s)--1-1)
1
1
ZJ
(m! 11: 2zz)
-(1 t)yyuus
which simplifies into (using (1 - (1-t)t" = 1-
((+1))
J-1
1-1
(1/-1)
1 (1 11-1) 1).
max
UyUga
Uyusi
(39)
m 11 Zij
1-
exp, (-S,),
m** ||/=1 Zzj
20

---

with
S
=
min-
max
e91 1)
Σ
+ UJ
==1
(//-1)
=
min-
UyUli + min
1 1-t²
Ujugi
111-t
1-1
J-1
= min
eount +
(91-1)
Σ
Ugu
U/
1-6
J
(y1-0
VyUli
(we used twice the definition of clipped summation), which completes the proof of Lemma for / < 1.
We now treat the case t 1. The base induction is equivalent, while unraveling gives, instead (39):
((++1)
J Σ j-1
1+ (1-t)-
min ---
UgUli
m IT; Zaj
1%/-11
expe (-S,);
m2 11; Zzş
and, this time,
SJ max
min
(40)
1-
-11/
j=1
Σ
max
CJuN + max
Vzllgi
(41)
t-1
-1%
1-1
max
CjuJi + -(1-11
Ujuji
(42)
1-1
UyUlfss
(43)
(-))
j=1
which completes the proof of Lemmal
II.I1.2.3
Introducing classifiers
Ordinary linear separators Suppose we have classifier
j-1
8 my hy(2), Bg = m² , II
Hs(x) =
Zeu.
k=1
where иj R, Výj E [J]. We remark that [= * r] & expi ( for any & 2 and 2, R, and
exp; ((-(())2) is decreasing for any & 2, using [3.] in Lemma D get for our training
21

---

sample 8 = {( (i), i [m]] and any < 1 (from Lemma E
Σ
sign H, (x:)) * vill
e m
expi
2-1
1ー- m²-t* (TTi-) Zis)
1-t
My . yoh)
m
v m
(1/-t)
m --- (Ihi Zes) 1-t
expi
My yoh)(
j==1
(44)
VE m
(- (th--)
exp;
2-t
Σ 1=1
where
j-1
1-2
Uj = m 1-
I
Zex
Hí ; Uji = yihg(ax))
(45)
Using Lemma with those definitions, we get
2-t
I1 Ztz
signi( Hz()))) # yil
&
Σ
NE ml]
rE[m]
Z2-t
Σ
(J+I)i
j-1
ke|mm]
J
2
(46)
because qu Am- We thus have proven the following Lemma. Lemma F. For any < 1 and any linear separator
J E (g-h()))))())))
(0)
H)(Ø) =
[, = m
I x=1
Zek My R, R Vj E [J]]
where Zix is the normalization coefficient of q in 25
with uzi = v1hz(2x),
1.
J 11
[sign (zx))) vill <
(47)
j-1
Clipped linear separators
Suppose we have classifier (1 1)
J (i-)
Σ 8 1 My hy(m), B, m² i-1
H (x))
I
Zek
(-11 1)
22

---

We can now replace 44 by
1
sign
H
(x:)) * yill
m
expt 2
(4/2-1)
m² m (Ilh- Zoss)
1-t
Rs k2)(
(-
m
m
(3/1-)
m2- 2---
(1lK-t Zix
1-
us yels(
exp;
(-1/1-0)
mm
exp;
2-1
(4/2-1)
j=1 m 1-t
(IRE-) Zeo)
Ma (rhg((s)
(48)
m
ic[m]
(4/
exp; 2-1
UgUlii
j-1
m
mm(m
The first identity has used the fact that yi {-1, 1), it be folded in the doubly clipped summation without changing its value, and the second inequality used [3.] in Lemma D This directly leads to the following Lemma.
Lemma G. For any t < and any clipped linear separator
J H (x: = (1/-1) (-11--)
(B) m
E 23 hz(2),
Zik M3 Ry ERRR
where Zex the normalization coefficient of q in 25 with ujs
yill
J <
[sign H
(x:)) # y:ll
11 j=1
Zzz
(49)
m
(m(m)
II.II.2.4 Geometric convergence of the empirical risk
To get the right-hand side of (47 and (49) small as possible, we can independently compute each My so to minimize
(x)
Σ expi (loge 9j - pujs))
(50)
xE [m]
We proceed in two steps, first computing convenient upperbound for 50 and then finding the that minimizes this upperbound.
Step 1: We distinguish two cases depending on weight gz Let [m]] + {i >
0} and
[m]] = {i: Qzz = 0}:
Case e [m] Let uzj////" -t and suppose Rg > is a real that satisfies
Injil
R3. Vi [m]]
(51)
For any convex function f defined on [-1, 1]. we have f(2) & ((1 + +)/2)) -(11 + ((1 2)/2) f(-1),(-)))) [-1, (the straight line is the chord crossing of at 1). Because
23

---

2 [1 2]+ is convex for & 2, for any i e [m]]
expi-
(log, qi pujjt
1
10
(1 - t)pu
fj
2-1,
- (1 - (-)RR
rjs
Rj.
R3 + rii
Rí R--1% -Tji
9ft
2-t +
[1- (1 t)pRy]
1-
+ 4ji
2-t
[1+ + (1 t)pR,]
2Rj
2R₃
2 1 Rí + Uji4ii
'R Ujs
2-t
9j
2-1
9jt
[1 + (1 - -)tRR,1 -
(1 t)
2R
2R,
Case 2 iE [ml]. Let o} > 0 be a real that satisfies
Ri, Vi [m]]].
(52)
Using the same technique in case 1, we find for any i E [m]]
exp; 2-1 (loge 95: - poljs)
exp,- 2- (- (-1- puye
1
7
= [-(1 - f))
() 11- 11--=-100 -11-1)
7-1
<
< 9 2-
Rg + u3u
2-1
+ 9
82-1
Rí o/
1) =
[1 -
[)
[1 + (1
2R
2R,
Folding both cases into one and letting
ie [m]
L s
(53)
q} if i [m]]
we get after summation, using ml = Card([m])) and
Σ ببا (=),,,
(54)
(1 ml,,) 2--1 RR 1m|ml
)
that
(p-(
2 1 Rg (
(1 + mgg
(1- - (1- + (1- pp) [1) [1+ + (1- t))uR 1
2R,
1-
m
((1 + pj) exp! 2-1 - (-MRg) + (1 p.) exp (KR))).
(55)
Step 2: we have our upperbound for 50 We now compute the minimizer μ** of 55 If this minimizer satisfies
(56)
R2 1
then it can be found by ordinary differentiation, as the solution to
(1 - pz) exp; (1r RR) (1 + p,) exp, (- RT) 0.
24

---

which is equivalently
exp, (- Rg) exp; (1* (u*Rg)
=xp, (- Rí O 12" R2)
1 1- Pi
1 1 Pj
where we recall a a b (a- b)/(1 (1 + (1 - t)b). Solving it yields
1
1
(1 - (1-p))
pg) 1-1 (1 (1+ pj)
"²a
Rj
1-1
pÿ) 1-1
pÿ)
1
1
pz)2-1+ (1 (ÿ)zz)= 1 Pj
Rj
1-t
logg
M1 - Py. p,)
R2
where M,(a,b) = ((a8 + /)) is the power mean with exponent q. We now check (56).
Lemma For any t E R, let
1
1- Pj
14
R
logr
M pj. + pT)
(57)
Then lay1 & 1/(R d))-
Proof. Equivalently, must show
1- log, (M Mi 2, (
V2 E [-1,1],
which is equivalent showing
2(1 - -2
2)= (1 2) 1
[-1.1-
Define function f(2,t) -/10/1/11 + 2 over Rx0 it is easy to check that for
t < 12, [1,,1] and the symmetry (=, f(2, 1) also allows to conclude that for
t t> 12, [1. This ends the proof of Lemma
For the expression of μ in (57). we get from 55 the upperbound on 22;-((H)))
+ m
m
(p,) <
((1+ pj)
2-1 -x (-prRR) + (1 - pp) -expi- 1 (H,R,)) (1- p;)(1 p,)
2
+2-t
1 m/10
(1 (;) p=)
2
MP-((1 p3. Pj)
MF Pz. + pj)
22-1)
(1
p| Pj. 1 p5)
+ m
MP Pj. 19.14 pj)
1 P3
1 + (1+m3
M1-((1 - P5. 1 P3)
We conclude that for both sets of classifiers defined in Lemmata and with the choice of μuy in 57 we get
J
03 Mi Pj. 1 pT)
signn H(x))) * vsl &
II
+ +,mmaa
4H E (H,, H (h-1))
m
3=1
25

---

looking at To complete the proof of Theorem their constraints suggests
2 we just need to elicit the best R3
511) and q] (22
R3
max it[ml]
Ojs
max sem|]] (a;hy
of
R1((1-))
This completes the proof of Theorem We complete the proof by two Lemmata of additional
useful results in the context of Algorithm t-ADABOOST, and finally important remark on the
interpretation of Theorem 2
Lemma 1.
The following holds true: (i) Pj 1J; (ii) if, among indexes not in [m]] there exists
at least one index with Uzi > 0 and one index with uji < O, then any # O, Liz (p) > 0 in (50)
(in words, the new weigh vector 9i+1 cannot be the null vector before normalization).
Proof. To show (i) for Pj & L, write (using Uja = yehg(z,) Vi [m]] for short),
(1 + ml,,,
2-- BR Pj
Σ
o'
mm[ma
Σ
d
Eiemm luyal
Σ
Jujel
12-
Ojf
+ 9
9 1-1
Ajs
ie [m],
Rí mm|] [asal
2-
Rj
+ 4g Off
max se [m]] [asal
xe [m]]
(1+ + m]aa R,. showing & 1. Showing Pj > -1 proceeds in the same way. Property (ii) trivial. Lemma J.
Ry + q
m,,R,
& exp (-(12))
K₁(z)
Proof. We remark that for e 1). 0, K2(2) is concave and (7( -(2 t), K((2)) &
-(2 - 222, V2 > 0, from which it follows by integration
1 (11))))
Kx(z)
and since 1 1- < exp(-2), we get the statement of the Lemma.
Remark 1. The interpretation of Theorem foror t < are simplified to the case where there is no weight switching, i.e. m. = 0, Vj. While we have never observed weight switching in our experiments -perhaps owing the fact that we did never boost for very long number of iterations or just because our weak classifiers, decision trees, were in fact not so weak -, it is interesting, from a theoretical standpoint, to comment on convergence when this happens. Let Q, = 1+ m), and أ; = Q2P; (Notations from Theorem D). We note that P. > B B.,,, [v:,((()) where Pj lives on the simplex and lyh] & 1, 3 & 1. Using Lemma and (12) (main file). keep geometric convergence, it is roughly sufficient that Q, log Q, & (f))) Since af is homogeneous tempered weight, one would
expect in general m) ( 1, using the Taylor approximation Q, log Q2 -1 + Q, one gets the refined sufficient condition for geometric convergence
m) & (0,) (((;))²).
What does that imply? We have two cases:
26

---

If this holds. then we have geometric convergence:
if it does not hold, then for a "large" number of training examples, we must have Qjs O which, because of the formula for q (8) implies that all these examples receive the right class with a sufficiently large margin. Breaking geometric convergence in this case is not an issue: we already have a good ensemble.
I1.3 Proof of Theorem
Starting from the proof of Theorem 2 we indicate the additional steps to get to the proof of Theorem The key is to remark that our margin formulation has the following logical convenience:
3
1+ - (1 t)yH(())
0
[v.((z..)) & d] = [-yH(z) + log:
> 0]
11-01 0
1 - 0
1 +
= [(-yH(()) +c loge
> O].
1 1- 0)
We then remark that since [= 0| & expi 2-1 (x),, we get
1- (1-0)
1 ++0 0
[ 9:), H1 < 0l < expi +-t (-yll(xx)) @r log,
1 (1))))
1 [1+0]
expt
2-t
log,
exp; (-)H(())
1+
2-1
expt 2 ' (())
1-0
We then just have to branch to 44). replacing the [sign( (H) which yields in lieu of (46) the sought inequality:
vills by [u(((,,, v)) H) s 0J.
0
2-1
(H,
<
1-0
I 2
(58)
IT.4 Proof Theorem
The proof proceeds in three parts. Part (A) makes a brief recall on encoding linear classifiers with decision trees. Part (B) solves (6) MF, i.e. finds boosting's leveraging coefficients as solution of:
q(u)
0.
(59)
we then simplify the loss obtained and elicit the conditional Bayes risk of the tempered loss, i.e. (0 in MF. Part (C) elicits the partial losses and shows properness and related properties.
Part (A): encoding linear models with a tree architecture We use the reduction trick of (au- thor?) [16] to design decision tree (DT) boosting procedure, find out the (concave) loss equivalently minimized, just like in classical top-down DT induction algorithms (6). The trick simple: DT can be thought of as set of constant linear classifiers. The prediction is the sum of predictions put at all nodes. Boosting fits those predictions at the nodes and percolating those to leaves gets a standard DT with real predictions at the leaves. Figure provides a detailed description of the procedure. Let denote leaf node of the current tree H, with HA* R the function implements for leaf If parent (A) denotes its parent node (assuming wlog it is not the root node), we have
H^
H parent(()) + pxhx,
(60)
Part (B): eliciting the Bayes risk of the tempered loss With our simple classifiers at hand, the tempered exponential loss Z2 in (14) (MF) can be simplified to loss
((H) = Σ expt 2-2 (log, Qıe Us (x.)))
Σ m expi 2-1 (log, qui Hx) + m, exp? (log, Q1: + Hx), (61)
=
(eA(H)
27

---

p4b.
2 02
3/2 <
0g
pigb2
14302
.ta 2 0u
Zg < ag
2g 2 dg
Fig. 0g
peybi Mala BAEDa
Pyb peato
pighs
Figure 2: The weak learner provides weak hypotheses of the form [IA az] by. From the boosting standpoint, this weak hypothesis is "as good as" the weak hypothesis h,(2r) [ a,] bbg- The predicates of both are used to craft a split, e.g. for the root (in our depiction, by = b2) and then solving (59) provides the leveraging coefficients μ... We then repeat this for many splits as necessary. At the end, we can "percolate" nodes reals towards the leaves below and get an equivalent
classifier that resembles a decision tree (right). See [66] for further details.
where ((x) is the leaf reached by observation æ and X(H) its of leaf nodes of H, and Hx sums all relevant values in (60). Also, m m denote the cardinal of positive and negative examples À and pa = m///mm²/ + the local proportion of positive examples X, and finally ra = (m + +m \/m the total proportion of examples reaching X.
Theorem A. we compute μa the solution of (59). we end up with the prediction Hx:
m
H사 = 41
(62)
t
mx
1-t
+1
(1 - px) 1 1-
P
(63)
P1 1
(1 1-1
and the loss of the decision tree equals:
2px(1 - PA)
L(H) =
Σ
TX
M MI.(PA,.1 1 PA)
(64)
AEA(H)
(65)
Proof. To compute μx. (6) is reduced to the examples reaching X, that is, simplifies
m exp, (log, qii H parren((A) Rauxha) m, exp; (log, qie H Hparent(2) Rawxh666) that we solve for μ사- Equivalently,
exp; (log, Qie H parent(2) RAMxlis)
m
exp; (log, Qii H parrent()) RAMxlis)
mx
or, using (u)/ (v) exp, (u O v),
2H (apeent())) + 2RAuxhx
m m
log,
1+ (1 (log, 91: H (2) RAHx)a)
after reorganizing:
(1 (1 (log, 9i Hparent(A))) log m m
2H parent(A)
Rapahx
=
m m,
2 (1 loge
28

---

which yields the prediction at A:
(1+ (1 - (log, 9is - H parren(())) logg
2H parent(A)
H
H (A) +
m
(67)
2 (1 1) loge
mi
mxx
(1+ (1 log, 91e) logr
m
=
(68)
2 (1 t) logr
m
log
m
9i
meg
(69)
2 2+ (1
loge
m
m
-1
41
m
(70)
t
m
1-1
+1 1
(1 Px) 1-
Px
(71)
t
P (1
Px)
We plug Hx back in the loss for all leaves and get, using qıa 1/m
mx exp? 2-c (10g, qii
a/i p/_ (1-
L(H) = E
T-r
p2, - ((1-aa)-- )-
(72)
+m expi- (10g, Qii
(11-)>)))
AEA(H)
I-T
P2 p1
We simplify. First,
93. p) - (1 Px)
m² expi-1 2-1
logg, 91:
1-t t 1-1 + (1 PA 2-
1-t, (1 (1- 1- (1-Px) 1- 1-1
m
91
px 1-t + (1 - px) (1-px)
mx
2(1 - p2) 2-
(73)
1-t (1 px) 1-t
m
P2
mx
1- p2
(74)
m
MM-((Pxx 1 PA)
and then
I 1-t p 1-1 (1-px)
mx exp? 2-t
(log, 92s +
1- t p) 1-t + (1 - 1-
11 1-t - p2) (1-px) 1-1
my
Oii
1-t
1+
Px -t + (1 - px) --
2ph I-
1
m
(75)
m
(1 - PA)
2-1
m
PA
(76)
M Mi-r(px, 1 - PA)
m
29

---

and we can simplify the loss.
2-t
I(H)
Σ TAPA
1 1 PA
+ra(1 p2) M M- -pA)
(77)
M1 MI 1 PA)
AEA(H)
Pa(1 - PA(1-PA)2 + 1(1+++11---1111110 -PAlp
Σ HE
(78)
Mpxi(xx11 1 1-PN) PA)
Px(1 PA) (pp-'1+ + (1 -Px)-
Σ AEA(H)
(79)
M (px, PP>)
2px Px) Mp 1 PA)
Σ AEA(H)
TX
M 1 -P))
(80)
2px (1 P2)
Σ TX Mi 1 PP))
(81)
ΛEA())
as claimed. This ends the proof of Theorem A
Part (C): partial losses and their properties The proof relies on the following Theorem. We recall that a loss is symmetric iff its partial losses satisfy {u( f-1(1 u), Vu E [0. 1] 20 and differentiable iff its partial losses are differentiable.
Theorem B. Suppose t < 2. A set of partial losses having the conditional Bayes risk L in 65 are
(u) (Mr-o(u,1-)) u)
-
2-2
(u) - ef - u).
(82)
The tempered loss is then symmetric and differentiable. It is strictly proper for any t e (-00, 2) and proper for t -00.
Proof. Symmetry and diffcrentiability are straightforward. To check strict properness, we analyze the cases for * (otherwise, it is Matusita's loss, and thus strictly proper), compute the solution u to
à Lu, 0.
(83)
du
To this end, let Nw)) = u(1 2)2-t t (1 v)u²- and the q-sum
by
(a + 10)3/44 2//9 Mg(a, b).
(84)
We also let D(u)= - ( 1- -1.. u). Noting l. (u, - 2 /N())D(u and D(v) * 0, Vu e
[o, 1]. the set of solutions of (83) are the set of solutions to (()) = N (')) which boils down, after simplification,
((1 v)u² 1- v(1 - -) u)
u), developing and simplifying yields first simplified expression (1 - 2v) (u(1 x)) = nu 1(
= (u(1- - -)² + (1 - vu- -1-
u)²-t (1-v)( (1 u) - which, after reorganising to isolate expressions depending on v, yields
(u(1 -)) -) (1 u) 2-t
u. (u '(1 = + + (1- - + - 2 (3))
Assuming e (0, 1), we multiply by (u(1 u)) 1-t (we shall check E (0, 1)) and simplify, which
yields un u) + 2² = v((1 - u²² + u² + 2u 1 - u)), and indeed yields
=
(86)
and we check from (55) that if 0 (resp. 1), then necessarily 0 (resp. u 1). To complete the proof, using the previous derivations, we can then simplify
L(, du
0
(2 t) 1 2 (u(1- - u))² S (u, u
u 1--
(87)
30

---

which shows that if 2 > 0 but * -2, u= = v is strict minimum of the pointwise conditional risk, completing the proof for strict propemess. Strict properesss sufficient show by a simple
computation that L (t) is 655 For - 00, we pass to the limit and use the fact that we can also write
(w)
(we recall ta = 1/(2-- 100-)) f))
(88)
M1-1* 1, 1-11
t -0 is equivalent to ts 0+. uf 1/2, u/(1 - u) < 1 and so we see that
1 2
lim Mi 1, 1-
2
because M1 is the arithmetic mean. When u > 1/2, u/(1 - u) > and so this time
lim Mi-r# (1, (1.( 1 11-u
# (1))
u
= +00.
Hence,
(w) (u)
2. Iu & 1/21,
(89)
which is (twice) the partial loss of the 0/1 loss
26
This ends the proof of Theorem
31

---

Domain
Source
m
sonar
UCI
208
60
btspe://archive. oda/////// http///w....ooooo////aaa/aaaaaaa
winered
UCI
599
12
bespe: http:///.....o//////////////////
atspe://archave.. 1cs uct www.//////aaaa///
abalone
UCI
4 177
qsar
UCI
155
41
acspa://archit
uci www.//l//aaaaoaa wwtp:////aaaaaataaaaaaaaaaa/ae//
winewhite
UCI
4.898
12
acspa://ar htt.://ww......aaaaaaaatttttt...
hillnonoise
UCI
1212
101
bccp::/ bacp:///rchan http//rcchheeeeeeeeeeee Ics uuc. cessi..dd/oeee www////////eeeeeeoooee
hillnoise
UCI
1212
101
Bcap:/ accp://ardin
eeg
UCI
14 980
15
hespa //wrch/ ve. unc add./// /nl/ /ttt://///basaeaa////aegeg
creditcard*
UCI
14 599
24
maspa://archivee Ses..cct /edu//lllllll /tw.d/aatttt//eeeaaeeeeeee
adult
UCI
32 561
15
hexpp:///archs iic...... www.////aaaaa......aa http:////dddaaat///eaaaa
Table A3: Public domains considered in our experiments (m
total number of examples, d = total
number of example's features, including class), ordered in increasing m (see text). (*) first m rows in the domain.
III
Supplementary material on experiments
Domains
Table A3
presents the 10 domains used for our experiments.
I11.2 Implementation details and full set of experiments on linear combinations of decision trees
Summary This Section depicts the full set of experiments summarized in Table (MF), from Table A4 Table[AT5) Tables are ordered in increasing size of the domain (Table
all cases, up to J= 20 trees have been trained, of size 15 (total number of nodes, except the two biggest domains, which the size 5). For all datasets, except creditcare and adult, we have tested in complete range, / (0.0, 0.2, 0.4, 0.6, 0.8, 0.9, 1.0, 1.1] (the MF only reports results for > 0.6), and in all cases, models both clipped and not clipped. For each dataset, we have set a 10-fold stratified cross-validation experiment, and report the averages for readability (Table 2 in MF gives the results of a Student paired t-test on error averages for comparison, limit p-val = O.I). We also provide two examples of training error averages for domains hillnoise and hillnonoise (Tables A10 and A12).
Implementation details of (-ADA BOOST First, regarding file format, we only input cav file to (-ADABOOST. We not specify file with feature types as ARFF files. L-ADABOOST recognizes the type of each feature from its column content and distinguishes two main types of features: numerical and categorical. The distinction important to design the splits during decision tree induction: for numerical values, splits are midpoints between two successive observed values. For categorical, splits are partitions of the feature values in two non-empty subsets. Our implementation of t-ADABOOST (programmed in Java) makes it possible choose f just in the range of values for which we have shown that
l 1. Because we thus implement ADABOOST convergence is possible (f [o, 1)). but also 1) but also for / 1, weights can fairly easily become infinite, we have implemented safe-check during training, counting the number of times the weights become infinite zero (note that in this latter case, this really is problem just for ADABOOST because in theory this should never happen unless the weak classifiers achieve perfect (or perfectly wrong) classification), but also making sure leveraging coefficients for classifiers do not become infinite for ADABOOST, a situation that can happen because of numerical approximations in encoding, In our experiments, we have observed that none of these problematic cases did occur (notice that this could not be the case if we were to boost for large number of iterations). We have implemented algorithm t-ADABOOST exactly as specified to train decision tree in which the stopping criterion is the size of the tree reaching a user user-fixed number of nodes. There thus no pruning. Also, the top-down induction algorithm proceeds by iteratively picking the heaviest leaf in the tree and then choosing the split that minimizes the expected Bayes risk of the tempered loss, computing using the same values as for L-ADABOOST, and with the constraint to not get pure leaves (otherwise, the real prediction at the leaves, which relies on the
MF. The weak learner implemented
32

---

We have performed some additional experiments on several domains, on which we have trained bigger ensembles and / or considered more noise levels than in the previous experiments, with the objective to see if / when overfitting happens and how performances degrade with noise as a function make based on those perr (not clipped)
perr (clipped)
min weight
max weight
Adaboooa
Adabossi
0.07
0.08
0.00
3.07
0.000
2,005
0.00
0.00
0.00
00225
3,005
0.00
945
04
5.001
0.02
0.02
0.3
00
02
0.01
0.0003
0.01
Kaaboour (-1
Raatooaa (1-1 (i)
Adatiooa (+1
71125
Kaaabook 01-
0.12
0.03
0.5
0.8
0.8
0.1
30
345
0.105
0.11
0.1
0.
04
0.01
00235
0.000
2010
0.02
0.8
0.4
0.00
22
02 0.001
02
0.000
0.67
1.08
5.005
12
Table A4: Experiments on B-ADABOOST comparing with ADABOOST (f = 1, bullets) on domain sonar, when trained without noise (n) 0.0, top row) and with noise (17 0.1, bottom row). Columns are, from left to right, the estimated true error of non-clipped and clipped models, and the min and max codensity weights. The set of t values used is displayed in each plot with colormap (right), and varying thickness of curves for an additional ease of reading (the thicker the curve, the larger 1). ADA reference results are displayed with bullets. Averages shown for readability.
link of the loss, would be infinite for ADABOOST) In our implementation of decision-tree induction, when the number of possible splits exceeds fixed number S (currently, 2 000), we pick the best split in subset of S splits picked random.
Results First, one may notice in several plots that the average test error increases with the number of trees. This turns out to be sign of overfitting, as exemplified for domains hi billnonoise and hillnoise, for which we provide the training curves. If we align the training curves T 1 (the value is different because the splitting criterion for training the tree is different), we notice that the experimental convergence on training is similar for all values of t (Tables [10] and A12]. The other key experimental result, already visible from Table 2 (MF), is that pretty much all tested values of t are necessary to get the best results. One could be tempted to conclude that slightly smaller than 1.0 seems to be a good fit from Table (MF), but the curves show that this is more a consequence of the Table being computed for J = 20 trees. The case of eeg illustrates this phenomenon best: while small (-values are clearly the best when there is no noise, the picture is completely reversed when there is training noise. Notice that this ordering is almost reversed on creditcard and adul t: when there is noise, small values of tend to give better results. Hence, in addition to getting (i) pruming mechanism that works for all instances of the tempered loss and (ii) a way to guess the right number of models in the ensemble, good problem to investigate is in fact appropriately tuning in domain-dependent way. Looking at all plots reveals that substantial gains could be obtained with an accurate procedure (over the strategy that would be to always pick fixed f, e.g. t 1).
III.3 Supplementary experiments: learning with more trees/ against more noise
of t. Table [ 16 summarizes the results obtained. A few comments experiments are:
overfitting can indeed happen (sonar for 1 0.4) but affects differently the algorithm depending on and whether clipped models are learned instead of regular linear models; results also display that tuning can also have the purpose of handling overfitting:
33

---

perr (not clipped)
perr (clipped)
min weight
max weight
Adhdioaa
9224
5,0008
223
0.59
0.24
0.29
9.29
0,0022
8,003
00015
E/002
0.22
322
0222
02
0.001
02
0218
0210
00006
Acadoool (H)
Kaabooaa
10033
Adaboool D+1
Adaobooll ge1
0.80
0.200
6,0005
08
0.
0.20
0.6
0220
06
0.0033
D0018
E.022
08
04
0.4
D0218
04
0215
02
0215
02
2.0011
0.3
02
321
221
00006
Table A5: Experiments on B-oST comparing with ADABOOST (f bullets) on domain
winered. Conventions follow Table A4
perr (not clipped)
perr (clipped)
min weight
max weight
12212
Scadreed
12210
0.214
F10722
00311
D2111
0.11
00302
DI0014
3.1
0212
08
E.001
0.200
00301
DO008
0.207
6x105
A 1009
1009
4 3000
1000
22118
(1-1.0)
0000115
0.214
5/00222
0.913
0.122
0000
00010
0.207
00012
002245
0207
0.200
0200
0.200
5,00000
0200
0.204
2,00036
0.0005
Table A6: Experiments on (-ADABoost comparing with ADABOOST (L 1, bullets) on domain abalone. Conventions follow Table A4
clamped models can be very useful handle overfitting (sonar for 17 0.4, qsar for T 0.2); this provides another justification to learn clamped models;
the overall diversity curves as a function of t supports the idea that good strategies could in fact tune f at training time and change its value with iterations.
34

---

perr (not clipped)
perr (clipped)
min weight
max weight
0.2
Ad00005:8-12;
0.19
A588606.8-1.3
5,0003
Asaboost (-130)
E301
0.10
5,009
0.18
20:17
88
0,0000
3,007
08
0.11
302
0.16
5.0034
3.033
2
0.14
*oote
6.0001
2,002
16
10 12
1402
* 3223
2040
(+1.0)
(-1.0)
0.108
0.179
0,0007
50.17
Di025
9:17
9:19
2.0344
DU322
0.190
8.0033
0.022
3.10
0.145
0.145
0.0001
D0215
Table A7: Experiments t-ADABOOST comparing with ADABOOST (f 1, bullets) on domain qsar. Conventions follow Table A4
perr (not clipped)
perr (clipped)
min weight
weight
1228
12230
00202
Assacok 0105066.11111
0001E
Assnoost BR13)
8.00113
8.000
08
30200
202000
D00012
D0301
0.999
0.200
Ext0
0.220
0220
Sx104
4x12/5
DI006
# 3CC0
A3000
Adadooot
(1-100)
(1-1.0)
(1+1
0.366
0.206
000066
0.24
0.022
100001
0.00080
0222
122
00014
0.20
10312
0.28
0228
0000100
0.0044
0.26
0.24
5.00330
0.000
0204
0.200
5,00936
000025
Table A8: Experiments (-ASABoOST comparing with ADABOOST (f 1, bullets) on domain wineshite. Conventions follow Table A4
35

---

perr (not clipped)
perr (clipped)
min weight
max weight
0.305
1.89
Aciloool De
0.890
Adiifoooa (P
0,0930
00338
00389
D0215
00216
Assoscal (PT3)
0.
500075
D0214
0.0
0.060
3.7
1.30
0.59
100355
28307
00305
0.45
0.4
08
00305
3.20
00204
10
23
12
1,400
0122270
002118
0.15
0.00382
D.015
2:10
0415
00308
00314
08
DAT
6nbsaa
D0212
0.201
8.00355
00305
00011
609942
à 1000
1000
$ 32005
1000
Table A9: Experiments t-ADABOOST comparing with ADABOOST (t 1, bullets) on domain hillnonoise. Conventions follow Table A4
training err (not clipped)
training err (clipped)
0:371
Asscosil (+12]
Adacocal
0.27
0.388
0.258
0.354
0.38
0.340
0.36
0.309
0.4
0:158
34
0.0
0:250
0.2
0.254
42
0.252
0:345
0.25
15
17:11
Adeoosel (+12)
0.
00
0.399
0,35
0.8
0.20
38
0.4
0:26
0.375
0375
14 10 16 23
10 12 14
3044
Table A10: Experiments t-ADABOOST comparing with ADABOOST 1, bullets) on domain hillnonoise: training errors displayed for all algorithms using conventions from Table A4 See text for details.
36

---

perr (not clipped)
perr (clipped)
min weight
max weight
0.370
1.27
Aciioooal (PP D1
0.990
00389
002188
Adlbccot (Pr)
00308
000125
0.8
0.0012
0.508
0.35
0.50
0.345
0.
0.5
0.0011
04
0345
0.4g
00385
0.4
0.0011
0.338
8.00555
0.001
2:33
0.300
000000
15 20
12
15
23
13
12400
117.270
003-11
0.300
0.00382
3.28
0.385
1.30
000075
00013
08
3.20
800355
00300
2011
0375
6.001
04335
8 1000
1000
$ 32005
1000
Table A11: Experiments t- t-ADABOOST comparing with ADABOOST 1, bullets) domain hillnoise. Conventions follow Table A4
training err (not clipped)
training err (clipped)
0.26
Adsocca [F12]
0.355
0.31
0.34
0.35
0.4
34
0.0
0.325
02
0.315
42
1:775
Adsossel (+12))
17:122
Adabocel [+12]
0:374
0.0
00
0,344
0.8
0.77
08
0.304
0.4
04
0,302
0.26
14 10
10 12 14
5944
2300
Table A12: Experiments t-ADABoOST comparing with ADABOOST 1, bullets) on domain hillnoise: training errors displayed for all algorithms using conventions from Table A4 See text for details.
37

---

perr (not clipped)
perr (clipped)
weight
max weight
129
Acatooos (1-50
02000
Aoaboost (1-10)
5000007
Kaatood (-130
0000244
Adaoocst (-1a)
0.294
0.200
20,0323
08
9.29
0000033
20.00018
0.20
0.6
9:274
0.27
0.272
1000033
20/00012
0.200
0.298
5,00022
0.00311
16
# 1900
2940
A9 1000
0.200
51002017
(+1.0)
0703205
(-1.0)
2100037
100030
0000211
30215
00000
0000310
0.206
0299
0.00333
0.00212
0200
0.203
2.00332
0.0000
Table A13: Experiments t-ADABOOST comparing with ADABOOST 1, bullets) domain eeg. Conventions follow Table A4
perr (not clipped)
perr (clipped)
min weight
weight
1222
Acatooot 1I1
2216
Xadoooa (i1
000038
Ad0lood (F130
U0004
Adbicooo (111
0214
P0214
0216
0212
Bose
Goop
00035
0.0069
000000
0.5
5.000
0.200
0.20
10033
00
8
0:0062
0.000
0.204
3,00033
0.00111
4 1000
30:5
(1-10))
(1-1.0)
(1+1
0.216
0.216
500033
000022
0212
0.14
0.212
1.21
Peo
25,0003
0,0002
0:21
200
0208
2000
C000034
D000116
0206
07
0.204
D00014
07
0204
0.200
0.6
5,00033
000012
Table A14: Experiments A-AoBooST comparing with ADABOOST (t 1, bullets) domain creditcard. Conventions follow Table A4
38

---

perr (not clipped)
perr (clipped)
min weight
max weight
2.18
0.1a
3010"
0.00203
2.5x10*
0.00345
0.17
0.176
Fo.ra
15dy5
2009
2000335
5000033
0.9
9.17
5 0.198
txbo
0.00333
0.168
0.166
0.7
02
0.7
03
0.184
0.162
0.5
0:00005
0.8
A30
0.176
0.174
0:176
50.12
3:17
0.5
0.174
0:172
0.5
0000311
0000320
0.8
0:168
000310
0.166
20032212
B1000004
0.162
0.164
0,102
0.164
00003100
0000306
0,00003
3.16
0. 2.10
0.0
0.00300
0.6 0.00904
06
Table A15: Experiments on B-AST comparing with ADABOOST (t = 1, bullets) on domain adult. Conventions follow Table A4
7) 0
0.1
0.2
0.3
0.4
sonar, clamped sonar, unclamped winered, clamped
0.7
2.00
0.20
3240
3.26
1.2
0370
035
2:34
87 221
1.24
317
04
04
315
AE 90 30
(014)
2155
009
0.1
020
0.43
316
318
110
011
0.44
0.3
017
2760
20 30 At 30 10
09.0 12 100
13 50 53
30
13.25
30 50
qsar, une une lamped
Acabooal 3013
3155
Ansinoa 3o1
316
011
017
2165
0455
011
6.5
3155
6.7
6-12
20
23
15
06 10:00
3145
10
30-0
62100
863185
10
50
83100
85 0.0
13
70
0.44
00200 36 N0 00100
qear, clamped
6:66
p+1.))
315
1.1
31105
Acsicca 3013)
022
Kicooa (01A)
17.
211
6012
2:20
03 8115
6.34
312
22 23 50 6:18
9012
02
13
12.20 20
TO
Table A16: Additional experiments with a larger number of trees and various levels of noise, on winered (J = 150 trees, T = 2 splits per tree) and sonar and qsar (J= = 100, T = 2). Note that the range of noise levels tested is broader than for the other experiments.
39


Reviews:
[{"review_id": "HDBliLfpl4", "reviewer": "Reviewer_6L9a", "summary": "The paper presents an estension of ADABoost algorithm for binary classification, called t-ADABoost, by modifying the weight optimisation under simplex constraint formulation of the original algorithm. The generalised formulation involves optimisation of modified Bregman divergence between new and old weights under a so called co-simplex constraint (i.e. a sum constraint on the power of the weights). The paper establishes that these new optimisation problems amount to a one parameter optimisation problem in a way similar to ADABoost, then that the resulting construction of a strong learner will, under a generalised assumption, will have an empirical error which decreases exponentially quick.\n\nThe paper complements their results by experiments comparing the behavior of the t-ADABoost algorithm for decision tree using different t values. The results show that depending on the data and presence of noise, the relationship between t value and test error can change.", "questions": "The algorithms presented here works for binary classification, as is the case for the initial ADABoost algorithm. ADABoost has been extended to multiclass settings. Could such an extension also work for t-ADABoost?\n\nThe interpretation of theorem 2 relies (line 161) on the assumption that $\\lvert \\rho_j\\rvert \\geq \\gamma$. If $m_j^\\dag > 0$, the value of $\\rho_j$ depends on $t$ and therefore the assumption above could be false for certain $t$. Is there any insight on how this impacts the exponential decay? Moreover, even in the case where $m_j^\\dag = 0$, considering that $\\rho_j = \\frac{1}{R_j}\\sum_{i\\in[m]} q_{ji}, y_i h_j(x_i)$  and that $q_{ji}$ no longer need sum to $1$ but rather should belong to a co-simplex, the assumption that $\\lvert\\rho\\rvert >\\gamma$ does not have the same implication depending on the value on $t$. Could you comment on whether this is a stronger requirement in the case where $t<1$.\n\nAre there any overfitting issues related to t-ADABoost, notably when $t \\ll 1$ or when $t > 1$? Could these be investigated by allowing the number of trees grown to be larger than 20 in the experiments?\n\nIn section 6, it is mentionned that reference 10 note that Matusita's loss implies a near optimal boosting rate while the empriical risk gives the worst possible guarantee. Could you specify where these two results are stated in the reference?", "limitations": "The current form of the algorithm seems to be usable only the case of binary classifiation, while the original ADABoost has been extended to multiclass settings. It is unclear whether this restriction can be lifted efficiently.\n\nThe authors clearly mention that the current work should be complemented by further insights on the selection of $t$, which is coherent with their experiment results (where the optimal $t$ value depends on the dataset and noise).", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well introduced and describes an original extension of ADABoost algorithm, by incorporating the notion of tempered exponential measures which was found to improve robustness in clustering.\n\nThe authors give sufficient evidence that the extended algorithm is able to decrease the empirical risk as at least the same rate as the original ADABoost algorithm  (Theorem 2 and discussion following) and that the use of an oracle t-ADABoost algorithm can reduce the test error compared to the initial ADABoost algorithm (Table 1). This, as the authors note, imply that while work remains to be done in order to learn the optimal t for each new dataset, this generalisation has its use cases.\n\n", "weaknesses": "Part of section 5 and Algorithm 1 are confusing. Notably, in the description of Algorithm 1, the beginning of Step 2.2 starts with what seems to be a typo (I believe $\\mu_{ji} = y_i h_j(x_i)$ should read $ u_{ji} = y_i h_j(x_i)$, then neither the coefficients $\\nu_j$ and $\\alpha_j$ are defined until Theorem 2. The wording \"choose leveraging coefficient\" seems to imply that the choice can be arbitrary, while, considering that Algorithm 1 is described just after Theorem 1., one could infer that the coefficient $\\nu_j$ is the minimizer of equation (5). \nIn equation 11, the quantity $m^{1-t^*}$ is not introduced anywhere.  The next mention is in line 180, where it is stated that it can be discarded in the unclamped case, but that it does play a role in equation 12, where the quantity does not appear (while $1 + m^\\dag {q_j^\\dag}^{2-t}}$ appears and could play the \"dampening part\" mentionned later on).\n\nParts of section 6 could be clarified. There is some confusion between the notations $L$ and $\\underline{L}$ (line 200, $\\mathbb{E}_\\lambda[\\underline{L}(p_\\lambda)$, but $\\mathbb{E}_\\lambda[L(p_\\lambda)]$ line 219, which in itself does not make sense as $L$ takes 2 arguments. Moreover in equation (16), from equation 200 implies that the DT is trained from the Bayes risk, and as such, reverse engineering should start by computing the Bayes risk rather than CPE loss). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we would like to thank the reviewer for reading our paper and noticing the typos mentioned. \n\n(weaknesses section)\n\n> Part of section 5 and Algorithm 1 are confusing\n\n[6L9a:A] We sincerely apologize for the confusion, resulting from our choice of organization, and unwanted typos. Correct for $\\mu_{ji}$.\n\n> The wording \"choose leveraging coefficient\" seems to imply that the choice can be arbitrary\n\n[6L9a:B] We followed the convention for AdaBoost [28] (our paper). We can do otherwise\n\n>  could infer that the coefficient $\\nu_j$  is the minimizer\n\n[6L9a:C] (we assume it is $\\mu_j$) It is a minimizer of an upperbound of (5) with the “secant trick” (II.II.2.4 supplement)\n\n> the quantity $m^{1-t^*}$\n \n[6L9a:D] $m$ is the number of training examples, $t^* = 1/(2-t)$. This is just a factor (the same for all leveraging coefficients) that makes the formal analysis “simple”. It logically disappears from (12) because it is part of $H$.\n\n> Parts of section 6 could be clarified\n\n[6L9a:E] As we state in L219, the simplification ends up with a loss of the form $E_\\lambda[L(p_\\lambda)]$. Here, $L$ may just be any function from $[0,1]$ to $\\mathbb{R}$. It turns out that, in our case, it ends up being a very particular function with the key property of being proper – and thus eliciting Bayes prediction as its minimizer – for any $t\\in [-\\infty,2)$, a function usually noted $\\underline{L}$ [22,23] (our paper). We can make this more explicit.\n\nNote: we insist on the fact that in a field (ML) where we are used to see a plethora of loss functions, such an invariant is quite exceptional because one can safely slide $t$ in a huge range without ever breaking up properness *and* guaranteeing boosting rates in the complete spectrum of known rates (and even unknown rates, for $t\\in(1,2)$ (L243). We know of no other parameterized loss with such a property.\n\n(Questions section)\n\n> The algorithms presented here works for binary classification... Could such an extension [to the multiclass setting] also work for t-ADABoost?\n\n[6L9a:F] Most certainly, following the blueprint of [28], Section 6.\n\n> The interpretation of theorem 2 relies (line 161) on the assumption\n\nExcellent questions ! First, the theoretical analysis covers all cases, including $m_j^\\dagger > 0$. In our experiments, we always noted $m_j^\\dagger = 0$ so the first question seems to be essentially relevant to theory. The question(s) led us to reconsider why we observed this and in fact there is a simple explanation as to why $m_j^\\dagger > 0$ would be very rare *if* the weak learner is not “that” weak (which is our case, with decision trees): one needs to consider Lemma J (supplement) together with (12). Let $Q_j = 1 + m_j^\\dagger (q_j^{\\dagger})^{2-t}$ and $\\tilde{\\rho}_j = \\rho_j \\cdot Q_j$. Note that $\\tilde{\\rho}_j$ is of the form $\\beta \\cdot E_{p_j}[yh]$ where $p_j$ lives on the *simplex*, and $|yh| \\leq 1$, $\\beta \\leq 1$. Using Lemma J with (12), to keep geometric convergence, it is sufficient that\n\n$Q_j \\log Q_j \\leq  \\tilde{\\rho}_j^2 / (2t^*) $\n\nSince $q_j^{\\dagger}$ is homogeneous to a tempered weight, one would expect in general $m_j^\\dagger (q_j^{\\dagger})^{2-t} \\ll 1$, so using $Q_j \\log Q_j \\sim_1 -1 + Q_j$, one gets the sufficient condition\n\n$m_j^\\dagger (q_j^{\\dagger})^{2-t} \\leq \\tilde{\\rho}_j^2 / (2t^*)$\n\nNote that for $t=0$, $2t^* = 1$, so one roughly gets that to keep geometric convergence, one needs $m_j^\\dagger (q_j^{\\dagger})^{2-t} = O(\\tilde{\\rho}_j^2)$. What does that mean ?\n\n1. If it is not violated, then we have geometric convergence\n2. If it is, then a large number of training examples have $q_{ji} = 0$, which means that they are receiving *the right class with large margin* [4pmA:C], [4pmA:D]. In this case, breaking geometric convergence is not an issue: we already have a very good ensemble !\n\n[6L9a:G] We propose to put this analysis, which we believe is enlightening, at least in the supplement. \n\n> Are there any overfitting issues related to t-ADABoost,\n\n[6L9a:H] Excellent question. We have performed additional experiments on learning ensembles with a larger number of trees ($J$), each of them being smaller ($T$) *and* tested domains with a larger amount of training noise (because noise affects just training, it could induce overfitting by models “focusing” more on fitting training data or the noise patterns, at the expense of the full domain). We crammed a few in **the attached .pdf**, selected for the topic raised (we would be in a position to present all results in the supplement of the camera-ready). What emerges:\n\n1. Overfitting *can* happen (winered $\\eta = 0.2, 0.4$, sonar $\\eta = 0.4$) but affects very differently the algorithm at different $t$ values and yields very substantial differences (by several % points). Overall, this displays that tuning $t$ can also have the purpose of handling overfitting.\n\n2. Clamped models can be better at resisting overfitting (qsar, all $\\eta > 0$). Strong incentive to train clamped models as well.\n\n3. Some plots (sonar $\\eta > 0.1$) suggest the idea that more than just tuning $t$ beforehand, good strategies could in fact **learn** $t$ and adapt it **during training** (so each iteration $j\\in J$ would use a specific $t_j$). We suggest adding this in conclusion.\n\n> In section 6, it is mentionned that reference 10 note that Matusita's loss \n\n[6L9a:I] Optimality of Matusita = paragraph following Theorem 1 in the JCSS version (open access). Empirical risk = worst: Fig 2 + Fig 5 (+legends). Note: [10] prove the optimality of Matusita’s from an information-theoretic standpoint. It is also shown from a computational complexity standpoint in [A] \n\n[A] Nock & Nielsen, “On domain-partitioning induction criteria: worst-case bounds for the worst-case based” (TCS 321, pp 371-382, 2004).\n"}, {"review_id": "MqSP7J9e8R", "reviewer": "Reviewer_KBAC", "summary": "The paper proposes a generalization of the ADABOOST algorithm using tempered exponential measures. To do this, they begin by introducing $log_t$ and $exp_t$ and the generalization of entropy. A first theorem is proposed to explain how to find the solution for the minimization of this entropy and an adaptation of the ADABOOST algorithm, called t-ADABOOST, is presented. Section 5 is dedicated to explaining the convergence of the t-ADABOOST algorithm and a theoretical study of its behavior. In section 6, the authors take the time to introduce tempered loss and the associated decision trees. The authors conclude with experiments and a discussion.", "questions": "I think the paper would be easier to read if the number of notations were reduced (for example, $t^*$ is not compulsory in my opinion, as it's often $1/t^*$ that's used). I think it should be made clear whether $Z_t$ is a function or not. In the same vein, I think some equations lack rigor. For example, $\\log_t$ and $\\exp_t$ are introduced at the same time, even though their spaces of definition are different. On line 106, $\\mu$ is not introduced either.\nI didn't understand where clamped sum was used. Given the limited space available, I think there's a point in putting a paragraph on it. Could the authors explain?\nWhat does the $\\|\\|\\cdot\\|\\|_{1/t^*}$ norm represent? Is it just the Hölderian norm with $\\alpha=1/t^*$? Or is it a new norm based on the new dissimilarity measure introduced?\nI thought I read a few typos:\n* Page 2, line 90: [11, 6, 17] is not in increasing order.\n* Page 7, line 246: Table A1 or Section III1 instead of Section A1?\n* Page 8, Table 1: isn't it a figure?", "limitations": "I didn't see any limitations that weren't addressed by the authors. I appreciated their honesty.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I think the paper is quite original in that the authors generalize ADABOOST using the functions $\\log_t$ and $\\exp_t$. In this way, they obtain an algorithm generalizing the former and extending the perspectives.\nI was interested in the reflections on $\\log_t$ and $\\exp_t$ and how the introduction of these functions forced the authors to rethink the rest of the procedure.\nThe authors propose theorems that are consistent with our expectations as readers of these new notions, and the order seems logical.\nFinally, the authors have chosen a complete path (new notions + theory + experiments + discussions), which makes the whole coherent in my opinion.\n", "weaknesses": "For me, a big weakness of the paper is the introduction of numerous notations that I didn't always find interesting (for example, I didn't understand the use of clamped sums) and which makes reading difficult. Certain notations, such as $t^*$, complicate reading in my opinion (because when $t$ and $t^*$ behave in opposite ways, you have to do some mental gymnastics to follow the reasoning). Finally, some notations are used differently: for example, $\\textbf{q}$ is sometimes a vector (Definition 3.1) and sometimes a matrix (Algorithm 1), or $Z_t$ is sometimes a function in $\\mu$ and sometimes not.\nSimilarly, the graphs are not intuitive for me. For example, why did the authors choose a color scale when there are only 7 values $t$ presented?\nA last small weakness of this paper for me is the fact that the authors present \"just\" an extension of the ADABOOST algorithm but I do not have the impression to know if it will help or not to improve things (it is a point of discussion). I would have liked them to highlight at least one case where the algorithm actually worked around a weakness in ADABOOST.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we thank the reader for having evaluated our paper despite its heavy notational nature. \n\n(weaknesses)\n\n> For me, a big weakness of the paper is the introduction of numerous notations that I didn't always find interesting\n\n[KBAC:A] We would like to emphasize that it has been asked that we consider additional theoretical results that will add additional notations [4pmA:B][4pmA:C][4pmA:D]. We do believe there is value in those additional results, and we believe that what the proposal we make (general rebuttal) to better present our notations will be of great help to understand the paper. We also believe that some hiccups in reading were in fact created by typos that the reviewers have spotted; removing them will substantially contribute to easing the reading.\nFor clamped summations, we in fact do believe that such classifiers could be of substantial use, in particular when training or inference is done with *reduced computational power* (either because of machines, e.g. ML at the edge, or because of compute constraints, e.g. MPC / secure multiparty computation). It is important to realize that clamping / clipping a value -- as it is usually done -- still requires *storing the full value* before “simplifying” it (or you lose arbitrary numerical precision, which can be damaging). In our case, *all steps in the computation of the output can be performed with the desired complexity* and do not alter the guarantees.\n\n> q  is sometimes a vector (Definition 3.1) and sometimes a matrix\n\nNo, $q$ is always a vector. The first index in the notation in Algorithm 1 is the iteration number, explicit in Step 2.\n\n> $Z_t$ is sometimes a function in $\\mu$ and sometimes not\n\nNo. Dependences may be implicitly noted to lighten the text. $Z$ is the normalization coefficient, which *de facto* is always a function of the leveraging coefficients (and their additional parameters, eventually). This is a consequence of (4).\n\n> For example, why did the authors choose a color scale when there are only 7 values  presented? \n\nSimply because we wanted to give the reader different ways to visually compare the curves, one using the thickness of the curves, one using the colors of the curves. By this choice, we hope to be more inclusive with respect to the readers of our paper.\n\n(questions)\n\n> I think the paper would be easier to read if the number of notations were reduced\n\nWe hope the comments above clarify some proposed changes on $Z$. \n\n> for example, $t^*$  is not compulsory in my opinion\n\nThis notation was introduced in [3]. We agree with the reviewer; however, we believe removing the $t^*$ notation (and substituting the value $\\frac{1}{2-t}$) will eventually make the expressions longer and impair the readability of the derivations.\n\n> I think some equations lack rigor. For example, $\\log_t$ and $\\exp_t$ are introduced at the same time, even though their spaces of definition are different\n\n$\\log_t$ and $\\exp_t$ are indeed inverse functions introduced by Naudts (2011), as generalizations of standard $\\log$ and $\\exp$. If the reviewer is referring to their respective domains, we can make further clarifications in the text. Did the reviewer also want us to change the width of the equations ? (this would affect the height as well and would decrease the readability of our paper)\n\n>  $\\mu$ is not introduced either.\n\n$\\mu$ is just a real number. We can put $\\mu \\in \\mathbb{R}$.\n\n>  I didn't understand where clamped sum was used\n\nAs explained in (9), clamped sums are used to define models.\n\n> What does the $\\|.\\|_{1/t^*}$  norm represent? \n\nThe $L_p$ norm with $p = 1/t^*$. Standard notation.\n\nWe acknowledge the typos found and will make the modifications. Thanks !\n\n(limitations)\n\n> I didn't see any limitations[...]. I appreciated their honesty.\n\nWe would like to very much thank the reviewer for this comment.\n\n(Referene)  \nNaudts, J. (2011). Generalized thermostatistics. Springer"}, {"review_id": "WGetAGTnRu", "reviewer": "Reviewer_tiN4", "summary": "This paper introduces a generalization of Ada Boost called “t-Ada Boost”. Boosting algorithms aggregate multiple weak classifiers into a strong classifier. Ada Boost is a well-established boosting algorithm.\nt-Ada Boost generalizes Ada Boost by introducing an additional parameter $t$, which is a “tempering” parameter. When $t=1$, the algorithm becomes identical to Ada Boost. Thus, the main focus of the paper is to analyze whether or not any benefit can be gained by selecting a different value of $t$, besides $t=1$. \nThe paper provides a thorough theoretical and experimental analysis of t-AdaBoost, for various values of $t$. The theoretical analysis shows that different values of $t$ are viable to study, and bounds the convergence rate. The experimental analysis shows that, while $t=1$ works best for some data sets, and some values of $t$ seem equivalent to AdaBoost on other data sets, there do exist some data sets for which various values of $t$ perform better than Ada Boost. So, the overall analysis suggests that $t$ would be a good additional parameter to introduce on top of AdaBoost. For some data sets, tuning $t$ could lead to improvements on top of AdaBoost, so it’s worth consideration.\n", "questions": "-\tOriginally, I went looking for the full plots from the experiments, and did not see them in the supplement. I then realized that they occurred after the references. Perhaps add an additional entry in the “Table of Contents” would be appropriate, or else make sure the experiment plots are before the references.\n-\tPlease include the code, or a link to the repository, along with the final version.\n-\tFor some data sets, the plots see a high variability from changing the decision trees (see, for example, sonar, bottom). I know you mentioned that some of this might be due to overfitting. However, I also see that, in some cases, the error repeatedly rises and falls as the number of decision trees increases. This makes me wonder whether the variability here is something intrinsic. For example, if you rerun your experiments (perhaps with a very slight variation), do you get the same results? If not, then I think it is important to execute multiple runs and give a standard deviations, or other variance measure. \n", "limitations": "I don't think this paper has any negative societal impacts.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I think the paper is well-written, and conducts a thorough analysis of the proposed technique. It is built upon well-respected approaches.", "weaknesses": "The proposed method can have numerical instabilities, resulting from exponentiation, but the authors give reasonable consideration of this in their theory and experiments. This weakness is not very significant.\n\nAlso, see my experiment question below.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "(questions)\n\n> Originally, I went looking for the full plots from the experiments, \n\nExcellent suggestion ! We will oblige.\n\n> Please include the code,\n\nWe commit to sharing all codes, inclusive of the plotting code\n\n>  If not, then I think it is important to execute multiple runs and give a standard deviations, or other variance measure.\n\nAll our experiments are done using a 10-folds stratified cross-validation (L246). Thus, they include as well the standard deviations. We chose not to plot the deviation on the pictures to keep the pictures readable (we tried with, readability was very poor for many plots). **Hovever**, we emphasize that the summary results in Table 2 use a Student paired $t$-test to assess significance (Cf Table), and thus integrate the variability for comparisons.\n"}, {"review_id": "yHXFTEkMUR", "reviewer": "Reviewer_4pmA", "summary": "The paper proposes a variant of AdaBoost algorithm based on a generalized exponential function parametrized by the temperature. The generalized exp function also induces a new criterion for splitting nodes of decision trees. The paper shows a training error bound of the AdaBoost variant. The experimental results show that the generalized AdaBoost often perform better than AdaBoost.", "questions": "-Does the temperature control the smoothness of the function or resulting distributions over the sample? If so, please discuss the relationship between the previous boosting algorithms that keep distributions smooth (e.g., SmoothBoost by Servedio or AdaFlat by Gavinsly).\n\n\n\n\n- ", "limitations": "As raised above, the paper does not show any theoretical advantages of the proposed function. That is a huge drawback of the paper and thus the paper seems pre-matured.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The strength of the contribution is the potential advantages of the proposed exp function. The exp function can derive new Bregman divergences and be applied to online learning or Boosting. In a practical sense, the new exp function and updates derived based on it seem more robust in numerical computation. \n\nAnother strength is a theoretical guarantee of its convergence rate of training error, which is the same as AdaBoost's, when given weak hypotheses with edge gamma. This iteration bound is optimal in the worst case (when the final hypothesis is a majority vote).", "weaknesses": "A crucial weakness of the paper is the lack of explanation about the generalization ability of proposed algorithms. Previous boosting algorithms, including AdaBoost, are motivated by their margin maximization properties. In fact, standard generalization bounds of weighted-voting classifiers depend on the margin over the sample.  Furthermore, there are boosting algorithms explicitly designed to optimize the soft margin optimization problem (e.g., SoftBoost or entropy regularized LPBoost). So far, the paper only considers the convergence rate of the training error. \n\nSo far, theoretical results do not improve previous ones, say, the convergence rate. So, the merit or theoretical advantages of the proposed function and the resulting boosting algorithm are unclear yet. \n\n\nI read the rebuttal comments and the new analysis seems to resolve my concern.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> A crucial weakness [...] generalization ability [...] margin maximization properties. \n\n[4pmA:A] we conjecture in L187 that similar rates of convergence (as the one we provide for the 0/1 loss) hold for margins as well; we also do not discuss generalization. We would like to point out also that margins are not discussed in the original AdaBoost paper [A] because this was not the focus of the paper. Historically, margins came later in the explanation as to why AdaBoost indeed works so well.\n\nWhile we initially thought that our paper was already dense enough to leave margins + generalization for a further step, the additional page of camera-ready might be used in part to address the reviewer’s concern. We have two good news in the direction they point at: one from the standpoint of margins, one on generalization. We apologize in advance for the use of Markdown to formally summarize those results (we were told that the 1 page pdf cannot be used for proofs).\n\n[4pmA:B] 1. Margins bounds. Instead of bounding $L_{0/1}(H)$ as in (12), we want to upperbound $E_i[f(y_iH(x_i)) \\leq \\theta]$ where $f(z)$ is increasing and typically in a bounded domain, say $[-1,1]$. [B] normalize their hypothesis space by the sum of leveraging coefficients. [C] prefer to pass the unnormalized classifier, with arbitrary real value, through the $\\tanh$ function. A simple way forward for us is to generalize the approach of [C] to TEMs as well, which is in fact easy. Define the tempered hyperbolic tangent as $\\tanh_t(z) = (1-\\exp_t(-2z))/(1+\\exp_t(-2z))$ and the margin of $H$ on example $(x, y)$ as:\n\n$\\nu((x, y), H) = \\tanh_t(yH(x)/2)$.\n\nDeveloping and reorganizing the predicate $[[\\nu((x, y), H) \\leq \\theta]]$, it is the same as predicate\n\n$-yH(x) + \\log_t\\left(\\frac{1+\\theta}{1-\\theta}\\right) - (1-t) yH(x) \\log_t\\left(\\frac{1+\\theta}{1-\\theta}\\right) \\geq 0$,\n\nWhich, with the tempered algebra of [16] (our paper) is just stating $(-yH(x) \\oplus_t \\log_t\\left(\\frac{1+\\theta}{1-\\theta}\\right)) \\geq 0$. Since $[[z \\geq 0]] \\leq \\exp_t^{2-t}(z), \\forall t \\in [0,1], \\forall z\\in \\mathbb{R}$ ($[[.]]$ = Iverson’s bracket) and $\\exp_t(u \\oplus_t v) = \\exp_t(u) \\cdot \\exp_t(v)$, we derive:\n\n$[[\\nu((x,y),H) \\leq \\theta]] \\leq \\exp_t^{2-t}\\left[ (-yH(x)) \\oplus_t \\log_t\\left(\\frac{1+\\theta}{1-\\theta}\\right)\\right] = \\exp_t^{2-t}\\left[ \\log_t\\left(\\frac{1+\\theta}{1-\\theta}\\right)\\right] \\cdot \\exp_t^{2-t}(-yH(x))$,\n\nAnd so, after simplification, we get\n\n$[[\\nu((x,y),H) \\leq \\theta]] \\leq \\left(\\frac{1+\\theta}{1-\\theta}\\right)^{2-t} \\cdot \\exp_t^{2-t}(-yH(x))$.\n\nWe then branch directly to Section II.II.2.3, eq. 24, replacing $[[\\mathrm{sign}(yH(x)) \\neq y]]$ by $[[\\nu((x,y),H) \\leq \\theta]]$, which yields in lieu of the (unnumbered) identity just before Lemma F,\n\n$\\frac{1}{m} \\cdot \\sum_i [[\\nu((x_i,y_i),H_J) \\leq \\theta]] \\leq \\left(\\frac{1+\\theta}{1-\\theta}\\right)^{2-t} \\cdot \\prod_{j=1}^{J}Z_{tj}^{2-t}$,\n\nand the rest of the proof of Theorem 2 remains unchanged. So, the left ineq. (12) (to save space) in our paper becomes the much more general inequality on **margins**:\n\n$\\frac{1}{m} \\cdot \\sum_i [[\\nu((x_i,y_i),H_J) \\leq \\theta]] \\leq {\\color{blue}\\left(\\frac{1+\\theta}{1-\\theta}\\right)^{2-t}} \\cdot\\prod_{j=1}^J \\tilde{Z}^{2-t}_{tj}$\n\nWhen $\\theta = 0$, we recover (12) and if $t=1$, the ${\\color{blue}\\mbox{blue}}$ factor above recovers the one in Theorem 1 in [C]. First discovery, thanks to the reviewer:\n\n[4pmA:C] **$t$-AdaBoost is a margin maximization algorithm** (for any $\\theta\\in[-1,1), t\\in[0,1]$)\n\nDrilling a bit reveals a perhaps more interesting phenomenon: when $\\theta < 0$ (examples badly classified, eventually with large confidence), the blue factor $\\left(\\frac{1+\\theta}{1-\\theta}\\right)^{2-t}$ can be substantially *smaller* than the same factor for $t = 1$ (this is the difference between $z$ and $z^2$ for $z\\in [0,1]$), while when $\\theta > 0$ (examples receiving the right class), the blue factor can this time be substantially *larger* than the same factor for $t = 1$. Hence, the analysis brings the interesting second discovery that\n\n[4pmA:D] **Fixing $t<1$ increases the “focus” of $t$-AdaBoost on increasing the margins of examples badly classified, compared to AdaBoost ($t=1$)**\n\nWe certainly propose to use part of the camera-ready to state and prove [4pmA:C] and [4pmA:D], with due acknowledgements.\n\n[4pmA:E] 2. Generalization guarantees (simplified analysis, summarized). Suppose $H \\in [-v,v]$, i.e. $|H|$  is bounded (e.g. we learn clamped classifiers). Then it is straightforward to see that the Lipschitz constant $L_t$ of the tempered exponential loss in $[-v,v]$ is $L_t = (2-t) \\exp_t(v)$. If $v$ is sufficiently large, then $L_t < L_1$, $\\forall t \\in [0,1)$. Hence, from [D], the empirical minimization of the tempered exponential loss is better “aligned” with generalization for $t<1$ compared to AdaBoost. Note that if $v$ can be small, a more careful analysis is required, but could lead to nice characterizations of the appropriate *loss* to minimize for convergence rate *and* generalization.\n\n> So far, theoretical results do not improve previous ones [...] unclear yet.\n\nEven without [4pmA:C], [4pmA:D] and [4pmA:E], we strongly disagree with this statement. Just one example (space limit): it has been known for decades that AdaBoost can quickly run into numerical errors [13] because of its unbounded leveraging coefficients. We show that $t<1$ just gets rid of this problem, **and** at no cost convergence-wise.  Nor margin-wise [4pmA:C], [4pmA:D]. Nor generalization-wise [4pmA:E].\n\n> Does the temperature control [...] SmoothBoost [...] AdaFlat\n\nBriefly, $t<1$ allows to control the divergence of weights – equivalently, the smoothness parameter as in D. Gavinsky – (vs explicit in both SmoothBoost and AdaFlat)\n\nReferences:\n\n[A] Freund & Schapire, JCSS 55, 119-139, 1997.\n[B] Schapire, Freund, Bartlett & Lee, ICML 1997, 322-330.\n[C] Nock & Nielsen, ECAI 2006, 509-515.\n[D] Bartlett & Mendelson, JMLR 3, 463-482, 2002.\n\n"}, {"review_id": "4kfezofXGk", "reviewer": "Reviewer_J18J", "summary": "\nThe paper introduces a generalization of the classic adaboost algorithm to apply to a family of certain exponential losses, called TEMs (tempered  exponential measures). They demonstrate the validity of their approach both theoretically  and empirically. \n\n\n", "questions": "Questions in the above comment", "limitations": "not applicable", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This technique allows their method to overcome numerical issues that typically arise when classic adaboost is employed. \nExperiments show that tuning t can lead to significant improvements, compared to adaboost. \nMoreover, the algorithm is simple and gives an interesting and practical generalization of adaboost. \n", "weaknesses": "My main issue here is the notational choices and somewhat unclear technical presentation. \n\nNotation issues : \n- Intuition regarding the used notation (in particular the terms in Eq. 4) would have been helpful, and also for the definitions of log_t and exp_t. Especially as these are key parts of the main algorithm which is very simple otherwise. \n- Equation 5 is unclear - how is \\mu defined? and the notation Z_t(\\mu)  is confusing. \n- What is Card? (Line 140) is that short for cardinality? \n- Eq 14 - I’m assuming these are indicators returning +1/-1  ? \n\n\nBecause of the notation issues above, Theorem 2 is harder to parse. However, it does resemble in form to the standard bounds on adaboost - maybe it would be nice to emphasize that comparison more explicitly.\nAlso, consider giving more explanation of the meaning of theorem 2. \nMaybe the paragraphs below it try to do that, but it was a little dense and technical. \n\nI am also confused about Figure 1 - it is essentially plotting the convergence rate, the arrows indicate the case of t=0 and t=1, but is that something easily seen by the connection of the x-axis of rho to the value of t? Is it possible to also give a plot with an axis for values of t ? \n\nTable 1 does not say what each line indicates (it did say on the appendix though) but still not sure what is the red line?  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for having evaluated our paper, despite its heavy technical nature.\n\n(weaknesses)\n\n> My main issue here is the notational choices and somewhat unclear technical presentation.\n\n[J18J:A] We apologize for the inconvenience, also probably due to several typos – fortunately spotted by the reviewers – that would have dampened the readability. As we explain in the general rebuttal, we believe there is a way forward to making it more readable. It is important as it has been asked that we consider additional theoretical results that will incur a few additional notations [4pmA:B][4pmA:C][4pmA:D]. \n\n> Intuition regarding [...]\n\n[J18J:B] We believe this is one of the first times the tempered algebra (extending that over the reals) is used. To ease the reading, we propose to add in Section I of the supplement not just a primer on TEMs, but also a primer on this algebra and its properties.\n\n> Equation 5 is unclear [...]\n\nWe used the same formalism as [11] (their eq. (1.5))\n\n> What is Card? (Line 140) is that short for cardinality?\nCorrect. We will make this explicit.\n\n> Eq 14 - I’m assuming these are indicators returning +1/-1 ?\n\nNo, this is the Iverson’s bracket (see Knuth in [12]), returning the truth value in ${0,1}$\n\n> Maybe the paragraphs below it try to do that, but it was a little dense and technical.\n\n[J18J:C] This is actually correct. Hopefully, with the additional page, we can put a bit of spacing in here to make it more readable\n\n> I am also confused about Figure 1 - it is essentially plotting the convergence rate\n\nNo. The function plotted is the one in (12). The $x$-value is in fact $\\rho_j$, which is in $[-1,1]$. The *color code* provides all different curves for all the different $t$s that are relevant. To simplify, the LHS of (12) is of the form $(K_t(\\rho))^J$. Hence, if $K_t(\\rho)$ is smaller than 1 (and the smaller it is), we have geometric convergence (and the faster it is). The plot shows that the curve for AdaBoost ($t=1$) is in fact the “highest” among all, and thus provides the “worst” guarantee of all, for $t\\in [0,1]$. We could put $t$ as an axis but this would make the plot a 3D plot, not necessarily easily parsable at this size.\n\n> Table 1 does not say what [...]\n\nThe red / thickest line is for $t=1.1$. We picked this color code because it is in fact the only value of $t$ for which the convergence is not guaranteed by our theory – but experiments obviously display that it is working as well !\n"}, {"review_id": "8icjoXfFR7", "reviewer": "Reviewer_XQ4B", "summary": "This work proposes a generalization of the popular ADABOOST algorithm based on the use of the t-logorithm/exponential. Their method is derived by replacing the standard relative entropy with the _tempered_ relative entropy (introduced in eq. 2), and solving a constrained optimization problem (eq. 3). This results in a solution (eq.4) which is a tempered generalization of ADABOOST's exponential update. Their approach recovers the standard ADABOOST updates at t->1, and maintains the exponential convergence rate of ADABOOST for values of 't' between 0 and 1. A new family of tempered losses is derived from the loss that t-ADABOOST minimizes, and experimental results using t-ADABOOST+trees show significant improvements can be gained by tuning 't'.", "questions": "- In https://arxiv.org/abs/2107.00745 the authors show t is a highly sensitive hyperparameter, and best results are obtained using tiny perturbations away from 1. This is due to numerical problems associated with using a log-t density instead of the more numerically-stable log-density. Did the authors see similar effects? Might their grid search of [0,0.2, 0.4, 0.6, 0.8, 0.9] be too coarse? Could significant gains be achieved with a finer grid search? \n- If I'm a practitioner who is willing to do a grid search to find the best t, why wouldn't I spend that effort just tuning the hyperparameters of standard ADABOOST instead? If I take a hyperparameter-tuned ADABOOST, _then_ tune t, do I get significant gains compared to tuning t with untuned ADABOOST?  \n- With the introduction of the new losses in section 6, does that introduce a second t I need to tune, or should I use the same one? \n- Does the second column of table 1 indicate clamping isn't effective? \n- Do all/most values of t pick out the same \"difficult\" examples, or are the weights totally different for diff values of t? \n- Is there any relationship between number of examples N and number of features D, and the best t? i.e do \"tall+skinny\" datasets get different optimal t's than 'short and fat' datasets, and might this offer tuning suggestions to practitioners? What about the depth of the weak classifier? \n- ADABOOST can also be used for regression - would their approach work in this setting? A few comments about regression would be useful even if not feasible under the proposed approach. ", "limitations": "There does not appear to be a \"Limitations and Broader Impacts\" statement in this work. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- This paper has both strong theoretical and experimental results, and show compelling improvements over baselines\n- ADABOOST is a very popular and performant ensemble technique, and so this work has the potential to have significant applications for ML practitioners, and could easily be implemented in existing libraries (sklearn etc )\n- The paper is well written and easy to follow, and their algorithm is accompanied with a comprehensive theoretical analysis ", "weaknesses": "- The major limitation is that performance is highly sensitive to the choice of t, and currently it looks like the only way to choose t is to perform expensive hyperparameter sweeps. Further, their Table 1 (should that be \"Figure 1\"?) seems to imply there is no rhyme or reason to the datasets which perform better with large/medium/small t. Unless practitioners have a way of learning/tuning t it's unlikely this approach will be adopted widely in practice\n- AFAICT, there are no ablation experiments testing the effect of the new losses, separate from the effect of the new exponential update. Which loss(es) were used in section 7? How do we know they work? How should a practitioner choose their loss? \n\n\n## Four dimensions \n\n**Originality:** \n- Are the tasks or methods new? \n  - Yes\n- Is the work a novel combination of well-known techniques?\n  - Yes, the work builds off developments in ADABOOST showing connections to exponential families and bregman divergences, and uses this to generalize ADABOOST by replacing exp/log with t-exp/t-log\n- Is it clear how this work differs from previous contributions? \n  - Yes, section 2 discusses this well.\n- Is related work adequately cited?\n  - Yes. \n   \n**Quality:** \n- Is the submission technically sound?\n  - Yes, the technical contributions seem sound.\n- Are claims well supported (e.g., by theoretical analysis or experimental results)? \n  - Theoretically yes, experimentally yes, with the exception of missing experiments evaluation the new losses \n- Are the methods used appropriate? \n  - Yes \n- Is this a complete piece of work or work in progress? \n  - Yes, modulo missing loss experiments \n- Are the authors careful and honest about evaluating both the strengths and weaknesses of their work?\n  - yes\n\n**Clarity:** \n- Is the submission clearly written? \n  - Yes\n- Is it well organized? \n  - Yes\n- Does it adequately inform the reader? \n  - Yes\n**Significance:**\n- Are the results important? \n  - If the authors provide a mechanism of choosing t, yes the results would be important.\n- Are others (researchers or practitioners) likely to use the ideas or build on them? \n  - Yes \n- Does the submission address a difficult task in a better way than previous work? \n  - Yes \n- Does it advance the state of the art in a demonstrable way?\n  - Yes \n-  Does it provide unique data, unique conclusions about existing data, or a unique theoretical or experimental approach?\n   - Yes \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for having evaluated our paper despite its heavy notational content.\n\n> The major limitation is that performance is highly sensitive to the choice of t, \n\n[XQ4B:A] We respectfully disagree with the argument: our theory says that regardless of the value of $t \\in [0,1]$, the regime of performances do not degrade (both from the standpoint of the 0/1 loss, but also in terms of margins [4pmA:B][4pmA:C][4pmA:D]). Our experiments show that different datasets correspond to different values of “good” $t$s on test. Thus, there is an incentive to **not** stick with a single $t$ (e.g. AdaBoost). \n\nNow, more broadly – since the reviewer makes the comments from the angle of practical considerations –, ML is a field where heavy-hyperparametered algorithms abound: in deep learning, apart from architectural choices (use BatchNorm vs. LayerNorm, add/remove skip-connection, add/remove dropout, etc.), there are several hyperparameters to tune: starting with the optimizers, say, Adam, there are four parameters (lr, beta1, beta2, eps), plus the schedule for the learning rate (number of warm-up steps, decay type, etc.), weight decay parameter, etc.. Even in the field of tabular data learning, these are very common: the number of hyperparameters of XGBoost is 2-digits. In this big world of heavily tuned algorithms, adding one extra hyperparameter does not add too much complexity (compared to deep learning methods; even a ResNet-50 model has an order of two digits or more hyperparameters + plus many more architectural design choices). **This being said**, it would be nice to get “good guesses” for $t$ beforehand. *However*, it emerged after experiments suggested (**see attached pdf**) [6L9a:H], we in fact believe that the best way to approach the question could in fact be to **learn** $t$ during training and adapt it at *each* iteration, thus equivalently ** learning the loss**, a problem getting traction in ML.\n\nWe also dispute the fact that there is “no rhyme or reason” in the results: in many cases, one could group the results for small $t$ and “big” $t$, with one group performing better than the other. That this picture changes among domains is not a downside: it is the *opposite*. It shows that the problem is worth solving *and* it is non-trivial. But it is out of the scope of our paper. We can even say it *has to be* out of the scope of our paper: almost all reviewers notice the already heavy load of material, which is probably to be made even heavier after some fruitful remarks [4pmA:B][4pmA:C][4pmA:D]. It would be a *tour-de-force* to fully explore *in addition* all dimensions of this problem. In fact, we claim it probably deserves its own paper (also considering the problem of learning the loss, see above) !\n\n\n> AFAICT, there are no ablation experiments testing the effect of the new losses\n\n[XQ4B:B] We do not understand this question: each value of $t$ gives rise to a different loss to optimize. So each time we fix a different $t$, the problem solved radically changes. Even more (Section 6), the full range of $t$ for the induction of decision trees covers the full range of known boosting rates !\n\n> How should a practitioner choose their loss?\n\nThis is exactly the question / problem of choosing $t$ [XQ4B:B] ! We hope that this, the discussion in [XQ4B:A] and the new experiments (**see attached pdf**) [6L9a:H] shows the interest of our experiments and the fact that this problem deserves its devoted “iteration” (=paper). \n\n(questions)\n\n> In https://arxiv.org/abs/2107.00745 the authors [...] Did the authors see similar effects? \n\nEssentially, no. One reason is that we address a completely different problem.\n\n> Could significant gains be achieved with a finer grid search\n\nThis is precisely relevant to [XQ4B:A].\n\n> why wouldn't I spend that effort just tuning the hyperparameters of standard ADABOOST instead? \n\nBecause we add a new “robust” (=for which the theory behind stand still) dimension for which experiments – as the reviewer has already remarked – clearly show that there is value in exploring this dimension [XQ4B:A]. And depending on the package, the way some hyperparameters are fixed might just be recycled for a standard search for better $t$ than $t=1$ (AdaBoost). We also refer to the discussion [XQ4B:A].\n\n> should I use the same one?\n\nWe use the same one. \n\n> Does the second column of table 1 indicate clamping isn't effective?\n\nQuite the opposite: it shows that it can be quite effective (for example, $t=0.9$ and **see attached pdf** [6L9a:H]) – with the additional benefit of doing computations for training / inference that remain in a prescribed “precision” interval, which could especially be relevant to specific applications [KBAC:A].\n\n> Do all/most values of t pick out the same \"difficult\" examples,\n\nGood question. From a purely theoretical standpoint, we would not expect this to be true, in particular for the comparison clamped / unclamped models.\n\n> Is there any relationship between number of examples N and number of features D, and the best t? \n\nThere does not seem to be. We conjecture this has more to do with properties of the full domain itself.\n\n> ADABOOST can also be used for regression\n\nGood question, we conjecture it is possible, though some care-and-caution has to be applied, in particular for clamped models.\n"}]

Author rebuttal:
We would like to thank all six reviewers for their work and appreciate the global positive tone of reviews given the notation-heavy nature of our paper. To ease the cross-search among the pieces of our rebuttal, we have put tokens of the form **[Reviewer-Id:Letter]** in rebuttals, making it easily to search for cross-references among rebuttals. Each rebuttal proceeds by quoting the review and replying, in the order of the review’s comments. References shown like [number] refer to our paper’s bibliography. References shown like [letter] refer to references put in each rebuttal.

This is a general rebuttal, summarizing the major changes, all of which could be easily done given the additional page in the camera-ready.

## From the standpoint of its theoretical content

We note that our paper *might* see an increase in notations after new results that we got for a rebuttal on margins and generalization **[4pmA:B][4pmA:C][4pmA:D][4pmA:E]**. We believe however that reviewers have done a fantastic job of typo-spotting and that the final version of our paper will surely gain in readability. We apologize however for having used the keen eye of six reviewers to find those.

To ease reading our paper, we propose 

1. To correct all typos (we believe they contributed to hiccups in reading)
2. To put in the camera-ready before Section I in the supplement a table of notations, grouped by topics (models, TEMs, properness, etc.), eventually by paper Section, to help the reading of the paper
3. To strengthen part I in the supplement to include not just a primer on TEMs but also on the tempered algebra of [16]

## From the standpoint of its experimental content

Experiments vs overfitting suggested by **[6L9a:H]** have been put in **the attached .pdf**, and present an interesting direction which we believe could present value, briefly mentioned in the main file and then put in the supplement. 


Meta-review: This meta review is based on the reviews, the authors rebuttal and the discussions with the reviewers, discussions with the SAC, and ultimately my own judgement on the paper. There was a consensus that the paper contributes sound and interesting contributions. I feel this work deserves to be featured at NeurIPS and will attract interest from the community. I would like to personally invite the authors to carefully revise their manuscript to take into account the remarks and suggestions made by reviewers. Congratulations!
Decision: Accept (poster)