2020

Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime

Chatterji, Niladri S., Long, Philip M.

Understand

We prove bounds on the population risk of the maximum margin algorithm for two-class linear classification.

For linearly separable training data, the maximum margin algorithm has been shown in previous work to be equivalent to a limit of training with logistic loss using gradient descent, as the training error is driven to zero.
We analyze this algorithm applied to random data including misclassification noise.
Our assumptions on the clean data include the case in which the class-conditional distributions are standard normal distributions.

Built on

“Structural risk minimization over data-dependent hierarchies”
John Shawe-Taylor, Peter Bartlett, Robert Williamson and Martin Anthony · 1940
Earlier work this paper cites.
“Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition”
Thomas Cover · 1965
Earlier work this paper cites.
“Estimation of dependences based on empirical data”
Vladimir Vapnik · 1982
Earlier work this paper cites.
“Learning from noisy examples”
Dana Angluin and Philip Laird · 1988
Earlier work this paper cites.
“Learning with an unreliable teacher”
Gabor Lugosi · 1992
Earlier work this paper cites.
“Toward efficient agnostic learning”
Michael Kearns, Robert Schapire and Linda Sellie · 1994
Earlier work this paper cites.
“Chernoff–Hoeffding bounds for applications with limited independence”
Jeanette Schmidt, Alan Siegel and Aravind Srinivasan · 1995
Earlier work this paper cites.
“The nature of statistical learning theory”
Vladimir Vapnik · 1995
Earlier work this paper cites.
“Balls and Bins: A Study in Negative Dependence”
Devdatt Dubhashi and Desh Ranjan · 1998
Earlier work this paper cites.
“Efficient noise-tolerant learning from statistical queries”
Michael Kearns · 1998
Earlier work this paper cites.
“Sample-efficient strategies for learning in the presence of noise”
Nicolo Cesa-Bianchi, Eli Dichterman, Paul Fischer, Eli Shamir and Hans Simon · 1999
Earlier work this paper cites.
“On PAC learning using Winnow, Perceptron, and a Perceptron-like algorithm”
Rocco Servedio · 1999
Earlier work this paper cites.
“Equitable coloring extends Chernoff-Hoeffding bounds”
Sriram Pemmaraju · 2001
Earlier work this paper cites.
“Lectures on the coupling method”
Torgny Lindvall · 2002
Earlier work this paper cites.
“On discriminative vs. generative classifiers: A comparison of logistic regression and naive Bayes”
Andrew Ng and Michael Jordan · 2002
Earlier work this paper cites.
“An introduction to multivariate statistical analysis”, Wiley Series in Probability and Statistics
T.W. Anderson · 2003
Earlier work this paper cites.
“Some theory for Fisher’s linear discriminant function, ‘naive Bayes’, and some alternatives when there are many more variables than observations”
Peter Bickel and Elizaveta Levina · 2004
Earlier work this paper cites.
“Understanding deep learning requires rethinking generalization”
Original
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht and Oriol Vinyals · 2004
Earlier work this paper cites.
“Boosting in the presence of noise”
Adam Kalai and Rocco Servedio · 2005
Earlier work this paper cites.
“Risk bounds for statistical learning”
Pascal Massart and Élodie Nédélec · 2006
Earlier work this paper cites.
“Statistical performance of support vector machines”
Gilles Blanchard, Olivier Bousquet and Pascal Massart · 2008
Earlier work this paper cites.
“Higher criticism thresholding: Optimal feature selection when useful features are rare and weak”
David Donoho and Jiashun Jin · 2008
Earlier work this paper cites.
“High dimensional classification using features annealed independence rules”
Jianqing Fan and Yingying Fan · 2008
Earlier work this paper cites.
“Agnostically learning halfspaces”
Adam Kalai, Adam Klivans, Yishay Mansour and Rocco Servedio · 2008
Earlier work this paper cites.
“Neural network learning: Theoretical foundations”
Martin Anthony and Peter Bartlett · 2009
Earlier work this paper cites.
“Introduction to algorithms”
Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein · 2009
Earlier work this paper cites.
“The elements of statistical learning: data mining, inference, and prediction”
Trevor Hastie, Robert Tibshirani and Jerome Friedman · 2009
Earlier work this paper cites.

Similar

