Research map / Learning theory and algorithms / Kernels and regression theory
Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures
Yuan Cao, Quanquan Gu, Misha Belkin
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the general bound in the low-SNR setting | Maximum margin classifier · Low-SNR sub-Gaussian mixtures | mean norm condition for o(1) population risk: \| \bmu \|_2^4 = \omega(d / n); [prior] \| \bmu \|_2^4 = \omega( (d / n)^{3/2}) | Improved |
| Allow anisotropic covariance with polynomially decaying eigenvalues | Maximum margin classifier · Anisotropic sub-Gaussian mixtures | mean norm condition for o(1) population risk: \| \bmu \|_2 = \omega( d^{1/4 - \alpha/2} ); \omega( (\log(d) )^{1/4} ); \omega( 1 ) | Improved |
| Align the mean with an eigendirection associated with a smaller covariance eigenvalue | Maximum margin classifier · Sub-Gaussian mixtures with anisotropic covariance | population risk: R(\hat\btheta_{\text{SVM}}) \leq \exp\Bigg( \frac{ - C' n \| \bmu \|_2^4 }{ n \lambda_k\cdot \| \bmu \|_{2}^2+ \| \bSigm | Improved |
| Apply the general risk bound to the rare/weak feature model | Maximum margin classifier · Rare/weak feature model | population risk bound: our bound is tighter by a factor of n in the exponent | Improved |
| Use the maximum-margin classifier under the stated high-dimensional covariance conditions | Maximum margin classifier · Gaussian mixtures, two lower-bound regimes | population risk bound tightness: lower bounds match our population risk upper bound up to some absolute constants | Improved |
| Use a rapidly decaying covariance spectrum with α ∈ (1/2,1) | Maximum margin classifier · Anisotropic sub-Gaussian mixtures | dimension dependence of mean norm condition: \| \bmu \|_2 = \omega( 1 ) | Improved |
| Use the paper's stated rare/weak feature setting | Maximum margin classifier · Rare/weak feature model | population risk: when s = \omega(d^2), o(1) population risk is achievable | Improved |
Closest papers by meaning
- Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime (JMLR 2021 · similarity 0.90)
- Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation (NeurIPS 2021 · similarity 0.89)
- The Implicit Bias of Benign Overfitting (JMLR 2023 · similarity 0.89)
- Minimax Optimal Early-Stopped Gradient Descent for Gaussian Mixture Classification (NeurIPS 2026 · similarity 0.87)
- The optimality of kernel classifiers in Sobolev space (ICLR 2024 · similarity 0.85)
- Rethinking Benign Overfitting in Two-Layer Neural Networks (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
