Publications [#377061] of Rong Ge

Papers Published

1. 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, vol. 36 (January, 2023)
   (last updated on 2026/01/17)

   Abstract:
   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 ≳ d^k*−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 ≳ d^k*/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 ≳ d^k*/2 samples. We also draw connections to statistical analyses of tensor PCA and to the implicit regularization effects of minibatch SGD on empirical losses.