Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
Authors: Zijian Liu
Zhengyuan Zhou
Venue: ICML 2025 poster (2025)
Keywords: Convex optimizaton
Nonsmooth optimization
Shuffling methods
Primary area: optimization->convex

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).

Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
Zijian Liu'
Zhengyuan Zhou
Abstract
empirical risk minimization framework (Shalev-Shward & Ben-David, 2014), such problem arises in wide range of applications (e.g., SVMs (Cortes & Vapnik, 1995)) and has been extensively studied in the past few years.
We study the convergence of the shuffling gra- dient method, a popular algorithm employed to minimize the finite-sum function with regular- ization, in which functions are passed to apply (Proximal) Gradient Descent (GD) one by one whose order is determined by permutation on the indices of functions. In contrast to its easy im- plementation and effective performance in prac- tice, the theoretical understanding remains lim- ited. A recent advance by (Liu Zhou, 2024b) establishes the first last-iterate convergence re- sults under various settings, especially proving the optimal rates for smooth (stronglyy convex op- timization. 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 (RR) and Single Shuffle (SS) strate- gies are both provably faster than Proximal GD, reflecting the benefit of randomness. As impor- tant implication, we give the first (nearly) optimal convergence result for the suffix average under the RR sampling scheme in the general convex case, matching the lower bound shown by (Koren et al., 2022).
Two text-book level algorithms for solving the problem are Proximal Gradient Descent (GD) and its variant Proximal Stochastic Gradient Descent (SGD) (Nemirovski & Yudin, 1983; Nesterov et al., 2018; Bubeck et al., 2015; Lan, 2020), where the former requires a true gradient in every step in contrast to the latter only computing the gradient sin- gle function selected based on a random index uniformly sampled from [m] A (1,...,,)) ,n].
Whereas neither of the above classic algorithms is widely adopted in practice since, when is large (the standard sce- nario nowadays), Proximal GD incurs large computational overhead and Proximal SGD suffers from cache misses. In- stead, the shuffling gradient method is arguably the most popular and practical choice, in which functions (or data points) are passed to apply (proximal) gradient descent one by one whose order determined by a permutation on [n]. In partieular, three shuffling strategies named Random Reshuffle (RR), Single Shuffle (SS), and Incremental Gra- dient (IG) are mostly used, where the permutation varies randomly in every epoch (containing n steps) for RR, is ran- domly sampled at the beginning and employed through all updates for SS, and deterministically picked in advance for IG.
Compared to its easy implementation, lightweight com- putation, and effective performance (Bottou, 2009; 2012; Bengio, 2012), the theoretical understanding of the shuffling gradient method remains limited, especially for the most common output, the last iterate. recent advance by (Liu & Zhou, 2024b) establishes the first last-iterate convergence results measured by the function value gap under various settings, particularly, proving the optimal rates for smooth (strongly) convex optimization under the pling schemes mentioned before. However, their bounds for nonsmooth (strongly) convex functions are proved for any kind of shuffling strategy (not limited to RR/SS/ and only as fast as Proximal GD, leaving the following un- addressed research question as also mentioned by (Liu & Zhou, 2024b):
1. Introduction
This work considers a common machine learning problem, minimizing a finite-sum function with regularization, i.e.,
min F(x) A f(x) + (xx) where f(x) & " f(()). ZER
in which fa and vi are convex and potentially satisfy other properties, e.g., Lipschitz continuity. Due to the famous
sam-
'ttern School of Business, New York University 2 Areea Tech- nologics. Correspondence to: Zijian Liu <z13067 @eteeeestttt...m.e .dd.uu.
Proceedings of the nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
Table Summary our new convergence rates and the best-known upper/lower bounds under different settings when T' Kn where K E N. All results use the function value gap as the convergence measurement. In the "Shuffling" column, ANY means the rate in the same row holds for any type shuffling scheme not limited to RR/SS/IG. In the "Rate" column, D. _ ||=, 1n.-aa at denotes the Euclidean distance (or any upper bound on it) from the optimal solution and the initial point #1. A and V indicate min and max sutti & 1> at Kn+1
avg _ Kn Dis1 #++1 operations, respectively. the last column, & Km++1 average iterate and the suffix average of the last epoch.
L #++1 respectively refer to the
F
+ d where / = E ii=1
Sa each Si is convex and G-Liipschtz, and 1 is justrronlly convex
Setting
Shuffling
Reference
Rate
Output
ANY
(Liu & Zhou, 2024b)
0
GD2
VK
KKn+1 avg a Kn+11
(Koren et al., 2022)
GD.
n1/AKK
RR
Ours (Theorem 4.2)
nt/4KK
GD.
a #Kn+1
Ours (Corollary 4.3)
0
GD.
#Kn+
1 =
(Koren et al., 2022)
GD.
GD.
a Kn+1
avg
SS
Ours (Theorem 4.5)
nt/4g174
GD.
GD.
VR
ØKn+1
Ours (Theorem 4.6)
n K//
GD.
GD
/K
2Knt1
RR/SS
(Koren et al., 2022)
Ω
suffix *Kn+1
BI/K
uD?
ANY
(Liu & Zhou, 2024b)
KJ
+
pk
ØKn+1
nD²
1a 1>00
RR
Ours (Theorem 4.4)
n²
PVUK
EKn+1
SS
Ours (Theorem 4.7)
uDa n²
G²
KKn+1
pvnK
"The same rales hold for the last iterate of Proximal when gradient budget is Kn. Also, we remark these rates cannot apply to our Algorithm once v * 0 due to the difference from the method studied in (Liu & Zhou, 2024b). See Section 3 for details. "These rates are proved under
Ic where
the characteristic function for the nonempty closed convex in Rd.
"hii rate can automatically improve to 1//4// ). i.e., no extra logarithmic factor, if K f(llogn). n).
GDD
This bound is built under G = 4, D. = 1. and v Ig for C being the unit ball centered at 0. See also discussions in Subsection 1.2.
For nonsmooth (strongly) convex optimization, can we prove better last-iterate convergence rates than Proximal GD for RR/ SS to reflect the benefit of randomness?
trajectory, matching the lower bound shown by (Koren et al., 2022) and thus filling the gap.
For SS, our rates are better than the bounds in (Liu & Zhou, 2024b) when the time horizon is below a certain threshold. Specifically, suppose T = Kn where K N, then there exists a critical value K. E (1, n] such that once K < K., our bounds decay faster than (Liu & Zhou, 2024b) (and also Proximal GD) for both general and strongly convex optimization. In the special case of constrained optimization (i.e., / = Te where Te is the characteristic function for the nonempty closed convex set in IRd), we sharpen our bound further and obtain an improved rate better than (Liu & Zhou, 2024b) for any K E N. These results suggest that the SS strategy also beats Proximal GD (at least partially), demonstrating the benefit of using random permutations.
1.1. Our Contributions
We answer the question affirmatively by establishing the first improved last-iterate convergence rates for nonsmooth (strongly) convex optimization under both RR and SS sam- pling schemes, as summarized in Table 1.
For RR, our new rates are better than the best-known bounds in (Liu & Zhou, 2024b) by up to a factor of Onn -144) in the general convex case and a factor of (1/2) the strongly convex case. As such, our results provide the first concrete evidence indicating that the RR sampling scheme indeed converges faster than Proximal GD, reflecting the benefit of randomness. As an important implication, we give the first provable and (nearly) optimal convergence result for the suffix average of the last n points in the optimization
We also highlight that results (except Theorem 4.6) hold for any T E N, which far know is new in the litera- ture on shuffling gradient methods for convex optimization.
2

---

Improved Last-Tterate Convergence of Shuflling Gradient Methods for Nonsmooth Convex Optimization
Moreover, we propose a novel sufficient condition to guar- antee the last-iterate convergence when the index is selected in general manner, not limited to shuffling-based methods.
gradient methods for nonsmooth (strongly) convex optimiza- tion is long-open problem. The first insightful observation is by (Nagaraj et al., 2019) pointing out that any lower bound established for the deterministic case is also valid here as one can take f; = f and dp = Ic where C is a certain convex set (usually a ball in E centered at O). Such a reduction immediately implies two results (not limited to the last it- erate) working for any shuffling strategy, i.e., P 1
1.2. Related Work
Due to limited space, we will only review the study of shuffling-basee gradient methods for nonsmooth (strongly) convex optimization. For details and progress in smooth optimization, the reader could refer to (Gurbuzbalaban et al., 2019; Gürbüzbalaban et al., 2021; Ying et al., 2018; Haochen & Sra, 2019; Nagaraj et al., 2019; Rajput et al., 2020; Safran & Shamir, 2020; Ahn et al., 2020: Mishchenko et al., 2020; Nguyen al., 2021; Safran & Shamir, 2021; Rajput et al., 2022; Mishchenko et al., 2022: Tran et al., 2022; Cha et al., 2023; Cai et al., 2024: Cai & Diakonikolas, 2025) for the convex case and (Solodov, 1998: Li et al., 2019; Mishchenko et al., 2020; Nguyen et al., 2021; Tran et al., 2021; Pauwels, 2021: Lu et al., 2022b; Mohtashami et al., 2022: Lu et al., 2022a; Li et al., 2023; Nguyen &
Vnk
for the general convex case and Q (nk)) ) for the strongly convex case (Nemirovski & Yudin, 1983; Nesterov et al., 2018; Bubeck et al., 2015).
Though these two lower bounds may be too optimistic for shufflin-bbased gradient methods, no further progress has been made until (Koren et al., 2022), showing that both RR and SS sampling schemes with a constant step- size 17 in the general convex case admit the lower bound Ω (min { [, [I, + 11 qnk }) for the suffix average ΣK-1
of the last epochs (i.e., In Zj=K-J Ei= 2 +i++++). Noticing Ω
Tran, 2023; Yu & Li, 2023; Qiu et al., 2023; Koloskova
(1VF T
2 Ω JI/AAA/KK and
et al., 2024; Qiu & Milzarek, 2024; Josz et al., 2024) for the nonconvex case.
Ω (1+ Ronk
2
we hence can simplify the
vnk
In the following, we assume the time horizon T = Kn where K E N for simplicity and only focus on the depen- dence of n and K in the convergence rate.
bound into P
Especially, this im-
vnk
plies the Ω
n//A/K) barrier for the suffix average of the last one epoch as listed in Table 1.
Upper Bound. In the general convex case, the first rate is established by (Nedic& & Bertsekas, 2001) O VK
However, whether the Ω n//4// bound also holds for the last iterate under RR/St RSSSS// is still unclear. Furthermore, whether the general lower bound ? (x²R) for the strongly convex mentioned above is tight for shuffling gradient methods remains unknown as well.
for IG when +b = Ic. Later in (Bertsekas, 2011). the re- quirement 10- = Ic is relaxed to sb = & + Ie where &p needs to be Lipschitz on C. (Shamir, 2016) studies the general- ized linear model and provides the O RR/SS when K- 1. As for general objectives and general K E N, (Koren et al., 2022) is the only work showing the rate for SS, both under To- = Ie. However, all the results men- tioned until now only work for the average iterate. Recently, (Liu& & Zhou, 2024b) gives the first last-iterate convergence result O of shuffling strategy not limited to RR/SS/IG. /SS/IG.
Vn upper bound for
2. Preliminary
( (///K) rate for RR and the O (1/4K174 VT
Notation. N is the set of all positive integers and [m] & (1...., m). Vm E N. a A b and a b respectively indicate min {a, b} and max (a, X 2 Y means that two random variables X and Y have the same probability distribution. (,))) denotes the Fuclidean inner product on Idd ||-|| A V (..)) is the 2-norm. Given an extended real-valued con- vex function h Rdd - R where IR _ (-o0, +ox], domh & (a E Rd. M(x)) < +oo]. For any x E domh, 0h(x)) A {g Rd: h(y)) 2 h(x) + (g. x) , Vy Rd) is the set of subgradients at æ. We denote by Vh(æz) an element in 0h(x) when 0h(x) * Ø. Throughout the paper, C always denotes a nonempty closed convex set in Id and Ic repre-
being applied to any convex vé and any type
In the strongly convex case, (Kibardin, 1979; Nedić & Bert- sekas, 2001) show the IG sampling scheme guarantees the O (+)) convergence measured by the squared distance from the optimal solution and the last iterate, assuming strongly convex f and di = Ic. (Liu & Zhou, 2024b) proves a similar Ō (++) rate for strongly convex v with improvements in two aspects: one is using a stronger criterion, the function value gap, to measure convergence, the other is that their result holds for any shuffling scheme not restricted to RR/S3 RR/SS/IG.
'A subtle point is that this lower bound is established for strongly convex instead of t. not strictly fitting our Assumption 1. However, by slightly modifying the existing proof (Buheck et al., 2015) to make it work for the first-order algorithm containing proximal update step, we can show the same bound still holds for strongly convex v. See Appendix D for details.
Lower Bound. The lower complexity bound of shuffling
3

---

