paperlist.ai

NeurIPS 2023 Papers

Conference on Neural Information Processing Systems

202620252024202320222021202020192018201720162015

Decision breakdown

3,584papers

Counted from the official paper list; may differ slightly from the number the conference announced.

  • Oral
    772.1%
  • Spotlight
    40011.2%
  • Poster
    3,10786.7%

Top 10 topics (click to filter)

Trends for all 207 research topics

Browse all papers

All3,584Oral77Spotlight400Poster3,107
Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models

Alex Damian, Eshaan Nichani, Rong Ge, Jason D. Lee

Expand abstract

We focus on the task of learning a single index model $\sigma(w^\star \cdot x)$ with respect to the isotropic Gaussian distribution in $d$ dimensions. Prior work has shown that the sample complexity of learning $w^\star$ is governed by the information exponent $k^\star$ of the link function $\sigma$, which is defined as the index of the first nonzero Hermite coefficient of $\sigma$. Ben Arous et al. (2021) showed that $n \gtrsim d^{k^\star-1}$ samples suffice for learning $w^\star$ and that this is tight for online SGD. However, the CSQ lower bound for gradient based methods only shows that $n \gtrsim d^{k^\star/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^\star$ with $n \gtrsim d^{k^\star/2}$ samples. We also draw connections to statistical analyses of tensor PCA and to the implicit regularization effects of minibatch SGD on empirical losses.

Oral
Deep learning · large language modelsDeep learning · generative models and autoencoders