Distribution-dependent sample complexity of large margin learning

zbMATH Open1317.68186arXiv1011.5053MaRDI QIDQ2933877FDOQ2933877

Naftali Tishby, Nathan Srebro, Sivan Sabato

Publication date: 8 December 2014

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.

Full work available at URL: https://arxiv.org/abs/1011.5053

Recommendations

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

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)

Cited In (4)

• Computing and Combinatorics
• Bounds on margin distributions in learning problems
• Improving the sample complexity using global data
• Computational sample complexity and attribute-efficient learning

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)