Boosting with Tempered Exponential Measures

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'.

Strengths

- This paper has both strong theoretical and experimental results, and show compelling improvements over baselines - 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 ) - 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 - 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? ## Four dimensions **Originality:** - Are the tasks or methods new? - Yes - Is the work a novel combination of well-known techniques? - 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 - Is it clear how this work differs from previous contributions? - Yes, section 2 discusses this well. - Is related work adequately cited? - Yes. **Quality:** - Is the submission technically sound? - Yes, the technical contributions seem sound. - Are claims well supported (e.g., by theoretical analysis or experimental results)? - Theoretically yes, experimentally yes, with the exception of missing experiments evaluation the new losses - Are the methods used appropriate? - Yes - Is this a complete piece of work or work in progress? - Yes, modulo missing loss experiments - Are the authors careful and honest about evaluating both the strengths and weaknesses of their work? - yes **Clarity:** - Is the submission clearly written? - Yes - Is it well organized? - Yes - Does it adequately inform the reader? - Yes **Significance:** - Are the results important? - If the authors provide a mechanism of choosing t, yes the results would be important. - Are others (researchers or practitioners) likely to use the ideas or build on them? - Yes - Does the submission address a difficult task in a better way than previous work? - Yes - Does it advance the state of the art in a demonstrable way? - Yes - Does it provide unique data, unique conclusions about existing data, or a unique theoretical or experimental approach? - Yes

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? - 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? - 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? - Does the second column of table 1 indicate clamping isn't effective? - Do all/most values of t pick out the same "difficult" examples, or are the weights totally different for diff values of t? - 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? - 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.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

There does not appear to be a "Limitations and Broader Impacts" statement in this work.

Summary

The 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.

Strengths

This technique allows their method to overcome numerical issues that typically arise when classic adaboost is employed. Experiments show that tuning t can lead to significant improvements, compared to adaboost. Moreover, the algorithm is simple and gives an interesting and practical generalization of adaboost.

Weaknesses

My main issue here is the notational choices and somewhat unclear technical presentation. Notation issues : - 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. - Equation 5 is unclear - how is \mu defined? and the notation Z_t(\mu) is confusing. - What is Card? (Line 140) is that short for cardinality? - Eq 14 - I’m assuming these are indicators returning +1/-1 ? Because 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. Also, consider giving more explanation of the meaning of theorem 2. Maybe the paragraphs below it try to do that, but it was a little dense and technical. I 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 ? Table 1 does not say what each line indicates (it did say on the appendix though) but still not sure what is the red line?

Questions

Questions in the above comment

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

not applicable

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.

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. Another 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. So 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. I read the rebuttal comments and the new analysis seems to resolve my concern.

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). -

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

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.

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. t-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$. The 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.

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. Also, see my experiment question below.

Questions

- Originally, 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. - Please include the code, or a link to the repository, along with the final version. - For 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.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

I don't think this paper has any negative societal impacts.

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.

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. I 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. The authors propose theorems that are consistent with our expectations as readers of these new notions, and the order seems logical. Finally, the authors have chosen a complete path (new notions + theory + experiments + discussions), which makes the whole coherent in my opinion.

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. Similarly, 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? A 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.

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. I 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? What 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? I thought I read a few typos: * Page 2, line 90: [11, 6, 17] is not in increasing order. * Page 7, line 246: Table A1 or Section III1 instead of Section A1? * Page 8, Table 1: isn't it a figure?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

I didn't see any limitations that weren't addressed by the authors. I appreciated their honesty.

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. The 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.

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. The 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.

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). In 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). Parts 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).

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? The 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$. Are 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? In 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?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

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. The 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).

Thank you for the follow-up

I have read your rebuttal comments, and appreciate the clarifications.

Thank you for your response

Hi - I found your rebuttal convincing and appreciate the thoroughness of your response. None of the issues I raised were make-or-break, so I will keep my scores as they are. Looking forward to reading the final camera ready!

I have always some questions

I thank the authors for clarifying the text. I hope it is more understandable by the uninitiated. > No, $q$ is always a vector. The first index in the notation in Algorithm 1 is the iteration number, explicit in Step 2. Ok, thanks. As $q$ is a vector, I think it would be better to use the $q^(1)$ notation for iteration. > No. 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 Sorry, I think my comment was misunderstood. In math, if $f$ is a function, $f(x)$ is a scalar. My problem is your choice to consider $Z_t$ to be a scalar when $Z_t(\mu)$ is the scalar. I understand that it is painful to write it every time but I find it more precise to add it. > (and their additional parameters, eventually). If you say that there may be other parameters, I think it is all the more important to add them. > This 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. We agree on the advantages/problems of both choices, and whether to take $t^*$ or $\frac{1}{2-t}$ is obviously just a matter of point of view. Mine remains that since you're talking about $t$ convergence, it's clearer for the reader to understand what's going on if they see $\frac{1}{2-t}$ directly rather than $t^*$. Alternatively, you could put convergences directly in $t^*$ to avoid any intellectual gymnastics. > 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 ? My remark was simply to remind you that $\log_t$ was defined on $\mathbb{R}^+_{\star}$ and $\exp_t$ on $\mathbb{R}$. Once again, I understand that, if there is no clarification, the first idea is to copy the definition sets of $\log$ and $\exp$. But since these are extensions, what proof do we have that the set isn't different? A bit like the extension of the logarithm to the imaginary, which can be defined almost anywhere. > We can put $\mu\in\mathbb{R}$. Thanks. > As explained in (9), clamped sums are used to define models. Sorry, my question was *where $H_J^{(\delta)}$ was used?* I must have had a moment's inattention because it was line 145. Sorry for my question. > The $L_p$ norm with $p=1/t^*$. Thank you for your reply. I don't remember why, on first reading, it bothered me. Sorry about that.