Fabian Latorre, Leello Dadi, Paul Rolland and Volkan Cevher
It has been recently observed that neural networks, unlike kernel methods, enjoy a reduced sample complexity when the distribution is isotropic. 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 nuclear-norm-constrained quadratic classifiers. 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.
10-01-2021 00:00 +0000
a8559d1 @ 12-10-2021