mlsanityData to 7 Oct 2026

Error Scaling Laws for Kernel Classification under Source and Capacity Conditions

arXiv 2201.12655 ↗First posted 29 Jan 2022stat.ML cs.LGcited by 17

Not on the map. Why?

Abstract (arXiv)

We consider the problem of kernel classification. While worst-case bounds on the decay rate of the prediction error with the number of samples are known for some classifiers, they often fail to accurately describe the learning curves of real data sets. In this work, we consider the important class of data sets satisfying the standard source and capacity conditions, comprising a number of real data sets as we show numerically. Under the Gaussian design, we derive the decay rates for the misclassification (prediction) error as a function of the source and capacity coefficients. We do so for two standard kernel classification settings, namely margin-maximizing Support Vector Machines (SVM) and ridge classification, and contrast the two methods. We find that our rates tightly describe the learning curves for this class of data sets, and are also observed on real data. Our results can also be seen as an explicit prediction of the exponents of a scaling law for kernel classification that is accurate on some real datasets.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). Builds on 28 of its 53 references that are in the map. First posted on arXiv 29 Jan 2022.

Builds on

28 of 53 references.

References · 28

  1. 2020Scaling Laws for Neural Language Modelscited by 6,411
  2. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,283
  3. 2017Deep Learning Scaling is Predictable, Empiricallycited by 556
  4. 2019Benign Overfitting in Linear Regressioncited by 544
  5. 2020Scaling Laws for Autoregressive Generative Modelingcited by 510
  6. 2021Explaining Neural Scaling Lawscited by 353
  7. 2017High-dimensional dynamics of generalization error in neural networkscited by 238
  8. 2019A Constructive Prediction of the Generalization Error Across Scalescited by 202
  9. 2020Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networkscited by 200
  10. 2020Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networkscited by 166
  11. 2015High-Dimensional Asymptotics of Prediction: Ridge Regression and Classificationcited by 146
  12. 2020Classification vs regression in overparameterized regimes: Does the loss function matter?cited by 97
16 more
  1. 2021Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regimecited by 95
  2. 2021Learning Curve Theorycited by 79
  3. 2020Statistical Mechanics of Deep Linear Neural Networks: The Back-Propagating Kernel Renormalizationcited by 71
  4. 2018Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passescited by 69
  5. 2018Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spacescited by 59
  6. 2021Separation of Scales and a Thermodynamic Description of Feature Learning in Some CNNscited by 53
  7. 2020Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimizationcited by 51
  8. 2021Last iterate convergence of SGD for Least-Squares in the Interpolation regimecited by 41
  9. 2020Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Modelcited by 39
  10. 2020Kernel regression in high dimensions: Refined analysis beyond double descentcited by 39
  11. 2020On the proliferation of support vectors in high dimensionscited by 32
  12. 2019Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordancecited by 28
  13. 2021Learning curves for Gaussian process regression with power-law priors and targetscited by 14
  14. 2019Kernel Truncated Randomized Ridge Regression: Optimal Rates and Low Noise Accelerationcited by 12
  15. 2020The Nystr"om method for convex loss functionscited by 8
  16. 2021Support vector machines and linear regression coincide with very high-dimensional featurescited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 9; 2025: 4; 2026: 2.

17 papers.

Sort:

By area:

  1. 2024A Tale of Tails: Model Collapse as a Change of Scaling Lawscited by 127
  2. 2024Model Collapse Demystified: The Case of Regressioncited by 80
  3. 2024Strong Model Collapsecited by 62
  4. 2024How Feature Learning Can Improve Neural Scaling Lawscited by 55
  5. 2024Scaling and renormalization in high-dimensional regressioncited by 45
  6. 2023Bayes-optimal Learning of Deep Random Networks of Extensive-widthcited by 41
  7. 2026There Will Be a Scientific Theory of Deep Learningcited by 21
  8. 2023High-dimensional Asymptotics of Denoising Autoencoderscited by 19
  9. 2025Deep Linear Network Training Dynamics from Random Initialization: Data, Width, Depth, and Hyperparameter Transfercited by 17
  10. 2024A Random Matrix Theory Perspective on the Spectrum of Learned Features and Asymptotic Generalization Capabilitiescited by 14
  11. 2024High-dimensional learning of narrow neural networkscited by 12
  12. 2025Kernel ridge regression under power-law data: spectrum and generalizationcited by 8
5 more
  1. 2024AlphaZero Neural Scaling and Zipf's Law: a Tale of Board Games and Power Lawscited by 7
  2. 2026Optimal scaling laws in learning hierarchical multi-index modelscited by 6
  3. 2025Quantifying Overfitting along the Regularization Path for Two-Part-Code MDL in Supervised Classificationcited by 2
  4. 2024No Free Lunch From Random Feature Ensembles: Scaling Laws and Near-Optimality Conditionscited by 1
  5. 2025On the Existence of Consistent Adversarial Attacks in High-Dimensional Linear Classificationcited by 1