Heavy-ball momentum and batch size in streaming least squares: matching bounds on the tuned speedup over SGD

We consider realizable streaming least squares with Gaussian covariates x~ N(0,H) and mini-batches of size B, and compare stochastic heavy-ball momentum with plain stochastic gradient descent, each with its step size and momentum chosen to minimise the spectral radius ρ of the exact second-moment recursion. Writing κ=hₘₐₓ/hₘᵢₙ for the condition number of H, we prove that the ratio of the optimal spectral gaps satisfies \[ max(1,1{16}\,m)\;≤\;{1-ρHB^*}{1-ρSGD^*}\;≤\;128/3\,m, m=min(max(1,{Bhₘₐₓ}{tr H}),√κ). \] Momentum therefore gains at most a constant factor while B H/hₘₐₓ, gains a factor proportional to B in the intermediate range, and gains the full factor √κ once B√κ\,tr H/hₘₐₓ. The upper bound 1-ρHB^*≤8min(Bhₘᵢₙ/tr H,1/√κ) is due to Morwani, Meterez, Nair and Kakade; the new ingredient is an explicit choice of parameters, critical damping at the smallest eigenvalue, that attains it up to a constant. Both directions rest on an exact renewal equation for the diagonal second moments, which also gives a closed-form necessary and sufficient condition for mean-square stability.