Skip to main content

Smoothing the Landscape Boosts the Signal for SGD Optimal Sample Complexity for Learning Single Index Models

Publication ,  Conference
Damian, A; Nichani, E; Ge, R; Lee, JD
Published in: Advances in Neural Information Processing Systems
January 1, 2023

We focus on the task of learning a single index model σ(w* · x) with respect to the isotropic Gaussian distribution in d dimensions. Prior work has shown that the sample complexity of learning w* is governed by the information exponent k* of the link function σ, which is defined as the index of the first nonzero Hermite coefficient of σ. Ben Arous et al. [1] showed that n ≳ dk*−1 samples suffice for learning w* and that this is tight for online SGD. However, the CSQ lower bound for gradient based methods only shows that n ≳ dk*/2 samples are necessary. In this work, we close the gap between the upper and lower bounds by showing that online SGD on a smoothed loss learns w* with n ≳ dk*/2 samples. We also draw connections to statistical analyses of tensor PCA and to the implicit regularization effects of minibatch SGD on empirical losses.

Duke Scholars

Published In

Advances in Neural Information Processing Systems

ISSN

1049-5258

Publication Date

January 1, 2023

Volume

36

Related Subject Headings

  • 4611 Machine learning
  • 1702 Cognitive Sciences
  • 1701 Psychology
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Damian, A., Nichani, E., Ge, R., & Lee, J. D. (2023). Smoothing the Landscape Boosts the Signal for SGD Optimal Sample Complexity for Learning Single Index Models. In Advances in Neural Information Processing Systems (Vol. 36).
Damian, A., E. Nichani, R. Ge, and J. D. Lee. “Smoothing the Landscape Boosts the Signal for SGD Optimal Sample Complexity for Learning Single Index Models.” In Advances in Neural Information Processing Systems, Vol. 36, 2023.
Damian A, Nichani E, Ge R, Lee JD. Smoothing the Landscape Boosts the Signal for SGD Optimal Sample Complexity for Learning Single Index Models. In: Advances in Neural Information Processing Systems. 2023.
Damian, A., et al. “Smoothing the Landscape Boosts the Signal for SGD Optimal Sample Complexity for Learning Single Index Models.” Advances in Neural Information Processing Systems, vol. 36, 2023.
Damian A, Nichani E, Ge R, Lee JD. Smoothing the Landscape Boosts the Signal for SGD Optimal Sample Complexity for Learning Single Index Models. Advances in Neural Information Processing Systems. 2023.

Published In

Advances in Neural Information Processing Systems

ISSN

1049-5258

Publication Date

January 1, 2023

Volume

36

Related Subject Headings

  • 4611 Machine learning
  • 1702 Cognitive Sciences
  • 1701 Psychology