Distribution-dependent sample complexity of large margin learning

MaRDI QIDQ2933877zbMATH OpenFDO

Authors Sivan Sabato, Nathan Srebro, Naftali Tishby

Publication date 8 December 2014

Full work available at URL https://arxiv.org/abs/1011.5053, http://jmlr.csail.mit.edu/papers/v14/sabato13a.html

zbMATH Keywords

supervised learningsample complexitylinear classifiersdistribution-dependence

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: We obtain a tight distribution-specific characterization of the sample complexity of large-margin classification with L_2 regularization: We introduce the gamma-adapted-dimension, which is a simple function of the spectrum of a distribution's covariance matrix, and show distribution-specific upper and lower bounds on the sample complexity, both governed by the gamma-adapted-dimension of the source distribution. We conclude that this new quantity tightly characterizes the true sample complexity of large-margin classification. The bounds hold for a rich family of sub-Gaussian distributions.

Recommendations

• Computing and Combinatorics
• Learning complexity vs communication complexity
• Local Rademacher complexities
• scientific article; zbMATH DE number 1804114
• 10.1162/153244303768966111

Cited in

(7)

• Computing and Combinatorics
• Improving the sample complexity using global data
• Large scale analysis of generalization error in learning using margin based classification methods
• Learning complexity vs communication complexity
• Towards a deeper geometric, analytic and algorithmic understanding of margins
• Computational sample complexity and attribute-efficient learning
• Bounds on margin distributions in learning problems

This page was built for publication: Distribution-dependent sample complexity of large margin learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2933877)