An Improved Analysis and Rates for Variance Reduction under Without-replacement Sampling Orders 
Authors: Xinmeng Huang
Kun Yuan
Xianghui Mao
Wotao Yin
Venue: NeurIPS 2021 Poster (2021)
Keywords: convex optimization
stochastic optimization
SGD
variance reduction

Abstract: When applying a stochastic algorithm, one must choose an order to draw samples. The practical choices are without-replacement sampling orders, which are empirically faster and more cache-friendly than uniform-iid-sampling but often have inferior theoretical guarantees. Without-replacement sampling is well understood only for SGD without variance reduction. In this paper, we will improve the convergence analysis and rates of variance reduction under without-replacement sampling orders for composite finite-sum minimization.

Our results are in two-folds. First, we develop a damped variant of Finito called Prox-DFinito and  establish its convergence rates with random reshuffling, cyclic sampling, and shuffling-once, under both generally and strongly convex scenarios. These rates match full-batch gradient descent and are state-of-the-art compared to the existing results for without-replacement sampling with variance-reduction. Second, our analysis can gauge how the cyclic order will influence the rate of cyclic sampling and, thus, allows us to derive the optimal fixed ordering. In the highly data-heterogeneous scenario, Prox-DFinito with optimal cyclic sampling can attain a sample-size-independent convergence rate, which, to our knowledge, is the first result that can match with uniform-iid-sampling with variance reduction. We also propose a practical method to discover the optimal cyclic ordering numerically.

