On the Dual Formulation of Boosting Algorithms

By Chunhua Shen, Hanxi Li. 2009

140 citations recorded by the source corpus.

We study boosting algorithms from a new perspective. We show that the Lagrange dual problems of ℓ1-norm-regularized AdaBoost, LogitBoost, and soft-margin LPBoost with generalized hinge loss are all entropy maximization problems. By looking at the dual problems of these boosting algorithms, we show that the success of boosting algorithms can be understood in terms of maintaining a better margin distribution by maximizing margins and at the same time controlling the margin variance. We also theoretically prove that approximately, ℓ1-norm-regularized AdaBoost maximizes the average margin, instead of the minimum margin. The duality formulation also enables us to develop column-generation-based optimization algorithms, which are totally corrective. We show that they exhibit almost identical classification results to that of standard stagewise additive boosting algorithms but with much faster convergence rates. Therefore, fewer weak classifiers are needed to build the ensemble using our proposed optimization technique.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs (2019, methodology): “We ﬁrst propose an approach to learn personalized nonlinear classiﬁers as combinations of a set of base predictors inspired from l 1 -Adaboost (Shen and Li, 2010).”
A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning (2014, methodology): “D C ] 1 2 Ja n 20 15 learning, such as LASSO regression (Tibshirani, 1996), support vector machines (Cortes and Vapnik, 1995), multiple kernel learning (Bach et al., 2004), `1-Adaboost (Shen and Li, 2010) and sparse coding (Lee et al., 2006).”
Hopular: Modern Hopfield Networks for Tabular Data (2022, unknown): “4 in (Shen & Li, 2010): L = ln N∑ i=1 exp(− yi g(zi)) .”
Parallel Coordinate Descent for the Adaboost Problem (2013, unknown): “The functionF has a coordinate-wise Lipschitz gradient with constants(Li)1≤i≤n such that Li = max 1≤j≤m A2j,i , and if one chooses aτ -nice samplingŜ, then (F, Ŝ) ∼ ESO(β, L) .”
On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learning (2017, background): “…invoking the Karush-Kuhn-Tucker (KKT) conditions, the unique maximizer of (6) is the softmax function evaluated at z ∈ n , i.e., argmax It has been noted in [20], [39], [51], [52] that the argument of the left-hand side of (8), represents the so called “free energy” in statistical thermo-dynamics.”