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

arXiv: https://arxiv.org/abs/2602.02431 · HTML: https://mlsanity.com/paper/2602.02431/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Feb 2026.

## Built on by (most cited first, 3 of 3)

- [Statistical Inference on Gradient Flows](https://mlsanity.com/paper/2606.01257/) (2026)
- [Less Data, Faster Training: repeating smaller datasets speeds up learning via sampling biases](https://mlsanity.com/paper/2605.20314/) (2026)
- [Approximate Message Passing with Random Initialization for Phase Retrieval](https://mlsanity.com/paper/2608.01654/) (2026)

## Abstract (arXiv)

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 ngtrsim dlog 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 gtrsimlog d gradient steps suffice to achieve strong (exact) recovery.