Research map / Optimization / Nonconvex and smooth optimization
Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives improved last-iterate convergence rates for random reshuffling (RR) and single shuffle (SS) proximal shuffling gradient methods on nonsmooth convex and strongly convex problems, showing they beat proximal GD.
Problem
Last-iterate convergence of shuffling gradient methods (RR, SS, IG) for nonsmooth (strongly) convex finite-sum optimization was only as fast as proximal GD in prior analyses, leaving open whether randomness helps.
Approach
Analyze the general proximal gradient method with any index process satisfying i(t) ~ Uniform[n] by adapting the proximal SGD last-iterate analysis, via a sufficient lemma that controls the bias E[f_i(x_s) - f(x_s)] by the stepsize; this yields rates for RR/SS that beat prior bounds and is valid for any T, not just multiples of n.
Key results
- For RR in general convex case, rate O(n^{1/4} sqrt(G_{f,1}G_{f,2}) D / sqrt(T)) for last iterate, improving prior bounds by up to Theta(n^{-1/4}).
- Suffix average under RR attains nearly optimal O~(1/(n^{1/4} sqrt K)) matching the Ω(1/(n^{1/4} sqrt K)) lower bound (up to logs) when G_i equal.
- For SS with constrained optimization (psi = indicator), rate min{ n^{-1/4}K^{-1/4}, 1/sqrt K } improves on prior bounds for all K.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Random Reshuffle sampling instead of the prior shuffling-gradient method | General Proximal Gradient · Nonsmooth general convex, last iterate | expected function value gap: O\left(\frac{G_{f,1}D_{\star}}{\sqrt{K}}\right) -> O\left(\frac{\sqrt{G_{f,1}G_{f,2}}D_{\star}}{n^{1/4}\sqrt{K}}\right) | Helped |
| Use Random Reshuffle sampling instead of the prior shuffling-gradient method | General Proximal Gradient · Nonsmooth strongly convex, last iterate | expected function value gap: \widetilde{O}\left(\frac{\mu D_{\star}^{2}}{K^{2}}+\frac{G_{f,1}^{2}}{\mu K}\right) -> \widetilde{O}\left(\frac{\mu D_{\ | Helped |
| Use Single Shuffle sampling instead of the prior shuffling-gradient method | General Proximal Gradient · Nonsmooth general convex, last iterate when \(K\leq K_{\star}\) | expected function value gap: \widetilde{O}\left(\frac{\sqrt{G_{f,1}G_{f,2}}D_{\star}}{n^{1/4}K^{1/4}}\right) vs. O\left(\frac{G_{f,1}D_{\star}}{\sqrt | Helped |
| Use Single Shuffle sampling instead of the prior shuffling-gradient method | General Proximal Gradient with constrained optimization · Nonsmooth general convex, last iterate | expected function value gap: \widetilde{O}\left(\frac{\sqrt{G_{f,1}G_{f,2}}D_{\star}}{n^{1/4}K^{1/4}}\land\frac{G_{f,1}D_{\star}}{\sqrt{K}}\right) | Helped |
| Use Single Shuffle sampling instead of the prior shuffling-gradient method | General Proximal Gradient · Nonsmooth strongly convex, last iterate when \(K\leq K_{\star}\) | expected function value gap: \widetilde{O}\left(\frac{\mu D_{\star}^{2}}{T^{2}}+\frac{G_{f,1}G_{f,2}}{\mu\sqrt{T}}+\frac{G_{f,2}^{2}}{\mu n}\right) | Helped |
| Use the suffix average of the last n iterates | General Proximal Gradient with Random Reshuffle · Nonsmooth general convex, suffix average | expected function value gap: \widetilde{O}\left(\frac{n^{1/4}\sqrt{G_{f,1}G_{f,2}}D_{\star}}{\sqrt{T}}\right) | Helped |
Surprising findings
- For RR with constant stepsize, the O(n^{1/4}/sqrt T) rate is conjectured tight, implying a tight picture for last iterate.
Limitations
- SS bound for general psi and T not multiple of n is not improved beyond prior bounds; gap remains with proximal SGD.
- Results for RR with general stepsizes have extra log factors unless T = Omega(n log n).
Experimental setup
Metrics: function value gap (expected)
Baselines: Proximal GD Proximal SGD Shuffling gradient last-iterate bounds (Liu and Zhou 2024)
Builds on: Proximal SGD last-iterate analysis Shuffling gradient last-iterate analysis (Liu and Zhou 2024) Incremental subgradient-proximal method
Closest papers by meaning
- On the Last-Iterate Convergence of Shuffling Gradient Methods (ICML 2024 · similarity 0.95)
- Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimization (NeurIPS 2024 · similarity 0.92)
- Stochastic Extragradient with Flip-Flop Shuffling & Anchoring: Provable Improvements (NeurIPS 2024 · similarity 0.90)
- Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness (ICML 2025 · similarity 0.90)
- Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods (ICLR 2024 · similarity 0.90)
- Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems (NeurIPS 2026 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.