Optimal Time Complexities of Parallel Stochastic Optimization Methods Under a Fixed Computation Model
Authors: Alexander Tyurin
Peter Richtárik
Venue: NeurIPS 2023 poster (2023)
Keywords: nonconvex optimization
convex optimization
parallel methods
asynchronous methods
lower bounds

Abstract: Parallelization is a popular strategy for improving the performance of methods. Optimization methods are no exception: design of efficient parallel optimization methods and tight analysis of their theoretical properties are important research endeavors. While the minimax complexities are well known for sequential optimization methods, the theory of parallel optimization methods is less explored. In this paper, we propose a new protocol that generalizes the classical oracle framework approach. Using this protocol, we establish minimax complexities for parallel optimization methods that have access to an unbiased stochastic gradient oracle with bounded variance. We consider a fixed computation model characterized by each worker requiring a fixed but worker-dependent time to calculate stochastic gradient. We prove lower bounds and develop optimal algorithms that attain them. Our results have surprising consequences for the literature of asynchronous optimization methods.

Optimal Time Complexities of Parallel Stochastic Optimization Methods Under Fixed Computation Model
Alexander Tyurin
Peter Richtárik KAUST
KAUST
Saudi Arabia alexandert.uurii@mmll.cc
Saudi Arabia
richtarik@gaillcom
Abstract
Parallelization is a popular strategy for improving the performance of iterative algorithms. Optimization methods are no exception: design of efficient parallel optimization methods and tight analysis of their theoretical properties are important research endeavors. While the minimax complexities are well known for sequential optimization methods, the theory of parallel optimization methods is less explored. In this paper, we propose a new protocol that generalizes the classical oracle frame- work approach. Using this protocol, we establish minimax complexities for parallel optimization methods that have access to an unbiased stochastic gradient oracle with bounded variance. We consider a fixed computation model characterized by each worker requiring fixed but worker-dependent time to calculate stochas- tie gradient. We prove lower bounds and develop optimal algorithms that attain them. Our results have surprising consequences for the literature of asynchronous optimization methods.
Introduction
We consider the nonconvex optimization problem
min { f(x)) == R&WD (((:)))) =EQ
(1)
where f x - = R2, and & a random variable with some distribution on Sg. In machine learning, Sg could be the space of all possible data, 'D is the distribution of the training dataset, and f(., {) is the loss of data sample ç. In this paper we address the following natural setup:
(i) n workers are available to work in parallel,
(ii) the 7th worker requires т; seconds' to calculate stochastic gradient of f.
The function is I-smooth and lower-bounded (see Assumptions 7.1-7.2), and stochastic gradients are unbiased and o² --variance-bounded (see Assumption 7.3).
1.1 Classical theory
In the nonconvex setting, gradient descent (GD) is optimal method with respect the number of gradient (Vf) calls (Lan, 2020; Nesterov, 2018; Carmon et al., 2020) for finding an approximately stationary point of f. Obviously, key issue with GD is that it requires access to the exact gradients
Or any other unit of time.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Vf of the function f. However, in many practical applications, it can be infeasible to calculate the gradient of (=) analytically. Moreover, even if this possible, e.g., if the distribution D is described by possible samples, so that EE (=: {)] (1/m) 2i=1 ((): m can be huge (Krizhevsky et al., 2017), and gradient
gragiiient evaluation can arbitrarily expensive.
Stochastic Gradient Descent. Due to the above-mentioned problem, machine learning literature is preoccupied with the study of algorithms that can work with stochastic gradients instead (Lan, 2020; Ghadimi and Lan, 2013). For all I E IRd, we assume that the n workers have access to independent, unbiased, and ---variance-boundde a random sample from Under such assumptions, with one worker, stochastic gradient descent (SGD), i.e., the method -*+1 = x² y fx=: (aa":"" <h), where ş are i.i.d. random samples from D, is known be optimal with respect to the number of stochastic gradient calls (Ghadimi and Lan, 2013; Arjevani et al., 2022). SGD guarantees convergence to an e-stationary point in expectation after O LA/e + ('L2))2) stochastic gradient evaluations, where A f(x²) I" and x0 Rd is starting point.
stochastic gradients A (xx E) (see Assumption 7.3), where is
1.2 Parallel optimization methods
Using the bounds from Section 1.1, easily estimate the performance of these algorithms in real systems. For instance, it takes T seconds to calculate a stochastic gradient with one worker, then SGD guarantees to return solution after
o
0
LA
LA
seconds. If instead of a single worker access workers that calculate stochastic gradients in parallel, we can consider the following classical parallel methods:
Minibatch SGD. The minibatch SGD method (Minibatch SGD), i.e., the iterative process
.+1
f 5*),
where y is stepsize, & are i.i.d. samples from D, and the gradients & </: are calculated in parallel. This method converges after O (LA/e + d² =A/="") iterations (Cotter et al., 2011; Goyal et al., 2017; Gower et al., 2019) and after
LA
o 2 LA
Tmax
(2)
ng²
seconds, where Tiax max Ty is the processing time associated with the slowest machine
Although the time complexity (2) of Minibatch SGD improves with the number of workers n, in general, this does not guarantee better performance due to the delay Tmax. In real systems, parallel computations can be very chaotic, e.g., they can be slow due to inconsistent network communications, or GPU computation delays (Dutta et al., 2018: Chen et al., 2016).
Asynchronous SGD. We now consider the asynchronous SGD method (Asynchronous SGD) (Recht et al., 2011; ;; Nguyen et al., 2018; Arjevani et al., 2020; Feyzmahdavian et al., 2016) described by
Receive V fx 46x 6k from a worker,
2. x 1+1 = x f
Ask the worker calculate (f
where g* are i.i.d. samples from DD and òg are gradient iteration delays. This is an asynchronous method: the workers work independently, finish calculations of stochastic gradients with potentially large and chaotic delays 6R, and the result of their computation is applied as soon as it ready, without having wait for other workers. Asynchronous SGD was also considered in the heterogencous setting (see details in Section A.2).
Further, assume that the last nhth worker is the slowest Tmaxx

---

Table 1: Homogeneous and Heterogeneous Case. The required time get an e-stationary point [B]]V 8) in the nonconvex setting, where 7th worker requires 7; seconds to calculate stochastic gradient. We assume that 0 < S .... S Tn-
Homogeneons Case
Heterogeneous Case
Method
Complexity
Method
Complexity
Minihatch SGD
Tix
LA
-2L me
Minihatch
Tw
LA
o'
mc
Asyuchronous SGD (Cohen et ul., 2021)
1
Malenia (Thoorem A.4)
LA
2
(Koloskova et al., 2022)
[-]
(Mishchenko et al., 2022)
Rennala SGD (Theorem 7.5)
min mc [g]
1/4
2
-1
(يي + مييده
Lower Bound (Thoorem A.2)
Tn
La
+
n
To
2
nx"
Lower Bound (Theorem 6.4)
1
مياهه
mc [N]
Cohen et al. (2021); Mishchenko et al. (2022); Koloskova et al. (2022) provide the current state-of- the-art analysis of Asynchronous SGD. In particular, they prove that Asynchronous SGD converges after (nLA/e + L iterations. To show the superiority of Asynchronous SGD, Mishehenko et al. (2022) consider the following fixed computation model: the 7th worker requires seconds to calculate stochastic gradients. In this setting, Asynchronous SGD converges after
o ((=11)
LA
LA nE²
(3)
seconds (we reprove this fact in Section L). Thus, Asynchronous SGD can be (1/x) Ei=
times faster than Minibatch SGD.
Besides Asynchronous SGD, many other strategies utilize parallelization (Dutta et al., 2018; Wood- worth et al., 2020; Wu et al., 2022), and can potentially improve over Minibatch SGD,
2 Problem and Contribution
In this paper, we seek to find the optimal time complexity in the setting from Section 1: our goal is to provide a lower bound and method that attains it. Our main contributions are:
(i) Lower bound. In Sections 4 & 5, we define new Protocols & 3, and a new complexity measure mime (see (6)), which we believe are more appropriate for the analysis of parallel optimization algorithms. In Section 6, we prove the time complexity lower bound for (nonconvex) functions and algorithms that work with parallel asynchronous oracles.
(i) Optimal method. In Section 7, we develop a minimax optimal method Rennala SGD that attains this lower bound.
In addition, we investigate several other related questions. As an independent result, in Section we prove that all methods which synchronize workers in each iteration (e.g., Minibatch SGD) have provably worse time complexity than asynchronous methods (e.g., Rennala SGD (see Method 4), Asynchronous SGD). In Section A, we extend our theory to the heterogeneous case, in which the workers have access to different distributions (datasets), and provide lower bound and new method that attains it. In Section B, we provide the optimal time complexities in the conver setting.
httpe://o //t/de/r/dnggggeeeeeee wikt fextralife. con/tennals -uueet+ -oeee-o---ceeeee +th++ PMoon Rennala, Queen of the Full Moon is Legend Boss in Elden Ring. Though not demigod, Renmala of the shanlbearers who resides in the Academy of Raya Lucaria. Rennola is powerfull sorceress, head of the Carian Royal family, crsihbile Academy.
3

---

3 Classical Oracle Protocol
Let us recall the classical approach obtaining lower bounds for optimization algorithms. We need to define a fimction class F, an oracle class O, and an algorithm class A. We then analyze the complexity of an algorithm
1 E A, using the following protocol:
Protocol Classical Oracle Protocol
1: Input: function f E F, oracle and distribution (O,D) e O(f), algorithm E A
2: for = 0, O..... 00 do
3: zf A ...g..".))))
x0 for
4: gx+11 = O(r", ghitl), gh+1 D
5: end for
More formally, in first-order stochastic optimization, the oracle class O returns random mapping I2 x Se + Hd based on a function f E FF and a distribution D; we use the notation (0, D) E Of).. An algorithm A [ E A is sequence such that
1 Rdd
RR
Rd Vk 21,,, and A E IRd
Typically, an oracle O returns unbiased stochastic gradient that satisfies Assumption 7.3: (xr, {) V f(x;; for all x I& and E &ę. Let us fix an oracle class O. Then, in the nonconvex first-order stochastic setting, we analyze the complexity measure
Moracle (A.F) == inf sup sup inf { e [|| sej.
(5)
AEA SEF (0,D)EO(S)
where the sequence {a*}* is generated by Protocol 1. Virtually all previous works are concerned with lower bounds of optimization problems using Protocol 1 and the complexity measure (5) (Nemirovskij and Yudin, 1983; Carmon et al., 2020; Arjevani et al., 2022; Nesterov, 2018).
Time Oracle Protocol
In the previous sections, we discuss the classical approach estimating the complexities of algorithms. Briefly, these approaches seek to quantify the worst-case number of iterations or oracle calls that are required to find solution (see (5)), which very natural for sequential methods. However, and this is key observation of our work, this approach is not convenient if we want to analyze parallel methods. We now propose an alternative protocol that can more helpful in this situation:
Protocol Time Oracle Protocol
1: Input: functions E F, oracle and distribution (O,D) O(f), algorithm A E A
2: 8 =
3: for k = 0. 0...., do
4: (1R+1, xxk) A (g)
..... gd), 5: (st+1 -g++1)= = 0 11111 xk gh+l), gb+1 D
1++1
6: end for
Protocol is almost identical to Protocol except for one key detail: Protocol requires the algorithms to return sequence [1*+1]00, such that f++1 > 1 ' 0 for all l: > 0. We assume that t = O. We also assume that the oracles take to the input the states s and output them (the role of these states will be made clear later). In this case, we provide the following definition of algorithm.
Definition 4.1. An algorithm
= fA"10e is sequence such that
A
x ... Rd + Rzo x Rd Wk 2 1, E Ezo x Rd,

---

and, for all & 2 1 and g'..... g" IR th+1 2 th, where t and t are defined as (t*+1, (,) (g "ig",,....'"""......
g*) and (t* = A (g -
Let us explain the role of the sequence (t*) Jk- In Protocol 1, an algorithm outputs a point x. and then asks the oracle: Provide me a gradient at the point x² In contrast, in Protocol 2 an algorithm outputs point æ² and time 1h-1, and asks the oracle: Start calculating gradient at the point x² at time p++1 We have constraint that + 2 1 for all 0, which means that the algorithm not allowed travel into the past.
Using Protocol 2, we propose use another complexity measure instead of (5):
miime (A,F) = inf sup sup inf { FEF
E
inf RES.
| sej.
(6)
S. = No st}.
where the sequences t and æ are generated by Protocol 2. In (5), we seek to find the worst-case number of iterations k required to get E. [+**) S e for any A A. In (6), seek to find the worst-case case time required to find an e-stationary point for any A E A.
We now provide example, considering oracle that calculates a stochastic gradient in seconds. Let us define the appropriate oracle for this problem:
R20 x
x
R
x Rd x (0,
XS + (R20 x Rd x (0, xRd
time
point
imput
oulpul state
xtt, 1),
0):
$y
such that 0 (1, (8e, Sy, 8q),E)
(($1, Sz, 1),
0),
Sq 1 and t < St + (7)
0),,
{s)x
Sy and 8t + T,
and V f is mapping such that V Rd Sg + Rd. Further, we additionally assume that A is an unbiased 0² seariance-boundee stochastic gradient (see Assumption 7.3).
Note that the oracle / emulates the behavior of real worker. Indeed, the oracle return three different outputs. If 8, O, means that the oracle has been idle, then "starts the calculation" of the gradient the point v; and changes the state 8g 1. Also, using the state, remembers the time moment when the calculation began and the point æ. Next, if s, = 1 and f < St + it means the oracle still calculating the gradient, so an algorithm sends time such that < St + т, then receives the zero vector. Finally, if 5g = 1, as soon as an algorithm sends time such that 2 8; + т, then the oracle will be ready to provide the gradient. Note that the oracle provides the gradient calculated at the point z that was requested when the oracle was idle. Thus, the time between the request of an algorithm to get the gradient and the time when the algorithm gets the gradient is at least 7 seconds.
have game between algorithm A E A and oracle class O where algorithms can decide the sequence of times t*_ Thus, an algorithm wants to find enough information from an oracle soon as possible obtain e-stationary point.
In Protocol
Let us consider an example. For the oracle class O that generates the oracle from (7), we can define the SGD method in the following way. We take any starting point x. E IRd step size min f/2r,=) (see Theorem D.8) and define A (Rd x Rd) R x RR such that
times
(T [k/22 - -g
1=1 &mod 2) 0,
A ( .........'
(8)
(T(K/21+11)))
(mod 2)
for all 1, and A (0, .;)). Let us explain the behavior of the algorithm. In the first step of Protocol 2, when & 0, the algorithm requests the gradient at the point z. at the time t 0 since
5

---

A = (0,z") 22). The oracle O changes the state from sg = 0 to i = and remembers the point x in the state s². In the second step of the protocol, when k = the algorithm calls the oracle at the time T (L%/2] + 1) = т. In the oracle, the condition t² 2 s + T + T 2 0 + T is satisfied, and returns the gradient at the point xº. Note that this can only happen if an algorithm does the second call at time that is greater or equal to T.
One can see that after T seconds, the algorithm returns the point x 2K
x
y E ff(a"), where & D are iid. random variables. The algorithm is equiva- lent to the SGD method that converges after K = O (1 d'1 steps for the function class FA.L (see Definition 6.1) for α0 = 0. Thus, the complexity mume FA.L) equals O ( x (LA/E+ ( -
Actually, any algorithm that was designed for Protocol I can be used in Protocol 2 with the oracle (7). Assuming that we have mappings A# Rdd x ... x Rdd -> IRdd for all 2 1, we can define mappings
A Rd x ................................ x Rd + R20 x Rd via
T [k/22, Alk/2) g ......g2))) g2m)) (T
k (mod 2) = 0,
(g 9
k (mod 2) = 1.
For k O, we define A = =0, A9)
5 Time Multiple Oracles Protocol
The protocol framework from the previous section does not seem be very powerful because one can easily find the time complexity (6) by knowing (5) and the amount of time that oracle needs to calculate gradient. In fact, we provide Protocol 2 for simplicity only. We now consider a protocol that works with multiple oracles:
Protocol 3 Time Multiple Oracles Protocol
1: Input: function(s) f E F, oracles and distributions algorithm A E A
(DI, D.)) O(),
2: of -0 for all i [n]]
3: for k = 0, O...., Do do
4: (E++1, jeti x²) = A (g) ..... g²)
D D+++1 th
5: (s (s kh+l) , (+++1 x sk Ek+l), ghitl Drets
D D1
st Vj + gh+1
6: end for
Compared to Protocol 2, Protocol 3 works with multiple oracles, and algorithms return the indices (t+1 of the oracle they want to call. This minor add-on to the protocol enables the possibility of analyzing parallel optimization methods. Also, each oracle O can have its own distribution D,.
Let us consider an example with two oracles 0 = ni and O₂ = O from (7). One can see that a "wise" algorithm will first call the oracle O₂ with the time t = O, and then, in the second step, it will call the oracle O₂ also with the time t' = 0. Note that it is impossible to do the following steps: in the first step an algorithm calls the oracle O with the time 1 = O, in the second step, the algorithm calls the oracle O with the time {1 7i and receives the gradient, in the third step, the algorithm calls the oracle O2 with the time 12 = 0. Indeed, this can't 't happen because 12 < 1!.
An example of a "non-wise algorithm is algorithm that, in the first step, calls the oracle O₁ with the time
0. In the second step, the algorithm calls the oracle O with the time t = Ti and receives the gradient. In the third step, the algorithm calls the oracle O₂ with the time f2 = T1. It would mean that the "non-wise wisew algorithm did not use the oracle O2 for Ti seconds. Consequently, the "wise" algorithm algorithm can only receive two gradients after Ti + 72 seconds.
receive two gradients after max/TT, T2 seconds, while the "non-wise"
We believe that Protocol 3 and the complexity (6) is a better choice for analyzing the complexities of parallel methods than the classical Protocol 1. In the next section, we will use Protocol 3 to obtain lower bounds for parallel optimization methods.

---

Lower Bound for Parallel Optimization Methods
Considering Protocol define special function class F, oracle class O, and algorithm class A. We consider the same function class as Nesterov (2018) 8); Arjevani et al. (2022); Carmon et al. (2020): Definition 6.1 (Function Class FA.L). We assume that function f Ra + R is differen- tiable, L-smooth, i.e,, [V Vf(v)) & L ||æ yl Vz, E IR and A-bounded, i.e.
ʃ(0) inlzeR" (() A. set of all functions with such properties denote by FA,L.
In this paper, we analyze the class of "zero-respecting" algorithms, defined next.
Definition 6.2 (Algorithm Class A..). Let us consider Protocol 3. We say that an algorithm A from Definition 4.1 is a zero-respecting algorithm, if supp (a*) S U supp (g') for all k E No, where supp(x) = { E [d] 2 + 0}. A set of all algorithms with this property we define as Aa.
zero-respecting algorithm does not try to change the coordinates for which no information was received from oracles. This family is considered by Arjevani et al. (2022); Carmon et al. (2020), and includes SGD, Minibatch and Asynchronous SGD, and Adam (Kingma and Ba, 2014).
Definition 6.3 (Oracle Class O
Let us consider an oracle class such that, for any f FA,L, returns oracles O = 0 and distributions D; for all i E [n]. where fʃ is an unbiased x²- puriance-boundes mapping (see Assumption 7.3). The oracles O are defined in (7). We define such oracle class as O²" "......." Without loss of generality, we assume that 0 < T1 S ... S Tr.
We take Oa² TI..... because emulates the behavior of workers in real systems, where workers can have different processing times (delays) Note that O TI...,7a has the freedom choose mapping V f. We only assume that the mapping is unbiased and oe-variance-bounded We are now ready to present our first result; a lower bound:
Theorem 6.4. Let us consider the oracle class O P......7 for some o² > 0 and 0 < ... S Tn. We fix any L, A > O and < S CLA. In view Protocol for any algorithm A E Az: there exists function f E Fa,r. and oracles and distributions ((O),.. (DI..... ,.)) Og" Og (J)
such that E infkes, [[V](x*)]])) e, where S {k: No 1k (} and
-1
LLLA
f=ex min mEnn
m
The quantities and e are universal constants.
Theorem 6.4 states that
1
m
LA
σ² LA
meime (Az FA,L)= =Ω
min mEin]
mg?
The interpretation behind this complexity will be discussed later in Section 7.3. No algorithms known to us attain (9). For instance, Asynchronous SGD has the time complexity (3). Let us assume that o²/e < p and E [n). Then (lower bound from (9)) = O ( Σ +) ((A)). (4A) In this case, the lower bound in (9) will be at least ( Σ /
times smaller. It means that either the obtained lower bound is not tight, Asynchronous SGD is suboptimal method. In the following section we provide a method that attains the lower bound. The obtained lower bound is valid even if algorithm has the freedom to interrupt oracles. See details in Section F.
6.1 Related work
For convex problems, Woodworth al. (2018) proposed the graph oracle, which generalizes the classical gradient oracle (Nemirovskij and Yudin, 1983; Nesterov, 2018), and provided lower bounds
7

---

for rather general family of parallel methods. Arjevani et al. (2020) analyzed the delayed gradient descent method, which is Asynchronous SGD when all iteration delays óg = ó a constant.
As far as we know, Woodworth et al. (2018) provide the most suitable and tightest prior framework for analyzing lower bound complexities for problem (1). However, as we shall see, our framework us more powerful. Moreover, they only consider the convex case. In Section M, we use the framework of Woodworth et al. (2018) and analyze the fixed computation model, where 7th worker requires т; seconds to calculate stochastic gradients, In Section B, we consider the convex setting and show that the lower bound obtained by their framework is not tight and can be improved. While the graph oracle framework by Woodworth et al. (2018) 88) is related to the classical oracle protocol (Section 3) and also calculates the number of oracle calls in order to get lower bounds, our approach directly estimates the required time. For more details, see Section B and the discussion in Section B.1.1.
Method 4 Rennala SGD
Input: starting point x0, stepsize y, batch size
2: Run Method 5 in all workers
3: for k = 0, 1.... K- do
Method 5 Worker's ' Infinite Loop
4: Init -* = 0 and
1: Init g = 0 and k' = -1
5: while 8 S 5 do
2: while True do
6: Wait for the next worker Receive gradient and iteration index (g, k')
3: Send (g, k') to the server
7:
4: Receive (x* k)) from the server
8:
if K' = k then
9:
9* = g + sg: s=
5:
k' k
6: g = v)(a)))), E~D
10: end if
11: Send (x*, k) to the worker
7:
end while
12: end while
13: x k++ = x 79
14: end for
7 Minimax Optimal Method
We now propose and analyze new method: Rennala SGD (see Method 4). Methods with a similar structure were proposed previously (c.g., (Dutta et al., 2018)), but not aware of any method with precisely the same parameters and structure. For us, in this paper, the theoretical bounds are more important than the method itself.
Let us briefly describe the structure of the method. At the start, Method 4 asks all workers to run Method 5. Method 5 is a standard routine: the workers receive points x² from the server, calculate stochastic gradients, and send them back to the server. Besides that, the workers receive and send the iteration counter & of the received points z² At the server's 's side, in each iteration k. Method 4 calculates g² and performs the standard gradient-type step xL+11 x² -ng*. The calculation of g done in loop. The server waits for the workers to receive stochastic gradient and iteration index. The most important part of the method that the server ignores a stochastic gradient if its iteration index is not equal to the current iteration index. In fact, this means that g² (1/s) > f((=t;)) where & are i.i.d. samples. In other words, the server ignores all stochastic gradients that were calculated at the points x. x.
It may seem that Method does not fully the information due to ignoring some stochastic gradients. That contradicts the philosophy of Asynchronous SGD, which tries to use all stochastic gradients calculated in the previous points. Nevertheless, complexity than Asynchronous SGD, and this complexity matches the lower bound from Theorem 6.4. The fact that Rennala SGD ignores the previous iterates is motivated by the proof of the lower bound in Section 6. In the proof, any algorithm, on the constructed "worst case" function, does not progress stationary point if it calculates a stochastic gradient at a non-relevant point. This suggested us to construct a method that would focus all workers on the last iterate.
show that Rennala SGD has better time
7.1 Assumptions
Let us consider the following assumptions.
8

---

Assumption 7.1. f differentiable & L-smooth, i... [VV Vf(y))l - L vll Vr, R
Assumption 7.2. There exist f R such that f(z) f for all z e R
Assumption 7.3. For all x E R. stochastic gradients (z; are unbiased and d²-variance-
bounded, i.e., Bg (f(=;) fz(z) and Eg |[ (of(x:))-f((())) Vf(x)]] S so² where o² 2
7.2 Analysis Rennala SGD
Theorem 7.4. Assume that Assumptions 7.1, 7.2 and 7.3 hold. Let take the batch size S
max [[00/] 11 and y = min {t) 2Lo = θ (1/L) ) in Method Then after
24
K 2 E iterations, the method guarantees that 1 EKJLE
| Se.
||+)(=)))
In the following theorem, we provide the time complexity of Method 4.
Theorem 7.5. Consider Theorem 7.4. We assume that it worker returns a stochastic gradient every seconds for all i [n]. Without loss of generality, assume that 0 < T1 S ... Tn- Then after
LA 8
LA
96 min mE(n]
(10)
ms²
seconds, Method guarantees find an E-stationary point.
This result with Theorem 6.4 state that
1
LA
اااههه
miime (An, Fa,1.) =
min m
ms²
(II)
for Protocol and and the oracle class Og?
Ta from Definition 6.3.
7.3 Discussion
Theorem 7.5 and Theorem 6.4 state that Method 4 is minimax optimal under the assumption that the delays of the workers are fixed and equal to тı. Note that this assumption is required only in Theorem 7.5, and Theorem 7.4 holds without it.
In the same setup, the previous works (Cohen et al., 2021; Mishchenko et al., 2022; Koloskova et al., 2022) obtained the weaker time complexity (3). We do not rule out that it might be possible for the analysis, the parameters or the structure Asynchronous SGD to be improved and obtain the optimal time complexity (10). We leave this to future work. However, instead, that has not only the optimal time complexity, but also a very simple structure and analysis (see Section D.4.1). Our claims are supported by experiments in Section J.
developed Method
The reader can see that we provide the complexity the parameter m E [n:] Note that Method 4 automatically finds the optimal m in (7.5), and it does not require the knowledge of the delays T₃ to do so! Let us explain the intuition behind the complexity (10). Let m be the optimal parameter of (10) with the smallest index. In Section D.4.3, we show that all workers with the delays 7. for all > m can simply ignored since their delays are too large, and their inclusion would only harm the convergence time of the method. So, the method automatically ignores them! However, in Asynchronous SGD, these harmful workers can contribute to the optimization process, which can be the reason for the suboptimality of Asynchronous SGD.
nonconstructive way, as the minimization over
In general, there are two important regimes: 0²/s & n ("low noise/large of workers") and o²/8 >> n ("high noise/small # of workers"). Intuitively, in the "high noise/small # of workers" regime, (11) is minimized when m close to n. However, the "low noise/large # of workers". the optimal m can be much smaller than

---

8 Synchronized Start of Workers
In the previous sections, we obtain the time complexities for the case when the workers asyn- chronously compute stochastic gradients. is important that the complexities are obtained assuming that the workers can start their calculations asynchronously. However, in practice, it is common to that all workers
train machine learning models with multiple workers/GPUs, after each stochastic gradient calculation (Goyal et al., 2017; Sergeev and Balso, 2018). The sim- plest example of such strategy is Minibatch SGD (see Section 1.2). We want to find answer to the question: what is the best time complexity we can get if we assume that the workers start simultaneously? In Section G, formalize this setting, and show that the time complexity equals to
synchronized
LA E
LA
Miime
=
min (EE(n)
Tim
me²
(12)
for Protocol 2 and the oracle class - can see that methods that start the calculations of workers simultaneously are provably worse than methods that allow workers to start the calculations asynchronously.
syme .n..TT
from Definition G.I. Comparing (11) and (12), one
9 Future Work
In this work, we consider the setup where the times т; fixed. In future work, consider natural, important, and more general scenarios where they can be random, follow some distribu- tion, and/or depend on the random variables from Assumption 7.3 (be correlated with stochastic gradients).
Acknowledgements
This work of P. Richtárik and A. Tyurin was supported by the KAUST Baseline Research Scheme (KAUST BRF) and the KAUST Extreme Computing Research Center (KAUST ECRC), and the work of P. Richtárik was supported by the SDAIA-KAUST Center of Excellence in Data Science and Artificial Intelligence (SDAIA-KAUST AI).
References
Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N., and Woodworth, B. (2022). Lower bounds for non-convex stochastic optimization. Mathematical Programming, pages 1-50.
Arjevani, Y., Shamir, O., and Srebro, N. (2020). A tight convergence analysis for stochastic gradient descent with delayed updates. In Algorithmic Learning Theory, pages 11 111-132. PMLR.
Aytekin, A.. Feyzmahdavian, H. R., and Johansson, M. (2016). Analysis and implementation of an asynchronous optimization algorithm for the parameter server. arXiv preprint arXiv: 1610.05007.
Carmon, Y., Duchi, C., Hinder, O., and Sidford, A. (2020). Lower bounds for finding stationary points i. Mathematical Programming, 184(1):11-120.
Chen, Pan, X., Monga, R., Bengio, S., and Jozefowicz, R. (2016). Revisiting distributed syn- chronous sgd. arXiv preprint arXiv:1604.0098/
Cohen, A., Daniely, A., Drori, Y.. Koren, T., and Schain, M. (2021). Asynchronous stochastic optimization robust to arbitrary delays. Advances in Neural Information Processing Systems, 34:9024-9035.
Cotter, A., Shamir, O., Srebro, N., and Sridharan, K. (2011). Better mini-batch algorithms via accelerated gradient methods. Advances Neural Information Processing Systems, 24.
Dutta, S., Joshi, G., Ghosh, S., Dube, P., and Nagpurkar, P. (2018). Slow and stale gradients can win the race: Error-runtime trade-offs in distributed SGD. International Conference on Artificial Intelligence and Statistics, pages 803-812. PMLR.
10

---

Feyzmahdavian, H. R., Aytekin, A., and Johansson, M. (2016). An asynchronous mini-batch algorithm for regularized stochastic optimization. IEEE Transactions on Automatic Control, 61(12):370033554
Ghadimi, S. and Lan, G. (2013). Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4))2341-25 --368.
Gower, R. M.. Loizou, N., Qian, X., Sailanbayev, A., Shulgin, E., and Richtárik, P. (2019), SGD: General analysis and improved rates. In International Conference on Machine Learning, pages 5200-5209. PMLR.
Goyal, P., Dollár, P., Girshick, R., Noordhuis, P., Wesolowski, L., Kyrola, A., Tulloch, A., Jia, Y., and He, K. (2017). Accurate, large minibatch SGD: Training imagenet in hour. arXiv preprint arXiv:1706.02677 02677.
Khaled, A. and Richtárik, (2020). Better theory for SGD in the nonconvex world. arXiv preprint arXiv:2002.03329,
Kingma, D. P. and Ba, J. (2014). Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6988)
Koloskova, A., Stich, S. U., and Jaggi, M. (2022). Sharper convergence guarantees for asynchronous SGD for distributed and federated learning. arXiv preprint arXiv:2206.08300
Konečný, J., McMahan, H. B., F. F.X., Richtárik, P., Suresh, A. T., and Bacon, D. (2016). Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv: 1610.0592.
Krizhevsky, A., Sutskever, I., and Hinton, G. (2017). Imagenet classification with deep convolu- tional neural networks. Communications of the ACM, 60(6):84-90.
Lan, G. (2020). First-order and stochastic optimization methods for machine learning. Springer.
LeCun, Y., Cortes, C., and Burges, C. (2010). Mnist handwritten digit database. ATT Labs [Online]. Available: http://yamm. http://wwm..cc....o///////////// 2.
Mishchenko, K., Bach, F., Even, M., and Woodworth, B. (2022). Asynchronous SGD beats minibatch SGD under arbitrary delays. arXiv preprint arXiv:2206.0766
Mishchenko, K., lutzeler, F., Malick, J., and Amini, M.-R. (2018). A delay-tolerant proximal-gradient algorithm for distributed learning. In International Conference on Machine Learning, pages 3587-3595. PMLR.
Nemirovskij, A. S. and Yudin, D. B. (1983). Problem complexity and method efficiency in optimiza- tion.
Nesterov, Y. (2018). Lectures on convex optimization, volume 137. Springer.
Nguyen, J., Malik, K., Zhan, H., Yousefpour, A., Rabbat, M., Malek, M., and Huba, D. (2022). Federated learning with buffered asynchronous aggregation. In International Conference on Artificial Intelligence and Statistics, pages 3581-3607. PMLR.
Nguyen, L., Nguyen, P. H., Dijk, M., Richtárik, P., Scheinberg, K., and Takáe, M. (2018). SGD and hogwild! convergence without the bounded gradients assumption. In International Conference on Machine Learning, pages 3750-3758. PMLR.
Recht, B., Re, C., Wright, S., and Niu, F. (2011). Hogwild!: A lock-free approach to parallelizing stochastic gradient descent. Advances in Neural Information Processing Systems, 24.
Sergeev, A. and Balso, M. D. (2018). Horovod: Fast and easy distributed deep learning in TensorFlow. arXiv preprint arXiv: 180299579.
Woodworth, B., Patel, K. K., Stich, S., Dai, Z., Bullins, B., Mcmahan, B., Shamir, O., and Srebro, N. (2020). Is local SGD better than minibatch SGD? International Conference on Machine Learning, pages 10334-1033.. PMLR.

---

Woodworth, B. E., Wang, J., Smith, A., McMahan, B., and Srebro, N. (2018). Graph oracle models, lower bounds, and gaps for parallel stochastic optimization. Advances in Neural Information Processing Systems, 31.
Wu, X., Magmusson, S., Feyzmahdavian, H. R., and Johansson, M. (2022). Delay-adaptive step-sizes for asynchronous learning. arXiv preprint arXiv:2202.085550
12

---

Contents
1
Introduction
1.1 Classical theory
1.2 Parallel optimization methods
2
Problem and Contribution
3
Classical Oracle Protocol
Time Oracle Protocol
5
Time Multiple Oracles Protocol
Lower Bound for Parallel Optimization Methods
6.1
Related work
7
Minimax Optimal Method
7.1
Assumptions.
7.2
Analysis of Rennala SGD
7.3
Discussion
8
Synchronized Start of Workers
10
9 Future Work
10
A Heterogeneous Regime
16
A.1 Lower bound
16
A.2 Related work and discussion
17
A.3 Minimax optimal method
17
A.4 Discussion
18
Convex Case
18
B.1 Lower Bound
18
B.1.1 Discussion
19
B.2
Minimax optimal method
20
B.2.1 Assumptions
20
B.2.2 Analysis of Rennala SGD and Accelerated Rennala SGD in convex case
20
Table of Notations
D Proofs for Homogeneous Regime
21
D.I The "worst case" function
D.2 Proof of Theorem 6.4
21
D.3 Auxillary lemmas
23
13

---

D.3.1
Proof of Lemma D.2
23
D.3.2
Proof of Lemma D.6
27
D.3.3
Lemma D.7
30
D.4 Proof of Theorems 7.4 and 7.5
32
D.4.1
Proof of Theorems 7.4
32
D.4.2 The classical SGD theorem
32
D.4.3 Proof of Theorems 7.5
34
E Proofs for Heterogeneous Regime
35
E.1 Proof of Theorem A.2
35
E.2 Proof of Lemma E.1
38
E.3 Proof of Theorem A.3
40
E.4 Proof of Theorem A.4
Interrupt Oracle Calculations
42
Time Complexity with Synchronized Start
43
G.1 Minimax optimal method
43
G.2 Proof of Theorem G.2
44
G.2.1 Proof of Lemma G.5
46
G.2.2 Lemma G.9
49
G.2.3 Proof of Lemma G.8
49
G.3 Proof of Theorem G.3
52
G.4 Proof of Theorem G.4
52
H Proofs for Convex Case
53
H.1 The "worst case" function in convex case
53
H.2 Proof of Theorem B.4
53
H.3 Proof of Theorem B.8
55
H.3.1
The classical SGD theorem in convex optimization
................................
55
H.4 Proof of Theorem B.9
56
H.5 Proof of Theorem B.10
57
H.6 Proof of Theorem B.1l
57
I Construction of Algorithm for Rennala SGD
58
Experiments
59
J.1 +Setup
59
J.2 Results
59
Experiment with Small-Scale Machine Learning Task
59
Time Complexity of Asynchronous SGD
61
14

---

M Analysis of Tixeu-Computation Model Using Graph Oracle Models
62
M.1 Example when the lower bound from (Woodworth al., 2018) is not tight
62
15

---

Table 2: Heterogeneous Case. The required time to get e-stationary point in the nonconvex setting, where 1hh worker requires 7j seconds to calculate a stochastic gradient. We assume that 0 < ... S. Tn.
Heterogeneous Case
Method
Time Complexity
Minibatch SGD
Tn
LA
L²LA ns²
Malenia SGD (Theorem A.4)
Tn
LA
+
Ti
LALA
ne*
Lower Bound (Theorem A.2)
Tn +
LA
2
Ti
ne
A Heterogeneous Regime
Up this point, discussed the regime when all workers calculate i.i.d. stochastic gradients. In distributed optimization and federated learning (Konečný et al., 2016), it can be possible that the workers hold different datasets. Let us consider the following optimization problem:
min {(()) = Σ BEWDD (f(==)))
(13)
where Si IRd x Sg. Rd and random variables with some distributions D; Sc. Problem (13) generalizes problem (1). Here we have the same goals as the previous sections. We want to obtain the minimax complexities for the case when the workers contain different datasets.
A.1 Lower bound
For the heterogeneous case, we modify Definition 6.3:
Definition A.1 (Oracle Class Og" Jeteroy).
Let consider an oracle class such that, for any f == - FA.L, returns oracles O, -
f and distributions D, for all E [m], where & is an unbiased --aiiacce-boundee
mapping for all i [n]] (see Assumption 7.3). The oracles 0 are defined in (7). We define such oracle class as Og" heteroy Without loss of generality, we assume that 0 < < S ... Tn-
TI....Ta
Theorem A.2. Let us consider the oracle class O " Jeteroy for some 0² > 0 and 0 < TI...TT < Tn- We fix any L, > 0 and O < < LLA In the view Protocol 3, for any algo- rithm A E Ag, there exists a function f = 5m E E FA.L and oracles and distributions heterog
((O,,...,O0. (Di,...,Dyy,
Sn) (,,,..,, E O²² n....n.
such that E [infRES. |[{{{>>)]] > E,
where S, = {k E Nolth < {t}. and
and
LA g
T
t=cx
T:
(14)
n
i=1
The quantity d' and are universal constants.
Theorem A.2 states that
LA
1
a²
LA
Miime (Az. FALL) =Ω
Tn
+
n
One can see that the lower bound for the heterogeneous case larger than (9). In Section A.3, we provide method that attains the lower bound.
16

---

A.2 Related work and discussion
The optimization problem (13) is well-investigated by many papers, including (Aytekin et al., 2016; Mishchenko al., 2018; Nguyen al., 2022; Wu et al., 2022; Koloskova al., 2022; Mishchenko et al., 2022). There were attempts to analyze Asynchronous SGD the heterogeneous regime. For instance, Mishchenko et al. (2022) proved the convergence only. In general, it is quite challenging to get good rates for Asynchronous SGD without additional assumptions about the similarity of the functions f: (Koloskova al., 2022; Mishchenko al., 2022).
neighborhood of a solution
In the non-stochastic case, when x² = O, Wu et al. (2022) analyzed the PIAG method in the non- stochastic heterogeneous regime and showed convergence. Although the performance of PIAG can be good in practice, in the worst case PIAG requires O (T.AA/s) seconds to converge, where Tn is the time delay of the slowest worker, L := ~V L, and L, is Lipschitz constant V f.. Note that the synchronous Minibatch SGD (see Section 1.2) method has the complexity O (T,.A/e), which is always better.*
Our lower bound in Theorem A.2 does not leave hope of breaking the dependence on the worst straggler the heterogeneous case. the stochastic case, the lower bound slightly more optimistic in the regimes when the statistical term (the second term in (14)) is large. If the stragglers do not have too large delays, then their contributions to the arithmetic mean can small. Note that in Theorem 6.4 in the homogeneous case, we have the harmonic mean of the delays instead.
A.3 Minimax optimal method
In this section, we provide Malenia' SGD (see Method 6) that is slightly different from Rennala SGD (Method 4). There two main differences: the first is that Method has different gradients estimators of¹ for each worker, and the second one is the constraint ( Σi= 1/B.) < <5/n in the inner loop'. The more gradients we get from the workers, the larger the term (2 E.= 1/B.)
Method 6 Malenia SGD
1: Input: starting point æ0, stepsize y, parameter S
2: Run Method in all workers
3: for k 0....... K-
do
4: Init g = and B =
5: while ( E B,
< < do
6: Wait for the next worker Receive gradient, iteration index, worker's index (g, ii)
7:
8:
if W' = k then
9:
g.t o + B: +1
10:
end if
12:
Send (z* k) to the worker
end while
14: 9
Di=1 B, 5
x k+1 x "9
16: end for
As in Section 7.2, we can provide the convergence theorems.
Theorem A.3. Assume that Assumptions and hold for the function f. Assumption 7.3 holds for the function fs for all [n). Let us take the parameter S = max [0// n and
In nonconvex case, T. can arbitrarily larger than
aniir88 of +Miquella:: Malasia, Miquella and Malenia, Giddless Maguella, most powerful Empyreans, gained renown fox her legendary against Stursoourge Kadihn during the Shanering, in which she unfeashed the power of the Scarles Roi rediaed Caclid mins.
// dearing wiki, festral
Demigad Boss Ring. She's
We assume that D 1/2,)
if exists [n] such that B: 0.
17

---

Method 7 Worker's Infinite Loop
1:
Init 0, k' = -1, and worker's index i
2:
while True
3: Send (g, k', .i) to the server
4: Receive (x k) from the server
5: k k
6: g ;5( E~D
7:
end while
min I 2L
c8
(1/L) ) in Method 6, then after K 2 24AL/e iterations the method guarantees |f((>>11
=
that R
Ek=
E
E.
Theorem A.4. Let us consider Theorem A.3. We assume that ith worker returns stochastic gradient
every TÜ seconds for all E [n]. Without loss of generality, we assume that 0 T1 S S Ty. Then after
LA C
0² LA
96
+
(15)
i=1
seconds, Method guarantees to find an E-stationary point.
Comparing Theorem A.2 and Theorem A.4, one can see that the complexity (15) is optimal. Note that Theorem A.3 holds without assumptions that the delays Ti are fixed.
A.4 Discussion
Unlike Asynchronous SGD and PIAG, Malenia SGD ignores all stochastic gradients that were calculated in the previous iterations, which appears to be counterproductive. Nevertheless, show that Malenia SGD converges, and the time complexity is optimal with respect to all parameters. Note that Malenia SGD does not require the Lipschitz smoothness of the local functions fs does not depend on the time delays T;, does not need any similarity assumptions about the functions fi, and can be applied problems where the function is not Lipschitz (does not have bounded gradients). The analysis of the method elementary and does not go far away from the theory of the classical SGD method. When the ratio fe is large, Malenia SGD is better than Minibatch SGD (see (2)) by times.
@ (Tn/ (A EE_TT
B Convex Case
B.1 Lower Bound
Let us consider the optimization problem (1) in the case when the function f is convex. For the convex case, using Protocol 2, we propose to use another complexity measure instead of (6):
meime (A,
sup inf 0 AEA feF (O,D)EO())
inf sup
E inf kES.
[(x
=EQ f(x) S (())=E}
inf
(16)
S. No. < (),
where the sequences t and x are generated by Protocol 2. Let us consider the following class of convex functions:
R.M.L)- Let us define (0, R) == (x E Rd ||]||| < R). We assume that function f RR + R is convex,
Definition B.1 (Function Class Feomy
differentiable, L-smooth on the set (0, R), i.e.,
[Vv((r) - fv & L | yil Yz, E B2(0, R), and M-LLpschitz on the set (2, R), i.e.
[f()) f(y) M || vll
Vo, E B2(0, R).
A set of all functions with such properties define Fromy
FRMMLL
18

---

Table 3: Convex Homogeneous Case. The required time to get E-solution in the convex setting, where 1hh worker requires 7j seconds to calculate a stochastic gradient. We assume that < 71 S
Tn-
Method
Time Complexity
Minihatch SGD
Tw
min
VCR v2
M n²
+
o pg ne?
Asynchronous SGD
E
LR²
e2 me?
(Mishcheako al., 2022)
(Accelenaed)) SGD (Theorems B.9 and B.)
min mc(n)
( Lin 1m To
mia
Sin vc
x2
med
Lower Bound (Theorem B.4)
min mc
1 2 [-1 T2
min
TTi vc
22 n2
mee
Lower Bound (Section M)
(Woodworth et al., 2018)
min
JLB Ve
1 Ei
me?
For the convex case, we analyze the following class of algorithms: Definition B.2 (Algorithm Class A
Let us consider Protocol 3. We say that algorithm A from Definition 4.1 belongs to class A iff A E Aa and x E (0, R) for all k 2 O.
We also define an oracle class:
Definition B.3 (Oracle Class O
Let us consider an oracle class such that, for any E Fromy R.M,L: it returns oracles O, = / and
distributions D; for all E [n], where f f is an unbiased - mapping on the set B2 R). The oracles 0 defined in (7). We define such oracle class Oconv Without loss of generality, we assume that < T1 S ... Tu-
For this setup, we provide the lower bound for the class of convex functions in the next theorem.
Theorem B.4. Let consider the oracle class O for some o² > 0 and 0 < S... Ta We fix any R, L. M, > 0 such that v VLR > Ci VE > O and 2 > C2E2. In the view Protocol for any algorithm A AR there exists function E Feony R,M.L and oracles and distributions
On), Dn)) Oconv (f) such that
[(at)]==
inf kEs.
inf f(x) e, =))
where : (k Nolth < {t] and
-1
VLR 2²
o² R22
1=ex min mEin)
min
m
The quantities C12 C2 and e are universal constants.
B.1.1 Discussion
We improve the lower bound obtained by (Woodworth et al., 2018) (see Table 3). Woodworth et al. (2018) try to reduce any optimization problem to an oracle graph. Then, they get lower bound using the depth and the number of nodes in graph. Our approach is different, we directly estimate the required time and avoid the reduction an oracle graph. One can think that our "oracle graph" is always linear in Protocol 3, but every node in an "oracle graph" is associated with a timestamp and an index. Unlike the oracle (Woodworth et al., 2018), which always returns stochastic gradient, our oracle (7) returns stochastic gradient only if the conditions are satisfied. Also, Woodworth et al. (2018) construct different "worst case" functions and oracles for the "optimization" and "statistical" terms. While our construction consists only of one function and one oracle.
19

---

B.2
Minimax optimal method
B.2.1
Assumptions
Additionally some assumptions from Section 7.1, use the following assumptions in the convex case.
Assumption B.5. The function f is convex and attains the minimum at some point x" E IRd.
Assumption B.6. The function f M-L.ipschizz, i.e.,
(f(x) - f()) s M | - ull Va, y Rd..
Assumption B.7. For all R stochastic gradients V fx;; are unbiased and have -arrinnce
bounded, i.e., BE-D [+(=))) E af(x) and RE [(;)))
[+)
S o² where
0² 220 0.
B.2.2 Analysis of Rennala SGD and Accelerated Rennala SGD in convex
Theorem B.8. Assume that Assumptions B.5, B.6 and B.7 hold. Let take the batch size E and 7 M²40218 = ((/MM²) in Method 4, then after K 2 2M2 R²/22
= max
iterations the method guarantees that E [f(**)] - f(x*) I where 2k = K Ekoo x² and
R
=l.
Theorem B.9. Let us consider Theorem B.8. We assume that tt worker returns a stochastic gradient every T; seconds for all E [n]. Without loss generality, assume that 0 < T1 S S Ta. Then after
(1-1) m
m
-1
M
o² R2
8 min me|n
+
(17)
E2
mE?
seconds Method 4 guarantees to find an E-solution.
Let us provide the theorems in the smooth convex case. We consider the accelerated version of Rennala SGD. In particular, we assume that instead of Line 13 in Method 4, we have
7++1 = 7(k + 1), a6+1 2/(k + 2)
y A+1 (1 =(1-a4+)dtt + aRt1u",
(u² = =x)
(18)
w k+1 = r²² -7+-196s
b+1 - -0+1) 0x411kt1
We refer such method Accelerated Method 4 Accelerated Rennala SGD. The acceleration technique is based on (Lan, 2020).
Theorem B.10. Assume that Assumptions B.5, 7.1 and 7.3 hold. Let us take the batch size max {[(02 R)/((>/2V))) 11. and 7 min 41.
3RSS 1/2) in Accelerated (1)(K22
1
Method 4, then after K 2 8yLR iterations the method guarantees that E [f(**]] f(x*) S E, Ve
where 2 100 x0
Theorem B.11. Let us consider Theorem B.10. We assume that th worker returns stochastic
gradient every T seconds for all [n]. Without loss of generality, we assume that 0 < S ... Tn. Then after
VLR Ve
R²R2 me²
32 min mEin
m
Te
seconds Accelerated Method 4 guarantees to find an e-solution.
20

---

C Table of Notations
Notation
Mcaning
= O(f)
Exist C > such that g(z) S C x f()) for all E
[(f
Exist C"
such that g(z) C' x f(2) for all E Z
O() a1, b}
g O()) and g = Q()
Set (i 2 < b}
(1....,m
D Proofs for Homogeneous Regime
D.1 The "worst case" function
In this section, we recall the "worst case" function that we use to prove our lower bounds. This is the standard function that used in nonconvex optimization. Let define
(ro = 1). prog(z) == max 0 + 0}
In proofs, the construction from (Carmon al., 2020; Arjevani al., 2022). For any
T E N, the authors define
Fr(x) - (1))((())) +
(- - ((Z=-1)(())))
(19)
1=2
where
0,
S 1/2,
x 2 1/2, and Φ(x) = ve vel te dt.
V (x)
exp
12x-11
The main property of the function (r) is that its gradients are large unless prog(z) 2 T.
Lemma D.1 (Carmon et al. (2020); Arjevani et al. (2022)). The function Fr satisfies:
1. Fr(0) - inzzer" FT(x)= = T where A 12.
2. The function Fr is 4-smooth, where 4 = 152.
3. For all a E RT, V I Too: where Yoo = 23.
4. For all RT. prog V (x)) & prog (z) + 1.
5. For all R.T. if prog(2) xx) T, then | FVFF(())) >
We these properties in the proofs.
D.2 Proof of Theorem 6.4
Theorem 6.4. Let us consider the oracle class Or' for some o² > 0 and 0 < .... S T
We fix any L, A > 0 and 0 < E S CLA.. In view Protocol 3, for any algorithm A E Ag. there exists function f E FA.L and oracles and distributions ((O,, O,), (D,....,
O Oi..... (J)
such that E infnes, [[((x*)]] E, where S, {K No t < t) and
LA
LLA
t= min mE
m
The quantities c' and universal constants.
21

---

Before we prove the theorem, let us briefly explain the idea. In Steps and 2 of the proof, we construct the appropriate scaled function and stochastic oracles using the function (19). These steps are almost the same as in (Carmon et al., 2020; Arjevani et al., 2022).
In Step 3, we use the zero-chain property of the function (19) and the zero-respecting property of algorithms that would guarantee us that unless oracles send us non-zero coordinate, an algorithm would not be able to progress
new coordinate. The oracles send non-zero coordinate with some probability We have n parallel oracles that flip random coins in parallel. With large probability, we show that will not get new coordinate earlier than
m
(+++m)
min mEIn
seconds, where тı the delays of the oracles. So, with large probability, we will not be able to solve the optimization earlier than
)
Σ
1 + m m)
x min mE
Ti
p
where T is the dimension of the problem.
Proof. (Step 1: f FA.L)
Let us fix À > O and take a function f(x) := / Fr (5),
where the function Fr is defined in
Section D.1. Note that the function f is L-smooth:
[v)
Vf(wil LA/4
Fr x
Fr
1/
- LA
T
vll
Vx, y E Ied.
X
Let us take
A
T=
LA
then
LX2
LAPA-
f(0)
inf f()
(FT (0)
inf PT(x))
s A..
ZERT 11
ZER?
We showed that the function ʃ E Fa.L. (Step 2: Oracle Class)
In the oracles O,, we have the freedom to choose a mapping f((:)) (see (7)). Let us take
{ 11= Vz E R²,
f(: v=f((z) 1 1 prog(z))
and D. Bernouilli(p) for all i [n], where p E (0. 1]. We denote [zl, as the jth index of a vector RTT is left to show this mapping unbiased and o² variance-bounded Indeed,
v.f(2) (1 (1+1 prog(z)]
E [ -1 1) = v.f(z)
E [1
p
for all E [T], and
E [((=;)) -/(0)|))))(()))))))
( p
-1) 27
max jELTI
2 E
because the difference is non-zero only in one coordinate. Thus
E =[158000)-
[ (1 (1-p)
L2
Fr (4) |2 (1 - -p)
l7p
P
L2X2n2 (1 p)
0
Hp
22

---

where we take
1
p= min
0219
(Step 3: Analysis of Protocol)
We choose
X V2el
to ensure that [f))] Lemma D.1. Thus
L2X² &
VFr (1)
2=1 [prog(x) < 7] for all RT, where
AL
T
21l1 A
and
22 o²
min
Protocol 3 generates sequence {-* 120
1==
We have
inf keS,
> 25 inf
1 [prog(x*) < <T].
(20)
kES:
Using Lemma D.2 with = 1/2 and (20), we obtain
E
inf
2&P
inf 1 [prog(æ*) keS.
< 21 7
keS.
for
1
0²
(AL Au -2) -2)
AL
t
min mEin]
+
24
i=1 Tr
207
D.3 Auxillary lemmas
D.3.1 Proof of Lemma D.2
Lemma D.2. Let us fix T N such that T < T', consider Protocol with a differentiable such that (z))(V[(x)) S prog(x)) for all x domain( ['), delays T1 S S Tax distributions D. Bemouilli(p) and oracles O O for all [n],
function f RTT
mappings
[)(x)) vf(()) (1 (1+15> prog(=)) ( 11))
Vx YORR", ,V (0,1),
(21)
and an algorithm A E Ag. With probability not less than
inf 1 [prog(>**) keS,
< T] 2
for
)
1 min
)
(T + log
t 5
24
me(n!
Tr
where the iterates a defined in Protocol 3.
23

---

< 1 holds, then we have the inequality Σx=1 Ey I t, where Ey are random variables with some known "good" distributions. Ifinl 1 [prog(a*) < <T] < 1 then it means that exists k such that prog(x")= =T Note that the algorithu is zero-vespecting. so can not progress to Thh coordinate unless the oracles generate stochastic gradients with non-zero 1st 2nd, .. T coordinates. The oracles flip coins in parallel, so the algorithm should wait for the moment when the oracles flip success. Al the same time, it takes time generate coin (calculate a stochastic gradient), and the oracles can not flip more than k coins before some time b2- So if the Th is index of the first success to generate non-zero tth coordinate, then the algorithm should wait at least Eyp. seconds. Next, we give a formal proof.
Proof. (Part 1): Comment: in this part, we formally show that if ffiffes, [prog(x*) < T
Let us fix 2 and define the smallest index k(i) of the sequence when the progress prog(x*(() equals ;
(i)) == inf { E No i prog(=")} E No U foo).
If infRes, 1 [prog(>**) ) < T] < holds, then exists & E St such that prog(x*)) T, thus, by the definition of k(T), (4()) < 1 < and k(T) < oc. Note that (k(2) is the smallest time when we make progress to the T coordinate.
Since 00 and A is a zero-respecting algorithm, the algorithm can return a vector sx with the non-zero first coordinate only if some of returned by the oracles stochastic gradients have the first coordinate not equal to zero. The oracles O are constructed in such a way (see (21) and (7)) that they out coordinate based i.i.d. Bernoulli trials.
Definition D.3 (Sequence k.). Let consider set
s { E N k-1 ( = and th
k-1 Sihtt
+ Tu
k-1 k-1 5/6 k- s (s Six 5,k
We order this set and define the result sequence as (M.5 1ز: (15)m= sequence. The sequence kf is a subsequence of iterations where the oracles use the generated Bernouili random variables in the third output of (7). The sequence k-1 is defined in Protocol 3.
where E [0, oo] is the size of the
Let ksuccess be the first iteration index when the oracles draw 1, i.c.
ksnccess in g* and k (15)72)) NU
Since the algorithm A is zero-respecting and the function f is zero-chain function, i.e., prog f(g)))(()) & prog(x) + for all x E domain(f), then prog(g*) = prog(x*) = 0 for all k < Kanceess If infses, 1 [prog(a*) < T] < 1 holds, then kisaccess < (c, and kussss < k(1)
The oracles use the generated Bernoulli random variables { (k5) Let us denote the index of the first successful trial as 1/. i.e.,
? = inf E and i [1, E (oo)..
The 7th worker can generate the first Bernoulli random variable not carlier than after seconds, the second Bernoulli random variable not earlier than after 2r, seconds, and so forth.
Definition D.4 (Sequence Eg). Let consider a multi-set of times
{jr j 2 1, i [m]} = {f,,2m 2 } U... w {Tn, 2T.:
We order this multi-set and define the result sequence as {2g 12 and fro = lime Eo ac.
Then 71 Bernoulli random variable can not be generated earlier than Ey, because E,, is the earliest time when the oracles can generate 7/, random variables. Therefore, if infress, 1 |prog(**) < T <
holds, then F. fiucces < (1(1)
Using the same reasoning, +++++) 2 ( + Engzr where 7), is the index of the first successful trial of Bernouilli random variables when prog(.) in the sequence zt More formally:
24

---

Definition D.5 (Sequence 1, Let us consider set
{k N k-1 t = and th 2
k-1 + and prog(s = =}..
We order this and define the result sequence 1 where mj+1 E [0, oo] is the size of the sequence. The sequence k5,, is subsequence of iterations where the oracles use the generated Bernouilli random variables in (7) when prog(s j.
Then
7/ 7+ inf and i [1, [1,m)+1]} E (NO) Vj (0,..,, 1}.
(22)
By the definition of k(j). =k( is the first vector of the sequence, that contains non-zero jth coordinate. Thus the oracles will start returning stochastic gradients that potentially have non-zero j + 1th coordinate starting only from the iteration k:j). Therefore,
R (h(T-1) + Egp 2 Σ mn
Combining the observations, if infnee, Thus
[prog(>") < T) holds, then ET= Eyg S (t((T) St.
PP
inf AES:
1 [prrog
<T] <
S
Σ Eyps St
V2 0.
In Section D.3.2, we prove the following inequality that we use in Part 2 of the proof.
Lemma D.6. Let us take lj+1 E N. Then
P (1)+1 12+1/11-1111 .m) S (1 -))
for all j E (O...., 13. T1...
(Part 2): Comment: in this part, we use the standard technique to bound the large deviations of the - sum Ei= D
Let us fix t' 2 O. Recall Definition D.4 of (fe) If the number of workers then f. kr1 for all & 2 For 1, the sequence (tx 1oe has more complicated structure and depends on the delays .I.....Tx.
For any A 2 if < t', then k < E x-m 1 Indeed, let us assume that k > E L The sequence &x constructed by the ordering the multi-set (jr lj 2 1, [n]]. The number of elements, which are less or equal to l', equals Σm [ Thus, we get a contradiction.
means that
P (Enges I _t......... m) SP Mit1 S
m
Using Lemma D.6, we have
Em
Penyer S St 5
Σ
(1 (1-p) p)
0 < &' Ti, then En [1/ra] = 0, and
P (Pajer S t'|ns....,,,
25

---

Otherwise, if > T1, then Ei=1 [1/=1] 2 1, and
P Pf S St [fjj......))) m) s 1 1 (1- (1-p) -)= +or S Σ
n
where we use the fact that 1 - 11 -1-p) S pm for all p [0, 1] and m E N. For all t' 2 0, we have
IP (Crsts S s/........ m1 S
Let us define
p' : p a
then
(F S mm m) S pl.
(23)
Let us fix s 2 0 and 8 0. Using the Chernoff method, we have
T
P
8
mm
2 st
P
exp
8
2 exp (-st)
T
I
B
exp
88
Exp
i=1
Let us bound the expected value separately:
T
T
E
exp
n
E
E
st,
T
71
i=1
Since Eyg 2 0, we have
E Ses
spa
17-
711
E e
by
S 1 Mi 11111..... m1
P f(tn, S f11m:-11111 1...........
+ E stn,
Er t,, 1b-1..... m7
(1 P (Fr S t' t1)
$ IP (Ty, S "m
m) +e st' (1 - P (En, s 2 2t1m=-1...,,11)
(23)
2 p' + E st' (1 (1-1').
Thus
s > tm )
p'' (1 (1- T
E
exp
and
P Tm
S a
(p'+e-st sst (1 (1-D'))== = sis''' (1 -1)
Let us take 8= = 3/e' and get
T
< 2// (1+ (e - 11)1/² $ TT+-TT
IP
(24)
Let us recall the definition of ofp' p'
p' = p
Σ
26

---

Now, we have to take the right t'. We will take it using a nonconstructive definition. Assume that 1'
ap E
where
inf
[n]]
Tm+11
(Tn+1 = oo).
4p
This set not empty because n belongs to it. Using the definition of j", we have
='=p
S pt
i=1
Substituting this inequality to (24), we obtain
T
P
Σ
En
S
S
2110-33
1=1
For & t' ( + log 6), we have
P
Si
S 8.
Recall that 6' 1 4p
(Er= T
Using Lemma D.7, we have
-1
1 min
Σ
m
+ m
24
mE(m)
Finally, we obtain
P inf 1 [prog(x**)
< <J]
< <1
S P
E S
58
(25)
kES:
i=1
for
S 24 mE(a)
1 min
Σ
m
-1
{_ + m )
(
( +
log
D.3.2 Proof of Lemma D.6
In the following lemma, we use notations from Part of the proof of Lemma D.2.
Lemma D.6. Let us take 1J+1 E N. Then
P ( = 1,41119......................... .)) s (1 11111-1p
for all jE "T....,T-1.. 1}.
In this lemma, we want to bound the probability for the random variable 75++1 from (22). 7i+1 the index of the first successful trial of the sequence of Bernouilli random variables. At first sight, this is a trivial task since 7/+1 has distribution similar to the geometric distribution. But the main problem here is that the sequence k5,, and the quantity mj+1 are also random variables. Therefore, must be careful with this.
27

---

Proof. Since the image of the random variables Tg.....77) is in Nn (oo}. Let us take ........y NU (oo), and prove the theorem for a probability conditioned on an event Oi {m 433 such that P (N (n: 4.) > 0. Therefore, it is enough to prove that
IP 11+t = 13+1 h (m: -1,) 5 -1-1pp (11-))b-1--
First, assume that exists E [j] such that 1 It means that, for all &s 0, prog(*") < j, thus
2 [m = 4: (3) =
ntm
P M 1-+1=144 = 4,+1
i=1
for all 1++1 E N. Let us explain this step. if exists E [j] such that 4 - oo, then an algorithm never
get a progress to 1 coordinate, thus 7/+11 = inf ( and i E [1, my-1)) = oo a.s. because Mj+1 = 0 and k5. is an empty sequence.
Assume that 1, < co for all i E [i]. By the definition of 7j+1, we have mj+1 2 lit and g+
- 0 and { 11,4
Thus
11+1-1
G Nmm 1mm=-i)) 113
Mitt = 1++1 ntm (m li}
-1+1
S
n g
0},5 5
1, 2 ls+1
Since h.f.
k5, a.s. for all <iE [m]+t], using the law of total probability, we have
7/+1 = =,++1 P
[n: [7: = 47
i=1
11+1-1
P
(5 = =0},5 03,5 5.5m = 11, 2 11t1,
n
(k5, = kz
n
fm 11)
ki t
1=1
i=1
lj+1
P
(
0).5 1,1
1z+1,
n
(1.f. kz}
n (m 11)
i=1
where En
Ekpeh.eheu Next, if the event
is a sum over set k,,,), E No+1 I4 < p E [1yta]: hi < kkp.
f
n
( kk] {mmt1 2 2411
holds, then an event n 1++1 As, holds, where
A& = {8 (8/4-g) and v 2 b + Tm and prog(s/;-))) = j}.
At the same time, if n As, holds, then {m,+1 l++1 holds. Therefore,
15+1
19+1
(KS, ked (mpr1 2 [4+11 = 0 (1S5, kit) 1 Aks)
==1
and
11+1 = 1++1 0 (m 111
28

---

20
19-11
4-1 n
(15 ki) kid ARs ) 1:3
P
(5 03,5
(1
Let us define o(E),...
-1)= ( as a sigma-algebra generated by e ,..... 5 Note that, for all E 11++1 - 1], the event { = 0} E a(S ...... 5 9). Also, for all i E [4+1], the event [kf, = kit Ak, E ".....,,,,,,, Finally, since k < N5 "ilsys the event
Akig42 A 31542 kiz+1 00 (m =4] S Co(s), .
for all E [j]. Therefore, the event (5 1} is independent of the event
4-1-1 (c = 0} 4541
N (15,, = k; n Ak. n (n = 4.) E "...,,,.......1.
because 5h are i.i.d random variables. Using the independence and the equality P (5 =1) p.
we have
IP
Mj+1
1++1
0 fm = 43
1111-1 {E
3 n to 4.
0}, n (1ff. ki) n AAx)
<p p
S Cuc (
Since the events (K :..44 probability, f = 1, we get
h n Akyja do not intersect, we can use the additivity of the
-1) -
P Mj+1 44+1 nm =
=4] 41 s pp
U (il
(1Ke 34511 =1 -
11) s p.
i=1
and prove the lemma for 1J+1 1. Otherwise, if lj+1 > 1, obtain
7j+1 = 15+1
n
(n: 47
i=1
1141-1
4441-1
S p
P
{ = 0}.
n im1
(1K5 = kis n Art)
ki E Cancci
iml
U
= n Az)
0 (T1 111
( +
5m1
For any events A and B, we have IP (A. B) < P (A), thus
P
1jt1
1++1
ntm
{m
= 41
i=1
1--1-1
1s+1-1
6 (m = 41
< p
P
{
0},
n
(15. = ki) ki) Ak.)
511
Let us continue for li+1 > and rewrite the last inequality:
1i+1 = -,+
{mH = -4]
29

---

4+1-2
4+
n (n 113
Sp
P
(5th = 5 0, n (ks, kis n AR.
ch -1
Note that, for all i 11-+1-22 2], the event {5th 03 a(E), ,.... " Also, for all E 11+1-111
the event {1.t. = ki} n AR, E E 5h1 5 9). Finally, since k < k5 11 the event
Ak
NeKS, Jil 1-1 = ki n (m - Co(e'...... ...., (4)-))
for all i E [i]. Therefore, the event 14-1+ = 0} is independent of the event
4+1-2
4+1-1
(5th = 0}
(1h, = ki) n ARe n (n = 4}.
==1
Thus, we have
P 1/+1 1i+1 0 {m = -lib)
121-2
441-11
(K5.. = ki n Ane) ) =11] 113
S 1p(1 - p)
P
(st
0}.
n
ki kh 1=1
i=1
Since the events fhee
1,1 -1 = ki, 1 Ak
41 do not intersect, we use the additivity of the
probability. If 3--1 = 2, we get
P
MJ+1
15+1
1 n = 44
S pp(1p)p
U
(K (15 -
(4a)) (n:
Atm 41
$ p(1 -p),
and prove the lemma for 4yt1 2. Otherwise, if ly+1 2, obtain
P
1/+1 = -1411
fm = 4
80 Σ
1112-2
41112
$ <p(1- - p)
P
15th 0}.
0
(155 = ki n An.)
h S Chach 2
i=1
i=1
6 Fm = 4
U
-111
(1 = = Utf A.))
Rize1
2+1
i=1
21122
1111-2 2
2 (m 1m)mm
$ p(1 p) p)
P
th =0}.
(15,, kt n A
41}
Cuc..cki 1 2
where we use P ((A, B) S (A) for any events A and B. Using mathematical induction, we can continue and get that
i
1,+1 0 (nH 1i) s s p)5s1111
Mjt1
D.3.3 Lemma D.7
This is technical lemma that in the proof of Lemma D.2.
30

---

Lemma D.7. Let us consider a sorted sequence 0 <T S ... ST
Tn S Tn+1 oo and constant
S M + q.
We define
t = s
Tt
where
-1
m
o = inf
m E [n]
Σ
<
Tm+11
i=1
and
-1
t/ = min
(5 (5+
i=1 7i
Then
t1 tt 1'g.
Proof. Additionally, let us define
1
J2 arg min jE[n]
Σ
(8 (1+
where jž is the smallest index. For jž = 1, we have
82 = TI 15
For 12 > 1, we have
1 -1 1=1 Tj
1
1
Σ
(S + 12)
(S j 1).
To
1=1
From this inequality, we get
11 1
Σ
(S
(Z)
<
(8+ 1)
7
1=1
and
Σ
(5)
T32
i=1
Thus Ty2 < for all jž 2 1.
Then either jž < ji and
jz
t2 =
(S+ S
v s
Σ
= 4
Ts
T
i=1
or 8 > ji and
12 2 T S
where we used the definition of oī. It concludes that to 2 t1.
31

---

Assume that jî > S + 1. Since the harmonic mean of a sequence less or equal to the maximum, we have
c 1 1)
S
Gi
S Tjc -1 S T3
7
This incquality contradicts the definition of ji means that o S S 1 and
ji
5
t2 -
(28 + 5
Σ
(65) S 6t1.
i=1
D.4 Proof of Theorems 7.4 and 7.5
D.4.1 Proof of Theorems 7.4
Theorem 7.4. Assume that Assumptions 7.1, 7.2 and 7.3 hold. Let take the batch size ESS
max { [02/e] 11, and y min { 2L = θ (1/L) in Method 4. Then after
K 24AL
8
iterations, the method guarantees that 1 K
Ek-In || | Se.
Proof. Note that Method 4 is just the stochastic gradient method with the batch size S. Method 4 can be rewritten as x²+1 x² 3 Σ S vf(=";;) where the & are independent random samples. It means that we can use the classical SGD result (see Theorem D.8). For stepsize
sS
7 = min
L 2L
we have
K
E [[
S
k=
12AL
12ALo
K
E2S
Using the choice of S, we showed that Method converges after
24AL
K 2
8
steps with
1 ES
7 min
T
2L
2T.
D.4.2
The classical SGD theorem
We reprove the classical SGD result (Ghadimi and Lan, 2013; Khaled and Richtárik, 2020).
Theorem D.8. Assume that Assumptions 7.1 and 7.2 hold. We consider the SGD method:
k+1 v ))
where
min
L 2L
32

---

For fixed x E R ((x) is random vector such that E [g(x)] = vx()),
E - f=x)) s
-19(())
(26)
and g(x²) are independent vectors for all k 2 0. Then
K E
Vf(x*)
|||
SE
K
for
4AL
8AL
K
+
E
8²
Proof.
From Assumption 7.1, we have
f(aht)) s f(z²) + (Vf(=*), k+l -x L
||-01- 21
Lg²
= =f(z²) -
g(x²1)) + ||s(
2
We denote G as a sigma-algebra generated by g(x²), ) ,..,, g(x Using unbiasedness and (26),
we obtain
E [[((att)/ot $
-7 -
(1- 4
+
L 2
E
[llet o*
2
(1- 47)
||/f(>>>)\/ + LI20²
S f(1*²) -
2
2
Since 7 S 1/2, we get
LX20²
E [(( S f(a²) - 2 2
|f( +
2
We subtract f and take the full expectation to obtain
TnR02
E ||f(a*t1)- - fr < E [f - 1*] - 3
||] +
2
2
Next, we sum the inequality for ls {0, .0.-...;. K - 1}:
K
KIN20²
E [ -- s 5(x0)
- 1r
Σ
JE [|(
2
km 0
K-1
I [| |||] + KTn202
A
Σ
k=0
Finally, we rearrange the terms and use that E [[(xk))
fr 2 0:
K-1 E
Σ
\|
2A
+ Iya?
K
The choice of and K ensures that
K
Σ
B
Se.
K
K=
33

---

D.4.3 Proof of Theorems 7.5
Theorem 7.5. Consider Theorem 7.4. We assume that ih worker returns a stochastic gradient every Tj seconds for all i [n]. Without loss of generality, we assume that T1 S S Tn. Then after
LA e
LA
min 96
(10)
mE[n]
m
seconds, Method guarantees to find an e-stationary point.
Proof. In this setup, the method converges after X {rime required to collect a batch of the size S}. Without loss of generality, we assume that TI ...S Tn.
Let us define time that enough to collect a batch of the size S as 1', Obviously, one can always take t'= 3r, 1 and guarantees that every worker calculates least [ stochastic gradients, but will provide tighter t'.
We define B; the number of received gradients with an iteration index equals k. For each worker, there are two options: either the 1th worker does not send gradient with an iteration index and B, 0, or sends least once and B, O.
In the worst case, for 1th worker, the time required to calculate B; gradients equals
( (1 B,)
B; > 0
=
because either B, >> O and, in the worst case, worker finishes the calculation of a gradient from the previous iteration (that we ignore) and only then starts the calculation of gradient of the current iteration k, or B, and the server does not receive any gradients from worker.
Note that all workers work in parallel, so our goal is to find feasible points i E R and B1, Bn E No such that
t' 2 max f kE(n)
B1, Bn No
(27)
B 2 S
1=1
First, we relax an assumption that B, E No and assume that B; E IR for all i E [m]
2 maxt,
sE(n]
B1, Bn E R
(28)
B1, B, 2 0
Σ B; S i=1
B, E IR are feasible points of (28), then
maxt t; = max T (1 + B₂) I max Tú (1 + [B,]]
:E[n]
B.>0
B,50
S max T; (2 + B₂)
max Ti (1 + B,) max 4.- 8,>0
B,50
*E(n)
means that if E IR and ...... B, are feasible points of (28), then 21' and [B], ... [B,]] are feasible points of (27).
Let us define
{()) = Σ
(S+
Vie
"Note that worker may send gradient from the previous iterations that ignore in the method.
34

---

and take j" = arg minje[n] r' jr is the smallest index from all minimizers of (' Let us show
that ((") and
1, i j
B,
0,
i> j
are feasible points of (28). First, we have
t'(i") ((G)--1) -1) 52
Σ
B
(S+
Σ
j S.
Next, we show that B, > 0 for all Jr jf 1, then (1) = TI + 1), thus B1 = 0.
1, then, by its definition, we have (j() < t' 1), thus
(i+
Σ Tr
(
To
From this inequality, we get
Σ 1
Σ i=l
(S
(8+5)<
(S+
n
i=1 T4
and
Σ
1 j*)
From the last inequality, we get that Ty. < <t())),, thus B; 2 By. > 0 for all i S j" It left to show that
maxt, t = max Ti (B: + 1) = (j)) sE|n
Finally, we can conclude that Method 4 returns solution after
-1
K 2t
48AL
min JE(n]
Σ
(8+
E
seconds.
E Proofs for Heterogeneous Regime
E.1 Proof of Theorem A.2
Theorem A.2. Let us consider the oracle class Oo² heterog for some o² > 0 and O < Ti S TT....T
& Tu- We fix any L, A > and O < E S LLA In the view Protocol 3, for any algo- rithm A E Az, there exists a function == n > Lim1 E FA,L and oracles and distributions
((O,,..,,O,)) (Di,..., Dn)) heteroo (S1, JI...., fn) such that E [iinfkes. [[V[(x+))] > 8,
where = {kr E Nollk S s and and
LA
n
LL
t=ex
Tn
T
(14)
E
12
ng²
The quantity è' and are universal constants.
The structure of the following proof is similar to the proof of Theorem 6.4. In the heterogeneous regime, the main difference is that we have more freedom to choose the functions ft.
35

---

Proof. In (14), we have the sum of two terms. We split the proof in two parts for each of the terms.
(Part
(Step 1: ʃ E Fa.t)
Let us fix 0. We consider the following functions ft
0,
i < n,
fx(x)
DLA FT
(#)
n.
Let us show that the function is L-smooth:
[Vf(z)- - vf()
1 ~ Σ (v)(())
v(((e))
LA
VFT
2 A
VFT (
S
||
11
Let us take
A LA A
then
inf f(x) = nLA²
OA 4 AA.
f(0)
(Fr
inf Fr(x)) ZERT
ZERT
We showed that the function f f FA.L. (Step 2: Oracle Class)
In the oracles Oi, we have the freedom to choose a mapping f((-)) (see (7)). In this part of the proof, we simply take non-stochastic mappings fz(; V (xx that are, obviously, unbiased and x²- variance-bounded. We can take an arbitrary distribution, for instance, let us take D; = Bernouilli()) for all E [n].
(Step Analysis of Protocol)
We take
liVE L
A ==
to ensure that
1 n²
1
2
L 17
FT
for x E R such that prog(1)) < T. Thus
AL
heA"
Only the th worker contains a nonzero function and can provide a gradient every тn seconds. Since A is zero-respecting algorithm and the function fu. is zero-chain function, for all l: 2 0 such that
th T.
have
f || >
because need at least T' oracle calls obtain prog (x*) 2 T. It means that
inf kES.
||>)(>>)|'
|| >
for
AL t=
-1)
hE
We now prove the second part of the lower bound. (Part
(Step 1: e FA.L)
36

---

Let us fix A > 0. We assume that x = [.i....,a.. E R We define E R as the 1th block of a vector z 21..... znl E RRT.. We consider the following functions :
[x(x) = nLX
T2 A
FT
1
The function fi depends only on a subset of variables 2; from æ. Let us show that the function f is L-smooth. Indeed, have
- (V.(=))-V((())1 ALA
24
yi A
VFT
PT
S nL ||=
well
vi E [n],
Xi
and
Σ (V)(()) - v((co)) 2
[V -/(1)
[fi(z) v)(2))
n
< 11
n T2? ||:
vill = 1.? 100 - y1
1=1
Let us take
1
T=
L DE X²A0
then
1 TLL
LA SA.
((0)
inf (xx ZERT
[PT (0)
inf FT()))
S
h
ZERT
i=l
We showed that the function f E F..L (Step Oracle Class)
In the oracles Oj, we have the freedom choose mapping A vi((s)) (see (7)). Let us take
{ pj
-1) Vz RTT
fd Ol {)f(()) 1 1 > (i 1)T prog(2;)
D: = Bernouill(pp;) and ps E (0, 1] for all i E [n]. Let us show it is unbiased and q--variance- bounded:
E [V](0;; 0b] = v)((() ( [++1 > (i 1)T + prog(>;))
[ - 11 1)) = Vzf((z)
pi
for all j E nf, and
-v(())))((((())) |] < f E
E
-1
27
pi
because the difference is non-zero only in one coordinate. Thus
2
[+ (1 (1-p))
n²
Fr
(1
Pa)
E - -
00
Pi
Tipp
n2 n22 Tool (1 - -p:)
02
lpp,
where we take
nn' n2= 100
P; min
0217
(Step 3: Analysis of Protocol)
37

---

We fix > 0 and choose
11 MET,
LV EVEEE Di=1
to ensure that
L2
[VS(z)]
[f((2)] =
FT.
I
nt
P
11
M
VPT:
neT
[prog(x.))
<T]
(29)
1=
A
2i=1 7i
for all x = [.1...., In] E R². Thus
AL
T=
nE4
and
n TETi
p; min
Vi [n].
(30)
0² Ei= Ti
Protocol 3 generates the sequence
{o* [==]==
{[zt,...
1 M From (29), we have
k=0
inf kES.
inf
TsT D==T Ti
1 [prog
(x/²)
T
net
inf (prog(x;)) T).
kES.
E
Ti kES.
(31)
Further, we require the following auxillary lemma. See the proof in Section E.2.
Lemma F.1. For 1j 4, with probability not less than 1/2,
nET
inf 1 [prog < > 2e
x
1= KES.
for
1
0 -
T
-1)
<
24
n2=2200 mE
Using Lemma E. and (31), we have
inf
[
|
KES:
for
0² En
Di=l
Ti
AL
-2)
24
4
8c
This finishes the proof of Part 2.
E.2 Proof of Lemma E.
In the following lemma, we use notations from the proof Theorem A.2.
Lemma E.1. For r) = 4, with probability not less than 1/2,
NET
inf 1 [pro (x))
<
>
28
#= Tj
KES,
for
1
o E Ti
2 -1)
T
<
24
n2 me
38

---

Proof.
Let us fix t 2 0. Our goal is to show that the probability of an inequality
neT; inf
proo x < T S 2c
(32)
D= To KES.
small.
We now use the same reasoning as in Lemma D.2. We use notation {5), is 1th block of the vector x.
Let us fix a worker's index i E [n]-
Definition E.2 (Sequence k. k....)) Let consider set
KEN 1 .4 = 1, k-1 pk,t + Tga prog ({ (* j, =i]. 5, (6 a St (
We order this set and define the result sequence as ( size of the sequence. The sequence kf,5, is subsequence of iterations where the 7h oracle use the generated Bernuilli random variables in (7) when prog ({s=), j. The sequence S,z is defined in Protocol 3.
1i where m4j+1 [0, o0] is the
k-1
Then
Ma-+1 == in = 1 and I e [1, m1,++il] E NU foc}.
The quantity Wii++ is the index of the first successful trial, when prog(-) = j in the 7th block of the sequence z², Since the algorithm A is zero-respecting algorithm, for all & < 15 Kijmmnn the progress prog(177 <
As in Lemma D.2 (we skip the proof since the idea is the same. It is only required to use the different notations: x² - x Eny - fi.m.)). for all E [n], one can show that if infxes, [prog(>{) T] < 1
holds, then Σラ=1 fim. S t, where b == kT, for all & 2 1. The time Er is the smallest possible time when the 7th oracle can return the 1tth stochastic gradient. Thus
PP
NET inf [prog(())) < S 28
< IP
NETs T2
Σ Timis St
2$
T3 KES,
Using (25) with (and the different notations p - Pi, T1 + Tú, and Fng fimms)) ) have
P
aam. St
5
Vt
Ti
T
+
logo
(33)
24p;
2
We now rearrange the terms and use Markov's inequality to obtain
NET
P
1
>
S
2e
iml
Ti
2
P
Tj 1
Timm
21
>
1
Σ
Ti
17
T
<
1
1
2
Ti
E
Timo
1=1
T
2
1
fimm
St
f=1
for 17 >>>>> 2. Using the choice of p, in (30), we have
2 Σm
T >
To
n2
1222 nE
39

---

for all i E [n]. The last term does not depend on i. Therefore, we can use (33) with
1
0² nh Zi=1 Ti
T + log 6)
t S
24
2
to get
Σ timi
S 2E
S
2
-1
Σ
Σ
n
8
2
8.
Ti
/=1
7
Finally, for 2) 4 and 8 1/4, we have
P
net
inf 1l [prog(>;) < <T] S
28
2 2
== Ta kES.
E.3 Proof of Theorem A.3
Theorem A.3. Assume that Assumptions 7.1 and 7.2 hold for the function f. Assumption 7.3 holds for the function for all E [n]. Let us take the parameter = max { min ( 29
.n}, and 2Loz } = 0 (1/)) in Method 6, then after K 2 24A//e iterations the method guarantees
that K E E | S..
Proof. Note that Method 6 can be rewritten as x++1 = x² - - 1 E &1()) where the ENg are independent random samples. The variance of the gradient estimator equals
B,
B.
E
fi(l" - VV(ao)
11
B
n
1
E
(a= V)((a*))
n
B
B;
(i((=")E.)) - V/((o*) 11]
0²
(1
n
2
o²
n
B
S
where we use the inequality Theorem D.8). For a stepsize
( En Bi)
1 )=²²
2
We can use the classical SGD result (see
{ 1 ES
7 = min
I
2L
we have
||> Se,
k=0
12AL 12AL0
K
+
E2S
Using the choice of S, we obtain that Method converges after
24AL
K 2
8
steps.
40

---

E,4 Proof of Theorem A.4
Theorem A.. Let consider Theorem A.3. We assume that it worker returns a stochastic gradient
every seconds for all E [n]. Without loss of generality, we assume that 0 < S ... after
S Tn. Then
LA
o² LA
96
Ti
n
(15)
i=1
seconds, Method 6 guarantees find an E-stationary point.
Proof. The method converges after K (time required to collect batches with the sizes B; such that ( 1/B)) $ holds}.
In the worst case, for Tth worker, the time required to calculate B; gradients equals
ts == Ti (1+
because it is possible that a worker finishes the calculation of a gradient from the previous iteration (that we ignore) and only then starts the calculation of gradient of the current iteration.
Our goal to find feasible points 1 E R and BI, Bn such that
2 max ti, iE(n]
B
Bn
E N,
(34)
S
B:
n
Using the same reasoning as in Theorem 7.5, we relax the assumption that B; E N and assume that B, E R for all i [n]]
maxt tj (E[n]
B1,
Bn
R
(35)
B,,.., Bn > 0
n 1
S
71 B
n
If 1' E IR and B,,.., Bn are feasible points of (35), then 2/' and [B]].... [B,] are feasible points
of (34). Let show that t' = 2 (Tn + " Tτ) _ and B are feasible points. Indeed, for all e [n].
2T
B;
1>
1>
Next, we have
max 4 = max T3 (B. 1) 1
1E|n]
sE(m]
and
-1
1
1
Σ
Ti
27
=
B
-
where we use solution after
ti +/2
T, T
11/2 for all i Finally, it means that Method 6 returns
96AL
K 2t'
Tn +
T
8
n
72
i=1
seconds.
41

---

F Interrupt Oracle Calculations
Let us define a protocol and oracle where an algorithm can stop the oracle anytime. If an algorithm stops the oracle, its current calculations are canceled and discarded.
Protocol 8 Time Multiple Oracles Protocol With Control
1: Input: functions f F, oracles and distributions ((O1...., On), (Di...., ,,)) o(f),
algorithm E A
2: of = for all i E [n]]
3: for k 0 00 do
4: (t*+1 , x²)
A A
(g)
9*), ( gh+1 D
D t 2 th
.....
5: (8,441, gh+1) Opt (1 x*t e s s
D Day s = &
6: end for
In Protocol 8, we allow algorithms to output the control variables c² that can used the following oracle.
We take an oracle
0 R20 Rd
(R20 Rd x (0,1)) x (0,1) XS (R2o x Rd {0, 1)) xR"
input state
output state
such that
(1,,,, 1),
0),
c c= 0 and 8q = 0
((st, Szz 1),
0),
C 0 and
Sq 1 and
8, + T
O (t, (2), C,E)
((0,0,0),
(snn E)),
c 0 and
8q = 1 and 2 8, + T,
((0,0,0),
0),
1,
(36)
and f is a mapping such that
f Rd x S + Rdd.
The oracle (36) generalizes the oracle (7) since an algorithm can send signal e to the oracle (36) and interrupt the calculations. Note that if c 1, then (36) has the same behavior as (7). But, if 0, then the oracle (36) discards all previous information in the state, and changes Sg to 0.
Let us define an oracle class:
Definition F.1 (Oracle Class "n".stup
Let us consider an oracle class such that, for any f FA.L. it returns oracles O, O and distributions D; for all i [n], where f is unbiased oe-variancebbounded mapping (see ,stup
Ti
Assumption 7.3). The oracles 0 are defined in (36). We define such oracle class as Or Ti.....Te Without loss of generality, we assume that Ti
Tn
For the oracle class OF"" stop we state that
LA
d LA
Miime (An. FA.L)= =Ω
min mEin)
me²
The lower bound is the same as for the oracle class from Definition 6.3. We do not provide a formal proof, but close investigation can reveal that the proof is the same as in Theorem 6.4.
Indeed, in Part of the proof of Lemma D.2, we reduce the the inequality infkes, 1 prrog(=*) <T < 1 to the inequality Σ Ty 5 L, where Ey the shortest time when the oracles draw successful Bernouili random variable. The fact that algorithm can interrupt the oracles not change the quantity En.
42

---

G Time Complexity with Synchronized Start
In this section, we continue and fill up the discussion in Section 8.
Let us design an oracle for the synchronized start setting. We take an oracle
R20 x R2 x (R>0 x R2 x {0.13) x (Sg x x.. x Sq)
(R20 x Rd x {0. (0) xR
imput state
na
times
cutput state
such that
0
Teuntt (1, (82) 8os 84); (EI...,....,,))))
(1,,
0),
8q = 0,
(10,0,0).
0),
8q 1 and E [0, T1),
0,0,0,0),
ff(s::
$ and E [s, TI, T2),
((0, 0),
f((iii)))
5 and E [s T2,8 + Tz),
(37)
(10,0,0). E (((s))))
$ 1 and [st Tni 00),
and f f is a mapping such that
f Rd x Se - Rdd
We assume that gk+1 a tuple in Protocol 2: gh+l = (g ,..., c D.
The oracle (37) with Protocol emulates the behavior of a setting where we broadcast an iterate x all workers, and they start calculations simultancously. The workers have different time delays, hence some finish earlier than others. An algorithm can stop the procedure earlier and get calculated stochastic gradients, but other non-caleulated ones will be discarded.
For this oracle, we define an oracle class:
Definition G.1 (Oracle Class Or" O1....7.) ).
Let us consider oracle class such that, for any E FA,L, it return an oracle 0 = OVf and a distribution D, where f is an unbiased ge-variance-boundee mapping (see Assumption 7.3).
The oracle 0 fi.... is defined in (37). We define such oracle class as Oº syne generality, we assume that 0 < I ... Tu-
O....... Without loss of
now provide the lower bound for Protocol 2 and the oracle class " T.....
Theorem G.2. Let us consider the oracle class O sync for some a² > 0 and 0 < TI S...... S Tn- Orvins We fix any A > 0 and < I LA.. In the view Protocol 2, for any algorithm A Ans there exists a function f E FA.L and an oracle and a distribution (O,D) E O sync (f) such that infkes, [f((>) > e, where St = {K E Nole* I t}., and
LA
o² LA
]
mE(n)
min
Ti
ms?
The quantity and e are universal constants.
G.1 Minimax optimal method
In this section, we analyze the m-Minibatch SGD method (see Method 9). This method generalizes the Minibatch SGD method from Section 1.2. Unlike Minibatch SGD, the m-Minibatch SGD method only asks for stochastic gradients from the first m [n]] (fastest) workers. Later, show that optimal
43

---

Method 9 m-Minibatch SGD
1: Input: starting point x", stepsize 7, number of workers m E [rx]
2: for k == 0, ...... K do
3: Send the point x" to the first m workers
4: Receive i.i.d. stochastic gradients fx(" (a (f*H,,,n (m) from the workers
5: ==++1 = =x* - - Di
=i=1 Vs(*
6:
end for
m is determined by (38). And with this parameter, m-Minibatch SGD method is minimax optimal
under the setting from Sections 8 and G. Note that m m-Minibatch SGD is Minibatch SGD if m n.
We now provide the convergence rate and the time complexity.
Theorem G.3. Assume that Assumptions 7.1, 7.2 and 7.3 hold. Let us take the step size
Em
min
L 2L
in Method then after
12AL
12ALo
K N
E2m
iterations the method guarantees that 1. K
E
[f(x))]] Se.
Theorem G... Let us consider Theorem G.3. We assume that tt worker returns a stochastic gradient every TÜ seconds for all [nl]. Without loss of generality, assume that 0 Ti S... S. Tn Let us take
σ²
17 = arg min Tim m [(n)
1+
(38)
m's
Then after
LA
LA
12 min Tm
(39)
mE(N)
me²
seconds Method 9 guarantees to find an E-stationary point.
Despite the triviality of the m-Minibatchh SGD and it analysis, we provide it to show that the lower bound Theorem G.2 tight.
G.2 Proof of Theorem G.2
Theorem G.2. Let consider the oracle class of for some o² > 0 and 0 < Ti .... S Ta. We fix any A > O and < E S. LAL. In the view Protocol 2, for any algorithm A E An there exists a function f FA.L and an oracle and a distribution (O,D) D) O sync infRes, [f((>) > E, where St = {k E No St). and
O. (f) such that
LA
o²LA
-=ex
min mE(n)
Tm
m
The quantity e' and are universal constants.
Step 1 and Step 2 mirrors the corresponding steps from the proof of Theorem G.2.
Proof. (Step 1: Fa.L)
Let us fix À > 0. We take the same function f E FA.L as in the proof of Theorem 6.4. We define
LX²
f(z) =
Fr
h
44

---

with
A
T
LAPA0
(Step 2: Oracle Class)
Following the proof of Theorem 6.4, in the oracle O, we take the following stochastic estimator
(1 [1+ 1 prog(x)] _ (1)
fxx v,f(z)
Ve YEER"
(40)
and D (Bernouilli Bernoullll)))))))
where p (0, 1]. The stochastic gradient is unbiased
and x² variance--buudee if
2222202
min
021
(Step 3: Analysis of Protocol)
choose
X V221
ensure that [| L23 4
[FF(())]1
2=1 [prog(x)) < T] for all RT, where we use
Lemma D.1. Thus
AL 2el, A
=
and
(287 0²
min
Protocol 2 generates a sequence {-* { -
We have
RES [[((=>)]] > inf 1 [prog(=*) < <T].
inf
(41)
kES;
Further, we require the following auxillary lemma. See the proof in Section D.3.
Lemma G.5. With probability not less than 1-8.
inf [prog(x*) T kES.
for
(1+ (1+ 4pm )
(2 + log
T
<
min Tm me(r)
Using Lemma G.5 with
1/2 and (41), obtain
E
inf keS.
|V
2 2=P
inf 1 [prog(=*) < <T) >
kes,
for
1
(1+
o² 8 me
( AL 2cl, o - 2)
t min Tm
2 mm(m)
45

---

G.2.1 Proof of Lemma G.5
Lemma G.5. With probability not less than 1 8,
inf KES.
[prog(>*)
< T) 21
for
t S min Tm (1+ (1+4 4pm
(2 + log
2 me(n
Proof. (Part 1): Comment: in this part, we mirror the proof of Lemma D.2. We also show that if infsess, [prog(=*) < <T] < 1 holds, then we have the inequality Σ Ty S where Ey are random variables with some known "good" distributions. However, in this lemma the quantities fyc different.
In Protocol 2, the algorithm consequently calls the oracle O. inf [prog(=*) T] holds, then exists k St such that prog(=") = T. Since the algorithm A is zero-respecting, the mappings A will not output a non-zero vector (a vector with a non-zero first coordinate) unless the oracle returns non-zero vector.
<
Let us define the smallest index k(t) the sequence when the progress (r0)(=*(()) equals
k(i)= == inf k E No = prog(>")} E No J {oo}.
Definition G.6 (Sequence (k,,, 85, Let us consider a set
{(kk i) N [n] 1 and t 2 5 +. sk-1 (s A-1 s s
1
We order this lexicographically and define the result sequence as {(K5, i5, }p)pp= where m [0, oo] the size of the sequence. The sequence s defined in Protocol 2.
m since the sequence
Note that the algorithm A is only depends the random samples
p=
{(&,, (5)) are the indices of the random samples that are used in the oracle (37).
Let us denote the index of the first successful trial mi, i.e.,
711 == inf
and E [1, m]] ENU(
infses. 1 |prog(=*) < T] < 1 holds, then m < 00. Using the times th, the algorithm conse- quently requests the gradient estimators from the oracle (37).
In each round of the oracle's 's calculation, the algorithm can get the vector Vf {1) in not less than Ti seconds, the vector E & (s in less than T2 seconds, and so forth (see (37)). The algorithm can repeat any number of these rounds sequentially.
The algorithm A one by one requests mi;--- ma
{o...., n) gradient estimators from the oracle (37). takes at least Ti, seconds (Tu 0) to get a vector Σ (szi E.). Let us consider that A E N is the first index of gradient estimators such that is depends on some & = 1. Necessarily, have E Tmy I (11) Note that k. and mı..... my. depend the algorithm's 's strategy. Let find "the best possible" quantities k and mi...., my that are independent of an algorithm.
have Σ} m, ?/- Also, since the A is zero-respecting,
Let us assume that h.",, and m ... m, minimize the quantity
min
Tmy?
s.t. 1 e
(42)
m my E TO,
mj m/1
j=1
46

---

Then, we have
k
(k(1)
T
Note that if exists E [k=]] such that m3 > 1J1, then k", and m m -1: ",> .... m are also minimizers of (42) since the sequence Th is not decreasing. Therefore, (42) is equivalent to
min
Tmy
s.t. k EN
(43)
mi....ng E t0....,
my 2 m-
==1
Then, using the simple algebra, we have
(L)
Tm
Σ
Tmz
Σ
mi Tmg
Σ
m
min mE(m)
Tm
j=1
j 1:
I /:m33
my
j:m
m
Tm
Tm
m
min
2
min meInl
ml
m
In the first inequality, we use that my {0, ... ........,. m for all j [A**]. Next, using Lemma G.9, we get
(1) 2 2
min Tm (1 !/1
me/nl
m
Using the same reasoning, for j E (O...., - 1).
((++1) k()
1 min Tm (1+ Mi+1 mE(m)
2
where 7/+1 is the index of the first successful trial of Bernouilii random variables when prog(-) = j.
More formally, for all j E (0....,T-13
Definition G.7 (Sequence (K5, (S Let consider set
((k, E N x
[m] by
and t 2 - + t; and prog(s=-1) j),
6-1=(s7) ,8 c k-1
We order this set lexicographically and define the result sequence ppp)) where Mj+1 E [0, so] is the size of the sequence. The sequence k is defined in Protocol 2.
Then,
15+1 = inf
and E [1, [1,m)1]] E N (x).
By the definition of k(j), kb) is the first iterate such that prog(.) = j. Therefore, the oracle can potentially start returning gradient estimators with the non-zero, j 1 coordinate from the k(j)th iteration.
Thus, infNes, (prog(x*)
T 1 holds, then
min m
(1+
s {k(l) <t.
2
Am
Finally, we can conclude that
P inf 1 [prog(a*) kes,
<T
<1
< IP
min m
Tm
(1+ Di m
<t
Wt 0.
(44)
As in Lemma D.6, we show that
47

---

Lemma G.8. Let us take 44+1 E N. Then
P P - 1i+ m) s (1 p)5ti11P
(45)
for all j e , 1}.
T
See the proof in Section G.2.3. Intuitively, the algorithm A can not increase the probability of getting a successful Bernouilli random variable earlier with its decisions.
Let us temporally define
En = 2 me(n)
1 min Tm
(1 +
Th
m
for all E [T). (Part 2): Comment: in this part, we use the standard technique to bound the large deviations of the Sum E/= Im..
Note that function g IR + IR. such that g(x) minmel|n] Tm (1 =)) monotone and invertible. For t' 2 0, we have
is continuuus, strongly-
m
IP (Fr St' [is-...m. m) P (0(1)+1) </) = (1z+1 $g (6)
Using (45), we obtain
[ ((0)
P (En S _t|mmg..... m² s
Σ j=1
(1- p S p1-p)"'pSplp p
Let us define
p' p':=
then
P (Tu S s(/mm,....,, m) S v/.
Using the Chernoff method, as in Lemma D.2, one can get
P
Σ [m
T 57
S 2/0 214-0/
Let us take
t'
9
4p
min Tm me xl]
1+
4pm
then
1
)
p'
P
9
9
4p
4p
Therefore,
T
P
Σ
Eyp
21
i=1
Using (44), for
1
(1 (1+1) 4pm )
(T
+ log logo)
min Tm
me(ni
we have
T
P inf 1 [prog(**) <T] <1
< P
Σ
Eqp
<
KES,
1=1
The last inequality concludes the proof.
48

---

G.2.2 Lemma G.9
Lemma G.9. Let us consider sorted sequence 0 < T1 S ... S In and constant E N. We define
mm
t1 := min
mE
m
and
1 ?
t2 min Tm
me ng
m
Then
41 S t2 S 211.
Proof. Additionally, let us define
m1 == arg min Tm mE(r) mn)
and
(1
2 m
m2 arg min Tm
mE/m]
Then, using mi S 77, we have
77 [
7
7
f2 min
Tm
S
Tim
1+
2Tm.
261.
mE(n]
m
mi
m78
If m2 S v) then
f1 == 17
min mE/v)
Tm
S
Tmz
S Tmg
1 77
= 12-
m
m22
Otherwise, m2 > 1),
1l To
1+ 1)
f1 7 min
Ty
Tma S Tmg
tz2.
mEin| m
1
m2
G.2.3 Proof of Lemma G.8
In the following lemma, we use notations from Part of the proof of Lemma G.5.
Lemma G.8. Let take 4411 N. Then
P ( 14+1 Mall........ . m) < (1 5)511-11
(45)
for all j E (O....,T-11] 1}.
The idea of the following proof repeats the proof of Lemma G.8. But Protocol 2 with the oracle (37)
differ, so we present the proof for completeness.
Proof. We prove that
11t1 = 4++1 non (mh =4, S (1-1))---12
for all l,....I, N such that TP (Ni (n = 1.b) > o.
If exists i [i] such that 4 oc, then
P M1+t1
1i+1
n {mk = 113
49

---

for all 15+1 E N (see details in the proof of Lemma D.6).
Assume that < oo for all i [i]. By the definition of 7z+1, we have mj+1 2 fj+1 and
M 11---11
S11t4 1. Thus
0 and 6,
3,541
1y+1-1
1 n 43
S 1, m, 4--1
P
7/+1 4+1 0 [iee 4i
SP
{
0}, 5
345-11
Let us define set
S1 = {((k), i.),..., (Ka, 1 (21))) e (Nx(n])<st 18p < E [b+1] (Kps ip) < (kz, Alz+1 2 1.
Using the law of total probability, have
P
M6+1 = 1+
n (ne = 1:}
i=1
4111-1
15 K5,
441
P
0}.
5
1, m, 2 1121, n
f(K (5.p) = (Kp. ip)
81z11
300
111511
1=1
1--1-1
1941
Σ
P
hp (6
0}.
1,111 2 11+1, n
m (g = (kpp)p))
(1: 4i]
$1,11
i=1
where we take the sum over all ((K1, ..., (K E S If the event
1++1
(0. p (pp)
ip)) {mi+1 2 15+13
p=1
holds, then an event f:11 A ((pp))))) holds, where
A A(k) (5 and the 2 Ap-1 + Ti, and prog(s$r-1) = 5}.
At the same time. if Nit A(ke))))) holds, then {m++1 2 1 holds. Therefore,
1++1
1,+1
n
(1e Jar 1 (.p)) = (kips bp)3 n {ma-1 2 1+++1 = n
(1(K ( (kips (p)) n Ackp.1)))
p=1
p=1
and
M1tt = 1,+1
n (1n =1i}
i=1
11+1-1
1541
5 In = 41
( = 0}.
Suz11
Aay11
1, n (I(S p=1
((:k5pp=55pp)) = (p)) n A Alto)ss)
Sige1
1=1
Let us define of as a sigma-algebra generated by $ 2 and j E {0..... n). Then, we have
.,)),..,,,,,........... .e)...,(ii....... (si...., 53) for all
2f-1-1
Kp = =0} E 41
and
4,41
n
(10 (((5ppr55))) (kp: n Actr)i)) E b p0+11
50

---

since, for all e [yt1l the event (g) is only determined by shx-1 and thy that do not depend on { h And, for all p E [[+t], the fact that (k "ip (.p) (kp: does not depend on
(5' kig Note that kg-1. Ki (a.s.) for all i E [5]. Thus
Miah (1,11) (his)1) ( )} n [m = 4 E on M
i=1
since, for all i [s], this event implies that 15 kiy+1
All in all, we have that
b-4111
4
by G
0}
n
(105)p (. ) &p)) n A(kp)te))
n (n 443 E on Ry U
11
p=1
k=1
11i11 = } is independent of on (Sizes)
keg11 U
11511-1
Since
Uoayti-i 01
we get
11+t1 = 14-1 n (m -0:1 -1]
1941-1
1y+1
p
IP
( =0} n (1(4) ((s5,p::19p))
(Kips
1n) (n) A A(te)ss))
1:3
St.
If 1y+1 1, observe that the events [(K 55
(.6mm)) (ki, i 15 n A o do not
intersect for all (0 EN x [n]. Thus, we can use the additivity of the probability, and obtain
1 Nt - 143
P MJt1
li+1
S plP
((a))) (k, (wa)
(n 113
S p.
Otherwise, if 1++1
> 1, we also use the fact that the events do not intersect and get
1
P
1/i+1 - 1i+1
n (ni = 41)
1141-1
1-41-1
Sp
Σ P
(5
=0},
n
(10
hp)) n Actp.t))):
S1
p=1
p=1
5
U
(1: (1 =k; ((()))))))))
Acmos)
$
[n m =1}
(ke 111 1)
1=1
11-1-1
141-1
3 En = 4
<p Σ
P
t = =0}, n
(1(KS = (kps A A(tr)te))
815t1
p=1
i=1
where we used inequality (AA, B) < IP (A) for any events A and B. We take the sum over all (1),,1),.... (kt (1)) -1, where
Sty+1-1 = (((k),)), ... (ki (111-1)) E (Nx(m))6++)1 144 < 111+111: (kpp (p) < (ki,, ()).
Using the same reasoning, one can continue and get that
15t1 = 15+1 n (n= -4) s p1
Foor all i,j 2 and a, (o,...,n), the union of of and of is algebaa since either of C op. or of Coj.
51

---

G.3
Proof of Theorem G.3
Theorem G.3. Assume that Assumptions 7.1, 7.2 and 7.3 hold. Let us take the step size
1
min
L,
2L
in Method 9, then after
12AL
12ATo
K
E
iterations the method guarantees that
Σ==
K
[f((t)]
S..
K
Proof. Note that
k+
k
f(x Et),
m
where the stochatsic gradients are i.i.d Therefore, we can use the classical SGD result (see Theo- rem D.8). For stepsize
{ Em
7 = min
L 2Lo
we have
K
E
[+
Se.
K k=
12AL
12ALo
K
e2m
G.4 Proof of Theorem G.4
Theorem G.4. Let consider Theorem G.3. We assume that 8t worker returns stochastic gradient every TÜ seconds for all E [n]] Withou loss of generality, we assume that Ti S... S Tn. Let us take
o²
arg min Tm E
1+
(38)
m'e
Then after
LA
of LA mg?
12 min Tm
(39)
mE(n)
seconds Method 9 guarantees to find an E-stationary point.
Proof. In this setup, the method converges after K Tm seconds because the delay of each iteration is determined by the slowest worker. Thus, the time complexity equals
12AL
12ALo²
12AL
o²
12AL
1 o²
Ty
E
22m
Tm
EM
min Tm m' m'E(m)
m'e
where use the choice of the number of workers m.
52

---

H Proofs for Convex Case
H.1 The "worst case" function convex case
In this proof, we use the construction from (Woodworth et al., 2018). Let us define (0, R) {x E RT+1 |||||| S R}.
=
Let us take functions ft. - + RR and ft.m - R such that
fin(()) = min
{Fr(l)) + 11 x1
VER
and
(1 -
(1,(())== = max
Lx
1srST+1
n
where 1, > are free parameters. Let us define
y(z) == arg min (Fo)l))
" b1y x ==²)
SER
For ths function finss we have the following properties:
Lemma H.1 (Woodworth al. (2018)). The function Jt.9 satisfies:
1. (Lemma 4) The function fi is convex, I-Lipschitz, and smsoohhh.
2. (eq. 75)
I
min xEB.(0.1)
f(,(())
vT+1
3. (Lemma 6) For all x E B2)0, prog( Vin(())) S prog(x) + 1 and prog(u(z)) < prog(x)) +1.
H.2 Proof of Theorem B.4
Theorem B.4, Let us consider the oracle class O for some o2 > 0 and < Ti S... ...S.
.... S Ta-
We fix any R, L, M, e 0 such that VLR > e cive O and 2 = c2s². In the view Protocol for any algorithm E AR, there exists a function f E F R.M.L and oracles and distributions
(O,....,On)) (D....., Da)) E Oomiva" (f) such that
flatt)
E
inf
inf f(x) >E,
RES,
where S, == = No {t] and
1
VLR
M R²
o² R2
1=ex min mE(m]
min
VE
m
The quantities C12 and e are universal constants.
In Step almost repeat the proof from Woodworth et al. (2018). Steps and are very close to Steps 2 and 3 of the proofs for the nonconvex case.
Proof. (Step 1: f E Fromy R.M.E) Following Woodworth al. (2018), we assume that 1. Otherwise. one can rescale the parameters of the construction. Let us take the function fi,, from Section H.I with parameters
L
min M, 10(T + 1)3/2
and = 10(T + 1)3/21.
53

---

Using Lemma H.I, one can see that ft.n is convex, M- -ippschhi,, and L smsohh.. Therefore, ft.n E Fram L. Further, we use the notation f fl.
(Step 2: Oracle Class)
Let us take
[[ = v,f(x) [++1b > prog(z)) { (
Vo E R²,
and D, = Bermouill((p) for all é [n), where E (0, 11. We denote [æ], the jth index of a vector E RT+1, .I left to show this mapping is unbiased and o² --aarancce--ouueeeee bounded. Indeed,
[ - 1) = V.f(x)
E [1
v.f(x)
1++1 1 prog(z)]
for all E [T + 1], and
E [[()))))
V / E
($-1)
max JE[++1]
because the difference is non-zero only in one coordinate. Thus
-
(1-p) p)
[V (1 p))
E
P
12 p)
0
Vr (2,
where we take
p min 12
(Step 3: Analysis of Protocol)
Protocol 3 generates the sequence { k=0- Then, we have
f(**)
max 1SrST+1 (Ib(0*)))
51 1)
?
[1v(x*)) - =011 =0 (11(2=1 ]T+ 21(((=))]T+1
512T
7
7
Assume that prog(>**) < T. Using Lemma H.1, if prog(a*)) [u(=*))z+1 O. Therefore, f(x*) 2 5( 5/ (T++)
< T, then prog(y(z*)) S T and
and "
"
1
5/2(T +1)
M
1
f(z*) min f(z) 2 10
min
VT+I
"
2
2
20(T + 1)2
if prog(a=* < T. Let us take
M
VL
1 |
T min
6462
V80VE
to ensure that
M
f(x²)
min (0.1)
f(x) 2 min
2 48 2s
2VT +1 20(T + 1)2
if prog(a**) < T. is left to use Lemma D.2 with 8 = 1/2:
E
inf
f(z*))
min xEB110.1)
f(x) > 2=P
inf 1 (prog(x*) <T] 21) kES;
<T]21>> >E
(46)
RES,
for
-1
2
+ m )
[ (2-1)
Σ
5 min
24
mE[n]
54

---

1 24
(
(
0²
+1
-1)
- 2
min me(n]
ml?
We can take universal constants and c2 equal to 8-64 ensure that T 2 6. Therefore, 16r 2 2v741 and (46) holds for
(
(
0²
S min
+T+
(T+
(T
96 mEID
ml?
for
1
m -
1
0²
12
S
min 96 mEID
(T
(T+
+2)
m
ml?
32
and for
1 min 96
m
-1
σ²
M
VL
<
min
mE mM]
m
T3
me
64s2
V8OVE
H.3 Proof Theoree B.8
Theorem B.8, Assume that Assumptions B.5, B.6 and B.7 hold. Let us take the batch size S max { [ ,1], and M=40-75 (+//M²) in Method then after K > 2M2
iterations the method guarantees that TE [[(**]] f f(x*) S e, where z.K k -K--1 x.t and R = | -
Proof. Using the reasoning as in the proof of Theorem 7.4, just the stochastic gradient method with the batch size S. Method 4 can be rewritten as x++ = x² - 3 Σ Li=1 ff(="; &t), where the & are independent random samples. It means that we can use the classical SGD result (Theorem H.2). For a stepsize
that Method 4 is
7 = M g2
we have
E
[](*)] - -(x²)) 8
if
2M K >
xx
20112
(M2 + =2
||0
500 1
22
H.3.1
The classical SGD theorem in convex optimization
We reprove the classical SGD result (see, for instance, (Lan, 2020)) for convex functions. Theorem H.2. Assume that Assumptions B.5 and B.6 hold. We consider the SGD method:
k+1 x >g(x*),
where
2 + o²
For a fixed E IRd,, g(x) is a random vector such that [gg(x)] e 0f(z) (0f(z) is the subdifferential of the function f at the point z)).
E [1((a)) E [+(t)]]]]]
< 0
55

---

and 9(*²) are independent vectors for all h 2 0. Then
K
* )
E
f(x²) S
(47)
K
k=0
for
K 2 (M² + o²²) - 101
Proof. We denote G as a sigma-algebra generated by g(x"),...,,......)))..)..)))))). g((h Using the convexity, for all Rd, we have
f(x) 2 f(x*) + (E [9(00)] gh] - xx = f(x²) + E [ [g((x))) x - -
Note that
(o(a*), x²) = (g(at)) ght1 - xt) + (g(a*)) ) tltl)
--> |1²
(zth x k+1 20 x )
= -
11
x
k+1 1|
+ 2
1
|
x
k+ 112
1
1|0- x//
24
- |19(0**)] 1|?
+
1
| 11-111
112
||
x ||
2y
2
and
E [19(2* 0|? E | E [9((= ||0*)]1
+
|
|²1l12 [0]11{5c0
S 0² + +M2
Therefore, we get
f(x*) S f(x) + E [gg(=t), x² - -z)1
= f((x) + E [19(2*)) 012 |* + 2
1
||0-x*1
x² 112
1
||0 - x ++ 13 g*)
E
27
< 5((x) + 7 2 (M² + +²²)
1
||0 x
E
x
k+1 2 g+
27
24
By taking the full expectation and summing the last inequality for t. from 0 to K 1, we obtain
K
E
((xt))
Kf(()) + Ky (M2 + 0²) +
1
| 2012
RF. 27
1
|10 - x |1?]
27
<Kf()) + Ky (M² + 02) +
27 2 101
Let divide the last inequality by K, take = x", and use the convexity:
K
] -1(a") ? (M² + 0²) + 2 1| - =011
E
f
Σ k=
k
K
The choices of y and K ensure that (47) holds.
H.4 Proof of Theorem B.9
Theorem B.9. Let us consider Theorem B.8. We assume that tth worker returns a stochastic gradient every T seconds for all E [n]. Without loss of generality, assume that 0 < Ti S ... S Tn. Then after
M²R²
R²R²
8 min mein]
+
(17)
E2
mE²
seconds Method 4 guarantees to find an e-souution.
56

---

Proof. The proof is the same as in Theorem 7.5. It is only required to estimate the time that is required collect batch of size Method returns solution after
4M²
xx x
1
K x 2()())
min JE(n
Σ i=1
(S +
c²
seconds.
H.S Proof of Theorem B.10
Theorem B.10. Assume that Assumptions B.5, 7.1 and 7.3 hold. Let us take the batch size
an's 112) Accelerated max () 1 and ? min AL' (x²((<))((K+))))
Method 4, then after K
SVLR iterations the method guarantees that E [f(x]]] f(x*) S S, Ve
where R 2 x z²|
Proof. One can see that Accelerated Method 4 is just the accelerated stochastic gradient method with the batch size S. means that can the classical SGD result (Proposition 4.4 in Lan (2020)). For stepsize
1
3RSS
1/2
min
4L
40²(K
1)(K 2)
we have
4LR 4Vo2R2
E [[[[x)]] - f(x)) S
K2 +
VSK
Therefore,
E - Se
((x0)
if
8v LR
VLR o² R2
K
2 max
VE
VE E2S
where we use the choice of S.
H.6 Proof of Theorem B.11
Theorem B.11. Let consider Theorem 1. We assume that tth worker returns stochastic
gradient every Ti seconds for all E [n]. Without loss of generality, we assume that O < Ti S Tn. Then after
(1 m
(151)
VR Ve
o² R2
32 min mEim
To
me²
seconds Accelerated Method 4 guarantees to find an e-solution.
Proof. The proof is the same in Theorem 7.5. It is only required to estimate the time that is required to collect batch of size Accelerated Method returns a solution after
16VLR VE
K x 2t(
min jEin]
Σ
(S (S+
seconds.
57

---

I
Construction of Algorithm for Rennala SGD
In this section, we provide the formal construction the algorithm from Definition 4.1 for Rennala SGD. We consider the fixed computation model, where hth worker requires т; seconds to calculate stochastic gradients. We now define the corresponding sequence {A* 1,0 Tk=-- Let us fix a starting point
x² Rd. stepsize ? 2 and batch size S E N.
First, let consider the sequence { from Definition D.4 that represents the times when the workers would be ready provide stochastic gradients. Additionally, let define to and sequence of the workers' indices { 1se that are corresponding to the times {tx) We can define
25x (1/12))
(EU1//2)) (11/))))0((//))))))) 2 S
Σ
s¹), A (mod 2) 0,
(48)
(mod 2) = 1,
for all & 2 1, and A (fa, 2,, x²). For the fixed computation model, one can use this algorithm in Protocol 3 with the oracle (7) to get equivalent procedure to Method 4.
58

---

Experiments
In this section, we compare Rennala SGD with Asynchronous SGD and Minibatch SGD on quadratic optimization tasks with stochastic gradients. The experiments were implemented in Python 3.7.9. The distributed environment was emulated on machines with Intel(R) Xeon(R) Gold 6248 CPU @ 2.50GHz.
J.1
Setup
We consider the homogeneous optimization problem (1) with the convex quadratic function
1 x Ar - xT Vor E R
f(x)
2
We take d = 1000,
2
A
1
-1
R
1 and b
RR
-1
0
2
Assume that all n workers has access the following unbiased stochastic gradients:
[v((x))), Vzf(x) (1 11 11+113 1 > prog(=)) p -1) Va Rd
where & ~ D; = Bernouilli(p) for all i [m]. where E (0, 1]. We denote [ær,, as the jth index of vector E IRd In our experiments, we take p 0.01 and the starting point x. = [Vd, ... 0.... OjT. We emulate our setup by considering that the 7th worker requires vi seconds calculate stochastic gradient. In methods, we fine-tune step sizes from set {2 i [-20, 20]3. Rennala SGD, we fine-tune the batch size S E (1,5, 10, 20, 40, 80, 100, 200, 500, 10003.
J.2 Results
In Figures 1, and 3, we present experiments with different number of workers {100, 1000, 10000}. When the number of workers = 100, Rennala SGD with Asynchronous almost the same rate. However, when we start increasing the
SGD converge to the minimum number of workers n, one can see that Asynchronous SGD" starts converging slower. This is an expected behavior since maximum theoretical step size in Asynchronous SGD decreases as number of workers increases (Koloskova et al., 2022; Mishchenko et al., 2022).
K Experiment with Small-Scale Machine Learning Task
We also consider the methods in a more practical scenario. We solve a logistic regression problem with the MNIST dataset (LeCun et al., 2010). We take 1000 workers that hold the same subset of MNIST of the size 3000. Each worker samples stochastic gradients of size In Figures 4 and 5, we provide convergence rates and histogram of the time delays from the experiment. As in (Mishchenko et al., 2018), we can observe that asynchronous methods converge faster than Minibatch SGD. Unlike Section where Rennala SGD converges faster than Asynchronous SGD, these methods have almost the same performance in this particular experiment.
We implemented Asynchronous SGD with delay-adaptive stepsizes from (Koloskova al., 2022)
59

---

10a
Asynchronous SGD:
0.0625
Asynchronaus SCD: Stop size: 0.03125
Asynchronaus SGD: Step 0.015625
Minibatch SGD: Step size: 1.0
Minibbatch Step
Minibatch SGD: Step size: 0.25
SGD: Step size:
Rennala SCD: Stop sic:: 2.0 Batch Size: 40
SCD: Stop size: 1.0
10-1
10-2
200
600 times (seconds)
400
800
1000
Figure 1: # of workers n 100.
10a
Asymchronous SGD: Step size: 0.0076125 Asymchronous
Asynchronaus SCI: Step size: 0.001 953125
102
Miribaich Step
Miribatch SGD: Step size: 0.5
Minibatch Step
f(x
10
Rennala SGD: Step size: 1.0 Batch Size:
Rennala
Batch Stre:
100
Rennala SGD: Step size: 1.0 Batch Size: 5
10
10
1000
3000 times (seconds)
2000
5000
Figure 2: # of workers n 1000.
Asynchrenous
0.00048626125
Asynchrenous SGD: Step size: 0.000244110625
10a
Asynchronous SGD: size: 0.8001220703125
Minibatch SCD: Stop sire: 1.0 (Timcout)
Minibatch SCD: Step size: 2.0 (Timeout)
10a
Minibatch SCD: Stop sire: 0.5 (Timcout)
f(x
Rennala SGD: Step size: 2.0 Batch Size:
Rennala SGD: Step size: 2.0 Batch Size: 80
109
Rennala SGD: Step size: 1.0 Batch Size: 20
10-1
10-2
200
600 times (seconds)
400
800
1000
Figure 3: workers n = 10000.
60

---

10a
Asptskarww: 5003
Ayyneteareue Sab: 1aep 02268/25
Viibstt Step
100
SGD: Peg laach
Rx
500, siep tatch
sambl S0p Sies size satch Size: 100
10
10-2
250
500
750
1000 time
1250
1500
1750
2000
Figure 4: Logistic regression experiment
60
50
number of delays
20
10
time
Figure 5: Histogram of time delays
L Time Complexity of Asynchronous SGD
The works (Mishchenko al., 2022: Koloskova al., 2022) state that Asynchronous SGD convereges after
O
ALL
o² LA
iterations. This result directly does not reveal the time complexity of Asynchronous SGD. Let us provide the time complexity for the case when the workers require exactly т seconds to compute stochastic gradients. Let us fix time t 0. Then the workers will calculate most
Σ
stochastic gradients. To get e-stationary point, we have find the minimal t such that
nLA
2
LA
CX
(49)
2
pm
61

---

where the quantity is numerical constant, since the number of iterations can not be larger than the number calculated gradients. Note that
75
The time t' that satisfies
nLA
OLLA
+
Σ
22
i=
LA
LA
(=
(50)
ng
Therefore, the minimal time / that satisfies (49) greater or equal to (50).
M Analysis of Tixed-Computation Model Using Graph Oracle Models
In this section, we analyze the fixed computation model, where 7th worker requires seconds to calculate stochastic gradients. Without loss of generality, let us assume that < T₁ S S TT- We use the graph oracle framework by Woodworth et al. (2018). Let us fix some in the fixed computation model, the depth of the graph oracle D is at least Ω (fr.). This is the number of gradients that the first node can calculate after t seconds. The size of the graph N equals
Tn- Then,
EEL 7 since all workers calculate in parallel. Applying these estimates to Theorem of (Woodworth et al., 2018), one can see that, for convex, I-smooth, M M-Lipschitz problems with unbiased and oe-variance-bounder stochastic gradients on the ball (2, R), the lower bound is at most equals
MR
LR
oR
O min
(Vt/n'
(U/))²
From this estimate, we can conclude that in order to get e-solution, it is required
M
V.R
n
o² R2
O n min
+
22
VE
71
n
seconds.
M.1 Example when the lower bound from (Woodworth et al., 2018) not tight
Let us provide example when the lower bound from Theorem B.4 is strictly higher. Let take fi all i [m]. Then, it is sufficient compare
- 1=1
VLR Ve
M² c²
R² m
min
min
+
m
and
VLR M²R²
a2 R2 nE?
Ti min
VE
2²
n
Let us divide both formulas by the term with minimum and obtain
(1+
- m
min
mE
m
62

---

and
1
7
1=1
for some
O. Since
Σ
2i=1
θ (vm),
then we get
Vi
1
Vm (1 m)1 θ (Va)
min mE [n]
m)
min mEin|
m i=1
T5
and
1
a θ
(1+
a 1
71 +
if a S For instance, let us additionally assume that a nn, then the first term equals è (n'/4). while the second equals (1)) Theorefore, the lower bound from Theorem B.4 is tighter.
63


Reviews:
[{"review_id": "M8H18Wm2S9", "reviewer": "Reviewer_563Q", "summary": "This paper studies the minimax complexities of distributed asynchronous stochastic optimization methods. By extending the oracle framework previously used in the literature, it establishes new (lower) lower bounds for parallel optimization methods. Based on the insights from their proof, they propose a new algorithm meeting these bounds. Notably, it is provably faster than previous synchronous and asynchronous methods in the homogeneous case, which is verified experimentally.", "questions": "* Your model assumes fixed delays per worker: could your analysis also hold with stochastic ones?\n* You experimented with a fixed delay of $\\sqrt i$ for worker $i$ (line 1163). Did you also experiment with real-life delays experienced naturally in the distributed asynchronous setting (as in Mischenko 2022 [1])? (For example, this would hint that your method also work with stochastic delays)\n* Did you experiment with other convex functions other than the one introduced line 1159, and did you consistently observe that Renata leads to better results than Asynchronous SGD, or is this highly dependent on the convex functions used?\n* Why Goyal et al 2017 [2] is cited line 45?\n\n**Typos :**\n\n* Line 212: our framework *is*.\n\n**References :**\n\n[1] Mishchenko, K., Bach, F., Even, M., andWoodworth, B, *Asynchronous SGD beats minibatch SGD under arbitrary delays*, In NeurIPS, 2022.\n\n[2] Goyal, P., Dolla´r, P., Girshick, R., Noordhuis, P., Wesolowski, L., Kyrola, A., Tulloch, A., Jia, Y., and He, K., *Accurate, large minibatch SGD: Training imagenet in 1 hour.*", "limitations": "*", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "* This paper naturally extends the oracle protocol of previous work to cater for analysing parallel methods instead of sequential ones, which allows for a finer analysis of distributed methods.\n* Efforts have been made in the writing to explain the introduced novelties step by step, which greatly helps understand and position the contributions.\n* The insight taken from their new complexity proof that “ignoring stale gradients might actually help to converge faster” is interesting and highly relevant to the community, as it led to the development of a new state-of-art optimal method, which has provably and experimentally faster convergence rates than previous asynchronous algorithms in the homogeneous case.\n", "weaknesses": "* Many notations are introduced, which makes the paper a bit cluttered and cumbersome to read at times.\n* No experiments comparing Renata & Asynchronous SGD to minibatch (synchronized) SGD are made to confirm the “provably better rates” claimed Section 8. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review!\n\n> Your model assumes fixed delays per worker: could your analysis also hold with stochastic ones?\n\n> You experimented with a fixed delay of ... Did you also experiment with real-life delays experienced naturally in the distributed asynchronous setting...\n\nGreat question. We were thinking about this setup when we were writing the paper. However, we decided to stop with the fixed computation model and understand it first. We didn't try to run ahead of the train. Note that the Rennala and Malenia SGD methods can work even with stochastic delays. See Theorem 7.4 and Theorem A.3. These theorems do not assume that the delays are constants. \nWe believe that stochastic delays should be analyzed in future work. We will add a future work section where we will comment on this question. We believe that experiments with stochastic delays will be more appropriate in a paper that will consider such delays.\n\n> Did you experiment with other convex functions other than the one introduced line 1159...\n\nIn this paper, we only experimented with quadratic optimization tasks. In Figure 3, we show that Asynchronous SGD is not robust to slow workers. We expect such behavior in other practical optimization problems also. Quadratic optimization tasks are the simplest and the best-understood problems in optimization, and even on these problems, Asynchronous SGD can show bad performance.\n\n> No experiments comparing Renata & Asynchronous SGD to minibatch (synchronized) SGD are made to confirm the “provably better rates” claimed Section 8.\n\nNote that \\[1, Fig. 1\\] showed that Asynchronous SGD is better than Minibatch SGD in their experiments. Unlike \\[1\\], we provide *theoretical* evidence that asynchronous methods are strictly better.\n\n\\[1\\]: Mishchenko K. et al. Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays\n"}, {"review_id": "q5sfoXlN33", "reviewer": "Reviewer_Vdkt", "summary": "This paper studies time complexity of parallel stochastic optimization, establishes lower bounds, and proposes algorithms achieving matching complexity results.", "questions": "Doubts:\n- In (6), S_t is the set of indices that started computing gradients before time t. Shouldn't we consider k's which \"finished\" computation before t?\n- Line 205: what does it mean by the freedom to interrupt oracles?\n\nQuestions:\n- As the authors themselves remark in line 237, Rennala SGD goes contradictory to the idea of using all stochastic gradients. In that case, have the authors studied how it performs in practice in comparison to async SGD, especially with heterogeneity?\n- In Theorem 7.4, we need a large batch size in the presence of sizable noise. Since in a lot of analyses, the ratio of learning rate and batch size is the crucial quantity, is it possible to choose $S=1$, and $\\gamma = \\Theta (\\epsilon)$, and still get convergence? One would expect this to be closer to asynch SGD while achieving better rates, and performing better in practice.\n- I haven't looked at Appendix A, but looking at the heterogeneous result in Table 1, the lower bound and Malenia SGD complexity have no dependence on the heterogeneity term. How come?\n- The bound in (12) for when the workers start simultaneously: What is the explanation for this approach being slower?\n", "limitations": "n/a", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Based on my reading of the main paper (I haven't read the proofs), this is a solid theoretical work. The theoretical results improve widely used asynchronous SGD, and are even a bit surprising, especially the fact that ignoring some computations actually helps.", "weaknesses": "General comments:\n- The organization of the paper is a bit reader unfriendly. The assumptions are mentioned at multiple places, starting with page 1, but are formally introduced almost at the end (page 8). This makes the reading tedious.\n\nMinor comments:\n- line 16, shouldn't the codomain of $f$ be $\\mathbb R$ rather than $\\mathbb R^d$?\n- line 39: $L, \\Delta$ have not been introduced so far in the paper\n- Async. SGD (after line 52): step 2 gives the impression that only homogeneous data distribution across devices is considered in the paper. This is true for the main paper, but since the authors do have heterogeneous case results as well, they might consider reflecting that here.\n- Lines 98-99: \"this approach is not convenient\" Maybe giving a short intuition why (which becomes clear on the next page), would help the reader.\n- Typo in line 212", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the comments!\n\n> The organization of the paper is a bit reader unfriendly. The assumptions are mentioned at multiple places, starting with page 1, but are formally introduced almost at the end (page 8). This makes the reading tedious.\n\nWe define assumptions about our main problem (1) only in Section 7.1. In the introduction (Section 1), we give the reader a brief description of the class of optimization problems that we consider. If we delete Lines 21-22, then it would be more difficult to explain the history of previous results in Section 1.1.\n\n> line 16, ...\n> line 39, ...\n\nThank you, indeed, we will fix it.\n\n> Async. SGD (after line 52): step 2 gives the impression that only homogeneous data distribution across devices is considered in the paper. This is true for the main paper, but since the authors do have heterogeneous case results as well, they might consider reflecting that here.\n\nWe will add a comment near line 52. Note that we have a long discussion in Sections A.2 and A.4. We do not avoid the fact that Async. SGD was considered in the heterogeneous case.\n\n> Lines 98-99: \"this approach is not convenient\" Maybe giving a short intuition why (which becomes clear on the next page), would help the reader.\n\nWe tried to explain it in Lines 108-116. Unfortunately, we could not find a nice way to explain why \"this approach is not convenient\" without introducing our new protocol first.\n\n> In (6), S_t is the set of indices that started computing gradients before time t. Shouldn't we consider k's which \"finished\" computation before t?\n\nWe consider all k's which \"finished\" computation before t. Indeed, let us fix an index $k$ and a time $t.$ Let us consider the gradient $g^k.$ From line 5 in Protocol 2, we know that the time of calculation of $g^k$ is $t^k.$ So if $t^k \\leq t,$ then by definition of $S_t,$ we have that $k \\in S_t.$ \n\n> Line 205: what does it mean by the freedom to interrupt oracles?\n\nIn Section F, we generalize our new protocol and assume that an algorithm can stop the calculations of workers at any time. In Theorem 6.4, we analyze the oracle from (7). Note that an algorithm should wait till the end of every calculation and can not stop/interrupt calculations in (7). In Section F, we answered to the question: \"How will the complexity change if an algorithm can stop calculations at any time?.\" We show that it does not change the complexity.\n\n> As the authors themselves remark in line 237, Rennala SGD goes contradictory to the idea of using all stochastic gradients. In that case, have the authors studied how it performs in practice in comparison to async SGD, especially with heterogeneity?\n\nIn Section J, we have experiments that support our theory. We show that Rennala SGD (that ignores previous stoch. gradients) has better time complexities than Async. SGD.\n\n> In Theorem 7.4, we need a large batch size in the presence of sizable noise. ...  is it possible to choose $S = 1$, and $\\gamma = O(\\epsilon)$, and still get convergence?\n\nYes, it is possible. With this choice of parameters, Rennala SGD reduces to the classical SGD method with the fastest worker. However, it is better to choose $S = n,$ then one can show that Rennala SGD will have the suboptimal time complexity of Async. SGD. (we didn't add it to the paper because the choice of the parameter is suboptimal). But this a good question. We should probably add this clarification to the paper.\n\n> I haven't looked at Appendix A, but looking at the heterogeneous result in Table 1, the lower bound and Malenia SGD complexity have no dependence on the heterogeneity term. How come?\n\nPlease take a look at the proof of Theorem A.3 for the heterogeneous case. It is very short and gives the answer to why Malenia SGD complexity has no dependence on the heterogeneity term. The main idea is that Melania SGD calculates unbiased stochastic gradients of the function $f$ (not of the function $f_i.$). So Melania SGD can work in the arbitrary heterogeneous setting!\n\n> The bound in (12) for when the workers start simultaneously: What is the explanation for this approach being slower?\n\nOne should compare (12) and (11). First, the harmonic mean $\\left(\\frac{1}{m}\\sum_{i=1}^m \\frac{1}{\\tau_i}\\right) \\leq \\tau_m,$ so (11) $\\leq $ (12). One can show that (11) $\\ll$ (12) by taking $\\tau_i = i$ (as a theoretical example to show the gap). Since $\\frac{1}{m}\\sum_{i=1}^m \\frac{1}{i} \\approx \\frac{\\ln m}{m},$ then\n$$(11) \\approx \\min_{m \\in [n]} \\left(\\frac{m}{\\ln m} \\left(\\frac{L \\Delta}{\\varepsilon} + \\frac{\\sigma^2 L \\Delta}{\\varepsilon^2 m} \\right)\\right) \\leq \\frac{\\sigma^2 L \\Delta}{\\varepsilon^2} \\frac{1}{\\ln \\frac{\\sigma^2}{\\varepsilon}},$$ where we take $m \\approx \\frac{\\sigma^2}{\\varepsilon}$\nand\n$$(12) = \\min_{m \\in [n]} \\left(m \\left(\\frac{L \\Delta}{\\varepsilon} + \\frac{\\sigma^2 L \\Delta}{\\varepsilon^2 m} \\right)\\right) \\geq \\frac{\\sigma^2 L \\Delta}{\\varepsilon^2}.$$\nSince $\\frac{\\sigma^2 L \\Delta}{\\varepsilon^2} \\frac{1}{\\ln \\frac{\\sigma^2}{\\varepsilon}} \\leq \\frac{\\sigma^2 L \\Delta}{\\varepsilon^2},$ we have (11) $\\ll$ (12).\n\nThank you for the comments!\n"}, {"review_id": "JjnQLzPbCR", "reviewer": "Reviewer_DBuG", "summary": "This paper proposes a protocol that generalizes the classical oracle framework approach. Using this protocol, it establishes minimax complexities for parallel optimization methods that have access to an unbiased stochastic gradient oracle with bounded variance.", "questions": "Please cf. weaknesses part.", "limitations": "none", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The motivation of this paper is clear. \n- The theoretical analysis seems sound.", "weaknesses": "I am not an expert on this topic of this paper.\n\n1. The challenge of theoretical analysis should be made more clear, which highly relates to the contribution of this paper.\n2. The empirical study lacks.\n3. The organization of this paper is strange. E.g., related work is located in 6.1, and conclusion section lacks, etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review!\n\n> The challenge of theoretical analysis should be made more clear, which highly relates to the contribution of this paper.\n\nLet us briefly explain the main challenges of the paper:\n1. Even before we started proving the lower bounds, the main challenge was to understand how to analyze parallel optimization methods. In Section 3, we explain that previous papers were counting the number of oracle calls. We proposed a completely different paradigm, where instead of counting *oracle calls*, we count *time*. We believe that this is the first challenge.\n2. The next challenge comes from analyzing the lower bound for the complexity (6) (lines 113-144 in the paper). Nobody before us analyzed this complexity. The analysis required us to develop new non-trivial proof steps. For example, we discuss these non-trivialities in Section D (e.g., lines 571-573, 596-605, 670-674). There are many technical details that were not considered before.\n3. The next challenge was to develop the new optimal methods, Rennala SGD and Malenia SGD. These are new methods that improve the complexity of the celebrated Asynchronous SGD! For a long time, the community *believed* that Asynchronous SGD is the best asynchronous method. Our work shows that Asynchronous SGD is suboptimal. Instead of it, we designed new optimal methods. We believe that these are non-trivial solved challenges.\n\n**Summing up, our goal was to understand the theoretical limits of the celebrated stochastic gradient descent (SGD) method in the asynchronous setting with $n$ parallel workers. We believe that we took a nontrivial step towards a better understanding of parallel optimization methods. Further, we believe our work is a fundamental contribution to an important subfield of machine learning, resolving a long-standing open problem. As such, we think that a borderline/weak score is not appropriate. We hope we can convince the reviewer about this.**\n\n> The empirical study lacks.\n\nNote that in Section J, we consider experiments. There we show that even on simple quadratic optimization tasks, Asynchronous SGD can have bad convergence rates. Our new method significantly outperforms the previous baseline. However, our work is theoretical and we would want it to be judged as such.\n\n> The organization of this paper is strange. E.g., related work is located in 6.1, and conclusion section lacks, etc.\n\nWe understand that related work sections are typically written at the beginning of papers. In our paper, we put related work later because it makes the explanation of the Time Oracle Protocol easier. We can add the future work or conclusion section. We followed an organization that best fits our paper and its contents rather than the other way around: fit the paper into a pre-conceived/static organization structure. We believe the paper benefitted from this.\n\nWe hope that our comments have addressed the reviewer's concerns. If the reviewer has other questions, we will be happy to continue the discussion."}, {"review_id": "iWxc9dAqQP", "reviewer": "Reviewer_AK4H", "summary": "Consider the classical statistical risk minimization framework with stochastic gradients, and propose new lower bounds on the optimal time complexity. Also propose a new method Rennala SGD that attains the lower bound. This work makes the case for asynchronous methods.\n\nIn particular, this work proposes a new oracle-based lower bound on the optimal convergence rate in time, rather than iterations, and develops an algorithm (essentially straggler-based SGD) that achieves this bound in the shared-system/parameter-server setting.", "questions": "Please see my questions provided in-line above, in the weaknesses section.", "limitations": "Limitations of the work are not adequately addressed. There are for instance, many assumptions that are taken for granted in the analysis that may limit the applicability of the findings to practical settings... namely the fixed delay model per worker, and the relationship between the batch-size S and the number of workers n. I am curious how findings would change in settings where S >> n or S << n.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "**Significance**\nThis work takes a step towards developing more practical asynchronous optimization methods, and providing convergence rates and complexity bounds that more closely reflect practical considerations of convergence time, rather than iterations.\n\n**Originality**\nThe proposed method is not entirely novel (e.g., see Dutta et al., 2018 or related works on straggler-based SGD methods that ignore computation from stragglers), however the new lower bounds, problem formulation, and analysis are of sufficient novelty, to the best of my knowledge.\n\n**Clarity**\nThe work is well written and easy to follow.", "weaknesses": "Lacking empirical evaluations, the only such experiments are on quadratics, buried deep inside the appendix. While these plots are compelling, I would encourage the authors to consider small-scale numerical results on other machine learning workloads.\n\nAnother weakness of this work is on assuming a fixed computation time for each worker. Such models are highly restrictive and impractical. I would encourage the authors to consider ways for extending their framework to arbitrary, but bounded worker delays. I would appreciate a discussion on how such lower-bounds (or the optimal method), may change if these bounds were overly conservative and long-tailed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the interesting comments!\n\n> Lacking empirical evaluations, the only such experiments are on quadratics, buried deep inside the appendix. While these plots are compelling, I would encourage the authors to consider small-scale numerical results on other machine learning workloads.\n\nOur work is theoretical. Thus we seek to understand the theoretical properties of asynchronous methods and their limits. One can see that even on simple quadratic optimization tasks, Asynchronous SGD can have bad convergence properties. We expect such behavior on other machine learning tasks. Having said that, we will follow your advice and include a few more small-scale experiments with different tasks. We expect the results to be similar.\n\n> Another weakness of this work is on assuming a fixed computation time for each worker. Such models are highly restrictive and impractical. I would encourage the authors to consider ways for extending their framework to arbitrary, but bounded worker delays. I would appreciate a discussion on how such lower-bounds (or the optimal method), may change if these bounds were overly conservative and long-tailed.\n\nPlease note that unlike much of existing asynchronous optimization/SGD literature, which works with the formalism of **(iteration) delays** (which does not refer to time but to the difference in iteration counters between when a model was read and an update by a \"delayed\" worker written/applied), we directly work with the notion of **time** it takes for each worker to perform its computation. This is a different paradigm. The classical iteration delays are not first-class citizens in our formalism, i.e., they are not assumed. Instead, they are the result of the algorithm and the problem (e.g., larger noise $\\sigma^2$ and/or smaller error tolerance $\\varepsilon$ lead to larger batch size in Thm 7.4, and in classical asynchronous SGD, this would lead to larger iteration delays since such an approach counts every stochastic gradient as an iteration), and an indirect function of the speeds $\\tau_i$, which are the first-class citizens in our work. We believe our approach is more reasonable - we assign processing times to all workers, and the  delays are a function of the algorithm. Not assumed, but observed.\n\nWe say this to make it more clear that our constants $\\tau_i$ should not be mistaken with the iteration delays from the majority of  previous works on asynchronous SGD (we are not saying the reviewer made such a mistake - we just want to make this very clear since the reviewer refers to delays in his/her question). These prior works sometimes indeed work with non-constant and even unbounded delays. Due to the different nature of iteration delays and compute times $\\tau_i$, the fact that they do so, and that we work with fixed times $\\tau_i$ should therefore not be seen as a relative shortcoming of our approach. \n\nWe therefore interpret the question as follows: \" I would encourage the authors to consider ways for extending their framework to arbitrary, but bounded worker computation times $\\tau_i$.\"\n\nHaving said that, it absolutely does make sense to extend our setup to non-constant processing times $\\tau_i$, e.g., \n- processing times belonging to some interval, \n- or random processing times following some distribution (with mean $\\tau_i$ an variance $\\sigma_i^2$, \n- or processing times which depend on the stochastic gradient sampled). \n\nWe believe these are all good ideas for future study, which should be simpler given our foundational work in the constant $\\tau_i$ setting. We believe that more complicated computation models deserve a separate research effort and analysis. We will add a future work section where we will comment on this question.\n\nWe remark that Reviewer 563Q also asked us a similar question, too.\n\n> Limitations of the work are not adequately addressed. There are for instance, many assumptions that are taken for granted in the analysis that may limit the applicability of the findings to practical settings... namely the fixed delay model per worker, and the relationship between the batch-size S and the number of workers n. I am curious how findings would change in settings where S >> n or S << n.\n\nThe assumption \"the fixed delay model per worker\" (here delays mean computation/processing times $\\tau_i$, and not iteration delays) was never hidden. It is immediately considered in the introduction. Even in the title of the paper, we say that we get theoretical complexities \"Under a Fixed Computation Model.\"\n\nAll our findings will hold in both regimes $S \\gg n$ or $S \\ll n$. Let us clarify it. If $S \\gg n$, then $\\frac{\\sigma^2}{\\varepsilon} \\gg n.$ It is a \"high noise/small # of workers\" regime. Then one can show that (11) is minimized when $m \\approx n.$  In the \"high noise/small # of workers\" regime, we need the contribution of all workers. However, when $S \\ll n,$ then $\\frac{\\sigma^2}{\\varepsilon} \\ll n.$ It is a \"low noise/large # of workers\" regime. In this case, the optimal $m$ can be much smaller than $n$ (see Lines 199-205). We will be happy to add this clarification to the camera-ready paper.\n"}]

Author rebuttal:

Meta-review: This paper introduces novel lower bounds and addresses a crucial topic concerning the optimality of parallel/asynchronous methods. The content of the paper is thoroughly discussed, and although some reviewers noticed a minor flaw related to organization and experiments, it appears that the authors' rationale for introducing context before discussing related work and incorporating additional experiments to substantiate their claims is well-founded. The concerns raised by reviewer DBuG lack specificity, making it challenging to endorse their assessment. Considering these factors collectively and the support of other reviewers toward acceptance, I recommend the acceptance of this paper.
Decision: Accept (poster)