Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling
Authors: Alexander Tyurin
Lukang Sun
Konstantin Pavlovich Burlachenko
Peter Richtárik
Venue: Submitted to ICLR 2023 (2023)
Keywords: nonconvex optimization
empirical risk minimization
SGD
variance reduction
data sampling
client sampling
optimal methods
biased gradient estimator
federated learning

Abstract: We revisit the classical problem of finding an approximately stationary point of the average of $n$ smooth and possibly nonconvex functions. The optimal complexity of stochastic first-order methods in terms of the number of gradient evaluations of individual functions is $\mathcal{O}\left(n + n^{1/2}\varepsilon^{-1}\right)$, attained by the optimal SGD methods SPIDER (Cong Fang et al., 2018) and PAGE (Zhize Li et al., 2020), for example, where $\varepsilon$ is the error tolerance. However, i) the big-$\mathcal{O}$ notation hides crucial dependencies on the smoothness constants associated with the functions, and ii) the rates and theory in these methods assume simplistic sampling mechanisms that do not offer any flexibility. In this work we remedy the situation. First, we generalize the PAGE algorithm so that it can provably work with virtually any (unbiased) sampling mechanism. This is particularly useful in federated learning, as it allows us to construct and better understand the impact of various combinations of client and data sampling strategies. Second, our analysis is sharper as we make explicit use of certain novel inequalities  that capture the intricate interplay between the smoothness constants and the sampling procedure. Indeed, our analysis is better even for the simple sampling procedure analyzed in the PAGE paper. However, this already improved bound can be further sharpened by a different sampling scheme which we propose. In summary, we provide the most general and most accurate analysis of optimal SGD in the smooth nonconvex regime. Finally, our theoretical findings are supposed with carefully designed experiments.

