Full-Batch Gradient Descent Outperforms One-Pass SGD: Sample Complexity Separation in Single-Index Learning

It is folklore that reusing training data more than once can improve the statistical efficiency of gradient-based learning. While this phenomenon has been extensively studied in linear regression, the benefit of multi-pass gradient descent (GD, which reuses all the data) over one-pass stochastic gradient descent (online SGD, which uses each data point only once) is not well-understood in nonlinear and non-convex settings, except for a loss modification mechanism achieved by the first two passes on the data. In this work, we consider learning a $d$-dimensional single-index model with a quadratic activation, for which it is known that one-pass SGD requires $n\gtrsim d\log d$ samples to achieve weak recovery. We first show that this $\log d$ factor in the sample complexity persists for full-batch spherical GD on the correlation loss; however, by simply truncating the activation, full-batch GD exhibits a favorable optimization landscape at $n \simeq d$ samples, thereby outperforming one-pass SGD (with the same activation) in statistical efficiency. We complement this result with a trajectory analysis of full-batch GD on the squared loss from small initialization, showing that $n \gtrsim d$ samples and $T \gtrsim\log d$ gradient steps suffice to achieve strong (exact) recovery.

Modern machine learning systems are trained by methods that repeatedly adjust their parameters using examples from data. It is not fully understood when it is better to use a fresh random data example at each step, rather than repeatedly using the whole dataset for each parameter update. In this work, we explore this question further. We focus on a simple but informative setting where the goal is to recover a hidden direction from data. Earlier results identified how many examples are needed by methods that use fresh random examples in this setting. We compare this with what happens when the training method repeatedly reuses the same dataset, and show that the answer can change depending on small changes in the learning problem. For a standard unbounded non-linear output setting, iteratively reusing data does not improve over using fresh random examples. However, when the setting is slightly modified by limiting very large responses, reusing data can become more effective and succeeds with fewer examples than iterative methods that only rely on fresh random examples. These results shed more light on when reusing data helps iterative training methods and when it does not.