Improved Last-Tterate Convergence of Shuflling Gradient Methods for Nonsmooth Convex Optimization
sents its characteristic function, i.e., Ic(ar) if x C, +00 otherwise.
Now we provide some concrete examples of how to generate the index i(t). The first one is Example 3.2, showing that Proximal SGD is special case of Algorithm 1.
In this work, we study the following optimization problem
Example 3.2. When i(1) to i(T) are mutually independent random variables uniformly distributed on [ni,, Algorithm I recovers the famous Proximal SGD algorithm.
min F(x) - f(x) + (2x) where (ax) - 1 n aERd
[(()))
Next, to formally define different shuffling strategies, we require some new notations. Henceforth, r(t) denotes the modulo operation of n, i.e., r()) _ L mod n, where we use the convention Kn mod n = n, AK E N. In addition, we let qt) be the smallest integer greater than or equal to A i.e., (()) & [ where [-1 is the ceiling function. Remarkably, the equation
Our analysis relies on two mild assumptions.
Assumption 2.1. Each f. : R + R is convex. & : Rd -> R is proper, closed, and convex. Moreover, there exists μ 2 0 such that v(x)- (yy) - (Ve(y), - y) z 2
# || - yll² Vx E Rd, y E domp, Viyl)) E o0(y)
whenever (g) + Ø.
(q(t) 1)n + r(t), Vt E N always holds. Lastly, we denote by S., the symmetric group of [n], i.e. the set containing all permutations of [n].
Under Assumption 2.1, (z) is always nonempty for any Rd and i E [n]] since domf; Rd. Assumption 2.2. Each fü is G. G.-Lipschitz on domb for some G, >0 O.
Equipped with these notations, we introduce the commonly used RR/SS/IG shuffling schemes as follows.
Example 3.3. When i(t) xT aq(t) where मं to (T(Tr) are mutually independent random permutations uniformly dis- tributed on S,, it is called the RR sampling scheme.
(())
We remark that Assumption 2.2 only requires fi to be Lips- chitz on dome' instead of the whole space IR. Hence, it is also possible to consider the case of strongly convex Sa or f without the domain issue pointed out by (Nguyen et al., 2018). However, to keep it simple, we only focus on the situation of va being possibly strongly convex.
Example 3.4. When i(t) ,((() where т is random permutation uniformly distributed on Sn, it is called the SS sampling scheme.
Example 3.5. When i(t) = (( where π is deterministic permutation in Sn, it is called the IG sampling scheme.
3. General Proximal Gradient Method
4. Improved Last-Iterate Convergence Rates
Algorithm 1 General Proximal Gradient Method
Input: initial point x1 E domp, stepsize TJ. > O, Vt E (T). for [. = T do
In this section, provide our improved last-iterate con- vergence rates for Algorithm I under both RR and SS sampling schemes. To simplify the notation, we define Gリ A 1 n E G, and 222 A V E G? respec- tively representing the arithmetic mean and the root mean square of Lipschitz parameters. Notably, the following in- equality always holds
Generate an index i(t) E [n]
Øt+1 argmin E (x) + (V fin) x) 2 -- ?
2n
Output: xy-1
Remark 3.1. Algorithm 1 is also known as Incremental Subgradient- -roxiimal Method (Bertsekas, 201 However, we use a different name here to distinguish it from the term Incremental Gradient in the literature.
GI,1 S G12 fn
(I)
Next, to make easy and fair comparisons to the best exist- ing convergence results of shuffling gradient methods for nonsmooth (strongly) convex optimization (Koren al., 2022; Liu & Zhou, 2024b), we make two extra assumptions here. One is the existence of a point x., E I attaining the minimum value of F, i.e., F(x.) = F. 2 inf F(xx) Under this assumption, let D, - xr. 2., || denote the dis- tance between the optimal solution and the initial point. The other assuming the time horizon satisfies T 2 n (or one can simply think T Kn for K E N as in prior works). Remark 4. We clarify that the above assumptions are both unnecessary in the full statement of every theorem (except Theorem 4.6). Concretely, for any reference point z E Rd
The algorithmic framework studied in the paper, General Proximal Gradient Method (Bertsekas. 2011), is provided in Algorithm 1. We highlight three key differences from the prior proximal shuffling gradient methods (Kibardin, 1979; Mishchenko et al., 2022; Liu & Zhou, 2024b; Josz et al., 2024). First, Algorithm is more general since the genera- tion process of i(t) is not limited to shuffling shuffling-based. Second, Algorithm works for any T E N, in contrast to T = Kn where K E N required in the studies mentioned above. Moreover, the proximal update in Algorithm happens in every step instead of at the end of every epoch (containing n gradient descent steps) the existing algorithms.
4

---

Improved Last-Iterate Convergence of Shuflling Gradient Methods for Nonsmooth Convex Optimization
and T E N, the gap E [(( F(z)] can always be properly upper bounded. See Appendix A for details.
In particular, the ((n improvement can be achieved when G; G, leading to the rate O ably, such a rate is as fast as the previously best-known bound established only for the average iterate x avg - Kn++
<1/AA/K Remark-
GD.
In addition, following the convention in nonsmooth opti- mization for the general convex case (Nesterov et al., 2018; Lan, 2020), the value of 1) used in the stepsize T in Theo- rems 4.2, 4.5, and 4.6 has been optimized obtain the best dependence
Kn R - 1 when vp = Ic (Koren et al., 2022).
An important implication of Theorem 4.2 is to provide the convergence of 1 Sulffix & Ei=r--e L++1 as follows.
dedeeddddenndentt parameters, c.g., GG, G and D.. Rates working for arbitrarily picked are de- ferred to the corresponding full version of each theorem in Appendix A, in which the precise logarithmic factor hidden in the O notation is also provided.
Corollary 4.3. Under the same setting in Theorem 4.2 (using the third stepsize), Algorithm guarantees
n 1/4 / GGGGGgDDD
E F((TTti)) sutto F.] =ō
4.1. RR Sampling Scheme
VT
This subsection will focus on the RR sampling scheme. As the reader will see, our new last-iterate bounds are always better than the best-known results in (Liu & Zhou, 2024b).
Proof. Due to the convexity of F, E [ F(2)41) - F. 1
1 ET L EE [F(#++1) F.]. We conclude from Theo-
àn
Theorem 4.2. Under Assumptions 2.1 (with = 0) and 2.2, suppose the RR sampling scheme employed with one of the following three stepsizes Th,, Vt E [T]:
rem 4.2 and the inequality _ T-
1 o VT
To our best knowledge, Corollary 4.3 is not only the first provable but also the first optimal rate for the suffix average since when T = Kn and G, = G, matches the lower bound Z
n7 = a
a(t)+ and 1 q(T)VT
D. n-14 n-11 Gr 4
loc
n//4K/ (up to logarithmic factors) shown by (Koren et al., 2022) proved for 1b = Ic. However, the careful reader may argue that Corollary 4.3 is not convine- ing because the original lower bound is established for the constant stepsize 1/: 1) and has stronger version de- pending on the value of 17 (see Subsection 1.2). In Corol- lary A.2, we close the gap by giving E [ (F(x:5uf)) - F.] S Ô कF x1 when 7)2 = 17 and T 2 2(n 1), which perfectly matches the original lower bound in (Koren et al., 2022) by up to logarithmic factors.
1
3 and 1) = ni/4 GraaGrattttt f V
D.
1 " and n n344 GGAGEE
Then Algorithm! guarantees
E [[F(aT+)) - F.) Oō 1/44 GG1Gg2DD
VT
If additionally assuming = Mnllgg n), then the first stepsize choice achieves the following improved rate
Moreover, we want to talk about the first stepsize choice T) = ((T)
a(T)VT which is inspired by (Liu & Zhou, 2024b) who showed that the stepsize schedule proportional to K - k + in the k-th epoch when T = Kn can remove any extra logarithmic factor in the final rate. Here, we prove this strategy can also be applied to arbitrary T e N but will incur an additional O
1/44 GG
E [F((T++)) - F.J5s so
-F.]
VT
We start with the general convex case and discuss Theo- rem 4.2 in detail here. As far as we know, the best and only last-iterate bound that can be applied to the same set- ting is O D. for T Kn where K E N (Liu & Zhou, 2024b). In that case, Theorem 4.2 achieves the rate VGraGraD, ). nt/4/KK
log 2 q(T)
factor, which is at most in
the order of ((Vloog n)) and is automatically shaved off once (T) = 2(log n) + T = Q(n logn). We emphasize that, though the principle of our first stepsize is highly similar to (Liu & Zhou, 2024b), showing it indeed works for any T E N requires a refined analysis, for example, see Lemma C.1 in the appendix.
VK
Note that by (1), there is
Theorem 4.4. Under Assumptions 2.1 (with P > 0) and 2.2, suppose the RR sampling scheme is employed with the stepsize the R Vt E (T), then Algorithm I guaranttes
GGI,G55DD. GG n//4/KK KK
G E
1 (n//4.1)
1/4
GØ
Therefore, our new result is always better than (Liu & Zhou, 2024b) by up to factor of (nn-1/4)
HDD2 T
VTGz11G122 PT
E B[F(TT41) F.] Sō
5

---

Improved Last-Tterate Convergence of Shuflling Gradient Methods for Nonsmooth Convex Optimization
Now turn our attention to the strongly convex case. As before, we first check the case T = Kn, under which
falls into (1, n| due (I). If K S K,, we notice the rate in
Theorem 4.5 equals Ö ( @Gr.GGaD. and is faster than n//'g'44
Theorem 4.4 gives us the rate Ô (DD2 n² + GraGra) Pyak In
Gr..D.) vR Otherwise, the rate in Theorem 4.5 equals GraDe v'n
comparison, the only last-iterate bound in the same setting is Ö
O
uDD K
(Liu & Zhou, 2024b). As one can see,
and is slower than O (Qra))) This observa-
μD² the higher order term n²x² achieves acceleration by factor م Hynk is also always faster due to G2 < fT 1.1 in the aforementioned inequality (I). If further assuming G; = G, Theorem 4.4 yields the rate Ö
tion suggests an interesting convergence phenomenon for the SS sampling scheme, that is the function value gap will during
of (nn Notably, the lower order term
decay in the rate no slower than Ō (VGrGGGDD,
the first (K.) epochs until reaching the Ō Gra.D. regime. We emphasize that this does not necessarily im- ply the SS strategy must bear constant optimization error since Theorem 4.5 only states a convergence upper bound. In other words, Theorem 4.5 improves upon (Liu & Zhou, 2024b) when K is small. Especially, if G. = G, the rate in Theorem 4.5 and the threshold K, n match the conver- gence behavior of a avg et al., 2022).
G²
(suppose K is large for simplic-
Vn
error
Mynk
ity) significantly improving upon the bound Ö
G2 F
in
(Liu& & Zhou, 2024b) by a factor of (nn2))
In addition, we also extend the convergence result to the stepsize 1/2 at for any m N like (Liu & Zhou, 2024b). The interested reader could refer to Theorem A.3 for details.
Kn-1 when ui = Ie proved in (Koren
Before ending this subsection, we should mention that though both Theorems 4.2 and 4.4 improve upon (Liu & Zhou, 2024b) and indicate that RR enjoys faster conver- gence than Proximal GD suggesting the benefit of ran- domness, these results are however still slower than Prox- imal SGD, whose last iterate is known to converge in 22 for general and strongly O CraDD and Ô [DD2 + af
The reader may not feel satisfied with Theorem 4.5 since the rate does not vanish as T becomes larger and could ask whether this is an inherent issue of Algorithm I under SS. The answer turns out to be negative, A simple but important observation is that when 3/ and T = Kn, Algorithm 1 with chuffinn-based i(l) and the algorithm studied in (Liu & Zhou, 2024b) are actually the same method. We recall key fact that the rate O GraD. in (Liu & Zhou, 2024b) is proved for any shuffling type as mentioned in Subsection 1.2 (or see Table 1). Hence, at least in the case of e O and T = Kn, we should expect refined upper bound that converges to 0 when K approaches infinity.
VT
functions, respectively (Harvey et al., 2019; Jain et al., 2021; Orabona, 2020; Liu & Zhou, 2024a). Whether RR can be proved to guarantee the same rates is unclear?.
<K
4.2. SS Sampling Scheme
We study the SS sampling scheme in this subsection. Unlike the always faster rates achieved by RR presented before, our new results for SS are better than (Liu & Zhou, 2024b) only when certain condition is met.
Built upon this thought, we prove the following sharper rate when s = Ic (i.e., constrained optimization) and T = Kn.
Theorem 4.6. Under Assumptions 2.1 (with sb = Ic) and 2.2, suppose T = Kn where K E N and the SS sampling scheme employed with the stepsize th- = 3/. Vt E [T] then Algorithm
Theorem 4.5. Under Assumptions 2.1 (with μ = 0) and 2.2, suppose the SS sampling scheme is employed with the stepsize Tt Vt Vi E [T] and = then Algorithm
and 1 (IN guarantees
D.
D.
V guarantees
(1+1ORT)
VGJGGaDD GJaD, n//K1/44 VK
E [F((aKat))- -
VGr.GrDD. =O T1/4
V GraD.
E E[F(
Remarkably, the above result integrates the advantages of Theorem 4.5 and (Liu & Zhou, 2024b) and is thereby faster than both. One point we remind the reader is that the existing analysis in (Liu & Zhou, 2024b) immediately invalids once C o TRd (equivalently & * 0) since in that case Algorithm I is no longer the same as the method in (Liu & Zhou, 2024b) due to different places for the proximal update as discussed in Section 3. Therefore, a more careful analysis is required to overcome this issue. We also mention that the condition
We begin with the general convex case in Theorem 4.5. To understand how the above rate compares to the bound
o G..DD when T Kn where K E N (Liu & Zhou, VR
nata f
2024b), we introduce a critical value K.
which
We incline a negative answer least for the general convex case. See our discussion after Corollary A.2 for why.
6

---

Improved Last-Tterate Convergence of Shuflling Gradient Methods for Nonsmooth Convex Optimization
= le can be further relaxed to d = + + le for yp being Lipschitz on C (see Lemma B.3 for details) as previously assumed in (Bertsekas, 2011). However, how to extend Theorem 4.6 to any general & and T' E N is unknown to us currently, which is left as an important future work.
5. Key Ideas and Proof Sketch
This section describes our key ideas in the analysis, provides the most important Lemma 5.1, and then uses it to sketch the proof. Any omitted detail can be found in the appendix.
Theorem 4.7. Under Assumptions 2.1 (with μ. > 0) and 2.2, suppose the SS sampling scheme is employed with the 2 stepsize T/p pi Vt E [T], then Algorithm I guaranteess
5.1. The Existing Analysis Misses Randomness
Before talking about our analysis, we first provide an in- tuitive explanation for why (Liu & Zhou, 2024b) can only achieve the same rate as Proximal GD. Roughly speaking, this is because (Liu & Zhou, 2024b) analyzes the shuffling gradient methods in a way similar to Proximal GD. More technically, their analysis views one whole epoch as a single update step (this also explains why their proximal step hap- pens at the end of every epoch) and then measures how close the progress made in every epoch is Proximal GD (see their Lemmas D.1 and D.3). Afterwards, they follow the way developed in (Zamani & Glineur, 2023; Liu & Zhou, 2024a) to prove the last-iterate convergence rate.
IuD. T2 +
GraG12 HVT
G7 pn
E [[F(2T+1) F.] F.
+
Lastly, we move to the strongly convex case. When T = Kn where K E N, one can check the critical time to balance the last two terms is still K,-
nO2,,
E (1, G2
Consequently, compared to Ō ( (up²
G3 μk
However, one key point missed in (Liu & Zhou, 2024b) is the randomness. Precisely, their proof for the nons- mooth case goes through whenever the index i(t) satis- fies {i((k - 1)n + 1),...,i(kn))) = [n]] Vk E [K] if T Kn where K E N (this also explains why their rates work for any shuffling scheme not limited to RR/SS (R/SS/IG) As such, results in (Liu & Zhou, 2024b) cannot reflect any potential benefit for randomly generated i()).
(Liu & Zhou, 2024b), Theorem 4.7 outperforms in the regime K S K,,
One may expect that when T is multiple of and v sat- isfies certain conditions, we can again obtain an improved rate better than both Theorem 4.7 and (Liu & Zhou, 2024b). However, even under some additional assumptions, the best improvement upon Theorem 4.7 we can obtain currently is the rate Ô nGG uk
(suppose K is large enough). Unfortu- nately, this is worse than Ō
5.2. Our Analysis Considers Randomness
G9 in (Liu & Zhou, 2024b). k
Due to the above discussion, natural thought arises, iden- tifying the role of randomness for RR/SS and trying to integrate it into the analysis.
Therefore, we simply leave Theorem 4.7 in its current form without providing any further refined result and hope that a bound faster than both Theorem 4.7 and (Liu & Zhou, 2024b) could be found in the future.
Let us first understand what randomness RR and SS have. A simple but important observation is that for both of them, regardless of the dependence between indices, every i(t) has the same distribution as the random variable uniformly dis-
Like the strongly convex case for RR, the stepsize in Theo- rem 4.7 can also be generalized to 17- put For details, see Theorem A.6.
m for any m N.
tributed on [n)]. i.e., i(l) 2 Uniform [n], VL E (7). Hence, we can make an abstraction here, i.e., consider any possible
To summarize, this subsection provides a new picture for the last-iterate convergence of the SS sampling scheme. Precisely, we show SS indeed boosts the convergence lead- ing to a faster rate than Proximal GD at least in the early optimization phase, which partially improves upon (Liu & Zhou, 2024b) and reflects the benefit of randomness. In the special case of constrained general convex optimization, we give an even sharper bound demonstrating that SS provably beats Proximal GD no matter how long the time horizon is. In contrast, such information missed in the best previous bounds (Liu& & Zhou, 2024b). However, the same as the RR strategy, there is still gap between SS and Proximal SGD. Understanding this difference is an important future work.
random process i(t) satisfying i(t) _ Uniform [m], Vt
[T] instead of limited to RR/SS.
Next, we think about how to inject this abstraction into a concrete analysis. A potential template we can try to follow is the last-iterate analysis for the standard Proximal SGD method (Liuu & Zhou, 2024a), where indices i(1) to i(T) are exactly mutually independent random variables uniformly distributed on [n]. which can be recognized as the extreme case. Moreover, note that Proximal SGD converges for any T E N, it is hence perfect candidate to help us remove the requirement T' = Kn for K E N used in prior works. Unfortunately, proofs in (Liu & Zhou, 2024a) cannot work directly due to the potential dependence between every i(t)
'The reader who wonders why we cannot do better could refer to the discussion of Lemma B.3.
7

---

Improved Last-Tterate Convergence of Shuflling Gradient Methods for Nonsmooth Convex Optimization
in the general case. Thus, our analysis contains careful changes and naturally diverges from (Liu & Zhou, 2024a). In brief, our plan is to analyze the last-iterate conver- gence of Algorithm (for general indices satisfying i(t) _ Uniform [x], VL E (T) in a manner inspired by Proximal SGD instead of Proximal GD. We clarify that though some analyses motivated by SGD have also appeared in (Nagaraj et al., 2019; Koren et al., 2022) before, there are however many differences. The first and most important one is that they only focus on thuffling-based methods without further abstraction on i(t). Moreover, their goal is to establish con- vergence for the average iterate in contrast to the harder last iterate. In addition, both of them only take 1a = Ic (i.e., constrained optimization) into account instead of general vb studied by us. Even more, (Nagaraj et al., 2019) additionally requires smoothness on ft. (Koren et al., 2022) only has re- sults for the general convex case, and both of them assume G = G. As the reader will see, our core Lemma 5.1 holds for general i(t) and gives a novel sufficient condition for the last-iterate convergence working any vb under minimal conditions, Assumptions 2.1 and 2.2. Hence, although the high-level idea may sound similar, our analysis significantly differs from theirs.
mentioned before. Condition 2 is satisfied by almost all com- mon stepsizes. However, we remark that it is actually not necessary and only for simplicity. Even without it, the rate still holds with the only change n7 to (n V Mc+1). Condi- tion 3 is the most important. Intuitively, it says that even i(t) and Dg are possibly dependent leading to E [x,)( * 0 (equivalently, EE [[ie)))==)]] + E (f.,)))) Algorithm still guarantees the last-iterate convergence once | [0, [z)) can be controlled by the value of nis with another multiplica- tive factor 4 2 O. Notably, the smaller & is, the better the convergence rate is. As a sanity check, we consider Proxi- mal SGD and notice that & = 0 in this case. Then Lemma 5.1 recovers the existing bound in (Liu & Zhou, 2024a).
Armed with Lemma 5.1, to prove a last-iterate convergence rate for Algorithm employing any general random index i(t), it is sufficient to find the corresponding constant Φ Here we claim that under the same setting of every theorem in Section 4, there is always
( (VT ( GT + + 0
{or o
for RR for SS
With these two values of & and the inequality (l), i.e. Gリ I Gy22 vnG we immediately conclude The- orems 4.2, 4.4, 4.5, and 4.7 after plugging in the stepsize. However, we remark that finding these two values is not a trivial task for RR/SS. Though some clues on how to bound [E [x,)l can be found in prior works (Nagaraj et al., 2019; Koren et al., 2022), our goal is more general and hence harder since we need to bound |E [24(2x)) by a time-dependent stepsize 7)s for any S l. More importantly, our fine-grained analysis on Gr and 222 is the key to establishing the superiority of our convergence results over (Liu & Zhou, 2024b), which cannot be found in (Nagaraj et al., 2019; Koren et al., 2022) due to their simpler settings as mentioned earlier.
5.3. A New Sufficient Lemma for the Last-Iterate Rate
Due to limited space, we will not provide formal analysis but only state the core result, Lemma 5.1, new sufficient lemma giving the last-iterate convergence rate.
Lemma 5.1. Under Assumptions 2.1 and 2.2, suppose the following three conditions hold:
1. The index satisfies i(t) 2 Uniform [n], Vt E [T].
2. The stepsize Tt, Vt E [T] is non-increasing.
3. IEE (1, < Tn VL E [T), 8 E [4] where se(-) fun - f()) E [T] and & 2 0 is a constant probably depending on T, n, pa and G2 to Gn,
Lastly, we briefly discuss Theorem 4.6. Due to the depen- dence on T in & for SS, the above analysis is inadequate. However, as hinted by (Liu & Zhou, 2024b) (though algo- rithms are different), one should expect that SS at least provably converges as fast as Proximal GD when T = Kn for K E N. As such, we will combine some other tech- niques to obtain Theorem 4.6 and not discuss them here.
Then Algorithm! 1 guarantees
E [F(TT++)
- F.]
D2
T
50
+ (Gf.2 + +)
E 1em
T
== YoA
6. Conclusion and Future Work
V where 7/+ A =II=)( p1)) [T+
We provide improved last-iterate convergence rates for non- smooth (strongly) convex optimization under both RR and SS sampling schemes, showing they are faster than Prox- imal GD (conditionally for SS) and enjoy the benefit of randomness. Two valued problems are left to be addressed in the future. One is to explore whether our rates for RR are tight. The other is to prove better bounds for SS if possible.
Remark 5.2. We again assume the existence of an optimum v. E R2d and use the notation D. ||ær. x ||. See Lemma B.2 for the full version valid for any e Rd
We first talk about the three conditions in Lemma 5. Condi- tion 1 is from the abstraction of the randomness in RR/SS
8

---

Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
Acknowledgments
plexity. Foundations and Trends@ in Machine Learning. 8(3-4):231-357, 2015.
This work is supported by the NSF grant BCCCS-241956) We also thank the anonymous reviewers for their valuable comments,
Cai, X. and Diakonikolas, J. Last iterate convergence of incremental methods as model of forgetting. In The Thir- teenth International Conference on Learning Represen- lations, 2025, URL ht https: /ttp:////peeeeeeeeeeeeeeeeeeeeee nnt// forum? dd
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Cai, X., Lin, C. Y., and Diakonikolas, J. Tighter con- vergence bounds for shuffled sgd via primal-dual perspective. In Globerson, A., Mackey, L.,, Belgrave, D., Fan, A., Paquet, U., Tomczak, J., and Zhang, C. (eds.), Advances in Neural Information Processing Systems, volume 37, pp. 72475-72524. Curran Associates, Inc.,
References
2024. URL htwp:::tt//cctc https::/prroeeedlnga neurips.
Ahn, K., Yun, C., and Sra, S. Sgd with shuffling: optimal rates without component convexity and large epoch requirements. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 17526-17535. Curran Associates, Inc., 2020. URL /t/ppppe__flleeppppprr////////// mew..e. co/paper_ (bfacb..es8211117466463333333339 Paper.pdf.
cc/paper Sacaaper_fieespppeee hitpperr_iLlee/ppppre////////a
Paper-Conferencee
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, B., Sabato, S.. and Scarlett, J. (eds.), Pro- ceedings of the 40th International Conference on Ma- chine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 3855-3912. PMLR, 23-29 Jul 2023. URL htth:t::: http://ppocecee.ceee/e/ee/e / mlr press/ p
Bassily, R., Feldman, V., Guzmán, C., and Talwar, K. Stability of stochastic gradient descent non- smooth convex losses. In Larochelle, H., Ranzato, M., Hadsell, R., Balean, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 4381-4391, Curran Associates, Inc.,
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 Journal on Optimization, 29(4):
2020. URL https: http:://proeeddigg..eeee. cc cc/paper httpee/ffileeepppe////0////e
2019.
Paper.pds pdf.
Gürbüzzalaban, M., Ozdaglar, A., and Parrilo, P. A. Why random reshuffling beats stochastic gradient descent. Mathematical Programming, 186:49-84, 2021.
Bengio, Y. Practical recommendations for gradient-based based training of deep architectures. In Neural Networks: Tricks of the Trade: Second Edition, pp. 437-478. Springer, 2012.
Haochen, J. and Sra, S. Random shuffling beats SGD af- ter finite epochs. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Confer- ence on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2624-2633. PMLR, 09- 15 Jun 2019. URL https: https::/proceee:::ee /pw.ceedoooceeeeoee mmlr. press / vv7 htt.h/hchhen11 9a html.
Bertsekas, D. P. Incremental gradient, subgradient, and proximal methods for convex optimization: A survey. 2011.
Bottou, L. Curiously fast convergence of some stochastic gradient descent algorithms. In Proceedings of the sym- posium on learning and data science, Paris, volume 8, pp. 1624-2633. Citeseer, 2009.
Harvey, N. J. A., Liaw, C., Plan, Y., and Randhawa, Tight analyses for non-smooth stochastic gradient de- scent. In Beygelzimer, A. and Hsu, D. (eds.), Pro- ceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learn- ing Research, pp. 1579-1613. PMLR, 25-28 Jun 2019. URL https: /ttp///eeccegg...ce//e////c mlr. press press/vs9. v99/ harveyl 9a html.
Bottou, L. Stochastic gradient descent tricks. In Neural Networks: Tricks of the Trade: Second Edition, pp. 421- 436. Springer, 2012.
Bubeck, S. et al. Convex optimization: Algorithms and com-

---

Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
Jain, P., Nagaraj, D. M., and Netrapalli, Making the last iterate of sgd information theoretically optimal. SIAM Journal Optimization, 3102):108--113, 2021. doi: 10.1137/19M128908X, 1137/1 9M1 28908X.
Learning, volume 235 of Proceedings of Machine Learning Research, pp. 32471-32508. PMLR, 21-27 Jul 2024b. URL https::/pproceeeeeeee httss//235/liu24ggg
.mlr.
https: htt///ii.orrg//////
Lu, Y., Guo, W., and De Sa, C. M. Grab: Find- ing provably better data permutations than random reshuffling. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Ad- vances Neural Information Processing Systems, volume 35, pp. 8969-8981, Curran Associates, Inc., 2022a. URL httpss/procceelmm neurips. cc/paper_ //aappee_fflle/pppper/////////L Sacd442222187efas5222aaedddd Paper-Conferenceee pdf.
Josz, C.,, Lai, L., and Li, X. Proximal random reshuf- fling under local lipschitz continuity. arXiv preprint arXiv:2408.07 201220088..., 2024.
Kibardin, V. Decomposition into functions in the minimiza- tion problem. Automation and Remote Control, 1979, 1979.
Koloskova, A., Doikov, N., Stich, S. U., and Jaggi, M. On convergence of incremental gradient for non-convex smooth functions. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A.,, Oliver, N., Scarlett, J., and Berkenkamp, F. (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Ma- chine Learning Research, pp. 25058-25000 PMLR, 21- 27 Jul 2024. URL https: /ptpc/edioocceeeeseoooooo mlr.. html.
Lu, Y., Meng, S. Y., and Sa, C. D. A general analysis of example-selection for stochastic gradient descent. In International Conference on Learning Representations, 2022b. URL https: /pwp/eeeeeeeweeeeeeeeeeeee net forum? id= id=7gwSJrP3opE.
press/v233
Mishchenko, K., Khaled, A., and Richtarik, P. Random reshuffling: Simple analysis with vast improve- ments. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin. H. (eds.), Advances Neural Information Processing Systems, vol- ume 33, pp. 17309- Curran Associates, Inc., 2020. URL
Koren, T., Livni, R., Mansour, Y., and Sherman, U. Benign underfitting of stochastic gradient descent. In Koyejo, S., Mohamed, S., Agarwal, A., Bel- grave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, vol- ume 35, pp. 19605-19617. Curran Associates, Inc., 2022. URL https://procceediin neurips. co cc/paper_fiie ppaper_filees/pperr////////L Tlodf4eebcctecceee1088886786 Serer-Conference..oe pdf.
neurips. c8cc siapeer_fiie///pppe/222///L Paper.pde
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, volume 162 of Proceedings of Machine Learning Research, pp. 15718-157271 PMLR, 17-23 Jul 2022. URL https: http::::///ccceeeppeeeeoo .mlr. press / v1 62 m www.hsshhhhhhacacccccccc html.
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 methods for weakly convex optimization. arXiv preprint 10X. 2019.
Li, X., Milzarck, A., and Qiu, J. Convergence of ran- dom reshuffling under the kurdyka lojasiewicz inqquality. SIAM Journal on Optimization, 33((): 2023.
Mohtashami, A., Stich, S., and Jaggi, M. Character- izing finding good data orderings for fast conver- gence of sequential gradient methods. arXiv preprint arXiv:2202.01838 2022.
Liu, Z. and Zhou, Z. Revisiting the last-iterate conver- gence of stochastic gradient methods. In The Twelfth International Conference on Learning Representations, 2024a. URL https: http:///opnweeeeeeeeeeeem www.iiewwwweeeeeeeeeeeeeeeeeeeee forum? 1d=xxaEhwC114.
Nagaraj. D., Jain, P., and Netrapalli. SGD without replace- ment: Sharper rates for general smooth convex functions. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceed- ings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learn- ing Research, pp. 4703-4711. PMLR, 09-15 Jun 2019. URL httht:////// http:////ooceeneeeeeee mlr. pwwss/evvv nagarajl 9a html.
Liu, Z. and Zhou, 7. On the last-iterate conver- gence of shuffling gradient methods. In Salakhutdi- nov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F. (eds.), Proceed- ings of the 4 sss International Conference on Machine
10

---

Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
Nedić, A. and Bertsekas, D. Convergence of incre- mental subgradient algorithms. Stochastic optimization: algorithms and applications, pp. 223-264, 2001.
Qiu, Li, X., and Milzarek, A. A new random reshuffiing method for nonsmooth nonconvex finite-sum optimiza- tion. arXiv preprint
2023.
Nedic, A. and Bertsekas, D. Incremental subgradient methods for nondifferentiable optimization. SIAM Jour- nal on Optimization, 12(1):109-138, 2001.
Rajput, S., Gupta, A., and Papailiopoulos, D. Clos-
ing the convergence gap of SGD without replace- ment. In III, H. D. and Singh, A. (eds.), Proceed- ings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 7964-7973. PMLR, 13-18 Jul 2020. URL wtw.::tttps..ccm pttpttts::/pprceeeeee http://oooeeddegee ngs. ml p.eess/ v119 v119/rajpute
Nemirovski, A. and Yudin, D. Problem complexity and method efficiency in optimization. Wiley-Interscience, 1983.
html.
Nesterov, Y. et al. Lectures on convex optimization, volume 137. Springer, 2018.
Rajput, S., Lec, K., and Papailiopoulos, D. Permutation- based SGD: Is random optimal? International Confer- ence on Learning Representations, 2022. URL https: / oppprevveew.... net/ forum? d=Y 9HKTyXE.
Nguyen, L. and Tran, H. On the convergence to global solution 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. 75545-75566. Curran Associates, Inc., 2023. URL htc//ppee_ffillesppperr///2///// http://pprcceeiiign.eeee.pppppps neurips.
Safran,
Shamir, How good is sgd with ran- dom shuffling? In Abernethy, and Agarwal, S. (eds.), Proceedings of Thirty Third Conference Learn- ing Theory, volume 125 of Proceedings of Machine Learning Research, pp. 3250-3284. PMLR, 09-12 Jul 2020. URLhttps: /ttpt:p::/pprceeeeeee http///ppceeeeeggeeeeeee/e mlr. / v125 safraaa0aa00. html.
ce6671ae775e3313337f222222333883 Paper-Conference.. pdf.
Safran, I. and Shamir, O. Random shuffling beats sgd only after many epochs on ill-conditioned prob- lems. Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances Neural Information Processing Systems, vol- ume 34, pp. 15151-15161. Curran Associates, Inc., 2021. URL https: .eurips. //t/apeerfillee/ppppr///////// 803e555436044440ccccc33333333333 Paper.
Nguyen, L., NGUYEN, P. H., 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 Conference on Machine Learning, volume 80 of Proceedings of Machine Learn- ing Research, pp. 3750-3758, PMLR, 10-15 Jul 2018. utLhttps:: /ttptt:s:/pproceeeee ngs ml wwwpprrsss/v... agayen18c.htm.
Nguyen, L. M., Tran-Dinh, Q., Phan, D. T., Nguyen, P. H., and van Dijk, M. A unified convergence analysis for shuffling-type gradient methods. Journal of Machine Learning Research, 22(207):1 2021. URL http: html.
Shalev-Shwartz, S. and Ben-David, S. Understanding ma- chine learning: From theory to algorithms. Cambridge university press, 2014.
//jmlr. wttpoopppppep///////2//.2//
Shamir, O. Without-replcemment sampling for stochas- tic gradient methods. In Lee, D., Sugiyama, M., Luxburg, U. Guyon, I,, and Garnett, R. (eds.), Advances Neural Information Processing Sys- tems, volume 29. Curran Associates, Inc., 2016. URL.
Orabona, F. Last iterate of sgd converges (even in unbounded domains). 2020. URL https:
//pparameterfree.ee com/ http://eeee..cecee////////////// -oeerrtte---ss---oooeeeeeeeeeeee 20tmm//0000/////tttttt lebounded-domainnn
https::/prroceddingg neurui cc/paper bitaaper_file/ppeeee https//eeeee//ppp////////// 07449100leea2337e4aaaabbbbee Paper.
Pauwels, E. Incremental without replacement sampling in nonconvex optimization. Journal of Optimization Theory and Applications,
190())))) 190(1):274-299 2021.
Sherman, U., Koren, T., and Mansour, Y. Opti- mal rates for random order online optimization. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, vol- ume 34, pp. 2097-2108. Curran Associates, Inc.,
Qiu, J. and Milzarek, A. Random reshuffling with momentum for nonconvex problems: Iteration com- plexity and last iterate convergence. arXiv preprint arXiv:2404. 18452, 2024.

---

Improved Last-Iterate Convergence of Shuflling Gradient Methods for Nonsmooth Convex Optimization
2021. URL http::/prroceddngg.rrrrrii / 007000a6880766ocddee1eeeeee333 Paper. pdf.
Solodov, M. Incremental gradient algorithms with step- sizes bounded away from zero. Computational Optimiza- tion and Applications, 11:23-35, 1998.
Tran, T. H., Nguyen, M., and Tran-Dinh, Q. <Smg: A shuffling gradient-based method with momentum. In Meila, M. and Zhang. T. (eds.), Proceedings of the 38th International Conference Machine Learn- ing. volume 139 of Proceedings of Machine Learn- ing Research, pp. 10379-10389, PMLR, 18-24 Jul 2021. URL URLhttps: /ptpc/eeeceeenssseeeee wwm. press/ v139/tran2lb.hnm htmll.............m..mmm...m....
Tran, T. H., Scheinberg, K., and Nguyen, L. M. Nes- terov accelerated shuffling gradient method for convex optimization. Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Pro- ceedings of the 39th International Conference on Ma- chine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 21703-21733 PMLR, 17-23 Jul 2022. URL pwtpppooooddoooooooooooo mlr / v1 2162ttra22a 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, (7):): 474 489, 2018.
Yu, H. and Li, X. High probability guarantees for random reshuffling. arXiv preprint arXiv:2311.11841, 2023.
Zamani, M. and Glineur, F. Exact convergence rate of the last iterate in subgradient methods. arXiv preprint 13314:2307.11134 2023.
12

---

Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
A. Full Theorems
In this section, we provide the full version each theorem presented in Section 4 and the corresponding proof. The proofs of lemmas used in the analysis are deferred Sections B and C later. One point here we want to remind the reader is that our new last-iterate results (except Theorem A.5) hold for any T N instead of only T Kn for K N used in most of the existing works for shuffling gradient methods mentioned in Subsection 1.2.
A.1. RR Sampling Scheme
We first consider the general convex case in Theorem A.I. One notable thing that, under the first stepsize choice, the extra logarithmic factor can be shaved off once q(T) () T [n log n) previously mentioned in Theorem 4.2. Finding stepsize that can remove any extra logarithmic factor without requiring T = 92(n log will be an interesting task. Theorem A.1. (Full version of Theorem 4.2) Under Assumptions 2. (with μ = 0) and 2.2, suppose the RR sampling scheme is employed:
Taking the stepsize Tte ((T))((0+11 VE [I'], then for any z E Rd, Algorithm I guarantees q(T)VT
[[F((T+1) F(z)) 0 2|2-=111
((Ii===l"* +nVnGgaagr 1+ log n
)
q(T) VT)
Setting n1/4 Go,.Gr,
2-
optimize the dependence parameters.
loRn
Taking the stepsize The J Vt E [T], then for any 2 E IRd, Algorithm 1 guarantees
(( 1
1 VT
E ([ - F(z)] =())) so
Setting w1/4 n1/4 C
optimize the dependence on parameters.
Taking the stepsize n
Vi Vt (T), then for any z E Rd, Algorithm I guarantees
E ( -F())))))((()15555 so ((1==1 π
F(=))
1 VT)
1
Setting 17 n1/4 /Gy
||=- to optimize the dependence on parameters.
Proof. Note that the RR sampling scheme satisfies i(l) Uniform [m], 74 E [T], and all these stepsizes listed are non- increasing. Hence, Conditions and in Lemma B.2 are fulfilled. If Condition 3 also holds, i.e., | [E,(())))) Pnps Vt [T') E [t] for some & 0, we can invoke Lemma B.2 to obtain for any E Rd
2 211
T
Y
B(F( F(z)] < 0
+ (G)
$
Σ7 -1=1 767
[=]
s=!
Ys
|2 2212 12
T
T/
=0
+ (G7,22 +)
(2)
Σr 1/
Es=t 1]s
where the second line is by = -I'' [1+ pm))) = 1, Vt E [T' + 1] since μ = 0 now.
Our next task is to find a constant 2 0 satisfying
|E [[((x.)] < D7e. Vt E [T], E [t].
For all stepsizes listed, we claim
4 G2
(3)
To prove our statement, we apply Lemma B.4 with μ = have:
13

---

Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
I [(q(t) 1)m), there is
E [2,() 0 > | [ 0 -
47s-
If [[((t))()) 1)m] (which implies g(s) = (t)), there is
V2G72
2v 2v2G
1
E
(2,)ll
Σ
n2 +
n
n
(=(9(()
1)++1
(= 11)++1
j=i
(a)
V222
2/2G
1.2
Σ
Σ
vs inp
7
n
n
)=(q(1)-1)n-t
(a((0-1))+1
2 /7 + J.
8-1
Σ
(4)
n
(=(q
where (a) is because Fγ is non-increes non-increasing and (b) is due to vs - S V (q(t) - 1nn-inn------
I = vr(s) S vn
when E {(q(t) - 1) 1)m + 1, ..... , 1}. Note that if s = (q(t) 1)m + 1, [(. = 0 47/s. Hence, we assume (q(4) - 1)n + 2 S 8 S in the following.
For the stepsize satisfying 7/2 (1a(t)-1)++1 AI (T) (the first two), we observe that (q(() 1)m + 1 مSjS
8 - 1 + T 11q(0)-1)a+ = 1/.- Therefore,
Σ
7= (r(s) 1)n, S nn..
(5)
)=(9(t)-1)at
Thus, there is
(4)(5)
(3) V2 + +2/nGG,1G122) ns S om.
E [x,(l
S
For the stepsize n7
Je Vt [77, we know
Σ
1
S1 f
(111)-13m dj = 277 V(a((t)()))))))))))))))<<)) 1)n)
1
m1 =
(=(a(() - 1jn+1 vj
i=(a())-1)++
(r(sr - -1)
2(r(s) 1)v3 173 S 22/2nn
(6)
V + ((((1) - 1)n V V(q(t) - 1)m
where the last step is by 21r(3)
(a(t)--1) 2 ب < <2/2n when s 2 (q(t) 1)m + 2 2 2. Thus, there is
(4)(6) E (x,(2.))
2 4 (C,,2 + +2 7 Φn.
By (2) and (3), we have for all these stepsizes
-P(FT-))-F(3))
2 - 11
+ (G,,22 VnG
T
nf
Σ 11t
Σ
1=1
s=
1ls
||2- xi 1|2
0
+ VnGG,a5222 Σ
m
Σ Ei=1 11t
ΣJ
173
where the last step is by noticing 2522 fT.
For the stepsize N)- = 1) 9(1)) VI E (T]. by applying Lemma C. with n,
we know ΣT 2 DVT
q(T)/T
q(''T
and Σ
oi < On
(1
log n q(T))
which implies
Eime n 2/T
| [ x
(1+
log n qT))
1
[[F( - F(=)] 50 (0
+ #NNGG,,GGR
VT)
14

---

Improved Last-Iterate Convergence of Shuflling Gradient Methods for Nonsmooth Convex Optimization
Setting 1) = n1/a n//a/ GraGra
to obtain
log 203)
n!/4 V -x1ll
log q(2p
E [[ - 5x) 0o
VT
Particularly, q()) 2(logn) + - log there is
n/ VG || x1
B[ P(z)] so
VT
For the stepsize 7)+ =
7 /
Vt E (T], we know
T
n11 + log T)
T i
VT
s=
Hence, we have
(11==0111 GT.G,,1Gr2211 + log logT)
1
B[ So
Setting 1]
2 m
to obtain
n /H////11122l==
x1ll VT --
log
E [[ - F(z)) so
VT
For the stepsize 7) 2 Vt E [T]. we know for any t E [T].
Σ Σ Σ 11
T+1
1
ds
-1 VO),
V8
which implies
T + Vi
VT+I
1
vt) =
Σ
2m Σ t(T +1
t(vT
((vT+I
t(T +
t=1
1=1
[=1
27
Σ
T
1
1
4n(1 + log T)
vT+
T+1-t
+T+I
Hence, have
((I=-aul)
1
E [[ F(2)) < 0
WTGG,,G5221 + log 7)
1)
VT
Setting 1) n1/4 | to obtain
VG,,
xill (1+ log
E [[((TT+1) F(z)]
VT
15

---

Improved Last-Iterate Convergence of Shuflling Gradient Methods for Nonsmooth Convex Optimization
Built upon Theorem A.I, give the following rate for suffix +
T++ Lt=T #t+1-
Corollary A.2. (Full version of Corollary 4.3) Under Assumptions 2.1 (with μ 0) and 2.2, suppose T and the RR sampling scheme is employed:
Taking the stepsize Tre 17, Vt E [T), then for any E Rd, Algorithm guarantees (additionally assuming T 2 2(n 1
|= - x1ll
((07+1)
sutti F(z) 0
+ CT
n/T
Taking the stepsize Th-
vt E [7], then any 2 E Rd, Algorithm / guarantees 2 v
F(z) 0 ( |a= x1
E
F(x (Ufi
Wi log
n
VT
Proof. Both results are directly implied by Theorem A.1.
For the stepsize 17. vt E [T), we invoke the second result in Theorem A.1 (under changing to n/T in it) to obtain
||= | x 1 + Gra
B [[((T++1) - =
00
T/
Note that the above result actually holds for any T E N. Hence, there is by convexity
T
T
||2 - x
E
F(
suffix F(z)
Σ
(1 - =
Σ
+ #nvnGy1Gy2(1 + logt)
T=
I=T-n
Moreover, we have
T
(a)
T Σ T=T=++1
and
1 logt < + log T,
T
+1
T
T=
where we use 7' 2(n 1) in (a). Finally, we obtain
(1=-2z11) 1111=111" GWGG
[|
F ((x F(z)] 5o
T/T
For the stepsize '/. / Vt [T], invoke the third result in Theorem A.1 and follow almost the same steps for proving Corollary 4.3 to conclude.
We emphasize two important implications of Corollary A.2.
The first one is that under the same setting in the proof of lower bound (Koren et al., 2022), i.e., Ie where C is the unit ball, G; = 4, T Kn, = O. the existence of x. E argmin F(x), and m/: 7,, we have
E F(
F.. s
mK + +vnn(1 + log
where F(x.). addition, notice that now
F Fufff kn++)
) F. f
suffix f(x.) s G₁.1
suffix [K++1
x, < 58=0 0(1).
*hii requirement can further relaxed 2 (1 +1++0 c) - 1) for any e 0. We simply choose c
16

---

Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
We hence obtain
1
+ nVT(1 + log nk)) nk)))
E
F F(*
- F. s O min ( mnn (xK+1))
suffix
Remarkably, this rate matches the lower bound 5 min { mink + +vva) of the suffix average for the last one epoch exactly by up to an extra logarithmic factor. Therefore, we (almost) close the gap.
The second one is related the discussion in Footnote 2, which is that we suspect the O (or O
/ when = Kn where K N) is tight for the last iterate under the RR sampling scheme in the general convex case. By the first implication above, one can see our last-iterate bound Ô
vT
WfT + vVn)) for the constant stepsize = 17 (we only include
n, and I' in the rate for simplicity) is almost tight by up to extra logarithmic factors. This because if one can establish the following bound
(1) nT
+ mv/)
E [F - F.J s
then, using the same proof of (7), there will be
F( F. so min 1, '/ + a mmm))
which contradicts the lower bound ?2
1 qak + vv/z) (Koren et al., 2022). Hence, at least in the case 77 17. our last-iterate result Ō + mV)) should be tight, which immediately implies that Ō
min {
1/4 vT
is also tight by picking the
2//44
optimal 1). As such, we conjecture that the rate when the stepsize is not constant.
is tight for RR the general convex case though we cannot prove VT
Next, Theorem A.3 shows the convergence rate when vp is j-strongly convex, e.g., the common regularizer (xx) -/2 ||
Theorem A.3. (Full version of Theorem 4.4) Under Assumptions 2.1 (with μ 0) and 2.2, suppose the RR sampling m VI E [T] where m E N, then any z E Red, Algorithm I guarantees
scheme is employed with the stepsize 1/t XE
|= -5=1111** 21l1? m++T)
mVT + log +og
E [[((TT+1) F(2)] So
nT
Proof. Note that the RR sampling scheme satisfies i(t) _ Uniform [n], vt [T], and the stepsize nee is non-increasing. Hence, Conditions and in Lemma B.2 are fulfilled. If Condition 3 also holds, i.e., [E (xx))) S 4 VI E (7) (4) for some & 2 0, we can invoke Lemma B.2 to obtain for any Rd.
jut
2 x 11
E [[F(ar+1) F())) So
+ (G7 (G7
(8)
-=1 Talle
t= Ls 7/8)/
where 7 IT + pm.)) Vt [T+ 1].
When 1/2- pe: vt (T), there is
(m t 1)!
(m - 1)
(m+ vt E +1],
Y
s
m!(t- - 1)!
m
which implies
(m + - 1)!
1 (m + t 1-1) 1) Vt E [T.
70
(9)
ml(t 1)!
μtt
μ m -
Therefore, we know
Σ
T
1 T
m + t 1
1
T
m
+t
m + 1)
p (
1 m + +
-
(10)
1
m
m
tml
17

---

Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
and
T
71
m 1)t
T
1 1
2m + log
(11)
M
p(T
+ t=1
T
+
s= 7s
1=1
1=1
where (a) is because Telp non-decreasing in as shown in (9). We combine (8), (10) and (11) to have
1 |=|= -1 x m (G9,2 + 1 (1 + log T)
- 30
(12)
(m+T)
Our last task is to find constant & 2 0 satisfying
E [[c(xx))] S 27,, Vt E [T] E [t]
Here we claim
t V2G7,22 + 2v
(13)
To prove our statement, we use Lemma B.4 to have:
i [(q(t) 1)m], there is I [()()(()))) 1 mm), there is
E [x,() = 0 -
E [2 (xx)]] S D7
E (x) 5
V2G²,2 f.2
Σ
7o +
2V2G,,1Gr
Σ
%
?
i= 1)m))
V2G2
B/2G,.1Gr
1.2
1/ +
Σ
Σ
1/
)=(a(()-1)ntt
(((t)-1))+
j=1
(0)
(22 + 2V 222nn,,,G.r. n7 MM
where (b) holds by 73%6 < 1k, Vj E is 1] since 7:7h is non-decreasing as shown in (9) and (c) is due to
Σ
ns = (r(s) 1)m S mm,.
f=(q(t) 1)++1
Σ
Σ
11
Σ
Vs- - ins S n ns.
k= (q()) 11))))1))++1
f=1
-1)m())1)m+1
By (12) and (13), we finally have
m G2 VnGG,1G12) + (1 + 1lg T)
/. /| - 21l
-F())) 50
(m+T)
nT
# /1| x 2
mVGGGr,GGyalll + log
00
(m+T)
m
where the last step is by using 2I < f.
18

---

Improved Last-Tterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
A.2. SS Sampling Scheme
First, Theorem A.4 below gives the convergence guarantee for general convex functions (i.e., μ 0). Unlike the previous Theorem A.I, currently do not know how to design proper stepsize get rid of the extra logarithmic factor, which leave future direction. Another crucial fact is that we also have idea how to set vareing stepsize. Loosely speaking, this is because & depends on T now. See our analysis for details.
Theorem A.4. (Full version of Theorem 4.5) Under Assumptions 2.1 and (with μ = 0) and 2.2, suppose the SS sampling scheme is employed with the stepsize 1nt VT. 1I E [T], then for any E Rd, Algorithm I guarantees
||= (
E [[F(Tr-1) - -Fx)] 00
(q(T)G7, V (nq(T)) (1 llgg))g))
1
7
VT
Setting 1) (o(T)GG (all)) (1+loTTT) to optimize the dependence on parameters.
2= |
Proof. Similar to (2), if we can find a constant 2 such that
[E [2())))) S Dme Vt E [T], E [t]
Then there is
E ([F(xT=)--((2) 5o
2|- x1-2111
(G + .)
Σ q
(14)
E1=1
Lo=t 179
1=1
Here, we claim
Φ = =qq + (2/2a/))222//(())
(15)
To prove our statement, we invoke Lemma B.6 with μr = to have for any E [T] and s E [t].
1 [r()) + r(())]
E (x,)))
S4G²
f
= [()))
n n-1
n
s-1
nG G²
Σ Gi
Σ 1
+ = r(t)
[r(i) # r(0)
n
1=1
j=1
4(2'n
1 [ (+G)+r((1) (r(()) =r(t)]+
<4G²
Σ n
f. 1,2
n
==1
2 Σ Giy
(T)
nG G? (r(i) # r(0))
Σ ni
G2 01(6) +1+0166)- r(t)
(16)
i=1
where the second step is by s < q()) I n.. Note that when the stepsize constant, there are
c
(r() - = 7/ Σ
q(T)m
1 ((( 4 (10))((1)))) = =2q(T))s
Σ Mi
(r())
n 1-1
(((0)r(())
(17)
n-
j=1
and
+.2+011000 = -()])+ nG G?
Σ
2
[r()) # r(0)
n n-1
#=1
q(T) Σ
nC G
=
+ -())
1
[r()) + r())
=2ng(T)G)
(18)
n-1
0=1
19

