Tight Risk Bounds for Multi-Class Margin Classifiers
We consider a problem of risk estimation for large-margin multi-class classifiers. We propose a novel risk bound for the multi-class classification problem. The bound involves the marginal distribution of the classifier and the Rademacher complexity of the hypothesis class. We prove that our bound is tight in the number of classes. Finally, we compare our bound with the related ones and provide a simplified version of the bound for the multi-class classification with kernel based hypotheses.
Code (0)
등록된 구현이 없습니다.
Tasks
ClassificationGeneral ClassificationMulti-class ClassificationSimilar Papers 제목 키워드 기반
On the Complexity of Linear Prediction: Risk Bounds, Margin Bounds, and Regularization
We provide sharp bounds for Rademacher and Gaussian complexities of (constrained) linear classes. These bounds make short work of providing a number of corollaries including: risk bounds for linear prediction (including …
Improving Generalization Bounds for VC Classes Using the Hypergeometric Tail Inversion
We significantly improve the generalization bounds for VC classes by using two main ideas. First, we consider the hypergeometric tail inversion to obtain a very tight non-uniform distribution-independent risk upper bound…
Generalization BoundsTight Risk Bounds for Gradient Descent on Separable Data
We study the generalization properties of unregularized gradient methods applied to separable linear classification -- a setting that has received considerable attention since the pioneering work of Soudry et al. (2018).…
Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures
Modern machine learning systems such as deep neural networks are often highly over-parameterized so that they can fit the noisy training data exactly, yet they can still achieve small test errors in practice. In this pap…
ClassificationGeneral ClassificationregressionTight Sample Complexity of Large-Margin Learning
We obtain a tight distribution-specific characterization of the sample complexity of large-margin classification with L2 regularization: We introduce the gamma-adapted-dimension, which is a simple function of the spectru…
ClassificationGeneral ClassificationL2 Regularization