Error Scaling Laws for Kernel Classification under Source and Capacity Conditions

• URL: http://arxiv.org/abs/2201.12655v3
• Date: Wed, 6 Sep 2023 12:20:43 GMT
• Title: Error Scaling Laws for Kernel Classification under Source and Capacity Conditions
• Authors: Hugo Cui, Bruno Loureiro, Florent Krzakala, Lenka Zdeborov\'a
• Abstract summary: We consider the important class of data sets satisfying the standard source and capacity conditions. We derive the decay rates for the misclassification (prediction) error as a function of the source and capacity coefficients. Our results can be seen as an explicit prediction of the exponents of a scaling law for kernel classification.
• Score: 26.558090928198187
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Limits to classification performance by relating Kullback-Leibler divergence to Cohen's Kappa [0.0]
  Theory and methods are discussed in detail and then applied to Monte Carlo data and real datasets. In all cases this analysis shows that the algorithms could not have performed any better due to the underlying probability density functions for the two classes.
  arXiv  Detail & Related papers  (2024-03-03T17:36:42Z)
• Deep Imbalanced Regression via Hierarchical Classification Adjustment [50.19438850112964]
  Regression tasks in computer vision are often formulated into classification by quantizing the target space into classes. The majority of training samples lie in a head range of target values, while a minority of samples span a usually larger tail range. We propose to construct hierarchical classifiers for solving imbalanced regression tasks. Our novel hierarchical classification adjustment (HCA) for imbalanced regression shows superior results on three diverse tasks.
  arXiv  Detail & Related papers  (2023-10-26T04:54:39Z)
• Adjusting Logit in Gaussian Form for Long-Tailed Visual Recognition [37.62659619941791]
  We study the problem of long-tailed visual recognition from the perspective of feature level. Two novel logit adjustment methods are proposed to improve model performance at a modest computational overhead. Experiments conducted on benchmark datasets demonstrate the superior performance of the proposed method over the state-of-the-art ones.
  arXiv  Detail & Related papers  (2023-05-18T02:06:06Z)
• When Noisy Labels Meet Long Tail Dilemmas: A Representation Calibration Method [40.25499257944916]
  Real-world datasets are both noisily labeled and class-imbalanced. We propose a representation calibration method RCAL. We derive theoretical results to discuss the effectiveness of our representation calibration.
  arXiv  Detail & Related papers  (2022-11-20T11:36:48Z)
• On the Benefits of Large Learning Rates for Kernel Methods [110.03020563291788]
  We show that a phenomenon can be precisely characterized in the context of kernel methods. We consider the minimization of a quadratic objective in a separable Hilbert space, and show that with early stopping, the choice of learning rate influences the spectral decomposition of the obtained solution.
  arXiv  Detail & Related papers  (2022-02-28T13:01:04Z)
• Evaluating State-of-the-Art Classification Models Against Bayes Optimality [106.50867011164584]
  We show that we can compute the exact Bayes error of generative models learned using normalizing flows. We use our approach to conduct a thorough investigation of state-of-the-art classification models.
  arXiv  Detail & Related papers  (2021-06-07T06:21:20Z)
• Classification and Uncertainty Quantification of Corrupted Data using Semi-Supervised Autoencoders [11.300365160909879]
  We present a probabilistic approach to classify strongly corrupted data and quantify uncertainty. A semi-supervised autoencoder trained on uncorrupted data is the underlying architecture. We show that the model uncertainty strongly depends on whether the classification is correct or wrong.
  arXiv  Detail & Related papers  (2021-05-27T18:47:55Z)
• Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures [100.55816326422773]
  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.
  arXiv  Detail & Related papers  (2021-04-28T08:25:16Z)
• 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)
• Calibration of Neural Networks using Splines [51.42640515410253]
  Measuring calibration error amounts to comparing two empirical distributions. We introduce a binning-free calibration measure inspired by the classical Kolmogorov-Smirnov (KS) statistical test. Our method consistently outperforms existing methods on KS error as well as other commonly used calibration measures.
  arXiv  Detail & Related papers  (2020-06-23T07:18:05Z)

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.