Stochastic Optimization Under Power-Law Spectra: Tight Bounds and Shuffling Analysis
Abstract
Recent work has established that power-law spectral conditions on data enable tight convergence bounds for deterministic gradient descent, resolving the conflict between classical exponential bounds and observed power-law learning curves. In this work, we extend this result to the stochastic regime of high-dimensional machine learning. We provide two main contributions: (1) We generalize the power-law spectral theory to Stochastic Gradient Descent (SGD), showing that the same spectral exponents govern stochastic dynamics; (2) For the fundamental case of isotropic Gaussian data, we provide a precise analysis of data shuffling, deriving exact constants that prove Single Shuffle is strictly superior to Flip-Flop and IID sampling. Our results bridge the gap between abstract spectral theory and practical stochastic training choices, offering a unified picture of how data geometry drives optimization speed.
Related
- How Many Directions Must a Truncated Diffusion Sampler Retain? Matching Bounds Under Power-Law Spectra
- Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds
- Tight Lower Bounds for Stochastic Nonconvex-Strongly-Concave Minimax Optimization
- Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback
- Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization
BibTeX
@misc{sa2026stochastic,
title = {{Stochastic Optimization Under Power-Law Spectra: Tight Bounds and Shuffling Analysis}},
author = {Christopher De Sa and Thomas Dybdahl Ahle and Yaroslav Bulatov and Christopher Ré},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.36271},
eprint = {2609.36271},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.36271},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Stochastic Optimization Under Power-Law Spectra: Tight Bounds and Shuffling Analysis
AU - Christopher De Sa
AU - Thomas Dybdahl Ahle
AU - Yaroslav Bulatov
AU - Christopher Ré
PY - 2026
DA - 2026/10/17
PB - arXiv
DO - 10.48550/arxiv.2609.36271
UR - https://arxiv.org/abs/2609.36271
AB - Recent work has established that power-law spectral conditions on data enable tight convergence bounds for deterministic gradient descent, resolving the conflict between classical exponential bounds and observed power-law learning curves. In this work, we extend this result to the stochastic regime of high-dimensional machine learning. We provide two main contributions: (1) We generalize the power-law spectral theory to Stochastic Gradient Descent (SGD), showing that the same spectral exponents govern stochastic dynamics; (2) For the fundamental case of isotropic Gaussian data, we provide a precise analysis of data shuffling, deriving exact constants that prove Single Shuffle is strictly superior to Flip-Flop and IID sampling. Our results bridge the gap between abstract spectral theory and practical stochastic training choices, offering a unified picture of how data geometry drives optimization speed.
ER -