On the Last-Iterate Convergence of Shuffling Gradient Methods

arXiv:2403.07723v1 Announce Type: new
Abstract: Shuffling gradient methods, which are also known as stochastic gradient descent (SGD) without replacement, are widely implemented in practice, particularly including three popular algorithms: Random Reshuffle (RR), Shuffle Once (SO), and Incremental Gradient (IG). Compared to the empirical success, the theoretical guarantee of shuffling gradient methods was not well-understanding for a long time. Until recently, the convergence rates had just been established for the average iterate for convex functions and the last iterate for strongly …

abstract algorithms arxiv convergence cs.lg gradient incremental iterate math.oc popular practice random replacement stat.ml stochastic success type