Stochastic Learning Under Random Reshuffling With Constant Step-Sizes

DOI10.1109/TSP.2018.2878551MaRDI QIDQ4628203zbMATH OpenOpenAlexWikidataFDO

Authors Bicheng Ying, Kun Yuan, Stefan Vlaski, Ali H. Sayed

Publication date 6 March 2019

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.07964

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Convex programming (90C25) Stochastic programming (90C15)

Abstract: 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 function. 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(m{u}^2)$ around the minimizer rather than $O(mu)$. 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.

Cited in

(4)

• Asymptotic behaviour in learning from stochastic examples: one-step RSB calculation of the learning curve
• Incremental without replacement sampling in nonconvex optimization
• Random-reshuffled SARAH does not need full gradient computations
• The Random Batch Method for N-Body Quantum Dynamics

This page was built for publication: Stochastic Learning Under Random Reshuffling With Constant Step-Sizes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4628203)