Skip to main content

Write a PREreview

Minibatch Heavy-Ball SGD at Finite Dimension: Exact Threshold, Rate and Critical Slowing Down

Posted
Server
Zenodo
DOI
10.5281/zenodo.23972672

For heavy-ball SGD on a quadratic in R^P with minibatches of B random features having independent coordinates in the Hessian eigenbasis, coordinate-dependent fourth moments and a common random scale, we give at finite P and B the mean-square threshold via a rank-one secular equation and the exact convergence rate ρ = 1/z*, where z* is the smallest positive root of z K̂(z) = 1 for the kernel K̂ of an exact convolution equation for the loss, together with the prefactor of the approach to the noise floor and the slope of 1−ρ at the threshold. Applied to the vocabulary model of Everett and Paquette (2026), where token rows are gated features sharing (η, β, B), this settles at every finite batch the three vocabulary statements that their Appendix A.4 lists as not proved, and the numerical observations of their Remark H.17: when the two extreme-frequency rows are stable, the slowest row is one of them; no (η, β) makes a gated feature decay faster per step than the best SGD step (proved at leading order there), so the fewest samples per decay time with momentum equal those of SGD; at fixed β the sample cost increases strictly with B, giving E_β in closed form; the tuned β is zero with S_mom(B) = S_SGD(B) for B−1 ≤ B× (their batch size B×), and positive for B−1 > B×; and the fewest steps approach their large-batch limit as C_mom B^(−1/2) with explicit C_mom. At high effective rank r_eff = tr H/λ₁ the threshold of the EMA step η/(1−β) is 2B/(γ tr H), independent of β and of the coordinate fourth moments, up to an explicit relative error that is O(1/r_eff) when the coordinate kurtoses and B(1−β)/(1+β) stay bounded.

You can write a PREreview of Minibatch Heavy-Ball SGD at Finite Dimension: Exact Threshold, Rate and Critical Slowing Down. A PREreview is a review of a preprint and can vary from a few sentences to a lengthy report, similar to a journal-organized peer-review report.

Before you start

We will ask you to log in with your ORCID iD. If you don’t have an iD, you can create one.

What is an ORCID iD?

An ORCID iD is a unique identifier that distinguishes you from everyone with the same or similar name.

Start now