“Impossibility of successful classification when useful features are rare and weak”
Jiashun Jin · 2009
Cited alongside, same era.
“Learning halfspaces with malicious noise”
Adam Klivans, Philip Long and Rocco Servedio · 2009
Cited alongside, same era.
“Random classification noise defeats all convex potential boosters”
Philip Long and Rocco Servedio · 2010
Cited alongside, same era.
“A direct estimation approach to sparse linear discriminant analysis”
Tony Cai and Weidong Liu · 2011
Cited alongside, same era.
“Probability and Computation, Lecture 3” Scribes: A. Chiesa and Z. Zhu. (Downloaded 4/13/20)., http://people.csail.mit.edu/costis/6896sp11/lec3s.pdf , 2011
Constantinos Daskalakis · 2011
Cited alongside, same era.
“Pattern classification”
Richard Duda, Peter Hart and David Stork · 2012
Cited alongside, same era.
“On the necessity of irrelevant variables”
David Helmbold and Philip Long · 2012
Cited alongside, same era.
“Learning with noisy labels”
Nagarajan Natarajan, Inderjit Dhillon, Pradeep Ravikumar and Ambuj Tewari · 2013
Cited alongside, same era.
“Classification with asymmetric label noise: Consistency and maximal denoising”
Clayton Scott, Gilles Blanchard and Gregory Handy · 2013
Cited alongside, same era.
“In search of the real inductive bias: On the role of implicit regularization in deep learning”
Original
Behnam Neyshabur, Ryota Tomioka and Nathan Srebro · 2014
Cited alongside, same era.
“Efficient learning of linear separators under bounded noise”
Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab and Ruth Urner · 2015
Cited alongside, same era.
“A finite sample analysis of the Naive Bayes classifier.”
Daniel Berend and Aryeh Kontorovich · 2015
Cited alongside, same era.

Then

“High dimensional linear discriminant analysis: optimality, adaptive algorithm and missing data”
Tony Cai and Linjun Zhang · 2019
Later among the works it cites.
“Distribution-independent PAC learning of halfspaces with Massart noise”
Ilias Diakonikolas, Themis Gouleakis and Christos Tzamos · 2019
Later among the works it cites.
“Surprises in high-dimensional ridgeless least squares interpolation”
Original
Trevor Hastie, Andrea Montanari, Saharon Rosset and Ryan Tibshirani · 2019
Later among the works it cites.
“The implicit bias of gradient descent on nonseparable data”
Ziwei Ji and Matus Telgarsky · 2019
Later among the works it cites.
“The generalization error of random features regression: Precise asymptotics and double descent curve”
Original
Song Mei and Andrea Montanari · 2019
Later among the works it cites.
“The generalization error of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime”
Original
Andrea Montanari, Feng Ruan, Youngtak Sohn and Jun Yan · 2019
Later among the works it cites.
“Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate”
Mor Nacson, Nathan Srebro and Daniel Soudry · 2019
Later among the works it cites.
“Uniform convergence may be unable to explain generalization in deep learning”
Vaishnavh Nagarajan and J Kolter · 2019
Later among the works it cites.
“A modern maximum-likelihood theory for high-dimensional logistic regression”
Pragya Sur and Emmanuel Candès · 2019
Later among the works it cites.
“Benign overfitting in linear regression”
Peter Bartlett, Philip Long, Gábor Lugosi and Alexander Tsigler · 2020
Closest in time.
“Two models of double descent for weak features”
Mikhail Belkin, Daniel Hsu and Ji Xu · 2020
Closest in time.
“The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression”
Emmanuel Candès and Pragya Sur · 2020
Closest in time.
“Classification with imperfect training labels”
Timothy Cannings, Yingying Fan and Richard Samworth · 2020
Closest in time.
“Finite-sample analysis of interpolating linear classifiers in the overparameterized regime”
Original
Niladri Chatterji and Philip Long · 2020
Closest in time.
“A Model of Double Descent for High-Dimensional Logistic Regression”
Zeyu Deng, Abla Kammoun and Christos Thrampoulidis · 2020
Closest in time.
“The optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization”
Dmitry Kobak, Jonathan Lomond and Benoit Sanchez · 2020
Closest in time.
“Just interpolate: Kernel “ridgeless” regression can generalize”
Tengyuan Liang and Alexander Rakhlin · 2020
Closest in time.
“On the multiple descent of minimum-norm interpolants and restricted lower isometry of kernels”
Tengyuan Liang, Alexander Rakhlin and Xiyu Zhai · 2020
Closest in time.
“A precise high-dimensional asymptotic theory for boosting and min- ℓ 1 \ell_{1} -norm interpolated classifiers”
Original
Tengyuan Liang and Pragya Sur · 2020
Closest in time.
“Classification vs regression in overparameterized regimes: Does the loss function matter?”
Original
Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu and Anant Sahai · 2020
Closest in time.
“Harmless interpolation of noisy data in regression”
Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian and Anant Sahai · 2020
Closest in time.
“On the Error Resistance of Hinge-Loss Minimization”
Kunal Talwar · 2020
Closest in time.
“Benign Overfitting in Binary Classification of Gaussian Mixtures”
Original
Ke Wang and Christos Thrampoulidis · 2020
Closest in time.
“Kernel and rich regimes in overparametrized models”
Blake Woodworth, Suriya Gunasekar, Jason Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry and Nathan Srebro · 2020
Closest in time.
“On the Implicit Bias of Initialization Shape: Beyond Infinitesimal Mirror Descent”
Original
Shahar Azulay, Edward Moroshko, Mor Nacson, Blake Woodworth, Nathan Srebro, Amir Globerson and Daniel Soudry · 2021
Closest in time.
“On the proliferation of support vectors in high dimensions”
Daniel Hsu, Vidya Muthukumar and Ji Xu · 2021
Closest in time.
“Interpolating Classifiers Make Few Mistakes”
Original
Tengyuan Liang and Benjamin Recht · 2021
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…