Tighter Convergence Bounds for Shuffled SGD via Primal-Dual Perspective
Authors: Xufeng Cai
Cheuk Yin Lin
Jelena Diakonikolas
Venue: NeurIPS 2024 poster (2024)
Keywords: primal-dual analysis
cyclic methods
shuffled sgd
Primary area: optimization
TL;DR: We provide fine-grained primal-dual analysis and tighter bounds for shuffled SGD by interpreting it as a primal-dual method with cyclic updates on the dual side. Obtained improvements are up to order-$O(\sqrt{n})$ both theoretically and empirically.

Abstract: Stochastic gradient descent (SGD) is perhaps the most prevalent optimization method in modern machine learning. Contrary to the empirical practice of sampling from the datasets \emph{without replacement} and with (possible) reshuffling at each epoch, the theoretical counterpart of SGD usually relies on the assumption of \emph{sampling with replacement}. It is only very recently that SGD using sampling without replacement -- shuffled SGD -- has been analyzed with matching upper and lower bounds. However, we observe that those bounds are too pessimistic to explain often superior empirical performance of data permutations (sampling without replacement) over vanilla counterparts (sampling with replacement) on machine learning problems. Through fine-grained analysis in the lens of primal-dual cyclic coordinate methods and the introduction of novel smoothness parameters, we present several results for shuffled SGD on smooth and non-smooth convex losses, where our novel analysis framework provides tighter convergence bounds over all popular shuffling schemes (IG, SO, and RR). Notably, our new bounds predict faster convergence than existing bounds in the literature -- by up to a factor of $O(\sqrt{n})$, mirroring benefits from tighter convergence bounds using component smoothness parameters in randomized coordinate methods. Lastly, we numerically demonstrate on common machine learning datasets that our bounds are indeed much tighter, thus offering a bridge between theory and practice.

