Research map / Optimization / Nonconvex and smooth optimization
On the Last-Iterate Convergence of Shuffling Gradient Methods
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.
Proves the first last-iterate function-value-gap rates for proximal shuffling gradient methods (RR, SO, IG, any permutation) without strong convexity or smoothness-free assumptions, covering general regularizers psi and constrained problems.
Problem
Last-iterate convergence in function value gap of shuffling gradient methods (RR, SO, IG) for convex finite-sum problems with a general regularizer psi, where prior theory only covered average/tail iterates or squared distance to optimum.
Approach
Analyzes a proximal shuffling gradient method by bounding F(x_{k+1})-F(z_k) with auxiliary sequences z_k that are convex combinations of x_* and past iterates, constructing a separate auxiliary sequence for each k and applying a new algebraic recursive inequality; uses a carefully chosen stepsize with a 1+log K factor.
Key results
- For smooth components and uniformly random permutations (RR/SO), last-iterate rate Õ(L̄ σ_any^2/(μ_f^2 n K^2)) for strongly convex f with psi=0, nearly matching the Ω(L/(μ^2 nK^2)) lower bound and improving on prior tail-average results.
- For general convex smooth components, last-iterate rate Õ(L^{1/3} σ^{2/3} D^{4/3}/K^{2/3}) for any permutation, matching the best average-iterate IG rate up to log factors.
- For Lipschitz components, last-iterate rate Õ(Ḡ D/√K) for any permutation, matching best-known average-iterate rates of proximal IG.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a uniformly sampled permutation instead of an arbitrary permutation | Proximal Shuffling Gradient Method · Convex optimization with smooth components | last-iterate function value gap: \frac{\bar{L}^{1/3}\sigma_{\mathrm{any}}^{2/3}D^{4/3}}{K^{2/3}} -> \frac{\bar{L}^{1/3}\sigma_{\mathrm{rand}}^{2/3}D^{4/3 | Helped |
| Use a uniformly sampled permutation instead of an arbitrary permutation | Proximal Shuffling Gradient Method · Smooth components, strongly convex f | last-iterate function value gap: \frac{\bar{L}\asigma}{\mu_{f}^{2}K^{2}} -> \frac{\bar{L}\rsigma}{\mu_{f}^{2}nK^{2}} | Helped |
| Use a linear-decay stepsize instead of the other stated stepsizes | Proximal Shuffling Gradient Method · Convex optimization with Lipschitz components | last-iterate function value gap: \widetilde{\mathcal{O}}\left(\frac{\bar{G} D}{\sqrt{K}}\right) -> \mathcal{O}\left(\frac{\bar{G} D}{\sqrt{K}}\right) | Helped |
| Apply the last-iterate analysis to smooth components without requiring strong convexity | Proximal Shuffling Gradient Method · Convex optimization with smooth components | convergence guarantee for the last iterate | Helped |
| Allow general regularizers, including constrained optimization | Proximal Shuffling Gradient Method · Smooth convex optimization | applicability of last-iterate convergence guarantee | Helped |
Surprising findings
- For arbitrary permutations, the stepsize-based last-iterate bound is worse than the known lower bound for IG-type methods by a factor of n^2 in the strongly convex smooth case, suggesting permutation choice matters for matching lower bounds.
Limitations
- Extra 1+log K factor in stepsizes for smooth case appears necessary in analysis.
- Results restricted to constant stepsizes depending on K; time-varying stepsizes not addressed.
- For Lipschitz case, sample complexity matches GD but is worse than SGD by up to a factor n; no proof that random permutations help.
Experimental setup
Metrics: function value gap F(x_{K+1})-F_* convergence rate in K and n
Baselines: ProxRR ProxSO IG (incremental gradient) GraB SGD GD
Builds on: GD last-iterate analysis (auxiliary sequence z_k) ProxRR ProxSO proximal incremental gradient
Closest papers by meaning
- Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization (ICML 2025 · similarity 0.95)
- Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness (ICML 2025 · similarity 0.92)
- Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimization (NeurIPS 2024 · similarity 0.89)
- Stochastic Extragradient with Flip-Flop Shuffling & Anchoring: Provable Improvements (NeurIPS 2024 · similarity 0.89)
- Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods (ICLR 2024 · similarity 0.89)
- Tighter Convergence Bounds for Shuffled SGD via Primal-Dual Perspective (NeurIPS 2024 · similarity 0.88)
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.