Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures
Modern machine learning systems such as deep neural networks are often highly over-parameterized so that they can fit the noisy training data exactly, yet they can still achieve small test errors in practice. In this paper, we study this "benign overfitting" phenomenon of the maximum margin classifier for linear classification problems. Specifically, we consider data generated from sub-Gaussian mixtures, and provide a tight risk bound for the maximum margin linear classifier in the over-parameterized setting. Our results precisely characterize the condition under which benign overfitting can occur in linear classification problems, and improve on previous work. They also have direct implications for over-parameterized logistic regression.
Code (0)
등록된 구현이 없습니다.
Tasks
ClassificationGeneral ClassificationregressionSimilar Papers 제목 키워드 기반
Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime
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 equival…
Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
In overparameterized logistic regression, gradient descent (GD) iterates diverge in norm while converging in direction to the maximum $\ell_2$-margin solution -- a phenomenon known as the implicit bias of GD. This work i…
regressionPAC-Bayes Bounds for Gibbs Posteriors via Singular Learning Theory
We derive explicit non-asymptotic PAC-Bayes generalization bounds for Gibbs posteriors, that is, data-dependent distributions over model parameters obtained by exponentially tilting a prior with the empirical risk. Unlik…
Maximum Margin Multiclass Nearest Neighbors
We develop a general framework for margin-based multicategory classification in metric spaces. The basic work-horse is a margin-regularized version of the nearest-neighbor classifier. We prove generalization bounds that …
Generalization BoundsLast Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression
Stochastic gradient descent (SGD) has been shown to generalize well in many deep learning applications. In practice, one often runs SGD with a geometrically decaying stepsize, i.e., a constant initial stepsize followed b…
regression