Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness
Authors: Qi He
Peiran Yu
Ziyi Chen
Heng Huang
Venue: ICML 2025 poster (2025)
Keywords: shuffling-type gradient methods
convergence analysis
relaxed smoothness assumptions
Primary area: optimization

Abstract: Shuffling-type gradient methods are favored in practice for their simplicity and rapid empirical performance. Despite extensive development of convergence guarantees under various assumptions in recent years, most require the Lipschitz smoothness condition, which is often not met in common machine learning models. We highlight this issue with specific counterexamples. To address this gap, we revisit the convergence rates of shuffling-type gradient methods without assuming Lipschitz smoothness. Using our stepsize strategy, the shuffling-type gradient algorithm not only converges under weaker assumptions but also match the current best-known convergence rates, thereby broadening its applicability. We prove the convergence rates for nonconvex, strongly convex, and non-strongly convex cases, each under both random reshuffling and arbitrary shuffling schemes, under a general bounded variance condition. Numerical experiments further validate the performance of our shuffling-type gradient algorithm, underscoring its practical efficacy.

Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness
Qi He Peiran Yu²
Ziyi Chen
Heng Huang
Abstract
achieves optimal complexity of O(e-t) (Ghadimi and Lan, 2013), which matches the lower bound established by Arjevani et al. (2023).
Shuffling-ypp gradient methods are favored in practice for their simplicity and rapid empirical performance. Despite extensive development of convergence guarantees under various assump- tions in recent years, most require the Lipschitz smoothness condition, which is often not met in common machine learning models. We highlight this issue with specific counterexamples. To ad- dress this gap, we revisit the convergence rates of shuffling-ty tappinnggtteeggggeege gradient methods without assuming Lipschitz smoothness. Using our stepsize strategy, the shuffling-type gradient algorithm not only con- verges under weaker assumptions but also match the current best-known convergence rates, thereby broadening applicability. We prove the conver- gence rates for nonconvex, strongly convex, and non-strongly convex cases, each under both ran- dom reshuffling and arbitrary shuffling schemes, under general bounded variance condition. Nu- merical experiments further validate the perfor- mance of our shuffling-typ gradient algorithm. underscoring its practical efficacy.
In practice, however, random shuffling-type methods have demonstrated advantages over traditional SGD, These meth- ods, which involve iterating over data in a permuted order rather than drawing i.i.d samples, are widely used in deep learning frameworks due to their simplicity and computa- tional efficiency. Empirical studies have shown that such methods often outperform standard SGD in terms of conver- gence speed and generalization ability (Bottou, 2009; 2012). Notably, shuffling- training has been found to mitigate gradient variance, leading to smoother optimization trajecto- ries compared to purely stochastic updates (Gürbüzbalaban et al., 2021; HaoChen and Sra, 2019).
Theoretical analyses of shuffling- type methods have gained significant attention in recent years, aiming to explain their empirical success while tackling the unique challenges posed by the lack of independence between consecutive updates. Many early works focused on convex optimiza- tion, often relying on strong convexity assumptions estab- lish linear or sublinear convergence rates (Gürrbizzalaban et al., 2021; HaoChen and Sra, 2019; Safran and Shamir, 2020). More recently, research efforts have extended be- yond the convex setting (Mishchenko et al., 2020; Nguyen et al., 2021; Koloskova et al., 2023), suggesting that random reshuffling can exhibit faster convergence than SGD even in nonconvex settings under certain conditions, such as when gradient noise is structured or exhibits low variance.
1. Introduction
Gradient-baad based optimization has always been critical area due to its extensive practical applications in machine learn- ing, including reinforcement learning (Sutton and Barto, 2018), hyperparameter optimization (Feurer and Hutter, 2019), and large language models (Radford et al., 2018). While numerous gradient-basee based algorithms have been devel- oped for convex functions (Nemirovskij and Yudin, 1983; Nesterov, 2013; d' Aspremont et al., 2021), research non- convex functions has become particularly active in recent years, driven by advances in deep learning. Notably, with unbiased stochastic gradients and bounded variance, SGD
Despite these advances, most theoretical analyses rely on the Lipschitz smoothness assumption, which imposes re- strictive upper and lower bounds on the gradient variations. While this assumption holds in many standard optimiza- tion settings, it fails to capture a broad class important machine learning models, including deep language models (Zhang al., 2019), phase retrieval (Chen et al., 2023), and distributionally robust optimization (Chen et al., 2023), As result, many practical scenarios remain outside the scope of existing theoretical guarantees. To address this gap, our work develops new techniques to analyze the conver- gence of shuffling-type gradient algorithms under relaxed smoothness assumptions, aiming provide more compre- hensive theoretical foundation applicable wider range
'Department of Computer Science, University of Maryland, College Park. 'Department of Computer Science and Engineer- ing, University of Texas Arlington. Correspondence to: Qi He <qhe 12be 123@umi, uddu Heng Huang udd.
Proceedings of the 4dnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Revisiting Convergence: Shuflling Complexity Beyond Lipschitz Smoothness
of machine learning models.
The analysis of shuffling-type methods has a long history. For convex cases, Gürbüzbalaban et al. (2021) demonstrated that when the objective function is a sum of quadratics or smooth functions with a Lipschitz Hessian, and with a dimin- ishing stepsize, the average of the last update in each epoch of RGA converges strictly faster than SGD with probabil- ity one. Additionally, they showed that when the number of epochs T is sufficiently large, the Reshuffling Gradi- ent Algorithm (RGA) asymptotically converges at rate of (1/T9)) Similarly, Nguyen et al. (2021) established a con- vergence rate of (1 for strongly convex and globally L-smooth funcciions Furthermore, with uniform sampling and a bounded variance assumption or convexity on each component function, they showed that the convergence rate can be improved to (1/n22)).
We consider the following finite sum minimization problem:
1 n Σ flez i)
min WERd
F(w)=
(P)
where [=;i): Rd + R is smooth and possibly nonconvex for i E [n]:== = (1....,,): ,n.. Problem (P) covers empirical loss minimization as a special case, therefore can be viewed as formulation for many machine learning models, such as logistic regression, reinforcement learning, and neural networks.
We summarize our main contributions as follows:
We proved the convergence of the shuffling-typ gradi- ent algorithm under non-uniform smoothness assump- tions, where the Hessian norm is bounded by a sub- quadratic function of the gradient norm. With specific stepsizes and a general bounded variance condition, we achieved a total complexity of O(n 2+1 e e- gradient evaluations for the nonconvex case with random reshuf- fling, and O for arbitrary scheme, where 0 p < 2 is the degree of function L. These results match those with Lipschitz smoothness assumptions in Nguyen et al. (2021) when p = 0 and E-smoothness degenerates to Lipschitz smoothness.
In contrast, there is not much research nonconvex cases. For example, Nguyen et al. (2021) demonstrated a conver- gence rate of O(T- 2/3); Koloskova et al. (2023) proved
convergence rate of O + + min no
no
for single shuffling gradient method; Wang et al. (2024) analyzed Adam algorithm with random reshuffling scheme under (Lo, (L))-mmoothnss but they did not explicitly show the convergence rate.
2.2. Counterexamples
Although L-smoothness is empirically false in LSTM (Zhang et al., 2019) and Transformers (Crawshaw et al., 2022), we give some concrete counterexamples to demon- strate the popularity of non-Lipschitz functions in this sec- tion. First we give two machine learning examples, then we mention some common non-Lipschitz functions.
For the strongly convex case, we established a complex- ity of - for random reshuffling. In the non- strongly convex case, the complexity is O(n 241 e = for random reshuffling. Without assuming bounded variance, established complexity of Ö(ne 4) for arbitrary scheme in strongly convex case, and O(ne" 2) in non-strongly convex case.
Example The first example is distributionally robust optimization (DRO), which is a popular optimization frame- work for training robust models. DRO is introduced to deal with the distribution shift between training and test datasets. In (Levy et al., 2020), it is formulated equivalently as follows.
We conducted numerical experiments to demonstrate that the shuffling-ty ttppe gradient algorithm converges faster than SGD on two important non-Lipschitz smooth applications.
(E(w:)) - ) ) + 0, (1)
(((u::))-0)
min L(w, : Es
2. Preliminaries
WE WEW,DER
where w and @ are the parameters to be optimized, E is a sam- ple randomly drawn from data distribution P. f(w; {) is the loss function, si is the conjugate function of the divergence function 1b we choose to measure the difference between distributions, and X 0 is the regularization coefficient. It is proved in Jin et al. (2021) that L(w, 0) is not always Lipschitz-smone smooth even if E(w; {) is Lipschitz-smoott and the variance is bounded.
2.1. Shuffling-Type Gradient Algorithm
In practice, the random shuffling method has demonstrated its superiority over SGD, as shown in Bottou (2009) and Bot- tou (2012). Specifically, Bottou (2009) shows that shuffling- type methods achieve a convergence rate of approximately O11T²),, where T is the iteration count. Beyond shuffling- type stochastic gradient methods, variants such as SVRG have been applied in various scenarios, including decentral- ized optimization, as discussed in Shamir (2016) and De and Goldstein (2016).
The second example is the phase retrieval problem. Phase retrieval is a nonconvex problem in X-
Example 2.
2

---

Revisiting Convergence: Shufiling Complexity Beyond Lipschitz Smoothness
ray crystallography and diffraction imaging (Drenth, 2007; Miao et al., 1999). The goal is to recover the structure of molecular object from intensity measurements. Let æ E Rd be the true object and la 21 for r = 1,..., m, where ar E IRd. The problem to solve:
B(w, a C B(w, A( [[w))+))
dom(f); and for any W1, W1,W2
[V](()) - vf(w>)]l - { +C) ||w1 w2ll-
Another equivalent definition of Ê-smoothness in Li et al. (2023a) is:
Tn
min f(z) #ER
Σ Ur
(2)
Definition 2.3. real-valued differentiable function f f-smooth for some non-decreasing continuous function L [0, +00) - (0, +00) if
2m
This objective function is a high-order polynomial in high- dimensional space, thus it does not belong to the L-smooth function class.
almost everywhere.
Example 3. There are many common functions that are not Lipschitz smooth, including polynomial functions with order > 2, exponential functions, logarithmic functions and rational functions.
In the proof of sections we focus Definition 2.2, though Definition 2.3 provides clearer perspective on the relation- ship between Ê-smoothness and other smoothness notions. Both (To, I-) -s)-smoothesss and traditional Lipschitz sipschitzssmotth smooth- ness can be seen as special cases of Ê-smoothness. It is straightforward verify that the loss functions in phase retrieval and distributionally robust optimization (DRO) satisfy Ê-smoothness. While extensive research has been conducted based on (Lo, -ss-mmoothesss, comparatively less work has been done under the more general e-smooth framework. Xian et al. established convergence results for generalized GDA/SGDA and GDmax/SGDmax in minimax optimization, while Zhang et al. (2024) analyzed MGDA for multi-objective optimization under é-smoothness.
2.3. Relaxation of Lipschitz Smoothness
Because of the existence of these counterexamples, people have recently been investigating about smoothness assump- tions that are more general than the traditional Lipschitz smoothness. In Zhang et al. (2019). (Lo, L1) -mmoohhnsss was proposed as the first relaxed smoothness notion moti- vated by language modeling. It is defined as below:
Definition 2.1. (LLo, L1) L smoothhesss A real-valued dif- ferentiable function f' is (Zo, -mooohh if there exist con- stants Lp, L1= > 0 such that
3. Algorithm
sww)l s To + T. [V)((])
As demonstrated in our counterexamples, the Lipschitz smoothness assumption does not always hold in problem (P). In such non-Lipschitz scenarios, gradients can change dras- tically, posing a significant challenge for these algorithms. To address this issue, we propose a new stepsize strategy, de- tailed in Algorithm and section 4, to improve performance under these challenging conditions. This strategy aims to choose the stepsize to accommodate the variance and insta- bility in gradients, thereby enhancing the robustness of the optimization process.
Lipschitz smoothness can be viewed as a special case of (Lo. smoothness when L1 = O. Under L1)- smoothness assumption, various convergence algorithms have been developed including clipped or normalized GD/SGD (Zhang et al., 2019), momentum accelerated clipped GD/SGD (Zhang et al., 2020), ADAM (Wang et al., 2022) and variance-reduced clipping (Reisizadeh et al., 2023) with optimal sample complexity on stochastic non- convex optimization.
In this algorithm, we start with an initial point wg. During each iteration E [7), either all the samples are shuffled, we keep the order of the samples in the last epoch. This reshuffling introduces variance in the order of samples, which can help mitigate issues related to gradient instability, For each step j E [n]. we use the gradient from a single sam- ple with number mT. to update the weights w. The notation (t) is used to denote the j-th element of the permutation m n (t) for j E [n]. Each outer loop through the data is counted as an epoch, and our convergence analysis focuses on the performance after the completion of each full epoch.
Other relaxed smoothness assumptions include asymmet- ric generalized smoothness motivated by distributionally robust optimization (Jin et al., 2021) and its extension to a-symmetric generalized smoothness (Chen et al., 2023) and (-smoothness (Li et al., 2023a). In this paper, we use the definition of E-smoothness as below:
Definition 2.2. (E-smoothness) A real-valued differen- tiable function f is Ê-smooth if there exists some non- decreasing continuous function é [0, +o0) + (0, +oo) such that for any w E dom(f) and constant C > 0,
3

---

Revisiting Convergence: Shuflling Complexity Beyond Lipschitz Smoothness
Algorithm 1 Shuffling-type Gradient Algorithm
Assumption 4.2. F and f(;;1) are E-smooth for some sub- quadratic function e, Vi E [n].
Initialization: Choose an initial point th E dom(F).
for /. = 1, 1, ; do
Here, we assume all functions share the same l func- tion without loss of generality, we can always choose the pointwise maximum of all their E functions. We de- fine p to be the degree of the & function such that = supp20 {pl lim ((w) 0}. Since & is sub-quadratie we have 0 S < 2.
Set wp = 1;
Generate permutation (+ of [n].
Compute non-increasing stepsize Vjc-
for j 1...... do
Update / : w _ -. ( ) end for
Set ti = w/ end for
Next, we introduce our assumption about the gradient vari- ances.
Assumption 4.3. There exist two constants a, A E (0, +00) such that Vi E [n].
There are multiple strategies to determine (9))
If (+()) is fixed permutation of [n],, Algorithm func- tions as an incremental gradient method. This method maintains consistent order of samples, which can simplify the analysis and implementation.
|V -VFW)] & A[]VF(w]] + + (3)
a.s., Ve dom(F).
If (0) is shuffled only once in the first iteration and then used in every subsequent iteration, Algorithm operates as a shuffle-once algorithm. This strategy introduces randomness at the beginning but maintains a fixed order thereafter, providing a balance between randomness and stability.
Since component gradients behave as gradient estimations of the full gradient, this assumption can be viewed as a gen- eralization of the more common assumption E|[V F(w; {)
V F(w)]] I o², which is used in most E-smooth work.
4.1.1. NONCONVEX CASE
If 7(() is regenerated in every single iteration, Algo- rithm becomes a random reshuffling algorithm. This approach maximizes the randomness in the sample or- der, potentially offering the most robustness against the erratic behavior of non-Lipschitz gradients by con- stantly changing the sample order.
Let us denote A == F(w60) Under Assumptions
4.1 to 4.3, we have the following result for random shuffling scheme. Proofs can be found in Appendix A.1.1 and A. 1.
Theorem 4.4. Suppose Assumptions 4.1, 4.2 and 4.3 hold, Let {wr 1 be generated by Algorithm 1 with random reshuffting scheme. For any < 8 1, we denote 0lu² < 20(2u) H),
H = 121 G supfu G' == /2(1+ nA)G + 2na, = f(2G'). For any
Although the random reshuffling scheme is most used in practice, each of these strategies offers distinct advantages and can be selected based on the specific requirements and characteristics of the optimization problem at hand. For this reason, we will give convergence rates for random and arbitrary shuffling scheme.
> choose ht and T such that
T
ndi
32A1
T S
T S
T2
L2
2L
t=1
then with probability at least 1 - 8, we have | (t))) s G for every 1 S t T
4. Convergence Analysis
4.1. Main Results
In this section, we present the main results of our conver- gence analysis. Our findings indicate that, with proper step- sizes, is possible to achieve the same convergence rate, up logarithm difference, as under the Lipschitz smoothness assumption. First, we introduce the following assumptions regarding problem (P). Assumption 4.1 is standard as- sumption, and Assumption 4.2 requires all F and f(:;i) to be /-smooth.
1 T
(12 S
Remark 4.5. By choosing
= . = 0 00//1//1 -
O(n "rn"")), e), we can achieve complexity of T 0
outer iterations and O - total number of gradient eval- uations, ignoring constants, where is the order of the ! function in Definition 2.2. As p goes to 0, e-smoothness degenerates to the traditional Lipschitz smoothness, and
Assumption 4.1. dom(F) == {w E Rd F(w) < +00} # @ and F == infweR F(w)= > -00.

---

Revisiting Convergence: Shuflling Complexity Beyond Lipschitz Smoothness
our total number of gradient evaluations goes to O v e
For any e > 0, if we choose Tn and T such that
once again, which matches the complexity in Corollary 1 of Nguyen et al. (2021). If c I 1/vn, one possible stepsize is Vac
1/ = - 4 Aogg (oTg(VnT)
A nóe'
T
,T24 4
2
μT
(o()))
77
/ #
Our result here has polynomial dependency on J. T ~ It is important to note that, in our setting, 6 accounts for the probability that Lipschitz smoothness does not hold-a consideration absent in standard Lipschitz smoothness settings. Therefore, the dependency here is not as good in T-smoothness cases. In fact, a polynomial de- pendency on 5 is typical in papers with similar smoothness assumptions, e.g. in Li et al. (2023a), Li et al. (2023b), Xian et al. and Zhang et al. (2024).
8 "njuee'
To
max
2, I. 2, + 2), Lo
nd1
then for any 0 < 8 < 1, with probubility at least 1 5 we
have
F (T+1)) - F sc.
In Theorem 4.8, we can achieve a complexity of Ô (n"2'e) outer iterations and Ô (n "1 - total gra-
Next we consider arbitrary (*)) scheme in Algorithm 1.
dient evaluations with 7f Ö ( ignoring con- stants. This matches the result in Nguyen et al. (2021) with the same assumptions in the degenerate case of p = 0. The dependence on 5 is T = 0 -)))
Theorem 4.6. Suppose Assumptions 4.1, 4.2 and 4.3 hold. Let {we)) be generated by Algorithm with arbitrary scheme. Define H- = 2 G == sup(u 2 0lu²² < 2f(2u)) H, G == 22 + nA)G+ + 2na, == ((2G)). ) For any
It is not hard to follow proof of Theorem 4.6 for arbitrary scheme in strongly convex case and achieve a complexity of Ö (n 1 total gradient evaluations. Here we give slightly stronger result where we remove Assumption 4.3 to match the corresponding result in Lipschitz smooth case.
<> 0, choose i1 and T such that
1
2
8A,
Th S
T>
2/3AAA+
30 L
then we have || (V(
(()) ||| S G for every S T and
Theorem 4.9. Suppose Assumptions 4.1. 4.2 and 4.7 hold. Let {ı ( be generated by Algorithm I with arbitrary scheme. We denote S (ww) F(wgg)) )}, G' max VI (w, i)llww E S, E [m]], L == E(2G"). For any
T T
( 11
se.
<> O, choose Tu and T such that
6 (log(T)
11/²
This theorem gives the convergence rate for arbitrary scheme in Algorithm 1. By choosing 7) = 17 =
1/e = 11
n²
9112 + 1.2)0?*
WPT
n we achieve a complexity of O f
12T,2 log(T)
outer iter-
T = Ō(
1²2
total gradient evaluations, ignoring constants, Without the randomness in in every iteration, the complexity's 's dependency on n is increased by O(vn). One possible stepsize is 17 = 22(3A-2)
ations and O
where is the standard deviation at w.. Then we have [V (1)
[| I| S G' and
((t)) F -F* SC.
4.1.2. STRONGLY CONVEX CASE
In Theorem 4.9, we achieve a complexity of Ō (c-1/2 outer iterations and Ö (ne-1/2) total gradient evaluations with 7 = δ n (n-nee ignoring constants. It should be noted that the constant G' here is implicitly determined by constant p and can potentially be large. Therefore, the complexity here cannot be directly compared with those in Theorem 4.6 or 4.8.
For strongly convex case, we give results for both random reshuffling scheme and arbitrary scheme, with constant learning rate. Proof can be found in Appendix A.2.
Assumption 4.7. Function in (P) is p-strongly convex on dom
Theorem 4.8. Suppose Assumptions 4.1, 4.2, 4.3 and 4.7 hold. Let {wi(T= be generated by Algorithm I with ran- dom reshuffling scheme. For any < 8 < 1, we denote
4.1.3. NON-STRONGLY CONVEX CASE
H := max{ 30²
4u log& 1 + AI, 1 }. G := sup(u 2 0lu² V
Next we consider the case where only non-strongly convex- ity are assumed. In the following theorem, we assume the
20(2n) H). G' = 2(1 + mA)G + 22na, I = f(2G).
5

---

Revisiting Convergence: Shuflling Complexity Beyond Lipschitz Smoothness
optimal solution exists and denote one as wxe, the standard deviation w, as 0x :- / Ei (w.: i)l? and the average value of {wo Tr=1 as uT + Ei= "o Proof for this section can be found in Appendix A.3.
4.2. Proof Sketch and Technical Novelty
Broadly speaking, our approach involves two main goals: first, demonstrating that Lipschitz smoothness is maintained with high probability along the training trajectory {w₂}, and second, showing that, conditioned on Lipschitz smoothness, the summation of gradient norms is bounded with high probability. Here we slightly abuse the term 'Lipschitz' and 'Lipschitz smoothness' to refer to the property between neighboring steps along the training trajectory.
(T
Assumption 4.10. Functions f(;;)) in (P) are convex ondom F), for all i E [m].
Theorem 4.11. Suppose Assumptions 4.1, 4.2, 4.3 and 4.10 hold. Let {we J.- be generated by Algorithm I with random reshuffling scheme. For any < < 1, define H. G, G', L.
as in Theorem 4.4. For any E > 0, choose T7. = 1l and T such that
For the first goal, in Lemma A.4, we prove by induction that when starting an iteration with a bounded gradient, the entire training trajectory during this iteration will have bounded gradients. Consequently, we only need to verify the Lip- schitz smoothness condition at the start of each iteration. However, at this point, the two goals become intertwined. We need Lipschitz smoothness to bound the gradient dif- ferences, but we also need the gradient norm bounds to establish Lipschitz smoothness. Our solution is to address both issues simultaneously.
1
n
3n 3nl1un
(1) 0 w.ll
S min
21
A
+1
T
2LT
4 411200
w+ll 112
T Z
1jōe
then with probability at least 1 1- 8, we have VF s
for every 1 t T and
Assuming that, before a stopping time т, Lipschitz smooth- ness holds, we bound the gradient norm up to that time in Lemma A.5. However, this process nontrivial. Since we are examining behavior before a stopping time, every expec- tation is now conditioned on < т, rendering all previous estimations for shuffling gradient algorithms inapplicable. This presents a contradiction: we want to condition on t < T when applying Lipschitz smoothness, but we do not want this condition when estimating other quantities. In Lemma A.5, we find method to separately handle these two require- ments, allowing us to achieve both goals simultaneously.
F(WT)= F S.
By choosing 1) o 1
(
O (n'7 we
achieve a complexity of O outer iterations and total number of gradient evaluations, ignoring
constants. The dependency on ô is T 0 1 If
< 1/n, one possible stepsize is 2LV 41
/nn
Similarly, we can follow proof of Theorem 4.6 for arbitrary scheme and achieve complexity of O dient evaluations. Now we give a result without variance assumption 4.3.
4.3. Limitations and Future works
1 total gra-
2l.5
A Although we have proved upper bounds for the complexity of shuffling gradient algorithms, there are certain limitations in our work that we leave for future research:
Theorem 4.12. Suppose Assumptions 4.1, 4.2 and 4.10 hold. Let {w be generated by Algorithm I arbi- trary scheme. Define S (ww) < F(w())) )], G¹ = max mlxx fl; w)llw E S,i E [n]} co. L l(2G"). For any >> 0, choose 1/= 17 and T such that
First, as is common with many optimization algorithms, it is challenging to verify that the bounds presented are indeed the lower bounds. Future work could explore improving these results, for instance, by reducing the dependency on 8 to logarithmic factor, or by proving that the current bounds are, in fact, tight lower bounds.
1
36
1!
(1)
1.
7 S G
T = 0 0(151,))
2L
ne
Second, although we showed results for arbitrary shuf- fling schemes, there are better results for single shuf- fling under Lipschitz smoothness, for example Ahn et al. (2020) proved O ((,))) convergence rate for strongly convex objectives. It is interesting to see whether we can achieve the same convergence rate with e-smoothness as well.
then we have /F(W (wo (1))]| S fG 1 st Stsp T and
min F(WT) - F S. <E(T]
By choosing 17 - f). we have the complexity of O (2tt)) ) outer iterations and ((fft)) total number of gradi- ent evaluations, ignoring constants. One possible stepsize is 3
The results in Theorem 4.9 and Theorem 4.12 depends on constant G' that can be potentially very large and
1 GVL
6

---

Revisiting Convergence: Shuflling Complexity Beyond Lipschitz Smoothness
hard verify. In the absence of both Lipschitz smooth- ness and bounded variance, the behavior of gradients can be hard to track. We hope results here can be first step for future work.
SGD
0.8
Tixed-shuffling
Shuffle-once
0.6
Uniform-shuffling
0.4
Lastly, shuffling gradient methods have been inte- grated with variance reduction techniques (Malinovsky et al., 2023). Exploring the performance of these al- gorithms under relaxed smoothness assumptions is an- other promising direction for future work.
6000 Iteration t
8000
10000
5000
SGD
Fixed-shuffling
4500
Shuffle-once
Uniform-shie shuffiing
5. Numerical Experiments
We compare reshuffting gradient algorithm (Algorithm 1) with SGD on multiple é-smooth optimization problems to prove its effectiveness. Experiments are conducted with different shuffling schemes, on convex, strongly convex and nonconvex objective functions, including synthetic func- tions, phase retrieval, distributionally robust optimization (DRO) and image classification.
0
2000
4000
6000
8000
10000
Iteration
Figure 1: Experimental Results on Convex (up) and Strongly-convex (down) Objective Functions.
their sample average below.
5.1. Convex and Strongly Convex Settings
1 fi,((T) -
f(x) 1050
Σ
We first consider convex functions fa,(()) = x; + kx of x E R.50 for all (i,k) & == (1.2....,50) x {-10, 9, 10), well as their sample average f(z) = 1050 Eee = 50
(R,S)EE
exp(n + 1 1)= exp(-n)
Texp(a;) + exp(-xx)
1 Ei 24. It can
1050(exp(1) - -1
be easily verified that f and all fi. are convex but not strongly convex, and E-smooth (with t(u) 3u2/3) but not Lipschitz-smooth Then we compare reshuffling gra- dient algorithm (Algorithm 1) with SGD on the objec- tive miso f(z). Specifically, for each SGD update + x - V (x)), (k; E E is obtained uniformly at random. For Algorithm I, we adopt three shuffling schemes as elaborated in Section 3. The shufffifn scheme and shufffing-once fix all permutations (() respectively to be the natural sequence (1, 10), (1, -.,...- (50, 10) and its random permutation at the beginning, while the uniform- shuffling scheme obtains permutations (+) uniformly at ran- dom and independently for all iterations t. We implement each algorithm 100 times with initialization Ey = [1...., .1] and fine-tuned stepsizes 0.01 (i.e., /) = 0.01 for SGD and z 0.01 for Algorithm 1), which takes around min- utes in total. We plot the learning curves of f(x)) averaged among the 100 times, well as the 95% and 5% percentiles in the left of Figure 1, which shows that Algorithm with all shuffling schemes converges faster than SGD.
All these functions fj.A and f are I-strongly convex and t- smooth (with f(u) 5u + 5) but not Lipschitz-smooth. We repeat the experiment in the same procedure above, except that all the stepsizes are fine-tuned to be 10-5, The result is shown in the right of Figure 1, which also shows that Algorithm with all shuffling schemes converges faster than SGD.
5.2. Application to Phase Retrieval and DRO
We compare SGD with Algorithm on phase retrieval and distributionally robust optimization (DRO), which are &- smooth but not Lipschitz smooth. We use similar setup as in (Chen et al., 2023).
In the phase retrieval problem (2), we select and d = 100, and generate independent Gaussian variables x, a, ~ (O, 0.5La). initialization 20 (5,,, 0.54a), as well as y = |a, 2|2 + with noise n, ~ N(, 42) for í = 1, ...,, 1,..,,. m. We select constant stepsizes 2 x 10-6 and 71,"
3000
n
Then we consider strongly convex functions (x) = exp(a; - k) + exp(k x,)) + || for k) E and
0.007 for SGD and Algorithm respectively by fine-tuning and implement each algorithm 100 times. For Algorithm 1,

---

Revisiting Convergence: Shuflling Complexity Beyond Lipschitz Smoothness
1e6
Trainining Accuracy (%)
80
SGD
2.5
Fixed-shufling
60
Shuffle-once
Uniform-shufling
SGD
fiz)
1.5
40
Fixed-shuflling Shuffle-once
1.0
Uniform-shuflling
1000
2000
3000
4000
5000
6000
Iteration
0.0
0.0
0.2
0.4
0.6
0.8
1.0
tteration
1e3
70
Test Accuracy (%)
1e2
50
2.00
SGD
40
SGD
Fixed-shufif Siefl-huuflling
Fixed-shuflling
Shuffle-once
Shuffle-once Uniform-shuffling
Uniform-shuflinng
20
1.25
1000
2000
3000
4000 5000
6000
1.00
Iteration
0.75
Figure 3: Experimental Results on Cifar 10 Dataset.
0.50
2
3
Iteration
1c3
ing all the features 2, removing two categorical features ("country" and "status"), and adding standard Gaussian noise to the target get robust model. We use the first 2000 samples {æ;, V: J2 with features I₁ E R and targets y; E R for training. We use the loss function ( = 1 (Uc 2f w)² + 0.1 E (1 + (w() of (w) (34) 34 for any sample xe,, Dg. We use initialization no 0.1 and wo R3 from standard Gaussian distribution.
Figure 2: Experimental Results on Phase Retrieval (up) and
DRO (down).
we adopt three shuffling schemes as elaborated in Section 3. The fixed-shuffling scheme and shuffling-once fix all permutations (!) respectively to be the natural sequence 1, , 3000 and its random permutation at the beginning, while the uniform-shuffling scheme obtains permutations (4) uniformly at random and independently for all iterations We plot the learning curves of the objective function values averaged among the 100 times, as well as the 95% and 5% percentiles in the left of Figure 2, which shows that Algorithm with shuffle-once and uniform-shuffting schemes converge faster than SGD.
Then similar to phase retrieval, we implement both SGD and the three sampling schemes of Algorithm 1 100 times
with stepsizes (t) "t = 10-7_We evaluate (xx)) == min L(x,, 77) every 10 iterations. The average, 5% and 95% percentiles of (xx) among the 100 implementations are plotted the right of Figure 2, which shows that Algo- rithm with fixed shuffling converges faster than SGD.
5.3. Application to Image Classification
In the DRO problem (1), we select = 0.01 and (t)
203--41 - (corresponding to &i being x2 divergence). For the stochastic samples ç, we use the life expectancy data' designed for regression task between the life expectancy (target) and its factors (features) of 2413 people, and prepro- cess the data by filling the missing values with the median of the corresponding features, censorizing and normaliz-
2t+
We train Resnet18 (He et al., 2016) with cross- cross-entropy loss for image classification task on Cifar 10 dataset (Krizhevsky, 2009), using SGD and Algorithm with three shuffling schemes. We implement each algorithm 100 times with batchsize 200 and stepsize 10-3 After every 250 iterations, we evaluate the sample-average loss value well as clas-
'tttps: /wwwwwwwwwkk kaggle. com/datasets/ kumara jaraajissiii flife- httpa////ieee--eetttaaoaaaea-at expectancy-whoorreoorre download
"The detailed process of filling missing values and censoriza- tion: https://thccceeeeeeeeeeeee/ee http://thhhceeeeerrrrrrree amrer. rorrrrrrrrrrrr.....ooo.........r 06/1ife-expectancn ana lysi w-wiss with--ythhn//
8

---

Revisiting Convergence: Shuflling Complexity Beyond Lipschitz Smoothness
sification accuracy on the whole training dataset and test dataset. The average, 5% and 95% percentiles of these eval- uated metrics among the 100 implementations are plotted in Figure 3, which shows that Algorithm 1 with fixed-shuffling scheme outperforms SGD on both training and test data, and Algorithm I with the other two shuffling schemes outper- forms SGD on training data.
/ //api wew.mmtticcccoola...rr/orropsppo 1 16822133.
L. Bottou. Stochastic Gradient Descent Tricks, pages 421-436. Springer Berlin Heidelberg, Berlin, Heidel- berg, 2012. ISBN 978-3-642-35289-
doi: 10.1007/
978-3-642-35288--3 25. URL https:/ //dpii///.i...// org/ 10 10.1007/978 3- 642 35289- 8-8_25.
6. Conclusion
Z. Chen, Y. Zhou, Y. Liang, and Z. Lu. Generalized-smooth nonconvex optimization is as efficient as smooth non- convex optimization. arXiv preprint arXiv:2303.022. 02854,, 2023.
We revisited the convergence of shuffling-type gradient algo- rithms under relaxed smoothness assumptions, establishing their convergence for nonconvex, strongly convex, and non- strongly convex settings. By introducing a more general smoothness condition, we demonstrated that these meth- ods achieve competitive convergence rates without requir- ing Lipschitz smoothness, extending their applicability broader range of optimization problems. Our analysis cov- ers both random reshuffling and arbitrary shuffling schemes, showing that properly chosen step sizes can ensure effi- cient convergence both cases. Numerical experiments further validate our theoretical findings, demonstrating that shuffling-type methods outperform SGD in non-Lipschitz scenarios. These results provide a foundation for future work on shuffling-based optimization, including its integra- tion with variance reduction techniques, possible tighter bounds in certain situations and its application to large-scale machine learning problems.
M. Crawshaw, M. Liu, F. Orabona, W. Zhang, and Z. Zhuang. Robustness to unbounded smoothness of generalized signsgd. Advances in neural information processing systems, 15:9955-9968 2022.
S. De and T. Goldstein. Efficient distributed SGD with variance reduction. F. Bonchi, J. Domingo-Ferrer, Baeza- Baeza-Yates, Zhou, and X. Wu, editors, IEEE 16th International Conference Data Mining, ICDM 2016, December 12-15, 2016, Barcelona, Spain, pages 111-120. IEEE Computer Society, 2016. doi: 10.1109/CCDM.2011 0022. URL https: wttp:/ooooo.....//....... 2016 0022.
Drenth. Principles of protein X-ray crystallography. Springer Science & Business Media, 2007.
Impact Statement
A. d' Aspremont, D. Scieur, A. Taylor, et al. Acceleration methods. Foundations and Trends@ in Optimization, 5 (1-2):1-245 2021.
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
M. Feurer and F. Hutter. Hyperparameter optimization. Au- lomated machine learning: Methods, systems, challenges, pages 3-33, 2019.
Acknowledgments
S. Ghadimi and G. Lan. Stochastic first-and seroth-order methods for nonconvex stochastic programming. SIAM journal on optimization, 23(4):2341-2368 2013.
This work was partially supported by NSF IIS 2347592, 2348169, DBI 2405416. CCF 2348306. CNS 2347617.
M. Gürbüüzbalaaan, A. E. Ozdaglar, and P. A. Parrilo. Why random reshuffling beats stochastic gradient de- scent. Math. Program., 186(1):49 84, 2021. doi: 10. 10.1007/510000700099-44440...0 URL https::/tt/eete /oi. o 101110..10//110000
References
K. Ahn, C. Yun, and S. Sra. Sgd with shuffling: optimal rates without component convexity and large epoch re- quirements. Advances in Neural Information Processing Systems, 33: 2020.
J. Z. HaoChen and S. Sra. Random shuffling beats SGD after finite epochs. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, ICMI. 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 2624-2633. PMLR, 2019. URL http: hwwp::ttpp//oa/eee /pwppeeeeeigng..peeeeeeep.....ee mlr press/ v97/haochen1 9a. html.
Y. Arjevani. Y. Carmon, J. C. Duchi, D. J. Foster, N. Sre- bro, and B. Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199 (1):165-211) 2023.
L. Bottou. Curiously fast convergence of some stochastic gradient descent algorithms. 2009. URL https:

---

Revisiting Convergence: Shuflling Complexity Beyond Lipschitz Smoothness
K. He, X. Zhang. S. Ren, and J. Sun. Deep residual learn- ing for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770-778, 2016.
A. Radford, K. Narasimhan, T. Salimans, I. Sutskever, et al. Improving language understanding by generative pre- training. 2018.
A. Reisizadeh, H. Li, S. Das, and A. Jadbabaie. Variance- reduced clipping for non-convex optimization. arXiv preprint arXiv:2303.0088. 2023.
J. Jin, B. Zhang, H. Wang, and L. Wang. Non-convex distri- butionally robust optimization: Non-asymptotic analysis. Advances in Neural Information Processing Systems, 34: 2771-2782, 2021.
I. Safran and O. Shamir. How good is SGD with random shuffling? J. D. Abernethy and S. Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Gruz, Austria], volume 125 of Pro- ceedings of Machine Learning Research, pages 3250- 3284. PMLR, 2020. URL http: httpt::/pproceeding. mir wwwpppssssss./.p http:///1111///aaaaaaaaaaaa html.
A. Koloskova, N. Doikov, S. U. Stich, and M. Jaggi. Shuffle sgd is always better than sgd: improved anal- ysis of sgd with arbitrary data orders. arXiv preprint arXiv:2305.19255 2023.
A. Krizhevsky. Learning multiple layers of features from tiny images. Master's thesis, University of Toronto, 2009.
Shamir. Without-replacement sampling for stochastic gradient methods: Convergence results and application to distributed optimization. CoRR, abs/1 603.00570, 2016. URL htth: /ttp/aaaivvvv..////.//.../a..av.
D. Levy, Y. Carmon, J. Duchi, and A. Sidford. Large- scale methods for distributionally robust optimization. Advances in Neural Information Processing Systems, 33: 8847-8860, 2020.
R. S. Sutton and G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
H. Li, J. Qian, Y. Tian, A. Rakhlin, and A. Jadbabaie. Convex and non-convex optimization under generalized smoothness. In seveth- Conference on Neural Information Processing Systems, 2023a.
B. Wang, Y. Zhang, H. Zhang, Q. Meng. Z.-M. Ma, T.-Y. Liu, and W. Chen. Provable adaptivity adam. arXiv preprint arXiv:2208. 09900, 2022.
B. Wang, Y. Zhang, H. Zhang, Q. Meng, R. Sun, Z.-M. Ma, T.-Y. Liu, Z.-Q. Luo, and W. Chen. Provable adaptivity of adam under non-uniform smoothness. Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2960-2969, 2024.
H. Li, A. Rakhlin, and Jadbabaie. Convergence of adam under relaxed assumptions, 2023b.
G. Malinovsky, A. Sailanbayev, and P. Richtárik. Random reshufiling with variance reduction: New analysis and bet- ter rates. In Uncertainty in Artificial Intelligence, pages 1347-1357. PMLR, 2023.
W. Xian, Z. Chen, and H. Huang. Delving into the conver- gence of generalized smooth minimax optimization. In Forty-first International Conference on Machine Learn- ing.
J. Miao, P. Charalambous, J. Kirz, and D. Sayre. Extend- ing the methodology of x-ray crystallography to allow imaging of micrometre-sized non-crystalline specimens. Nature, 400(6742) 1999.
B. Zhang. J. Jin, C. Fang, and L. Wang. Improved analy- sis of clipping algorithms for non-convex optimization. Advances in Neural Information Processing Systems, 33: 15511-15525 2020.
K. Mishchenko, A. Khaled, and P. Richtárik. Random reshuffling: Simple analysis with vast improvements. Ad- vances in Neural Information Processing Systems, 33: 17309-17320, 2020.
J. Zhang, T. He, S. Sra, and A. Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity, arXiv preprint arXiv: 11881, 2019.
A. S. Nemirovskij and D. B. Yudin. Problem complexity and method efficiency in optimization. 1983.
Q. Zhang, P. Xiao, K. Ji, and S. Zou. On the convergence of multi-objective optimization under generalized smooth- ness. arXiv preprint arXiv:2405. 19440, 2024.
Y. Nesterov. Gradient methods for minimizing composite functions. Mathematical programming, 140(11:125-161, 2013.
L. M. Nguyen, Q. Tran-Dinh, D. T. Phan, P. H. Nguyen, and M. Van Dijk. A unified convergence analysis for shuffling-typ gradient methods. The Journal of Machine Learning Research, 22(1):9397-94MM 2021.
10

---

Revisiting Convergence: Shuflling Complexity Beyond Lipschitz Smoothness
A. A supplemental material
A.I. Nonconvex Case Analysis
In this section we prove the theorems section 4.1.1.
A. 1.1. LEMMAS
In this part we use notations as defined in Theorem 4.4, for completeness we repeat them here:
H = 4 6 = sup=uppu 2 5 20(2u) H} < co,
=
G' : v 2 + 2nno, L = f(2G").
We first state some lemmas that are useful in our proof. The following lemma is natural corollary of Definition 2.2, by the fact that is non-decreasing.
Lemma A.1. If F is E-smooth, for any w E dom(F) satisfying [V)ll]] S G, we have B(w, G/E(2G)) Cdom(F). For any w1, Wy E B(w, G/((2G))).
[VF(())) VF((2)) ((2G) w1 - w22l,
F(w)) S F(w2) + (VF(w2), w2) + ((2G) || w22l
The following lemma gives relationship between [ i) and /VF(()]] Lemma A.2. If Assumption 4.3 true, we have
[V((; < [/ + V2na.
Proof. From Assumption 4.3 we have that
V (w; 2 =
- V
2 [V](w;)) VF 2/
1=1
2n.A A [ 2no 2
= 2(1 + n4) [\) 2no
Taking square root on both sides and notice that [VF(w)] 2 0, > we have the conclusion.
According to Lemma A.2, for such that [F(w)] < G is true, we have
[V] i) < 2 + +nAG + 22na = G'
holds for all E [n)]
In our proof, we want that with high probability, L-Lipschitz smoothness in Lemma A.1, for both F(w) and f(w; i), (t) and w, (t) is true, for E [T), i.j E [n]. For that purpose, can prove the following inequalities with high
between w/
probability, for t E [T]:
[VV (2) < G: |/lb with GG))
[V/(w] (1) [1] [ S [n];
|ml| (1) (1 v'j in].
(4)

---

Revisiting Convergence: Shufiling Complexity Beyond Lipschitz Smoothness
By Lemma A.2 know that the third inequality in (4) holds if the first inequality is true. Noticing that &(C+)' ((2G') it suffices to prove that, for E [T].
IVF(W | - G, ||lg - w - G² /(/(((")) Vj [n].
For the first inequality, it can be hard to bound the gradient norm directly. The following lemma states the connection between gradient norm and function value of an f-smooth function.
Lemma A.3. (Lemma 3.5 in Li et al. (2023a)) If E-smooth, then
[VF(w)) ((2)) FF)
for any w Edom(F).
Since& & is sub-quat sub-quadratic, with Lemma A.3 can bound the gradient norm by bounding the difference between the function value and the optimal value. To ease the proof, let us define the following stopping time:
= min ( (1)) F > (T+++
For < r. we have (V (2) S G based on the definition of r and Lemma A.3, so the first inequality in (5) is satisfied. The following lemma proves that the other inequality in (5) is true for / < T as well, therefore guarantees the Lipschitz smoothness before
Lemma A.4. For t <T S
1 2I. we have all & [ra] and t [T], Iug (0)
101 - G¹ /e(2G").
Proof. We use induction to prove that
G'
w (1) B(wb)
),j 1,.,,..,.
T(2G')
First of all, this claim is true for j 0. Now suppose the claim is true for j S k 1, i.e.
|!m w S ((2G') . = 0, 1....,k--- 1
G'
we try to prove it for we (t) j S k 1. 1.
From Lemma A.1, we have Lipschitz smoothness, for all f(w; between wnm and (t)
uy if
Since we have
[V G' Vi E [m).
for any i E [n] and j E [k 1] we have
| [ ; i) <
IVS(W
: (9 (/o |) S G' + Ellw, - w s 26'
Hence, by the algorithm design we have
( -w
f0001 =
k-1 Th f Σ
k-1 7t [Vf(W); | -
k 1 2G' m <
G G'
n
L E(GG))
where the third inequality uses
n and n S 21
By induction, the claim true.
Therefore, we have the desired Lipschitz smoothness property in Lemma A.1 for 1. < T. Our next target is to bound
PP(r < T)
To simplify the notations, let us define
k
(0)
(w
(0) (1) (
vf(wb)==10)
n
1=0
12

---

Revisiting Convergence: Shuflling Complexity Beyond Lipschitz Smoothness
the average of differences between the gradients the start of iteration / and the actual gradients we used until step j in the t-th outer iteration. It worth mentioning that the actual step in f-th outer iteration is -1/, [VF + c.
Now we bound the probability of event (r T) by bounding the expectation of function value at the stopping time.
Lemma A.5. With parameters chosen in Theorem 4.4, we have
E[F(ug) (T) - =F] S 2A1.
Proof. For any < T,
F(wb ((w0+t)) - F(wo²)
S <(VF(w)) ),) wi (1+1) - -/0)) + 2 110 wi 11
(t+1)
Lit
n (VF( (1)) VF(wb) (3)) + (10) +
| F ww
(1)
+ f 10
2
The (1IVF( (1) 112 + [VF 19)
(1) 1|2 13)
Lid
| WVF(wn (t)) 1
S 1h
1 (VFF(w) (1)
71 1/
2
N I. 2 n-1
s 1h |VF (w)
(4)
)
Σ
1
-
11
(6)
2
2n
km0
Here the first and last inequalities are from Lemma A.1 and the second is because 7/ S 21.- to = T and taking expectation we have
Taking summation from = 1
1
E[F(wb)) (T)) F
A
E
1)t 2
VF
(1)
IP
E
(t)
(8) 19)
(7)
2n
k=0
Now let us get bound for the last term on the right hand side. For any t [T]. k E [m]. from Algorithm 1 and Cauchy-Schward inequality we have
| (1)
(2)
112
1221122
w ; ( l
(0)
n
1=
3
1
V (w) 11) (1
-F( +
3k3r n²
| FVF(w (m)
n²
3km
(VS( - 1T
n²
Let us denote the 3 terms on the RHS as A A, (t, k) and Aa(t, i.e. |ml
[ ( < - Aa(,
Since we are interested in E i i= 1,
2.L2
2n Σı w (1) - wu (912), we need to bound EΣT
m.
Σ A, k)] for
2n
For (1, k), since n (1) is randomly chosen, let J, = o (1)) ... (()) be the rlaleerra generated Algorithm 1, for
13

---

Revisiting Convergence: Shuflling Complexity Beyond Lipschitz Smoothness
L E [ have
1. R
1e1.2
n-1
31.2 Ti
(t)
Σ
Eill h: j=0
f :T -
2n
2n
112
h==
k=0
3/2212
k
VV ; /F(
2n
11²
k(n 1)
n-
31d k k:)
2 1) (A||VF(w))))) 12
2m
k=0
np L2
(AI )² +
2n
Here the second equation comes from variance of randomized reshuffling variables, (Lemma I in Mishchenko et al. (2020));
the first inequality is from assumption 4.3; the last inequality is because Ei=o k(n k) (x-1mix+1) < (n-1)
Let (Zehss be sequence such that Z1 0 and for any t E [2,
122
1 1 n-1
Z 7
(AIVF (w) ())) + 0²) +
Σ
A1 10t--1.4 1,
2n
2n
k=
We know {Z₂} is a supermartingale. Since F is a bounded stopping time, by optional stopping theorem, we have E[Z,] s R[Z)), which leads to
1-
T-1
12
(1
E
(1))) + +.))]
2n k=
2n
For Ag(t, k), for any E (T). taking summation over & we have Ek=o A2(t, k)) S nn (VF(w())) )1) therefore
2
1
11 T22
A2(t,
S E
| (w )))
2n
2
k=
1=1
For Ag(1,k), k), for any 1. < r. by Lemma A. we have
3kL2n?
Aa(t,k)
|1u( (8) w 12.
n²
Taking summation over k, taking expectation we have
1 2
R-1
1
3m/ I n-1
E
Aa(t,
E
Σ
|w05 -
w 111
2n
4n
k= 0
1=0
Now putting these together, we have
L2
E
||w)
w
(1)
E
(AI]V((w))) 12 02) 22
E
V
F
(2) ||
2n
2n
2
j=U
m
tm1
3nd
4 n-1
w/ 111
+
4n
jm
Since Te S 1
we have
3m 1
n 4n
rearranging the terms we have
27.
V3L
4n
E
1m mn 1
S E
21
+
2n
The n
1
4
(8)
1=1
0=
1=1
14

---

Revisiting Convergence: Shuflling Complexity Beyond Lipschitz Smoothness
Put this into (7) we have,
B Bl (7)) F*]
+ T
Tee |VF
| (1) - w 12)
SAI +E
2
2n
j=0
(8)
A + E
( ( + 1)
+11 )ー
n1
L' 17
<A + E
(
(9)
n1
1=1
<A + L²
T
3
n
t=1
Here the third inequality is from 1) S
and the last inequality is because d > 0 and T I T +1.
2 ++
Since E/= nh S T= we have (lF(wb (T) F+ < 2A,
Now we can bound the probability that T +T+1 1. Lemma A.6. With the parameters in Theorem 4.4, we have
(T) 8/2.
Proof. From Lemma A.5 and the value of H we have
E F( (r) F*]
2A 8 H
P(r ( F HJS
H
2
A. 1.2. PROOF FOR THEOREMS NONCONVEX CASES
Proof for Theorem 4.4
Proof. From (9) we have
L'O2 T
B[F(w5) F+] + E
V SA
SA
Σ
n
3
< 2
(10)
1=1
t=1
Therefore, since 8 < we have
8A
V F (wo (1) )2
TT
T
2 P(T = T + 1)
E
V
F
By Markov's 's inequality and our choice T', we have
P
T
V
(1)
>|
164
<
8 2
1T- Tea
15

---

Revisiting Convergence: Shuflling Complexity Beyond Lipschitz Smoothness
From Lemma (A.6) have P(r S T)
< 1.2 Therefore,
r T
V V >
SP(T s T) P
T
8
=
2
Since L ((26')= = P(G')) 22 ) with 17 - p'-2 T and T 0(a
we have the complexity.
The following lemma is useful in the proof of arbitrary scheme.
Lemma A.7. (lemma 6 in (Nguyen et al., 2021)) () For L < t and 0 < 1 S TN33'
1
we have
Σ j=0
Iw (2)
w0'12 S m3A 2)/ VF V (w) (wx")) )| + 30
Proof for Theorem 4.6
Proof. From inequality (6) we have for any & T,
F(wb ((w F(wb)))
s T1
IVF |12
(t)
10
1w
we
2
2n
1/ (3A + V
(8)
|| + 30
Th
|V (1)
)|1
2
2
3m 1.
S Th
4 IVF (2) ||2
2
where the second inequality is from Lemma A.7 and the last inequality is from n t from to r we have
Now taking summation of
L. 2(3A+22
o
((w(7)-FF) S =(((()) - F
F + Σ (
11 < +
m 2A1,
t=1
where the last inequality is because S T + 1 and the choice of n) Therefore we have = T + 1 since H 2 24,. On the other hand, we also have
8A1
(FF 12
1/
V (w) (w) 1|
1=1
Therefore, we have
T
1
VV (1) >12 S
8A1 < 2
T
Tmr
from our choice of T.
16

---

Revisiting Convergence: Shuflling Complexity Beyond Lipschitz Smoothness
A.2. Strongly Convex Case Analysis
Lemma A.8. If we let H 2 3e
lo + A and T/ = 1/, we have 2
2
log(
ip
Proof. From inequality (6) we have for <
nL n-1
F(w - F(w0))) ) S
! VF (1) )12 +
Σ
(8)
-wo
11
2
2n
k=0
1/ T + VE(W (2) )|2 +| 30
<
V )2
2
3n0
where the last inequality is from 1) -
S 2L From the definition of 7 we have
22/(3342)
8(11 DI)
r 2
1
log
3n0
lml
Proof for Theorem 4.8
Proof. From Lemma A.6 and the parameter choices we have P(T x T) S -.
Now we try to bound F(w(") (t) - F*. In the strongly convex case, for 1. < T we have
1tt (VF((b))] F(w6 (1) $ F(wg")
+
T,2r,
Σ
n-1
|| - w 1|
2
2n
j=0
La n
< F(w (t) lil (F (1) - - 7t F²)
[VF (w)
) )|²
1
(t)
wp
120)p
4
2n
j=0
here the first inequality is from (6) and the second one is from strongly convexity. We can rearrange the items and write the above inequality as
F(w (11)1))) F $ (1- pmme
==
(F(w))) (2) - -F*)+
L2'221
+ A(t),
(11)
n
where A(t) is defined as
A(t) == L'n R
n
|uy - u 11
17 F ((
L'
(12)
2n
4
Let 1). = 1) = have
Alog(vRT) (TT) 1T
we want
m7 2
> 0, therefore we need
log(vRr)
2 2. Taking expectation and summation we
2T
B[F(W(])) F=]
< [1[
IM
A1
(1
[M 2
2
7/4
E
Σ
(1
1-1 A(t)
2
t=1
212
< A, A/e/p (cceep((puu77111 /2]]
+ E
A(4)
n/
dc
22 log 2 (vTIT)
A1 +
+ E
A(t)
nI
17

---

Revisiting Convergence: Shuflling Complexity Beyond Lipschitz Smoothness
where the second inequality is from 1 S exp(-x) for (0, 1) and the last inequality is from Lemma A.8, P(r T) S 8/2 and the value of 77. Now if we look the last item, we notice from (8), by using Tv/2(3422 21 =+1
that we already have
E
A(t) S O.
Therefore, we have
8c
+ (A +
1
8L202 log" [log((/T))) (VTTT)
2 E ((((w)))) (w) - =F
8
n
P = T 1) ( F T T+1
2 L0FF(ug (T+1)) - =
P(F(wp (( F c/T T 1) S
E[F(wb (
(T+1),
F+ T +++1 +1
8L" log" (TTiT)
A
en??
3
8 8
8
<
+
8
8
2
where the last line is from the constraint T.
Proof for Theorem 4.9
) }}. Since strongly-convex, we have being compact. Therefore, we can define G' max {1l [w; i)ll E S,i [n]] co.
Proof. The algorithm starts from w/ and we define S = (w)F(w) s F(w
(t) ;)]] < G" for E [7] and i E [n]. On the other hand, by definition G' for / [T]. Therefore, by Lemma A.4 we have Lipschitz smoothness between wo() and wy for both (ww and (w; i), for E [7], i,j E [n]. The rest of the proof then follows the one in Lipschitz smoothness case (theorem 1 in Nguyen et al. (2021)).
we have w E S for all E [T), we have (' of F we have (
Now we prove that (t) E S, for E T. The statement is obviously true for t = 1. Now for E [2,T], assume that we already proved the conclusion for 1, -..-_ i- - 1, we can use Lipschitz smoothness in the first t iteeattons. Therefore, from theorem Nguyen et al. (2021) we have that
Dip²
(( - F(w.) S (1 pr))t11 A +
where p= g.
#. D (1²2 L.)o?. On the other hand, since
Asp² DD
we have
Dr² P
Di
(1 - -1-m)
< (1 pn) A1 +
< A
Therefore, we have F(w(")) < (( which means w (1) E S.
18

---

Revisiting Convergence: Shuflling Complexity Beyond Lipschitz Smoothness
A.3. Non-strongly Convex Case Analysis
Proof for theorem 4.11
Proof. From Lemma A.6 we know P(T T) < z.
For 1 < T, if = from lemma 7 in (Nguyen et al., 2021) we have that
1100 ((+1)) w.ll2= S (lmb) 2 FT]
+
2
11
V (wa;
(1)
(13)
n
where w. is the optimal solution. If we denote A(t)
Σ
Eز V/ww; mff1)11
and let a.
EL [V((w;;))1 we have that for any / (T]
n-1
n-1
B[A(O] Σ i)
v Vi(u j41 V((.))
(0)
i j=i
n-1
(n i)2i
n-
V f [. 3+111
(2)
n(n - 0)
n(n 1)o²
6
By optional stopping theorem we know that
n(n + 1)o
)] 0.
A(L)
Taking summation from t to 1 for (13) and taking expectation we have
2
n(n + 1)o2
2
((w)))) F²)] - |m!! (1)
w.112 +
E
n
6
2LT 0
< 1100 (1) w.1l
3n
where the second inequality uses T' 1. Therefore, we have
1 (1) w. w2112 +
2L
27 [111
E
(F( -F*)]
3n
T
(F(w)) (1) - F*)| - 11.
If we define wr $ ET= wb from convexity we have
T Σ
F(WT) F* < T
(( (2)
-F*.
tm1
19

---

Revisiting Convergence: Shuflling Complexity Beyond Lipschitz Smoothness
Consider the event F (F(WT) F* e), have
T Σ F+)
P(F S 7
Ei= (F (w) - FT) TT+1
x
Te
1
(1mg)
(1)
-w,1l 112 2LT 1 o3
nTC
3n
2
(
5
w.
1/T'
8
2'
where the last two incqualities are from the choices of and T,, separately.
Proof for Theorem 4.12
Proof. Similar to Theorem 4.9, if we have w E S for E [T', we have the desired Lipschitz smoothness.
Now we prove the conclusion by trying to prove that we fort E [2, T. assume that already proved the conclusion for 1, 1,.... t 1, use Lipschitz smoothness in the first t 1 iterations. Therefore, from (13) we have
(t) for t E [7]. The statement is obviously true for 1. Now
||/0 (t) - w.12 < 1110 (t-1) w= 2n/ (1-1)) F*] +
2
V f(w.: (t- )11
n
If F(w6 (1-1)) F S e, we have the desired conclusion.
If F(w (t- (1-1))- -- 1* e, since 71 5 +
/ /36 R.. we have
217 a-
(++1)
w.11 < (/206)) - w.112 2ne +
Σ
(n - G
n
i=1
< |110 (1) w+11 2me +
2 3
n
G
n 3
< (1 w.ll?
Therefore, if ((w)))) - F* 2 é for E [T], we have w (1) E for E (T). Taking summation we have that
F( - F(w))] s (mm1 -w,l2+ 2f
2m
Therefore we have
1 T
( F(ww)] )] - 2n' (110 w,ll
2 3T
Sc.
3
However, this contradict the assumption that (( - F* 2 e for 1 E [T]. Therefore, there must be t E [T] such that F(w(") F <
20


Reviews:
[{"review_id": "33Qlf6bkK2", "reviewer": "Reviewer_L7uE", "summary": "This paper studies convergence upper bounds of shuffling-based SGD on finite-sum minimization problems, focusing on random reshuffling SGD as well as SGD with arbitrary permutation (i.e., theorems that hold for any choice of permutations). The key contribution of this paper is the extension of standard (Lipschitz) smoothness assumption on the component functions to a generalized assumption named $\\ell$-smoothness. For $\\ell$-smooth functions with sub-quadratic $\\ell$, the paper carries out convergence analysis of random reshuffling and arbitrary permutation-based SGD on nonconvex, strongly convex, general convex functions. Numerical experiments are carried out to compare performance of with-replacement SGD and shuffling-based SGD variants.\n\n## Update after rebuttal\nAs I stated in my Rebuttal Comment, the authors' response addressed most of the questions I had, and I raised my score to 3 to reflect this. Having said that, I believe the paper has room for improvement in terms of clarity; I hope that the authors reflect the clarifications (e.g., on the dependence of different rates on $p$) in the next revision.", "questions": "", "limitations": "", "rating": 3, "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": "Thanks for the careful reading and constructive feedback. Below we respond to each point in detail:\n\n**Q1:** Achieving a logarithmic dependency on $1/\\delta$ remains an open challenge under $\\ell$-smoothness, and establishing such a result would constitute a significant advancement. As noted in Remark 4.5, most existing works under $\\ell$-smooth assumptions exhibit polynomial dependencies on $1/\\delta$. The only exception is in Theorem 4.1 of [1], where independence between steps allows for a log dependence; however, they turn to polynomial dependence in Theorem 6.2 a few pages later, after the independence is lost. That means no log complexity has been achieved with dependence between steps and $\\ell$-smoothness. Intuitively, under $\\ell$-smoothness, the parameter $\\delta$ accounts for bad cases from both variance and smoothness, whereas $L$-smooth scenarios only considers the former. Thus, significantly improving this dependency is nontrivial and would require substantial theoretical breakthroughs. We respectfully ask the reviewer to reconsider whether this aspect should be regarded as a major weakness, given the current state-of-the-art under similar assumptions.\n\n**Q2:** Thanks for highlighting this, we apologize for the confusion. The complexity bounds in Theorems 4.9 and 4.12 should not be directly compared to those in Theorems 4.8 and 4.11. The constant $G'$ in Theorems 4.9 and 4.12 can potentially be very large (as we mention in Section 4.3) and is implicitly influenced by $p$ through $G'$. These results serve as initial steps toward analyzing cases with no variance assumptions whatsoever. For completeness, if we were to adopt the variance Assumption 4.3 (similar to Theorem 4.6), we could derive results following proof of Theorems 4.6, yielding total gradient evaluation complexities of $\\mathcal{O}(n^{\\frac{p}{2}+1}\\epsilon^{-\\frac{1}{2}})$ and $\\mathcal{O}(n^{\\frac{p}{2}+1}\\epsilon^{-\\frac{3}{2}})$ for strongly convex and non-strongly convex cases with arbitrary scheme, respectively.\n\n**Q3:** To clarify the dependency of $T$ on $\\delta$: note first that we have $H=\\mathcal{O}(\\delta^{-1})$, which implies $G=\\mathcal{O}(\\delta^{-\\frac{1}{2-p}})$ and consequently $L=\\mathcal{O}(\\delta^{-\\frac{p}{2-p}})$. Combining these with the constraints $\\eta^3 T \\leq \\mathcal{O}(L^{-2})$ and $T \\geq \\frac{32\\Delta_1}{\\eta\\delta\\epsilon^2}$ gives the specified polynomial dependencies. Sorry for the confusion here, we will clarify this reasoning further in the appendix of a revision.\n\n**Q4:** Not really. The parameter $p$ is implicitly included within $L$ as we have $L=\\mathcal{O}(n^{\\frac{p}{2}})$. \n\n**W3:** Thanks for catching the missing assumption here, and $G'$ is finite indeed, but we need to add a short proof for that. We will add these in revision.\n\n**W4:** Sorry for the confusion from the wording. By \"smooth along the training trajectory,\" we meant that smoothness conditions hold between consecutive points during training, not necessarily globally across the entire trajectory. We recognize this wording was imprecise and will clarify this point explicitly to avoid misunderstandings.\n\nWe greatly appreciate the reviewer’s insights and suggestions, which have significantly improved the clarity of our manuscript.\n\n[1] Li, H., Rakhlin, A., Jadbabaie, A. (2023). Convergence of adam under relaxed assumptions.", "claims_and_evidence": "- Comments on theoretical claims are deferred to the \"Strengths and Weaknesses\" section.\n\n- The authors present several experiments, but unfortunately the performance gap between with-replacement SGD vs shuffling-based variants does not look significant except Figure 1. I doubt it's fair to claim better performance of random-reshuffling SGD or fixed-shuffling SGD based on Figures 2 and 3. Also, for these experimental results to corroborate the theoretical results, random-reshuffling SGD should have converged the fastest across different settings; however, it seems that there is no clear winner.", "methods_and_evaluation_criteria": "This paper does not propose a new method, and it analyzes existing methods theoretically under a relaxed set of assumptions. There are empirical evaluation results comparing the convergence speed of different methods, and I think the criteria for evaluation are sound.", "theoretical_claims": "I unfortunately did not have the time to check the details of the proofs in the supplementary material. I hope the authors provide a better intuition on why the requirement on the number of epochs $T = \\Omega (poly(1/\\delta))$ is difficult to remove (which I point out below in the Strengths and Weaknesses section).", "experimental_designs_or_analyses": "The design of experiments comparing the performance of with-replacement SGD and three variants of shuffling-based SGD looks quite standard to me, hence no issue identified.", "relation_to_broader_scientific_literature": "This paper studies popular variants of SGD, so it may have some broader impact on other scientific areas that involve optimization.", "essential_references_not_discussed": "The paper seems to include most of the essential references, but the authors should mention Mishchenko et al (2020) and Ahn et al (2020) when they discuss prior works on nonconvex optimization. Mishchenko et al are one of the first groups of people to prove convergence rates for nonconvex smooth optimization, and Ahn et al (2020) study nonconvex Polyak-Łojasiewicz functions. Also, it'd be more complete if the paper cites \"Convergence of Random Reshuffling Under The Kurdyka-Łojasiewicz Inequality\" by Li et al (2023).", "other_strengths_and_weaknesses": "Strengths\n- Extending the existing analyses of shuffling-based SGD to a wider function class of $\\ell$-smooth functions is definitely meaningful.\n\n- The authors honestly and directly discuss limitations of their results, which I appreciate.\n\nWeaknesses\n- First of all, to be strict, the paper violates the templates because the authors omitted the placeholder for author names. Unlike other papers, I don't see \"Anonymous Authors\" right below the title, as well as the footnote (attached to the placeholder) at the bottom of page 1.\n\n- The biggest weakness of the results presented in this paper is the dependence of the epoch count $T$ on $1/\\delta$. Each of the theorems on random reshuffling comes with an unfortunate $T = \\Omega(poly(1/\\delta))$ requirement on $T$, implying that for tiny choices of $\\delta$ we would need to run a ton of epochs to meet the requirement. Given that dependences on $1/\\delta$ in high-probability guarantees are typically poly-logarithmic, this is a big shortcoming in my opinion. The paper seems to build upon Theorem 5.3 of Li et al (2023a), and I understand that the existing theorem shares the same limitation. However, this doesn't mean that the improvement of poly to polylog dependence on $1/\\delta$ is impossible, so the authors should discuss this in the paper.\n\n- Some of the theorems have missing assumptions, although minor. In Theorem 4.11, we need to additionally assume that a finite $w_*$ exists. For Theorem 4.12, is $G'$ always guaranteed to be finite even when the sublevel set is unbounded? I guess so, but I'm not 100% sure.\n\n- I find the proof sketch confusing. The authors claim that they demonstrate that smoothness is maintained with high probability along the training trajectory, but smoothness is a global property of a function, and has nothing to do with a specific trajectory.", "other_comments_or_suggestions": "- In Line 102, the term RGA is used before being introduced a few lines below.", "questions_for_authors": "1. Is there any hope for improving dependencies on $1/\\delta$?\n\n2. For Theorem 4.9 and 4.12, why do these theorems have no dependence on $p$? Due to the absence of $p$, it looks to me that the epoch complexity of any arbitrary scheme is better than random reshuffling whenever $p > 1$, which does not sound right to me. Can you clarify why?\n\n3. After most theorems, the authors discuss step size choices and the resulting epoch/gradient computation complexities. It is quite difficult to follow why these particular choices of step sizes are used and how different dependencies are derived. Specifically, I failed to derive the $-\\frac{p}{2-p}$ terms that arise in the exponents of $\\delta$ when specifying the dependency of $T$ on $1/\\delta$. Can you elaborate on such derivations?\n\n4. When talking about \"one possible step size\" in Lines 207 and 242, I see no dependence on $p$, which is different from the choice of $\\eta$ in Lines 198 and 238 that involve $p$. Are the authors talking about the special case of $p=0$ here?", "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": "rb1PJowSv8", "reviewer": "Reviewer_UN8o", "summary": "- Most of the existing literature on shuffling SGD establishes the convergence rate under traditional gradient lipschitz continuity, which is a condition that does not hold in neural networks. To address this problem, the paper studies the convergence rate of shuffling SGD under the generalized smoothness assumption.\n- The paper proves the convergence rates of shuffling SGD for strongly convex, convex, and nonconvex functions, each under both random reshuffling (RR) and arbitrary shuffling schemes. The derived convergence rates recover the current best-known convergence rates established under the traditional gradient Lipschitzness assumption. Finally, the paper validates its theoretical findings by toy experiments.\n\n---\n**Update after Rebuttal**\n\nFirstly, I apologize for not being actively engaged during the rebuttal phase. Below, I summarize my current perspective on the paper:\n\n- My initial main concern regarding this paper was related to the technical novelty; I originally viewed the paper as combining existing techniques from shuffling SGD and general Lipschitz continuity. After carefully reviewing the authors' response and revisiting the paper, I find that the authors have addressed my concerns effectively.\n- The authors' response for the dependency on $p$ in Theorems 4.9 and 4.12 fully resolves my concern. However, the current paper remains slightly confusing. Specifically, in Section 4.1 (nonconvex case), both RR and arbitrary permutation schemes employ the bounded gradient assumption. Yet, for the strongly convex and non-strongly convex cases, RR results are presented under the bounded gradient assumption, whereas results for the arbitrary permutation scheme omit this assumption. If there is no particular reason for excluding the theorems on arbitrary scheme under bounded gradient assumption, I suggest the authors include these as well.\n\nOverall, I raise my score to 3 and lean toward acceptance.", "questions": "", "limitations": "", "rating": 3, "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": "Thank you very much for your detailed and helpful comments. Please find our responses below:\n\n**W1:** We appreciate your perspective but respectfully disagree that the paper is merely combining existing results. As we emphasize in Section 4.2, the main technical challenge arises specifically from analyzing the case when $t<\\tau$. Each step in our analysis is conditioned not only on the event $t<\\tau$ but also on all previous steps within the same epoch, due to the shuffling method. This dual conditioning has not been addressed by prior work that focuses only on either shuffling or $\\ell$-smoothness.  Additionally, our results hold under the relaxed gradient assumption (Assumption 4.3), and even without it, thereby broadening their scope compared to existing $\\ell$-smooth literature. We hope the reviewer can reconsider the novelty of our contribution in this context. Moreover, even if the novelty aspect were debated, considering the popularity of shuffling algorithms and restrictive nature of Lipschitz smoothness assumptions, our contributions extend theoretical guarantees to a broader class of problems. Thus, we respectfully suggest that novelty alone should not be considered a decisive reason for rejection.\n\n**W2:** We agree and will explicitly add the additional parameters for completeness. Thank you for this suggestion.\n\n**Q1:** Thanks for bringing up this important point. We apologize for any confusion caused. Indeed, complexities in Theorems 4.9 and 4.12 should not be directly compared to those in Theorems 4.8 and 4.11 due to the potentially large constant $G'$, which implicitly depends on $p$, as discussed in Section 4.3. The results in 4.9 and 4.12 are meant to be initial analyses for scenarios without the variance assumption. For completeness, if we did apply variance Assumption 4.3 and follow proof in Theorem 4.6, we could derive corresponding complexities of $\\mathcal{O}(n^{\\frac{p}{2}+1}\\epsilon^{-\\frac{1}{2}})$ and $\\mathcal{O}(n^{\\frac{p}{2}+1}\\epsilon^{-\\frac{3}{2}})$ for strongly convex and non-strongly convex cases respectively, with arbitrary shuffling scheme.\n\n**Q2:** Thank you for catching this typo. You are correct—the proper step size should be $\\eta_t=\\frac{6\\log(T)}{\\mu T}$. The learning rate currently listed in the draft mistakenly corresponds to the inner-loop step size. We appreciate your attention to details.", "claims_and_evidence": "Most claims are well-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 Theorems 4.4, 4.6, 4.8, and 4.9, and did not identify any significant flaws.", "experimental_designs_or_analyses": "The paper includes experimental results, but they are primarily intended to verify the theoretical findings rather than serve as a main contribution. As a result, I did not thorougly review the experimental design and analysis.", "relation_to_broader_scientific_literature": "While most prior work on shuffled SGD, such as results on random reshuffling, assumes Lipschitz-smooth gradients to establish convergence rates, this paper generalizes the framework by considering a weaker smoothness assumption. This generalization enhances the applicability of shuffling SGD, particularly in the context of neural network training.", "essential_references_not_discussed": "Essential references are appropriately cited and discussed in the paper.", "other_strengths_and_weaknesses": "Strengths\n\n- The paper derives the convergence rate of shuffling SGD under a weaker assumption (generalized smoothness) than prior works (Lipschitz continuous gradient).\n- The paper establishes the convergence rates for nonconvex, convex, and strongly-convex cases. The proofs seem correct and sound.\n- The gradient assumption (Assumption 4.3) is relaxed compared to prior works on shuffling SGD.\n\nWeakness\n\n- The main weakness of this paper is the novelty. In my view, this paper is simply a combination of two well-established topics—shuffling SGD and generalized smoothness—without introducing new technical analysis. In my understanding, the proofs of the theorems rely on the introduction of the random variable $\\tau$ to leverage local smoothness properties (just like [Li et al., 2023]), which are then applied to existing lemmas from the shuffling SGD literature. As a result, this work seems to be a straightforward application of existing results rather than a fundamentally novel contribution.\n- While this paper expresses the convergence rates in terms of $n$ and $\\epsilon$, recent studies on shuffling SGD ([Liu et al., 2024, Koloskova et al., 2024]) provide a more detailed characterization of convergence rates, including additional parameters such as $F(w_0)-F^*$, $\\mu$ (strong convexity), $\\sigma$. It would improve the completeness of the results if this paper also expressed the rates in a similarly detailed manner.", "other_comments_or_suggestions": "Typos:\n\n- In line 191R, “and” is missing in the end of the line\n- In line 258R, “ondom” → “on dom”\n- In line 285L, “Algorithm 1 arbitrary scheme” → “Algorithm 1 with arbitrary scheme”", "questions_for_authors": "Q1. I have a question regarding Theorems 4.9 and 4.12. Unlike Theorems 4.4, 4.6, 4.8, and 4.11, these two theorems do not include $p$ in their convergence rates. Why is this the case? Are these convergence rates tight? It seems more natural for these theorems to also depend on $p$.\n\nQ2. In Theorem 4.9, is the step size choice $\\eta_t = \\frac{6 \\log T}{\\mu n T}$ correct? Compared to the step size in Theorem 4.8, this choice is smaller by a factor of $n$. Could you clarify this discrepancy?", "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": "jgKcErorIM", "reviewer": "Reviewer_VM88", "summary": "This paper investigates shuffling-type gradient methods without assuming Lipschitz smoothness, which is often not satisfied in practice for many machine learning models. The authors propose stepsize strategies that enables convergence guarantees under a more general smoothness condition called \"$\\ell$-smoothness.\" They prove convergence rates for nonconvex, strongly convex, and general convex cases under both random reshuffling and arbitrary shuffling schemes. The paper provides theoretical contributions that match or extend existing best-known rates while requiring weaker smoothness assumptions, and validates the approach with experimental results.", "questions": "", "limitations": "", "rating": 3, "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": "Thanks for the careful reading and constructive feedback. Below we respond to each point in detail:\n\n**Assumption 4.3:**  Since component gradients behave as gradient estimations of the full gradient, this assumption can be viewed as a generalization of the more common assumption $\\mathbb{E}[\\|\\nabla F(w;\\xi)-\\nabla F(w)\\|]\\leq \\sigma^2$, which is used in most $\\ell$-smooth work, e.g., [1], [2].\n\n**W1:**  We want to mention that another key novelty is our analysis for the condition $t<\\tau$, where each step's analysis must account simultaneously for both the event $t<\\tau$ and the preceding steps within the same epoch due to shuffling. This dual conditioning has not been addressed by prior work that focuses only on either shuffling or $\\ell$-smoothness. Additionally, assumption 4.3 is relaxed compared to other $\\ell$-smooth literature.\n\n**W2:**  Achieving a logarithmic dependency on $1/\\delta$ remains an open challenge under $\\ell$-smoothness, and establishing such a result would constitute a significant advancement. As noted in Remark 4.5, most existing works under $\\ell$-smooth assumptions exhibit polynomial dependencies on $1/\\delta$. Intuitively, under $\\ell$-smoothness, the parameter $\\delta$ accounts for bad cases from both variance and smoothness, whereas $L$-smooth scenarios only considers the former. Thus, significantly improving this dependency is nontrivial and would require substantial theoretical breakthroughs.\n\n**W3:**  We agree that the experiments can better support our theory following the advice in 'claim and evidence' section. However, it can be hard to implement in reality, since the function $\\ell$ and constant $p$ are hard to determine. We leave it as a future work to design a better algorithm to work in practice. \n\n**W4:**  We agree with that. As we mentioned in Section 4.3, the potentially large constant $G'$ in Theorems 4.9 and 4.12 is indeed undesirable. These theorems are intended as initial steps toward a broader analysis without any variance assumptions.\n\n**Q1:** These counterexamples generally do not necessarily satisfy the $(L_0,L_1)$-smoothness conditions. One motivation to move from $(L_0,L_1)$-smoothness to generalized $\\ell$-smoothness is to cover functions such as double exponential functions $f(x)=a^{b^x}$ or rational functions $f(x)=P(x)/Q(x)$, where $P$ and $Q$ are polynomials, which satisfy $(L_0,L_1)$-smoothness conditions but not $\\ell$-smooth.\n\n**Q2:** Yes, we can use the theoretical results and give diminishing stepsizes. As suggested in theorem 4.4, as long as the stepsizes satisfy the constraints, they can be either constant or diminishing.\n\n[1] Li, Haochuan, Alexander Rakhlin, and Ali Jadbabaie. \"Convergence of adam under relaxed assumptions.\" Advances in Neural Information Processing Systems 36 (2023): 52166-52196.\n\n[2] Xian, Wenhan, Ziyi Chen, and Heng Huang. \"Delving into the convergence of generalized smooth minimax optimization.\" Forty-first International Conference on Machine Learning. 2024.", "claims_and_evidence": "The central claims about convergence rates under ℓ-smoothness are supported by theoretical analyses. While the authors demonstrate through counterexamples why Lipschitz smoothness is too restrictive in practice, the practical impact of their theoretical contribution is less clear.\n\nGiven that prior work has already established that shuffling SGD can outperform vanilla SGD, the experimental value in this paper should be focused differently. The core theoretical contribution is extending convergence guarantees to the ℓ-smoothness setting, which is more general than Lipschitz smoothness. A more meaningful experimental approach would have been to:\n1. Demonstrate convergence on problems that specifically violate Lipschitz smoothness but satisfy ℓ-smoothness, which they do attempt with their DRO and phase retrieval examples, but remains unclear for the Image Classification.\n2. Compare performance when using their theoretically-derived stepsizes versus other common choices to validate whether their analysis leads to practically superior parameter settings.\n3. Test the limits of the approach by examining problems with varying degrees of non-Lipschitz behavior (different values of the parameter p in the ℓ-smoothness condition)\n\nSimply showing that shuffling-type methods outperform vanilla SGD repeats what's already known rather than validating the unique aspects of this paper's theoretical contribution. The experiments would be more compelling if they directly connected to the paper's novel analytical insights rather than reestablishing the general benefits of shuffling.", "methods_and_evaluation_criteria": "The proposed methods are theoretically sound, but the assumptions are under discussed. Notably, Assumption 4.3 (which relates the variance of component gradients to the norm of the full gradient) appears unconventional, as I have not encountered it in previous literature, and it potentially represents a strong constraint on the problem class.\nThe experimental findings are discussed in the Claims And Evidence section of this review.", "theoretical_claims": "I roughly checked the proof of Theorem 4.4, and it appears rigorous.", "experimental_designs_or_analyses": "The experimental section provides some validation of the theoretical results, except for some limitations proposed already.", "relation_to_broader_scientific_literature": "The work builds on existing literature in shuffling-type gradient methods and generalized smoothness conditions. While it makes connections to both areas, the novel contribution is primarily in combining these two streams of research rather than developing fundamentally new insights in either area.", "essential_references_not_discussed": "I am not aware of any essential references that have been overlooked in this submission.", "other_strengths_and_weaknesses": "Strengths:\n1. The paper addresses an important gap by relaxing the Lipschitz smoothness assumption\n2. The theoretical results are mathematically sound and extend previous work. In particular, the analysis involving stopping time seems to be a novel contribution.\n3. The experimental results do show some benefits of shuffling-type methods\n\nWeaknesses:\n1. Except for the novel usage of stopping time, the theoretical novelty is somewhat incremental, building heavily on existing approaches\n2. The dependency on 1/δ is polynomial rather than logarithmic, which is a significant limitation\n3. The experimental validation doesn't sufficiently isolate the impact of the paper's specific contributions, and the connection between theory and practice is not firmly established\n4. The constants G' in the arbitrary shuffling results could be impractically large", "other_comments_or_suggestions": "The proof techniques would benefit from more detailed exposition in the main text, while the supplementary proofs could be refined for clarity and precision. Additionally, providing more intuitive explanations and practical discussions about why ℓ-smoothness matters in real-world applications would significantly strengthen the motivation for this work.", "questions_for_authors": "Do those counterexamples satisfy (L0, L1)-smoothness? What is the motivation to further relax (L0, L1)-smoothness to $\\ell$ smoothness?\n\nCan the (theoretical/empirical) results be generalized to other common strategies, like diminishing stepsizes?", "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": "DOaStYEptg", "reviewer": "Reviewer_Vaxv", "summary": "This paper establishes convergence of random reshuffling methods under a l-smoothness condition, where l is a function rather than a constant.", "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 acknowledging our contribution and careful attention to details. We will make modifications as suggested by the reviewer.", "claims_and_evidence": "New results that improve our understanding of random reshuffling approaches are potentially interesting, as random reshuffling is heavily used in practice.  This paper does a good job of reviewing existing literature and placing their result in the right context. Essentially they broaden the coverage of convergence results for RR methods to a new smoothness criterion that wasn't previously covered. It is a fairly general condition and it covers several problems of interest.\nIn terms of impact, although this is a useful contribution to the literature it's not ground breaking, and doesn't fundamentally change our understanding of RR methods, so I would lean towards an accept but not a strong accept.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I have not checked any theory from the Appendix. Results in the main body of the paper are precisely stated and make sense.", "experimental_designs_or_analyses": "Experiments seem reasonable and address the content of the paper. Error bars are shown, graphs are clear. For this sort of theory paper experiments are optional and don't need to address large scale problems.", "relation_to_broader_scientific_literature": "See Above", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "Please check that all uses of the term Lipschitz refer to Lipschitz smoothness, as there is a distinction between a function being Lipschitz and Lipschitz smooth. In some places (Line 80) when a function is described as non-Lipschitz the authors mean non-Lipschitz smooth.", "questions_for_authors": "N/A", "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: This submission focuses on unconstrained minimization and aims to combine shuffling idea with generalized smoothness. The goal is to generalize the Lipschitzness assumption on the gradient that is often violated in applications. 

This submission received 4 reviews and after the rebuttal period, all the reviewers agree on accepting the paper. The reviewers and myself agree that the problem is worth studying since both shuffling methods and generalized smoothness are common in applications and good theory on this front is interesting to the community.

On the other hand, there are also aspects of the paper that require improvements. For example, the polynomial dependence on the failure probability $\delta$ is noted by many of the reviewers (indeed it has been improved to a logarithmic dependence in the literature, without shuffling). 

Moreover, the assumption that the authors have (Eq. 3) is stronger than the works that focus on shuffling without the generalized smoothness assumption. Indeed, it is possible for the variance assumption Eq. (3) to require bounded domains in many cases and then the appeal of generalized smoothness is significantly less. Moreover, the constant $G$ that is used in the paper seems to be much larger than the previous works.

On the presentation side, the writing needs to be polished and improved. There are not many explanations between different results and many inline equations make the text quite a bit hard to read. The subtleties such as the stronger variance assumption compared to the shuffling literature are not discussed in the text. Similarly, proper comparisons with the literature on generalized smoothness are also necessary, to compare the constant $G$, dependence on $p$, dependence on $\delta$, and so on.
Decision: Accept (poster)