---

Improved Last-Tterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
Combine (16), (17) and (18) to obtain
E [ <88(TT))) + 2222n(())G no (15) D.le.
By (14) and (15), we have
|| x1
T
1/
E B[F(2r-1) - F(z)] 0
( + Vnq(T)G)AAGa)
Σ
Σ 1/t
2 111
(q(T)G7; V
Vi
- 4/
Les
|| æ112
+ +n + / (1 +og
1
vT
2z wi
+ (1()))) (ng(())GaGGpa)) (1 (1+1ogZ)
= 0
vT
where (a) is due to s (T)) and (b) holds by plugging in 7 = J. vl E (T..
Finally, setting
2-
to obtain
V /(ornoa..//aaa))G..... (1+)og))
(1+logT)
V Va(T)CT2 Vnq(T)G,,1Gaa 2i VI log
-(()) 50
VT
IAG
|n//4 GG,
VG,1G12 T1/4
G122 vn
||2
x1ll V1 11++oggT
(19)
VT
where (c) is by noticing q()) < T + and G22 < VTG together implying
T WT
((T))72 V Vnq(T)G,,
0 (VTVNNNN)))))))
( (VIVnG/aG(2)
00
o
(VnG)aG/2 VTG _ G12)
1/4 I. VT 5 317.. (19) thus reduces to the following form used in Theorem 4.5
When 7' 2 n, we observe that
(
VGJaGy2 T1/4 Vn
G122
([(())4))F(())5
| - /1 log
The above Theorem A.4 (or see (19) for the final bound) is not very satisfying as the rate will be blocked Ô if I' approaches too. As discussed in the main text, if ab Ie and T' = Kn where K E N, we actually can do better. Note that 1 = Ic can be further relaxed to き P + Ic for &o being Gi-Liccchitz on C. However, this will introduce new parameters Gy in the final rate. Instead, we choose to keep the following simple form. For why the relaxation holds, see Lemma B.3.
20

---

Improved Last-Tterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
Theorem A.S. (Full version of Theorem 4.6) Under Assumptions 2./ (with v Ie) and 2.2, suppose T Kn where K N and the SS sampling scheme employed with the stepsize 1/t V 4t E (7), then for any R. Algorithm I
guarantees
(1=-0011 +1 (VTKGyaGGaAnnC:) (
E ((((k)+)) - F(z)] S
log nk) logkk)
1
Vnk
Setting 11
V[ )0 (l)g to optimize the dependence on parameters.
1 2-- ||
Proof. Under the stepsize 1)t- =
7 E (T), we first know by Theorem A.4,
VT
2 - xi 2
E [[ - F(x)] 50
+ (9(2)G7, V (1 log
2 xill? +1 KG V VVKG)/1012) (1 + lognk)
1
+ -
(20)
VnK
where in the second line use (7') K when T' = Kn.
Next, note that the SS sampling scheme and the stepsize n = 2 Vt [T] respectively satisfy Conditions 1 and 2 in Lemma B.3. Moreover, we can take = and Gy = in Condition 3. Hence there is almost surely for any x E R
F(œKn+1) F(z) 50
|z æ1l
GM Σ
1
k: +1
Vnk
12- 11l1
0
+ +mmG7a2 + log k)
Vnk
which implies
((1=-
(12-x111
E [[((akn11)))) - F(2)] [(()) 50
+ mmG log log K)
(21)
Vnk
We combine (20) and (21) to obtain
12-21l1 +n (KGT2 V VVKGG,GGa)) A AnO7,)
E [[ - F(x)] 0
(1 log nk)
1)
Vnk
|| | x111 21
=0
+
log (kg
Vnk
71
where we use the fact (a V Vob) b = Vab A b for = KG, and b = nGJ,1 Finally, Setting
V(Vnka,,G الا
(1+llggk)) to obtain
G 2 ((VCASIT n1/44///4
x1ll / 1z-xill
log lognK nK
Finally, we establish the convergence upper bound for strongly convex functions in Theorem A.6. As mentioned after Theorem 4.7, we actually can improve the rate further to avoid the (1) barrier when T = Kn where K E and :2 + Ic for yp being Lipschitz on C. However, the rate in that case will be in the order Ō (x) for larger K, which is still slower than the bound Ö (t) in (Liu & Zhou, 2024b). Therefore, we do not provide it here. See Lemma B.3 for why we can do at most θ n
21

---

Improved Last-Tterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
Theorem A.6. (Fall version of Theorem 4.7) Under Assumptions 2.1 (with p and 2.2, suppose the SS sampling scheme is employed with the stepsize T/- uz Vt [T] where m N, then for any Rd, Allgoritum I guaranttes
j |=|l=- 1=1===011 x1 1
m(1 + logT)
ya T
GraG + 9/ n ))
E. [F F(z)] so
P
VT
Proof. Note that the SS sampling scheme satisfies i(t) 2 Uniform [n]. Vt [T], and the stepsize 1)- m is non-increasing.
jdt
Hence, Conditions and in Lemma B.2 are fulfilled. If Condition 3 also holds, i.e., [E (2,(),)] < hn.. Vi E [7), 8 E (t]
for some & 2 0, we can invoke Lemma B.2 and follow the same steps of proving (12) to obtain for any 2 E R.
m (G9,2 + Φ) (1 + log T)
p= -===- -11- x11
E (1F(01+)--F(e) 5o
(22)
(m
nT
and know
1 1mm + t ) 1I [T].
mm
Tedl
(23)
1 m
Our last task to find constant
2 0 satisfying
[E [fe((r)))] S 41,,, V1 E (T), E [1]
Here claim
(T n
T G12 G,
Φ = 8
(24)
To prove our statement, we invoke Lemma B.6 to have for any t E [T] and 8 [t].
E [2(())))
S4G]
[r())
r(t))
1 (r(j) + (r())
r(t))]
n-1
j=1
2
8-1
n C²
+
Gi
G +3
= r(0)
1 [r(i) + r(U)
71
1=1
)=1
5-1
= r(t) + +r(()
S4G²,
(r())==(tt)
n-1
21
n.
f.2 G² (r() # (())
+
Gi
Σ
G22 + G7 (r() = r(()]+
(25)
n
n-1
j=1
where the last step is due to S q()),, therefore have
75% %
< na. Vj E [s 1] because 7el is non-decreasing in & as shown in (23). Note that
1 ([((j) # r())
q())
1 (r(s) + r(t)] 2q(s).
1 110)= r(t)(()
Σ
-(t)
(26)
1
n
j=1
and
nG G
69 + ((1())))()
1 [r(i) # r(t)
n n-
j=1
d(s)n
nG 12
G²
<
G2
+ + G( = r(t)+
[r() + ((0)
n
(27)
22

---

Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
Combine (25), (26) and (27) to obtain
E (x,)]l (q(s) + 27, Σ
Giy 2mq(s) (8q()) 2/ (21(5)
i=1
$ <(s +1 f322 + 2(T +nG n1 (24) DT
7 +
where the second inequality holds by q(s) S q(T) +1 By (22) and (24), we finally have
m G + 11 (1) + (1+ log
11 // 2 æill
E [F((TT+1)) - F(=)) 0
(m+?)
nT
m
m (772 + VTG + VTG TG222 (1 + log 7)
14 z x1 ?
(m+T)
μ
|| 21
m(1 + log
VTGG, T
G3IG22 VT
G2
0
(m+1)
m
where the last step is by 2322- < fnG To recover the rate stated in Theorem 4.7, we only need to take m = 2 and
observe that LP VT
when T n.
B. Theoretical Analysis
This section includes our theoretical analysis in detail.
B.1. General Lemmas
As mentioned in 5, the high-level idea is inspired by (Liu & Zhou, 2024a). However, several important modifications are required to circumvent the potential issue caused by the general i(t) considered our setting. To begin with, we first characterize the progress made every single step, provided the following Lemma B.I. Note this result holds for any i(t) even if it does not equal Uniform [n]] in distribution.
Lemma B.1. Under Assumptions 2.1 and 2.2, for any E (T] and y TRdd Algorithm I guarantees
F(x -F)) S 11y 2..1?
11 -1411l
(1 umi)
+ me (Che) + +r,) + 22(x1))
2n
2n,
where (4) A Jicy(y) - f(y), Vy ERd.
Proof. Let L E [T] be fixed. If g domm,, then the inequality holds automatically since F(y) = to and F( < + almost surely. Thus, we only need to consider the case domp.. By the convexity of fi(e). we have
(x)( - fin (v) < <VV (2x). x, y) = (V fi(e) (2:))
x.+1 n) + (V (xto)) x(+1).
(28)
According to the update rule of x++1, there exists V E (v such that
0 V4(4441) Vi(e)(zs)
Et+1 Tt
3. -1+1 vD(14+1), V Vitej
17
m
23

---

Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
which gives us
(Et 1 0++1
y)
(z)) 2)
(Veh( xt+1)
y
3t
11-11 1y xe+1l1² 1|2
0141 - xzl1
+ (7b((1+1)) 21+1)
2tyt
y xell
1/ a++1 11
|
xz 1
(1 + poTTe)
+ +b(()) - (0(++1)),
(29)
21
21)
21/1
where the last step holds by the u-strong convexity of eb. addition, there is
(vi))) 24 x(+1) = (ax) - ([( - R(+1) + (V - x(+1)
- (V (xx)) - V (3+++), - xe+11 + f(xx) - f((tt+))
(30)
where the last inequality is due to the convexity of f.
Plug (29) and (30) back into (28) and rearrange terms to get (recall 22(-)) = fi(e) (.) f())
F(a:41) - F(y) 1
æel.
3 x
11
(1+ + pmm))
+ 22(y)) - Qe((x))
27)t
a1t11) || |2++1 2tel
(V (at)) vf(x(+1))
217
11 x2l1
11
21+1112 + 11e (Chi: + +G71) +t( - (x(x)))
(1+ + pm:)
201t
21
where the last line follows by
V Fice) (2x)) V ()( x
(b)
V (xx) v
||0011 - =zell S (Gi()) Gy,1) | xz
t/ (Gitn) Gr,1)² 2
||++11 - 12
| - m. |]
I m (Chi, + G77a) +
2
2T7
2m7
where (a) due Sauchy-Schwart inequality, (b) because fico and f are respectively Lipschitz on domp with the parameter Gitt) and GI,1, and (c) is by AM-GM inequality.
Next, we are ready to prove our core last-iterate result, Lemma B.2. which provides new sufficient conditions for the last-iterate convergence rate. We remind the reader again that Condition 2 is actually not necessary since we can simply stop the proof at the equation (46) and change vi to (T( V Tb+1) in the final bound.
Lemma B.2. (Full version of Lemma 5.1) Under Assumptions 2.1 and 2.2, suppose the following three conditions hold:
1. The index satisfies i(t) 2 Uniform [n] Vt [T].
2. The stepsize Tt, Vt E [T' is non-increasing.
3. [x+()))) < 4n. Vt [T] 8 E where O a constant probably depending T, n, μs and G G.
Then for any z E Rd. Algorithum guarantees
2z x111 + (G²,2 + +T)
T'
[[ -F())
Σ
Σ Te7
[m]
7/s
where (.(()) is defined in Lemma B.l and 7t 4 [ (1 + pmm), Vt E [T +1.
24

---

Improved Last-Tterate Convergence of Shuflling Gradient Methods for Nonsmooth Convex Optimization
Proof. It is enough to only consider the z E domp,, In the following proof, fix point domb. By Lemma B.1, the following inequality holds for any E [T] and RRd
ly x.11
y x4t1l
F(w(41) - Flv)= S
(1 um))
+ (Cin) + 0711) + +1((v)) Px(x))).
21/
Multiplying both sides by Yol yields (note that (1 + pm) nr 70+1, vt (T])
(F((F(()+1)) F(y))= y 1| M41 y x++1ll vone ( G72)) + ven((l(()) (2((x))).
(31)
Next, inspired by (Liu & Zhou, 2024a), we first define the following non-decreasing sequence
yT
Ut
Vt E [T' + []],
(32)
25=t11 7s7
PTTT
01
U2
(33)
E5 Yolls
and then introduce
21
Uo41
Vt E T 1].
(34)
Ut
Vt
Note that z, also falls in domb as it is convex combination of points in domb and admits
Z++1
Ut
+
(1-
0t Ut+1
xt. vt E [T).
(35)
Ut+1
For any t (T), we invoke (31) with y 1 to obtain
(Mn(F(((41)) - F(z(+1))
Yt || |1 z2l1 M+11 || 21+111
( u (Ches + G7a1) + (0((((()))))
"1 Mt 01+1
|| 2el1² - 7 ||
x1+11
+ nmm (Git)) + G7,1) + m - (c((x)))
(36)
2
where the second inequality is by || xt
21
1| - æe1 + (1 (I- - ||+, - xt11²
vr1i || x
due to
the convexity of I1-112 and (35). Multiply both sides of (36) by 1 and sum up from = 1 to T to obtain
T 701h - F(2(41)
1=1
11 |2] - <
x1 2
|| uT+
LT+Il
Σ
T
non u+t1 (Chy, + G7,2) + (0((=)))) (2x
2
11
11
2111?
Wolk 01+1
2
G + G7,))
71000 - (xx))
||
æ1 1|
Σ
2 ut+1
( G7.1) + +0m00++100(2z4))) P((xx)).
(37)
2
25

---

Improved Last-Tterate Convergence of Shuflling Gradient Methods for Nonsmooth Convex Optimization
Now focus the term E ((00442(((244)) and observe that
T
70
7 (fice ((((+1)
7:
[1)(())z) +
(Us+1 (x)s(c)((aa) -4:1) -00
==1
11 (f+(z) + f()))
Σ
(Us+1- 1 (o)((((s))) + f(x))) vet vet (((1(())
7:7
a=1
(1))(2) Σ (1s1 - -2)(S((zxx)
76T
+
1/ (z) Σ
(Va-1 vx)s(()e) - (4Ll((
(38)
8=1
where (a) is due to (it))(=++1) 0r+1 (z) in (34) and (b) holds by recalling that (2x()) = (.( -(().
+ + ===1
Es
fi(e) (2,) by the convexity of fi(e) and the definition of z++1
2141
Combine (37) and (38) to have
2v ||
x 11
Σ
mm F(21+1)) <
Σ
Yo 1 (ohts + G7a)) +0+
ut+1
(39)
2
t=1
t=1
where
7t
Ui (1()(()) +
Σ
(Us+1 vo)s2(((.)) - 0(410l(
(40)
t=1
a=1
A
7h
v1 fzf(z) +
(Us+1 - vz)f(xx) (+11f(24411
(41)
We bound term
as follows
(F(2)- + Σ (1041- -t)(())))) v(x+)) ve- e (F(zz+1) - (Zc+1))
Wh
01 (() + Σ (12-1-0,)))
- V241F v
+ ve+1 (z(+1) Σ
(Vo+1 - vo)((xx)) v1v(2))
s=1
11 F(z) + Σ - (() - w
F(Z4t1)
Wel
#=1
(Uo+1 - (vot1- v.)(((xss) F(z)) (F((t)) -(())
[-ml
Σ Wel
(vs41 - vs)(F(xs)) - F(z)) - Σ (F(22)))))))))
(d)
Yo- 1o-177-100 - F())) Σ (F(0)))))( F())),
(42)
where (c) holds by ((=++1) < - (z)) + Et_ (34) and (d) is by noticing that
" due to the convexity of &o and the definition of 214 in
Ue+1
26

---

Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
i =1
(33)
O;
(43)
if E [1},
(32)
TTT
YTIT
YT'T Yo- --1 177-1
(32) 7e-1 18/
1
Us
Dim mm
T6ll
(E 7
7ol (2 12 700)
2i 7h
which implies
Σ
7e
(Us+1
U.)) = 13-17/6-155
(44)
We then plug (42) back into (39) and rearrange terms to get
207 (F(#r-1) -(=))) v v1
||
==112
Σ
wil
w u+11 G + Gr,)
+0.
2
t=1
(32)
Take expectations and divide by "r on both sides and then use ur
and ?1 = 1 to obtain
(1F((T+))-FP3 S
U1 2 - x
E
G2 ((t))
+
G7,,)
E TT/
2TT/T
TT/
1=1
x x111
U1+1
E
+ +20
+
(45)
2YTUTT
T/T
1=1
where the last line holds due to i(t) 2 Uniform [n] [n), E [
E
1/2 -
G. G7 and GG. S G
i(t)
Lastly, we note that
E
E [[((2)] + Σ (Net1 -. v, [S4(((]) 1 (2:))
T
Σ Uo-1 - U. (2x - 2 I [2
7/07l
T
Σ
(Us+1 - -.))))00 -477 + u++1 2T7
-=1
T
T (1++1 - -
+
Wel
nem ust1
1=8
(43),(44)
Ye- 1 17- 1o +
Σ
moneee uet1
(46)
2=
1=1
(g)
2Φ
YeT 0t+1.
(47)
where (e) is due to [2)] = E (z) -()])) v, E [T] since i(t) 2 Uniform [n], Vt E [T], (f) holds by the
= condition of E (x,)) < lr E [ s [4], and (g) is by the condition of the non-increasing Ti Vi [T]. We thereby finish the proof by plugging (47) back into (45) and applying the definition of vs in (32) and (33).
Though Lemma B.2 is enough for the RR case, as the reader already has seen, it is inadequate for the SS case. So what do we miss? The problem that we never use the fact (i((k: 1)n + 1): ... i(km)] [m]. vk E [K] if Kn for E N.
27

---

Improved Last-Tterate Convergence of Shuftling Gradient Methods for Nonsmooth Convex Optimization
which is the major factor employed in the analysis of (Liu & Zhou, 2024b). So similar (Liu & Zhou, 2024b), we may also hope for a last-iterate convergence bound that holds almost surely. However, due to a different structure in our Algorithm 1, i.e. the place for the proximal update, the existing analysis and rates in (Liu & Zhou, 2024b) are immediately invalid. Hence, is unknown whether Algorithm 1 still guarantees last- rate in the same order as (Liu & Zhou, 2024b) (or equivalently, Proximal GD).
Fortunately, we can still prove a similar almost surely convergence bound with two extra requirements Conditions 2 and 3. Condition 2 here is standard if we consider the whole epoch as a single update like (Liu & Zhou, 2024b). contrast, Condition 3 more artificial and makes the rate depend on a new parameter Gg. We currently do not know whether can be removed not.
Lastly, we point out that, if ignoring G. (or one can think it is smaller than GJ,1), the rate in Lemma B.3 for the general convex case is in the same order as (Liu & Zhou, 2024b). This is why we can obtain the improved result in Theorem A.5, However, for the strongly convex case, Lemma B.3 is worse than (Liu & Zhou, 2024b) because the parameter μi in our Ykk is worse than a factor of n compared to (Liu Zhou, 2024b) (in other words, they have nj)). This crucial point leads us to a (e.g., setting îiK- μul Ak E [K]) than Proximal GD. We currently do not know whether it fixable. If is, one can improve Theorem A.6 to show SS also beats Proximal GD for any K E N (again, ignoring G
worse rate Ô ( (
Lemma B.3, Under Assumptions 2.1 and 2.2, suppose T Kn where K E N and the following three conditions hold:
1. The index satisfies {i((k- - 1)m + 1),- .. .i(kn)) = [n], Ak E [K].
2. The stepsize satisfies тJt = ni(t), Vt E [T'] where Tik Ak E [K] is another pasitive sequence.
3. 5b = @ + Ic where & Rd + R. is convex and G Gip-Lipschitz on domy = C.
Then for any Rd, Algorithm guarantees almost surely
|| - x11" n
K
(( - 50
(G),1
+ G
> k- 7k
tink 7001l
where 7h A T (1 (me), Ak E [K + 1].
Proof. Given y E dome' = C, for any E [T'] we have by (29)
(i)) 4) s |y - 2 (1 + pm7)) y - x++1/l
| xx 1
+ +1) - (b(x++1).
27
27
217
Combine the above inequality with (28) to obtain
(are) + (b(++))) - (10) - (1)))
(iiio) (axe;, xi ((41) + |18 - x:11? - (1 + +m))
11y Fe+1
11
[1,-1 1 - xe. 1
217²
2n
217e
y ærl1?
1 xE+11l
(1 pmme)
(48)
21).
21/z
2
where the second step is by applying Cauchy-Sehward inequality, Assumption 2.2 and AM-GM inequality to have
Gr. ((0)
|
xx
(Via o m.+1) < Vio ||ا, ..+1ll S Gia ||=, #1+1ll S
2
27p
We sum up (48) from L = (k- 1)n + 1 to kn for a fixed & E [K] and notice 7/. = Ti by Condition 2 to obtain
(xx) + (1(+++1)) Sice(()) (1))
t= (kc 1)++1
Ti 1) 1)n+1 11 (1 + pm7z)) 11 Iko+1ll 11?
kn
y
+
7k
Σ
Gioy
27/²
2
(k-x1))++1
28

---

Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
One more step, by Condition I, rewrite the above inequality into
y ((k-1))+11 (1 + pitk) lyy Ikn+1ll 1| Ti
1( F(y)= -
210TI
1
Ficey (2)k+1) (2xe) + (((knt1)) -
(2/ (2(41)))
(49)
n
1)++1
We now prove bound on [++11 - æzI1. which will used later. Observe that when vb = 1p + Ic, there is
| - x.11
argmin + (ace) x²
Fs+1
21/s
+ || x21
argmin V fi(s) (2,) (x)),)))))))))) x)
24/=-
which implies that, by the optimality condition, there exists V E 0p((x++1) such that for any 2 E C.
Vip(20+1)= + (z.)) Ex41 Is
xs+1 x) S 0.
In particular, set 2, to have
|x 22ll" < 1)s [v(((++)) Vi(cs (..), -xs+1)
[x,11 xx 77s Vg(œ,+1) + Vi(ss) (x:)] S 7h (Gp + Gi(s))
(50)
where in the last step we use 7)s = Tik when 8 E ((k- 1)n + 1, 1, kn) by Condition and yo is GipLiitchitz on C by Condition 3.
Now notice that
kn
Σ
- (xx))
(A Da+1
kn
knn
km
Gi(s) || - xx 5
Gi(s) | - xzll
t= (R 1)a+1
(A
1)a+1 s=8
(50)
km
T Guty (Gos + Gi(s)) S T/
n² n²G
n²Gg, f.1
nG
f.2
(51)
2
1)n+1
where (a) is by Assumption 2.2. Morcover, there
km
Σ
(( - (1(++1))
(m+1
km
kn-1
Σ
p( - (0(2411)= =
Σ
(( - (p((+11))
(=(k- 11
t= 11++1
(6)
An-1
kn
kn
G
Σ
| - Ee+1ll S G
Σ
|[ - xall
(m(k= 1)++1
tm
(k 1un+1 sst-1
(50)
An-1
km
G2
< G
Σ
Σ
Th (G + G(()) S mnn(n -1)
+ GoGG11
(52)
2
t=
#
where (b) is by Condition
29

---

Improved Last-Tterate Convergence of Shuflling Gradient Methods for Nonsmooth Convex Optimization Combine (49), (51) and (52) to have for any y E dome C and [K].
- |/ 2(k- 1) 1|2 + pTjj)) ly - #kn+1ll men (G Gt)
F( Fly)=
2nñj
Note that this inequality also holds for y & C. Hence, the above result is true for any y E Rd. We can then follow similar steps of proving Lemma B.2 to finally obtain for any 2 E R",
2 σ
K
F( - 0
n (G + ++))
11 Eズ= k= 7K
K
t= VeTie
1/ 211?
The
0
(G 1 + G
11 Σ No7
f. 7eME
where Th-
I (1 + (i)e) vk E [K + 1].
B.2. Analysis for the RR Sampling Scheme
Due to Lemma B.2, our task reduces to bound E (9,(), vt E , [t]. In this subsection, we will show how to bound it under the RR sampling scheme. The main idea is inspired by (Bassily et al., 2020; Sherman et al., 2021; Koren et al., 2022), where they only bound E [22 (xx)]] Vt E [T] in a simpler setting, i... e = Ic. G; = G. and constant stepsize. Here, we provide fine-grained analysis for [ [S2, (xx)]] Vt E [T] E [t] working for the broader setting considered in our paper. As mentioned, the finer dependence on Gyn and G is the key to help us obtain improved results over (Liu Zhou, 2024b).
Lemma B.4. Under Assumptions 2.1 and 2.2, suppose the RR sampling scheme is employed, then for any t E [T] and 8 E [t], let q a qt),, Algorithm I guarantees
E (2. = 0 if E [(q- 1)m};
E (x,,)] < 2 Σ j
7et +
2r22,,0r2
1-1 vi Liza- 1m+11 V VEj= 33
if's
[t I(qq 1)n]:
1)m+1
% n
where (2x(-) and "V are defined in Lemmas B.1 and B.2, respectively.
Proof. Let F. A aii(1), i(!),, VI [T] denote the natural filtration and Fo be the trivial o-algebra. Note that Dt Fi-1, Vt [T]. Additionally, use e r(s) in the following.
Given s E ((q 1)n),, know x. Fig-1) and i(t) 2 Uniform [ni] conditioned Fiq- under the RR sampling scheme. Therefore, E (x.) Fig-t)al E fxx)) = f(x.), which implies
E [[[((x))] = E (x.) - f(xx)] E (x.) F(g-1jm - -((xx) = 0.
Given E [t] ( [[q-[(q)))) 1)]j, we know i(t) and i(s) have the same distribution conditioned on F.-1 under the RR sampling scheme. Hence, there is
E [(o) (æx)) F.-1] = E [f(s(()( Fo-1] + E [ice = =E [x())) [x,() = (x.)))) (53)
Note that q(s) when E [6] [(q 1)m]. Thus, the index i(s) satisfies
ग (s) i(s)
(54)
a(a)
30

---

Improved Last-Iterate Convergence of Shuflling Gradient Methods for Nonsmooth Convex Optimization
Therefore, we know
- f(x,)
1
Σ f(())) = - 5 + 1 > En((o))
Saj (xx)
1=1
1
1
Sap (1x) + n
E (2x) Fo-1
(54)
FZz (3x)) + n --
E (x,)) | [Fa-1]
n
1
Σ
TP: [nn (a:s) + n-r+1
= [(x))
[iie)
72
n
[(,,(x))1 = 1 Σ
E (xo)) - fmz (xx.)
(44)
(n - fmg (2(())))
(55)
Now for any fixed i E [r - 1). we introduce Ta (r, i), which is generated by exchanging oig and ma in Tq. i.e.
(r, i) _ (ma ma " mā 1 aq
a
; m²)
(56)
We then define the following sequence of points, ن (),1tr)) e #(q-1)n+11
(57)
1ag e ax + (Vrt (a (0 (nt)(t)))))) x)) + [ :(q 1)m (mmmm((-)))) (1)))
Vj [r 1].
217 1)+
(58)
D By Lemma C.3, rq (r, i). which implies (T.. x.) 2 (fa (r, Hence,
E (xx)) = E ( (ā. i))] = E fng (e. (r.)))
which gives
E (x,))
(53)
E (x,)
(55)
E
fny (2x)) - Sag (ox)
= Σ E Fny (xx)) - fry (o.(
1=1
1=1
[E (xx))] 5
E
fag (xx) - fag (8.(
IE
Gig || tt (r,
E G E [||z (r.i)l
Gug V E |le, T. (r. i) mt
n
n
where (a) is because SNH is G. -ipsccith and (b) is due Hölder's inequality. Finally, we invoke Lemma B.5 to have
2 1/ 1)
E (2x()) -
Σ
E
2202 7i Mg 1)+ts
+ 2v2G,,G11. G122
Σ
7
23
1=1
V2G² 1.2
Vi- 110-1)++lll----- 1mm+
2/2G,,1
2
1)n
و Ma 1m+
N
7
1=1
V2G² 1.2
779li
BV2G,IG n
Σ
%
111++
i= Dj++1
SStrictly speaking, this equation requires that for any i E [n] and x Rd ( is deterministically picked from the subgradient set (m)) which possibly contains more than one element. We assume holds since this is realistic.
31

---

Improved Last-Tterate Convergence of Shuflling Gradient Methods for Nonsmooth Convex Optimization where the fact (q 1)n + in the final step.
Lemma B.S. Under the same settings in Lemma B.4, let (r, be the point defined by (57) and (58), then have
E |1,, (r) ma S 262 Mi (t--))as?(a 1)ati + 8G
Σ
[-1
(qa-1)at
7
z=
where is defined in Lemma B.2.
Proof. Note that Td = = i) for all 1i by the definition of (r, i) (see (56)) and 2(q-1)n+41 1(q-1)n+1(1,) by the definition (see (57)). Thus, by the definition of (ggg (1q-1)++++ (see (58)), there is
11g-1)n++J T( 1 i) E [+]
In the following, denote by y & 1)4-t and S/ & (lq Vj {i rr. Note that there is y, D.-
By Lemma C.2,
|1 D++ll y: D. 7iq V(q-1))m 1)a+t) (Vf v (e((),((()))
V f (y,) V (agga
11 19-1)nti
1 + 1177/a-1)000
+ j
(56) 7/q 1ln-t)n+/
V - Vlxg (V+)
Mi Mla-1)n+s(Gzr GGG))
(59)
1 11)
1 1llg--1)at
where the last step is by the Lipschitz property of fr- We invoke Lemma C.2 again obtain for any i i 1 1issjjr--
y 8, 7a + f (y₁) V (r.t)) (0,))
|1 Ts+ill 5
1 (0)((=1)))+
y y 1( 1)x V 5z (3z) V (
(56)
1 + (01(+t)
which implies
|B, U 2 1)tti
Uj 1z. (B)) V (1,)) + nig 1)+ts
Vf (3,)
V (7,)
|1 11
(1 + 1197(1111111 1)++))
||, -,,l" + 41//g 1)m+s G2
(60)
(1 1 )2
where the last line is by
(u, - VS (y,) VSzg (0))
Assumption 2.1 2
Assumption 2.2 I
| (21)
Vf (i,
4G2
32

---

Improved Last-Tterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
Finally, unrolling (60) recursively to obtain
Mit1 Di+1 1|
An (q-11-1 1)n G
10, 3.1l
1=it+ (1 + 1101(1 111((11)110 11)++))
+ 11l19
(59)
Mi 1)m+i (Gag + Grgg) )²
41 1)n++
I (1= + 100(9-1)n+t)
|-= (1 + 11ll 11ll(--1)+tl 1m++))
21 1)m+i (G2 + O3ai)
1 (1 + (1)(+)))+))
[== (1 + pT 1 1)
21((--1)+++* T3
4n 4g 1)n-1)+ G2
IT (1 + 1 (1)+t))
[==
(1 + 477(a-1)n+e) 1)ate)2
Therefore, know
21/9 1)u+r G
4n 1jnty
G2
E 11,, 8.112 1 má] <
mq
/ (1 + L071(1 1
pmm (1 + pm7/(9 1)n+e)²
20 11)+t
8nqq 1)+ 1.2
(0)
|= (1 W1la-1)ndd
(1 + pml 1 1)m+t) )
( 27 1)ati Miq 1)+t1 G2
87 1)m+ 1g p 1)++) 0722
where (a) is by (w.loogg. we assume n 2 2 now, otherwise, our final bound holds automatically when n = 1 since F, = (r, i) in that case)
nG G2 1.2 < vi #r
nG
E
G2 mg
m
Vj
n
and (b) is due to 71- (1 + pma) V E (T+17 1). We hence obtain the desired bound on || .r 1)1 ml as
y, (g 1jn+r v2 and D, ( = (r,
B.3. Analysis for the SS Sampling Scheme
This subsection helps us to bound [I [x,(), VI E [T] E [t] for the SS sampling scheme. The proof is inspired by (Koren al., 2022). Again, our result can be viewed as a finer generalization than theirs and hence requires more careful analysis.
Lemma B.6. Under Assumptions 2.1 and 2.2, suppose the SS sampling scheme is employed, then for any t [T] and E [t), let r A r(f), Algorithm 1 guarantees
E [xx())))] S4G
Yi
[r(()) = r] 100) #1)
f2
7s
n n-
G)++) - r]] nGa G [r(1) # #1)
+
G
?
where 92(+) and "i are defined in Lemmas B.I and B.2, respectively.
Proof. Under the SS sampling scheme, for any t [T]. o, can be recognized as being generated by deterministic map A from the permutation Idd when the initial point 21 and the stepsize 1)t Vt E [T] are fixed. In other words,
"Same as Footnote 5, we also assume V (x)) deterministically picked from (xr( for any i E [n] and x E Rd
33

