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

Abstract

We prove two last-iterate convergence bounds of the random reshuffling (RR) method in the smooth general convex finite-sum optimization. In the proved results, the stepsize sequence $\{{\eta }_k{\}}_k$ of RR is an arbitrary positive non-increasing sequence with ${\eta }_1\lesssim 1/(\mathrm{polylog}(n)L)$, where $n$ is the number of components of the finite-sum objective and $L$ is the smoothness parameter. Specifically, a last-iterate convergence rate $\tilde{\mathcal{O}}\left(\frac{\Vert x_1^1-x_{\ast }{\Vert }^2}{n{\sum }_{k=1}^K{\eta }_k}+{\sigma }_{\ast }^2{\sum }_{k=1}^K\frac{{\eta }_k^2}{{\sum }_{l=k}^K{\eta }_l}\right)$ of RR is proved, where $x_{\ast }$ is a solution of the optimization problem and ${\sigma }_{\ast }^2$ is the variance at the solution $x_{\ast }$. This rate is novel to the last-iterate of RR. Also, a last-iterate convergence rate $\tilde{\mathcal{O}}\left(\frac{\Vert x_1^1-x_{\ast }{\Vert }^2}{n{\sum }_{k=1}^K{\eta }_k}+n{\sigma }_{\ast }^2{\sum }_{k=1}^K\frac{{\eta }_k^3}{{\sum }_{l=k}^K{\eta }_l}\right)$ of RR is proved. A similar rate exists in the literature, but only under a restrictive stepsize condition $\eta \lesssim 1/(nL)$ and does not allow varying stepsizes. At the heart of our proof for the latter rate is an auxiliary sequence named the shadow sequence, which has the same epoch endpoints with the iterate sequence generated by RR. The shadow sequence can be regarded as an iterate sequence generated by performing an inexact RR on an auxiliary interpolated problem or performing a novel variant of random reshuffled SVRG on the original problem. The shadow sequence technique sheds light on deeper understanding of RR and may be useful in the analysis of other shuffling methods.