Research
Stochastic Optimization Under Power-Law Spectra: Tight Bounds and Shuffling Analysis
arXiv:2609.36271v1 Announce Type: new Abstract: Recent work has established that power-law spectral conditions on data enable tight convergence bounds for deterministic gradient descent, resolving the
arXiv:2609.36271v1 Announce Type: new 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
- Vanilla SGD with Momentum Survives Heavy-Tailed Noise: Convergence Analysis without Gradient Clipping or Normalization
- High-Probability Guarantees for SGD under eta-Heavy-Tailed Gradient Noise
- Muon Meets Mamba: Spectral Optimization for State Space Models
Source: arXiv cs.LG | 2026-09-30