---

Improved Last-Iterate Convergence of Shuflling Gradient Methods for Nonsmooth Convex Optimization
write
Ct Ar(T), 4 E [7].
We also recall the following fact about the index
i(t) = x1(1) x².
(61)
Hence, there is
E [xs)) = [f
Σ (T) =i].
For any E [n)], let (rr, denote the permutation obtained by exchanging n' and n where *; is the unique index satisfying n-i i. By applying Lemma C.4 with o(-) = f:(As(-), there
E ((( = i]] (F Mie,
which implies
n = R (T)
1 Σ
Σ
E ((((A(((()))))
n
Therefore,
1 n
EE (zx.)]
((AA -A(AA()) S
Σ
((I(((((((())) - -((AA())))
(a)
= Σ G.Bll,, x1) =xllll.
where (a) is because fi is G,-Lipschitz on domb and a, point œ and the stepsize ne Vt [T] under the SS sampling scheme but using the permutation +(r,+;), ie..
(r, *:) is the output of running Algorithm with the same initial
き (r) æ1.
(62)
C (r, xi) - argmin (()))) + (Vsnsnrnn)) (r,(), + x - (1)+
Vj E [s 11.
(63)
2nj
Finally, by Lemma B.7, we have
(1(r0)= = +]+ 1[(()) {1]
G.E (r. =x.ll=
G. 2 (G + +.))
Σ
Y5ml
n n-1
#=1
8-1
Gj + G[ = +]+ nGa f.2 G?
+
G 2,
[r(s] #1)
n
?
n 1
j=l
+-1
(1(r)) = +] 1 1+)))1)
GG + +.,22)
Σ
7illi
%
n n-1
5=1
2
G
G + G G22
(r(] G(O
r]+
nG2 G
1.2
1
[r(]) 4 rl
n 1
i=1
The proof is completed by using the fact GG,1 S 22
34

---

Improved Last-Iterate Convergence of Shuflling Gradient Methods for Nonsmooth Convex Optimization
Lemma B.7. Under the same settings in Lemma B.6, let (t(1, be the point defined by (62) and (63), then we have
1-1
[r()] =1] 1 (r(i) $
E || - (.(rr 5 (G + G.)
7/s
n1 n-
j=1
G + = nG
G. [r(]) + =1)
+ 2
2
n-1
jml
where 7t is defined in Lemma B.2.
Proof. For simplicity, we denote d, a ||,, (r, Vs [t]. Moreover, (e) represent the index trajectory generated T(s) a (+() Vs E
under the permutation a(r, +z). i.e.,
[t- [t-
(64)
By Lemma C.2, we have
8 - - Ix 18- [r,(,, x:), (x)) - Vi(e) (2.(1, + 1 (x()) - Vico (2, (T,(())))))
82
e+1 S
(1 + |m7,)²
(a) 83 + 2m
V (z.)) V fiee (xx)
6, + n
v Vi(o)(
Viico (r,((r,))))
(1 + 1m7,)2
(6)
8% + 27/
((ss)((ss) V Vice (wx))
dg 0,+33 21/²
(hhs) + cioo)
(65)
(1 + 2
where (a) is by
xx a,(r, *),, (z.) V Fia (G.(r,
xx (, +), Vi(ss Vit ( +i))
(z, (x,- (r,+t,,),, ((o))(Es) - VEics(Ea))
Assumption 2.1 Z
xx - a a.(r, *)), (x.) - Viico (caa) 2 ((i))(aa)) - Fico 80:
and (b) holds due to
(xs)) - Vir(ss) (0.
(r)))) +
Assumption 2.2 S
Gi(e) + GRts + Vion(e..) V FiL (G. xi))| S
==))/'=>(())))/ (Chi) + +Ros)
Now recall that = II==1 (1 + pm))) Vt E [T' + 1]. Multiply both sides of (65) by n: to obtain
224 63 S 1 + 2> Vite - V Vio (x. || 75d + +22202 (his) + +GO))
18+1 s+1 S 18/ + Σ 27 [hon) - (z)) N565 + 277713 (cin) + +Z2
82
27
[z,) - Vinn / + +27303 (chn + (
7500
(66)
where the last equation is by 8, = | - @ (t)l (2) o.
Next, we use induction to prove
|||
8-1 +
2202 < 4
Σ 35 [(nn) - Vin (m:))
23 (Ghn) + + vs E [t]
(67)
j=1
For 1, (67) holds as 8, = Suppose (67) is true for all indices in [s) where s E [t- 1]. Then for + 1,
35

---

Improved Last-Iterate Convergence of Shuflling Gradient Methods for Nonsmooth Convex Optimization
if 7/2
7011 0+11 S maxxe]s] 76 we know
1 S max 2 (+(
2
(67) max [x(ss]
E Ti [ig](()))- (ios(
+ >I (Gi, + ( GGn)
S
Σ 1=1
7i (in(( Tiol
+ +Σ 2ng (Gi)) + +Go):
1=1
if 7841 62 > maxke(s] 220 we know
(66)
[z()) - -inn) 250; + 225773 ( (
7x+1
x+1
273
+
j
S 2
Σ 15
((G) - V Vins [+ل) 70410441 + 222rn² (Giu) + (t2))
(6)
2/ 1-10211
Σ 15 [)o)(()))
+ Σ
27 2 (Gi,) + +tt
+2
2
j=1
j=1
2
= 1 S 4
Σ
Ty
V (x)) - Winn
+ 433 (Cib) + 0 k
+
where (c) is due to AM-GM inequality.
Therefore, we always have
2 Σ T [an)(())) - Vion
x
2 8:
S
+ +Σ 13 (Ciu) + +
1=1
By induction, (67) holds for any E [t], which implies
8-1 1
y=5.= < 2
75 [iin)( - Viio (x))
+2 +2
Σ
23 (Cin) + =GO)
1=1
1=1
s-1
+ Y.E < 2E
Σ 75 [in)(2z)) Vioos (23)
+2E
Σ 23 (Gin) + +
(68)
For term C, note that if *; r, then = f xi) + (Ii))(E;) = (z;) Vj E [s 1]. So there is
Vien((;)) - Viiis = [(in)) - Vir
|| [+: +1
Σ
V)nn( - Vion 1 [ = i].
=
36

---

Improved Last-Iterate Convergence of Shufiling Gradient Methods for Nonsmooth Convex Optimization
When x = i for some e [x]] \ {r), we observe that i(j) (44 (r, = = i() if rf(()) * and r(j) + E, which implies
[iig(a))) - v (oy) 1 | =
(( Vin (z,) 1| = 1 i [V Vf((2))] [ [r() - or !
r or !|
S (G + G;) [='= = [r()) =r or E),
where the second to last step is by [10), r(j) or &. Thus, for any [s 1l.
{ क (r, { under the events n' i and
v (z,) V Vins (2)))
5
Σ 1T - or !]
(E(m]i(0)
- - (iin) (x)) E
Σ
B[ GG; (T'= = 1 (r(s) = r or E
zEin|kirt
nG G.
G.
+ n
(r(s) or
n(n- 11
AE(n]Mr
n -=2G:: (11(6) = r]
(r())
(r(i) + r
-Gr +
n
+1) -
$ (G + Gi) (1(r()) -]+ n 1
where (d) is by, for any fixed & E [m]] \ (rr, there are
G₁ nG - G.
E Gr 1=''''= = = Σ
GLP(T = i, = k] n(n - 1) kE[m]((1
n(n 1)
kE
and
G:
E G [Tt =i]]
n
We thereby have
1 (r()) # 11 (11(0)=1+
O S (G G.) Σ Tm (1r() = -i+
(69)
n-1
For term
for any fixed j E [s 1). we claim the following three facts hold
i0) _ Uniform [m], 1() = 1if = i(j) 2 Uniform [M] \ (i) if fr,
in which the first one follows by the definition of the SS sampling scheme, the second one is true by recalling i() (64) (r,+)) i if r(j)) and the third one is by (64) and Lemma C.5. Therefore, by Hölder's inequality
E
G
+ E (
j=1
r|+ nG G? 1 [r(i) + rl
Σ
222+
(70)
n n-1
1=1
Finally, we conclude by plugging (69) and (70) back into (68) and dividing both sides by 7/-
37

---

Improved Last-Tterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
C. Auxiliary Lemmas
This section includes some technical results applied in the analysis presented the previous sections.
We first provide two algebraic inequalities for the stepsize proportional q(T) q(t) + which is used for the RR sampling scheme in Theorem A.I.
Lemma C.1. Suppose Nt 7), (q(T) q(t) 1), Vt [T]
where 1).
is a constant, then there are
Σ n nTq(TTI
T
9n, (q(2) + log n)
and
7
Proof.
Note that for any E (T], there is
T
(q(T)-1) l)
q(t)p
Σ
Th +
ns
+
N
==(aTT)-
1)n+1
(t)n+++
s=1
9(7)
1/1
((T) + n
Σ ((T) - 11+1 + (n ((n) + +mx-(1)) (1)(((7))))))))))))))))))))))))) - -((( +1)
/=q(1)+1
1/+ ((T + n (q(T) q()) - -1)(a(7)
- q(() + + (n r()) + 1)(9(T)- a(l) + +1]
(71)
2
In particular, for t = 1,
T
Σ n = n/ (((T) + n (q(T ()) + 1) + + = n, m ==1
(1)
2
[fq(T)) (i.e., T E [nD), we have
1/ m,r()) = n.9(TT n.((T)T
2
Ifq(T) 2 2 (i.e., T2 n + 1), have
Σ 1) 17.
+1)++((1)) (1) n]
(a)
2 1
n
(
T
n
(T)T
(T))
(b)
(TTTT
+ +((T)
(T(TTT
=1/- 2
+
n + (T)) -
2 7
2
2
2
2
where (a) is by q(7) 2 _ and (b) is due to (T)) > 2 now.
Hence, we always have
(Tq(TTT
7
2
Next, we observe
71
11
(T) r(t)+1 +1
s=t n
t=(q(T) - 1)n-1
q(T)
(q() - k + 1)2
Σ
+ 17+
(72)
+ - k --
- k - 1n-i+1)(q(7) - k 1)"
k=
38

---

Improved Last-Tterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
For the first part in (72), have
(T)
1
S + (T)
((T) - r(t) +1
(a() 1)+11
For the second part in (72), under relabeling the index, we have
(q k: + 1)2
(T) + (q((T) - A (T)) - k + 2) (n -n- 1)(q(T) - ++ 1)
q(7)
2k
Σ
r(T) + 5( - 2) +1) ik
1=1 r(T)
+ 2i
(k 2)( + 1)
2= i=1
k=
2n 1+ r(T))
2n r(T)
2o
2 (9(T) - 2) < 2og
1
+ 2
(9(T)
2
So there is
T
Th
2n r(T))
7 2
< 174
(T) + 2log
1+
+ (2())
s=t
T
fs
2
9
7
S 1/4
2 llg((r(T) + 2n) + ²2(TT)
2
2
2 2 + 9
7
s 7
2 29(T) - 2 log 3
2
9n, (q() + logn)
2
Next, we introduce Lemma C.2, which gives a general upper bound on the distance between two points output by different proximal updates but using the same stepsize and plays a key role in bounding |E [aa(ar))) 14 (T), 8 [t].
Lemma C.2. Under Assumption 1, given ā. D. Ix: 9g E Rd and n > 0, let
i A argmin (()) + (9 x)) + || xr
21
y A argmin ye (gg. y) 11
21
then there is
- 5l < y 1/ a= 94)
+ pm
Proof. By the definition of æ, there exists V (w)) such that 0 V
Im
which implies
"
Vz) + ã. ã ū) (w- 119 v- 5)
Similarly, we have
(V) + Ú. x) 1 19 v 5)
Sum up the above two equations obtain
7 V ( Vib()), ão 5) + ||: 011
[ 7 1/(9
9 5 ÿ)
39

---

Improved Last-Tterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
Note that Assumption 2.1 implies
V (3) Velū), 5) 1a ~1|².
Hence, there is
1 9yy), xt- 8) y
y
79 9yy
1 + pm
pM
Finally, we provide some useful facts related the random permutation inspired by (Sherman al., 2021; Koren et al., 2022). We recall that Sn is the symmetric group of [n]] i.e. the set containing all permutations of [n]. Lemma C.3. Suppose ı = (mr,... ... x²) is uniformly distributed on Su, for any [n] and i [r 1}, we define a(r, i) by exchanging n¹ and x² in n, then there is
D ir,
Proof. is enough prove that, for any fixed o Sn, there is
P π
= ( = o).
which clearly holds as both sides equal 1 W..
Lemma C.4. Suppose = (rt,.... T²) is uniformly distributed on Sn. for any r, E [n], we define Air, ks) by exchanging n' and t in where *; is the unique index satisfying x= = i, then there is
1
E [ i]] B
where o: Sn + R can ba any deterministic map.
Proof. We observe that
n
n =E
n
E (lo(((r, = E
Σ ( (+; 5]
Σ d(f(r)))) [+' - - Σ (o( |~ i]] (73)
For any fixed j [n], let Trass: Sn + S. be the operation of exchanging the value of of and of for Sn. Then we know
E [((((r,))))) [T' =1]
Σ
(Trrss(0)) [o' = = n! Σ (Trrss(0)) [(Tres(o))'= = =]]
n! D
oES
(()) 10" = = ix- = =]],
(74)
n!
DES
where the second to last step is by (o) :0 Sn} = Sn Combine (73) and (74) to finally obtain
[o(A(r)))) [ = =]] _ n
E B(O(T) |T' = =]]
[o(((r,+))))
Lemma C.5. Suppose π = (=',.... ,-") is uniformly distributed on Sn, for any r, E [n], we define (r, by exchanging n' and Thh in where *; is the unique index satisfying t* i, then there
(r, 2 Uniform [n) \ (1) Vk E [n] xr.
Proof. Given ls E [n] and & # let j E [n] be fixed. We define the function x(x)) 1 1T ]] and notice that
P ((* = = -B((((( Lemma C.4
nE (p(T) [Tt" = i]] = nP [T" i, n² 5]
0
j =
j j
n-1
which concludes the result.
40

---

Improved Last-Tterate Convergence of Shuflling Gradient Methods for Nonsmooth Convex Optimization
D. Lower Bound for Strongly Convex 1b
We present a lower bound that can be applied to the first-order algorithm containing a proximal update.
Given f + _ + R satisfying Assumptions 2.1 and 2.2 and an initial point æ1 R we consider family of algorithms obeying the following update rules in total of T iterations,
M++1 æ1 + Span Useld] fæ: - 31. U. 21, Vf(a)).
(75)
1141 = argmin * (2) + ||a: y1+1
(76)
27c
where yı = 21, Vf(z)) E (z (t) Vt E [T] for # E y), and n Vt E [T] is a positive sequence. Note that (75) can be viewed as a generalization of the existing span assumption (Nesterov al., 2018), as it contains more information based on the output of the proximal update in (76). In particular, (75) and (76) recover Proximal GD with the stepsize sequence Ne, Vt [T] by setting Vt+1 21 + z₁ æ1 7) Vxxz) Z; m V fxx) and "/ n)-
Now we are ready to prove the lower bound. As mentioned in Footnote 1, the proof is only simple variation of the existing analysis in (Bubeck et al., 2015).
Theorem D.I. For any given D. > G > 0, pz > 0, T N satisfying T G² D. DD:: - 1, d N satisfying d 2 T and
2c1 E R2, there exist a function F f tb: Rd IR where is convex and G-Lipschitz I&d and tb is p-strongly convex on R& and subgradient oracle V f such that any algorithm in the form of (75) and (76) starting with æ has
G
min F( F(x.) :E[T]
2 + +1)
where x, = argmin F(x) satisfying I|=-- - æill S D..
Proof. W.L.gg,, we assume 2 = 0. For general point æ1 E Rd, one can change every x to I1 in the following definition of f and sb and then conclude by similar steps.
The construction of the hard instance is essentially the same as (Bubeck et al., 2015). Let ((x) - G max æ [j] and (xx) / ||=|| where æ [j] is the j-th coordinate of æ. Note that
0f(x) = G CCnvv {e;: j argmax
where ej E &d denotes the vector that takes 1 in the j-th coordinate and 0 in any other place. So f is G-Lipschitz on Rd, + is j-strongly convex on Rd from its definition.
Next, we claim the minimum value F(x.))
G² 2p(7+1) where x, satisfies
G #(T+I)
jE [T + 1],
j je [d M [T [1
We consider two cases:
max x [/] 2 We observe falls into this case and note that F(x) 2 (xx)) 2 0 F(0).
max [i] < 0. We observe falls into this case. Now suppose maxje
[i]
for some > 0, we
have |e [i] a. Vjj E (T' 1]. Thus, there is
d
T+1
F(z) Ga +
x [i]
-Ga +
x
2
# 2
Σ
x 1il 2
2
1=1
1=1
J=
u(T + 1)a²
G²
Ga +
F(x.).
24TT + 1)

---

Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
We thereby have
G
min F(x) min ((, F(x+) 2u(T+ +1) EERd
(77)
Moreover, ||=;-||
#vT+I S D. once 2 D 1.
Because 21 0 now, have Ve+1 E Span UsE(t] {0 Ys (xx.). Vf(y))) Moreover, explicitly write
1++1 = gE + | Y=+1 2
|| 2
| ye+1
argmin
2 +
27
27
Ye+1 E Span Uselt] (æs: Us. Vf(.)))
1+ pm
Now we define the subgradient oracle
fx(z) - Csn, where ja - min a/ [t]
By induction, show Span Uselq (æc,, Vs. V/(x.,, v((y))) Span fer. ex), 74 [7]. As such, #
Span (ei,"",ed Vt E [T], which implies F(x(+1) f G + 11 0, vt E [T]. We hence conclude
(77)
G
min F(x - F(x.) EE(T]
2μ(TT + 1)
42


Reviews:
[{"review_id": "9UtKGtNWLs", "reviewer": "Reviewer_wDyR", "summary": "This paper studies shuffling-based variants of proximal SGD on nonsmooth convex optimization, where proximal SGD steps are taken using indices following randomly sampled or arbitrary permutations. Prior works on shuffling-based SGD mostly focus on smooth cases, and this paper tackles the more difficult nonsmooth case where Lipschitz gradients assumption is not available. The paper shows random reshuffling (RR) enjoys convergence faster than proximal GD for the first time in the literature, and proves that single shuffling (SS) converges faster than proximal GD at least in the \"low epoch\" regime, in both convex and strongly convex cases. \n\nUnfortunately, even with the improvements, the rates are slower than proximal SGD (where samples are chosen with replacement); the presence of a lower bound on RR/SS (due to Koren et al 2022) suggests that it may be the case that proximal RR/SS is fundamentally slower than proximal SGD (with-replacement).\n\n## Update after rebuttal\nReviewers were asked to update the reviews, but for this paper I have not much to add. I keep my positive evaluation.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the endorsement of our work. We would like to address the reviewer's concerns below.\n\n**W1&Q2.** To make the bounds for SS decrease to $0$, it indeed needs some other technique in addition to the analysis sketched in Section 5 (as mentioned at the end of the same section). In a high-level way, we need to utilize both the randomness and the deterministic property of SS, in which the former is described in Section 5 and the latter refers to that the index goes over the whole set $[n]$ in every epoch. These two key points are formalized in Lemmas B.2 and B.3, respectively. As such, proving SS converging to $0$ when $K\\to \\infty$ is possible once the conditions in Lemmas B.2 and B.3 are fulfilled. A special case is $\\psi=I_\\mathcal{C}$ used in Theorem 4.6, which further includes the situation $\\psi\\equiv 0$ (i.e., take $\\mathcal{C}=\\mathbb{R}^d$). For a more detailed discussion and some inadequate points of Lemma B.3, we kindly refer the reviewer to Lines 1427-1445.\n\n**W2&W3.** Thanks for the suggestion. We will try to incorporate your comments in the revision when more space is available.\n\n**Q1.** On Page 39 of the arXiv version of [1] (or Page 20 of the supplementary of the NeurIPS version), they obtained the rate in the order of $O\\left(\\eta G^2 (\\sqrt{nK}+K)+\\frac{D^2}{\\eta nK}\\right)$ where $\\eta$ is the stepsize. Thus, the best $\\eta =\\Theta\\left(\\frac{D}{G\\sqrt{(\\sqrt{nK}+ K)nK}}\\right)$ gives us the rate $O\\left(GD\\sqrt{\\frac{\\sqrt{nK}+K}{nK}}\\right)=O\\left(\\frac{GD}{n^{1/4}K^{1/4}} \\lor \\frac{GD}{\\sqrt{n}}\\right)$, where we use $O(a+b)=O(a \\lor b)$ for $a,b\\geq 0$. Moreover, we believe the statement $K\\geq n$ in their Theorem 6 in the main text is a typo and should be corrected to $K\\leq n$ as used in their supplementary (see the page we mentioned at the beginning).\n\n**References**\n\n[1] Koren, Tomer, et al. \"Benign underfitting of stochastic gradient descent.\" Advances in Neural Information Processing Systems 35 (2022): 19605-19617.", "claims_and_evidence": "I defer the discussion on the strengths and weaknesses of the developed theory to the \"Strengths and Weaknesses\" section. The paper does not contain any claims based on experimental results.", "methods_and_evaluation_criteria": "This paper does not propose a new method, and it analyzes existing methods theoretically. No empirical evaluation is considered necessary.", "theoretical_claims": "I unfortunately did not have the time to check the details of the proofs in the supplementary material. I find the proof sketch convincing, but I am not entirely sure if the new technique developed by the authors is technically sound.", "experimental_designs_or_analyses": "N/A. No experiments included, which I think is not a shortcoming given that it's a theory paper.", "relation_to_broader_scientific_literature": "This paper studies popular variants of proximal SGD, so it may have some broader impact on other scientific areas that involve nonsmooth optimization.", "essential_references_not_discussed": "I don't know of other essential references that were not cited in the paper.", "other_strengths_and_weaknesses": "Strengths\n1. The paper is well-written and reads well.\n2. The paper analyzes the shuffling-based proximal gradient method while taking the proximal operator at every iteration, not every epoch (which is the version analyzed in most existing results). I like it because it is closer to (with-replacement) Proximal SGD.\n3. The new technique (Lemma 5.1 and the analysis on $\\Phi$) sounds intriguing, because handling the index dependency within epochs has always been a huge bottleneck in the analysis of shuffling based algorithms, especially in the \"low epoch\" regime. I think the technique developed in the paper can have a broader impact beyond proximal SGD.\n4. The paper discusses several interesting future research directions.\n\nWeaknesses\n1. The biggest shortcoming I can point out is that the SS convergence results (except for Theorem 4.6) are slightly disappointing in the sense that the rates do not converge all the way to zero as the number of epochs grows to infinity.\n2. Minor clarity issue 1: upon looking at Table 1, I was confused for a long time why one cannot combine the \"ANY\" shuffling results by Liu & Zhou 2024b and the SS bounds shown in the paper to get the best of both worlds. I did not realize that the papers consider *different* algorithms until Section 4.2. Indeed, Section 3 points out the difference, but I failed to make the connection to the rates in Table 1. It would be helpful if the authors more explicitly emphasize the differences of the considered algorithms in different rows of Table 1.\n3. Minor clarity issue 2: The fact that RR rates are slower (and perhaps fundamentally so) than proximal (with-replacement) SGD is not revealed to the readers until the end of Section 4.1. Although I appreciate the authors' honesty, I believe this should be highlighted earlier, because it is easy for readers to \"extrapolate\" their prior knowledge from the smooth case to the nonsmooth case and falsely assume that the \"slower baseline\" that the paper is talking about is SGD, not GD.", "other_comments_or_suggestions": "Some suggestions are made in the Weaknesses part above.", "questions_for_authors": "Some minor questions:\n\n1. One question about Koren et al (2022): In their Theorem 6(ii) on SS, the rate $O (\\frac{GD}{ n^{1/4} K^{1/4}})$ is shown only for $K \\geq n$. Can you elaborate on how you can derive the other term $\\frac{GD}{\\sqrt{n}}$ in Table 1?\n\n2. The fact that SS bounds decrease all the way to zero as $K \\to \\infty$ (except for Theorem 4.6) is slightly disappointing. Is there any hope for improvements, or some other techniques that allow the bounds to converge to zero at least in the special case of $\\psi \\equiv 0$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Dvjo1OSGir", "reviewer": "Reviewer_JJsr", "summary": "- The paper investigates the convergence rates of shuffling SGD for nonsmooth (strongly) convex function. While the convergence behavior of shuffling SGD under smoothness assumption has been widely studied in recent literature, its investigation under Lipschitz continuity remains relatively less explored. The paper focuses on two shuffling strategies (RR and SS) in the context of the subgradient-proximal method.\n- The paper makes a fine-grained analysis on $G_{f,1}$ and $G_{f.2}$ to establish better convergence rates compared to prior works. For RR, when the objective is convex, Theorem 4.2 achieves $O(\\frac{\\sqrt{G_{f,1}G_{f,2}}}{n^{1/4}K^{1/2}})$, and when the objective is strongly convex, Theorem 4.4 achieves $O(\\frac{G_{f,1}G_{f,2}}{n^{1/2}K})$. Both rates improve upon previously known results, particularly when the Lipschitz cnostants of individual components are similar. Similarly, for SS, Theorem 4.5 and Theorem 4.7 demonstrates improved convergence rates over prior studies in both the convex and strongly convex setting, provided that the number of total epoch is small.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. We would like to answer the reviewer's questions below.\n\n**Typos&Suggestions.** Thanks for carefully reading and the helpful comments. We have corrected/modified them accordingly.\n\n**Q1.** Thanks for the interesting question. Honestly, we do not have too many insights on this phenomenon and don't want to provide a misleading explanation. We hope it can be fully understood in future research.\n\n**Q2.** Yes, as stated in Theorem 5 of [1], the lower bound construction is for $G_i\\equiv 4$. We also mentioned this point in Remark d under Table 1.\n\n**Q3.** We note that $G_{f,2}\\approx \\sqrt{n}G_{f,1}$ is a very special case, but doesn't need to be worried about. Suppose we have $B$ gradient evaluation budgets, then the rate of every related algorithm is as follows (for simplicity, we consider the non-strongly convex case):\n\n   - GD: $O(\\frac{G_{f,1}D}{\\sqrt{T}})=O(\\frac{\\sqrt{n}G_{f,1}D}{\\sqrt{nT}})=O(\\frac{\\sqrt{n}G_{f,1}D}{\\sqrt{B}})$.\n   - SGD: $O(\\frac{G_{f,2}D}{\\sqrt{T}})=O(\\frac{G_{f,2}D}{\\sqrt{B}})\\approx O(\\frac{\\sqrt{n}G_{f,1}D}{\\sqrt{B}})$.\n   - Theorem 4.7 in [2]: $O(\\frac{G_{f,1}D}{\\sqrt{K}})=O(\\frac{\\sqrt{n}G_{f,1}D}{\\sqrt{nK}})=O(\\frac{\\sqrt{n}G_{f,1}D}{\\sqrt{B}})$.\n   - Our Theorem 4.2 for RR: $O(\\frac{n^{1/4}\\sqrt{G_{f,1}G_{f,2}D}}{\\sqrt{T}})=O(\\frac{n^{1/4}\\sqrt{G_{f,1}G_{f,2}D}}{\\sqrt{B}})\\approx O(\\frac{\\sqrt{n}G_{f,1}D}{\\sqrt{B}})$.\n\nAs such, all algorithms have the same rate. Therefore, we believe our analysis for RR is optimal in this case.\n\nLastly, for SS, our Theorems 4.5 and 4.7 are never optimal for whatever case. Hence, we only need to discuss Theorem 4.6. In this special case, as one can check, it degenerates to the same rate $O(\\frac{\\sqrt{n}G_{f,1}D}{\\sqrt{B}})$ given above. Thus, we believe Theorem 4.6 in this special case is also unimprovable.\n\n**References**\n\n[1] Koren, Tomer, et al. \"Benign underfitting of stochastic gradient descent.\" Advances in Neural Information Processing Systems 35 (2022): 19605-19617.\n\n[2] Liu, Zijian, and Zhengyuan Zhou. \"On the Last-Iterate Convergence of Shuffling Gradient Methods.\" International Conference on Machine Learning. PMLR, 2024.", "claims_and_evidence": "Most claims are supported by theorems and propositions.", "methods_and_evaluation_criteria": "This paper is purely theoretical and does not involve empirical evaluation or benchmark datasets.", "theoretical_claims": "I briefly checked the proofs of Lemma B.1, B.2, B.3, B.4, and B.6 (which I think serve as the backbone for proving the main theorems), and did not identify any critical issues. However, since the proof is highly technical, I was not able to fully verify the entire proof framework in detail.", "experimental_designs_or_analyses": "The paper does not include any experiments.", "relation_to_broader_scientific_literature": "The paper improves the convergence rate of RR and SS compared to previously known rates under the Lipschitz continuity assumption. This assumption is more realistic in modern machine learning frameworks than traditional smoothness assumption.", "essential_references_not_discussed": "Essential references are appropriately cited and discussed in the paper.", "other_strengths_and_weaknesses": "Strengths\n\n- The paper is well-written with clear and detailed explanations.\n- The derived convergence rates for RR are strong. The results hold for the last iterate and general (strongly) convex $\\psi$. Also, this paper is the first to prove that RR converges faster than Proximal GD in this setting.\n\nWeaknesses\n\n- The convergence rates for SS  seem weak, compared to those for RR. As the authors pointed out, both Theorem 4.5 and Theorem 4.7 do not guarantee convergence to $0$ as $T \\rightarrow \\infty$. While Theorem 4.6 provides a vanishing bound, it requires an additional condition on $\\psi$. In particular, it is somewhat unusual that the convergence rate does not go to $0$ even in the strongly convex setting.", "other_comments_or_suggestions": "Minor typos:\n\n- Line 1299, 1301: $y\\rightarrow z_{t+1}$\n- Line 1311: $T+2 \\rightarrow T+1$\n\nMinor Suggestion:\n\n- In line 99L, the paper states that “For RR, our new rates are always better than the best-known bounds in (Liu & Zhou, 2024b) by up to a factor of $\\Theta(n^{-1/4})$ in the general convex case.” I believe this sentence slightly overclaims the contribution, as there may be no gain when $G_{f,2}\\approx \\sqrt{n}G_{f,1}$. Thus, I suggest removing the term “always” from the sentence.", "questions_for_authors": "Q1. In lines 831–849, the authors state that RR is slower than proximal SGD, at least in the convex setting. In contrast, under the smoothness assumption, RR has been extensively studied and shown to converge faster than SGD. Do the authors have any insights or intuition on why RR exhibits slower convergence under the Lipschitz continuity assumption?\n\nQ2. Below Corollary 4.3, the paper claims that when $G_i \\equiv G$, the result matches the lower bound $\\Omega(\\frac{1}{n^{1/4}K^{1/2}})$ shown by [Koren et al., 2022] proved for $\\psi=I_C$. Does the lower bound construction in [Koren et al., 2022] also satisfy $G_i \\equiv G$?\n\nQ3. The authors clearly state the significance of their work when $G_{f,2} \\approx G_{f,1}$. However, when $G_{f,2}\\approx \\sqrt{n}G_{f,1}$ (which is not well discussed in the paper), the results in the paper do not offer any improvement over prior works; for RR, both the rates in Theorem 4.2 and 4.5 match those in (Liu & Zhou, 2024b), and for SS, the critical epoch $K_*$ becomes 1. Do the authors believe that the current rate for this case is already optimal, or is there potential for achieving a better rate?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qXV79XJSJy", "reviewer": "Reviewer_4WZ4", "summary": "This paper studies the Last iterate convergence of proximal gradient methods for non-smooth (strongly) convex optimisation problem, with Random Reshuffle (RR) and Single Shuffle (SS) strategies. The paper considers the General Proximal Gradient Method, where proximal step is implemented at every step which is more natural than most recent works' variant (e.g. Liu & Zhou 2024) where the proximal step is implemented at every epoch. Further, the paper establishes an array of convergence results for RR and SS in general convex and strongly convex setting. For RR, the rates in the paper are always better than the SOTA by some polynomial factors in $n$, the number of individual functions. For SS, the algorithm might not converge when $n$ is small, but when the composite part $\\psi$ becomes the characteristic function over some feasible sets, the paper established some more refined convergence rate that improves over the SOTA.\n\n## Update after rebuttal\nI maintain that this is a very good paper and should be accepted. I will keep the score 4.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments. We will answer the reviewer's questions below.\n\n**Q1.** Our analysis is still inspired by and related to [1] but with some necessary changes to fit the shuffling method. However, whether the framework of [2] can be used to simplify the proof is unclear to us. We briefly explain why in the following. \n\n   - After a quick read, we think the core result of [2] is their Theorem 1, which relates the last-iterate convergence to the regret guarantee in online learning. As far as we can check, their Lemma 7 (the key to prove Theorem 1) relies on the fact that the gradient oracle $g_t$ is an unbiased estimator of $\\nabla f(\\boldsymbol{x}_t)$ conditioning on the history. \n\n   - In contrast, the gradient oracle in our setting is $g_t=\\nabla f_{\\textsf{i}(t)}(\\boldsymbol{x}_t)$, which is unfortunately biased due to the shuffling-based index $\\textsf{i}(t)$.\n\nAs such, their analysis immediately failed in our setting. Hence, how to make the idea in [2] work under the shuffling scheme remains unknown currently.\n\n**Q2.** Indeed, the improvement (or deterioration) comes from both the analysis and the algorithmic change. Simply speaking, the current analysis that considers randomness naturally leads us to make the proximal update happen in every step. More precisely, if we want to utilize randomness in the analysis, it is natural to recognize every single step as an update (one can think about SGD as an example). Therefore, the difference between our algorithm and [3] arises since the latter's analysis is epoch-wise, which therefore requires the proximal update to happen at the end of every epoch.\n\n   - For RR, such a different view is enough to improve the convergence, as commented by the reviewer (also pointed out in our Section 5).\n\n  - But for SS, things become tricky. As shown by our results, the new view (and hence the variation in the algorithm) is enough to guarantee better rates in the small epoch regime, but is inadequate in the large epoch regime. It turns out that one critical point missed in the proof is the deterministic property of the shuffling method, i.e., the index in every epoch goes over the entire set $[n]$ (the key property used in [3]). Hence, we could expect a better result for SS if this fact is used in the analysis (as stated in the last paragraph in Section 5). However, this is not an easy task due to the algorithmic change, especially for a general $\\psi$. But for some $\\psi$ (including but not limited to $\\psi=I_\\mathcal{C}$ in Theorem 4.6), we still can make it work. For the most general case and more details, we kindly refer the reviewer to our Lemma B.3 and the discussion in Lines 1427-1445.\n\n**References**\n\n[1] Zamani, Moslem, and François Glineur. \"Exact convergence rate of the last iterate in subgradient methods.\" arXiv preprint arXiv:2307.11134 (2023).\n\n[2] Defazio, Aaron, et al. \"Optimal linear decay learning rate schedules and further refinements.\" arXiv preprint arXiv:2310.07831 (2023).\n\n[3] Liu, Zijian, and Zhengyuan Zhou. \"On the Last-Iterate Convergence of Shuffling Gradient Methods.\" International Conference on Machine Learning. PMLR, 2024.", "claims_and_evidence": "The paper is theoretical in nature and I discuss the claims and evidence in the Theoretical Claims section.", "methods_and_evaluation_criteria": "The methods and evaluation criteria is valid.", "theoretical_claims": "The paper gives a number of convergence theorems, in particular, Theorem 4.2, Corollary 4.3, Theorem 4.4, Theorem 4.5, Theorem 4.6, and Theorem 4.7, all of which are backed by proofs in the appendices.\n\nAt the core of the these convergence rates, the authors gave a general last-iterate descent analysis in Lemma 5.1. I briefly went through Appendix B.1 which gives the proof for Lemma 5.1. While I didn't check the analysis therein line-by-line, the techniques seem solid to me.", "experimental_designs_or_analyses": "not applicable.", "relation_to_broader_scientific_literature": "The earlier Liu & Zho (2024) work gave a series of last-iterate convergence results of shuffling proximal gradient methods in various settings, some matching known lower bounds. However, their rates in the nonsmooth Lipschitz continuous setting did not demonstrate any improvements over the simple proximal (full) gradient method. This work follows up on the work of Liu & Zhou (2024) in the nonsmooth Lipschitz continuous setting in a spectacular way, proving improved convergence rates for RR in both the convex and strongly convex setting. The results for SS are however worse than that of Liu & Zhou (2024), failing to show convergence in some settings. But with some additional assumptions, the authors managed to improve the rates of Liu & Zhou even for SS.\n\nOn the algorithm side, the method studied in the paper differs from most of the recent works, where the proximal operator is applied at every step, instead of at every epoch. The epoch-wise proximal operator implicitly treats the shuffling method as a way to accumulate some approximate of the full gradients. The method considered in this paper is therefore in my opinion much more natural, and principled. \n\nI believe that this paper makes an important contribution towards of the field of shuffling gradient method.", "essential_references_not_discussed": "There are no essential references that the paper omits.", "other_strengths_and_weaknesses": "see the next section.", "other_comments_or_suggestions": "- Table 1 looks confusing and I suggest that the authors clearly mark the upper bounds and lower bounds.", "questions_for_authors": "There are a few questions that I would like to ask the authors about:\n\n- Regarding last iterate convergence: as the authors pointed out, the last-iterate convergence in Liu & Zhou (2024) is obtained following the technique of Zamani & Clineur (2023). While the proofs in this paper seems to be substantially different from that of L&Z, I wonder if the authors are still following the ideas of Z&C to obtain the last-iterate convergence guarantees? As noted in [1], the techniques in Z&C gives rise to stepsize schedulers that are, in some sense, separate from some backbone algorithms with only avg convergence guarantees. If the last-iterate convergence of this work also somewhat follows the ideas of Z&C, I wonder if it's possible that the observations in [1] can be applied to the results here as well? Is it possible that some (hopefully) simpler descent analysis for the avg iterate can be presented, and the scheduler part can then be added on top separately to obtain the last-iterate convergence?\n\n- Some further discussions on the source of improvement (or indeed, deterioration, in some cases) of the convergence rates: On one hand, the algorithm considered in this paper is somewhat more natural than the one in L&Z. On the other hand, the paper also presented different analysis techniques than the previous works, where the authors included in their considerations the randomness of RR and SS in each epoch. I wonder if the authors could comment on whether the improvement in the convergence rate for RR comes purely from this new insight in the analysis, or is the the fact that now proximal operator is applied at each step is also important for obtaining the improvement for RR? Similarly, can the authors comment on why, in the general case, is the convergence results for SS worse than that of L&Z? Is it purely a deficiency in the analysis (and it's absolutely fine if the authors have no idea on how to resolve it), or is the difference in the algorithm causing the difficulties in the analysis? Despite the fact that the algorithms in this paper and L&Z become the same when no proximal step is taken, can the authors also discuss why the results in Theorem 4.5 can be improved in Theorem 4.6 under the additional assumption? Is it because some difficulties with the every-step proximal operator can be overcame when the proximal operator is simple enough (suggesting that perhaps the difficulties might come from the proximal operator in Theorem 4.5), or there are some further insights in the analysis?\n\n\n[1] Defazio, Aaron, et al. \"Optimal linear decay learning rate schedules and further refinements.\" arXiv preprint arXiv:2310.07831 (2023).", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lDzjtq9PZ5", "reviewer": "Reviewer_P57t", "summary": "This work studies last-iterate guarantees under different shuffling models. In the RR model, the authors establish last-iterate (and suffix-averaging) guarantees, similar to the iterate-averaging results of (Koren et al., 2022), with slightly improved rates in the SS model. The obtained guarantees generally match or improve upon prior work on last-iterate guarantees in shuffling models (Liu & Zhou, 2024b). The results apply to both convex and strongly convex functions and support a broader class of $\\psi$ functions compared to $I_c$ in (Koren et al., 2022).\n\n## update after rebuttal\n\nI thank the authors for their response and continue to support the acceptance of this work.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's positive feedback. We will answer the reviewer's question below.\n\n**Question.** Thanks for the deep question. We will discuss it from the following two perspectives. \n\n  -  As mentioned in our Subsection 1.2 (see Lines 122-142, right column), the lower bound in [1] can be read as $\\Omega\\left(\\frac{1}{J^{1/4}n^{1/4}\\sqrt{K}}+\\frac{1}{\\sqrt{nK}}\\right)$ for the suffix average of the last $J$ epohs, i.e., $\\frac{1}{Jn}\\sum_{j=K-J}^{K-1}\\sum_{i=1}^{n}\\boldsymbol{x}_{jn+i+1}$. Therefore, for the average over all $K$ epochs, the lower bound is $\\Omega\\left(\\frac{1}{n^{1/4}K^{3/4}}+\\frac{1}{\\sqrt{nK}}\\right)$. In other words, the rate $\\Omega\\left(\\frac{1}{n^{1/4}K^{3/4}}\\right)$ for the average iterate could only be possible in the small epoch regime, i.e., $K\\leq n$.\n\n  - To be honest, we have no idea whether this rate is tight. If it is indeed achievable, then it means that there exists at least one problem instance such that the average iterate can improve over the last iterate by a factor of  $K^{-1/4}$, which is highly surprising and even seems impossible in our opinion since we have never seen an optimization method exibithing such a property if the stepsize is fine picked. As such, we suspect the lower bound for the average iterate should be improved.\n\n\n**References**\n\n[1] Koren, Tomer, et al. \"Benign underfitting of stochastic gradient descent.\" Advances in Neural Information Processing Systems 35 (2022): 19605-19617.", "claims_and_evidence": "The claims are supported by a thorough theoretical analysis across multiple shuffling models.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "Since the paper presents numerous technical results, most theoretical claims are established in the appendix, which is extensive. The reviewer primarily focused on Lemma 5.1 (Lemmas B.2 and B.3 in the appendix), which appear correct, and partially examined Lemma B.4 (RR scheme).", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The results greatly improve upon (Liu & Zhou, 2024b).\nThe technique builds heavily on (Liu & Zhou, 2024a) and, to a lesser extent, (Koren et al., 2022). However, the considered setting is more general, and Algorithm 1 aims to accommodate a broader range of shuffling schemes. This generality is reflected in Lemma 5.1, the use of $\\Phi$ on page 8, and the corresponding analysis.", "essential_references_not_discussed": "Essential references are discussed.", "other_strengths_and_weaknesses": "**Strengths:**\n\n- The analysis of shuffling schemes and last-iterate guarantees represents a valuable contribution to stochastic optimization, better reflecting real-world practice compared to sampling with replacement and standard iterate averaging.\n- The paper considers a broad range of settings, including convex, strongly convex, and general $\\psi$ functions.\n\n**Weaknesses:**\n\n- Some gaps remain compared to the best-known lower bounds from (Koren et al., 2022). Specifically, it is unclear whether the last-iterate guarantee is inherently worse than iterate averaging, given that the best-known lower bound when averaging across all epochs is $n^{-1/4} K^{-3/4}$. That said, the theoretical contributions of the paper remain solid even without resolving this issue.", "other_comments_or_suggestions": "Overall, the paper presents a strong contribution to an important topic, and the reviewer recommends its acceptance.", "questions_for_authors": "- In your view, what is the main challenge in closing the gap to the $n^{-1/4} K^{-3/4}$ lower bound established in (Koren et al., 2022)? Is the last iterate inherently worse, or should the lower bound for averaging across multiple epochs be improved?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies the last iterate convergence of proximal gradient methods for non-smooth (strongly) convex optimization problem, with Random Reshuffle (RR) and Single Shuffle (SS) schemes. All the reviewers recommend acceptance of the paper. Please incorporate the discussions into the final version of the paper.
Decision: Accept (poster)