The Effect of the Intrinsic Dimension on the Generalization of Quadratic Classifiers

Abstract

It has been recently observed that neural networks, unlike kernel methods, enjoy a reduced sample complexity when the distribution is isotropic (i.e., when the covariance matrix is the identity). We find that this sensitivity to the data distribution is not exclusive to neural networks, and the same phenomenon can be observed on the class of quadratic classifiers (i.e., the sign of a quadratic polynomial) with a nuclear-norm constraint. We demonstrate this by deriving an upper bound on the Rademacher Complexity that depends on two key quantities: (i) the intrinsic dimension, which is a measure of isotropy, and (ii) the largest eigenvalue of the second moment (covariance) matrix of the distribution. Our result improves the dependence on the dimension over the best previously known bound and precisely quantifies the relation between the sample complexity and the level of isotropy of the distribution.

PDF NeurIPS OpenReview Semantic Scholar

Cite

Text

Latorre et al. "The Effect of the Intrinsic Dimension on the Generalization of Quadratic Classifiers." Neural Information Processing Systems, 2021.

Markdown

[Latorre et al. "The Effect of the Intrinsic Dimension on the Generalization of Quadratic Classifiers." Neural Information Processing Systems, 2021.](https://mlanthology.org/neurips/2021/latorre2021neurips-effect/)

BibTeX

@inproceedings{latorre2021neurips-effect,
  title     = {{The Effect of the Intrinsic Dimension on the Generalization of Quadratic Classifiers}},
  author    = {Latorre, Fabian and Dadi, Leello Tadesse and Rolland, Paul and Cevher, Volkan},
  booktitle = {Neural Information Processing Systems},
  year      = {2021},
  url       = {https://mlanthology.org/neurips/2021/latorre2021neurips-effect/}
}