Generalization Error Bounds for Multiclass Sparse Linear Classifiers
We consider high-dimensional multiclass classification by sparse multinomial logistic regression. Unlike binary classification, in the multiclass setup one can think about an entire spectrum of possible notions of sparsity associated with different structural assumptions on the regression coefficients matrix. We propose a computationally feasible feature selection procedure based on penalized maximum likelihood with convex penalties capturing a specific type of sparsity at hand. In particular, we consider global sparsity, double row-wise sparsity, and low-rank sparsity, and show that with the properly chosen tuning parameters the derived plug-in classifiers attain the minimax generalization error bounds (in terms of misclassification excess risk) within the corresponding classes of multiclass sparse linear classifiers. The developed approach is general and can be adapted to other types of sparsity as well.
Code (0)
등록된 구현이 없습니다.
Tasks
Binary Classificationfeature selectionregressionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Precise Asymptotic Generalization for Multiclass Classification with Overparameterized Linear Models
We study the asymptotic generalization of an overparameterized linear model for multiclass classification under the Gaussian covariates bi-level model introduced in Subramanian et al.~'22, where the number of data points…
Adversarial Risk Bounds via Function Transformation
We derive bounds for a notion of adversarial risk, designed to characterize the robustness of linear and neural network classifiers to adversarial perturbations. Specifically, we introduce a new class of function transfo…
General ClassificationA Margin-based Multiclass Generalization Bound via Geometric Complexity
There has been considerable effort to better understand the generalization capabilities of deep neural networks both as a means to unlock a theoretical understanding of their success as well as providing directions for f…
Generalization BoundsMargin-Based Transfer Bounds for Meta Learning with Deep Feature Embedding
By transferring knowledge learned from seen/previous tasks, meta learning aims to generalize well to unseen/future tasks. Existing meta-learning approaches have shown promising empirical performance on various multiclass…
ClassificationGeneral ClassificationLearning TheoryMeta-LearningMulticlass Boosting: Simple and Intuitive Weak Learning Criteria
We study a generalization of boosting to the multiclass setting. We introduce a weak learning condition for multiclass classification that captures the original notion of weak learnability as being "slightly better than …
PAC learning