A sharp factor d/2 for diagonal preconditioning of single-sample SGD
Consider single-sample stochastic gradient descent with a constant step on noiseless Gaussian least squares with covariance Σ, preconditioned by a positive diagonal matrix P. Let γ* be the exact asymptotic decay rate of the expected loss at the best constant step, and let R(Σ) be the ratio of the rates of the two Gauss–Newton diagonal preconditioners diag(Σ)^(−1/2) and diag(Σ)^(−1). We prove that for every dimension d ≥ 3 and every Σ, R(Σ) < d/2, and that sup_Σ R(Σ) = d/2; the supremum is not attained. Equivalently, no diagonal preconditioner improves the exact rate of diag(Σ)^(−1) (Jacobi scaling) by a factor d/2 or more, and the factor d/2 is sharp. This is in contrast with the spectral condition number, where the corresponding worst-case factor of Jacobi scaling equals n/2 only for 2 ≤ n ≤ 5. The proof is computer-assisted. The reduction to a secular system and the lower-bound family are proved by hand, and so is the outer regime for d ≥ 26, up to two one-variable inequalities between rational functions that are proved in exact rational arithmetic. The regimes λ_min(C) → 0, λ_min(C) → 1 and d → ∞ are reduced by hand arguments to finitely many exact or interval checks on boxes that contain the limit; one of them, a dimension-free certificate for a floor on the fourth eigenvalue, serves every d ≥ 4. The remaining compact regions, in dimensions d ≤ 59, are certified with outward-rounded interval arithmetic on branch-and-bound trees whose leaves are checked to partition the domain by an exact volume count, together with exact rational identities and root counts. For d ≥ 60 we also prove the quantitative bound R(Σ) < (d/2)(1 − (1/20)·√min(λ_min(C), 1/(5d))), whose order √λ_min(C) is exact, and we give an explicit family showing that for large mini-batches the factor d/2 fails from d = 13 on. Files: the paper (PDF) and sources_and_supplement.zip (LaTeX source, bibliography, build script, the interval-arithmetic certificates with their logs and the exact hand checks). Companion papers: "On two questions of Shapiro on Jacobi scaling", doi:10.5281/zenodo.24315181, and version 4 of the WEDGE preprint, doi:10.5281/zenodo.24315153.
Authors
- Gabriel Costa de Mello Paiva
Institutions
- Elizabethtown Community Hospital (US)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-17
- DOI
- https://doi.org/10.5281/zenodo.24315182
- Citations
- 1
- Primary Topic
- Stochastic Gradient Optimization Techniques
- Type
- preprint