Tighter Convergence Bounds for Shuffled SGD via Primal-Dual Perspective
Xufeng Cai
Cheuk Yin Lin"
Department of Computer Sciences University of Miscooninn-Madison
Department of Computer Sciences University of Wisconsin-Madisee
xcai74@wisc.edu
cylinGcs. wisc.edu
Jelena Diakonikolas
Department Computer Sciences
University of Misconsin-Madiise
jelena@ca wisc. edu
Abstract
Stochastic gradient descent (SGD) perhaps the most prevalent optimization method in modern machine learning. Contrary to the empirical practice of sampling from the datasets without replacement and with (possible) reshuffling each epoch, the theoretical counterpart of SGD usually relies on the assumption of sampling with replacement.
only very recently that SGD using sampling without replacement shuffled SGD has been analyzed with matching upper and lower bounds. However, we observe that those bounds are too pessimistic to explain often superior empirical performance of data permutations (sampling without replacement) over vanilla counterparts (sampling with replacement) on machine learning problems. Through fine- fine-grained analysis in the lens of primal-dual cyclic coordinate methods and the introduction of novel smoothness parameters, we present several results for shuffled SGD on smooth and non non-smooth convex losses, where our novel analysis framework provides tighter convergence bounds over all popular shuffling schemes (IG, SO, and RR). Notably, faster convergence than existing bounds the literature - by up to a factor O(vn), mirroring benefits from tighter convergence bounds using component smoothness parameters in randomized coordinate methods. Lastly, we numerically demonstrate common machine learning datasets that bounds are indeed much tighter, thus offering a bridge between theory and practice.
bounds predict
Introduction
Originally proposed in [38] SGD has been broadly studied in the machine learning literature due to its effectiveness in large-scale settings, where full gradient computations are often computationally prohibitive. When applied to unconstrained finite-sum problems
min [(x,, where f(x) = 1 Σ f(x)), wER!
(P)
SGD performs the update 2; .1-1 7/ (x. for it [n] (n) := (l.....n1) .n).. in each iteration 1. Traditional theoretical analysis for SGD builds upon the assumption of sampling E [M] with replacement according to a fixed distribution p = (pi....,pn) over [n), which leads to
Equal contribution
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Exitiin Bound Our Theary
Existing Bound Our Theery
Exitting Bound Our Theary
101
Rid Roey
10
10x) -iie
fitt (ioe)
10"
107
1000
200
(40
1000
Data passes
Data passes
Data passes
An illustration of the convergence behaviour of shuffled SGD for logistic regression problems on LIBSVM datasets luke, leu and a9a, where and our work. Due to randomness, we average over 20 runs for each plot and include a ribbon around each line to show its variance. However, as suggested by the concentration of L (see Section 4.1 and Appendix Eb, the variance across multiple runs negligible, hence the ribbons are not observable.
Figure 1:
step sizes from existing bounds
E, [i, ((2,-1)((ppp))) V (1;;,)), and thus much of the (deterministic) gradient descent-style analysis can transferred to this setting. By contrast, no such connection between the component and the full gradient can be established for shuffled SGD which employs sampling without replacement - making its analysis much more challenging. As a result, despite its fundamental nature, there were non-asymptotic convergence results for shuffled SGD until very recent line of work 12 20 21 30
34 35 22 All existing results consider general finite sum problems, with the same regularity condition constant (Lipschitz constant of fs its gradient) assumed for all the component functions. As result, the obtained convergence bounds are typically no better than for (full) gradient descent, and are only better than the bounds for SGD with replacement sampling if the algorithm is run for many full passes over the data 30 34
Furthermore, there is a large gap between the empirical performance of shuffled SGD and the predicted convergence rates from prior work 20 30. One cause for this discrepancy are overly pessimistic bounds on the step size in prior work, which are of order 1/(nLmax), where Lmax is the maximum smoothness constant over components f. in (P). In practice, the step sizes are tuned to achieve better convergence bounds than predicted by the current theory. We illustrate how restrictions on the step size affect convergence of shuffled SGD (with random permutations in each epoch) in Fig. [ where we plot the resulting optimality gap over full data passes when shuffled SGD is applied to logistic regression problems on standard datasets. To compare the effect of the step size 7) from
prior work and our work, we choose take 1) = 1/(v2nLmax) based on [30], and r = 1/ V LL) from our work, where L, are our novel fine- grainedi data-dependent smoothness parameters defined in Section 3 for smooth convex finite-sum problems with linear predictors. As can be observed from Fig. [ larger step sizes resulting from our theory lead to faster convergence of shuffled SGD and, as result, convergence bounds better predict the performance of shuffled SGD.
Building on these insights, we introduce a fined-graine theoretical analysis to transparently show how the structure of the data and the possibly different Lipschitz constants of the component functions or their gradients affect the performance of shuffled SGD, thus providing a better explanation of the heuristic success of shuffled SGD in modern machine learning.
1.1 Background and related work
10 38 for SGD (with replacement) has been extensively studied in many settings (see e.g., 19 convex optimization). Compared SGD, shuffled SGD usually exhibits faster convergence in practice 8 (37, and is easier and more efficient to implement [3]. For each epoch k shuffled SGD- style algorithms perform incremental gradient updates based on the sample ordering (permutation of the data points) denoted by (k), There are three main choices of data permutations: (i) (*()) म for some fixed permutation of [n]] for all epochs, where shuffled SGD reduces to the incremental gradient (IG) method; (ii) (*) = स where मे is randomly chosen only once, at the beginning of the first epoch, referred to as the shuffle-once (SO) scheme; (iii) x (A) randomly generated at the beginning of each epoch, referred to random reshuffling (RR).
For general smooth convex settings, the convergence of shuffled SGD has been established only recently. For the number of epochs K sufficiently large, [31] proved a convergence rate
2

---

Table 1: Comparison of results with state of the art, in terms of individual gradient oracle complexity required to output Tou with E (Z - -(xx)) ) c, where c > is the target error and
2, is the optimal solution. Here, o² > [V 112. D |
l1,, and generalized n Ei= L, x) defined in Section
linear model refers to objectives of the form f(z) 1
Parameters L I are defined in Section and satisfy i - Ei=1
L, and L S Lmax. Parameters
L, L. and G are defined in Section 3 and are discussed the text of this section.
PAPER
COMPLEXITY
ASSUMPTIONS
STEP SIZE
NGUYEN ET AL. 34 AL.
(RR) ( n D2
Valmaro D²
fa: Loav SMOOTH, CONVEX
MISHCHENKO AL.
(RR/SO) O nLmaa D2
Vakmare, D2
fi: Lmax SMOOTH, CONVEX
[Ours, Theorem 1
(RR/SO)
O " +
VnLHo.D? 2572
Jc: L,-SMOOTH, CONVEX
O "VLLLR
[Ours, Theorem
(RR/SO)
O D(DVELD
Vnlo.D? 2722
4: L, L,-SMOOTH, CONVEX GENERALIZED LINEAR MODEL,
0( AVE..
CHA AL.. P
(RR)
0
yn Inmmmao 2/12
1: Lonox SMOOTH, CONVEX, LARGE K
LOWER BOUND
mLmax
0 8a (K 2(1/21)
4: Gmax LiPsCHITZ CONVEX B. BOUNDED ITERATES, ||: GENERALIZED LINEAR MODEL.
SHAMIR 4P
(R//SO)
-
O
[Ours, Theorem 3
(RRISO)
O (C02))
? G, G.-LIISCHITZ CONVEX GENERALIZED LINEAR MODEL
O
OLL/VnK for RR, which leads to the complexity matching SGD. This result was later improved to (1/(n>/3///33) by [0]]00 30 34 for K sufficiently large and with bounded variance assumed at minimizer, while the same rate holds for SO (30). These results were complemented by match- ing lower bounds in [12), under sufficiently small step sizes utilized in prior work. The results in 30 34 require restricted ((1(nL)) step sizes and reduce to (L/KK) for small K, acquiring the not
same iteration complexity full-gru bull-gradient methods. Unlike in strongly convex settings, aware of any follow-up work with improvements under small for smooth convex settings.
The major difficulty in analyzing shuffled SGD comes from characterizing the difference between the intermediate iterate and the iterate after one full data pass, for which current analysis (see e.g., [30 in smooth convex settings) uses the global smoothness constant with a triangle inequality. Such bound may be too pessimistic and fail capturing the nuances of intermediate progress of shuffled SGD, which leads to a small step size and large K restrictions. To provide a more fine-graines analysis that narrows the theory-practice gap for shuffled SGD, we notice that such a proof difficulty reminiscent of the analysis of cyclic block coordinate methods relating the partial gradients to the full one. This natural connection was further emphasized in studies cyclic methods with random however, these results were limited to convex quadratics. More generally, it is possible to interpret shuffled SGD as a primal-dual method performing cyclic updates on the dual side and
permutations 24 47
(see PD in Section and (LL-PD) in Section 3). We note here that prior work dual coordinate methods 41 provided theoretical guarantees only for the algorithms that choose the dual coordinate
to optimize uniformly at random, while the cyclic variant (related to shuffled SGD) had only been studied numerically up until this work. Further discussion of related work appears in Appendix
1.2 Contributions
In this work, we study the convergence rates of shuffled SGD in various settings through a unified primal-dual perspective, making intriguing connections to cyclic coordinate methods. This analysis framework is novel and allows us to leverage cyclic bias accumulation techniques on the dual side to obtain fine- fine-grained convergence bounds. The obtained bounds mirror the improvements in randomized coordinate methods, which come from different coordinate smoothness parameters. While coordinate methods no better than full- full-gradient methods in the worst case, typical
3

---

problem instances, they are much faster and the improvements come precisely from more fine- grained view of smoothness. We see similar phenomenon in our analysis, which highlights the usefulness of the fine-grained smoothness characterizations introduced in our work.
We provide improved bounds for all three popular data permutation strategies RR, SO and IG, in smooth convex settings. When the problem objective narrows to empirical risk minimization with linear predictors, we are able to exploit the data-dependent structure and uncouple the linear and nonlinear parts of the objective function, allowing us to provide tighter data-dependent bounds, up to a factor of ((v Moreover, we show that our techniques extend to non-smooth convex settings, providing improved bounds over existing work.
We summarize our results and compare them to the state of the art in Table I As is standard, all complexity results in Table D are expressed in terms of individual (component) gradient evaluations. They represent the number of gradient evaluations required to construct solution with (expected) optimality gap e, given a target error 6 >> 0.
Extensions to mini-batching and IG. When presenting our results for general finite-sum problems (in Section 2. we consider simple updates without mini-batching for ease of presentation and to avoid introducing excessive notation. However, we emphasize that all our results can be extended to shuffled SGD with mini-batching. Our results are also the first provide convergence bounds that demonstrate benefits of mini-batching in shuffled SGD. For completeness and generality, the proofs in the appendix are carried out for mini-batch settings with arbitrary batch sizes b E {1.....m1] n.). Thus, all the results stated in Section can be recovered by setting b = 1. Moreover, our framework provide similar fine- mne-grained convergence bounds for IG. However, as IG is not commonly used in practice compared to RR and SO and due to space constraints, we only present our results for RR and SO in the main body and include the results for IG in the appendix.
1.3 Notation
We consider real d-dimensional Euclidean space (IRd, |I= where d is finite and || is the f2-norm. For a vector æ, we let x denote its j-th coordinate. For any positive integer m, we use [m] to denote the set (1.2...., m). Given matrix A, | sup=ER"" || ||xx| denotes its operator
norm. For a positive definite matrix A. || lI사 denotes the Mahalanobis norm, ||œ|||| := / (Aæ, æ). We use I to denote the identity matrix, and diag(v) to denote the diagonal matrix with vector on the main diagonal. For any j E [n). we define Ijt as the matrix obtained from the identity matrix I by setting the first j diagonal elements zero, and let I, be the matrix with only the j-th diagonal element nonzero and equal to 1. To handle the cases with random data permutations, we use the following definitions corresponding to the data permutation
{ n ..... of [m]] A. (aTI aeg.. aT..) permuting the rows based on given matrix A = [ar, .2. a.)
and U. = Ts 22 mm)) permuting the coordinates/subvecttrs based on a given vector (v) 02 vn)
2 Primal-Dual Framework for Smooth Convex Finite-Sum Problems
Throughout this section, make the following standard assumptions.
Assumption 1. Each fi convex and L:-mmooth, and there exists minimizer v. Rdd for f(x
Assumption I implies that f and all component functions fa are L-smooth, where Lmax maxie[n] Li- also implies that each convex conjugate J is -troongyy convex 3. In this section, we define A
diag Ltag.L,.......
Lay...y In) E Ranxnd, and slightly abuse the no-
tation to A, diag( Lyg.... Lig
Lan given permutation of [n]. For the
permutation ग at the k-th epoch, we denote A A myo for brevity.
We further assume that the variance Φ. is bounded, same as prior work 30 34
Assumption 2. The quantity of Σn [Vxx) 2 is bounded.

---

Algorithm 1 Shuffled SGD (Primal-Duue View, General Convex Smooth)
1: Input: Initial point mo IRd, step size (m 0, number of epochs K >
2: for k= to K do
3: Generate some permutation Ty of [nx] (either deterministic or random)
4: 11-1,1 -k-1
5: for to n in the ordering of m do (y' x2-1,)) fi (3y')}
6: yi arg ma ERd
7: 1k-1, arg min med { (v)i) 277 ||ar 3 1,=1) 1 1,2 7/ VJ (1
8: end for
9: Tk = Tk 1. yk = (yk: ,
10: end for
11:
Return: tKK = - T Σx=1 1
2.1 Primal-dual view of shuffled SGD
Problem P can be reformulated into primal-dual form using the standard Fenchel conjugacy argument (see, e.g.,
14),
1 {( y) =- 71 Σ (
min max EER VERnd
-
(PD)
where we slightly abuse the notation to denote y = (y) ..... y E Rnd and f is the convex
conjugate of fo defined by (3) = suP=Er' { (y. x) f(())) We let y = (y...... yz) T E Rndd be the conjugate pair of x E RR, i.e., y'e = arg max { (y, x) f7 (v)) and we denote y. = yv..
Given a primal-dual pair (ar, y). the primal-dual gap of (PD) is defined by Gap(æz, y) (ax (L(x, v) L(u, }) In particular, we consider the pair (æz, y.) for x E BE, and bound Gap" (xx, y.) == L(x,, v) L(x., y)) for arbitrary but fixed To finally obtain the function value gap f(x:) - fxx.) for (P). we only need to choose v = arg max L(x,, w) = yn-
Using this primal-dual formulation and standard convex conjugacy arguments, we can equivalently write the standard shuffled SGD algorithm in a primal-dual form as summarized Algorithm [
Improved bounds with new smoothness constants. To prove a convergence bound for shuffled SGD in this general setting, we first construct an upper estimate of Gap" (T y.) for some fixed to be set later, summarized in the following lemma.
12_ and (xR-1 12t1 generated Lemma 1. Under Assumption 1 for any ls E [K]. the iterates { by Algorithm satisfy
Ek
7K
26 21-1,
1]
U
yi xk - x
(1)
2k
T7
11
|| 1,141 12:1.
2m
2n
2n
where & Th Gap" (Iok: are the (block-wise) permuted vectors based on the permutation Te at the k-th epoch.
(x= y-) 3/ ||. - xz
1/2 -
Uk U2(0), and yo ya 12-
We note that the first term Ti = 2h E (gf, u xx-1,5-1) from Lemma I can be aggregated into the terms capturing the primal progress within one epoch and cancelled by the last term in Eq. ( The precise bound on Ti and its proof are provided in Lemma 10 in Appendix C.I The second term
T2 : 7k R2 (of y 2x 2k-1.)) requires us to relate the intermediate iterate 2*-1.; to the iterate 2% after one full data pass, which corresponds to a partial sum of the component gradients, each at different iterates {œR-1.5 1, 1,j y In contrast to prior analyses (e.g., Mishchenko et al. (0) using the global smoothness and triangle inequality to bound this partial sum, we provide tighter bound on To that tracks the progress of the cyclic update the dual side, in the aggregate.
5

---

To simplify the notation in the following lemmas and to clearly compare our results, we introduce the following novel definitions of smoothness constants for shuffled SGD:
L = n Ei= Lu 106-1)); EE' La(s-1))) 2 112
L = max Lg
(2)
L2 = | E (1)) EEEI (di)) 1/2
i = max Lg,
where (di) = di 1)( 1 and E Id..... E Raddd Permutation-dependdar quantities
Lg and Lg defined in are obtained directly from our analysis. We remark that L is bounded by the average smoothness of f and L is bounded by the max of individual smoothness constants of ft; see more details in Appendix B However, we argue in later sections, these upper bounds on ig and Lg are loose in general, and the convergence bounds based on Lg and Lg that obtain align better with the empirical performance of shuffled SGD.
Assuming that uniformly random data shuffling strategy is used (SO or RR), the resulting bound on To summarized in Lemma 2 while proof is deferred to Appendix B
Lemma 2. Under Assumptions 7 and 2 for any k E [K]. the iterates {yk hi and {x==1,hi= 1
generated by Algorithm with uniformly random shuffling (RR/SO) satisfy
+ 1)
10 11 yr.ull2, L T2l - E minn (2))
U 1
Mall3
2n
6
where To = 2h E (ot yhe 2x 0k 11), Us 1000 and y+ y,,
With Lemmas 1 and in tow, we ready present the main result of this section.
Theorem 1. Under Assumptions andd if S "y f./2L2 (1) 00 (0)
and Hk E The the output
k of Algorithm
7 with uniformly random (RR/SO) shuffling satisfies
m
(n + 1)i9 o.a
[[Hx(f((kk - f(xx)))
x x
2n
As a consequence, for any e > O, there exists a choice of constant step size Tjs 1i for which ([f(#x)-f(es after O nV nn hoi mo mo-m. m.1ā Vniso, [m0 11 individual gradient queries.
3/2
3 Tighter Bounds for Convex Finite-Sum Problems with Linear Predictors
To study the effect of the structure of the data on the convergence shuffled SGD, we sharpen the focus from general finite-sum problems convex finite-sum with linear predictors:
{f(x) = T Σ (aTxx)
min
(PL)
ZER' BER
where E RR (i E [n]) are data vectors and 4 R R are convex and either smooth or Lipschitz nonsmooth functions associated with the linear predictors (a, x) for i [n]. In addition their explicit dependence standard convex ERM problems where shuffled SGD commonly applied, such as support vector machines, least absolute deviation, least squares, and logistic regression.
the data, it is worth noting that problems of the form (PL) cover most of the
Problem PL) admits an explicit primal-dual formulation using the standard Fenchel conjugacy argument (see, e.g., [1 14),
min max [(x, v) (Ax, v) n Σ (v) #ERd yER"
Σ a xy (10)))
(PL-PD)
n
where (1,,0,, an) E Raxd is the data matrix and E R - of l, This observation allows to again interpret without-replacemmet SGD updates as cyclic
the convex conjugate

---

coordinate updates on the dual side. Note that due to the objective structure in (PL), the primal-dual formulation (L-PD) can decouple the linear (a x) and the non-linear (L,) parts within individual loss functions fi. We redefine the conjugate pair of æ E IRd be ye (yz..... ................................ y yr) E R", with (v))).
v arg eR (y'a,
In this section, we consider shuffled SGD with mini-batch estimators of size b and assume without loss of generality that bm for some positive integer The detailed primal-dual view of shuffled SGD adapted to (PL-PD) and mini-batch estimators is provided Alg. Appendix
3.1 Smooth and convex objectives
Throughout this subsection, we make the following (standard) assumptions, corresponding to As- sumptions and 2 from Section 2
Assumption Each &s is convex and Li-smooth (i E [n]), ie. 1(((x) - (()) S Li/0 - y for any 2, R. There exisis minimizer a. E arg min f(x)).
We remark that Assumption 3 implics that both and each component function f((x) (a x) are mmxx -smooth, where maxx = max L: Assumption 3 also implics that each convex conjugate E is T: -t-tonlyyly convex 3 In the following, we let A diag(L1, Lz,.... La), and
A₃ diag diag(Lz1, LT2,... Lgn), given a permutation π of [n].
We further assume bounded variance at C., same as prior work 30 Assumption 4. of +. ET (. )1 + ET (C x..) a| 12 is bounded.
46
Improved bounds with new smoothness constants. Our convergence bounds depend the smoothness parameters defined in Eq. (3) below. We provide a detailed discussion on how these parameters relate to traditional smoothness parameters both in the worst case and on typical datasets, in Section 4.1 with additional numerical results provided in Appendix
i. = mm
1
| j=1 bO A A b 1/2
i. = max Lux
i =
j=1 16) A (T)
i. max Tor;
where [t] := Di -i= 1)+1 J. In comparison to the smoothness constants defined in Eq. for general finite-sum problems, we note that the constants in Eq. (3) applying to generalized linear models are tighter and more informative estimates, as the data matrix A and the smoothness constants from the nonlinear part A are separated in Eq. 3 Thus, the constants î.ę and ī., directly depend on the data matrix, which explicitly demonstrates how the structure of the data affects the convergence of shuffled SGD. The following theorem states the convergence of Algorithm 2 with these new refined smoothness constants, while its proof is provided in Appendix C
Theorem 2. Under Assumptions 3 and njs S
and Hx Ek lkk then the
/2/21, Fr output t of Alg. 7 with uniformly random (RR/SO) shuffting satisfies
m Li () + 6b2 1)
([HK( - [(x.))) < 2n ||:00 F.
0.
As a result, given O, there exists a constant step size mp 1 such that ((f((x) f(x S
after O nV aoVVLLL Li -a. (n=b)(++)) VnLo- 1|200 -1a0o-=-133 individual gradient queries.
m(n-1)
few remarks are order here. When = n, we recover the standard guarantee of gradient descent, which serves sanity check as in this case the algorithm reduces to standard gradient descent.
(n=b)(nb)o²? the resulting complexity is O n " Lij ). Observe that this case When = ( 11) can happen when either large (compared to, say, 1/n) or when a, small (it is, fact, possible for to be zero, which happens, for example, when the data rows are lincarly independent). Unlike
7

---

in bounds from previous work, we observe from our bounds the benefit of using shuffled SGD compared to full gradient descent, where the difference by a factor that can be as large as vn, as we
(nn=))(n+bjo] ) the second term have discussed in the introduction (see also Section 4). When O ( n
in our complexity bound dominates. In this case, when b = 1, we recover the state of the art results from 12 30 34 while for b > 1 our bound provides the S2 n(m-1)
[n=b)(x+b] ) } improvement,
providing insights into benefits from the mini-batching strategy commonly used in practice.
3.2 Extension to non-smooth convex objectives
In non-smooth settings, we make the following standard assumption.
Assumption 5. Each & is convex and G,-Lipschitz (i [nl)), i.e. 14(x)) 4(v)) S GiIz yl for any y E IR; thus [g:(z)] I G; where ge(z) E dl((x). There exists minimizer arg min (x)).
If Assumption holds, each (a æ) is also Fmaxx-ipsshhtz with respect to æ, where Gmax = maX G.lla,1l To state our results, define I ;= diag(G?, G2 G2..... G2) and F
diag( Gh G ......,, G..)) given data permutation of [n]]
We now extend our analysis of Algorithm to convex nonsmooth Lipschitz settings, where the conjugate functions E (y') are only convex. Proceeding in Lemma [] we obtain bound on the primal-dual gap similar to (T). but lose two retraction terms induced by smoothness. Instead of cancelling the corresponding error terms like in the smooth case, rely the boundedness of the subgradients to bound these terms under a sufficiently small step size, which is common in nonsmooth Lipschitz settings. Similar to Section 2 we introduce the following quantities to obtain tighter guarantee with respect to the data matrix and Lipschitz constants
1 mn
G
/
EE= 1D)- A, bu 11)
G : +| 1/ J0n A. A. ( r
We discuss the improvements in convergence from G2 and G. in Section 4 while the convergence of Algorithm 2 is described in Theorem 3 with its proof deferred Appendix D
Theorem 3. Under Assumption 5 if H Ek and G = E.IVV E.IVV the output ãx of
Alg. 7 with possible uniformly random shuffling satisfies
K
(f(k( - f(x ()x
1:000
x.113
+ k=1
2ninG,
2n
As a result, for any > O, there exists a step size Thk = such that [E]((x)) - f(xx.)) S after
O( GGl -0-1.13 =.13) individual gradient queries.
Discussion of Our New Smoothness Constants and Numerical Results
To succinetly explain where our improvements come from, we now consider (L where l is 1-smooth and = 1, ignoring the gains from the mini-batch estimators (for large K) and our softer guarantee that handles individual smoothness constants. For this specific case, L - Lmmax = maxigign ||a,]]?, and thus results for the smooth case and the RR and SO variants match state of the art in the second term, which dominates when there are many (K Ω [Imxx_""") epochs. When there
o!
K = K0O( D epochs in the SO and RR variants or for all regimes of K in the IG variant, the
difference between and state of the art bounds comes from the constant L that replaces Lmax- and our improvement by a factor v LLmax/ L. Note that (( ) from prior bounds, which the dominating term in the small K regime, is even worse than the complexity of full gradient descent, as the full gradient Lipschitz constant of f in this case is 1 AAA | ||2 < Lmax-
8

---

Given a worst-case permutation x, and denoting by As the data matrix A with its rows permuted according to म; our constant can be bounded above by Liax using the following sequence of inequalities:
(
L= + 1 J-1n A. A 6 1rll2
l12
S
2j=1 [ 1-1 An A G-null
(5))
A 1
(4)
n²
(#i)
Σ |a:11 maxigign ||,.11 - -maxs
where (i) holds by the triangle inequality, (ii) holds because the operator norm of the matrix 10-11) x I(-- (equal to the operator norm of the bottom right (n - -++ + 1) x (n - + 1) submatrix of A,A)) is always at most | = || for any permutation π, and (iit) holds by bounding above the operator norm of a symmetric matrix by its trace. Hence L is never larger than Lmax, but can generally While each of these inequalities can be loose, we emphasize that (iii) is almost always loose, by factor that can be as large as n.
)
much smaller, due to the sequence of inequality relaxations in (4).
As a specific example where Ż is smaller than Limax by factor of n. consider the example of Gaussian data, where we draw n i.id. standard Gaussian vectors from (00, and take d = n. By standard concentration results, with high probability, all columns/rows of Aş in this case are near-orthogonal (see, e.g., 7 Chapter]) and |al12 = d = for all i. As a result, the operator norm to trace inequality (iii) is loose by factor d = n, with high probability. Note that this example all individual smoothness parameters of components Si are essentially the same (w.h.p.) and equal [|a, 1 thus the improvement of our bound on the smoothness parameter does not come from averaging from the structure of the data. This observation is important for contrasting the results from Section P and Section 3 In particular, focusing solely on the finite sum structure and ignoring the structure of the data matrix would provide no improvements in the resulting convergence bounds.
As further evidence, we empirically evaluate Lmax/ L on 15 large-scale machine learning datasets and demonstrate that those datasets Lmax/ is of the order n² for E [0.15, 0.96] (see Sec. 4.1 for more details), providing strong evidence of a tighter guarantee as a function of n.
For the nonsmooth settings, by similar sequence of inequalities, we can show that G < G G which can be loose by factor 1/n due to the operator norm trace inequality. Thus, our bound is never worse than what would be obtained from the full subgradient method, but can match the bound of standard SGD, or even improve upon it for at least some data matrices A.
4.1 Numerical results and discussion
In this section, we provide empirical evidence support our claim about usefulness of the new convergence bounds obtained in our work. In particular, we conduct numerical evaluations to compare to the classical smoothness constant L on synthetic datasets and on popular machine learning benchmark datasets.
For a more streamlined comparison and to focus on the dependence on the data matrix, we as- sume that the loss functions l, all have the same smoothness constant, which leads to I (maxi |||a,|]" //))/((( + Σy= IG-1)1 A A (l)llll).. Since the scale of the smoothness con- stant of the loss functions is irrelevant for the ratio Lmax/ 7 in this case, for simplicity, we take it to equal one. Note that assuming different smoothness constants over component loss functions would only make our bound better compared related work (see Eq. 3 and the discussion following it).
We also compare i. and Tamax on number of benchmarking datasets from LIBSVM [15), MNIST 17), CIFAR1O [22), and Broad Bioimage Benchmark Collection (28). For each dataset, we generate a uniformly random permutation π for the data matrix A and compute L,. We repeat this procedure 1000 times for all datasets and display the average Lmax/ L in Table 2 except for e2006train, CIFAR10. MNIST, and BBBC005 where we do 20 repetitions due limitations of
TTis because it is possible for inequalities (i) and (ii) to be loose, in addition to (iii).

---

Table 2: The following table shows the computed values of Lmaxx where Ż is the empirical mean of Ln random permutations. We note that the quantity V / represents the improvement provided by the bound via our novel primal-dual perspective, compared previous work.
DATASET
#FEATURES (d)
#DATAPOINTS (n)
Liaa
log, Lmax/L
logmin(d.n) Lenax/
AIA
1605
5.50
0.231
0.354
A9A
123
32561
5.49
0.164
0.354
BBBCO0S
361920
19201
18.3
0.295
0.295
BBBCO10
361920
201
7.04
0.368
0.368
CIFAR10
3072
50000
10.0
0.213
0.287
DUKE
7129
44
38.0
0,962
0,962
E2006TRAIN
150360
16087
5.35
0.173
0.173
GISETTE
5000
6000
3.52
0.145
0.148
LEU
7129
38
32.8
0.960
0.960
MNIST
780
60000
19.1
0,268
0.443
NEWS20
1355191
19996
42.1
0.378
0.378
RCVI
47236
20242
111
0,475
0.475
REAL-SIM
20958
72309
194
0.471
0.529
SONAR
60
208
6.26
0.344
0.448
TMC2007
30438
21519
10.9
0.239
0.239
computation resources required for each calculation. We observe that among the datasets that we consider, which contain all three data matrix "shapes" d >>> n, d << nı, and d R our novel bound dependent on L is much tighter. For instance, for revi and real- datasets, where d and are of the same order, observe that Lmuxx/ are approximately 111 and 194, respectively. For news20 dataset where >>> n,, Lmaxx /L = 42.1. For MNIST, where << n, Lmax/ L 19.1. Further results are provided in Appendix
Finally, as a justification for using the empirical mean of L, over random permutations π in the results displayed in Table 2 we observe in our evaluations that the values of T / T.x are fairly concentrated around their empirical mean values. Histogram plots showing the empirical distributions of Lmax/L, for each of the datasets are provided in Appendix
We conclude with a few additional remarks. Our results indicate that the structure the data is important for predicting behavior of popular machine learning methods such variants of shuffled SGD considered our work, and thus should be incorporated in their study: as demonstrated the Gaussian data example, considering simple finite structure and ignoring the dependence the data can lead to overly pessimistic bounds. Thus it would be interesting to provide further theoretical study of shuffled SGD that incorporates distributional assumptions for the data. Additionally, as mentioned in the previous paragraph, we empirically observed that permutation-deeenneen parameter L, concentrates around its mean for permutations generated uniformly at random. Thus. it would be interesting consider whether our theoretical results can be strengthened depend on the mean value of L (as opposed maximum). We leave such considerations for future work.
Acknowledgements
This research supported in part by the U.S. Office of Naval Research under contract number N00014-22-1-2348.
10

---

References
[1] Alckh Agarwal, Martin J Wainwright, Peter Bartlett, and Pradeep Ravikumar. Information- theoretic lower bounds on the oracle complexity of convex optimization. In Proc. NeurlPS 09, 2009.
[2] Kwangjun Ahn, Chulhee Yun, and Suvrit Sra. SGD with shuffling: optimal rates without component convexity and large epoch requirements. In Proc. NeurlPS 2020.
[3] Amir Beck. First-order methods in optimization. SIAM, 2017.
[4] Amir Beck and Luba Tetruashvili. On the convergence of block coordinate descent type methods.
SIAM Journal on Optimization, 23(4):2037-2060, 2013.
[5] Yoshua Bengio. Practical recommendations for gradient- based training of deep architectures. Neural Networks: Tricks of the Trade: Second Edition, 2012.
[6] Dimitri P Bertsekas and John N Tsitsiklis. Gradient convergence gradient methods with errors. SIAM Journal Optimization, 10(3):627-642, 2000.
[7] Avrim Blum, John Hopcroft, and Ravi Kannan. Foundations of Data Science. Cam- bridge University Press, Cambridge, 2020. ISBN 9781108485067. doi: DOI: URL
https://www. cambridge org www./boooeeeeeeeeeo 144C0300E433110601111166662 wwwoos/oooodaainosss-ooooooo data- science/
[8] Léon Bottou. Curiously fast convergence of some stochastic gradient descent algorithms. In Proc. Symposium on Learning and Duta Science, Puris' '09, 2009.
[9] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-3) 2-1211111,,11 1,1, 2018.
[10] Séhastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 2015.
[11] Xufeng Cai, Chaobing Song, Stephen J Wright, and Jelena Diakonikolas. Cyclic block coor- dinate descent with variance reduction for composite nonconvex optimization. arXiv preprint arXiv:22 12.00888 2022.
[12] Jaeyoung Cha, Jaewook Lee, and Chulhee Yun. Tighter lower bounds for shuffling SGD: Random permutations and beyond. arXiv preprint arXiv:2303.07/60. 2023.
[13] Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of Mathematical Imaging and Vision, 40(1):120-145
2011.
[14] Antonin Chambolle, Matthias Ehrhardt, Peter Richtárik, and Carola-Bibiane Schonlieb. Stochastic primal-dual hybrid gradient algorithm with arbitrary sampling and imaging ap- plications. SIAM Journal on Optimization, 28(4):2783-2808, 2018.
[15) Chih-Chung Chang and Chih-Jen Lin. LIBSVM: library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST), 2(3): 2011.
[16] Christopher M De Sa. Random reshuffling is not always better. In Proc. NeurlPS 2020.
[17] Li Deng. The MNIST database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 2966):141114,, 2012.
[18] M Gurbuzbalaban, Asu Ozdaglar, and Pablo Parrilo. Convergence rate incremental gradient and incremental Newton methods. SIAM Journal on Optimization, 2944):2542- 2019.
[19] Mert Gurbuzbalaban, Asuman Ozdaglar, Pablo A Parrilo, and Nuri Vanli. When cyclic coordi- nate descent outperforms randomized coordinate descent. In Proc. NeurlPS' 17, 2017.
[20] Mert Gürbüzzalaban, Asu Ozdaglar, and Pablo Parrilo. Why random reshufiling beats stochastic gradient descent. Mathematical Programming, 186:49-84 84, 2021.

---

[21] Jeff Haochen and Suvrit Sra. Random shuffling beats SGD after finite epochs. In Proc. ICML'19, 2019.
[22] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[23] Zehua Lai and Lek-Heng Lim. Recht-ré noncommutative arithmetic geometrri mean conjecture is false. In Proc. ICML 2020.
[24] Ching-Pei Lee and Stephen J Wright. Random permutations fix worst case for cyclic coordinate 2019.
descent. IMA Journal of Numerical Analysis,
[25] Xiao Li, Zhihui Zhu, Anthony Man-Cho So, and Jason D Lee. Incremental methods for weakly convex optimization. arXiv preprint arXiv: 16687, 2019.
[26] Xingguo Li, Tuo Zhao, Raman Arora, Han Liu, and Mingyi Hong. On faster convergence of eyclic block coordinate descent-type methods for strongly convex minimization. The Journal of Machine Learning Research, (8()):67416664 2017.
[27] Cheuk Yin Lin, Chaobing Song, and Jelena Diakonikolas. Accelerated cyclic coordinate dual av- eraging with extrapolation for composite convex optimization. arXiv preprint drXiv:2303.16279 2023.
[28] Vebjorn Ljosa, Katherine L. Sokolnicki, and Anne E Carpenter. Broad bioimage benchmark collection. https://bbl..brrodmttttttttt org/ htsr:mmage__et_t 2012. Accessed: 2023-05- 16.
broadnstiiuute
[29] Olvi L Mangasarian and MV Solodov. Serial and parallel backpropagation convergence via nonmonotone perturbed minimization. Technical report, University of Wisconsin-Mann Madissn Department of Computer Sciences, 1993.
[30] Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random reshuffling: Simple analysis with vast improvements. In Proc. NeurlPS' 20, 2020.
[31] Dheeraj Nagaraj, Prateek Jain, and Praneeth Netrapalli. SGD without replacement: Sharper rates for general smooth convex functions. In Proc. ICML'19, 2019.
[32] Angelia Nedic and Dimitri P Bertsekas. Incremental subgradient methods for nondifferentiabl optimization. SIAM Journal on Optimization, 12(1):109-133) 2001.
[33] Yu Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341-36) 2012.
[34] Lam M Nguyen, Quoc Tran-Dinh, Dzung Phan, Phuong Ha Nguyen, and Marten Van Dijk.
A unified convergence analysis for shuffling-type gradient methods. The Journal of Machine Learning Research, 22(1)9997--9440, 2021.
[35] Shashank Rajput, Anant Gupta, and Dimitris Papailiopoulos. Closing the convergence gap of SGD without replacement. In Proc. ICML 20,,''0,10 2020.
[36] Benjamin Recht and Christopher Ré. Toward a noncommutative arithmetic geometrri mean inequality: Conjectures, case-studies, and consequences. In Proc. COLT 12, 2012.
[37] Benjamin Recht and Christopher Ré. Parallel stochastic gradient algorithms for large-scale matrix completion. Mathematical Programming Computation, 2013.
[38] Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics, pages 400-407, 1951.
[39] Itay Safran and Ohad Shamir. How good is SGD with random shuffling? In Proc. CO..'200, 2020.
[40] Ankan Saha and Ambuj Tewari. On the nonasymptotic convergence of cyclic coordinate descent methods. SIAM Journal on Optimization, 23(1):576-601, 2013.
12

---

[41] Shai Shalev-Shwarte and Tong Zhang. Stochastic dual coordinate ascent methods for regularized loss minimization. Journal of Machine Learning Research, 14(1). 2013.
[42] Ohad Shamir. Without-replacement sampling for stochastic gradient methods. In Proc. Neur/PS 2016.
[43] Chaobing Song and Jelena Diakonikolas. Fast cyclic coordinate dual averaging with extrapola- tion for generalized variational inequalities. arXiv preprint wrXi:22102.1324. 2021.
[44] Ruoyu Sun and Yinyu Ye. Worst-case complexity of cyclic coordinate descent: 0(n2) gap with randomized version. Mathematical Programming, (8544)25,,, 2021.
[45] Trang H Tran, Lam M Nguyen, and Quoe Tran-Dinh. SMG: shuffling gradient- -ased method with momentum. In Proc. (CML'21, 2021.
[46] Trang H Tran, Katya Scheinberg, and Lam M Nguyen. Nesterov accelerated shuffling gradient method for convex optimization. In Proc. ICML 22, 2022.
[47] Stephen Wright and Ching-pei Lee. Analyzing random permutations for cyclic coordinate descent. Mathematics of Computation, 89(325):211--2244 2020.
[48] Yangyang Xu and Wotao Yin. Block stochastic gradient iteration for convex and nonconvex optimization. SIAM Journal on Optimization, 25(3): 188))166661716, 2015.
[49] Yangyang Xu and Wotao Yin. A globally convergent algorithm for nonconvex optimization based on block coordinate update. Journal of Scientific Computing, 72(2):700-734, 2017.
[50] Bicheng Ying, Kun Yuan, Stefan Vlaski, and Ali Sayed. Stochastic learning under random reshuffling with constant step-sizes. IEEE Transactions Signal Processing, 67(2):474-489 2018.
[51] Chulhee Yun, Shashank Rajput, and Suvrit Sra. Minibatch vs local SGD with shuffling: Tight convergence bounds and beyond. In Proc. ICLR'22, 2022.
13

---

Supplementary Material
Outline.
The supplementary material of the paper is organized as follows:
Section
provides a brief survey on shuffled SGD and its related work.
Section
presents the proofs related the smooth convex setting from Section 2 where we only
assume each component function fs to be convex and L,-smooth.
Section presents the proofs related to the smooth convex setting with linear predictors from
Section
Section
D
presents the proof's related to the non-smooth convex setting with linear predictors from
Section
Section
presents the full details of the computational experiments performed in the paper.
A Further Related Work
In this section, we continue with the discussion on the background of shuffled SGD from Section We would like to briefly recall that shuffled SGD usually performs better in practice when compared to SGD, and is also easier and more efficient to implement. However, in terms of the theoretical analysis, sampling without replacement introduces the sampling bias at each iteration, making it difficult to approximate shuffled SGD by full gradient descent. Using empirical observations, shuffled SGD was conjectured to converge much faster than SGD with replacement, based on the noncomnutative arithmetic citiimmttic-eometriii mean inequality conjecture [6), which was later proved to be false [[6] 23). As shuffled SGD can be faster than SGD least in some regimes remained
consequence, whether
open g until a breakthrough result in 20). where it was shown that for the class of smooth strongly convex optimization problems, the convergence of the RR variant of shuffled SGD is essentially of the order-(1 (2) for K full passes of the data (also called epochs), which is faster than order-(1 l/nK) convergence of SGD for sufficiently large K. This bound for the smooth strongly convex case was later improved under various regimes and additional assumptions 21 30 31 34 42). while the tightest of those bounds were matched by lower bounds in 35
Since our results are for the general (non- moon-ttrongly) convex regimes, in this section we focus on the results that apply to those (convex, smooth nonsmooth Lipschitz) regimes. For convex nonsmooth Lipschitz problems, we are only aware of the results in [22 These results are only useful when the number of data passes K is small and the number of component functions is large, they contain an irreducible order- error, and are not directly comparable to our results.
v
For the IG variant of SGD without replacement (deterministic order), asymptotic convergence was with further convergence results for both smooth and nonsmooth settings 32 34 [5]. As IG does not benefit from randomization, it is known to have worse convergence bound than RR under the Lipschitz Hessian assumption [18 which was also shown in more general settings (30].
established in
6
29
provided in 18 25 30
In this paper, viewed shuffled SGD primal-dual method where the updates are performed on the dual side in a cyclic manner, thus we can leverage techniques from general cyclic methods. However, in contrast randomized methods (corresponding to standard SGD), cyclic methods are usually more challenging to analyze [33] basic variants exhibit much worse worst-case complexity
49], with more refined results being 43 While the inspiration for our work came from these recent results [TT] 27 43), they are completely technically disjoint. First, all these results rely on non- standard block Lipschitz assumptions, which are not present in our work. Second, all of them leverage proximal gradient-style cyclic updates to carry out the analysis, which is inapplicable in our case for the cyclic updates on the dual side, as otherwise the method would not correspond to (shuffled) SGD, Finally, [27 43 utilize extrapolation steps, which would break the connection to shuffled SGD in our setting, while [1] relies on a gradient descent-type descent lemma, which is impossible to establish in our setting.
than even full gradient methods 4
19
26
26
40
48
established only recently [ 27
14

---

B Omitted Proofs From Section 2
In this section, we consider the general finite-sum setting where we assume that each component function is convex and smooth, and derive the refined analysis under this setting. Here focus on the smooth convex problems as prior work did [0 34], since smoothness essential to showing the advantage of shuffled SGD BI] over SGD, otherwise the rate of SGD is optimal. In particular, we study the general smooth convex finite-sum problem
min [(xx) = mERd
1 Σ f((m))
where each Si is convex and smooth.
P is equivalent to
min max MER" yERnd
[(x y) = 1
Σ ==1
(v',x) f(((()
Ex y) - > f1')
(PD)
where we slightly abuse the notation in this section and use y' E RRd to be the i-th elements of the vector y such that y (v',...,"")) E Rnn E Idy..., Id E RRnddd is the vertical
concatenation of identity matrices La Radd and St is the convex conjugate of defined by fa()) y' (y' xx) (zy). In the following, consider the mini-batch estimator of batch size b, and let ( E bd denote the vector comprised of the 7th bd elements y. For simplicity and without loss of generality, we assume that = bm for some positive integer
that (y ...... (")) )T Note that if choosing b = 1, our setting is the same as the ones in 330 34 Then have the primal-dual view of shuffled SGD scheme for general smooth convex minimization as in Alg. where E -Ta. Id...., Id] E Ruddd is the vertical concatenation of b identity matrices
Ia E Rdxd, Given the data permutation (k) {mi ..... } of [ni] at the k-th epoch, we (M) the same notation of d ( 2 (4) )T Rad Y= (y y )T gnd as in
previous sections except now each at y are d-dimensional subvectors. Further, we denote the
permuted smoothness constant matrices by A& diag(L (e)_ (....... 400 L ................................ L (n)
Rudxxnd and we use for Ind Rudxnd throughout this section.
New smoothness constants and comparisons. We first recall the new smoothness constants for any permutation æ of [ri). defined in Eq. (
ig
Iod(i-111 11t EE Iod 1od()-1))) A A//211 A//2 Ei
i max Lg
i = 5
A 1/2 Ei (di)) EE ((a))) 1/2
7 = max S11
where I (ai)
bj=bd(i-1)+1 Ij-
bdit
To compare ig and L = max:emm] Li, we make use of the Kronecker product with notation X defined by
An B
A B
A 6
AmaB
A
for two matrices A E Ruxn and B E BPxx, The following lemma states useful fact for the Kronecker product.
Lemma 3. For square matrices A and of sizes p and q and with eigenvalues d (i E (p)) and pj
(j [g]) respectively, the eigenvalues of A & B are Aapty for i [p]. E [g].
15

---

We now use the following chain of inequalities to compare Lg and L for any permutation т of [n]]
1
A1/2
I bdll
EE Ind(s-1)7) 1
mn
1/2 E E A 1/2
(L.1)) @ la
L I
1=1
where we define 4- = (v L Vigg the eigenvalues of Ia all equal 1, while the largest eigenvalue of L,t ||2|| Li, so the operator norm of (424) @ Ia is Σ L.
For (i), we use Lemma and notice that
To compare ig and L, we notice that
1/2 EE Th (as)) GGJEET (as) A E (aa)
E A ((s))
block diagonal matrix whose operator norm is the maximum of the operator norms its diagonal block submatrices, so we have
i
Pla AL 12
(m)
(as ((1d)) & Ia) (da)
= max [mm]
max
Loma-nt S L
iE [m b
Lemma for each submatrix L (0, (O. O, T
where for (i)
La and 1
Im ......0)" ()T Similar to the case of generalized linear models, the inequality is tight when b = 1 but be loose for other values of b.
Before proceeding the omitted proofs, first state the following standard definitions and first-order characterization of strong convexity, for completeness.
Definition 1. A function f Rdd > TR is said to be p-strongly convex with parameter μ O, ifr any x, E Rdd and any X E (0, 1):
s(Xx + (1 X)y) S Af(x) + + ())-() - ~ A)(la yyl..
Lemma 4. Let f Rdd +R RR be a continuous p-strongly convex function with > O. Then, for any x, y E Rd;
f(y) f(x) + (gx: x) | y 12.
where In E 0f(x), and 0f the subdifferential of f at æ.
We also include the following lemma on the variance bound under withhutt sampling, which is useful for our proof.
Lemma 5. Let B be the set of [B] b samples from [n), drawn without replacement and uniformly at random. Then, Vx E Rd.
n-
EB |1 Σ
V
[
bnn -
16

---

Proof. We first expand the square on the left-hand side, as follows
Es
Σ
-
Es
(V)(())
V/) V
82
E
Es
Σ
-V Vf)(2) vf(2))
- Vf
ja
Since the batch B is sampled uniformly and without replacement from [n)]. the probability that any pair (i,2") from [n]] with 1' in B is b(b-1] By the linearity of expectation, have
m]=-1]
Eg
Σ
(Vi(())
(f(()) V
Es
Σ
LrrEs (Vf((=) vf(²), (fr()) - vf(x))
Σ
EB
1iPEB (V/((>) V/(²). V/((=) - vs(()))
b(b 1)
Σ (V)(2) f=))), (a) vf(a)),
n(n 1)
i
where 1 is the indicator function such that ie if both i E B and is equal to otherwise. Hence, we obtain
EB
Σ
Vi(()) ((())1
b
iEB
6
Σ
(V/(zz)
VS(x)) + ,, -
bn(n
b-1
Σ (Vf(()) V vf(x)) + n
b(n E. Vf((=) vf(2)
bn(n - 1)
- b
E. [1 fix)) - V f(
b(n -11 1)
where (i) due to f Σ fi having the finite sum structure.
Now we provide the omitted proofs from Section 2
Lemma 6. Under Assumption for any ko E [K], the iterates { (0)m by Algorithm 7 satisfy
jm and (xx-1,1) 1m+1 generated
372
E <
1]
E
D6 - Ib xh-115-1 + yk
E U
)
22. Ib-15))
n2
i=1
1=1
(5)
2n
1yk
vxl1 A.
Vkl
2n
mk
y:
yz
11
A
2n
2k-1114 11.1,111
where Eg : Th "ap y-)
+
2m
b
x.
2n
x
xk-1
Proof.
We first note that based on Line of Alg.
we have
b
Ey (0) xx-12))
Σ
fi
(V')= = Σ
(
a (8')
(k)
1=1
1=l
17

---

Since the max problem defining yı: is separable, we have for b(i - 1) + S bi and i E [m]
V arg max y ERd
{
- -Sau) (10))
which leads to 1,-11 E 05 (1) (vr). Further, since each component function fj is 1 -strongly convex thus for b(i 1) + S S bi, we also have
L,
1 11 2/212 G. (oo((( 2 (Uf) + (0x- v%. 21 5
which leads to
L( v)
bi E
Eg Up ..
f (o2) j=b(1-1)+1
+
1 Σ
Ej Uk I xk-1.
==1
1=1
bi
E Vk Fk xx211.)
(1x())))) j=b(i-1)+1
f
+
Σ
Ep 1
1
t=1
1=1
U ll
1/
2n
Using the same argument, as a. E (y.)) for i E [rz], we have
(un 2 (un (Ix., va -Vi
1
11
2L _0,
Thus.
L( ya)
m
Eg Mr x.
(2)
n
j=b(i- 1)+1
m
EB
Uk
(7)
bi
(1) (grk)
+
1
yy
ya.k 1|
2n
j=b(i 1)+1
m
Fg
Uk
(4)
+
b ||ar
1.11
||a.
bi
Mag (v1t)
n
217
277
i=1
(i-1)++1
+
1y
k 11 --
2n
Using the updating scheme of 04-11541 and noticing that (f(x)) = is b. -trongly convex and minimized at #4-1,141, we have
E. u
( )x) +
2np x xx 1.11
b
E Ub
....)
+
|x=.- - -kk-1,i1
277
E,
yb (4)
o0k-1,1tt)
b
11.1. + ||06-1,141
b
| 12.11
277
2mp
18

---

which leads to
[(x.,; y.) 2 _
m
Eg yk 5 1
(0)
b
aa 1,++1 1,11
bi Σ
2771
b(2 1)+1
b
+
Σ
[k - 2x11² 1 - -xxx2 111) +
yo x1, 11 1lyk
2n77
2n
i=1
bi
b
Eg yh
|| 1,141 1,i1
Gas (2rk)
2///:
2=1
j b(a 13+1
+
b
[|:05 - xx11² 1 - x2.1 + 2n
y - yr Ax""
2n7j
Hence, combining the bounds C(okk v) and L(xxx. y.) and letting
b ||
b
E = My (C(xx, v) (()). +
x x.112
0 x..1?
2n
2n
we obtain
E
7/
E y 1, xk-1,
(5)
7k
E
71
i=1
1/k
Uxl 2
7k
y/: - ye
F2 1,+1 - 2,6-1,51
2n
2n
Av
2n 1=1
m
m
1]
Eb Vi
(8)
22
0b 1,1 1) +
7k
Eg
U
y
(5)
32 xk-1,
71
Y=1
?e
yy
1x1
0k
yy
2 1,++1 33-1,1113
2n
A.
2n
thus completing the proof.
We note that the first inner product term Ti th Σm E yk 2x xk-1,441 in Eq.
(i)
can
be cancelled by the last negative term b
2m E ||0 xx=1, ll therein, as precisely proved
in Lemma of Appendix C In the following subsections, continue analysis and handle the remaining terms in Eq. (5) according to different shuffling and derive the final complexity.
B.1 Random reshufflin/shufffe-onnee schemes
We introduce the following lemma to bound the second inner product term Ta (v y
E
Fz xk-1,; Lemma when there are random permutations.
Lemma 7. Under Assumptions and 2 for any le E [K], the iterates {
( Jm and f 1++1
generated by Algorithm 7 with uniformly random shuffling (RR/SO) satisfy
n
is
Th L 6) + b) 0
T
1i vo A
+
ya Iik 1k 2n
111 A.
+
(n - 1)
where To = Db Em=1
E (v)
2/ (0)) ( .x Fk x
19

---

Proof. First note that æx 11-1, Σラ= ( Bk-11))
2 Σド
Eg y
Thk E Ibd(i-1) so we have
7
Eb
(Uk -Yh ,,h"),
1K - x xR-
7h
E
(v)
3k #k-1d+1 - Fh- m7-115))
77
1=
E (2a)) - ya), E In(()-1))311)
bn
E
(88)) - yk), E ToTdals-- 10605-131(6 (yk - ya,k))
bn
1=1
k
E
(di yk), E Idd(i-1)tya.t
bn
For the term In we use Young's inequality with a to be set later and obtain
I =
The
E (1sj(02 - yk), E Iod(a-1)1 - -y+x))
bn
m
na
E ((d)( - yx)l12+
1)) y=,x)11
(6)
2bm
2bn
Further, notice that
n
E
Ihati- (y) 21
2bn
yyk
k²
Ind(i 1)1 EE Ina(i- 13t (y y=
2bn
1=1
n
m
(Y)
-,,,k)
Σ
ballt 1)t EE Ibd(t- (2)x - ya.k)
2bn
na
(Ml
(=,k))
A
1/2 A
1/2
1y Inals 1/22 1/2
1/2 (Br 1/
1/21
y..))
2bn
n
A
1/2
I balti 1)t
EE Ind(i 111 A 1/2 1/2 1111k
v. 1
2bn
1lyk
y 11 A.
2b
where for the last inequality we use bound
inequality. Using the same argument, we can
E [(a -yx]1 <
mh 2bna
A
1/2
Σ
(da EET ((as) A | yk A
2bn
1=1
12 2ncex
i (2 11 1220011ux
yk 1 A
(8)
Thus, combining 6 18 and choosing
2n 8 ( obtain
The mi
I
n
y - 2
+ 4n
7k
yk 112 A
b
20

---

For the term In, we again apply Young's inequality with 3 > 0 to be set later and obtain
12
I (ds)(
-ys), E 1
bn
T%. 3
m
"
m
1yt
E
((x))
yk
2bm
2mm
m 8
L (k4)
E
11 Bull??
2bm
2nB
Choosing 3 2mp, T and using the fact that 1. x(k)
L, we have
I2
E
16) yo,k +
yk 1l =
bn
4n
Hence, combining the above two estimates with = n//, we have
3 L To S
M (1))
L
bn Σ E Ind 1y
((k)
1
TE 1
B2
2n
First, consider the RR scheme. Taking conditional expectation both sides w.r.t. the randomness up to but not including k-th epoch, we have
L bn
Eg [T2]
ER
LE
Ibd(i-1)1 1)1 Vo,l1
n L
Th
Eg
722
y=, A,
2n
11
y
A.
For the first term, since the only randomness comes from the permutation (k), we can proceed as in the proof of Lemma and obtain
n L bn
m i bn
E
E (20
E
1=1
np. L
m
E' Lod (ad(i-1) Yr.k
b(i -1 (k)
bn
12 b(i - 1)
i=1
(6))
b(i - 1)
Σ (n b(i 1))²
(n b(i 1)) - o
bn
i=1
n/ L (n - (n n + b)
6b 1) o.
where we use the linearity of expectation for (1), and (ii) is due to Lemma 5 and the definition of = Σ [Vf(( )1 >i ||? Then taking expectation w.r.t. randomness on both
sides, we obtain
Th 1 11)
m i. - b) + bb) o.
T
<
Ukk v +
2n Uuy y4 211
+ 66 1)
62
that the above argument for bounding the term Iba y also applies to the SO scheme, in which case there is only random permutation the very beginning that induces the randomness.
Finally, RL ba
we
remark
Ex
Σm m
We state the final convergence rate and complexity the following theorem and provide the proof for completeness.
21

---

Theorem 4. Under Assumptions and if ?) S
b
and HK = Ex= The the output
'.,m (k) kK of Algorithml 7 with uniformly random (RR/SO) shuffling satisfies
"I 2
K
in (b) 0
[[Hx( - [(xx))) - 2n 200 - v. 112
6b
As a consequence, for any c > O, there exists a choice of a constant step size Ths = 1l for which [[j(@k) f(x.)) S e after ( Loio wo 20-- queries.
V (n-bb(n++] Vniso. Ro -o---11. gradient
m(n-1)
672
Proof. Combining the bounds in Lemma 10 and 2 and plugging them into Eq.
5 we obtain
L
L200
Ln b)(n b)
E[EN] s
E
(2)
T
Ily: yu A.
+
6 1) o²
62
2n
menls
Li 62
For the stepsize Th such that 77 I
we have
S 0, thus Wk 2n
ny /222 (k)) 12,0)"
LL b)( + b) 66² - 1)
E|E,|
Using our definition of E and telescoping from k to K, we have
K
my Gap" (ork; y.)] s
-1x. xol12 Ell
b
b x.
xK
Li b)( b) o
2n
2n
6b2 - 1)
Noticing that C(x,0) v) is convex in x for fixed v. have Gap"(#k: y-) Ek=1 mh Gap y.)/HK. where øx Et to
K
K
ma
HK and HK Eh T which leads
b 11000
L (n b)(n + b) o
E
Gap (#x; w.)
s
m..12 +
2n
6b (n - 1)
Further choosing v = yax we obtain
b xx
K
m L b) + b) 6b2(n (n -
E[Hx (FFE)))())-(
f(x)))
xDp
112
(9)
2n
662
To analyze the individual gradient oracle complexity, we choose constant stepsizes 1) S then Eq. 9 will become
av2isis
17 L - b) o².
E[f(xk) f(x)))
2nnk ||000 x1112 +
6b² 1)
Without loss of generality, we assume that o n, otherwise the method and its analysis reduce (full) gradient descent. We consider the following two cases:
"Small K" case: if nV2iiats < 30 1/3 n(n bi we have
E[f(Ex) - -x(x))
b
i b)(n
100
x..12
0
2nnK
6 -111 1)
(n b)(n + b) 1/3 (1.)1/33 2/3 |aro - x. ///
||000 - x.112 + 2
V2K
n²(n -
31/3
22

---

36 (n-1n 10 m. 12
1/3
"Large K" case: if
have
nv n
L 6) + b)
B[f(xx)- - f(xx)] - 2n7k 1
x. 22.12
0²
6b2 (n - 1)
(n b)(n + 6))
1/3 (13)
1/3 0 2/3 2 112 4/3
nn - 1)
K2/3
Combining these two cases by setting 1 min
h
30 22 112
1/3
we obtain
nnviiii'
m(n=b][n+t)L>ke
(m- (n-bb(n+b)
(19)2/3 0.
2/3
20 W. 12
[( - [(ar.)) <
100 x2.12 +
v2K
n² (n
31/3
Hence, to guarantee [[)((x) f(x.)) S for e > 0, the total number of individual gradient evaluations will be
nv 29 30
V. 112
(n- 6) + b) 1/2 2 ||200 x.1.
n K 2 max
71
///2
as claimed.
B.2 Incremental gradient descent (IG)
In this subsection, we provide the convergence results for incremental gradient descent which does not involve random permutations. We first prove the technical lemma below to bound the term (4)
Ta Σー E (0k yk _ a TR-1,i in Eq. (5) of Lemma
Lemma 8. For any l E [K]. the iterates {yk pm and (. m++1 generated by Algorithm with fixed data ordering satisfy
T2 <
Th ba
Lg
v-llā-1 +
|1
2n
(10)
n
n
6)2 igo
min
ig
11.
12
112
Proof. Proceeding as in the proof of Lemma 7 we have
Tk
E (5)
y/ ab xb-
(1)
7k
ET (v()) -3 -, Σ
C #k-1.i+1 -xx-15)
1=1
v
E I [ai)( v yk), E Ina(e-1191))
bn
1=1
The
[da (v yk), E Todis 115 11 (yk - y-))
bn
T
E I (di) (v yk), E 1nd(i-1113.).
bn
23

---

For both terms I and 22, we apply Young's s inequality with = 27 Lg and obtain
m
I, S
E
Iod((- (yr - y-)112 +
E (ds)( - yx)112
2bm
2bna
iin T.01l3k - y-112-1 +
The
i.g. v
yı: 112
2b²
2na
m Tg 1-gllyx
-a1l2 1 +
7h
10 yı
1 1.
(11)
B2
4n
and
Th a
m
m
I2 -
11112112 E 11 +
(aa)((
yx)11
2b
2bna
! 0
2 m
E bod( 11)
+
Wek 2ncx
Lg
3/4k
11
2bm
mik La
E Iod(t- 1)1 1/
Th yı
1|0
112-1
(12)
nb
An
E [nd(i 1)1 v. no larger than either 2h L y 13
We now show that the term or 1i (n=²"))²² i.ga.. This is trivial when n as E Tu = E.= ya = O. When < n, to show the former one, we have
m2b
6²
m
m
E Tod(s 1y 1od( 1.1
1/2
Σ
I Tod(t-1) 1)f EE Tod(e- A/2 1
n² i Lgllea -
=mn f.g y. 112-1
To prove the latter one, we notice that
172
m
E Lbd 11)
Σ
3
Σ
Σ
j=b(i-
1)+1
j=bi+1
j=bi+1
m-- 1
y
using the fact that > n
yd = 0. Then using Young's inequality we obtain
m
bi
2
1=1
s 6(mm 1)
1
1
bi
= b(m 1)
(m - 1)1l2211
1=1 f=b(1 1)+1
(m
S b(m 1)2
Further noticing that
Σ i=1
(m-
1 113
< EL 1| !fll? no? we have
g
2ig
"f - -b}²
7
U
E
1y 3*
b(m 1)2n0
0%
nb
nb
b2
i=1
24

---

The same bound also captures the case b and leads to
mh
0
m
E
bbd( S min Th
ig
y- 11
n 6)
T.g0? 2 .5.
(13)
nnb
b²
Hence, combining Eq.
13
we obtain
I2 S
n
ig
v.113
7h
10
11112
8²
2n
T
m b)2
+
min
62 Lio0?
b2
which finishes the proof.
We are now ready to state our convergence results for IGD in the following theorem, with its proof provided for completeness.
Theorem 5. Under Assumptions and if me S
and HK Ek ak the output &. of "V2igg
Algorithm 7 with a fixed permutation satisfies
H (f((k) - f(xx)) S 2n
[0 - x. 113
+
K
min
The T2 2
i
menn - b)?
igo?
b2
1=1
As a consequence, for any > 0, there exists a choice of a constant step size The = such that
f(ix) f(x.) S e after 0 nV 1212 - gradient queries.
a.
min (Vnigigllv.
/ig..
1|a00 aito-m.. = 112
3/2
Proof. Combining the bounds in Lemma 10 and 8 and plugging them into Eq. 5 in Lemma without random permutations, we have
ninigi
1 6²
vi(n - b)2
Eg <
12112 + min
Lg
112-1.
L Lg
62
2n
6²
oinigig
T7 S
we have
O, thus
" n/2igig"
62
2n
& S min
Th {
112-1, m (n b)2
Lgo??
62
6²
Using the definition of & and telescoping from ht = 1 to K, we obtain
K
Th MaGap" (x y=) <
x.
xxl12
2n
2n
min
T 12
i
1 b)2
i
Noticing that L(x, v) is convex w.r.t. we have Gap" (# y.)
k= Mh Gap" (I y.)/ Hx.
where ēK-- = Ek= mxok// HI and HK = Ek= Mek so we obtain
Hg Gap (# <
2n
b
||000 xx.12
+
min
Th 1
b2
1,
Th b)2
62
18
L
Further choosing v yox we obtain
b
K
me b)2
(x(f((k) f(xx)) <
xo x
113
min
Lgggll +
Lgo 21
2n
ba
62
(14)
25

---

To analyze the individual gradient oracle complexity, we choose constant stepsizes and assume b <, without loss of generality, then Eq.
S
6
n22ig28
(14)
becomes
b
n
(1 - 6)2
f(0x) - (xx)) S
2nm 11000 m.112 +
min
Lg
A-1
Lgo2)
822
B2
When 1gl1y~112 I (n-b)² of we set 1 = min sider the following two possible cases:
8 20 a.
1/31 )r}
and con-
"y 22
"Small K" case: if
6 11 Ro
2.11
1/3
have
n2/2i.gg s
2n2
1/8/-
b
n
f(0x)-f(er
x.112
L8
2nnK
62
(LgD 1/3
133
1|
|000
xx.12 2/3 1/3
ID
xz
112
+
V2K
13
"Large K" case: if
671 20 a.
13
1/3
5
b
we have
2nn 22.222
11
b
72n
f(Øx)- - f(xx)( S
ID - -2+12 +
Lg 11.1111
2nmK
B2
2 (L81g)
1/3
|19.
2///3
120 - x.112 4/3
1/3
K2/3
Combining these two cases, we have
i ig
21/ (ig18)
1/3
yy 19-13
1//3//
200
xx 11/3
f((x) - f(z.) S
|00 - x.112+
v2K
n
K32333
Hence, to guarantee B[f(2x) f(x.)] S for e > 0, the total number of required individual gradient evaluations will be
n
2 2ig xo xx.12 4n 1/2 1/2 (
1/2
1y 1
2D -
x. 11
nk > max
(15)
6/2
When (n-b)² 6)2 o2 Lggl y. 11 we 1) min
8- a. 11
1/3
and consider
n
nn/2ige8'
2n(n (ainn-)3Tggoo
the two cases as below:
63 601 1/3
"Small K" case: if
we have
n2/2188
(2((nbb)igKo.
( b)
f(xx) (0(x)(((=))))))))))))(()))))--
LD - x.113 113 +
2nnK
6²
Lgig
(n 2)2/3 (
2/
2/3
120
x. x2112 4/3
|
1..13
+
V2K
22/3 K2/3
6. 10 x.
1/3
"Large K" case: if =
<
we have
b
r - 6)2
[(xx) - f(xra) S
| x. 11
igo
2n K
b2
21/3 (n
(To0)1333
2/3
x. 11
4/3
K2/3
26

---

Combining these two cases, we obtain
Lii0
21/3(n
(T,0)///// 1|20 - n. 11//
f(0x)- - f((x))
120
x.122
v2K
k22/3
To guarantee B(f(dx)= fxx))] S for 0, the total number of required individual gradient evaluations will be
m 22g x. 4(n (){) (/2g))/22000
Co xz 1
nk max
(16)
2//2
Combining Eq.
15 and Eq.
16... we finally have
nk 2 m 2 2o x.11
An 1/2 ((gTg)
11
=x,1.
4(n
()
250
x
min
r3/2
6//2
thus finishing the proof.
C Omitted Proofs for Smooth Convex Settting From Section 3
Before proceeding to the omitted proofs for the smooth convex settings finite-sum with linear predictors, we first recall its primal-dual reformulation, then state the specialized version of a primal- dual shuffled SGD algorithm in Algorithm [ Recall that (PL admits explicit reformulation using convex conjugates of f4:
n
1 a Σ (a xy - (z)))
min max (C(x,y) = (Ax, y) Σ 4400
(PL-PD)
aeRd yEkn
where v' - arg max, y' E3 (y'a, _ x (gy") (different from the general smooth convex finite-sum settings in Section 2 and Appendix B.. Further, for notational convenience, we assume that the partition is ordered, the sense that for 1 < < j m, maxiess min i' We denote by ( the subvector y E R" indexed by the elements of 81, and by A the submatrix obtained from A E 1nd by selecting the rows indexed by S).
Based on the formulation PL-PDD. we view shuffled SGD as a primal-dus method with block coordinate updates on the dual side, as summarized in Algorithm 2 for completeness. To see the cquivalence, in i-th inner iteration of k-th epoch, first update the i-th block y IR of the dual vector W E IR" based on Ø;- 1, as in Line 6. Since the dual update has decomposable structure, this maximization step corresponds to computing the (sub)gradients {E (a
(k) 1.i for the batch of individual losses indexed by {TT) J)=b(--1)-1 Then in Line 7, perform a minimization step using Dg to compute Fk-1,5+1 on the primal side. Combining these two steps, we have 18-1,i+1 3 The bi -i El (a) (a TT,, tk -P)- ns which is exactly the original primal shuffled SGD updating scheme.
(6)
" my
"This without loss of generality, as it be achieved by reordering the rows in the data matrix.
27

---

Algorithm 2 Shuffled SGD (Primal-Dual View)
1: Input: Initial point mg E IRd batch size b > 0, step size {m²} 0, number of epochs K > 0
2: for k= to K do
3: Generate any permutation ((k) of [n] (either deterministic or random)
4: 11-1,1 -k-1
5: for 1 to do
1,1 Ej=1 (0) (v')} 6: Vk arg maxxERt {V x (8)
1)+1-1)+
7: 22-1,i41 = arg mEn {yk A (6) x +
in 1
22 1, 1,01| 2
2716
8: end for
(1)
(2)
km)) T
9: Ik = 1k-1, yk = (y's 3k yk
10: end for
11:
Return: &K Ex= TR/ Σk=
K
C.1 Omitted Proofs for the Random Reshufling/Shufftl-Onnee Schemes
Lemma 9. Given {yk and 1.:=1, generated by Algorithm for k E [K], let Eg ==
b Ji=l
Th Gap" (zk: y-)
x
xxl12 1|
zk-1 112- If Assumption holds, then
2n
m
7
(
(4)
Ek
yk
A (xtk
71
17
kk
(4)
yx
(1)
T
A (xt 1.-
i=1
(17)
1 A-¹
ykk yo xl
2n
2n
| 2b 12-1.411122
2n
Proof. By Line 6 in Alg. 2 we have y
(9)
arg max yER' {uT (
xx-1,
-E
E
(4')}
forie E [m]] Notice that since
b (4')
y A F'
Σ
y (x)
L6 1,2 - 8 (2)
(88))
xb(1-1)+3
76(1-1)+3
j=1
1=1
is separable, we have V = arg yER (ya T (1) zk
E- (
(b)} for b(i 1) + 15 < bi, thus
(h 1, E 0e* (v) (v1)) Since Ej is -tronggy convex by Assumption 3 then by Lemma 4 we
obtain for bii 1) + 1 S < bi ( (v%) > ns (vrt) a us rh- 1. v1) + 21, 00)
(0% vi)
21,
which leads to
m
bi
m
C( v)
Uk
(G) (1)
A
0k-14
Uk
(6)
A
(1)
(xx xk-1,
11
7
j=b(i-1)+1
m
bi
m
<
yk
(T)
A (4)
xk-1,1
(0) (mk
(
A
(Ik
xk-1,5)
12
72
j=b(i 1)+1
|
11
(18)
2n
A
28

---

Using the same argument for L(a.. v.) as aj xx E (f)(v!) for j E [nn,, we have
bi
C(x.:
yook
(
1)+1
1
yk
(1)
( (vb))
+
1
31
(19)
2n
j=bli 1)+1
Adding and substracting the term
m
||0, x4 1 12 on the R.H.S. of Eq.
19
we obtain
2nina
i=1
C(a,, y.) 2
m
yk
T
A/
A x. +
b ||,,, Fh 1
gav
(vr))
27/
m
j=b 1)+1
b
x.
3k 1,xl2
+
1y -y..kll V
2n07k
2n
By Line 7 of Alg. ther noticing that 0x (x) == yk A x
we have Fk 1,541 = arg minl
( ( A
x + 2 || 2 mm-111 Fur-
T (b)
b
||=
xb- is 7/
-strongly convex w.r.t. x and
27p
Voh (xx-1.41)) = 0, we have
kk (xx) 2 0x (2x-
+
1| 22-1.44112.
2171
which leads to
bi
C(x.,
2
yk A xx 1.141.141 +
(i)
b
|00
1,641
1,i11
27/k
1=1
jmm b( - 1)+11
b
1
1,.1, (1 2K- 11-,,,++112 ||300
+
yy
y l|ا22
2n0Tjk
2n
bi
x
yk
(
0x-111+1 A
+
b
||00 - xx-1,
Σ
Ego ((rl)
n
2771
1)+111)+1
b
1
|| Ix
1.12
|| xx112 +
1 y=,k A,
(20)
2nm
2n7
2n
where we telescope from i = to m for the term Σm (I|ar- LK 14-1,5-118 - ||,00.
.K 1 12) and
use the definitions that ws = 3g 1m and 0x-1 = -1- for (i).
Combining the bounds from Eq. (88) and Eq. 20) and denoting
b x 2x
b
Ex : mi (C(Es, v) L(xx. vo)) + 2n
1
||,, 22-1
2n
we obtain
m
m
Eg
7
(
A (Ik-1,5 - Db xk-1,
(5)
1]k
Uk
(3)
A (xx- - -0k-1,)
72
1=1
f=1
M
b
m
2n
131k
Uh
AA
2n
1yk
A
2n
0k-1. 1. 2b 1,441,11
yk
(+)T
(2) (2x
C# xk-1,))1)
+
7k
k
(i)
yk
(8)
T
b
( (xx x22
7
i=1
i=1
77
12
The
1y
y
1/
A
b
| - 1 112
2m
2n
2m
thus completing the proof.
29

---

Lemma 10. For any ls E [K]. the iterates (1/g
mm
Ji=1 and ( b in Algorithm 2 saatisyy
T 1k-11.1 2k 1,44
1 2x
we have A (T) (6) (
Proof. By Line in Alg.
yk
T6- 1b-1.) Further noticing that
Kk 18111
2==i+1 (k-11 1, 2k-1, we obtain
T1 = 7
(O)
(x) 22-1,1+)
6
F 1,2 1,
2k-1, 1.++1)
1=1
j=i+1
b
b
m
1k 3g x1+1))))
2n
2n
thus completing the proof.
mm) Lemma 11. Under Assumption for any k [K], the iterates {yr Fe and f 1.
generated by Algorithm Q with uniorrmly random shuffling satisfy
Th n (1)) L,(
LLinn b)(n + b) yk 11 A 1 + 1k
7k
E T2l
<
ykk y- A2
+
62
2n
66 -
Proof. By Line 7 in Alg. 2 we have - 1,141 =
Dk
(T) (
Using the definition of Ist
b
for 0 Sj S 1 in Section 1 obtain
m
7Tk
Σ
GTT
(1)
T]k A A
3k 1k-
Ok-11 1 2h 2k-1.j+1)
yk
b
j=1
Also, we have A k these two observations, we have
(T yk (0)
(o
A (1) -yk) by the definition of ((s) in Section
Combining
m
7]
(1)) T A (xx - xk-1,;)
Ta
U
n
VI
2
A. To(1-1119 A ( -y:))
bn
Th
[A Io(i INGi-1((11 - vo.x). AT ((i)(1s Bn))
(21)
bn
v
(A I0 A (1) y²))
(22)
bn
where make decomposition w.r.t. y in (i). For the first term in Eq. (1I). Young's inequality for > 0 and have
2
A 16(1- - Br.k), A (1) yx))
bn
(23)
Tha
T
A 1666--11116 - 30,x)113
m
A (1))(k-9))))) -
2lm
2bna
30

---

Expanding the squares and rearranging the terms in Eq.
23 we have
m a
A I Joci-
1y1 (yk -v,,)
2bn
1=1
(y):
yz,k)) 1b(e-191 Ax Io(i-1)1 - yn,k)
26n 1=1
aa
m k),k)
(y)
M 1o(c-1)1 (yy yo,u)
(24)
2bm
aha yyk
1/2 1/2
10(t11)1 A 1o(c-1))) A 1/2 Ax 1/2 1/2 yo.k))
yo.k)
2bn
( a
()--))AA444 A Loci n1
A
1/2
Ily y. 12l1
2bm
k
where we use Cauchy-Schwarz inequality for (i). Using similar argument, we also have
17
m
I (o
A
1/2
An) (1)
//2 1lu yv vall12,
2bna
2bna
By the definitions of intes and Lys,, and choosing a = 21/, L,) in Eq. (23 we obtain
m
Al (3) v),,,, A (10)(0 - yxk)
bn
(25)
T
(x)))
L,000
yk V.
11 11112=1
62
4n
For the second term in Eq.
22
we apply Young's inequality with 3 and proceed as above:
m
A 16(- Al (1) - yk))
bn
3
A 1(1-1))t 11.
v
Σ
A (0) (v: 2xx)
2bm
2bm/3
2
2
A T Io(i-1)19-41
mi
T.
00,000
yk -
2dm
2n,3
1=1
Noticing that L,, < L, we choose 3 = 21p1 L and obtain
mh
A 10(i-1)1Be.d: AT LOl
ynh)
bm
(26)
mh. i
A (00-1)-aa.113
7k
|| - yn -
nb
4n
1=1
Combining Eq.
25 and Eq. (26). we have
mi (1)) _,000
To
A I 1o 1..
y- 11
1 3mll2
(27)
nbb
62
2n
We first assume the RR scheme. Taking conditional expectation w.r.t. the randomness up but not including k-th epoch, we have
L
Eg [T2 <
EE
|A Iu 13-
nb
1=1
Th
Li(
ER
62
V-
Am
2n
1
y 1 ||
31

---

For the first term permutation x (8)_ In this case, each term A, 16 can be considered as a sum of a batch sampled without replacement from (y'az) while Σ== y'a, a. is the minimizer, then can use Lemma and obtain
ni F. Ex
Ex= || D(6 1y1 Vo. v13.. the only randomness is from the random
nb
'/1 T. 15
m
T
m
| Jo 1)1 Vv,
(
E B [|| 10 [13]
nab
nb
7 L
|| A 10(i-1)t
n b(i 1) 1
(n b(i - 1))
" ExIs)
nb
b(i - 1)
Σ
(n bii - 1))
(n b(i 1)) (n 0.
nb 1=1
n Ln (n + b) 6b² (n 1)
0².
where (i) is due to the linearity of expectation, and we use our definition o. # E, [llyaaa Il for (ii). Taking expectation w.r.t. all the randomness both sides and using the law of total expectation, we obtain
L I
|] + Liinn - 6) + +b) o.
T < E
yk
y- A,
T 2n
y 1x A
6
66 1)
For the SO scheme, since there is only one random permutation generated at the very beginning. we can take expectation w.r.t. all the randomness on both sides of 27). and the randomness for the 2 is only from the initial random permutation. So the above argument still applies to this case, and we complete the proof.
term n2L E nb
||]] E
Theorem 2. Under Assumptions 3 Baddl ih " an) ,00
and H Ek= Tk then the
output æg of Alg. Tith uniformly random (RR/SO) shuffling satisfies
Linn ()(n b)
([HK( - [(x)))) S
2n | x 12
0 6b2(n - 1)
As result. given 0, there exists constant step size m n such that Elf f(x.)) )1 S
after O V.i.la a. (m=+))+b)) v VnLa.llan m.113 individual gradient queries.
m(n-1)
2/2
Proof. Combining the bounds in Lemma 10 and II and plugging them into Eq. we obtain
ninLy Lg0s)
m L(n 6)(n + 6) 02 6b
B[EN] < E
Th 2n
|
y- 12
12
For the stepsize 77 such that 77 I
b
we have 6
< 0, thus n
n2/2L /222,,00 Lسn
2n
(m (a--bj b)(n+ +b
E[Ex] <
o².
66² -
Noticing that & mn Gap (ark y.) + b 1|,. 2x112 2n ||,r. k to K, we have
0 2a-1 and telescoping from
2n
K L bb)( + b) 0² 6b (n - 1)
E
m Gap" (IL. y.)
S
b
xx_ xoll3
b E
Ella, x<
2n
2n
32

---

Noticing that L(x,0) v) is convex w.r.t we have Gap"(@x: y=) S k= mh Gap"a"( y.) HK.
K where ØK= k= Tk H and H - Me which leads to
K
T LL - ([((m-)(n++)) 0
I
Hx ( v.)] S
1:00
a.112
2n
6b2 (n (0-1) 1)
A=1
Further choosing yax: obtain
K
m L b) +b) 6b2 (11 - 1) 0..
Bi - -(x))))))))))]]])))))))))))))))) -
200
- x.
(28)
2n
To analyze the individual gradient oracle complexity, we choose constant stepsizes 1) S n n
then
Eq. 28
will become
b [[f(xx) f(xx)) 2nnk ||000 x.12+
(n 6) + b) 6n 1) o².
Without loss of generality, assume that + n, otherwise the method and its analysis reduce to (full) gradient descent. We consider the following two cases:
36 (n-1)) 20 13 1/3
"Small K"" case: if
we have
nV
in 6) b)
-[ [(xx))]
100 x.113 1/3
0
2mn
6b2 -1)
LL
1 (n- b) (n-b)(n + +b) 1/3 1/ 2/3 |
F. 3..12
<
x.
+
/2K
n2(n
31/3
"Large K" case: if = 30 [n || 11
1.13
1/3
<
we have
n(z=b)(ab))LKoo
nV2LL
b
i b)
E[f(#k) f(x.)) -
x.. 112
0x
2nT
612 - 1)
s (n-1) b)(n +b) 1/3 f,1/3 0 2/3
a00 x2.112 4/3
n (
32/3
(n-1) -0 1/3
Combining these cases by setting 1) min
Lnvel
m(n=bj(n+ j. we obtain
V.T.
- (n (1)))())-+++)
(n - ()(n + +b) n
1/3 f,1/3
2/3 a00 - x. 11
4/3
- -
x..12 +
/2K
31/3
Hence, to guarantee B[f(ix) evaluations will be
f(x.)) S for > 0, the total number of individual gradient
nv 2T æ - 22.1. 11 - b)(n b) 1/2 2/223/2,00 1/12 0. | x. 11
(m-b)(n
nk 2 max
3//2
as claimed.
C.2 Omitted Proofs for Incremental Gradient Descenet
We now provide the proof for convergence of IGD in the smooth convex settings. We first prove the following technical lemma, which bounds the inner product term To Σm (vl))
yk (0) A ( (xt xk-1.)) without random permutations involved.
33

---

Lemma 12. For any & E [K] the iterates (01 " and 1 1 with fixed data ordering satisfy
generated by Algorithm
T2 -
Th n LoLolleA -- +
7k
1100 Ba.l 31-12-1
b²
2n
(29)
Th
11 bij Lno??
+ min
b²
b²
Proof. Proceeding as in Lemma
11 we have
= 7
(v() (6) T ) A - 1x-1,1)
T2
1=1
Th
m
( A T0(3-11 A [0s)(v - -yk))
bn
(AT To (1) vo),A A [(0 A
-yk))
(30)
bn
(AT I 11 A (0) (ot))
(31)
on
For both terms in Eq. (30) and Eq.
31 we use Young's inequality for Lm > 0 and proceed
as in Eq. 24 to obtain
113
A 101-11)1 y.), A A [0 9n))
A T To(--1) -y0)11++ +
m
|A (0) (1)-))12
2bn
2bna
t=1
nana
in 11y:
1.112-1
Mi
i ||011
yk 11
2b
2na
m
LoLol
3yk
- yz 11
+
Th
|| yı 11a
(32)
62
4n
and
2
A I 16(--1) 1)t Yes A L()(v - yn))
bn
A T (((--1)1-113
+
mh
A
(v)(v - y
2lm
2bn
1m1
A T 100-11111111
Wh
Tool:0 yy 1
2bm
2na
nie To
||A In(--1)2a113
1|e
ye 11
(33)
nb
4n
where again we used a = 277 L.. We then prove the term veLo Σm || To 112 in Eq.
33
is no larger than the minimum of -i LoLooly--11 and (n- Loo Note that when b
8
have AT To 0, so this term disappears. When n, the former one can be derived in Eq. (4). which gives
m
m
T IGG
1
1)
1.11
1235
1/2
Σ
Io(3-197 AA IN ) A122| 11 112 = mnLo 1y- 12-
2
Lo yz 1
b
34

---

For the latter one, we notice that
A T 10
Σ
ya
==1
j=b
1)+1
y agj
j=bi+1
m-1
Σ
Σ
y
2
j=bi+1
==1
by using the fact that
Σy=1 y:a;
0. Using Young's inequality, we have
bi
bi
Σ
bi
y
12
1=1
j=1
bi
S 6(m
1)
==1
m
bi
6(m 1)
(m - -))laa,1
j=b(ā 1)+1
(m
1ib
S b(m 1)²
Σ
y l22
By the definition that o² obtain 1/
1 Σド= ygaa,13 and Σm
(m-1)M 1yya 113 Eソ= 1yda,113 = =no?, we
Tmo A 11
nhe To b(m 1)?0²
TTe(1 b)²
1135
Loo?
(34)
nb
ba
Note that the bound in Eq. descent, so we have
34
equals to zero when b = which recovers the case of full gradient
Lo nb
n b2
m b)2
A bu- 11 S min
T.
T002
(35)
822
Combining Eq.
32
35
we obtain
Th Ta <
Lo yk
1-1
+
7/k
+ min |/0 1
T
n
f
1olly.111
Thlnn - -)2
12
2n
b2
52
thus finishing the proof.
Theorem 6. Under Assumptions and im <
and H
-mmm mi the output k of
bo
Alg. 2 with a fixed permutation sanssfis
b ( f(x)))
n 12
me(n - 6)2
1:000 x.113
min
Lotol AoLolly.1 11111111111111
Lo0
2n
As a consequence, given > 0, there exists constant step size
such that
f((x) f(x..) S after the number of gradient queries bounded by o ny Lotollao--a - x.11 min Valooollu 11 (n- b) / Loo. ||=00 - æ. 11
372
35

---

Proof. Proceeding as in Lemmas 9 and
10,
but without random permutations, we have
T72
Ek
7
k:
( A A (20k-
(2x
2h 1,441
Th
yk
(6)
A (9)
(3
2k-1,2)
n
b
1/k
2/
11
1-11ā-1
[k
22 12--1.41113
2n
2n
2n
i=1
1k
(v)))
yk
(2))
A k
17k
y/
Th
3
y 14.12-1- (36)
2n
2n
Using the bound in Lemma Io
12
and applying Eq. (2
into Eq. (36). we obtain
E 1
1
1=11 + min m
Loto 18 12-1,
n2 n2(n-bb) b)2
Loo??
62
2n
62
6²
If 77 I
h
we have
Th noo
U2 - 0, thus 2m
nhn 12
(n b)2
& < min
Lo Lo 11
82 E
Noticing that & mn Gap (ark: y.) k to K, we have
2n 1|ar. 2xx11
in b11,
2 0k 113 and telescoping from
K
mh Gap (2)2
1=1
<
xx,
xol12
2n 1x,
x
1
K
min
m b2
Lo
10113 1, =.o
nh b)2
2n
6²
k=1
Noticing that L(xr, v) is convex W.r.t. æ. we have Gap (áx y.) S Ek= m Gap (ark: yo)l HK.
where kk- = > 1 TR Hx and HK- = Σx= Me. so we obtain
Hg Gap" I
b
Do x.
min
T 62
Lo Lo y. 1121,
vi b)
Loo
2n
8²
Further choosing v = yäx: we obtain
K
me(n - b)2
Hx(f((k) - f(xx)) S
x. 112
min
n 62
L 1
[oo?}
2n
b2
(37)
To analyze the individual gradient oracle complexity, we choose constant stepsizes 17 S and assume b < n without loss of generality, then Eq.
22ooo
(37) becomes
f(xx) - f(x.) <
2nnK |00 x. x.112 + min
b
{
n"n B2
Lo Moollll11
17 - 6)2
Look}
b2
When Lolly-112 112 (n-b)²
02, we set 17 min
6a 200 w 18
1/3
and con-
2n
Kllk. 1 1
sider the following two possible cases:
8 21
1/3
"Small K"' case: 17 nV22lgh
we have
2n Lo
11212
f(ēk) f(xx)) <
12:00 - xx.112
LoLool
210R
12
1
1/3
///31//3
1
11
11 ænn x. 22.1///3 4/3
2/3
<
1000
x..13
V2K
22/3 1/3/322/ 2/3
36

---

80 11 ma w.11
1/3
"Large K" case: if
have
2n Lo
Look
19-11
12
b
f(tk)- - f(xx)= S 2nnK
1D0 - xz
+
b²
2 2 1 Lap
1/3 1/3
F. 1.112 n²/3k 2/3
1- 1 ||:00
4/3
n
Combining these two cases, we have
LoLo
21/3f/1/31
y- 2 a0
T= 1111
f(xx) v
100 - -xa12++
v2K
K22333/3
Hence, to guarantee [[f(kx) f(x,)) S for > 0, the total number of individual gradient
evaluations will be
nV 2LoLo 2000 x.11 4n Lo 1/2
y- llA
1
x- 11
k > max
(38)
6
3/2
When (n-b)² o. < Lollu.112 we set min
b
1 x.
1/3
and consider
nn/22
2n(n b)a Loko?
the cases as below:
6 1011 w.
1/3
"Small K" case: if nV/2bot
we have
2m(n-b)22
b
(n b)
f f(xx) s
200 -xx112-
Luo
-
2nn
v Lo
(n (n- - 3 2/3
1
x.112 1/3
<
10000
xx
V2K
2//3 K2/33
( 10 22
1/3
"Large K" case: if 7
we have
S3((n-b)=Top
22
1f2
b)2
f(0x) f(x.)= 5 2nn 200 x, 11
20
62
2 (n b)2/3 12
2/3
4/3
0+
x
xx
/2/3K2/3
Combining these two cases, we obtain
f(ēk) - f(x.) < VioLo
21/3 (n b2)2/33 10/2///1/1
F1/302/3
2/3
DD x. 112////
120 x1112
V2K
n2/3
To guarantee E[f(#x) - f(x,)) )1 S for 0, the total number of individual gradient evaluations
will
nk > max n 2L Lo Lo x.1
4(n b) o æ x |
(39)
3/2
Combining Eq. 38 and Eq.
39 we finally have
nk > nv 2T Lo mo 2.11
1/2 1/2 11/2
y-
A
x. 11
4(n - b) o. 800 x. 11
+ min
3/2
3/2
thus finishing the proof.
37

---

D Omitted Proofs for Non-Smooth Convex Setting From Section 3
Before prove Theorem X in convex Lipschitz settings, for completeness, first recall the following standard first-order characterization of convexity.
Lemma 13. Let f: Rd Ih be continuous convex function. Then, for any a; y TR:
f(y) 2 f(x) (ga, y x)
where I E af()), and (x)) is the subdifferential of f al æ.
The following technical lemma provides primal-dual gap bound in convex nonsmooth settings.
Lemma 14. For any k E [K]. the iterates {gks (6) Ji=1 and ( yot generated by Algorithm satisfy
E Σ
Th
Uk
(8)
A
(0) (Dk - Ik-1 (o) yr T (xx Tb x
71
1=1
(40)
m
3k 1,2
2k F2-114++122.
2n
where Eg := Th (C(zk, v) L(x,, y.))
+
2n |x.
b
xxl12
b 2n
10+
x2-1
Proof. By the same argument as in the proof for Lemma
we know that a T ah
E 06"
100 (v())
for b(i - - + S bi, then by Lemma
13 we have
e (o)) 2 (v) ( +
(v/ -v().
x 1,
which leads to
bi
[(ckk v)
1
(
A TK 15-15
(as
(bb)
+
k
(i) (0) (xx
A
x x1-)
11
j=b(i-1)4+
1=1
bi
(i) A 11-1,
(v
+
k
(Q)
k
(xx x8-11))-
1)+
1=1
(41)
Using the same argument for L(x,, y.) as a x. E (y! for E [m)] have
bb
C(x,, ya)
yerk
(i)
(5)
Σ
j=b(i-1)
1)+1
m
y
T
(5)
xz
00) (u())
(42)
j=b(i 1)+1
Adding and substracting the term
x.
D2 xz- 1,4 11 on the R.H.S. Eq. 42).
we obtain
2n17
i=1
b
bi
L(x., y.) 2 yk
+
||,0. - DK 1,1l
Can (vkk)
27Tk
j=b
11+1
b
|.0 0k- 1,
2n7jj
(1) Denote 0% (zx) = yk
(
x +
|| 24 - 12 which is on -strnngyy convex w.r.t. æ. Noticing
2mp.
that 2g. 1,641 arg min e Rd
yk A x + b || æa 1, by Line 7 of Alg, we have
(T)
V Vol (xx-1,041) = 0, which leads to
o6 (x.) 2 0/ (0 (0:-1,141) +
1| x xx
27pr
38

---

Thus, we obtain
bi
C(..., Va)
2
Uk A k
(
(4)
1,141 +
b
115-1,1411
12-11
Gao (v1)
27%
1=1
j= 1)+1
m
+
(| 2% 1k-11++1112
-1aa. =.k-1,
2n7jkc
bi
Vk
T
k
1,1+1 +
21/k:
b
|008
Σ
E
(e((v)))
(v/)
j b(t -
1)+1
b
x2112
xz 112
(43)
2717R
where (i) is by telescoping Σx= (||x, 22 1,4-1,41111
112
|| - 1x and using æy = -211m
and Øk-1 - which both hold by definition.
Combining the bounds from Eq. (41) and Eq. (43 and denoting
E = mr (C(x,, v) L(xx; y.)) + b
b 2n
x
x&
1
22-1
2n
finally obtain
E
<
7k
k/
(i)T
A (#x-1,1 - Cb x1+1,
(J)
A (1)
(ax
x1.)
i=1
1=1
I'' 1, - #8-1,44111
2n
m
7K
Vk
(i)
A (xx 26 x2-1,141)
(4)
17k
Uk
(6)
yk
(8)
A (xt xx-1,
π1
71
0 -K 1,54111
2n
thus completing the proof.
Note that we can still use Lemma 10 to bound the first inner product term in Eq. 440). as we are studying the same algorithm. The following lemma provides bound the second inner product
term To = It 21mh (u) yyk
(8)) T
A (xx 1551,5) in Eq. (40).
Lemma 15. Under Assumption generated by Algorithm satisfy
for any lo E [K], the iterates {yk (7) (m) Fizl and { 1+
mm+1
Th G GREes
nh v
Gr
(44)
Ta S
p +
| yk 1
b
4b
Proof. Proceeding as in Lemma 11 we have
m
7k To =
17 (A) 161-111 yk. AT (1) - -bx)).
y
A (xy xk-1,1)
bn
Using Young's 's inequality for some a > and proceeding as in Eq. 24 we obtain
Ta <
a
A Toct 16(11))13113
T 2bmax
A (oh yx)ll
2lm
no G _ 1B --
v 2na
<
+
ā (w) || yk 1
26
39

---

where we use our definitions that Gams =
1/2
foy-1)t A Too 11) x and
G2o0= = | 1 proof.
( Ax
26 P remains to choose a n V to finish the
11/2
We are ready to prove Theorem for the convergence of shufiled SGD in the convex nonsmooth Lipschitz settings.
Theorem 3. Under Assumption HK = Σx= Te and = Ex IV GrGa), the output ã of Alg. D with possible uniformly random shuffling satisfies
(f(x) - f(x.))
x.112 + Σ 2ninG,
2n
Amm
As result, for any O, there exists step size Th n such that E[f((x)) - f(xx)) (nGllzaaaa Ra- -..18))).) individual gradient queries.
after
O nG
To simplify the presentation of our analysis. we first assume || S n, which will be later verified by our choice of v = Yëx and Assumption
Proof.
Combining the bounds in Lemma T0 and
15 and plugging them into Eq. 40 have
& < Th G
n V
Gran
T(M)
y 1 +
||00
yk F
4b
ni
G (a)
nh v G21N
G,00
Bull?? +
(1|0)12-1 + |1
2b
(1) 2nÊn Gras
G
(45)
where Young's inequality for 110e vKll and |esxllrz'' || is fixed vector for (i), and (ii) is due | 1 S by Assumption 5 and assuming that || 2 1 S n. Proceeding as the proof for Theorem 2 we first assume the RR scheme and take conditional expectation w.r.t. the randomness up to but not including k-th epoch, then we obtain
2n (V G/G G_m)]
Ex [Ex] S
Since the randomness only comes from the random permutation (k), we have
For notational convenience, we denote - Ex LV G. and further take expectation w.r.t all the randomness on both sides and use the law of total expectation to obtain
2ngnG
B|
(46)
For the SO scheme, there is one random permutation æ generated at the very beginning such that
(k) π for all & E [K]. So we can directly take expectation w.r.t. all the randomness on both sides Eq. (45). with the randomness only from N, which leads the same bound as Eq. (46)
with E G Gaws] = E. [VG Note that for incremental gradient (IG) descent, we can let G / Go without randomness involved, where Go G and Go G w.r.t. the initial, fixed permutation N (0) of the data matrix A.
40

---

Noticing that Ex mh (x k
+
2n
b.
1|
xxl12
2
2n
6.
2,,, zx-1ll2 and telescoping from
K, we have
2
E
nr Gap (a v.)]
1|ar.
27
xK 11 1El1
2n
2n
Noticing that L(x, v) is convex wrt we have Gap"(a yy)
S Σ k= Gap" (xx y.) HK.
where ØK= k== mk HK and HK- Ek=1 Uak so obtain
2n
Hx ( 8.)
-1:00 xx11 +
2n
Further choosing v Yáx, which also verifies obtain
|| = yy P S n by Assumption 5 we
b
2n
[[HK( (()0(((k)((()))))) ((x.)))
x. 112 +
2n
b
To analyze the individual gradient oracle complexity, we choose constant stepsize 17. Then, the above bound becomes
2nnG
(( f(xx)]
11200
xx112
2nnk
b
Choosing
20p 1n-ww ll,
we have
2nVKG
2vGl| x. ll2
E[f(ix)
vK
Hence, given >> O, to ensure [[f(xx) f(x.)) )1 S c, the total number of individual gradient evaluations will be
4nG m - 2.11
nK 2
2²
thus completing the proof.
We now briefly discuss this result. The total number of individual gradient queries is O which appears independent of the batch size, but this actually not the case, as the parameter
G = T== (VVV,,,,, depends the block partitioning, due Eq. (4). When b n, as sanity check, we recover the standard guarantee (full) subgradient descent, which is expected, as in this case shuffled SGD) reduces subgradient descent. When b = however, the bound is worse than the corresponding bound for standard SGD, by a factor O OnGG//² ) By similar sequence of inequalities in Eq. (4. this factor is never worse than n, but is typically much smaller, taking values small as 1. We note that it is not known whether a better bound is possible for shuffled SGD in this setting, as the only seemingly tighter upper bound from 42) applies only for constant K, when n 2(2)) and under an additional boundedness assumption for the algorithm iterates.
E Experiment Details
We implement the computation of Ż and Lmax in Julia, a high-performancee scientific computation programming language, and compute matrix operator norms using the default settings in the Julia Arpack Package. However, limited by computational memory and time constraint, selection of datasets focused on moderately large-scale datasets of n in the order of 0(105). We also include comparisons of small datasets such as a1a and sonar.
E.1 Evaluations of L, on Synthetic Gaussian Datasets
We first study the gap between Ln and Lmax for different batch sizes b, as shown Figure 2 As in Section 4.1 we focus on their dependence on the data matrix, and assume that the loss functions e, all have the same smoothness constant. In this case, the ratio L L, that characterizes the gap between
41

---

Ln and Lmax will become Lmax/Lr (maxigign ( 121///1 An In particular, run experiments standard Gaussian data of size d). We fix the dimension d 500, and vary the number of samples with n = 100, 500, 1000, 2000. In Figure we plot the ratio Lmax/Ls Le versus the batch size for 100 different random permutations म, where the dotted lines represent the mean values and the filled regions indicate the standard deviation of permutations. We observe that the ratio Lmax/ La is concentrated around its empirical mean and exhibits b (ar [0.74, 0.87)) growth as the batch size increases. In particular, we choose yn, the ratio can be (n.4.)
50
140
120
40
100
30
80
20
60
40
10
20
20
40
60
80
100
100
200
300
400
500
batch size
batch
size b
100
(b) 500
200
250
150
200
130
100
100
50
0-
0
200
400
800
1000
1000 125012051001500000
batch size b
batch size
(c) n 1000
(d)
2000
Figure 2: Illustrations of Lmax/ L for different batch size b on synthetic Gaussian data of size (n, d)-
E.2 Distributions Lmax/ f.g
In this subsection, we include histograms in Figure to illustrate the spread of Lmax/ Ln with respect to random permutations, for completeness. We observe that in all the examples Tmmax/ l. is concentrated around its empirical mean. The following plots are normalized, with y-axis representing the empirical probability density. The x-axis represents Lmax/ La-
42

---

12.5
75
25
3450 SA1 5350 5515 5350 5375
2.402
2.495
18..
aia
a9a
BBBCO05
1.0
40
08
0.05
30
20
0.4
02
0.1
BBBC010
CIFAR10
duke
132
120
0.04
60-
0.03
0.02
20
20
e2006train
gisette
1 eu
0.8
17.5
0.0
75-
0.4
25
78.07500
MNIST
news20
rcv1
15
0.-
1.0
04
02
0.0
68
5.4
real-sim
sonar
tmc2007
Figure 3: Visualization of the empirical distributions of L/ L for 15 large-scale datasets.
43

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Our abstract and introduction clearly state the scope of our work and contribu-
tions, see Section 1.2
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Yes, see detailed discussion in the introdcution.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
44

---

Justification:
We state our assumptions in sections 2 and 3 and the proofs are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We fully disclose the public datasets and tools we use for the numerical computations in Section 4.1
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
45

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips.c..a httpssccppbbbccc/cceeceee guides/ /ac////oddmiissseeeeeeee siiiiiicccyyyyyyccccooccocc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
We list the details of our experiments Section 4.1 and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We use various ways, including ribbon plots and histograms, to illustrate the variance of our numerically computed values.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
46

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We list the details all computational tools in Section 4.1 and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't I make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: This a primarily theoretical work and we conform to the rules with NeurIPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
47

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility MI).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We use public benchmarking datasets from LIBSVM (15), MNIST [17). CIFARIO (22), and Broad Bioimage Benchmark Collection 28 and have properly cited and credited the asset's 's creators.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
48

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
49

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
50


Reviews:
[{"review_id": "0bKqNyluxz", "reviewer": "Reviewer_JY5g", "summary": "This paper focuses on SGD with shuffling for finite-sum minimization problems. While there exists tight convergence upper and lower bounds for SGD assuming a global smoothness constant $L_{\\max}$, the proposed results give a more fine-grained analysis in terms of the component-wise smoothness constants $L_i$ to show possibly faster convergence rates using Fenchel dual arguments. By replacing the $L_{\\max}$’s with smaller constants $\\tilde{L}, \\hat{L}$, the new results can improve the iteration complexity by up to a factor of $L_{\\max}/\\hat{L} = O(n)$ as demonstrated in the linear predictor example. This work also extends to non-smooth, Lipschitz objectives in the case of linear predictors, and provides empirical evidence supporting the claims.", "questions": "- Is there a way to intuitively understand when or why $\\tilde{L}/L_{\\max}, \\hat{L}/L_{\\max}$ could be ‘much’ smaller than $1$ (with possible $n^{\\alpha}$-ish dependencies), both for the  Or are there at least any examples apart from the linear predictor that demonstrate significantly small $\\tilde{L}/L_{\\max}, \\hat{L}/L_{\\max}$?\n- Based on my knowledge, in coordinate descent algorithms it is common to use *different* step sizes for different coordinates, say $\\eta_i = 1/L_i$, to improve dependencies on the $L$’s. Would it be possible to do something similar for this case if we take the primal-dual approach?\n- Can you elaborate a bit more on why the inequality $(iii)$ of $(4)$ (in Section 4) is loose by a factor of $n$ in most cases? My understanding of the linear predictor case is that the norm-trace gap corresponds to the largest VS sum of singular values, and hence if the singular values are even, then the gap can be as loose as a factor of $n$, while if we have a single large $\\lambda_{\\max}$ then the inequality can be tight. I wonder if (i) this interpretation is correct, and (ii) whether something similar could hold for the $\\tilde{L}^g, \\hat{L}^g$’s in the general convex case.\n- Minor question: Is it true Algorithm 1 is completely equivalent to the standard SGD with random reshuffling (without the $\\boldsymbol{y}$’s), and the dual variables are just there for illustrative purposes?", "limitations": "The authors adequately addressed the limitations, and there seems to be no potential negative societal impact.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The idea of the ‘primal-dual’ formulation, which essentially allows one to exploit similar-to-coordinate-descent techniques for better dependencies on the $L_i$’s, is new to me and seems to be a potentially useful technique. I agree that using component-wise structures for improved convergence rates could be one of the many meaningful future directions for the shuffling community.\n- The paper presents results that consider general types of shuffling-based algorithms (RR, SO, IG) which I appreciate.", "weaknesses": "- Focusing on the results, the only big difference with previous work would be the constant $L_{\\max}$ being replaced with $\\tilde{L}, \\hat{L}$, which means that the improvements are directly linked with how small the ratios $\\tilde{L}/L_{\\max}, \\hat{L}/L_{\\max}$ could actually be. While Table 2 suggests that $L_{\\max}$ could be quite large (for the linear predictor case), it is quite hard to see how ‘small’ the values $\\tilde{L}, \\hat{L}$ are in first glance due to the relatively complicated definitions. The paper explains the gap for Gaussian data, but I think this example is a bit too ‘specific’.\n- Moreover, based on my understanding, the definitions of $\\tilde{L}, \\hat{L}$ for the general convex case and the linear predictor case seem to be a bit different. It is still unclear whether these fine-grained bounds could imply a significantly *faster* convergence rate, especially for the general convex case.\n- Minor Stuff: I might have missed this, but it seems that the definition of $\\boldsymbol{A}_{\\pi}$ (which I think is $\\\\boldsymbol{A}\\_{\\\\pi}  = [a\\_{\\pi_1} \\cdots a\\_{\\pi_n}]^{\\top}$) is missing in Section 3.1. Also, the proofs are all written for batch size $b$, might be confusing to readers: maybe it would have been better if the main body also contained statements including $b$.\n- TYPO: Line 9 of Algorithm 1, $m$ → $n$\n- TYPO: Line 473 mini-bath → mini-batch", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We appreciate the questions the reviewer raised. We hope that the answers provided below address the reviewer’s concerns and that the reviewer would consider reevaluating our work. We will fix the typos, update statements in the main body to apply to batch size $b$, and add more discussions in the revision, as suggested. Please let us know if there is any additional information that would be helpful.**\n\n---\n\n### Weaknesses\n> W1: While Table 2 suggests that $L_{\\mathrm{max}}$ could be quite large (for the linear predictor case), it is quite hard to see how ‘small’ the values $\\tilde{L}$, $\\hat{L}$ are in first glance due to the relatively complicated definitions. The paper explains the gap for Gaussian data, but I think this example is a bit too ‘specific’.\n\nWe share the same view that it may be difficult to directly compare $\\tilde{L}$, $\\hat{L}$ against $L_{\\mathrm{max}}$, which is why we conducted numerical computations on 15 popular machine learning datasets to illustrate the gap between $\\hat{L}$ and $L_{\\mathrm{max}}$. In some cases, we demonstrate that the gap can be as large as $O(n)$ in the linear predictor settings, suggesting the effectiveness of our fine-grained analysis through a primal-dual perspective.\n\n> W2: Moreover, based on my understanding, the definitions of $\\tilde{L}$, $\\hat{L}$ for the general convex case and the linear predictor case seem to be a bit different. It is still unclear whether these fine-grained bounds could imply a significantly faster convergence rate, especially for the general convex case.\n\nThe reviewer is correct on the difference between the two cases, while such a difference is intuitive and desirable. For the general convex case, one can view our fine-grained bounds as improving from maximum (in previous works [1–3]) to average smoothness, which could also lead to $O(\\sqrt{n})$ improvement in the final complexity (when component smoothness parameters are highly nonuniform). For linear predictors, the bounds are more informative (and in our opinion, interesting), as they are directly dependent on the data matrix. We will further clarify these points in our revision.\n\n---\n\n### Questions\n> Q1: Is there a way to intuitively understand when or why $\\tilde{L}/L_{\\mathrm{max}}$, $\\hat{L}/L_{\\mathrm{max}}$ could be ‘much’ smaller than $1$ (with possible $n^{\\alpha}$-ish dependencies), both for the Or are there at least any examples apart from the linear predictor that demonstrate significantly small $\\tilde{L}/L_{\\mathrm{max}}$, $\\hat{L}/L_{\\mathrm{max}}$?\n\nFor linear predictors, the main source of the improvement can be seen as our bounds being dependent on the operator (as opposed to Frobenius) norm of the data matrices, as discussed in Lines 241-250 in Section 4. The operator-to-Frobenius norm relaxation is almost always loose, and often by a factor of $n$ for $n \\times n$ matrices, as discussed in Lines 249-250. At an intuitive level, we expect this relaxation to be loose (and our bound to be tighter) when there is weak correlation between the data points, which we take to an extreme in our Gaussian data example (but similar conclusions could be drawn for e.g., sub-Gaussian data). We expect this to be the case in datasets where data is collected from independent sources, which is a standard assumption for even being able to guarantee good statistical properties pertaining to learning. For general convex smooth functions, our dependence on the smoothness also improves from the maximum to the average, leading to $O(n)$ improvement when the component smoothness constants are highly nonuniform. \n\n> Q2: Based on my knowledge, in coordinate descent algorithms it is common to use different step sizes for different coordinates, say $\\eta_i = 1/L_i$, to improve dependencies on the $L$’s. Would it be possible to do something similar for this case if we take the primal-dual approach?\n\nThis is a good point. We first note that our focus is not on proposing new algorithms but deriving tighter bounds for shuffled SGD, so we stick to the constant step size over all components/inner iterations, which agrees with previous works on shuffled SGD [1–3] and empirical practice. On the other hand, deploying different step sizes for each component gradient update based on the component smoothness would be an interesting approach. We believe it is possible to incorporate different step sizes in our analysis by carrying out the argument using a weighted $\\ell_2$ norm, similar to what was done for coordinate methods in nonconvex settings [4]. However, this is out of scope of the present work, and we leave it for future research.\n\n\n> Q3: Can you elaborate a bit more on why the inequality (iii) of (4) (in Section 4) is loose by a factor of $n$ in most cases? My understanding of the linear predictor case is that the norm-trace gap corresponds to the largest VS sum of singular values, and hence if the singular values are even, then the gap can be as loose as a factor of n, while if we have a single large $\\lambda_{\\mathrm{max}}$ then the inequality can be tight. I wonder if (i) this interpretation is correct, and (ii) whether something similar could hold for the $\\tilde{L}^g$, $\\hat{L}^g$’s in the general convex case.\n\nThe reviewer’s interpretation is correct. This is exactly what happens in our Gaussian example, but one can generalize. For general convex settings, there is no specific structure of data matrices in the optimization objective, so the best one may expect is the improvement from the max (in previous works [1–3]) to the average smoothness constant. We discuss those in Lines 493-501 in Appendix B.\n\n> Q4: Minor question: Is it true Algorithm 1 is completely equivalent to the standard SGD with random reshuffling (without the $\\mathbf{y}$’s), and the dual variables are just there for illustrative purposes?\n\nYes, the primal-dual version is provided for convenience of the primal-dual analysis; there is no difference in the actual algorithm.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "lgyKXf6NaC", "reviewer": "Reviewer_Ua2v", "summary": "This paper considers the primal-dual aspect of SGD using sampling without replacement (shuffled SGD). The authors present results for shuffled SGD on smooth and non-smooth convex settings with tight convergence bounds for several shuffling schemes (IG, SO, and RR). In some specific settings, the convergence rate can be improved with a factor of $\\sqrt{n}$. The authors perform experiments to demonstrate that their bound is tight and better than prior work.", "questions": "Why do you call RR and SO uniformly random shuffling? \n\nHow the results in section 3 reduces and compares to general convex finite-sum problems when $a_i$ are all-1 vectors i.e. loss function applies on $x$?\n\nI have read the author responses.", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The theoretical results seem to be solid, although I did not check the proofs. The authors choose to investigate a different type of smoothness constant compared to the prior work, thus lead to improvement in the bound. In addition, they study the primal-dual aspect for linear predictors and then extend the results to non-smooth setting.", "weaknesses": "The improvement in the convergence is not significant as it is only changing the Lipschitz constant. \nThe authors should be more transparent about the setting where there is $\\sqrt{n}$ improvement as it seems like this only applies to linear predictors (the claim in abstract, line 14-17 is not clear). The authors should include that context in your statements. Another weakness is that the bounds in Section 3 depend on the data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We thank the reviewer for their feedback and kindly request them to consider our responses below when evaluating our work. We appreciate the opportunity to further engage in a discussion, as needed.**\n\n---\n\n### Weaknesses\n> The improvement in the convergence is not significant as it is only changing the Lipschitz constant. \n\nWe respectfully disagree with this point, as obtaining a dependence on a fine-grained smoothness/Lipschitzness constant directly leads to up to $O(\\sqrt{n})$ complexity improvement. Dependence on other problem parameters cannot be improved, by the lower bound results in [1].\n\n> The authors should be more transparent about the setting where there is $\\sqrt{n}$ improvement as it seems like this only applies to linear predictors (the claim in abstract, line 14-17 is not clear). \n\nFor general convex smooth problems, one can also expect $O(\\sqrt{n})$ improvement, as our results improve the dependence from the max to average smoothness.\n\n> Another weakness is that the bounds in Section 3 depend on the data.\n\nWe note that such data-dependent bounds are generally appreciated in theory, because they automatically predict faster convergence than the worst-case analysis based on component smoothness.\n\n---\n\n### Questions\n> Why do you call RR and SO uniformly random shuffling?\n\nIt is because the permutation is chosen uniformly at random over the set of possible permutations. This terminology is standard in the shuffled SGD literature [1–3].\n\n> How the results in section 3 reduces and compares to general convex finite-sum problems when $a_i$ are all-$1$ vectors i.e. loss function applies on $x$?\n\nWe first note that having all $1$s in $a_i$ does not reduce to the general convex finite sum setting, as in that case each $f_i$ would be univariate, dependent on the sum of the entries of $x$. \n\nFor the comparison between the results in two sections, we note that our results in Theorem 2 provide a tighter bound than directly applying Theorem 1 to the generalized linear models. This is because Eq. (3) is a tighter estimate than Eq. (2), where the data matrix $A$ and the smoothness constants from the nonlinear part $\\Lambda$ are separated in Eq. (3). \n\nIn particular, consider the case where $\\ell_i$ are all $1$-smooth for simplicity and $f_i = \\ell_i(\\langle a_i, x\\rangle)$ is $\\\\|a_i\\\\|^2$-smooth. For brevity, we omit the permutation notation and let the batch size be $1$, then Eq. (3) and Eq. (2) reduce to the operator norms of two $n \\times n$-dimensional matrices $M$ and $N$ normalized by $1/n^2$ respectively, where their entries are given by $M_{ij} = \\min\\\\{i, j\\\\} a_i^\\top a_j$ and $N_{ij} = \\min\\\\{i, j\\\\} \\\\|a_i\\\\| \\\\|a_j\\\\|$. Note that the operator norm of $M$ is always smaller than the operator norm of $N$, because the absolute value of each element of $M$ is no larger than the corresponding element of $N$, by the Cauchy-Schwarz inequality. Further, for the case where all the row norms are scaled to $1$ (the average and the maximum component smoothness constants would both be equal to $1$), our results would still be tighter by a factor as large as $\\sqrt{n}$. This is implied by our Gaussian example discussed in Lines 251-260 in Section 4, using concentration of measure on the sphere.\n\nFor general convex cases, we refer to Appendix B for more discussion.\n\n---\n\n### References\n\n[1] Jaeyoung Cha, Jaewook Lee, and Chulhee Yun. Tighter lower bounds for shuffling SGD: Random permutations and beyond. In Proc. ICML'23, 2023.\n\n[2] Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random reshuffling: Simple analysis with vast improvements. In Proc. NeurIPS’20, 2020.\n\n[3] Lam M Nguyen, Quoc Tran-Dinh, Dzung T Phan, Phuong Ha Nguyen, and Marten Van Dijk. A unified convergence analysis for shuffling-type gradient methods. The Journal of Machine Learning Research, 22(1):9397–9440, 2021.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "zndgqdhjWZ", "reviewer": "Reviewer_EeyJ", "summary": "This paper studied the convergence of random shuffled SGD through the lens of dual coordinate descent. By leveraging the analysis in coordinate descent, the author(s) derived a rate that is $O(\\sqrt{n})$ faster than existing rate.", "questions": "The convergence analysis of coordinate descent usually have to assume the objective is smooth, which means the primal objective is strongly convex. But the strong convexity assumption was not used in this paper, I wonder how does the author(s) circumvent this assumption?", "limitations": "Limitations are not well-addressed. I do not see any potential negative impact of this paper.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Pros:\n-  The paper is well written and easy to follow, contributions are clearly stated (Table 1).\n-  The rate derived by the author(s) is better than previous state-of-the-art.", "weaknesses": "- The primal-dual relationship between SGD and coordinate descent has a quite long history, e.g. [1]. The author(s) should mention these works in the related work section or section 2.\n\n[1] Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization, Shai Shalev-Shwartz and Tong Zhang, 2013.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We thank the reviewer for their valuable feedback. We hope that the answers provided below address the reviewer’s concerns and that the reviewer would consider reevaluating our work. We appreciate the opportunity to answer further questions in the discussion phase.**\n\n---\n\n### Weaknesses\n> The primal-dual relationship between SGD and coordinate descent has a quite long history, e.g. [1]. The author(s) should mention these works in the related work section or section 2.\n\nThank you for pointing out this line of work. We will cite this paper and discuss related work in our revision. In particular, [1] provides theoretical results only for SDCA, which chooses the dual coordinate to optimize *uniformly at random*. The cyclic variant SDCA-Perm (related to shuffled SGD) that samples the dual coordinate without replacement is only presented as an empirical example and studied through numerical experiments.\n\n---\n\n### Questions\n> The convergence analysis of coordinate descent usually have to assume the objective is smooth, which means the primal objective is strongly convex. But the strong convexity assumption was not used in this paper, I wonder how does the author(s) circumvent this assumption?\n\nThe reviewer is correct, and that is exactly why the existing analyses for coordinate methods cannot be applied to shuffled SGD methods. Note that there is no smoothness or descent on the dual side in our setting, and we are also taking the \"best response\" steps on the dual, which is strongly convex (due to primal smoothness). It is also important to note here that cyclic methods would be making specific gradient or proximal steps and use the properties of such steps in the analysis, while here we can only allow the dual update to be “best response” so that we maintain the equivalence with the standard (primal-only) shuffled SGD. To handle these issues, we follow a primal-dual approach, which is different from traditional analysis of coordinate methods.\n\nStrong convexity is mainly used to bound the gap by introducing negative terms $-\\\\|y_k - y_*\\\\|^2_{\\Lambda^{-1}}$ on the dual side; see Lines 669-670 in the proof as an example. As a side note, our analysis can also deduce convergence results on the dual variables $\\\\|y_k - y_*\\\\|^2_{\\Lambda^{-1}}$. \n\nThe major part in which we build connections with coordinate methods is on how to characterize the difference between the intermediate iterate $x_{k- 1, i}$ and the iterate $x_k$ after one full cycle, as mentioned in Lines 73-79. To improve over previous worst-case analysis and obtain a tighter fine-grained bound, one needs to avoid using global smoothness with a triangle inequality, which is a prevalent approach in existing analyses of shuffled SGD [2–4]. Instead, we derive the fine-grained bounds on the partial sum of intermediate dual variables $y_k^i$ by tracking the progress of the cyclic update on the dual side, in the aggregate; see e.g., the proof of Lemma 11 to bound $\\mathcal{T}_2$. Our technique mirrors the very recent advance on the fine-grained bounds for coordinate methods [5–7]. However, our setting and algorithm are technically disjoint with these works, as discussed in Lines 455-462 in Appendix A.\n\n---\n\n### References\n\n[1] Shalev-Shwartz, S., & Zhang, T. Stochastic dual coordinate ascent methods for regularized loss minimization. Journal of Machine Learning Research, 14(1), 2013.\n\n[2] Jaeyoung Cha, Jaewook Lee, and Chulhee Yun. Tighter lower bounds for shuffling SGD: Random permutations and beyond. In Proc. ICML'23, 2023.\n\n[3] Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random reshuffling: Simple analysis with vast improvements. In Proc. NeurIPS’20, 2020.\n\n[4] Lam M Nguyen, Quoc Tran-Dinh, Dzung T Phan, Phuong Ha Nguyen, and Marten Van Dijk. A unified convergence analysis for shuffling-type gradient methods. The Journal of Machine Learning Research, 22(1):9397–9440, 2021.\n\n[5] Xufeng Cai, Chaobing Song, Stephen J Wright, and Jelena Diakonikolas. Cyclic block coordinate descent with variance reduction for composite nonconvex optimization. In Proc. ICML'23, 2023.\n\n[6] Chaobing Song and Jelena Diakonikolas. Cyclic Coordinate Dual Averaging with Extrapolation for Generalized Variational Inequalities. SIAM Journal on Optimization, 2023.\n\n[7] Cheuk Yin Lin, Chaobing Song, and Jelena Diakonikolas. Accelerated cyclic coordinate dual averaging with extrapolation for composite convex optimization. In Proc. ICML'23, 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "nM1HiiiCCQ", "reviewer": "Reviewer_S4vW", "summary": "This paper aims at improving existing bounds on random reshuffling. While lower bounds are tight in the worst case, refined smoothness definitions allow to take a larger step-size in favorable cases, which in turns allows faster convergence. These smoothness definitions involve a supremum over permutation-dependent partial averaging of individual smoothness constants. \n \nThe dependence on these refined smoothness constants is obtained through a primal-dual interpretation of SGD, though the convergence analysis does not consist in applying existing primal-dual analyses to this formulation. As a side note, results include mini-batching, which is nice to have. \n\nFor generalized linear models, individual covariances can be averaged instead of individual smoothness constants, thus allowing to gain even more especially in high-dimensions. A non-smooth extension is given, performing similar averagings over individual Lipschitz constants. \n\nTypos:\nLine 27: why does SGD rely on a standard basis vector?? This looks like a mix between SGD and coordinate descent. \nL45: we choose take \nAlgo 1: shouldn't this be a $\\nabla f_i$ on line 7?", "questions": "1) In the end, everything seems to depend on primal quantities. What makes an actual difference in the analysis that could not have been done in the primal (or why was it more intuitive to do it in the primal)? Why can't the full analyses be done by replacing the $y^i_k with $\\nabla f_i(x_{k,i})$?\n\nIn particular, what technical challenges do you expect moving to the non-convex setting? In the end all quantities can, but the primal-dual interpretation of SGD does not hold anymore since biconjugacy is used at some point if I'm not mistaken).\n\n2) What are the connections with existing (primal-dual) CD analyses? I see that the primal-dual reformulation allows to study a setting that is close (although different since CD would not get any residual variance). It is said in Appendix A that results are technically disjoints, so then why is this inspiration helpful still? \n\n3) It seems that the discussion from Section 4 only applies to the generalized linear models case, because it does not seem possible to benefit from structure in the general case. Do you have any intuition for why such assumptions cannot be made using Hessians, and thus benefit from similar improvements? Additionally, how would Table 2 look with these bounds instead of the generalized linear models ones?\n\n4) Do you actually expect to depend on the smoothness for the average permutation (instead of worst-case)? Is this complicated to analyze directly because of the dependence between iterates within a single epoch?", "limitations": "See weaknesses", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Nice use of the finite-sum assuption, which allows to use a primal-dual reformulation.\n- Improves over existing bounds for shuffled SGD, mimicking cyclic coordinate descent results.", "weaknesses": "- $\\tilde{L}$, the $L_{max}$-like constant, is the one that appears in Theorems 1 and 2. In particular, the more \"average smoothness\" constant (from which most of the improvement seems to come) only affect higher-order terms by using larger step-sizes to be used, but does not change anything for small step-sizes. \n- While results are strong for generalized linear models (taking into account the actual spectrum of each Hessian), general results are quite looser (though they still improve on existing ones).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We thank the reviewer for the positive evaluation of our paper. We hope that the clarifications provided below address the reviewer’s questions. We are happy to answer further questions in the discussion phase.**\n\n---\n\n### Summary\n> Typos\n\nThanks for pointing out. It should be $E_{i_t} [ \\nabla f_{i_t} (x_t) / p_{i_t}] = \\nabla f (x_t)$ in Line 27. We will correct those typos in our revision. \n\n---\n\n### Questions\n> Q1\n\nCorrect. In our case, the primal-dual view allowed us to separate the linear transformation ($a_i^\\top x$) from nonlinearity (loss $\\ell_i$), as is done in splitting primal-dual methods like [1]. The separation of linear vs nonlinear portion was useful for handling cancellations coming from the cyclic updates (see e.g., the proof of Lemma 9) and obtaining the data dependent bounds (see e.g., Lines 692–696 in the proof of Lemma 11). That said, given that in the end the algorithm is equivalent to standard shuffled SGD (i.e., the algorithm is primal-only and the primal-dual perspective is only there for the analysis), we expect that there is a way to write the analysis as primal-only. We did not pursue this direction as we did not think it would improve the readability and interpretations of the proofs. \n\n> Q2\n\nWe first note that in nonconvex settings one would need guarantees in terms of stationarity, which is different from the optimality gap in convex settings. Also, all the existing work on shuffled SGD for nonconvex objectives requires additional assumptions about the problem, such as bounded variance at all points [2] or bounded sequence correlation [3]. \n\nHowever, we believe that our techniques can be generalized to at least some (but still fundamental in the context of ML applications) nonconvex objectives, such as those arising from generalized linear models (GLMs). As a specific example, one could consider minimizing the mean squared loss of a GLM (e.g., ReLU as the most basic example): $$\\min_x \\frac{1}{2 n} \\sum_{i=1}^n (\\sigma(x^\\top a_i) - b_i)^2$$ where $\\sigma(t)$ is an activation function; for example $\\sigma(t) = \\mathrm{ReLU}(t) = \\max\\\\{0, t\\\\}.$ \n\nOne can “dualize” the quadratic portion of this objective to write it in a primal-dual form as: $$\\min_x \\max_y \\frac{1}{n} \\sum_{i=1}^n (\\sigma(x^\\top a_i) - b_i)y_i - (1/2)y_i^2.$$ In this case, we get a nonlinear (but structured) coupling of the primal and the dual, which we believe can be handled with a separate analysis. One relevant observation is that in this case $a_i y_i$ (which for convex ERM functions in our paper was the gradient of the component function) now corresponds to the gradient of a *surrogate* function for the nonconvex GLM problem. SGD-style methods applied to the surrogate function with the same gradient field $a_i y_i$ as here have been widely studied in the learning theory literature and used to argue about the learnability of these problems (under distributional assumptions); see e.g., [4] and references therein. We leave the investigation of nonconvex problems based on GLMs as an interesting topic for future study. \n\n\n> Q3\n\nThanks for raising this point. We draw inspiration from primal-dual methods to separate the linear and nonlinear components of the objectives and follow the methodology of gap construction in primal-dual methods. However, details of the analysis are crucially different, as discussed in Appendix A. First, most CD analyses cannot provide tight bounds for the setting with random permutation of blocks, while the only works handling random permutations are specialized to convex quadratics [5,6]. Further, for those works providing fine-grained CD analyses [7–9] (most CD works only provide analyses with the worst-case dependence on the number of blocks), they either rely on a certain block-wise descent lemma [7] ( there is no smoothness or descent on the dual side for shuffled SGD), or use extrapolation steps which are incompatible with the shuffled SGD algorithm [8, 9].\n\n\n> Q4\n\nTo use Hessians, we would need to assume the function is twice (continuously) differentiable, which are the assumptions we are not using right now. It is however a good insight that possibly similar fine-grained bounds can be obtained by working with the Hessian. An alternative approach would be to assume that functions are smooth with respect to Mahalanobis (semi)norms, similar to what was done in [7–9], and then obtain bounds dependent on the matrices defining those norms. This is something that seems doable and we can consider adding if the reviewer thinks it would be useful to include.\n\n\n> Q5\n\nWe first note the dependence on the worst-case permutation mainly appears in our final complexity and comes from the need to select a constant, deterministic step size, as discussed in Lines 716-723 in the proof. In principle, one can replace it with a certain high-probability bound on $\\hat L_\\pi$ and $\\tilde L_\\pi$. We would like to further point out that for the 15 datasets we looked at, the smoothness parameter over permutations seems to concentrate around the mean, as illustrated in Appendix E. Thus in practice, the difference between these two quantities appears minor.\n\nOn the other hand, for the dependence on $\\tilde L$ in Lemma 2 and Theorem 2, the reviewer is correct on the technical difficulty. We refer to our proof in Lines 695-705, as an example. From the inequality in Lines 695–696, we need to bound \n$\\tilde L_{\\pi^{(k)}}\\\\|A_k^\\top I_{(i - 1)\\uparrow}y_{\\ast, k}\\\\|^2$ with permutation randomness coupled together. Such a term is nontrivial to bound, so we first relax $\\tilde L_{\\pi^{(k)}}$ to $\\tilde L$ to reduce the randomness on $\\\\|A_k^\\top I_{(i - 1)\\uparrow}y_{\\ast,k}\\\\|^2$ only, and then use Lemma 8 to bound that term as in Lines 703–704. However, we conjecture that the dependence on the average permutation could be achieved by a much more complicated analysis combining our fine-grained analysis with the techniques of conditional expectations, which we leave for future research.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:
We would like to thank all the reviewers for their precious time and valuable feedback. In this top-level rebuttal, we reiterate the contributions and strengths of our work. 

---

We first summarize our main contribution by quoting the Review S4vW where they acutely pointed out 
> This paper aims at improving existing bounds on random reshuffling. While lower bounds are tight in the worst case, refined smoothness definitions allow to take a larger step-size in favorable cases, which in turns allows faster convergence.

---

Further, we are encouraged by reviewers recognizing the following aspects of our work:
- **Improved complexity**: All reviewers recognize that our fine-grained analysis provides improved complexity over previous worst-case analyses. 

- **Novel primal-dual view**: 

    * > (Reviewer JY5g) “New to me and seems to be a potentially useful technique, … using component-wise structures for improved convergence rates could be one of the many meaningful future directions for the shuffling community”,

    * > (Reviewer S4vW) “Nice use of the finite-sum assumption, which allows to use a primal-dual reformulation”.

- **Extensive study**: 

    * > (Reviewer JY5g) “consider general types of shuffling-based algorithms (RR, SO, IG) which I appreciate”, 

    * > (Reviewer Ua2v) “extend the results to non-smooth setting”, 

    * > (Reviewer S4vW) “As a side note, results include mini-batching, which is nice to have”.

- **Writeup**: Three reviews rate our soundness 3 and presentation 3 (Review JY5g, Review EeyJ, Review S4vW). It is also particularly mentioned that 

    * > (Reviewer EeyJ) “The paper is well written and easy to follow, contributions are clearly stated (Table 1)”.

---

We look forward to interacting with the reviewers and providing any further explanations as needed.

Sincerely,

Authors

Meta-review: The paper studies shuffling-based SGD on convex finite-sum optimization problems. Through a primal-dual analysis on the primal algorithm SGD, the authors develop new convergence theorems for random-reshuffling and shuffle-once SGD with alternative smoothness constants that can improve upon the existing bounds that contain the max smoothness constant. The authors then develop convergence bounds for smooth and non-smooth convex generalized linear model cases, demonstrating similar but more fine-grained bounds that can better reflect the data matrix.

The paper presents nontrivial and novel analysis inspired from the connection of finite-sum SGD with coordinate descent in the dual space. The bounds improve upon existing results in the literature and can offer tighter bounds especially when there is a large gap between the max smoothness constant and the "average" smoothness. The discussion provided in Section 4 is inspiring, in that it suggests that we should take the structure of data into account in the convergence analysis to get tighter results.

The newly proposed constants $\tilde L$, $\hat L$, etc…  are not readily interpretable, as the authors also admitted in the discussion. The authors provide some numerical experiments demonstrating that they can be smaller than $L_\max$, but I recommend the authors to supplement the paper with some theoretical analysis of the proposed constants in some specialized scenarios, e.g., when $L_i$'s decay as $i^{-\alpha}$. 

Overall, the reviews were mostly positive and the contributions look solid; hence I recommend acceptance of this paper.
Decision: Accept (poster)