Search papers, labs, and topics across Lattice.
This paper investigates the tradeoffs between compute efficiency (CE) and serial runtime in stochastic momentum methods, specifically heavy ball (HB) and Accelerated SGD (ASGD), for linear regression with Gaussian covariates. The authors establish that while HB maintains SGD-level CE over a larger batch-size window, it does not enhance the CE frontier, and for ASGD, the benefits depend significantly on the spectral properties of the data. Experiments corroborate the theoretical findings, revealing distinct regimes of performance based on the decay characteristics of the spectra involved.
HB doesn't push the compute efficiency frontier beyond SGD, but it does extend the batch-size window for reduced serial runtime significantly.
Stochastic momentum methods such as heavy ball (HB), Nesterov momentum, and variants of Accelerated SGD (ASGD) [Kidambi et al., 2018] are widely used in modern training, but their stochastic benefits depend on two distinct quantities: serial runtime, the number of iterations needed to reach a target accuracy, and compute efficiency (CE), the inverse total gradient-query or FLOP cost. Larger batches reduce serial runtime without hurting CE only when the contraction gap grows linearly with batch size. We study stochastic HB and ASGD for consistent linear regression with Gaussian covariates and prove finite-dimensional, discrete-time lower bounds on their batch-size tradeoffs. Our first result shows that HB does not improve the CE frontier over SGD for arbitrary spectra; rather, it preserves SGD-level CE over a larger batch-size window, allowing larger batches to reduce serial runtime until HB reaches its deterministic accelerated scale. This window can be a factor $\sqrt魏$ larger than the SGD critical batch size. For ASGD, the picture is more spectrum-dependent: for rapidly decaying power-law spectra, ASGD improves small-batch CE over HB/SGD, but as batch size grows it trades this CE advantage for improved serial runtime. Synthetic linear-regression experiments verify these qualitative regimes, including near-overlap of ASGD and HB for slowly decaying spectra and the predicted CE--serial tradeoff for rapidly decaying spectra.