Under review as a conference paper at ICLR 2023
SHARPER RATES AND FLEXIBLE FRAMEWORK FOR NONCONVEX SGD WITH CLIENT AND DATA SAMPLING
Anonymous authors Paper under double-blind review
ABSTRACT
We revisit the classical problem of finding an approximately stationary point of the average of smooth and possibly nonconvex functions. The optimal complexity of stochastic first-order methods in terms of the number of gradient evaluations of individual functions is O (n + n g attained by the optimal SGD methods SPIDER (Fang al., 2018) and PAGE (Li al., 2021), for example, where e is the error tolerance. However. i) the big-O notation hides crucial dependencies on the smoothness constants associated with the functions, and ii) the rates and theory in these methods assume simplistic sampling mechanisms that do not offer any flexibility. In this work we remedy the situation. First, we generalize the PAGE algorithm that it can provably work with virtually any (unbiased) sampling mechanism. This particularly useful in federated learning, as it allows us to construct and better understand the impact of various combinations of client and data sampling strategies. Second, our analysis is sharper as we make explicit of certain novel inequalities that capture the intricate interplay between the smoothness constants and the sampling procedure. Indeed, our analysis hetter even for the simple sampling procedure analyzed in the PAGE paper. However, this already improved bound can be further sharpened by different sampling scheme which we propose. In summary, we provide the most general and most accurate analysis of optimal SGD in the smooth nonconvex regime. Finally, our theoretical findings are supposed with carefully designed experiments.
INTRODUCTION
In this paper, we consider the minimization of the average of smooth functions (1) in the nonconvex setting in the regime when the number of functions is very large. In this regime, calculation of the exact gradient can be infeasible and the classical gradient descent method (GD) (Nesterov, 2018) can not be applied. The structure of the problem is generic, and such problems arise in many applications, including machine learning (Bishop & Nasrabadi, 2006) and computer vision (Goodfellow et al., 2016). Problems of this form are the basis of empirical risk minimization (ERM), which is the prevalent paradigm for training supervised machine learning models.
1.1 FINITE-SUM OPTIMIZATION IN THE SMOOTH NONCONVEX REGIME
We consider the finite-sum optimization problem
= [(x))= RERd
min
f(x) M())
(1)
where /i : Rdd >> IR is a smooth (and possibly nonconvex) function for all E [M] == (1..... n). We are interested in randomized algorithms that find an e-stationary point of (1) by returning a random point 3 such that F. ||V [ S e. The main efficiency metric of gradient-baser based algorithms for finding such a point is the (expected) number of gradient evaluations Vf; we will refer to it as the complexity of an algorithm.

---

Under review as a conference paper at ICLR 2023
1.2
RELATED WORK
The area of algorithmic research devoted to designing methods for solving the ERM problem (1) in the smooth nonconvex regime is one of the most highly developed and most competitive in optimization.
The path to optimality. Let us provide a lightning- speed overview of recent progress. The complexity of GD for solving (1) is O (ne-1), but this was subsequently improved by more elaborate stochastic methods, including SAGA, SVRG and SCSG (Defazio et al., 2014; Johnson & Zhang, 2013; Lei et al., 2017; Horváth & Richtárik, 2019), which enjoy the better complexity O (n + n=2
Further progress was obtained by methods such as SNVRG and Geom Seom-SARAH (Zhou et al., 2018; Horváth et al., 2020), improving the complexity to Ô (n + g Finally, the methods SPIDER, SpiderBoost, SARAH and PAGE (Fang et al., 2018; Wang et al., 2019; Nguyen et al., 2017: Li et al., 2021), among others, shaved-off certain logarithmic factors and obtained the optimal complexity O (n - n n matching lower bounds (Li et al., 2021).
Optimal, but hiding secret. While it may look that this is the end of the road, the starting point of our work is the observation that the big-O notation in the above results hides important and typically very large data-dependent constants. For instance, it is rarely noted that the more precise complexity of GD is O (L L__ss-)) while the complexity of the optimal methods, for instance PAGE, is O (n + 12m2/2=-1) where L- L+ are different and often very large smoothness constants. Moreover, it is easy to generate examples of problems (see Example 1) in which the ratio L LL_ is as large one desires.
Client and data sampling in federated learning. Furthermore, several modern applications, notably federated learning (Konečný et al., 2016; McMahan et al., 2017), depend on elaborate client and data sampling mechanisms, which are not properly understood. However, optimal SGD methods were considered in combination with very simple mechanisms only, such as sampling a random function fi several times independently with replacement (Li et al., 2021). We thus believe that an in-depth study of sampling mechanisms for optimal methods will be of interest to the federated learning community. There exists prior work on analyzing non-optimal SGD variants with flexible mechanisms For example, using the "arbitrary sampling" paradigm. originally proposed by Richtárik & Takáč (2016) in the study of randomized coordinate descent methods, Horváth & Richtárik (2019) and Qian et al. (2021) analyzed SVRG, SAGA, and SARAH methods, and showed that it is possible to improve the dependence of these methods on the smoothness constants via carefully crafted sampling strategies. Further, Zhao & Zhang (2014) investigated the stratified sampling, but only provided the analysis for vanilla SGD, and in the convex case.
1.3 SUMMARY OF CONTRIBUTIONS
Specifically, the original paper (Li et al., 2021), the optimal (w.r.t. n and é) optimization method PAGE was analyzed with simple uniform mini-batch sampling with replacement. We analyze PAGE with virtually any (unbiased) sampling mechanism using a novel Assumption 4. Morcover, we show that some samplings can improve the convergence rate O (n + L4n of PAGE (see Table 2). We improve the analysis of PAGE using new quantity. the weighted Hessian Variance L (or Lt,w), that is well-defined if the functions fi are L.-shooth. We show that, when the functions f; are "similar" in the sense of the weighted Hessian Variance, PAGE enjoys faster convergence rates (see Table 2). Also, unlike (Szlendak et al., 2021), we introduce weights w, that can play a crucial role in some samplings. Morcover, the experiments in Sec 5 agree with our theoretical results.
Our framework is flexible and can be generalized to the composition of samplings. These samplings naturally emerge in federated learning (Konečný al., 2016; McMahan et al., 2017), and we show that our framework can be helpful in the analysis of problems from federated learning.
2 ASSUMPTIONS
We need the following standard assumptions from nonconvex optimization. Assumption 1. There exists f" E IR such that f 2 f for all x E Rd.
Assumption 2. There exists L_ 2 such that [V - ff(il s L- 1|- sir-yllen for all x, E Rd.
2

---

Under review as a conference paper at ICLR 2023
Table 1: The constants A, B, we and [S] that characterize the samplings in Assumption 4.
Sampling scheme
W/
B
S
Reference
Uniformm Wirk Replacement
1/7
1/m
1/T
S
Sec. E.3
Importance
1/r
qi
1/r
Sec, E.3
Nice
7(n-1)
1/1
r[n-1]
T
Sec. E.
Independent
0
Ei=1 Pi
Sec. E.2
2i 11
>>
Extended Nice
7--
n-T
ST
Sec. E,4
7(x-1)
T[n-1]
Notation: n of data points, r batch size; q, probahility to sample data point in multiomiil distribution; probahility sample 1 data point the bernoulli distribution; 1, times repeat. e data point before apply the Nice sampling.
Assumption 3. For all i E [n], there existsa constant L > 0 such that [V Vi((i)) - L || vll for all x, y Rd.
2.1 TIGHT VARIANCE CONTROL OF GENERAL SAMPLING ESTIMATORS
In Algorithm (a generalization of PAGE), we form estimator of the gradient V f via subsampling. In our search for achieving the combined goal of providing a general (in terms of the range of sampling techniques we cater for) and refined (in terms of the sharpness of our results, even when compared to known results using the same sampling technique) analysis of PAGE, we have identified several powerful tools, the first of which is Assumption 4.
Let S = {[w]..... wx)) E IR [1,...,, Wn 2 0, Σm Wt = 1} be the standard simplex and (S, F, P) probability space.
Assumption 4 (Weighted AB Inequality). Consider the random mapping S Rd ... x R& x
- Rd, which we will call "sampling", such that E [S(a1,.... anj [n]w]] = 1
n E as for all
E Rd. Assume that there exist A, B 2 0 and weights (W1, W[n E S such that
E
S(a (wiw) 1 Σ
| 2
B
Vai...., On E R2d (2)
For simplicity, we denote S (a = S(a an) S(a1, ag an: Further, the collection
of samplings satisfying Assumption will be denotes S( A, B, in 1-1) The main purpose of sampling S E S(A, (w.)=)) is to estimate the mean Σn i=1 a using some random subsets (possibly containing some elements more than once) of the set (a1..... .an) J.ssumpttion 4 is the only nonstandard assumption in our paper, and we refer to Table where we provide examples of samplings that satisfy this assumption. It represents a convenient framework to build the theory.
We now define the cardinality [S] of sampling S (,A ),
Definition 1 (Cardinality of Sampling). Let take S E S(A, B, (w: and define the function
S. (a ax) Rd x ... x Rd + Rd such that S (ai....... an) == S(aj....,,.. aniw). If the function S_ an) depends only on a subset A(w) of the arguments (a1...., an), where A(w) > ax)). we define [S] = E [[]][]]]]]
Assumption 4 is most closely related to two independent works: (Horváth & Richtárik, 2019) and (Szlendak et al., 2021). Horváth & Richtárik (2019) analyzed several non-optimal SGD methods for "arbitrary samplings"; these are random set-valued mappings S with values being the subsets of [n]. The distribution a such a sampling is uniquely determined by assigning probabilities to all 2 subsets of [n)]. In particular, they show that Assumption 4 holds with S(a a.,) = = Eies a: p. P: := Prob(i E S). [S] = |S}, some 2 O, Wi...., Wn 2 0 and B = O. Recently, Szlendak et al. (2021) studied similar inequality, but in the context of communication-cdn -efttiiinneffieentt distributed training with randomized gradient compression operators. They explicitly set out to study correlated compressors, and for this reason introduced the second term in the right hand side; i.e., they considered
3

---

Under review as a conference paper at ICLR 2023
Table The complexity of methods and samplings from Table and Sec 4.
Sampling scheme
Complexity
Comment SVRG method Pi xc L
2/3 2r L.
Independent (Horvääh Richaärk, 2019)
n
Uniform With Replacement (Li al., 2021)
JRL
12 musl v
Uniform With Replacement (new)
vnl 2aa 4.)
Importance
91
20 19
The functions ft are splitted into groups
Stratifted
n
Notation: n = # of data points; 5 = ervor tolerance; L. Lis L by and I,++ are smoothness constants such that Limi S Lu L L.4; g = # groups Stratified sampling.
the possibility of B being nonzero, as in this way they obtain tighter inequality, which they can use their analysis. However, their inequality only involves uniform weights (w;). Our Assumption offers the tightest known way to control of the variance of the sampling estimator, and our analysis can take advantage of See Table for an overview of several samplings and the values A, B and {w;) for which Assumption 4 is satisfied.
2.2 SAMPLING-DEPENDI SMOOTHNESS CONSTANTS
We now define two smoothness constants that depend the weights {w;]i= of sampling S and on the functions fi.
Definition 2. Given a sampling S E S(A, (w; (wm))=)) let L4, to be a constant for which
Σ 1 nw,
[[) fi(u))l & 1 11 u1? Ya,y E Rd.
For (wi,.... ) (/,,..., 1/x), we define L+ == Lt+..
Definition 3. Given a sampling e S(A, B, (wi) / 1), let Lt be constant for which
[Vf(()) V((()) [V)(() v s 22 1 --------1 -l1?
Va,y E Rd
For (Wi...., wx) (z/n,..., 1/n,, define L+ == Lt
One can interpret Definition as weighted mean-squared smoothness property (Arjevani et al., 2019), and Definition 3 as weighted Hessian variance (Szlendak et al., 2021) that captures the similarity between the functions Jt- The constants Lt,w and Lt.w help us better to understand the structure of the optimization problem (1) in connection with a particular choice a sampling scheme. Note that Definitions 2, and Assumption 4 are connected with the weights (or)"
The next result states that L2 and L are finite provided the functions fr are Lm-shhoth for all i [n].
Theorem 4. If Assumption 3 holds, then 12,,0= = -. Ei 1
ne; LŽ satisfy Def. 2 and
Indeed, from Assumption 3 and the inequality |V - f 2 0 we get
TW: [Vf((z) - - (v)()) vf(1)12 Σ ran
L3 || 1112
thus we can take L 1. = Σー L3 The proof for L w is the same.
From the proof, one can see that we ignore |Vv(() {1)) when estimating L However, by doing that, the obtained result is not tight.
4

---

Under review as a conference paper at ICLR 2023
Algorithm 1 PAGE
Input: initial point 2º Rd, stepsize 7 > O, probability p E (0, 1]
2: g" Vv(x2)
3: for
0, f
T
4: xf+1 x² ?g
5: Generate a random sampling function S
Vf(z't1)
with probability p
6: g
o S ((V -V(()))))
with probability 1 -
7: end for
3 A GENERAL AND REFINED THEORETICAL ANALYSIS OF PAGE
In the Algorithm 1, we provide the description of the PAGE method. The choice of PAGE as the base method is driven by the simplicity of the proof in the original paper. However, we believe that other methods, including SPIDER and SARAH, can also admit samplings from Assumption
In this section, we provide theoretical results for Algorithm 1. Let us define Do := =f(x²)) f
Theorem 5. Suppose that Assumplions 2, 3 hold and the samplings St S(A, B, {ws {
Then Algorithm 1 (PAGE) has the convergence rate E [ S z where S
(I- [ ((A- 12,, + B12,
To reach an e-stationary point, it is enough to do
== 2Ag (A-B
+ BL2
(3)
iterations of Algorithm 1. To deduce the gradient complexity, we provide the following corollary.
Corollary 1. Suppose that the assumptions of Thm hold, Let us take p (the expected number of gradient calculations V of Algorithm equals
SS]
Then the complexity
18|tn
N = (n + (S|7) = n Do
L +
n S
((A B) 12 + BT2
Proof. At each iteration, the expected # gradient calculations equals pn + (1 [|] S 2|S). Thus the total expected number of gradient calculations equals n + 2|S T to get an E-stationary point. n
The original result from (Li et al., 2021) states that the complexity of PAGE with batch size is
Nonig = + (n n
Gur (T. + 2 O (n
ADyTL
(4)
T E 21,
3.1
Uniform With Replacement SAMPLING
Let us do sanity check and substitute the parameters of the sampling that the original paper uses. We take the Uniform With Replacement sampling (see Sec E.3) with batch size (note that r 2 [S))
A B 1/7 and w: 1/1 for all [n) (see Table and get the complexity Nunifum
+ n A (L.
for all (1,2,...,m) n). .1) Next, let us fix & max vol.
and,
Let compare it with (4). With the same sampling, our analysis provides better complexity; indeed, note that max VnL+, L-) < VRL+ (see Lemma Szlendak et al. (2021)). Moreover, Szlendak et al. (2021) provides examples of the optimization problems when L2 is small and L4 is large, so the difference can be arbitrary large.
finally, obtain that Nuniform θ + Do
5

---

Under review as a conference paper at ICLR 2023
3.2 Nice SAMPLING
Next, we consider the Nice sampling (see Sec E.1) and get that the complexity Nnice
n - [L_ ( mim (n-1)
L+) (
Unlike the Uniform With Replacement sampling, for e small
enough, the Nice sampling recovers the complexity of GD for = n. which is equal to θ (AnL_))
3.3 Importance SAMPLING
Let us consider the Importance sampling (see Sec E.3) that justifies the introduction of the @ n Aer (L- / L+111) S
weights Wi. We can get the complexity Nimportance
n Ao max((y/ll w.l for S mmxx ( 1 { Now, we take 9i wy Eizi Ix
L.
+ n n+ Sovi( Ei= Li) L.)
and use the results from Sec to obtain Namportance
Norig (See Sec G). In Example we consider the optimization task where 1 Σi= I, is v times smaller than L4. Thus the complexity Nimportance can be at least v times smaller that the complexity Norig-
3.4 THE POWER OF B
In all previous examples, the constant A B> 0. If A B, then the complexity N θ n ++++0 س S L + BL..)) thus the complexity N does not depend on L which
greater of equal to 12 This is the first analysis of optimal SGD, which uses B 0.
3.5 ANALYSIS UNDER PL. CONDITION
The previous results can be extended to the optimization problems that satisfy the Polyak-Lojasiewicz condition. Under this assumption, Algorithm 1 enjoys linear convergence rate.
Assumption 5. There exists 0 such that the function J satisfy (Polyal-Lojasiewice) Pł-condition:
|V > 2n(f(x) Va E R,
where f ang f(x)= xc.
Using Assumption 5, we can improve the convergence rate of PAGE.
Theorem 6. Suppose that Assumptions 1, 2, 3, 5 and the samplings St E S(A, B, (=
Then Algorithim (PAGE) has the convergence rate E [f(x")] [)
- f S (1 - 7/4 Do, where
S min (1-
-1
2(1p)) ((A B) 12,,0 + BI2
2p
COMPOSITION OF SAMPLINGS: APPLICATION TO FEDERATED LEARNING
In Sec 3, we analyze the PAGE method with samplings that satisfy Assumption 4, Now, let us assume that the functions f, have the finite-sum form, i.c. fa(x) = m, E ft)(x), thus we an optimization problem
f(z) = 1 +
min ZER
Another way to get the problem is to assume that we split the functions fi into groups of sizes m,. All in all, let us consider (5) instead of (1).
The problem (5) occurs in many applications, including distributed optimization and federated learning (Konečný et al.. 2016; McMahan al., 2017). In federated learning, many devices and machines (nodes) store local datasets that they do not share with other nodes. The local datasets represented by functions ft, and all nodes solve the common optimization problem (5). Due to

---

Under review as a conference paper at ICLR 2023
Algorithm 2 PAGE with composition of samplings
Input: initial point xº RRd, stepsize 7 > 0, probability p E (0, 1).90 vs(x")
2: for [ 0, 1,..... ,..., do
3: x o++1 x² -9g
1
with probability p
4:
d²1
0
with probability -
5:
if c' = then
6:
9 g+ (
1 FL Interpretation: Calculate the full gradients V Sa on the nodes and collect them */
7:
else
8:
Generate samplings S for all i [n]
9:
h,+1 S ((Vfe((tt)) -V (1m=)) for all [n]]
FL Interpretation: Calculate the mini-batches h hx+11 on the nodes */
10:
Generate sampling S' and set g"+ = g' + St ((ht+1
1e FL Interpretation: Collect h1+1 only from the sampled nodes $/
end if
12: end for
privacy reasons and communication bottlenecks (Kairouz et al., 2021), it is infeasible store and compute the functions f, locally in one machine.
In general, when solve (1) in machine, have the freedom of choosing sampling S for the functions fi, which we have shown See 3. However, in federated learning, a sampling of nodes or the functions fi is dictated by hardware limits network quality (Kairouz al., 2021). Still, each 7th node can choose sampling S; to sample the functions fij. As result, we have a composition of the sampling S and the samplings (see Algorithm 2).
Assumption 6, For all j E [m,], i E [m], there exists a Lipschitz constant Lij such that (z) - fig( s Ly ||æ - yll for all x, Rd.
We now introduce the counterpart of Definitions 2 and 3. Definition 7. For all E [n] and any sampling S S(A, B,, (wi, )ymn), define constant Li,t,w. such that
m
[fz((>)
Vx, E Rd. (fb(D)) < Ii,,.,,, || y11
Definition 8. For all i E [n] and any sampling S, E S(A, Bi, (wi)) define constant Tu,d, such that
(z)(() ( [V/(>) - V S 12,,, | vl Va, E Rdd
Let us provide the counterpart of Thm 5 for Algorithm 2.
Theorem 9. Suppose that Assumptions 1.
6 hold and the samplings S
S(A, B, (w:))1)) and the samplings S E S(A,, Bi, (wij m- for all E [n]. More-
over, B I 1. Then Algorithm has the convergence rate E ||] <
24a where
1-p P
(1 (1-B) ((A: B.). B.L (A- B---BBL22,00 + BL3
L-
na;
The obtained theorem provides a general framework that helps analyze the convergence rates of the composition of samplings that satisfy Assumption 4. We discuss the obtained result in different contexts.
7

---

Under review as a conference paper at ICLR 2023
4.1 FEDERATED LEARNING
For simplicity, let us assume that the samplings S' and S are Uniform With Replacement sam- plings with batch sizes T and Tı for all E n, accordingly, then to get e-stationary point,
enough to do T = A
L
+
2
+ 1 + + +xz))
iterations. Note that
Au L- + L for all T; 2 1 for all i E [r4] It means that after some point, there is no benefit in increasing batch sizes In order to balance 1,2 E F. L and L one can take Ti O (L/)/1 The constant L captures the intra-variance inside 7th node, while Lå captures the inter-variance between nodes. If the intra-variance is small with respect to the inter-variance, then our theory suggests taking small batch sizes and vice versa.
4.2 Stratified SAMPLING
Let us provide another example that is closely related to (Zhao & Zhang, 2014). Let us consider (1) and use a variation the Stratified sampling (Zhao & Zhang, 2014): we split the functions fi into g 7/m groups, where is the number of functions in each group. Thus we get the problem (5) with fxx = 1 - m Σm د==1 fiz(2). Let us assume that we al- ways sample all groups, thus A B O, and the sampling S are Nice samplings with batch sizes TI for all i E [n]. Applying Thm 9, we get the convergence rate Tgrou ==
L-
Le 1 E1 1 pgri
At each iteration, the algorithm calculates gT1 gra-
dients, thus we should take p = g +m
gTi
to get the complexity N Ngroup == O (TTT) =
θ n A (onL- vT Ei=1 (.,tt) Let us take Ti S max
E 17.t
ob-
gh_
tain the complexity N Ngroup A (
An max va V Ei-1 13 19,4
n
Comparing the complexity
Nerop with the complexity Nuniform from Sec 3, one can see that if split the functions Sa in a "right way", such that I4, is small for i E [ni] (see Example 3), then we can get at least vn/ vg times improvement with the Stratified sampling.
EXPERIMENTS
We now provide experiments' with synthetic quadratic optimization tasks, where the functions Ss- in general, are nonconvex quadratic functions. Note that our goal here is check whether the dependencies that our theory predicts are correct for the problem (1). The procedures that generate synthetic quadratic optimization tasks give us control over the choice of smoothness constants. All parameters, including the step sizes, are chosen as suggested by the corresponding theory. In the plots, we represent the relation between the norm of gradients and the number of gradient calculations V f.f.
5.1 QUADRATIC OPTIMIZATION TASKS WITH VARIOUS HESSIAN VARIANCES L+
Using Algorithm 3 (see Appendix), generated various quadratic optimization tasks with different smoothness constants L E [0, 1.0] and fixed L_ x 1.0 (see Fig. 1). We choose d = 10, n = 1000, regularization À= 0.001, and the noise scale E (0, 0.1, 0.5, 1). According the gradient complexity of original PAGE method ("Vanilla PAGE" in Fig. 1) is proportional to T.-- While the gradient complexity of the new analysis with the Uniform With Replacement sampling ("Uniform With Replacement" in Fig. 1) is proportional to Lz, which is always less or equal L4. In Fig. 1, one can see that the smaller L+ with respect to L+, the better the performance of "Uniform With Replacement." Moreover, we provide experiments with the Importance sampling ("Importance" in Fig. 1) with 4 L, Ly
Sec 3 and Table
for all i E [n). This sampling has the best performance in all regimes.
'Our code: https: /tt///gtttt/stt http:/hiw..commttttrrrreeeaaarae saapp ing- ing-in-we i-oot 1
8

---

Under review as a conference paper at ICLR 2023
C. 0.99 L. 0.99
0.111 0,36 997
6.5 0..96 C. 1.08
0.3311_ 0.36 La
Figure 1: Comparison of samplings and methods on quadratic optimization tasks with various L.s
5.2 QUADRATIC OPTIMIZATION TASKS WITH VARIOUS LOCAL LIPSCHITZ CONSTATNS I,,
Using Algorithm 4 (see Appendix), we synthesized various quadratic optimization tasks with different smoothness constants T., (see Fig. 2). We choose d = 10, n 1000, the regularization À = 0.001, and the noise scale & E (0, 0.1, 0.5, 10.03- We generated tasks in such way that the difference between max; Li and min; L, increases. First, one can see that the Uniform With Replacement sampling with the new analysis ("Uniform With Replacement" in Fig. 2) has better performance even in the cases of significant variations of Lg Next, we see the stability of the Importance sampling ("Importance" in Fig. 2) with respect to this variations.
346
mint, 0.8 1.62
5.58
mini, 61.47
Vi Redevred Caan do
14-
2R1S
Figure 2: Comparison of samplings and methods on quadratic optimization tasks with various Li.
5.3 NONCONVEX CLASSIFICATION PROBLEM WITH LIBSVM DATASETS
We now solve nonconvex machine learning tasks and compare samplings on LIBSVM datasets (Chang & Lin, 2011) (see details in Sec A.2). As in previous sections, PAGE with the Importance sampling performs better, especially in the australian dataset where the variation of L; is large.
12h
min 5.22 maxi, 2875
101
mini: 81.12 maxi 250013006600
Unilurm Weth uccmort
mosottnnc
10a
Un forr With teplacement Importacce
10100
10
101
101
16-4
10tt
30
0.2
0.4
0.6
2.5
100
12:1 0.5
0.2
0.5
3.0
w&a dataset
australian dataset
Figure 3: Comparison of samplings nonconvex machine learning tasks with LIBSVM datasets.
REFERENCES
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint 1rXiv:1912.0238800 2019.
Christopher M Bishop and Nasser M. Nasrabadi. Pattern recognition and machine learning, volume 4.
Springer, 2006.

---

Under review as a conference paper at ICLR 2023
Konstantin Burlachenko, Samuel Horváth, and Peter Richtárik. Fl.pytorc:: optimization research simulator for federated learning. In Proceedings of the 2nd ACM International Workshop on Distributed Machine Learning, pp. 1-7, 2021.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines. ACM Transactions Intelligent Systems and Technology (TIST), 2(3):1-27, 2011.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in Neural Information Processing Systems, 27, 2014.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. SPIDER: Near-optimal non-convex op- timization via stochastic path integrated differential estimator. In NeurIPS Information Processing Systems, 2018.
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT Press, 2016.
Samuel Horváth and Peter Richtárik. Nonconvex variance reduced optimization with arbitrary sampling. In International Conference on Machine Learning, pp. 2781-2788 PMLR, 2019.
Samuel Horváth, Lihua Lei, Peter Richtárik, and Michael Jordan, Adaptivity of stochastic gradient methods for nonconvex optimization. arXiv preprint arXiv:2002.05359, 2020.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in Neural Information Processing Systems, 26, 2013.
Peter Kairouz, Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems federated learning. Foundations and Trends@ in Machine Learning. 14(1-2):1-210, 2021.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv: 05442,, 2016.
Lihua Lei, Cheng Ju, Jianbo Chen, and Michael Jordan. Non-convex finite-sum optimization via SCSG methods. Advances in Neural Information Processing Systems, 30, 2017.
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. PAGE: simple and optimal
probabilistic gradient estimator for nonconvex optimization. In International Conference Machine Learning, pp. 6286-6295, PMLR, 2021.
Brendan McMahan, Eider Moore. Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication-effce learning of deep networks from decentralized data. Artificial Intelli- gence and Statistics, pp. 1273-1282. PMLR, 2017.
Yurii Nesterov. Lectures Convex Optimization, volume 137. Springer, 2018
Lam Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. SARAH: novel method for machine learning problems using stochastic recursive gradient. In The 34th International Conference Machine Learning, 2017.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Xun Qian, Zheng Qu, and Peter Richtárik. L-SVRG and L-Katyusha with arbitrary sampling. Journal of Machine Learning Research, 22:1-49, 2021.
Peter Richtárik and Martin Takáč. Parallel coordinate descent methods for big data optimization. Mathematical Programming, 156(1):433 484, 2016.
10

---

Under review as a conference paper at ICLR 2023
Rafat Szlendak, Alexander Tyurin, and Peter Richtárik. Permutation compressors for provably faster distributed nonconvex optimization. arXiv preprint arXiv:2110.03300, 2021.
Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. SpiderBoost and momentum: Faster
variance reduction algorithms. Advances in Neural Information Processing Systems, 32, 2019.
Peilin Zhao and Tong Zhang. Accelerating minibatch stochastic gradient descent using stratified sampling. arXiv preprint arXiv: 3005.3880, 2014.
Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduction for nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018.

---

Under review as a conference paper at ICLR 2023
CONTENTS
1
Introduction
1.1
Finite-sum optimization in the smooth nonconvex regime
1.2
Related work
1.3
Summary of contributions
2
Assumptions
2.1
Tight variance control of general sampling estimators
2.2
cenpedeg-dependent smoothness constants
3
A General and Refined Theoretical Analysis of PAGE
3.1 Uniform With Replacement sampling
3.2 Nice sampling
6
3.3 Importance sampling
3.4 The power of B
6
3.5
Analysis under PL Condition
Composition of Samplings: Application to Federated Learning
4.1
Federated Learning
4.2
Stratified sampling
5
Experiments
5.1
Quadratic optimization tasks with various Hessian Variances L
8
5.2
Quadratic optimization tasks with various local Lipschitz constatns L;
5.3
Nonconvex classification problem with LIBSVM datasets
A
Extra Experiments and Details
14
A.1 Quadratic optimization tasks with various batch sizes.
14
A.2 Details experiments with LIBSVM datasets
14
A.3 Federated learning experiments with LIBSVM dataset.
15
A.4 Computing environment
15
B Auxiliary facts
16
Examples of Optimization Problems
16
Missing Proofs
17
E Derivations of the Parameters for the Samplings
19
E.1 Nice sampling ................................
19
E.2 Independent sampling
20
12

---

Under review as a conference paper at ICLR 2023
E.3
Importance and Uniform With Replacement sampligg
21
E.4 Extended Nice sampling
22
F
The Optimal Choice of wi;
23
G The Complexity of Algorithm with the Importance sampling
23
Missing Proofs: The Composition of Samplings
23
Artificial Quadratic Optimization Tasks
27
13

---

Under review as a conference paper at ICLR 2023
A EXTRA EXPERIMENTS AND DETAILS
A.1 QUADRATIC OPTIMIZATION TASKS WITH VARIOUS BATCH SIZES.
In this section, we consider the same setup as Sec 5.1. In Figure 4, we fix L+. and show that the Importance sampling has better convergence rates with different batch sizes. Note that with large batches, the competitors reduce to the GD method, and the difference not significant.
1g 0.1; 0.96; L, 0.97
Lanceeee 1000
30
30
Manch
call knch tascl ships dueo
Phap- 0.7
Enportnci, botch Kopp o.r
epportacio, busch deop
inportano, Buld 1008 1.00
30
gradiennt calcuiations scaie)
Figure 4: Comparison of samplings and methods with various batch sizes.
A.2 DETAILS ON EXPERIMENTS WITH LIBSVM DATASETS
We compare the samplings on practical machine learnings with LIBSVM datasets (Chang & Lin, 2011) I) (under the 3-clause BSD license). Parameters of Algorithm I are chosen suggested in Thm and Cor 1. We take the parameters for Uniform With Replacement and Importance samplings from Table 1 with q = ΣE L. We consider the logistic regression task with a nonconvex regularization (Wang et al., 2019)
exp (a (.) E 21 exp (a. xny)
tayy f 12
f(11, x22) = Σ log
+
min 21.
DE (1,2) 1=1
where {.h is an indexing operation, E Rd is the feature of a tth sample, y: E 2} is the label of a 7th sample, constant 0.001. We fix batch size t and take w&a dataset (dimension d = 300, number of samples n 49.749) and australian dataset (dimension d 14, number of samples n 690) from LIBSVM. For the logistic regression, the Lipschitz constants I,, can be estimated. The distribution of Lipschitz constants L; across datapoints for that two datasets is presented in Fig. 5. We use Thm 4 to obtain L and L L2_.'
austullan
wSa
22566
200e
12
10
Figure 5: The distribution of Lipschitz constants L
14

---

Under review as a conference paper at ICLR 2023
unforn With Replecement 1m
10
undern with Sepiecement [Tane
unioo With Reslacement [ou
Uniform With heslasement [rwin
10"
Untorrn With Replacement
21
16
Unitern With Seplacement
Uniform With Repfogmment
25]
Unilorm Replacement 350
5.10
With Ruplasament Touns
Fours
Importecce Tawne
-10-
Iriestlance [oo
Ingultaced (igrem
Insertance Taon -21
Importance 121
10
Inpermance Unete
10
Importance Tuance
Inseriancel Toons +b01
Inpritnee (ipormb0l
10a
0.0
02
0-6
grodint calarations
1.0
0.0
0.2
3.1
gradiort cokstations
26
0.8
1.0
(a) Telients = 1, #clients 10
(b) Telients
3, #clients n = 10
Unitorm With Reptacement 11 Uniform With Replocement
10
Uniiamm With Replecement (1 unioo with Replacement
10
30
With Replacement Tuonseto)
unlom Replacomont (nance50)
Importance (1
Impertanca (uasee))
E10
Insormnce 77pman7)
E10
Impertinc Fiows
Inpertancel Tgona 2211
Impictancc Eguna 2211
Insertancel Fanns 255
10:
Impettnce -201
Insertaice
Impertnct
10-
0.0
58 gradent cilaration
0.6
0.0
63
grasient cakouatiess
(c) Telients 6, #clients
10
(d) Telients
9, #clients = 10
Figure 6: Comparison of methods on australian dataset from LIBSVM
A.3 FEDERATED LEARNING EXPERIMENTS WITH LIBSVM DATASET
In this experiment", we compare the Uniform With Replacement sampling and the Importance sampling on the logistic regression task from Sec. A.2 in a distributed environment. The training of the models is carried on australian dataset from LIBSVM. The dataset is reshuffled with uniform distribution, and then it is split across n = clients. In all experiments, we use Algorithm with theoretical stepsizes according to Theorem 9. We take the parameters of the Uniform With Replacement and Importance samplings from Table with q "
According to Algorithm 2, we have the samplings St that sample clients, and the samplings S that sample data from the local datasets of clients. Algorithm 2 allows mixed sampling strategies that satisfy Assumption 4. For simplicity, we consider that the samplings S and S are of the same type.
For the logistic regression, the Lipschitz constants L, and Lij of the gradients of functions fz( and (x)) can be estimated. As in Sec A.2, we use Thm 4 to obtain the constants Li,,, 1.2 t. T.2 and L2 The results of experiments are provided in Fig. 6. We denote by Tpoints the batch size of the samplings S for all i [n], and by Felients the batch size of the sampling St. The number of gradient calculations in Fig. 6 stands for the total number of gradient calculations in all clients.
We demonstrate results for different values of the batch sizes Telients and Tpoints As in previous experiments, the Importance sampling has better empirical performance than the Uniform With Replacement sampling. In addition we observe that plots with small batch sizes Tpoints converge faster.
A.4 COMPUTING ENVIRONMENT
The code was written in Python 3.6.8 using Py 1.9 (Paszke et al., 2019) and optimization research simulator FL PyTorch (Burlachenko al., 2021). The distributed environment was emulated on a machine with Intel(R) Xeon(R) Gold 6226R CPU @ 2.90GHz and 64 cores.
"Our code: https: http://pppp///.oooo/o/////rreeer
15

---

Under review as a conference paper at ICLR 2023
B AUXILIARY FACTS
We use the following auxiliary fact in out proofs:
1. Let us take random vector IRd then
E
|E E -IS-BBSII'' + [|B[S]1?
(6)
C EXAMPLES OF OPTIMIZATION PROBLEMS
Example 1. For simplicity, let assume that is even. Let consider the optimization problem (1)
with fi(x)) _ + gx²² for i E (1,.... . nn/2) and fe(x)
_ + h for E 1n/2+1,-. ,n),
where x E IR and b 2 O. Then f(x) y=²² and
V f(x) vf(v)l 6².
L sup
x - y|
azy
Moreover,
E [V((() f
1 ((a ((a+b)² + (a - (a-b)3).
_ sup ady
| - y|
2
and we can take arbitrary large. Example 2. Let us assume that n 2 2 and consider the optimization problem (1) with fi()) = -/2²
and fx) = 0 for i (2.... ,n), where R and b 2 0. Then f(x)
b x²
|f(z)) fl('l
b
L sup
I y/1
z/y
1
|V (x) - (u)(1)11
6
Li
sup xzy
|| - vl
[=1
and
Vf((z) v.((2))11
sup zzy
|| y|
Vn"
Example Let consider the optimization problem (5) with f(x) 3 Ei= 1 E==1 fi(()) and
m
(x) x² for all i E [g] and j E [m]. where R and b1 2 0 and 6; = for i E .2)....gh.
Then
f(x)
b 2
2g
VV (x) - vf(v)] b1
L_ sup z
| yl
g
V (f)(2)11 1[V - v (1
1
L sup
gm
b7.
| - w|
9 g²
z
and
1 Σ [z)((r fur( - - vf(eill
L sup
Wi W
|| 2
azy
Substituting the smoothness constants to the complexity N Nuniform from Sec 3 and Nuniform from Sec 4, one can show that
+ n .((++ Ao max (VTL,, 1. (/bb = n Aayabi
N Nuniforn
co(++
E/O
and
12 13 1
Ag max
Aobi
N Ngroup
n
θ n
E
The complexity N Ngnup is /n/yg times better than the complexity Nunitoem-
16

---

Under review as a conference paper at ICLR 2023
D MISSING PROOFS
Lemma 1. Suppose that Assumption 2 holds and let x²+1 = x² - -gg²- Then for any g' E T and
Y O, we have
1(xltt)
S f(x)) - 2 [f('')]1
(
L-
|| - =011² + 7 11
V/ (7)
27 2
2
Proof. Using Assumption 2, we have
f(xlt1) - f(x²) + (Vf ) x.+1 - x²)++ + L-
2 | - x²11
= -(x') - (VS(x*) ((((=)))))))) + L-
2 || 001
Next, due to (2x 2 ||20 - y/1 - ||=1| -2 |1 we obtain
1( S ((x') - 7 |[ 27 2
L-
|| x²11²
+ 2/2 21o' (
Theorem 5. Suppose that Assumptions 1, 2, 3 hold and the samplings
St S(A, B, {ws }
Then Algorithm 1 (PAGE) has the convergence rate E [[
24g +
where 5
(L- [ 1- 1 ((A-B) L3 BL3 1.m)
Proof. We start with the estimation of the variance of the noise:
E ||g (f( 1|
(1-p) ||s (VV)6
(1-p)F) ||oo* S (IVI(
vf(*t)
11g - {f(
where we used the unbiasedness of the sampling. Using Assumption we have
E |1 - vf(a \\ ||]
< (1 - p)
A 1=1
[/[(o+t))- - V - B | - -V((>)1
n2w;
+ p) ||g v
Using the definition of I,,,00 and Ln we get
11g
v5(x+t1) ||
E
1
- - - [[[(((+*)) - vS(at)12)
< (1 - p)
A
n2w;
i=1
+ (1 p)
l|g - vf(z')||
= (1 - p)
(A B)
Σ n2ws
|[f((ttt)) - -
(8)
[ V)( | ( -((e)))))))))))
+B B
Σ
fi/l n2w;
+ (1 p) "|g1 - -V
< (1 - p) ((A - (A-B)L3, 2. + BLL -| x + (1 - p) 11 V
17

---

Under review as a conference paper at ICLR 2023
We now continue the proof using Lemma 1. We add (7) with 2p x (8), and take expectation to get
E 1( - 2
1 /
2p
E
f ((²) - - ?
Vs (x')
I_-
| -0'1l=
7 llg't +2210s
VS (x*))²
27
2
2
1 (1 (1-p) 4s ( 2| + (1 - p) ((A B)T 1, BB ||/ - x912
2p
(9)
E
(( f +
g v (z') 2
2/1 11V5 (z') 1|
2p
1 4- (1
(1-ph ((A B) 12,,0 BL2 m0)
||ott!--t
27 2
2p
E
f f(+))
- fr + Y g Vf
(z')1
2 || (x') 11
2p
where the last inequality holds due to stepsize
1
L-
11-p1 2p
((A - B) 12,,, + BL2,,) 2 0 by choosing
27
2
I-P ((A - B) L3 + BBL
s -- +
(L--B)46
Now, if we define $ = f(x²(( f + zे/ l1g - Vf (I+ then (9) can be written in the form
E [[
E
E
Vf (-
Summing up from = to T 1, we get
T 7-1 Σ
E [p < E [
E V (x') (2]
Then according the output of the algorithm, i.e., Br randomly chosen from (x* heery and L = f (x²) - f + 2 Vf (x.) = f (z²) fo der Do, we have
E [|] S
24o IT
Theorem 6. Suppose that Assumptions 1, 2, 3, 5 and the samplings S E S(A, B, (w;)a_))
Then Algorithm (PAGE) has the convergence rate E [f(x²') - f < (1 7112 Do, where
/(1-)) S min (I=+ 2(1-p) ((A B) L3 + BL2,.))
Proof. From the proof of Thm 5, we know that
E - -1---1--- )11
(1 p) ((1 - B) 122 + BL2
||
-x
2²1 + - p) Ilo1 vs(x))]1 (10)
18

---

Under review as a conference paper at ICLR 2023
Using Lemma 1, we add (7) with 3 x (10), and take expectation to get
E ((+ - + 7 11 - /
p
< E s (x9) - - ? | (x
---21 1 - + Ells v. (x,))1
--
27
2
E (1 p) |6ا1 - // (x') (1 -1-))) p) ((A -A--1) B) 12 + +BL =
+
p
(x0)) 1" + (1 2) 1 و ( - -
E
p
1
L- (1-ply
((A - B) L,,00 + BL2 || |
27
2
< (x²)
E
s
l" + (1
p 2 | -
2
where the last inequality holds due to stepsize
1
L_
11-p12
((A- - B) L33 m + BL2 2 0 by choosing
27
2
p
2(1 p)
S レ- +
((A B) 1,,, + BL2,..
p
Next, using Assumption 5 and y S
p 2x
we have
E [(att1)- f + - -11 \](
p
$ < (1-74)E (z+) - - _ l1oe - VJ (+))))
Unrolling the recursion and considering that g" fx))), complete the proof of theorem.
E DERIVATIONS OF THE PARAMETERS FOR THE SAMPLINGS
E. Nice SAMPLING
Let be random subset uniformly chosen from [n] with fixed cardinality 7. Let fix di,.... Un E
Rd. A sampling S(ai,...,,a.) == Lies pt is called the Nice sampling, where p; == Prob(i E S).
Let us bound E ||a - -
and find parameters from Assumption 4. Note that |S] = |S|| = 7. We introduce auxiliary random variables
+ a:l aP]]
{
i iES otherwise."
X
{
19

---

Under review as a conference paper at ICLR 2023
Due to p: Prob (i E) n.
we have
U4
F.
Xidi
Pi
iES
||xeail
1
+
Kxia, Xjaj)
its
[xx]] ||,s11 2
+ 72
Σ
E [xx xi)l (a),
itj
1 + T 1
||::
(ais ag)
11 1)T
ifj
2
1
T-1
||a||
| 2
ai
11
n(n 1)T
n - 7
Σ
||:il +
ύ-1 1
T(n 1)
n(n 1)T
i=1
where we use E [x]] E [xil
_ and E [xxxy]
- n(a-1)
when i * j.
Finally, we have
a
0
E
iES
iES
n 7
1
|a,11
T-1 1
7(n 1)
n(n
1)7
i=1
n-T
1
|| 1|
1
a
7(n 1)
n i=1
Thus we have A B n-r and w. = n 7(x-1)
1 for all i E [n].
E.2 Independent SAMPLING
Let us define i.i.d. random variables
{
with probability P:
Xi {
with probability 1 ps:
[n] = 1}. We now fix a)....,,,, a, E Rd, A sampling a: is called the Independent sampling, where p. Prob(i S). S(a), -....... an) = Eies pt
for all E [m] and take S == {i E
20

---

Under review as a conference paper at ICLR 2023
We get
1
1
1
E
Σ 01
= E
Xx
Pi
Pi
iES
t=1
E
[
E Xi bxi
1
|0:11
(ai, az)
04
p2
n² pipp
11
i=1
||0:1| 2|
+
1
Σ 1=1
a
||i11
nFpp
n²
1=1
-1
||::11.
n
Pi
1=1
Thus we have A
B
and W/
for all i E [n]].
Σn
En
E.3 Importance AND Uniform With Replacement SAMPLING
Let us fix t > For all & E [r], we define i.i.d. random variables
1
with probability @1
2
with probability d2
X
n with probability ga.
where (g),..., (n) E S (simple simplex). A sampling
S(ap....,....
ax
n4xx
called the Importance sampling. The Importance sampling reduces to the Uniform With Replace- ment sampling when qi 1/n for all i E [n]. Note that [S| S
Let us bound the variance
Oxk
1
E
na
71
1=1
Oxk
1
ax
0 dxe n4xx
Σ
E
E
ndxx
ndxx
k=1
1=1
Agk
i=1
1=1
Using the independents and unbiasedness of the random variables, the last term vanishes and we get
E
axa
Σ
E
axa
1
nd
71 1=1
nlxx
7
i=1
(6)
E
axi
04
04
749
i=1
1=1
1
||a.1|
Q
n4
1=1
1=1
Thus have A B- 1, and w; qi for all i [m].
21

---

Under review as a conference paper at ICLR 2023
E.4 Extended Nice SAMPLING
In this section, we analyze the extension of Nice sampling. First, we I times repeat each vector a;. then we use the Nice sampling. We define
Ej 11
1sish
2
4 ++t
nda
a3 :=
E
On Eis Σド= 4,
ain
where a, E Rd and 4 2 1 for all i E [n].
Then we have
1
(.) Σ az(2).
72
where N = Ej=ı 4. Also, we denote No = c Σラ 4
For some 7 > 0, we apply the Nice sampling method:
N
1
1
S(a1.-..,,1
an)
Xidi
N
Pt
where
[1 ie S
X
= Prob (i E S)
0
otherwise
and S' is a random set with cardinality from [N]. The sampling S(a1,.... an) is called the Extended Nice sampling.
We now ready to bound the variance. Using the results for the Nice sampling, obtain
27
E
S(a
an)
n
E
S(a
an)
(x)
ā.
N
N
1
| 11
0
T(n
1) N
7(n
1)
N
i=1
1=1
T
N
2
Ni
||
2
N 2
Σ N=N++
N2
||22|
7(n
1)
nl
ntz
N
N
||,l1?
n - T 7(n 1)
N
nll
72 1=1
i=N--1+1
N
|aj|
1
N
||a2| 2
+
N
||anll"
71
0
T(n 1)
nl n
n22 n
nln n
T(n
71
n-T
||a:1|
n2 7
1
7(n 1)
n² w
7(n 1)
72
where w/ .. Thus we have A B カ-T
and w & for i E [n]]
7(n-1)
22

---

Under review as a conference paper at ICLR 2023
F THE OPTIMAL CHOICE OF Wi
Let us consider I2 and 12 In Sec 2, we show that one can take 12,,0 = I
- Lg Let us minimize Ei=1 2 D with respect to the weights such that W1y...r Wn and Ei= W; 1. Using the method of Lagrange multipliers, we can construct Lagrangian
1 + nww
C(w, A)
1 71 i=1
Li
Σ 1=1
n1
w -
Next, we calculate partial derivatives
OC
1
L3 - X
O'i E [n]
Ow;
n² n²w?
and get
L
3
2²
Using Σi=1 Wi = L, we can show that the weights w. tion problem. Moreover,
Σ. L. are the solutions of the minimiza-
2
n
L2
L
L
20
n1
n
G THE COMPLEXITY OF ALGORITHM 1 WITH THE Importance SAMPLING
The expected number of gradient calculations Vfr of Algorithm with the Imporiance sampling, the optimal w," from Sec. F, and r v max VOL+a. equals
A
Vn
N Vimorrtance =
0
n
T
L
+
L?
E
71 i=1
TEUR
Ag
I
Vn
T n Σ
Tuj
8
Ao
DovT ( Σ L;)
n
VnL+,w
8
Auyn (1 E.= L.)
n1
H MISSING PROOFS: THE COMPOSITION OF SAMPLINGS
Lemma 2. Let us assume that random sampling function S satisfies Assumption 4 with some A, B and weights wes and random sampling function S; sutisfy Assumption 4 with some Ai, B, and weights Wig for all i E [n). Moreover, B < Then
1
E
S (Si (aii...., (al....,amm))) ..m.)......
...., Sn (anty .... apm,.
a
i=1
1
(1 B)
A
+
|ais
B;
Oij
nw
m;
Willi
l=
j=1
23

---

Under review as a conference paper at ICLR 2023
A
1
my
aij
B
aij
71
new;
mi
m
where ai E R for all j E [mm and i E [n]]
Proof. We denote ā == S; (a:1.... aim. and = m.
1
2==1 aij. Using (6), we have
1
E
S (a)
an)
0g
iml
=
E
Es
S ((j,...., an)
0g
1=1
=
E
E.s
(T)
k
+
E
0g
04
72
1=1
Next, using Assumption 4 for the sampling S, we get
kx)) 1
E
S
(ā)
n2
1
A
E
|0,1
BE
TWWl;
n
i=
E
ai
im
Due to (6), obtain
11
E
[1
an)
0
n
1
1
<
A
E
||0: a,11?
+
A
||a:|'
nwW
7220%
km
[=1
1
BE
02
B
im
2m1
+ E
a
1=1
1=1
1 12
1
E
||ā:
- 131
+
1
11
1
||a:|]
12
11
1=1
11
1
12
1
+
B)E
0
aj
a
n
71
n
1
1
1
A
E
||0: -a11?
+ A
Σ
||a:|
71
i=1
[=1
+
(1
B)
|a=
- [=]
aj
n
1=1
24

---

Under review as a conference paper at ICLR 2023
A
+
(1
B) n
E a..
a:11"]
+A
1 12
Σ
1
||a:1l
B
1
n
nw;
Using Assumption 4 for the samplings S;, we have
E
S
(n)
f=1
A
(1
B)
1
A
|
B, ||as11 112
m
M,
==1
1
n2
1
||
2
1
0j
71
nWW
n2
Theorem 9. Suppose that Assumptions 1, 2, 3, 6 hold and the samplings S
S(A, B, 1= and the samplings S E S(A,, Bi, Awn } for all E [n]. More-
over, B S 1. Then Algorithu has the convergence rate E. [| S
20. where g
7 L-
P
B) (cA: B.LL, 2.)) 1 (A BYL 1 BL
Proof.
We start with the estimation of the variance of the noise:
E ||g (f(
(1 |00 + (s. -
-V
(1 p) ss (ls, -
- Vi [ (V + +1 (1-p)) p) l|g - {z(2))]
where we used the unbiasedness of the composition of samplings. Using Lemma 2, have
E - (1
(1- (1-B)
A 1
V - V[oc(tt)1 B, ( -
< (1 p)
m
miFliig
i=
+ Σ
n
1
V/((+))1
B V -1 VS((+))1))
-
nw;;
i=1
+ (1 p) |وgs V/(x')1''
Using Definitions 2, 3, 7 and 8, we get
E |
A
(1 (1-B) B)
A; B
m+
<11 p)
Ve (z - V/ag(aa))
n
n
m;
miWli
j=1
+
B,
my
1
Viiy(0++1)
Vfb((=))1 - |[(((t()))
m
my
Wi
+
[)((=++1)- - v
n
25

---

Under review as a conference paper at ICLR 2023
1
- - -1 -
+B
7
nww;
+(1 p) I1gs [](2')||
ト a
A
(1-B)
S1
((A, Bi)L + B,L, 2,,) + (A
B)L3, + BBL
|| 2²11
n
(1 p) l
vf(>"||"
From this point the proof of theorem repeats the proof of Thm 5 with
A
B)
)
+
((A, B. + m, + (A B)T + BT
n
instead of
(A B) 13 + BL2
26

---

Under review as a conference paper at ICLR 2023
I ARTIFICIAL QUADRATIC OPTIMIZATION TASKS
In this section, we provide algorithms that we use to generate artificial optimization tasks for experiments. Algorithm and Algorithm allow control the smoothness constants L4 and Li, accordingly, via the noise scales.
Algorithm Generate quadratie optimization task with controlled L (homogeneity)
1: Parameters: number nodes nt, dimension d, regularizer A, and noise scale s.
2: for i .,..., do
3: Generate random noises V 1+ o and v = s iid. Eg 5 NormalDistributionn(. 1)
4: Take vector b; ( + 0,. 0.. 0) E R
5: Take the initial tridiagonal matrix
A; 197
-1
e Rdxd
-1
6: end for
7: Take the mean of matrices A
EE= A;
8: Find the minimum eigenvalue Amnnn (A)
9: for = I,..., n do Update matrix A; Ai (2 Amin (A))I
11: end for
Take starting point x00 (Vd.0...... .0
13: Output: matrices A,, An, vectors b, bn. starting point x
Algorithm 4 Generate quadratic optimization task with controlled L;
1: Parameters: number nodes n., dimension d, regularizer X, and noise scale
2: for 1...., n do
3: Generate random noises 1 = + sEf, where i.i.d. ę ExponentialDDisrriuutii
4: Generate random noises 1/ sch iid & ~ NormalDistribution(() 1)
5: Take vector 6; (- + vh, 0, ... 0) E Rdd
6: Take the initial tridiagonal matrix
A
1/2
-1
e Ddxd
-1
-1
7: end for
8: Take starting point _0 (Vd.0, (V..0.....00
9: Output: matrices A1. An, vectors by bn. starting point x
27


Reviews:
[{"review_id": "eZYOGV94RV", "reviewer": "Reviewer_NfNX", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "#### ***Background*** :\nCurrent convergence results to attain \\epsilon approximate stationary point using first-order stochastic methods (ex SGD and its more recent variants like SARAH, PAGE) while achieve the optimal rates matching the lower bounds; the analysis has the following issues - (a) The big-O notation in the above results hides important and typically very large data-dependent constants (smoothness). The paper shows via simple examples to motivate why the dependence on L can be crucial. (b) Further these results are under the 'random' data sampling assumption -- which is often not true in modern distributed and federated learning settings. Prior work has analyzed different non-optimal SGD variants under different sampling schemes and showed improved constants.\n\n#### ***Main Contribution*** : \nIn this paper the authors unify these proof ideas and propose a unified framework to analyze PAGE and also show that it is possible to improve the convergence under certain sampling assumptions.", "summary_of_the_review": "I reviewed an earlier version of the paper for NeurIPS and unfortunately, the paper hasn't improved - in fact on a closer look they seem to have submitted the same draft w/o any changes. The paper still has significant weaknesses and unfortunately they didn't use the resubmission to improve upon them. ", "strength_and_weaknesses": "#### ***Strengths*** :\n1. Overall the paper is really well written, proofs are clean and easy to follow,\n2. The refined analysis will serve as a good consolidated reference note for using sampling in practical optimization settings - while the proofs are hard to find from a plethora of different papers.   \n\n#### ***Clarifications*** :\n\n1. Overall, I feel that the novelty is marginal. The main novelty in my understanding is the introduction of two smoothness constants introduced in Def 2,3. The rest of the proofs seem routine given the proof technique introduced in Richtárik62and Takáˇc (2016) in the study of randomized coordinate descent methods, Horváth and Richtárik63(2019) and Qian et al. (2021) in analyzing SVRG, SAGA, and SARAH.\n\n2. The paper simply extends the convergence results of PAGE under the non-traditional finer smoothness constants and the results while new are not surprising.\n\n3. The claims rely on the sampling strategy being aware of $L_i$ - I am not sure how is this of any practical importance since it is not available in practice. \n\n4. PAGE with important sampling performs better (Fig 3) - well this is known result.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "aof-CIfD2m", "reviewer": "Reviewer_CFoS", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This work reconsiders the problem of finding stationary points of finite-sum of $n$ smooth functions, where the optimal complexity for stochastic first-order methods is already known to be $\\mathcal{O}(n + n^{1/2} \\epsilon^{-1})$. The authors proposed to do a refined analysis since the $\\mathcal{O}$ could hide dependencies on smoothness constants, which could be unbalanced across different individual summands, and also a more detailed analysis for different sampling procedure to obtain stochastic gradients.\n\nThe authors generalize the analysis for PAGE method (Algorithm 1)to work for different sampling mechanisms, where the $L_+$ smoothness constants could possibly be improved as shown in Table 2. In particular, the authors define a new quantity called weighted Hessian Variance, which improves previous results as also shown in Table 2. Finally, the authors show that the analysis works for samplings used in federated learning.\n\nThe key technical results are to show that different sampling methods satisfy a weighted AB inequality (Assumption 4) as summarized in Table 1.", "summary_of_the_review": "Overall, I found the motivation reasonable and results interesting. However, it is unclear to me how we could use the results to compare different samplings and guide practice, which makes it unclear to me if doing the refined analysis does provide enough benefits. ", "strength_and_weaknesses": "**Strength**:\n\n1. The motivation of doing a refined analysis seems reasonable to me. The authors argue that this could be useful in federated learning.\n2. The more detailed analysis does improve the previous results and are more flexible for different sampling methods.\n3. The study of different samplings satisfying the weighted AB inequality is interesting, which provides intuitions for differences between sampling methods.\n\n**Weaknesses**:\n\n1. The work is still not enough to convince me doing the analysis does provide enough benefits. For example, from federated learning results in Section A.3 it can be concluded that the importance sampling achieved the best performances. How can we conclude from the complexity results in Table 2 that the analysis does reflect the experimental results?\n2. The results in Table 1 seem interesting. As mentioned in the paper, larger B values allow tighter results to be obtained. How do other quantities have impacts on performances of sampling methods?\n3. It is unclear to me how should we compare different sampling methods from Table 2. In particular, how do we compare complexity quantities of different samplings.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Z5f6zjxwzLG", "reviewer": "Reviewer_xtiL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_paper": "This paper generalizes the PAGE algorithm and analyzes that it can improve the convergence rate with virtually any (unbiased) sampling mechanism using a novel assumption.It is helpful in the analysis of problems from federated learning.Some carefully designed experiments have verified theoretical results.", "summary_of_the_review": "This paper generalizes the PAGE algorithm and analyzes that it can improve the convergence rate with virtually any (unbiased) sampling mechanism using a novel assumption.It is helpful in the analysis of problems from federated learning.Some carefully designed experiments have verified theoretical results.\nAlthough the paper is theoretically sound, there are still some questions need to be discussed in this paper:\n1.\tAbout assumption.It would be better to make a attempt to prove assumption 4 was satisfied in SPIDER and SARAH.\n2.\tThe chart in Figure 3 lacks coordinate description.\n3.\tAbout the experiments. All experiments are telling that some samplings can improve the convergence rate of PAGE.Importance sampling performs better.About other sampling schemes in Table 1,it would be better to add them to the experiment.\n", "strength_and_weaknesses": "Strength: This paper generalizes the PAGE algorithm and analyzes that it can improve the convergence rate with virtually any (unbiased) sampling mechanism using a novel assumption.It is helpful in the analysis of problems from federated learning. This paper is theoretically sound in general.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "45olYQffGu", "reviewer": "Reviewer_paK1", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper considers a probabilistic gradient method (PAGE). The authors invoke different kinds of sampling schemes and claim that the new result is shaper than the original one.", "summary_of_the_review": "The techniques are copies of those of (Li et al., 2021) and (Szlendak et al., 2021). I obtain this conclusion by reading their proof of Theorem 5 and that of Thm 1 in (Li et al., 2021) and that of Thm 4 in (Szlendak et al., 2021), which is a step-by-step copy-style. I would say the essential contribution is that the authors changed the compressor's property to a sampling property. The authors verified that several sampling schemes do satisfy their Assumption 4 (Indeed, an unbiased compressor seems similar to unbiased sampling in terms of analysis). It is good to know the result. However, I have to say that such a contribution does not meet the requirement for possible publication in ICLR.\n\n[Li et al., 2021] PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In International Conference on\nMachine Learning, pp. 6286–6295. PMLR, 2021.\n\n[Szlendak et al., 2021] Permutation compressors for provably faster distributed nonconvex optimization. arXiv preprint arXiv:2110.03300, 2021.", "strength_and_weaknesses": "The new sampling assumption is justified by considering several representative sampling schemes. However, the technique is a direct combination of (Li et al., 2021) and (Szlendak et al., 2021), rendering this manuscript far from possible publication in ICLR.\n\n\n[Li et al., 2021] PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In International Conference on\nMachine Learning, pp. 6286–6295. PMLR, 2021.\n\n[Szlendak et al., 2021] Permutation compressors for provably faster distributed nonconvex optimization. arXiv preprint arXiv:2110.03300, 2021.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject