Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization

Zhengyuan Zhou; Zijian Liu

Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization

T0 review · 0 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Shuffling gradient methods converge faster than proximal gradient descent for nonsmooth convex optimization, with Random Reshuffle achieving a nearly optimal last-iterate rate.

desk verdict Genuinely new last-iterate rates for nonsmooth shuffling methods; the correlation-bound lemma is the right linchpin and the analysis holds up. read the letter →

arxiv 2505.23056 v1 pith:GQO5V56R submitted 2025-05-29 math.OC cs.LGstat.ML

Zijian Liu , Zhengyuan Zhou This is my paper

classification math.OCcs.LGstat.ML MSC 90C25

keywords last-iterateconvergenceshufflinggradientmethodsrandomreshufflesingleshufflenonsmoothconvexoptimizationproximaldescentsuffixaveragefinite-sum

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that shuffling gradient methods—which pass the data points to (proximal) gradient descent one by one in a random order—converge faster than the classic Proximal Gradient Descent for nonsmooth convex optimization. Previous last-iterate bounds for the nonsmooth case were no better than Proximal GD, so the faster rates constitute the first evidence that the randomness in Random Reshuffle (RR) and Single Shuffle (SS) is provably beneficial. In the general convex case, RR attains a last-iterate rate of $\tilde{O}\bigl(n^{1/4}\sqrt{G_{f,1}G_{f,2}}\,D_* / \sqrt{T}\bigr)$ and the suffix average of the last epoch attains the same rate, matching the known lower bound up to logarithmic factors. For SS, the paper shows faster-than-Proximal-GD rates in the early phase for general problems and, in the constrained case, for every horizon. The strongly convex rates improve on the previous best by factors up to $n^{-1/2}$.

What carries the argument

The engine of the proof is Lemma 5.1, a sufficient condition for last-iterate convergence. It states that if every index $i(t)$ is marginally uniform, the stepsize is non-increasing, and the correlation term $|\mathbb{E}[\Omega_t(x_s)]| \le \Phi\,\eta_s$ for all $s \le t$—where $\Omega_t(x) = f_{i(t)}(x) - f(x)$ measures the discrepancy between the sampled component and the average function—then the expected function gap is bounded by $O\bigl(D_*^2 / \sum_t \gamma_t\eta_t + (G_{f,2}^2+\Phi)\sum_t \gamma_t\eta_t^2/\sum_{s\ge t}\gamma_s\eta_s\bigr)$. The paper then computes $\Phi$ for RR as $\Theta(\sqrt{n}\,G_{f,1}G_{f,2})$ and for SS as $\Theta(\sqrt{T}\,G_{f,1}G_{f,2} + (T/n)G_{f,2}^2)$ using coupling arguments that swap entries of the random permutation; the smallness of $\Phi$ is exactly what converts the sampling randomness into the faster rates.

What would settle it

Run the Random Reshuffle method on a small nonsmooth instance, such as $n=10$, $f_i(x) = |x-c_i|$, with a subgradient oracle that always selects the leftmost subgradient; estimate $\max_{t,s} |\mathbb{E}[\Omega_t(x_s)]| / \eta_s$ over many random permutations and compare with the claimed $\Phi \approx 4\bigl(G_{f,2}^2 + 2\sqrt{n}\,G_{f,1}G_{f,2}\bigr)$. An estimate exceeding this bound would refute Condition 3 of Lemma 5.1 and with it the paper's rates.

Watch

Extended reading notes

Core claim

The central claim is that randomness—not just the permutation structure—is what accelerates shuffling methods, and that this benefit can be captured by a single correlation parameter. The paper proves that under Assumptions 2.1 and 2.2, the last iterate of the general proximal gradient method satisfies $\mathbb{E}[F(x_{T+1})-F_*] = \tilde{O}\bigl(n^{1/4}\sqrt{G_{f,1}G_{f,2}}\,D_*/\sqrt{T}\bigr)$ for Random Reshuffle, with the same bound for the suffix average of the last $n$ iterates, matching the $\Omega(1/(n^{1/4}\sqrt{K}))$ lower bound of Koren et al. (2022) up to logarithms. For Single Shuffle, the paper obtains $\tilde{O}\bigl(\sqrt{G_{f,1}G_{f,2}}\,D_*/T^{1/4} \lor G_{f,2}D_*/\sqrt{n}\bigr)$ in general, and, when the problem is constrained ($\psi = I_C$) and $T = Kn$, the sharper $\tilde{O}\bigl(\sqrt{G_{f,1}G_{f,2}}\,D_*/(n^{1/4}K^{1/4}) \land G_{f,1}D_*/\sqrt{K}\bigr)$, which beats Proximal GD for every $K$. Strongly convex analogues (Theorems 4.4 and 4.7) improve the prior last-iterate bounds by factors of $\Theta(n^{-1/2})$ for RR and by the same order for SS in the early regime.

Load-bearing premise

The claimed rates stand or fall with the correlation bound $|\mathbb{E}[\Omega_t(x_s)]| \le \Phi\,\eta_s$ for every earlier time $s$, which the paper proves only under a deterministic subgradient oracle; if a different oracle choice makes this bound fail or forces a larger $\Phi$, the last-iterate guarantees collapse.

Editorial extensions

If this is right

If the RR rates are correct, then for nonsmooth convex ERM problems the last iterate of shuffled SGD is as good as the best known suffix-average guarantees, and the gap to Proximal GD closes by a factor up to $n^{-1/4}$.
For strongly convex objectives, RR improves the last-iterate function gap by a factor up to $n^{-1/2}$, making the shuffling regime strictly better than full-gradient passes.
SS is faster than Proximal GD for the first $K^* = nG_{f,1}^2/G_{f,2}^2$ epochs, and in constrained problems faster for all time, so the practical recommendation of shuffling passes is backed by a worst-case rate, not just heuristics.
All the RR and most SS results hold for any time horizon $T$, not only for $T = Kn$, which removes a standing restriction in earlier analyses.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The correlation-bound framework suggests a testable tool for other sampling schemes: block-shuffling with periodic reshuffles should interpolate between SS and RR, with the rate governed by the same $\Phi$; computing $\Phi$ for such schemes would predict their speed.
Because the coupling lemmas assume a deterministic subgradient oracle, adversarial tie-breaking in non-differentiable components could degrade the bound; an experimental check with a rightmost-subgradient oracle on a small nonsmooth instance would reveal whether this assumption is load-bearing in practice.
The non-vanishing $\tilde{O}(G_{f,2}D_*/\sqrt{n})$ term for SS in the general convex case looks like an analysis artifact; if a time-varying stepsize removed it, SS would beat Proximal GD for all horizons in the unconstrained case too.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Read it for you. The paper does what the abstract says: it gives the first last-iterate improvements over Proximal GD for nonsmooth convex and strongly convex finite-sum problems under Random Reshuffle and Single Shuffle. The RR suffix-average result matching Koren et al.'s lower bound up to logs is a real step forward, and the SS rates, though conditional on a time horizon threshold, clarify where shuffling helps and where it doesn't.

What is genuinely new is Lemma 5.1/B.2, a sufficient condition that separates the effect of randomness (the correlation bound on E[Omega_t(x_s)]) from the stepsize analysis. That is a clean abstraction, and the fine-grained treatment of G_f,1 versus G_f,2 is what lets them beat their own prior work and Proximal GD by the claimed factors. The paper is also honest about its limits: it says outright that the SS constrained result needs psi = I_C, that the strongly convex SS rate stalls at O(1/n), and that tightness for the last iterate under RR is only conjectured. That kind of clarity earns credit.

Soft spots are minor and mostly about verification. The whole rate collapses if Condition 3 fails, and the proofs of Lemmas B.4 and B.7 are long coupling arguments that I did not check line by line. They look right, and the stress-test found no gap, but this is a paper where small errors in constants or in the permutation exchange identity could hide. The deterministic-subgradient-oracle assumption in footnotes 5 and 6 is another spot: it is sufficient, and the stress-test is right that randomized tie-breaking can be conditioned away, but the paper should have said that in the main text rather than in a footnote.

The citation pattern is fair. They build on their own ICML 2024 paper and on Koren et al., and the new results are genuinely new; no circularity. The lower-bound appendix extends Bubeck's construction to proximal updates, which is a useful side contribution.

Who is this for? Specialists in convex optimization and learning theory who care about last-iterate rates for shuffling methods. It is a solid theory paper, not a paradigm shift. I would send it to a serious referee: the central claim is important enough and the proof structure sound enough to merit careful checking. I would also cite it in my own work on shuffling methods.

Recommendation: engage with it in review. It should be accepted after a careful pass on the constants and a clearer statement of the oracle assumption.

Referee Report

0 major / 4 minor

Summary. The paper studies Algorithm 1, a per-step proximal gradient method with a general index-selection rule, for minimizing F = f + ψ where f is a finite sum of convex Lipschitz functions and ψ is (possibly strongly) convex. Its main results are last-iterate function-value bounds for random reshuffling (RR) and single shuffling (SS): Theorem 4.2 gives Õ(n^{1/4}√(G_{f,1}G_{f,2})D_*/√T) for RR, Corollary 4.3 transfers this to the suffix average and matches the Koren et al. lower bound up to logarithms, and Theorems 4.5–4.7 give SS rates that improve on Proximal GD in the regime K ≤ K_* (and for constrained problems for all K). The key novelty is Lemma 5.1/B.2, a sufficient condition for last-iterate convergence expressed through a correlation bound on E[Ω_t(x_s)], together with coupling lemmas B.4 and B.6 that establish the required Φ for RR and SS.

Significance. If correct, these are the first last-iterate bounds for nonsmooth shuffling methods that are faster than Proximal GD, and the first nearly optimal suffix-average guarantee under RR. The proof strategy—reducing last-iterate convergence to a single correlation condition—is a useful contribution in its own right. The paper is carefully written: the main theorems are proved in full in Appendix A, the central coupling arguments are explicit, and the claimed matching with the Koren et al. lower bound is made precise in Corollary A.2 with the constant-stepsize version. I did not find a load-bearing gap; the issues below are local.

minor comments (4)

[Section 4, Theorem 4.5] The displayed formula for η is malformed and should read η = D⋆ / sqrt((q(T)G_{f,2}^2 ∨ sqrt(n q(T))G_{f,1}G_{f,2})(1+log T)), consistent with Theorem A.4; as printed it is not a valid optimization of the bound.
[Footnotes 5 and 6, Lemmas B.4 and B.6] The distributional identities used in the coupling arguments require a deterministic subgradient oracle; since this is an implementation assumption, please state it as a standing assumption in Section 2 or add a remark explaining that independent randomized tie-breaking can be handled by conditioning on its seed.
[Section 4 and Remark 4.1] The claim that all results except Theorem 4.6 hold for any T∈N is supported by the full statements in Appendix A, but Theorems 4.5 and 4.7 state simplified rates that are justified when T≥n; the qualification should be placed next to those theorem statements to avoid overstating the main-text bounds.
[Lemma C.1] The derivation of the second inequality in the proof is compressed; expanding the two displayed bounds (the log r(T) term and the 9(q(T)−2)/2 term) would help readers verify the constant and the claimed numerical factor.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the new last-iterate rates are derived from fully proved coupling lemmas and algebraic stepsize optimization, not from the conclusions being proved.

full rationale

The paper's central results do not reduce to their inputs by construction. Lemma 5.1 (full version Lemma B.2) is a new sufficient condition proved directly from Assumptions 2.1 and 2.2; the correlation bounds for RR and SS are established by the coupling lemmas B.4 and B.6, whose proofs are written out in the appendix. The theorems then follow by plugging in explicit stepsizes and optimizing parameters, with the dependence on G_{f,1}, G_{f,2}, D_bullet and T obtained algebraically. No fitted parameter is renamed as a prediction, and no target rate is assumed among the hypotheses. The authors' prior work (Liu & Zhou 2024b) is used as a baseline to beat and as a source of the stepsize schedule idea, but the schedule's validity for arbitrary T is proved via Lemma C.1 rather than imported. The lower bound of Koren et al. is external and used only for comparison. Footnootes 5 and 6 impose a deterministic subgradient-selection convention to make the coupling arguments valid; this is a technical assumption, not a circular step. Self-citations are present but not load-bearing, since the derivations are self-contained. Accordingly, no circular step is found and the circularity score is 0.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central claim rests on standard convex-analysis assumptions and on explicit stepsize choices. There are no fitted constants, no new physical or mathematical entities, and no hidden ad hoc assumptions beyond the domain requirements stated in Assumptions 2.1 and 2.2.

free parameters (1)

stepsize scale eta and exponent m = closed form, e.g., eta = D/(n^{1/4} sqrt(G1 G2)) for RR general convex; eta_t = m/(mu t), m in N, for strongly convex
The stepsize is an explicit algorithm hyperparameter chosen to balance the two terms in Lemma B.2. No empirical data is involved; different choices yield the stated rates.

assumptions (4)

domain assumption Assumption 2.1: each fi is convex; psi is proper, closed, convex and possibly mu-strongly convex
Defines the function class and is used in Lemma B.1 and throughout the proof of the one-step progress bound.
domain assumption Assumption 2.2: each fi is Gi-Lipschitz on dom psi
Provides bounded subgradients and is central to bounding E[Omega_t(x_s)] via the Lipschitz constants G_i.
domain assumption Existence of an optimum x* with finite D* = ||x* - x1||
Simplifies the theorem statements; Remark 4.1 notes that full versions in the appendix hold for any reference point z in R^d.
domain assumption Deterministic subgradient selection when the subgradient is not unique
Footnotes 5 and 6 assume a deterministic oracle so that the coupling arguments in Lemmas B.4-B.7 and Lemma C.4 are well-defined.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization." pith.science (2026). https://pith.science/paper/GQO5V56R

@misc{pith2026250523056,
  author       = {Pith},
  title        = {Pith review of: Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GQO5V56R}},
  note         = {Machine review of arXiv:2505.23056}
}

abstract

We study the convergence of the shuffling gradient method, a popular algorithm employed to minimize the finite-sum function with regularization, in which functions are passed to apply (Proximal) Gradient Descent (GD) one by one whose order is determined by a permutation on the indices of functions. In contrast to its easy implementation and effective performance in practice, the theoretical understanding remains limited. A recent advance by (Liu & Zhou, 2024b) establishes the first last-iterate convergence results under various settings, especially proving the optimal rates for smooth (strongly) convex optimization. However, their bounds for nonsmooth (strongly) convex functions are only as fast as Proximal GD. In this work, we provide the first improved last-iterate analysis for the nonsmooth case demonstrating that the widely used Random Reshuffle ($\textsf{RR}$) and Single Shuffle ($\textsf{SS}$) strategies are both provably faster than Proximal GD, reflecting the benefit of randomness. As an important implication, we give the first (nearly) optimal convergence result for the suffix average under the $\textsf{RR}$ sampling scheme in the general convex case, matching the lower bound shown by (Koren et al., 2022).

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

22 extracted references · 19 canonical work pages

[1]

The index satisfies i(t) D = Uniform [n] , ∀t ∈ [T ]

work page
[2]

cc/paper_files/paper/2020/file/ 2e2c4bf7ceaa4712a72dd5ee136dc9a8- Paper.pdf

URL https://proceedings.neurips. cc/paper_files/paper/2020/file/ 2e2c4bf7ceaa4712a72dd5ee136dc9a8- Paper.pdf. Bengio, Y . Practical recommendations for gradient-based training of deep architectures. InNeural Networks: Tricks of the Trade: Second Edition , pp. 437–478. Springer, 2012. Bertsekas, D. P. Incremental gradient, subgradient, and proximal methods...

work page 2020
[3]

v1fi(t)(z) + tX s=1 (vs+1 − vs)fi(t)(xs) − vt+1f (zt+1) # (b) = TX t=1 γtηt

