2018/03/31 by Bicheng Ying, Kun Yuan, Stefan Vlaski +1
Computer Science · Engineering · Mathematics · #Algorithm #Applied mathematics #Computer science #Constant (computer programming) #Convergence (economics) #Convergence of random variables #Convex function #Iterated function #Mathematical analysis #Mathematical optimization #Mathematics #Privacy-Preserving Technologies in Data #Random function #Random variable #Rate of convergence #Regular polygon #Sampling (signal processing) #Sparse and Compressive Sensing Techniques #Statistics #Stochastic Gradient Optimization Techniques #Stochastic approximation #Stochastic process #cs.LG #math.OC #stat.ML
paper · pdf · doi:10.1109/tsp.2018.2878551
arxiv created 2018/10/09 · openalex publication_date 2018/10/29 · arxiv updated 2019/01/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
In empirical risk optimization, it has been observed that stochastic gradient implementations that rely on random reshuffling of the data achieve better performance than implementations that rely on sampling the data uniformly. Recent works have pursued justifications for this behavior by examining the convergence rate of the learning process under diminishing step sizes. This work focuses on the constant step-size case and strongly convex loss functions. In this case, convergence is guaranteed to a small neighborhood of the optimizer albeit at a linear rate. The analysis establishes analytically that random reshuffling outperforms uniform sampling by showing explicitly that iterates approach a smaller neighborhood of size O(μ2) around the minimizer rather than O(μ). Furthermore, we derive an analytical expression for the steady-state mean-square-error performance of the algorithm, which helps clarify in greater detail, the differences between sampling with and without replacement. We also explain the periodic behavior that is observed in random reshuffling implementations.