Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures

• URL: http://arxiv.org/abs/2104.13628v1
• Date: Wed, 28 Apr 2021 08:25:16 GMT
• Title: Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures
• Authors: Yuan Cao and Quanquan Gu and Mikhail Belkin
• Abstract summary: We study the phenomenon of the maximum margin classifier for linear classification problems. Our results precisely characterize the condition under which benign overfitting can occur.
• Score: 100.55816326422773
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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" (Bartlett et al. (2020)) 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.

Related papers

• Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization [59.038366742773164]
  Linears and leaky ReLU trained by gradient flow on logistic loss have an implicit bias towards satisfying the Karush-KuTucker (KKT) conditions. In this work we establish a number of settings where the satisfaction of these conditions implies benign overfitting in linear classifiers and in two-layer leaky ReLU networks.
  arXiv  Detail & Related papers  (2023-03-02T18:24:26Z)
• The Implicit Bias of Benign Overfitting [31.714928102950584]
  benign overfitting is where a predictor perfectly fits noisy training data while attaining near-optimal expected loss. We show how this can be extended beyond standard linear regression. We then turn to classification problems, and show that the situation there is much more favorable.
  arXiv  Detail & Related papers  (2022-01-27T12:49:21Z)
• Self-Certifying Classification by Linearized Deep Assignment [65.0100925582087]
  We propose a novel class of deep predictors for classifying metric data on graphs within PAC-Bayes risk certification paradigm. Building on the recent PAC-Bayes literature and data-dependent priors, this approach enables learning posterior distributions on the hypothesis space.
  arXiv  Detail & Related papers  (2022-01-26T19:59:14Z)
• Benign Overfitting in Adversarially Robust Linear Classification [91.42259226639837]
  "Benign overfitting", where classifiers memorize noisy training data yet still achieve a good generalization performance, has drawn great attention in the machine learning community. We show that benign overfitting indeed occurs in adversarial training, a principled approach to defend against adversarial examples.
  arXiv  Detail & Related papers  (2021-12-31T00:27:31Z)
• Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation [39.02017410837255]
  We study benign overfitting in multiclass linear classification. We consider the following training algorithms on separable data. We derive novel bounds on the accuracy of the MNI classifier.
  arXiv  Detail & Related papers  (2021-06-21T05:34:36Z)
• Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions [79.35722941720734]
  Generalised linear models for multi-class classification problems are one of the fundamental building blocks of modern machine learning tasks. We prove exacts characterising the estimator in high-dimensions via empirical risk minimisation. We discuss how our theory can be applied beyond the scope of synthetic data.
  arXiv  Detail & Related papers  (2021-06-07T16:53:56Z)
• Scalable Marginal Likelihood Estimation for Model Selection in Deep Learning [78.83598532168256]
  Marginal-likelihood based model-selection is rarely used in deep learning due to estimation difficulties. Our work shows that marginal likelihoods can improve generalization and be useful when validation data is unavailable.
  arXiv  Detail & Related papers  (2021-04-11T09:50:24Z)
• Binary Classification of Gaussian Mixtures: Abundance of Support Vectors, Benign Overfitting and Regularization [39.35822033674126]
  We study binary linear classification under a generative Gaussian mixture model. We derive novel non-asymptotic bounds on the classification error of the latter. Our results extend to a noisy model with constant probability noise flips.
  arXiv  Detail & Related papers  (2020-11-18T07:59:55Z)
• Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime [16.1176305285103]
  We prove bounds on the population risk of the maximum margin algorithm for two-class linear classification. We analyze this algorithm applied to random data including misclassification noise.
  arXiv  Detail & Related papers  (2020-04-25T00:06:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.