|E [Ωt(xs)]| ≤Φηs, ∀t ∈ [T ] , s∈ [t] where Φ ≥ 0 is a constant probably depending on T , n, µ, and G1 to Gn Then for any z ∈ Rd, Algorithm 1 guarantees E [F (xT +1) − F (z)] ≤ O ∥z − x1∥2 PT t=1 γtηt + G2 f,2 + Φ TX t=1 γtη2 tPT s=t γsηs ! , where Ωt(·) is defined in Lemma B.1 and γt ≜ Qt−1 s=1(1 + µηs), ∀t ∈ [T + 1]. 24 Improved Last-Iterate Convergence...

work page
[7]

cc/paper_files/paper/2020/file/ c8cc6e90ccbff44c9cee23611711cdc4- Paper.pdf

URL https://proceedings.neurips. cc/paper_files/paper/2020/file/ c8cc6e90ccbff44c9cee23611711cdc4- Paper.pdf. Mishchenko, K., Khaled, A., and Richtarik, P. Proximal and federated random reshuffling. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Proceedings of the 39th International Conference on Machine Learning ...

arXiv 2020
[9]

Random Reshuffling with Momentum: Complexity Bounds and Last-iterate Convergence

URL https://proceedings.neurips. cc/paper_files/paper/2023/file/ eeb57fdf745eb31a3c7ef22c59a4661d- Paper-Conference.pdf. Nguyen, L., NGUYEN, P. H., van Dijk, M., Richtarik, P., Scheinberg, K., and Takac, M. SGD and hog- wild! Convergence without the bounded gradients as- sumption. In Dy, J. and Krause, A. (eds.), Proceed- ings of the 35th International Co...

work page Pith review arXiv 2023
[10]

Rajput, S., Lee, K., and Papailiopoulos, D

URL https://proceedings.mlr.press/ v119/rajput20a.html. Rajput, S., Lee, K., and Papailiopoulos, D. Permutation- based SGD: Is random optimal? In International Confer- ence on Learning Representations, 2022. URL https: //openreview.net/forum?id=YiBa9HKTyXE. Safran, I. and Shamir, O. How good is sgd with ran- dom shuffling? In Abernethy, J. and Agarwal, S....

work page 2022
[11]

Safran, I

URL https://proceedings.mlr.press/ v125/safran20a.html. Safran, I. and Shamir, O. Random shuffling beats sgd only after many epochs on ill-conditioned prob- lems. In Ranzato, M., Beygelzimer, A., Dauphin, Y ., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems , vol- ume 34, pp. 15151–15161. Curran Associates, Inc.,

work page
[13]

cc/paper_files/paper/2021/file/ 107030ca685076c0ed5e054e2c3ed940- Paper.pdf

URL https://proceedings.neurips. cc/paper_files/paper/2021/file/ 107030ca685076c0ed5e054e2c3ed940- Paper.pdf. Solodov, M. V . Incremental gradient algorithms with step- sizes bounded away from zero. Computational Optimiza- tion and Applications, 11:23–35, 1998. Tran, T. H., Nguyen, L. M., and Tran-Dinh, Q. Smg: A shuffling gradient-based method with momen...

work page 2021

Show all 22 references

[14]

URL https://proceedings.mlr.press/ v139/tran21b.html. Tran, T. H., Scheinberg, K., and Nguyen, L. M. Nes- terov accelerated shuffling gradient method for convex optimization. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Pro- ceedings...
[15]

Ying, B., Yuan, K., Vlaski, S., and Sayed, A

URL https://proceedings.mlr.press/ v162/tran22a.html. Ying, B., Yuan, K., Vlaski, S., and Sayed, A. H. Stochastic learning under random reshuffling with constant step- sizes. IEEE Transactions on Signal Processing, 67(2): 474–489, 2018. Yu, H. and Li, X. High probability guara...

2018 arXiv
[17]

The stepsize ηt, ∀t ∈ [T ] is non-increasing
[19]

In contrast, Condition 3 is more artificial and makes the rate depend on a new parameter Gψ

