Full-batch beats one-pass (online) stochastic gradient descent in sample complexity
ABSTRACT
It is folklore in machine learning 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 (reuses all the data) over one-pass (online) stochastic gradient descent (uses each data point only once) is not so well-understood in nonlinear and non-convex settings. In this talk, we consider learning a $d$-dimensional single-index model with a quadratic activation function, for which it is known that one-pass SGD requires $n \gtrsim d \log d$ samples to achieve weak recovery. We introduce three new results for the full-batch gradient descent algorithm for this model; (i) without preprocessing, the full-batch algorithm still requires $d \log d$ samples for weak recovery; (ii) after simple truncation of activation, i.e. discarding data points, the sample complexity of weak recovery drops to $n\gtrsim d$; (iii) the truncated gradient descent achieves strong recovery after $T\gtrsim \log d$ iterations. The talk is based on a joint work with Kovacevic, Wu, Soltanolkotabi, and Mondelli.
