A Shadow Sequence Technique for Last-Iterate Convergence Analysis of the Random Reshuffling Method: Relaxed Stepsize Conditions and Beyond

Random reshuffling, in which stochastic gradient descent passes through the \(n\) components of a finite sum in a fresh random order each epoch, is what practitioners run, but its last iterate has been hard to analyse. For smooth convex problems Liu, Guo and Han prove a last-iterate rate of order \(\widetilde{O}\big(\|x_1^1 - x_*\|^2 / (n \sum_k \eta_k) + \sigma_*^2 \sum_k \eta_k^2 / \sum_{l \ge k} \eta_l\big)\), where \(\sigma_*^2\) is the gradient variance at the solution, for any non-increasing stepsizes with \(\eta_1 \lesssim 1/(\mathrm{polylog}(n) L)\).

A second rate, with \(n \sigma_*^2 \sum_k \eta_k^3 / \sum_{l \ge k} \eta_l\) in place of the variance term, was previously known only for a constant stepsize \(\eta \lesssim 1/(nL)\). The proof rests on a shadow sequence that shares the epoch endpoints of the iterates and can be read as inexact reshuffling on an interpolated problem, a device the authors expect to carry over to other shuffling methods.