Condition 2 here is standard if we consider the whole epoch as a single update like (Liu & Zhou, 2024b). In contrast, Condition 3 is more artificial and makes the rate depend on a new parameter Gψ. We currently do not know whether it can be removed or not. Lastly, we point out...
[20]

The index satisfies {i((k − 1)n + 1), · · ·, i(kn)} = [n] , ∀k ∈ [K]
[21]

The stepsize satisfies ηt = eηq(t), ∀t ∈ [T ] where eηk, ∀k ∈ [K] is another positive sequence
[22]

ψ = φ + IC where φ : Rd → R is convex and Gψ-Lipschitz on domψ = C. Then for any z ∈ Rd, Algorithm 1 guarantees almost surely F (xKn+1) − F (z) ≤ O ∥z − x1∥2 n PK k=1 eγk eηk + n G2 f,1 + G2 ψ KX k=1 eγk eη2 kPK ℓ=k eγℓeηℓ ! , where eγk ≜ Qk−1 ℓ=1 (1 + µeηℓ), ∀k ∈ [K + 1]. Pro...

2020
[137]

Nguyen, L

Springer, 2018. Nguyen, L. and Tran, T. H. On the convergence to a global solution of shuffling-type gradient algo- rithms. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Ad- vances in Neural Information Processing Systems , volume 36, pp....

2018
[436]

Bubeck, S

Springer, 2012. Bubeck, S. et al. Convex optimization: Algorithms and com- plexity. Foundations and Trends® in Machine Learning, 8(3-4):231–357, 2015. Cai, X. and Diakonikolas, J. Last iterate convergence of incremental methods as a model of forgetting. InThe Thir- teenth Inte...

2012
[2020]

cc/paper_files/paper/2020/file/ cb8acb1dc9821bf74e6ca9068032d623- Paper.pdf

URL https://proceedings.neurips. cc/paper_files/paper/2020/file/ cb8acb1dc9821bf74e6ca9068032d623- Paper.pdf. Bassily, R., Feldman, V ., Guzmán, C., and Talwar, K. Stability of stochastic gradient descent on non- smooth convex losses. In Larochelle, H., Ranzato, M., Hadsell, R...

2020
[2021]

cc/paper_files/paper/2021/file/ 803ef56843860e4a48fc4cdb3065e8ce- Paper.pdf

URL https://proceedings.neurips. cc/paper_files/paper/2021/file/ 803ef56843860e4a48fc4cdb3065e8ce- Paper.pdf. Shalev-Shwartz, S. and Ben-David, S. Understanding ma- chine learning: From theory to algorithms. Cambridge university press, 2014. Shamir, O. Without-replacement samp...

2021
[2022]

cc/paper_files/paper/2022/file/ 7bc4f74e35bcfe8cfe43b0a860786d6a- Paper-Conference.pdf

URL https://proceedings.neurips. cc/paper_files/paper/2022/file/ 7bc4f74e35bcfe8cfe43b0a860786d6a- Paper-Conference.pdf. Lan, G. First-order and stochastic optimization methods for machine learning. Springer, 2020. Li, X., Zhu, Z., So, A. M.-C., and Lee, J. D. Incremental meth...

2022 arXiv
[2023]

Cortes, C

URL https://proceedings.mlr.press/ v202/cha23a.html. Cortes, C. and Vapnik, V . Support-vector networks. Ma- chine learning, 20:273–297, 1995. Gurbuzbalaban, M., Ozdaglar, A., and Parrilo, P. A. Con- vergence rate of incremental gradient and incremental newton methods. SIAM Jo...

1995 arXiv
[2024]

cc/paper_files/paper/2024/file/ 84d395725a9b40cb4a49d84478ac24c7- Paper-Conference.pdf

URL https://proceedings.neurips. cc/paper_files/paper/2024/file/ 84d395725a9b40cb4a49d84478ac24c7- Paper-Conference.pdf. Cha, J., Lee, J., and Yun, C. Tighter lower bounds for shuffling SGD: Random permutations and be- yond. In Krause, A., Brunskill, E., Cho, K., En- gelhardt,...

2024

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

