On the equivalence of weak learnability and linear separability: new relaxations and efficient boosting algorithms

By Shai Shalev-Shwartz, Yoram Singer. 2010

84 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition, Optimization & Training, Statistical Learning Theory

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

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

Spectrally-normalized margin bounds for neural networks (2017, background): “On the other hand, in the boosting literature, special types of regularization were developed to maximize margins (Shalev-Shwartz and Singer, 2008); perhaps a similar development can be performed here?”
The Implicit Bias of Gradient Descent on Separable Data (2017, background): “Indeed, the coordinate descent interpretation of AdaBoost shows that coordinate descent on the exp-loss for a linearly separable problem is related to finding the maximum L1 margin solution (Schapire et al., 1998; Rosset et al., 2004a; Shalev-Shwartz & Singer, 2010).”
A Quasi-Newton Approach to Nonsmooth Convex Optimization Problems in Machine Learning (2008, background): “(2007), Shalev-Shwartz and Singer (2008), and Warmuth et al. (2008). The key idea is that at each iterate Algorithm 2 decreases the upper bound (i) on the distance from the optimality, and the decrease in (i) is characterized by the recurrence (i) − (i+1) ≥ c( (i))2 with c > 0 (Theorem 7).”
On the Dual Formulation of Boosting Algorithms (2009, background): “In [24], it is proved that soft-margin LPBoost actually maximizes the average of 1 /D smallest margins.”
Gradient Descent Maximizes the Margin of Homogeneous Neural Networks (2019, methodology): “Margin maximization phenomenon is also studied for boosting methods (Schapire et al., 1998; Schapire and Freund, 2012; Shalev-Shwartz and Singer, 2010; Telgarsky, 2013) and Normalized Perceptron (Ramdas and Pena, 2016).”
Characterizing Implicit Bias in Terms of Optimization Geometry (2018, background): “…(cid:96) 1 regularization (Schapire & Freund, 2012), and later on AdaBoost with small enough stepsize was shown to converge in direction precisely to the maximum (cid:96) 1 margin solution, just as is guaranteed by Theorem 5 (Zhang et al., 2005; Shalev-Shwartz & Singer, 2010; Telgarsky, 2013).”
Trading Accuracy for Sparsity in Optimization Problems with Sparsity Constraints (2010, result): “We refer the reader to [3, 23] and see also a similar derivation in [26].”