Multiclass learning with margin: exponential rates with no bias-variance trade-off

• URL: http://arxiv.org/abs/2202.01773v1
• Date: Thu, 3 Feb 2022 18:57:27 GMT
• Title: Multiclass learning with margin: exponential rates with no bias-variance trade-off
• Authors: Stefano Vigogna, Giacomo Meanti, Ernesto De Vito, Lorenzo Rosasco
• Abstract summary: We study the behavior of error bounds for multiclass classification under suitable margin conditions. Different convergence rates can be obtained in correspondence of different margin assumptions.
• Score: 16.438523317718694
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the behavior of error bounds for multiclass classification under suitable margin conditions. For a wide variety of methods we prove that the classification error under a hard-margin condition decreases exponentially fast without any bias-variance trade-off. Different convergence rates can be obtained in correspondence of different margin assumptions. With a self-contained and instructive analysis we are able to generalize known results from the binary to the multiclass setting.

Related papers

• The Implicit Bias of Gradient Descent on Separable Multiclass Data [38.05903703331163]
  We employ the framework of Permutation Equivariant and Relative Margin-based (PERM) losses to introduce a multiclass extension of the exponential tail property. Our proof techniques closely mirror those of the binary case, thus illustrating the power of the PERM framework for bridging the binary-multiclass gap.
  arXiv  Detail & Related papers  (2024-11-02T19:39:21Z)
• A Universal Growth Rate for Learning with Smooth Surrogate Losses [30.389055604165222]
  We prove a square-root growth rate near zero for smooth margin-based surrogate losses in binary classification. We extend this analysis to multi-class classification with a series of novel results.
  arXiv  Detail & Related papers  (2024-05-09T17:59:55Z)
• The Implicit Bias of Batch Normalization in Linear Models and Two-layer Linear Convolutional Neural Networks [117.93273337740442]
  We show that gradient descent converges to a uniform margin classifier on the training data with an $exp(-Omega(log2 t))$ convergence rate. We also show that batch normalization has an implicit bias towards a patch-wise uniform margin.
  arXiv  Detail & Related papers  (2023-06-20T16:58:00Z)
• Multi-Label Quantification [78.83284164605473]
  Quantification, variously called "labelled prevalence estimation" or "learning to quantify", is the supervised learning task of generating predictors of the relative frequencies of the classes of interest in unsupervised data samples. We propose methods for inferring estimators of class prevalence values that strive to leverage the dependencies among the classes of interest in order to predict their relative frequencies more accurately.
  arXiv  Detail & Related papers  (2022-11-15T11:29:59Z)
• Shift Happens: Adjusting Classifiers [2.8682942808330703]
  Minimizing expected loss measured by a proper scoring rule, such as Brier score or log-loss (cross-entropy), is a common objective while training a probabilistic classifier. We propose methods that transform all predictions to (re)equalize the average prediction and the class distribution. We demonstrate experimentally that, when in practice the class distribution is known only approximately, there is often still a reduction in loss depending on the amount of shift and the precision to which the class distribution is known.
  arXiv  Detail & Related papers  (2021-11-03T21:27:27Z)
• When in Doubt: Improving Classification Performance with Alternating Normalization [57.39356691967766]
  We introduce Classification with Alternating Normalization (CAN), a non-parametric post-processing step for classification. CAN improves classification accuracy for challenging examples by re-adjusting their predicted class probability distribution. We empirically demonstrate its effectiveness across a diverse set of classification tasks.
  arXiv  Detail & Related papers  (2021-09-28T02:55:42Z)
• Intra-Class Uncertainty Loss Function for Classification [6.523198497365588]
  intra-class uncertainty/variability is not considered, especially for datasets containing unbalanced classes. In our framework, the features extracted by deep networks of each class are characterized by independent Gaussian distribution. The proposed approach shows improved classification performance, through learning a better class representation.
  arXiv  Detail & Related papers  (2021-04-12T09:02:41Z)
• Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View [82.80085730891126]
  We provide the first modernally precise analysis of linear multiclass classification. Our analysis reveals that the classification accuracy is highly distribution-dependent. The insights gained may pave the way for a precise understanding of other classification algorithms.
  arXiv  Detail & Related papers  (2020-11-16T05:17:29Z)
• One-vs.-One Mitigation of Intersectional Bias: A General Method to Extend Fairness-Aware Binary Classification [0.48733623015338234]
  One-vs.-One Mitigation is a process of comparison between each pair of subgroups related to sensitive attributes to the fairness-aware machine learning for binary classification. Our method mitigates the intersectional bias much better than conventional methods in all the settings.
  arXiv  Detail & Related papers  (2020-10-26T11:35:39Z)
• Relative Deviation Margin Bounds [55.22251993239944]
  We give two types of learning bounds, both distribution-dependent and valid for general families, in terms of the Rademacher complexity. We derive distribution-dependent generalization bounds for unbounded loss functions under the assumption of a finite moment.
  arXiv  Detail & Related papers  (2020-06-26T12:37:17Z)
• Negative Margin Matters: Understanding Margin in Few-shot Classification [72.85978953262004]
  This paper introduces a negative margin loss to metric learning based few-shot learning methods. The negative margin loss significantly outperforms regular softmax loss, and state-of-the-art accuracy on three standard few-shot classification benchmarks.
  arXiv  Detail & Related papers  (2020-03-26T17:59: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.