The index satisfies i(t) D = Uniform [n] , ∀t ∈ [T ]

work page

[2] [2]

cc/paper_files/paper/2020/file/ 2e2c4bf7ceaa4712a72dd5ee136dc9a8- Paper.pdf

URL https://proceedings.neurips. cc/paper_files/paper/2020/file/ 2e2c4bf7ceaa4712a72dd5ee136dc9a8- Paper.pdf. Bengio, Y . Practical recommendations for gradient-based training of deep architectures. InNeural Networks: Tricks of the Trade: Second Edition , pp. 437–478. Springer, 2012. Bertsekas, D. P. Incremental gradient, subgradient, and proximal methods...

work page 2020

[3] [3]

v1fi(t)(z) + tX s=1 (vs+1 − vs)fi(t)(xs) − vt+1f (zt+1) # (b) = TX t=1 γtηt

|E [Ωt(xs)]| ≤Φηs, ∀t ∈ [T ] , s∈ [t] where Φ ≥ 0 is a constant probably depending on T , n, µ, and G1 to Gn Then for any z ∈ Rd, Algorithm 1 guarantees E [F (xT +1) − F (z)] ≤ O ∥z − x1∥2 PT t=1 γtηt + G2 f,2 + Φ TX t=1 γtη2 tPT s=t γsηs ! , where Ωt(·) is defined in Lemma B.1 and γt ≜ Qt−1 s=1(1 + µηs), ∀t ∈ [T + 1]. 24 Improved Last-Iterate Convergence...

work page

[4] [7]

cc/paper_files/paper/2020/file/ c8cc6e90ccbff44c9cee23611711cdc4- Paper.pdf

URL https://proceedings.neurips. cc/paper_files/paper/2020/file/ c8cc6e90ccbff44c9cee23611711cdc4- Paper.pdf. Mishchenko, K., Khaled, A., and Richtarik, P. Proximal and federated random reshuffling. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Proceedings of the 39th International Conference on Machine Learning ...

arXiv 2020

[5] [9]

Random Reshuffling with Momentum: Complexity Bounds and Last-iterate Convergence

URL https://proceedings.neurips. cc/paper_files/paper/2023/file/ eeb57fdf745eb31a3c7ef22c59a4661d- Paper-Conference.pdf. Nguyen, L., NGUYEN, P. H., van Dijk, M., Richtarik, P., Scheinberg, K., and Takac, M. SGD and hog- wild! Convergence without the bounded gradients as- sumption. In Dy, J. and Krause, A. (eds.), Proceed- ings of the 35th International Co...

work page Pith review arXiv 2023

[6] [10]

Rajput, S., Lee, K., and Papailiopoulos, D

URL https://proceedings.mlr.press/ v119/rajput20a.html. Rajput, S., Lee, K., and Papailiopoulos, D. Permutation- based SGD: Is random optimal? In International Confer- ence on Learning Representations, 2022. URL https: //openreview.net/forum?id=YiBa9HKTyXE. Safran, I. and Shamir, O. How good is sgd with ran- dom shuffling? In Abernethy, J. and Agarwal, S....

work page 2022

[7] [11]

Safran, I

URL https://proceedings.mlr.press/ v125/safran20a.html. Safran, I. and Shamir, O. Random shuffling beats sgd only after many epochs on ill-conditioned prob- lems. In Ranzato, M., Beygelzimer, A., Dauphin, Y ., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems , vol- ume 34, pp. 15151–15161. Curran Associates, Inc.,

work page

[8] [13]

cc/paper_files/paper/2021/file/ 107030ca685076c0ed5e054e2c3ed940- Paper.pdf

URL https://proceedings.neurips. cc/paper_files/paper/2021/file/ 107030ca685076c0ed5e054e2c3ed940- Paper.pdf. Solodov, M. V . Incremental gradient algorithms with step- sizes bounded away from zero. Computational Optimiza- tion and Applications, 11:23–35, 1998. Tran, T. H., Nguyen, L. M., and Tran-Dinh, Q. Smg: A shuffling gradient-based method with momen...

work page 2021