Generalization for multiclass classification with overparameterized linear models

• URL: http://arxiv.org/abs/2206.01399v1
• Date: Fri, 3 Jun 2022 05:52:43 GMT
• Title: Generalization for multiclass classification with overparameterized linear models
• Authors: Vignesh Subramanian, Rahul Arya and Anant Sahai
• Abstract summary: We show that multiclass classification behaves like binary classification in that, as long as there are not too many classes, it is possible to generalize well. Besides various technical challenges, it turns out that the key difference from the binary classification setting is that there are relatively fewer positive training examples of each class in the multiclass setting as the number of classes increases.
• Score: 3.3434274586532515
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Via an overparameterized linear model with Gaussian features, we provide conditions for good generalization for multiclass classification of minimum-norm interpolating solutions in an asymptotic setting where both the number of underlying features and the number of classes scale with the number of training points. The survival/contamination analysis framework for understanding the behavior of overparameterized learning problems is adapted to this setting, revealing that multiclass classification qualitatively behaves like binary classification in that, as long as there are not too many classes (made precise in the paper), it is possible to generalize well even in some settings where the corresponding regression tasks would not generalize. Besides various technical challenges, it turns out that the key difference from the binary classification setting is that there are relatively fewer positive training examples of each class in the multiclass setting as the number of classes increases, making the multiclass problem "harder" than the binary one.

Related papers

• 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)
• Precise Asymptotic Generalization for Multiclass Classification with Overparameterized Linear Models [4.093769373833101]
  We resolve the conjecture posed in Subramanian et al.'22, where the number of data points, features, and classes all grow together. Our new lower bounds are akin to an information-theoretic strong converse: they establish that the misclassification rate goes to 0 or 1ally. The key to our tight analysis is a new variant of the Hanson-Wright inequality which is broadly useful for multiclass problems with sparse labels.
  arXiv  Detail & Related papers  (2023-06-23T00:59:15Z)
• A Multi-Class SWAP-Test Classifier [0.0]
  This work presents the first multi-class SWAP-Test classifier inspired by its binary predecessor and the use of label states in recent work. In contrast to previous work, the number of qubits required, the measurement strategy, and the topology of the circuits used is invariant to the number of classes. Both analytical results and numerical simulations show that this classifier is not only effective when applied to diverse classification problems but also robust to certain conditions of noise.
  arXiv  Detail & Related papers  (2023-02-06T18:31:43Z)
• Generalization Error Bounds for Multiclass Sparse Linear Classifiers [7.360807642941714]
  We consider high-dimensional multiclass classification by sparse multinomial logistic regression. We propose a computationally feasible feature selection procedure based on penalized maximum likelihood. In particular, we consider global sparsity, double row-wise sparsity, and low-rank sparsity.
  arXiv  Detail & Related papers  (2022-04-13T09:25:03Z)
• Learning Debiased and Disentangled Representations for Semantic Segmentation [52.35766945827972]
  We propose a model-agnostic and training scheme for semantic segmentation. By randomly eliminating certain class information in each training iteration, we effectively reduce feature dependencies among classes. Models trained with our approach demonstrate strong results on multiple semantic segmentation benchmarks.
  arXiv  Detail & Related papers  (2021-10-31T16:15:09Z)
• 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)
• 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)
• Self-Weighted Robust LDA for Multiclass Classification with Edge Classes [111.5515086563592]
  A novel self-weighted robust LDA with l21-norm based between-class distance criterion, called SWRLDA, is proposed for multi-class classification. The proposed SWRLDA is easy to implement, and converges fast in practice.
  arXiv  Detail & Related papers  (2020-09-24T12:32:55Z)
• M2m: Imbalanced Classification via Major-to-minor Translation [79.09018382489506]
  In most real-world scenarios, labeled training datasets are highly class-imbalanced, where deep neural networks suffer from generalizing to a balanced testing criterion. In this paper, we explore a novel yet simple way to alleviate this issue by augmenting less-frequent classes via translating samples from more-frequent classes. Our experimental results on a variety of class-imbalanced datasets show that the proposed method improves the generalization on minority classes significantly compared to other existing re-sampling or re-weighting methods.
  arXiv  Detail & Related papers  (2020-04-01T13:21:17Z)
• Adversarial Multi-Binary Neural Network for Multi-class Classification [19.298875915675502]
  We use a multi-task framework to address multi-class classification. We employ adversarial training to distinguish the class-specific features and the class-agnostic features.
  arXiv  Detail & Related papers  (2020-03-25T02:19:17Z)

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.