Improved Analysis and Rates for Variance Reduction under Without-replacmment Sampling Orders
Xinmeng Huang" University of Pennsylvania Philadelphia, PA 19104 xinmengh@sas. upenn. edu
Kun Yuan"
DAMO Academy. Alibaba Group Bellevue, WA 98004 kun www.anallaaaaalaaaaaaaaaaa com
Xianghui Mao Tsinghua University Beijing, China 100084 xi xianghui. xh, www.maammmmm...m com
Wotao Yin
DAMO Academy, Alibaba Group Bellevue, WA 98004 wotao, . www.yyaalaaaaaaiinnooomm com
Abstract
When applying stochastic algorithm, one must choose an order to draw samples. The practical choices without-replacemmett sampling orders, which are empir- ically faster and more cache-friendly than siffooommid-saapliiiii inferior theoretical guarantees. Withemetreplacemmnt sampling is well understood only for SGD without variance reduction. In this paper, we will improve the convergence analysis and rates of variance reduction under without-replacement sampling orders for composite finite-sum minimization.
but often have
Our results are in two-folds. First, we develop a damped variant of Finito called Prox-DFinito and establish its convergence rates with random reshuffling, cyclic sampling, and shuffling-one These rates match full-batch gradient descent and are sfate-of-the-ard compared to the existing results for without-replacement sampling with variance-reduction Second, our analysis can gauge how the cyclic order will influence the rate of cyclic sampling and, thus, allows us to derive the optimal fixed ordering. In the highly data-heterogeneous scenario, Prox-DFinito with optimal cyclic sampling can attain convergence rate, which, to our knowledge, is the first result that can match with uniform-in iisoom-iid-saae hid-sanpling with variance reduction. We also propose practical method to discover the optimal cyclic ordering numerically.
under both convex and strongly convex scenarios.
Introduction
We study the finite-sum composite optimization problem
F(x) + r(x) and F(x) Σ f(()).
min ZERd
where each f1( is differentiable and convex, and the regularization function r(x) is convex but not
necessarily differentiable. This formulation arises in many problems in machine learning 33 39 [4]
distributed optimization [20 3 and signal processing 9].
The leading methods to solve 1 are first-order algorithms such as stochastic gradient descent (SGD) 28 and stochastic variance-reduced methods 14
32 the implementation of
'Equal Contribution. Correspondence Kun Yuan
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Table 1: Number of individual gradient evaluations needed by each algorithm to reach an e-accurate solution. Notation (-) hides logarithmic factors. Error metrics (E) (E)) and (E)l x are used for convex and strongly convex problems, respectively.
Algorithm
Supp. Prox
Sampling
Asmp
Convex
Strongly Convex
Prox-GD
Yes
Full-batch
F(x)
onn
O(n log(
SGD 22
No
Cyclic
f((2)
(((
((n( Je)
SGD 22
No
RR
f((2)
(())())
((VT()))
PSGD 21
Yes
RR
f((x)
O(n( [ ve)
PIAG 35
Yes
Cyclic/RR
F(x)
O(n" log(
AVRG 37
No
RR
f((T)
(2(( log( (b))
SAGA 33
Yes
Cyclic
f((x)
O(n²
O(n log(
SVRG 33
Yes
Cyclic
f((2)
O(n
On log(:))
DIAG 23
No
Cyclic
f((T)
O(n log()))
Cyc. Cord. Upd 5
Yes
Cyclic/RR
f((a)
O(n2 !
O(n( (( log (o)(
SVRG [8]
No
Cyclic/RR
F(x)
0(n
O(n(5)) log(t))
SVRG [8
No
RR
F(x)
0(n4)
O(n log {))
SVRG 18
No
RR
f((x)
O(n (
O( log(?
Prox- Mox-DDinito (Ours)
Yes
RR
f((x)
(n
O( ())(
Prox-DFinito (Ours)
Yes
worst cyc. order
f((a)
Ó(n
Oin log(t))
Prox-DFise (Ours)
Yes
best cyc. order
Maa)
o
Ón log( )
The "Assumption" column indicates the scope of smoothness and strong convexity. where F(x) means smoothness and strong convexity in the average and fxxx assumes smoothness and strong convexity for each summand function.
[8] is an independent and concurrent work.
1 This complexity is attained under big data regime: n n> (
$ This complexity can be attained in highly heterogeneous scenario, see details Seo 4.2
these methods, each f. (x) can be sampled either with or without replacement. Withou--replaemennt sampling draws each fz() exactly once during an epoch, which is numerically faster than with- replacement sampling and more cache-friendly; see the experiments in [T 38 37 5] This has triggered significant interests in understanding the theory behind without-replacement sampling.
Among the most popular without-replacement approaches are cyclic sampling, random reshuffling. and shuffling-once. Cyclic sampling draws the samples in cyclic order. Random reshuffling reorders samples the beginning of each sample epoch. The third approach, however, shuffles data only once before the training begins. Without-replacement sampling have been extensively studied for SGD. was established in 1 [8
22 24) that without--relaceemen sampling enables SGD with faster convergence For example, it was proved that without-replacemmnt sampling speed up SGD from (11kk) to Ö(1/k²) (where k is the iteration) for strongly-convex costs in [2), and (1/2:1/22 (11kk) for the convex costs in [24 22 33 establishes a tight lower bound for random reshuffling SGD. Recent works (27 22 close the gap between upper and lower bounds. Authors of [22) also analyzes without-replacemeet SGD with non-convex costs.
11
mniform-iid-sapllie
In contrast to the mature results SGD, pariance-reduction under sithout-replacement sampling are less understood. Variance reduction strategies construct stochastic gradient estimators with vanishing gradient variance, which allows for much larger learning rate and henee speed up training process. Variance reduction under without-replacement sampling is difficult to analyze. In the strongly convex provide linear convergence guarantees for SVRG/SAGA with random reshuffling, but the rates are worse than full-batch gradient descent (GD). Authors of [35 23 improved the rate so that it can match with GD. In convex scenario, existing rates for without-replacmmen sampling with variance reduction, except for the rate established in independent and concurrent work (18),
scenario, [37 33

---

are still far worse than GD [33 51, see Table Furthermore, no existing rates for variance reduction under sethout-replacement sampling orders, in either convex or strongly convex scenarios, can match those under uniform-iid sifffrrm-idd-ampling which are essentially sample-size independent. There is clear gap between the known convergence rates and superior practical performance for without-replacement sampling with variance reduction.
1.1
Main results
This paper narrows such gap by providing convergence analysis and rates for proximal DFinito, proximal damped variant of Finito/MISO 7 17 26), which is a well-known variance reduction algorithm, under without-replacement sampling orders. Our main achieved results are:
We develop a proximal damped variant of Finito/MISO called Prox-DFinito and establish its gradient complexities with random reshuffling, cyclic sampling, and shuffling-one under both convex and strongly convex scenarios. All these rates match with gradient descent, and are state-of-the-art (up to logarithm factors) compared to existing results for without--eplaceemen sampling with variance-reduction,, see Table T
Our novel analysis can gauge how cyclic order will influence the rate of Prox-DFinito with cyclic sampling. This allows us to identify the optimal cyclic sampling ordering. Prox- DFinito with optimal eyclic sampling, in the highly data-heterogeneouus scenario, can attain a sample-size-ing -iizeiieddeeeeeent convergence rate, which is the first result, to our knowledge, that match with uniform-iie -iiioonpiid-----iinnggn-- with variance reduction in certain scenarios. We also propose a numerical method to discover the optimal cyclic ordering cheaply.
1.2 Other related works
Our analysis on cyclic sampling is novel. Most existing analyses unify random reshuffling and cyclic sampling into the same framework; see the SGD analysis in [I], the veriance-reduction analysis in [10 36 23 37 and the coordinate-updatt analysis in [5] These analyses are primarily based
on the "sampled-once-perr -ere-ooe-eppppph""" property and do not analyze the orders within each epoch, so
they do not distinguish cyclic sampling from random reshuffling in analysis. [16] finds that random reshuffling SGD is basically the average over all cyclic sampling trials. This implies cyclic sampling can outperform random reshuffling with a well-designed sampling order. However, [16] does not discuss how much better cyclic sampling can outperform random reshuffling and how to achieve such cyclic order. Different from existing literatures, our analysis introduces an order-specific norm to gauge how cyclic sampling performs with different fixed orders. With such norm, we are able to clarify the worst-case and best-case performance of variance reduction with cyclic sampling.
Simultaneously and independently, a recent work also provided an improved rates for variance reduction under without-replacemenn sampling orders that can match with gradient descent. However, [8] does not discuss whether and when variance reduction with replacement sampling can match with uniform sampling. In addition,
[18) studies SVRG while this paper studies Finito/MISO. The convergence analyses in these two works are very different. The detailed comparison between this work and [8] can be referred to Sec. 3.3
1.3 Notations
Throughout the paper we let col(f1, xn} denote column vector formed by stacking "1, Zy We let [n] = (1,-..,,, n2 and define the proximal operator as
+ 1 -1y--=13 1=]
prox po (x) == arg min ((v) yERd
which is single-valued when is convex, closed and proper. In general. we say is an operator and write A: : X' + y if A maps each point in space X' to another space y. So A(x) E y for all a E X. For simplicity, we write Ax A(x) and A Bx A(B(x)) for operator composition.
Cyclic sampling. We define π := (11) T (2).. (2)..... (n)) as an arbitrary determined permutation of sample indexes. The order is fixed throughout the entire learning process under cyclic sampling.
Random reshuffling. When starting each epoch, random permutation T = (r(1), (2), 7 T(n)) is generated to specify the order to take samples. Let Tk denote the permutation of the k-th epoch.
3

---

Algorithm Prox-DFinito
Input: 20 = 15 Σ 2i step-size a, and 0 E (0, 1);
for epoch k == 1, do
for iteration 1.
kn + 2, 2, . 1)n do
-'-1= -r -r
Pick it with some rule;
Update z4, and Œ according
4a and (5)
end for
(k+1)n (1 (1-0)==m + Oz (k+1)n 1)n for any i E [n]:
damping step damping step
z(k+1)n (1 0)=hn + 0z(h+))m;
end for
2 Proximal Finito/MISO with Damping
The proximal gradient method to solve problem 1
x. (ix'sxx'')
[
(3a)
x² = prox,
(3b)
12
To avoid the global average that passes over all samples, we propose to update one 2; per iteration:
(4a)
i i
x² prox.r or
(4b)
When is invoked with uniform-iid-sampllee
and r(x) 0, algorithm (4a)
(4b)
reduces to
FinIto/MISO 17 17). When i, is invoked with cyclic sampling and r(z) = 0. algorithm (4a
(4b)
reduces DIAG [23 and WPG [19. We let zt E. 2f. The update (4a) yields
= (=f, - 1/n.
This update can be finished with (d) operations if {- are stored with O(nd) memory. Further- more, to increase robustness and simplify the convergence analysis, we impose a damping step to z; and when each epoch finishes. The proximal damped Finito/MISO method is listed in Algorithm I
Note that the damping step does not incur additional memory requirements. A more practical implementation of Algorithm Tis referred to Algorithm 3 in Appendix A
2.1 Fixed-point recursion reformulation
Algorithm
4a 4b can be reformulated into fixed-poing recursion in {2,) Such a fixed-point
recursion will be utilized throughout the paper. To proceed, we define z = col ... =.. E RRdd
and introduce the average operator AA: 1nd + Rd Az Σn 2.. We further define the i-th block coordinate operator T, 1nd - [nd as
-ol= ... (I-aVfi prox (Az), ... }
where I denotes the identity mapping. When applying Tr, it is noted that the i-th block coordinate in # is updated while the others remain unchanged.
Proposition 1. oFinito with fixed cyclic sampling order is equivalent to the following fixed-point recursion (see proof in Appendix B.T)
(k+1)m k) + kT
(6)
where Tx TT((p) .... Ta(1)- Furthermore, variable x' can be recovered by
x' prox,r Az = 0, 2,.

---

Similar result also hold for random reshuffling scenario.
Proposition 2. Frox-DFime with random reshuffling is equivalent to
2 (k+1) = = 0)z + =T z
(8)
where Tr. = (Te( .... T Furthermore, variable x² can be recovered by following
2.2 Optimality condition
Assume there exists x² that minimizes F(x) r(x)), i.e., 0 E (F(x*) + 0r(x))) Then the relation between the minimizer x² and the fixed-point x" of recursion (6) and ( can be characterized as: Proposition 3. x² minimizes F(x) +r(x) afd only if there is z" that (proof in Appendix B.2
x' =Tæ', ViE [n],
(9)
x² = =rox o Az"
(10)
Remark 1. If x² minimizes F(x) r(x), holds from and (10) that 27 = (V-oV prox (Az') x² <VV((x")) for any e [m]]
2.3 An order-specific norm
To gauge the influence of different sampling orders, now introduce order-specific norm.
Definition 1. Given x = col 21, .. =n3 E nd and a fixed cyclic order n, we define
2 +- =
1 |= +
|| 11
as the r-specific norm.
Note that the coefficients in || are delicately designed for technical reasons (see Lemma and its proof in the appendix). The order-specific norm facilitates the performance comparison between two orderings.
For two different cyclic orders π and n', it generally holds that || * 12|2.-
Convergence Analysis
In this section establish the convergence rate of Prox-DFinito with eyclic sampling and random reshuffling in convex and strongly convex scenarios, respectively.
3.1 The convex scenario
We first study the convex scenario under the following assumption: Assumption (Convex). Each function f((x) is convex and L-smooth.
worth noting that the convergence results on eyclic sampling and random reshuffling for the
convex scenario are quite limited except for 22 33
[8]
Cyclic sampling and shuffting-onee. We first introduce the following lemma showing that Tg is non-expansive with respect to || [.. which is fundamental to the convergence analysis.
Lemma 1. Under Assumption if step-size 0 < a 2. and the data is sampled with fixed cyclic order it holds that (see proof in Appendix C.I
T T v.
||u
v12 Vu, E Rnd.
(1I)
Recall (6) that the sequence 2 kn is generated through z (k+1))n (km), Since S, -1--0) and Ta is non-expansive,
can prove the distance || -==t)) will converge to sublinearly: Lemma 2. Under Assumption if step-size 0 < a < 2, and the data is sampled with fixed cyclic order it holds for any k 0. that (see proof in Appendix
0
|| (b+1)) -2 1 |
<
1| -x-12
(12)
(k: + 1)(1 0)
where 0 (0, 1) is the damping parameter.
5

---

With Lemma and the relation between z' and x" in 77. we can establish the convergence rate:
Theorem 1. Under Assumption I if step-size 0 < a S
2 and the data is sampled with a fixed cyclic
I.
order it holds that (see proof in Appendix
CT?
min geOr(zen)
VF( +gll (k+1)0(1-0)
(13)
where A E (0, 1) and C= C=(2) )² log(n)+1 120 11.
Remark 2. Inspired by reference NoV, one can take expectation over cyclic order a to obtain the convergence rate of Prox-DFinit shuffled once before training begins (with C
13
2 2 (a+ (logg()) aL
|| 113)
2n
CL²
E min (E@r(a)))
[VF +gl? (k+1))(1-0)
(14)
Random reshuffling, We let Th denote the sampling order used in the k-th epoch. Apparently, Tıe is a uniformly distributed random variable with n! realizations. With the similar analysis technique, we can also establish the convergence rate under random reshuffling in the expectation sense.
Theorem 2. Under Assumption 7 if step-size < a I reshuffling, holds that (see proof Appendix D.2
2 and data is sampled with random
CI2
E
min gE0r(ak))
IVF a
+
(15)
(k+1)0(118)
where 0 E 10 and C = ((3 3ax
z" 1²
Comparing 15 with (13). is observed that random reshuffling replaces the constant ||> - =" by || 2 and removes the log(n) term in the upper bound.
3.2 The strongly convex scenario
In this subsection, we study the convergence rate Prox-DFinita under the following assumption: Assumption (Strongly Convex). Each function fi(x) is u-strongly convex and L-smooth.
Theorem 3. Under Assumption if step-size () < a S atL it holds that (see proof in Appendix E
2
(E) |0.k x=1 s (1- 20cu
n ) ycc
(16)
where 0 E (0,1) and
log (+)
12 2 with N-order cyclic sampling,
2" with random reshuffling.
Note when 0 - 1, Prox-DFinito actually reaches the best performance, damping is essentially not necessary strongly convex scenario.
Remark 3.
3.3 Comparison with the existing results
Recalling ||>|| = Ei
(x 12, it holds that
1 |= < || < 1|11,, Vz,
(17)
For fair comparison with existing works, consider the worst case performance of cyclic sampling
by relaxing ||z" zz 1| to its upper bound ||=0 2 1|2 Letting a O(1/LL /L), 0 1/2 and assuming
|| 2" 2 (1), the convergence rates derived in Theorems 3 reduce to
C-Cyclic = =Ö(L2/A).
C-RR = O(L2/k)
SC-Cyelic = ō((1 1//K)*,
SC-RR = 0(11-1kk)

---

where "C" denotes "convex" and "SC" denotes "strongly convex", n L/p, and Ö(-) hides the (n)(n) factor. Note that all rates are in the epoch-wise sense. These rates can be translated into the the gradient complexity (equivalent to sample complexity) of Prox-DFinito to reach an 6-accurate solution. The comparison with existing works are listed in Table
Different metrics. Except for [3] and our Prox-DFinito algorithm whose convergence analyses are based on the gradient norm in the convex and smooth scenario, results in other references are based on function value metric (i.e., objective error F(x F(x*) )). The function value metric can imply the gradient norm metric, but not always vice versa. To comapre Prox-DFinito with other established results in the same metric, we have to transform the rates in other references into the gradient norm metric. The comparison is listed in Table When the gradient norm metric is used, we observe that the rates of Prox-DFinito match that with gradient descent, and are state-of-the-art compared to the existing results. However, the rate of Prox-DFinito in terms of the function value is not known yet (this unknown rate may end up being worse than those of the other methods).
For the non-smooth scenario, the functional suboptimality F(r) + rr)z)
metric minge [V + 0r(z)]l2 may not be bounded by F(x*) r(=*). and hence Prox-DFinito results not
x
comparable with those in [21 35
37 33 18). The results listed in Table are all for the smooth
scenario of 22 33 37 33 18), and we use "Support Prox" to indicate whether the results cover the
non-smooth scenario or not.
Assumption scope. Except for references [8 35 and Proximal GD algorithm whose convergence analyses are conducted by assuming the average of each function to be L-smooth (and perhaps j-strongly convex), results in other references are based on stronger assumption that each summand function to be L-smooth (and perhaps ju-strongly convex). Note that L. can be much smaller than L sometimes. To compare [88 (35 and Proximal GD with other references under the same assumption, we let each L = L in Table 1 However, it worth noting that when each L; is drastically different from each other and can be evaluated precisely, the results relying on L (e.g.. 35 and [8] much better than the results established in this work.
can be
Comparison with GD. It is observed from Table I that Prox-DFinito with cyclic sampling or random reshuffling is no-worse than Proximal GD. is the first no-worse-Ihun-GD result, besides the independent and concurrent work [18] that covers both the non-smooth and the convex scenarios for variance- rerrutce-reduction methods under wiihoottreplaccmmett sampling orders. The pioneering work DIAG p 23 established similar result only for smooth and strongly-convex problems
Comparison with RR/CS methods. Prox-DFinito achieves the nearly sfate-of-the-art gradient complexity in both convex and strongly convex scenarios (except for the convex and smooth case due to the weaker metric adopted) among known the finite-sum optimization problem ([). see Table [ In addition, it is worth noting that in Table [ algorithms of [33 35| 23 and our Prox-DFinito have an O(d)) memory requirement while others only need (d) memory. In other words, Prox-DFinite is memory-costly in spite of its superior theoretical convergence rate and sample complexity.
stochastic approaches to solving
Comparison with uniform- -iamspiin-- methods. It is known that uniform- saafpliig variance- reduction can achieve an O O(max(n. L/u} log(1/c) sample complexity for strongly convex problems
14 26 6 and O /c) (when using metric (1v)F())'' for convex problems [26). In other words, these uniform- comoooinnnmmingggggggm methods have sample complexities that are independent of sample size n. Our achieved results (and other existing results listed in Table and (18) for random reshuffling or worst- case cyclic sampling cannot match with uniform maiforr--ampling yet. However, this paper establishes that Prox-DFinito with the optimal cyclic order, in the highly data-heterogeneous scenario, can achieve an O(L2// /c) sample complexity in the convex scenario, which matches with uniform-sanl sampling up to a log(n)) factor, see the detailed discussion in Sec. 4 To our best knowledge, it is the first result, at least in certain scenarios, that variance reduction under without--relaaeemen sampling orders can match with its miiform-sampiing counterpart in terms of their sample complexity upper bound. Nevertheless, it still remains unclear how to close the gap in sample complexity between variance reduction under without- without-replacemmen replacement sampling and uniform sampling in the more general settings (i.e., settings other than highly hata-heterogeneouss scenario).
WWiile DIAG is established to outperform gradient descent in 23 we find its convergence rate is still on the same order of GD. Its superiority to GD comes from the constant improvement, not order improvement.
7

---

4
Optimal Cyelic Sampling Order
See 3.3 examines the worst gradient complexity of Prox-DFinito with cyclic sampling, which is worse than random reshuffling by a factor of log(n) in both convex and strongly convex scenarios. In this section we examine how
performs with optimal cyclic sampling.
4.1 Optimal cyclic sampling
Given sample size n, step-size a, epoch index k; and constants L, fa and 0, it is derived from Theorem that the rate of n-order cyclic sampling is determined by constant
||" 201
x(1)
7 11
(18)
We define the corresponding optimal cyclic order as follows. Definition 2. An optimal cyclic sampling order πt" of Prox-DFimice is defined as
π² arg min 2" )
(19)
Such an optimal cyclic order can be identified as follows (see proof in Appendix Proposition 4. The optimal cyclic order for Frox-DFinito is the reverse order of {1la Remark 4 (IMPORTANCE INDICATOR). Proposition 4 implies that ||2|- 222-2a =
2, 1
can be used as importance indicator of sample i. Recall 2 = x² a f((x)) from Remark [ If 2f is initialized as O, the importance indicator sample reduces to || V fx("))1 which is determined by
both x² and V fa(x)). If 2 is initialized close to x², we then have |2 - 2," 12 = a² f((x**) In other words. the importance of sample can be measured by f. (x*) which is consistent with the imporiance indicator in uniform-itd-smppen -id---i-p---ingggggg [4] 40
4.2 Optimal cyclic sampling can achieve samplesiin-indepeedennt complexity
Recall from Theorem I that the sample complexity of Prox-DFinito with cyclic sampling in the convex scenario is determined by (log(n)/n) x²) ==" =1 From (17p we have
|| - 11 - 200 11 S | 11 Vz,
(20)
In Sec. 3.3 we considered the worst case performance of cyclic sampling. i... we bound || x ||
with its upper bound ||200 -=11 1= 2 In this section, will examine the best case performance using the lower bound || 2 1| / and provide a scenario in which such best case performance is achievable. We assume
||00 x1 112 /n O(1) in previous sections.
Proposition 5. Given fixed constants n, a, k. 8, L, and optimal cyelic order x², if the condition
12 - x" -
2 2+ -0
(21)
holds, then Prox-DFinito with optimal cyclic sampling achieves sample complexity ((T,2/e).
The above proposition can be proved by directly substituting 21 into Theorem
In the following.
we discuss a data-heterogeneous scenario in which relation 21 holds.
A data-heterogenneous scenario. To this end, let x= colfx* ... ,x* and vf(=*) col (f"()") ....., fx())), it follows from Remark [ that x" = x= - -Vf((*) If we set 00 = 0 (which is common in the implementation) and = 1/T. (the theoretically sug- gested step-size), it then holds that =| 1/ = || //T(a)/I[ Next, we assume || 1/ ||.- Vf((*))/L [/ ni (0 < < 1) holds. Under such assumption, the
optimal cyclic order will be π
21, ... .n). Now we examine || x= 1... and || z" ?
1
3
Σ
i
1
3
By
when n is large, which implies that ||
-11 ((/n)) since 3 is a constant independent of n. With Proposition 5 we know Prox-DFinito with optimal cyclic sampling can achieve Ö(T.2ee) which is independent of sample size n. Note that [[ = nyfi-1 implies data-heterogeneouus scenario where 3 can roughly gauge the variety of data samples.
8

---

CIFAR:10
MNIST
300
RR. RR.AVRE
Cye-Sv9G
Cyc-VVR
RR.SAGA
10"1
1074
Cyn-AGA
30-1
SAGA
20
10
10-1
10:1
60
60
80
100
100
10:10
20
80
552
150
10:12
PGrmdlents
KGrodienss 20
arondllett kn
Comparison with SVRG and SAGA under without-reelaaemment sampling orders using theoretical step sizes on Cifar-10 (A 0.005), MNIST 0.008), and Covtype 0.05). The y-axis indicates the versus graadient evaluations/n.
Figure 1:
relative mean-square error (E) || x" / [|=|=>> x
4.3 Adaptive importance reshuffling
The optimal cyclic order decided by Proposition
Algorithm 2 Adaptive Importance Reshuffling
q is not practical since the importance indicator
Initialize: ( = || =012 for E [n];
of each sample depends on the unknown 2
xx V fx("). This problem can be overcome by replacing 2 by its estimate 2,th, which leads an adaptive importance reshuffling strategy.
for epoch k = 0, 1, do
Reshuffle [r]] based on the vector wx
Update Prox-DFinito epoch:
Update w+1 according to (22):
We introduce w E IR" as an importance indicat- end for ing vector with each element w; indicating the
importance of sample and initialized as w (i) = = 11, Vi E [n]. In the k-th epoch, we draw sample earlier (i) () is larger. After the k-th epoch, w will be updated as
wh R+1 = - 7)00 (1) + + (k+1)m
(22)
where E [nx] and 7 E (0, 1) is fixed damping parameter. Suppose = -> 27, the above recursion
will guarantee w (i) - 1|ق| 2, 12. other words, the order decided by w will gradually adapt to
the optimal cyclic order as k increases. Since the order decided by importance changes from epoch to
epoch, we call this approach adaptive importance reshuffling and list it in Algorithm 2 We provide the convergence guarantees of the adaptive importance reshuffling method in Appendix
Numerical Experiments
5.1 Comparison with SVRG and SAGA under without-replacemmet sampling orders
In this experiment, we compare DFinito with SVRG [14 and SAGA 7 under without-replacemmet
sampling (RR, cyclic sampling). We consider a similar setting as [18 Figure 2), where all step sizes
chosen the theoretically optimal one, see Table 2 in Appendix H We run experiments for the
regularized logistic regression problem, i.c. problem T with fa log (1 + exp( (w,, x)))
|>||² with three widely-used datasets: CIFAR-10 15). MNIST S and COVTYPE 29 This
x. From Figure I. it is observed that DFinito outperforms SVRG and SAGA in terms of gradient complexity under without-replaccmment sampling orders with their best-known theoretical rates. The comparison with SVRG and SAGA with the practically optimal step sizes Appendix
problem is T.-smooth and j-stroongly convex with I, = Amar (WTW) + À and
5.2 DFinito with cyclic sampling
Justification of the optimal cyelic sampling order. To justify the optimal cyclic sampling order " suggested in Proposition 4 we test DFinito with eight arbitrarily cyclic orders, and compare them with the optimal cyclic ordering π as well as the adaptive importance reshuffling method (Algorithm{)). To make the comparison distinguishable, we construct a least square problem with
heterogeneous data samples with n 200, d 50, L 100, μ 10-2 (see Appendix 1 for the constructed problem). The constructed problem is with
||= -=--==10 1|3
2113- 0.006 when
= = 0, T0 0, and a 3 that the optimal cyclic sampling achieves the fastest convergence rate. Furthermore, the adaptive
1 which is close to 1/n = 0.005. In the left plot in Fig. 2 it is observed

---

Oz
Dilnee opt Gyt.
05
Aosp
10
10"
Firtey List Surpl
Resmiee Enoo
Rebetvee
10
10
Arop
10"10
10"10
60
100
150
200
200
800
600
1000
1600
2000
2600
3003
#Gradlentemm
@Grstientern
Figure 2: Left: Performance of DFinito under different sampling orders. Error metric: || x //1/"///>" x=1
Right: Comparison of DFinito under -cyclli sampling and uniform sampling highly heterogeneous scenario. Error metric: [[V(())) /IVF("))
shuffling method can match with the optimal cyclic ordering. These observations are consistent with theoretical results derived in Sec. 4.2 and 4.3
Optimal cyclic sampling can achieve sumplesiin-indeeeenden complexity. It is established in (26) that Finito with uniform-iid-samplee can achieve nn-independent gradient complexity with n In this experiment, we compare DFinito (a = ? with Finito under uniform sampling (8 SL.
runs, a = s in convex and highly heterogeneous scenario (p = O())). The constructed problem with = 500, d = 20, L = 0.3, 0 = 0.5 and || - = 10000
S i S n (see detailed initialization in Appendix D We also depict DFinito with randon-reshuffling (8 runs) another baseline. In the right plot of Figure 2 is observed that the convergence curve of DFinito with -*-cyclic sampling matches with Finito with uniform sampling. This implies DFinito can achieve the same re-independent gradient complexity as Finito with uniform sampling.
5.3
More experiments
We conduct more experiments in Appendix D First, we compare DFinito with GD/SGD to justify its empirical superiority to these methods. Second, we validate how different data heterogeneity will influence optimal eyclic sampling. Third, we examine the performance of SVRG, SAGA, and DFinito under without/with-repllccmee sampling using grid-search (not theoretical) step sizes.
6 Conclusion and Discussion
This paper develops Prox-DFinin DFinito and analyzes its convergence rate under without- ceahout-replacement sampling in both convex and strongly convex scenarios. Our derived rates state-of-the-ae tf-ttr-art compared to existing results. In particular, this paper derives the best-case convergence rate for Prox- DFinito with cyclic sampling, which can be sample-size-ing -iie-iizze-dedeeenttt in the highly data-heterogeneouus scenario. future direction to close the gap in gradient complexity between variance reduction under without-replaceen and uniform- iifoorm-ii--aae -ii--dmmpppngg in the more general setting.
References
[1] L. Bottou. Curiously fast convergence of some stochastic gradient descent algorithms. In Proceedings of the symposium on learning and data science, Paris, volume 8, pages 2624-2633, 2009.
[2] L. Bottou, Curtis, and Nocedal. Optimization methods for large- scale machine learning. Siam Review, 60(2):223-3) 311, 2018.
[3] S. Boyd, N. Parikh, and E. Chu. Distributed optimization and statistical learning via the alternating direction method of multipliers. Now Publishers Inc, 2011.
[4] S. S. Chen, D. L. Donoho, and M. A. Saunders. Atomic decomposition by basis pursuit. SIAM review, 1391):129-159, 2001.
[5] Y. T. Chow, Wu, and W. Yin. Cyclic coordinate-update algorithms fixed-point problems: Analysis and applications. SIAM Journal Scientific Computing, A914): 2017.
10

---

[6] A. Defazio. F. Bach, and S. Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. arXiv preprint arXiv:1407.0202, 2014.
[7] A. Defazio, J. Domke, et al. Finito: A faster, permutable incremental gradient method for big data problems. In International Conference Machine Learning, pages 1125-1133, PMLR, 2014.
[8] L.. Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 1411)114 2012.
[9] D. L.. Donoho. Compressed sensing. IEEE Transactions information theory, 52(4):1229- I 1306, 2006.
[10] M. Gurbuzbalaban, A. Ozdaglar, and P. A. Parrilo. On the convergence rate of incremental aggreggated gradient algorithms. SIAM Journal on Optimization, ((12)):1335-048,, 2017.
[11] M. Gurbuzbalaban, A. Ozdaglar, and P. A. Parrilo. Why random reshuffling beats stochastic gradient descent. Muthematical Programming, pages 1-36, 2019.
[12] J. Haochen and S. Sra. Random shuffling beats sgd after finite epochs. In International Conference on Machine Learning, pages 2624-2633, PMLR, 2019.
[13] X. Huang, E. K. Ryu, and W. Yin. Tight coefficients of averaged operators via scaled relative graph. Journal of Mathematical Analysis and Applications, 492(1))1 2020.
[14] R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26:315-323, 2013.
[15] A. Krizhevsky. Learning multiple layers of features from tiny images. 2009.
[16] S. Ma and Y. Zhou. Understanding the impact of model incoherence convergence of incremental sgd with random reshuffle. International Conference on Machine Learning. pages 5574-6574. PMLR, 2020.
[17] Mairal. Incremental majorization
majorzzation-miiiizzztiin minimization optimization with application to large-scale machine learning. SIAM Journal on Optimization, 25(2):829-855) 2015.
[18] G. Malinovsky, Sailanbayev, and Richtárik. Random reshufiling with variance reduction: New analysis and better rates. arXiv preprint arXiv:2104.09342 2021.
[19] X. Mao, Y. Gu, and W. Yin. Walk proximal gradient: An energy-efficient algorithm for consensus optimization. IEEE Internet of Things Journal, ((2):2048-206) 2018.
[20] G. Matcos, A. Bazerque, and G. B. Giannakis. Distributed sparse linear regression. IEEE Transactions on Signal Processing, 58 58(10))5262-5276, 2010.
[21] K. Mishchenko, A. Khaled, and Richtárik. Proximal and federated random reshuffling. arXiv preprint arXiv:2 2021.
[22] K. Mishchenko, A. Khaled Ragab Bayoumi, and P. Richtárik. Random reshuffling: Simple analysis with vast improvements. Advances in Neural Information Processing Systems, 33, 2020.
[23] A. Mokhtari, M. Gurbuzbalaban, and A. Ribeiro. Surpassing gradient descent provably: A eyclic incremental method with linear convergence rate. SIAM Journal on Optimization, 1222):142011447, 2018.
[24] D. Nagaraj, P. Jain, and P. Netrapalli. Sgd without replacement: Sharper rates for general smooth convex functions. In International Conference on Machine Learning, pages 4703-4711. PMLR, 2019.
[25] Y. Park and Ryu. Linear convergence of cyclic saga. Optimization Letters, 14(6):1583- 1598, 2020.
11

---

[26] X. Qian, A. Sailanbayev, K. Mishchenko, and P. Richtárik, Miso is making a comeback with better proofs and rates. arXiv preprint arXiv:1906.01477 01744, 2019.
[27] Rajput, A. Gupta, and D. Papailiopoulos. Closing the convergence gap of sgd without replacement. In International Conference on Machine Learning, pages 7964-7973, PMLR, 2020.
[28] H. Robbins and S. Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407) 1951.
[29] R. A. Rossi and N. K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015,
[30] E. K. Ryu, R. Hannah, and W. Yin. Scaled relative graph: Nonexpansive operators via 2d euclidean geometry. arXiv: Optimization and Control, 2019.
[31] I. Safran and O. Shamir. How good is sgd with random shuffling? In Conference on Learning Theory, pages 3250-3284 PMLR, 2020.
[32] M. Schmidt, N. Le Roux, and F. Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(1-2):33-122, 2017.
[33] T. Sun, Y. Sun, D. Li, and Q. Liao. General proximal incremental aggregated gradient algorithms: Better and novel results under general scheme. Advances in Neural Information Processing Systems, 32:996-1006, 2019.
[34] R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series (Methodological), 58(1):267-288 1996.
[35] N. D. Vanli, M. Gürbüizaalaban, and A. Ozdaglar. stronger convergence result on the proximal incremental aggregated gradient method. arXiv: Optimization and Control, 2016.
[36] N. D. Vanli, M. Gurbuzbalaban, and A. Ozdaglar. Global convergence rate of proximal incremental aggregated gradient methods. SIAM Journal on Optimization, 28(2):1222-1300, 2018.
[37] B. Ying, K. Yuan, and A. H. Sayed. Variance-reduced stochastic learning under random reshuffling. IEEE Transactions on Signal Processing, 08:133901444 1400, 2020.
[38] B. Ying, K. Yuan, S. Vlaski, and A. H. Sayed. Stochastic learning under random reshuffling with constant step-sizes. IEEE Transactions on Signal Processing. 67(2))474 2018.
[39] H.-F Yu, F.-L. Huang, and C.-J. Lin. Dual coordinate descent methods for logistic regression and maximum entropy models. Machine Learning. 85(1-2):41-75, 2011.
[40] K. Yuan, B. Ying. S. Vlaski, and A. Sayed. Stochastic gradient descent with finite samples sizes. 2016 IEEE 26th International Workshop on Machine Learning for Signal Processing (MLSP), pages 1-6, 2016.
[41] Zhao and T. Zhang. Stochastic optimization with importance sampling for regularized loss minimization, In international conference on machine learning, pages 1-9. PMLR, 2015.
12


Reviews:
[{"review_id": "zVPuYD4HAv", "reviewer": "Reviewer_dHKd", "summary": "This paper develops a proximal damped version of the Finito algorithm. The algorithm is proved to achieve the same convergence rate as proximal GD, for cyclic sampling, random reshuffling and shuffling-once versions of the algorithm. Further, the authors claim that this is the first* shuffling based variance reduction algorithm to achieve the convergence rate. The paper also gives a new norm that captures the optimality of sampling orders and provides a heuristic based on that for importance based reshuffling.\n\nBesides the theoretical results, the empirical results seem to suggest that the proposed algorithm is indeed faster than other variance reduction algorithms. \n\n*: The authors cite a concurrent work (Malinovsky et al.) that also achieves the same convergence rates for general convex functions, but the algorithms in the two papers are different.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "This paper proposes Prox-DFinito, which is a shuffling based variance reduction algorithm. \n\nThe theoretical results show that the cyclic sampling, random reshuffling and shuffling-once versions of the algorithm achieve the same convergence rate as GD (up to logarithmic factors) on general convex and strongly convex functions. The paper also proposes a new heuristic to get good sampling orders based on a new norm.\n\nOverall, the theoretical results look good and the empirical evaluation support the theory. \n\nA concern that I have is regarding the claim that the optimal cyclic sampling can achieve a sample complexity of $\\widetilde{O}(L^2/\\epsilon)$, which is independent of $n$. While this might indeed be correct, this might be slightly misleading. The fact is that without looking at all the $n$ functions at least once, good convergence cannot be achieved - consider the case where a fraction of the functions have minima very far away from others. Hence, even to determine the optimal cyclic order, at least $\\Omega(n)$ computation must be done. The authors should clarify this.\n\nThe empirical evaluation for the optimal cycling sampling order seems to be done on an artificial dataset of quadratics that share the same minima. This does not give sufficient indication to whether the proposed optimal cyclic sampling order would work in practice. Can the authors provide evaluation on real datasets? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. Please move the comparison done in Table 3, appendix K to the main paper.\n2. Please also provide plots for the test error of the evaluations done on MNIST, CIFAR-10 etc.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "yRI-LvhFLqw", "reviewer": "Reviewer_y5Mf", "summary": "The paper proposes a new method called Prox-DFinito based on the proximal Finito with without-replacement sampling. The authors derive complexity bounds for the proposed method in convex (for making the squared norm of the gradient small) and strongly convex cases (for making the squared distance to the solution small) that match under some additional assumptions the rate of Gradient Descent. Moreover, under additional assumptions on the objective function, the authors show sample-size independent bound in the convex case. The proofs are non-standard but clean and easy to follow. However, the paper has several strong weaknesses.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "## Strengths\n\n1. **Clarity.** The paper is clearly written and well-organized.\n\n2. **Interesting proofs.** The proofs of the theoretical results of the paper are non-standard and, therefore, valuable. In addition, the proofs are easy to follow and do not contain inaccuracies.\n\n## Weaknesses\n\n1. **Weak guarantees in the convex case.** In the convex case (i.e., all $f_i$ are convex), the authors establish complexity bounds ensuring that $\\text{dist}(\\|\\nabla F(x^{kn}) - \\partial r(x^{kn})\\|^2, 0) = \\min_{g\\in \\partial r(x^{kn})}\\|\\nabla f(x^{kn}) + g\\|^2 \\leq \\varepsilon$. In other papers and, in particular, in [18], bounds are obtained to ensure $F(x^{kn}) - F(x^*) \\leq \\varepsilon$ (no regularization). When the objective is convex and smooth it is possible that the gradient is small but functional suboptimality is huge. Moreover, it is more important to achieve small functional suboptimality rather than the small norm of the gradient. Although the proofs are interesting, the result in the convex case is not strong enough and cannot be directly compared with known results. The authors should clarify it in Table 1 since in the cited papers the bounds in the generally convex case are established for functional suboptimality, not for the squared gradient norm. Moreover, the authors should clarify what do they mean by such a comparison. In the non-proximal scenario, one can use classical inequality $\\|F(x)\\|^2 \\le 2L(F(x) - F(x^{*}))$, but there are no analogs of such inequality for the composite problems. This place should be carefully clarified.\n\n2. **Complexity bounds depend on $\\frac{1}{n}\\|\\mathcal{z}^0 - \\mathcal{z}^{*}\\|_{\\pi\\text{ or }2}^2$.** This norm has implicit dependence on the heterogeneity of local loss functions $f_i$. Indeed, if $\\mathcal{z}^0$ is close to $x^*$, then for RR $C \\sim \\frac{\\alpha^2}{n}\\sum_{i=1}^n\\|\\nabla f_i(x^{*})\\|$ where $C$ is the factor appearing in all upper bounds.In other words, even if the starting point is extremely close to the solution the constant $C$ can be large. This observation immediately implies that all derived rates in the paper can be arbitrarily worse than known results. In contrast, the concurrent work [18] does not have this issue.\n\n3. **Results are weaker than state-of-the-art ones.** In view of the first weakness, the complexity bounds in the convex case are weaker by default since they do not provide guarantees for the functional suboptimality. Next, in the strongly convex case, much tighter results are given in [35], where the authors use $L$ being the average of individual smoothness constants (that can be almost $n$ times smaller than the worst one) and $\\mu$ being the strong convexity constant of the average and do not require individual loss functions to be strongly convex. In contrast, this paper uses the worst $L$ for all summands and relies on the assumption that all $f_i$ are $\\mu$-strongly convex. Moreover, in view of weakness 2, it is even impossible to fairly compare the results without additional assumptions.\n\n4. **Incomplete comparison with the related work.** The paper tries to create an impression that the obtained results are the current state-of-the-art. However, it is not true. As it was mentioned earlier, the derived results are weaker than the state-of-the-art ones but the authors do not write about such important details. Moreover, since [18] is the recent concurrent work, the authors should add more details in the main part of the paper. First of all, the rates from [18] should be added in Table 1 (otherwise it creates a biased impression). Next, the authors should explicitly write that the results in the convex case from [18] are stronger (see weakness 1). Moreover, [18] contains some results for the \"Big Data regime\" establishing $O(n \\frac{L}{\\mu} \\log \\frac{1}{\\varepsilon})$ complexity in the strongly convex case and it is shown without assuming strong convexity of each summand. Finally, rates from [18] do not have the issue described in weakness 2. Therefore, the authors should write about all of these details in the paper and at least briefly mention them somewhere in the main part.\n\n## Questions and comments\n\n1. **Table 1, results from [33] and [5]:** The bounds are strange since their \"physical dimension\" is incorrect. That is, the complexity should be dimensionless quantity whereas $\\frac{L^2}{\\mu}$ and $\\frac{L}{\\mu^2}$ are not. Please, correct these bounds.\n\n2. **line 42, \"accelerated\":** This word has a certain meaning (Nesterov's acceleration) in the optimization literature that differs from what the authors want to say (e.g., see d'Aspremont, Alexandre, Damien Scieur, and Adrien Taylor. \"Acceleration methods.\" arXiv preprint arXiv:2101.09545 (2021).). The authors should rewrite the sentence.\n\n3. **lines 46-47, \"In the generally convex scenario, existing rates for without-replacement sampling with variance reduction are still far worse than GD\":** this is not true because [18] exists.\n\n4. **line 101, \"Note that the damping step does not incur additional memory requirements\":** In theory, it is still $O(nd)$, but in practice, there is a big difference between $nd$ and $2nd$.\n\n5. **Algorithm 3:** The algorithm is not equivalent to Algorithm 1.\n\n6. **inequality (54), the last line:** the identity is not correct since $\\sum_{t=0}^{j-i-1} \\neq \\left(1 + \\frac{1}{n}\\right)^{j-i-1}$. However, one can stop one line earlier since it is not important for the next arguments in the proof.\n\n## Comment after the rebuttal\n\nI thank the authors for their detailed response. I have read it carefully.\n\n**Bounds in the convex case.** Both authors and me agree that bounds for the norm of the gradient are weaker than bounds for functional suboptimality, so my concern is still valid. However, I acknowledge that before this work and [18], which is written independently and has different analysis, are the first results for VR methods with without-replacement sampling that match the rate of GD in the convex case under the assumption that all $f_i$ and $F$ have the same smoothness constant. Moreover, in the \"highly-heterogeneous scenario,\" the rate derived in this paper is independent of $n$ that I find quite interesting.\n\n**On the $\\frac{1}{n}\\|z^0 - z^*\\|^2$.** Indeed, if $z_i^0 = x^0 - \\alpha \\nabla f_i(x^0)$, then there is no issue. I suggest the authors write about this initialization in the main text. I think it is important for the comparison with other results.\n\n**Revised Table 1 and clarifications about the comparison with other works.** Now, these parts are much more transparent for the readers. I believe these corrections are very important.\n\n**On Algorithm 3.** Thank you for the clarifications. Now I see the equivalence. Initially, I was confused because of the difference in the formulas for $z_{i_t}^t$ in Algorithms 1 and 3. However, after your clarifications, I realized that the two methods are indeed equivalent. I suggest the authors add these clarifications to the paper.\n\nOverall, although the paper has several limitations, it does contain some valuable contributions. In particular, the idea of using order-specific norm in the analysis is of separate interest. Taking all these aspects into account, I decided to increase my score from 4 to 6. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12 hours"}, "extra_text": {}}, {"review_id": "iIalgQtGN7", "reviewer": "Reviewer_zgXx", "summary": "In this paper, the authors study a stochastic variance reduced method under sampling rules that are without replacement for smooth and non-smooth, convex and strongly convex objectives. More precisely :\n- they develop a proximal method call Prox-DFinito for which they study convergence rates for random reshuffling, cyclic and shuffling once samplings\n- in the cyclic sampling, they derive an optimal fixed ordering (and a practical adaptive variant which do not require the knowledge of $z^*$\n- Finally, the authors highlight the fact that, when assuming data heterogeneity, their study lead to a convergence rate independent of the number of data samples. This was up until now just known for iid sampling.    \n\n ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "First of all, the paper is very well written (especially the background detailing precious works), very very few typos, main proofs seem correct.\n\nMinor comments which are just my opinion:\n- 1) I do not find that \"generally convex\" is a proper way to describe a function which is just \"convex\". It's not standard and reading it quickly might make the reader think it's more general than convexity.\n- 2) Lines 37 and 39 : i would not start a sentence with a ref, I would write \"Authors of [XX] establish ...\"\n- 3) Prop. 1 & 3: I would not put \"(proof in Appendix XX)\" inside the proposition but before or after. \n\n\nMinor/medium importance comments:\n- 4) Could you precise in Table 1 that you assume that the $f_i$'s are strongly convex (not $F$), it makes easier the comparison with [18]\n- 5) Eq. (13) : I don't know what is the squared norm of a subdifferential. I think it's not standard. I would rewrite this to make it more mathematically correct if you meant, \"the squared norm of all elements in the subdifferential\".  \n- 6) Remark 3: typo \"One can takING\" -> \"take\"\n- 7) maybe it is worth citing again [16] in Remark 3.\n- 8) line 154: why \"Apparently\" ? It makes the sentence look potentially false\n- 9) line 232, 2 typos: $==$ and a word is missing before the parenthesis\n- 10) line 242, typo : written $\\nabla f (x^*)$, it should be $\\nabla f_i (x^*)$ instead\n\nMajor comments:\n- 11) Could you clearly explain and highlight the fact that Table 1 is comparing number of gradients evaluations (total complexity) to reach $\\epsilon$-solutions, it makes easier the comparison with Table 1 in[18]\n- 12) I find that the rate of [18] are missing in table 1. Even if an entire section in the appendix describe the differences, we need a more detailed comparison in the main text instead of the short 3 lines at the end of subsection 1.2. Giving the pros and cons of each method (and clearly stating the difference in memory $\\mathcal{O} (nd)$ (yours) vs $\\mathcal{O} (d)$ ([18])).\n- 13) Lines 98-100: It's not clearly explained how you came up with this damping parameter. Why do you need it ?\n\nMajor comments on Appendix K:\n- 14) You do not discuss the \"Big Data regime\" + strong convexity for which the authors of [18] clearly have a gain : in their terms they get an iteration complexity of $\\mathcal{O} (\\frac{L}{\\mu} \\log (\\frac{1}{\\epsilon}))$. This assumption lead to the same total complexity than yours for RR and worst cyclic order : $\\mathcal{O} (n \\frac{L}{\\mu} \\log (\\frac{1}{\\epsilon}))$ right ?\n- 15) Could you precise that your memory cost is $n$ times the one for SVRG ?\n\nQuestions :\n- 16) Did you come with the idea of this \"order-specific norm\". If not, could you please add a reference ?\n- 17) I was not aware of the \"data heterogeneity assumption\" before reading this paper. Where does it come from ? Could you add ref about this ?  Is it met in practice ? What is the link between the assumption and the heterogeneity of the data ?\n- 18) Proof of theorem 1, line 465: Why is $z_{\\pi(j)}^{kn+j-1} = z_{\\pi(j)}^{kn}, \\ \\forall j=1, \\ldots, n\\$ true ? For instance, if $\\pi(j)=j$ and $k=0$, then it would mean that\n$$z_j^{j-1} = z_j^0$$\nwhich is not necessarily the case if the index sampled at step $j-1$ is j. Maybe I'm wrong on this one, but let me know if there is an easy way to see this.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- Authors do not clearly explain how to set $\\theta$ (except in the strongly convex case) and how this affects the performance. As said before, the reader don't get why and if this parameter is important or if it is just introduce for the analysis.\n- Same remark for $\\gamma$ in (22)\n- Numerical experiments seem to correctly recover what theory predicts for data-heterogeneity case and for recovering GD rate\n\n\n**COMMENT AFTER THE REBUTTAL**\n\nI thank the authors for there clear and exhaustive answers to my questions/concerns and those of the other reviewers. \n\nI read the authors' rebuttal and it made things clearer in my mind on some points : \n- the extended Table 1 clarifying the comparison with other works, especially [18] \n- I read carefully the discussion about the measure of suboptimality done in this work (pointed out by reviewer y5Mf). I also think it is a limitation of this paper. \n- After reading answers to my review and the one of Reviewer VeN3, I now understand now why the dampening parameter is required.\n\nI this paper will be valuable to the community both for its theoretical results (sample independent rate with highly heterogeneous assumption) and its technical aspects (eg the introduction of order-specific norms). Also, fair comparison with previous work (especially [18] in/out of the Big data regime) will be clearly presented in the final version of this work. **Thus, I increase my score from 6 to 7.**\n\n\n\nSide comment : I would have been interested to see what is the magnitude of $\\rho$ for different datasets and if it is close to $\\mathcal{O} (1/n)$ for  some real data sets.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "cQiobiDf28M", "reviewer": "Reviewer_VeN3", "summary": "This paper proposes a new first-order algorithm using without-replacement strategy to solve a class of composite convex minimization problems. The main idea is to modify the well-known scheme, called Finito/MISO method by applying a without-replacement strategy and a damping step. Under the convexity and L-smoothness of f, the proposed algorithm achieves O(1/k) rate in epoch on the optimality residual. When f is additionally strongly convex, the rate is improved to linear as in standard proximal gradient methods. The analysis relies on a weight norm defined through the order of the underlying shuffling strategy. The authors also compare their method with other schemes such as a coordinate descent method with cyclic rule, and standard GD. Next, the authors also investigate the optimal cyclic rule for sampling and propose an adaptive variant. Numerical examples on standard logistic regression problem are presented to illustrate the performance of the proposed methods. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Originality: I believe that the result of this paper is new, especially the use of a new weighted norm in this case. In fact, the algorithm can be cast into a variant of the ARock method [Peng et al, 2015], but the use of without-replacement is new. The use of damped step is not new, which has been widely used in fixed-point methods as well as in optimization. The key idea of analysis is to show that the corresponding fixed-point mapping is nonexpansive, which allows to use a damped step and achieve O(1/k) rate in epoch. However, the convergence rate is not really encouraging even it is comparable with GD. The reason is that this method requires to store n auxiliary vectors as in SAGA, making it less practical when n and d are large.\n\nQuality/clarity: The paper is well written and well-motivated in general. It does have both algorithmic and theoretical contributions. The technicality sounds and the analysis seems to be nontrivial.\n \nSignificance: Overall, the paper has nice contribution in terms of new algorithm, especially when using without-replacement strategy. \n\nBelow are some concrete comments and questions:\n\n-- Is the damped step in Algorithm 1 really the key to achieve the O(1/k) rate? In fact, it is not needed for the strongly convex case. I have a feeling that this is only needed if the fixed-point mapping is only non-expansive. Could the authors clarify and discuss this point, because it is highlighted in the paper?\n\n-- It seems that the nonexpansiveness of T is rather trivial since it is constituted by a proximal gradient operator which is nonexpansive for such a chosen stepsize. Does it need any other properties to guarantee the non-expansiveness of T in (11)?\n\n-- The comparison with SVRG and SAGA using randomized reshuffling rule seems to not make sense. These variants may not work with without-replacement rules unless an appropriate variant (e.g., in [18,37]) is used. The authors may use [18] for SVRG, but for SAGA, which variant is used in the experiments?\n\n-- The weighted norm only depends on z0 and z*, and does not depend on the landscape of the problem. This is a very interesting aspect of the new method. Can you also add more discussion on this aspect to elaborate the new contribution?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper does not discuss the limitation as well as social impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is favored by two of four expert reviewers and is acceptable to the other two. Reviewers agree that it is clearly written and organized. There is also general agreement that parts of the analysis are new and insightful, and possibly useful outside of this paper, in particular the "order-specific" norm that is introduced.

Some reviewers make valid points about the limitations of the end result. For instance, reviewer VeN3 points out that the convergence rate is not necessarily encouraging even if it matches plain GD since the paper's method has memory requirements that scale linearly with the dataset size. The relative advantage then happens in an optimistic case where an optimal cyclic ordering is known (in practice, this ordering is replaced by a heuristic) and when the data is sufficiently heterogeneous (a technical condition detailed in the paper).

I will add that the reviews on this paper were quite thorough, and that there was detailed discussion among reviewers and authors. Ultimately, these exchanges addressed many reviewer concerns and left the authors with suggestions for improvement that might only strengthen the writing further. They've even led to some additional empirical measurements and several references to related work.
Decision: Accept (Poster)