Tight Time Complexities in Parallel Stochastic Optimization with Arbitrary Computation Dynamics
Authors: Alexander Tyurin
Venue: ICLR 2025 Poster (2025)
Keywords: nonconvex optimization
lower bounds
parallel methods
asynchronous methods
convex optimization
Primary area: optimization

Abstract: In distributed stochastic optimization, where parallel and asynchronous methods are employed, we establish optimal time complexities under virtually any computation behavior of workers/devices/CPUs/GPUs, capturing potential disconnections due to hardware and network delays, time-varying computation powers, and any possible fluctuations and trends of computation speeds. These real-world scenarios are formalized by our new universal computation model. Leveraging this model and new proof techniques, we discover tight lower bounds that apply to virtually all synchronous and asynchronous methods, including Minibatch SGD, Asynchronous SGD (Recht et al., 2011), and Picky SGD (Cohen et al., 2021). We show that these lower bounds, up to constant factors, are matched by the optimal Rennala SGD and Malenia SGD methods (Tyurin & Richtárik, 2023).

Published as a conference paper at ICLR 2025
TIGHT TIME COMPLEXITIES IN PARALLEL STOCHAS- TIC OPTIMIZATION WITH ARBITRARY COMPUTATION DYNAMICS
Alexander Tyurin AIRI, Moscow, Russia
Skoltech, Moscow, Russia al invandertiurnne com
ABSTRACT
In distributed stochastic optimization, where parallel and asynchronous methods are employed, we establish optimal time complexities under virtually any computation behavior of menker/deviies/CPU/GGGUUU capturing potential disconnections due to hardware and network delays, time-varying computation powers, and any possible fluctuations and trends of computation speeds. These real-world scenarios are formalized by our new universal computation model. Leveraging this model and proof techniques, we discover tight lower bounds that apply virtually all synchronous and asynchronous methods, including Minibatch SGD, Asynchronous SGD (Recht al., 2011), and Picky SGD (Cohen et al., 2021). We show that these lower bounds, up to constant factors, are matched by the optimal Rennala SGD and Malenia SGD methods (Tyurin & Richtárik, 2023).
INTRODUCTION
Optimization is one of the main workhorses in machine learning (ML), data science (DS), and federated learning (FL) (Bottou et al., 2018; Kairouz et al., 2021). These fields rely on stochastic optimization methods, with notable examples including the stochastic gradient descent method (SGD) (Robbins & Monro, 1951) and ADAM (Kingma & Ba, 2015), which are considered to be the de facto choices for solving large-scale optimization problems (Schmidt et al., 2021). Due to the computational demands of modern functions, the size of datasets, and the need for data privacy, parallelization and distribution are essential for building efficient systems (Kairouz et al., 2021; Mayer & Jacobsen, 2020). However, it brings many challenges, including computation heterogeneity: many workens/CPPss/GUUS/phoor work in parallel but with varying computation speeds, fluctuating performance over time, and potential disconnections due to hardware and network delays (Li et al., 2020).
1.1 PROBLEM SETUP
Unconstrained smooth optimization problems that arise in ML, DS, and FL are described by
min
f(x),
(1)
ZER4
where / Rd -> IR with the following standard assumptions:
Assumption 1.1. f is differentiable & L-smooth, i.e., fxx) ( < L || ul1. Vo, Rd. Assumption 1.2. There exist f" IR such that f(x) f* for all a E Rdd
In the nonconvex world, we want to find an e-stationary point, a (random) vector 전 E gd such that E[llV [+) c, since, in general, it is intractable to find global minimum in the nonconvex setting (Nemirovskij & Yudin, 1983; Murty & Kabadi, 1985). We analyze convex functions in Section H.
We consider a problem where workers do not have access to the gradients of the function f. Instead, they can only calculate stochastic gradients. Such problem arises when the computation cost of an

---

Published as a conference paper at ICLR 2025
exact gradient is huge or even infeasible due to batch normalization (loffe & Szegedy, 2015), dropout, random data augmentation, and many other handcrafted and naturally occurring noise sources that do not allow calculate gradient (Goodfellow et al., 2016).
Assume that n workers work asynchronously in parallel and calculate stochastic gradients. We focus on two setups:
Homogeneous setup. For all E [ra], worker has access to an unbiased stochastic gradients V (x;; with Ee--ariance-boundee variances, where & is a random variable from some distribution DD on Sg. In ML and FL, this would mean that all workers have access to the same data.
Assumption 1.3 (Homogeneous setup). For all E [n], worker i can only calculate V ff(=; {) and [<[Vf(=;(]] = (x) and Eg [e]lVf((
(()))(]]])))))) o² for all x E R where o² 2 0.
Heterogeneous setup. Unlike the previous setup, we assume that f(x) = = f((x) in this setting, where fa Rd + IR for all i E [n], and worker i can only access stochastic gradients v f((z;()) &:) of the local function fi, where & is a random variable from some distribution D; on Sg. In ML and FL, this would mean that all workers have access to different data.
Assumption 1.4 (Heterogeneous setup). For all i E [n], worker can only calculate (z( fz), and E4, (x; [.) (ax and Eg, (z; (=)) I a² for all RRd, where o² 2
1.2 RELATED WORK
Oracle complexity with one worker. The optimal (dimension-fiee free) oracle complexity. # of stochastic gradient calls, and an optimal method are well-known in the homogeneous and heterogeneous setups. In particular, Arjevani et al. (2022); Carmon et al. (2020) showed that the optimal oracle complexity is (LA/= + o LL/E2) achieved by SGD, i.e., x+1 = _² /V <*), where ç are i.i.d. random samples, A = f(x)) - f" x E IRd is a starting point, = θ (mi,
is a step size.
Oracle complexities with workers. There Arjevani et al., 2020; Lu & De Sa, 3021), to generalize the classical oracle complexity (Nemirovskij & Yudin, 1983; Arjevani al., 2022) the parallel setup with workers. In the homogeneous convex setup, the most relevant to our setup work (Woodworth et al., 2018), using the graph-based oracle model, obtained the tight oracle complexities for several parallel setups. The heterogeneous setup with the local smoothness assumption was addressed in (Arjevani & Shamir, 2015; Hanzely al., 2020; Lu & De Sa, 2021).
several approaches, e.g., (Scaman et al., 2017;
The listed works address key questions in parallel optimization by establishing lower bounds and developing methods to achieve them. However, the assumptions regarding the computation processes are overly idealistic, as they assume stable, unchanging. and equal computation speeds for all workers. They fail to capture practical scenarios such as partial participation, random outages, computation heterogeneity (some workers being faster than others), communication heterogeneity (some workers sending vectors faster than others), and changing computation performance over time. is unclear if the optimal methods for their lower bounds will maintain optimality in more realistic computation scenarios.
Time complexities with bounded computation times. Instead of using oracle complexities, another way to compare algorithms is to use time complexities. Using this paradigm, Mishchenko et al. (2022); Koloskova al. (2022) showed that the celebrated Asynchronous SGD method (Recht al., 2011;
Dean et al., 2012) with the proposer step sizes can provably improve Minibatch SGD in the homoge- neous setup. Asuum for now that worker requires most T. seconds calculate one stochastic gradient for all E [n]. Minibatch SGD is the iterative process x++1 = z² 7/n Σ V ff(==(()) where 7 is stepsize, et are i.i.d. samples, and V fz= ; { are calculated in parallel. This method converges after O (LA/s + LD/nee) iterations (Cotter et al., 2011: Goyal et al., 2017; Gower et al., 2019) and after
0 max 7, iE(n]
LA
LLLA n2
(2)
2

---

Published as a conference paper at ICLR 2025
Notoor
Figure 1: Fixed Computation Model: The previous compu- tation paradigm (Mishchenko et al., 2022) assumes that the performances/powers of the workers remain constant over time. Tyurin Richtárik (2023) established the optimal time com- plexities (13) and (20) for this paradigm.
Conpesze Fowess
Time
Weake Worke
Computitoo Pouerrs
1892
Tine
Time
(a) Itregular Powers
(b) Periodic Powers
(c) Random Outages
Figure 2: Universal Computation Model: new computation paradigm that captures virtually all possible computation scenarios. The three subplots present illustrative and non-exhaustive examples of irregular { (Fig. 2(a)), periodic noisy powers {v: (Fig. 2(b)), and random outages of the workers, where v; equals 0 periodically (Fig. 2(c)). For all possible scenarios,
establish optimal time complexities (see Theorems 5.1, 5.3, 6.2, and 6.4). It is possible to get interpretable and explicit formulas for the optimal time complexities in some scenarios (see Examples 3.2, 5.4, 5.5, 6.5, and 6.6). However, for Fig. 2(a), Fig. 2(b), and Fig. 2(c), is arguably intractable to find [fza/e] analytically, Instead, we can easily do it numerically in Fig. 2(a) and get the optimal time complexities 6.57 and 13.02 sec with LA / = 10 and a² ///=- = 100 in the homogeneous and heterogeneous settings, respectively (Fig. 2(b): 2.34 and 2.53 sec; Fig. 2(c): 77.04 and 84.62 sec).
seconds because this method waits for the slowest worker with the time max,e([) T. Using Asyn- chronous SGD, the time complexity (2) be improved
LA
(3)
where the dependence the processing times is harmonic (Mishchenko al., 2022). An alternative method that also achieves this time complexity Picky SGD (Cohen et al., 2021).
Subsequently, Tyurin & Richtárik (2023) formalized the notion of time complexity using the time oracle protocol, and under the assumption that worker requires at most тı seconds to calculate one stochastic gradient for all E [m]) proved that the time complexity lower bound is
+ min
1
LA
OLLA
(4)
mein|
Tmu
seconds in the homogeneous setup, where permutation that 7, Twy Tx.. Moreover, they developed new method, Rennala SGD, that achieves the lower bound in the homogeneous setup. Under the bounded computation and communication assumptions, Tyurin et al. (2024b); Tyurin & Richtárik (2024) provided optimal time complexities in setup where the communication time between the workers cannot be ignored.
CONTRIBUTIONS
In this work, we aim to determine the optimal time complexities of distributed stochastic optimization with parallel and asynchronous methods in scenarios where the computational performance of workers can be arbitrarily heterogeneous and variable. We want to capture all possible cases, including random outages, time-changing computation performances, and slow and straggler workers.

---

Published as a conference paper at ICLR 2025
We consider computation paradigm, for which coin the name universal computa- tion model, that includes virtually all possible computation scenarios that can appear in practical distributed, parallel, and asynchronous optimization environments.
Using the universal computation model, we prove a tight lower bound for time complexities of parallel and asynchronous optimization methods in the homogeneous setting, which is matched, up to constants, by our Theorem 5.3, saying that Rennala SGD (Tyurin & Richtárik, 2023) is optimal.
We also close the problem in the heterogeneous setup. We discover the optimal time complexity and prove the optimality of Malenia SGD (Tyurin & Richtárik, 2023) (see Theorem 6.4). The proofs of the lower bounds are based new proof techniques and constructions (see Section A for overview).
In Section H. we provide time complexities of (Accelerated) Rennala SGD and (Accelerated) Malenia SGD in the convex setting.
3 UNIVERSAL COMPUTATION MODEL
To achieve the goal of finding the optimal time complexities for the stochastic optimization problem under any heterogeneous asynchronous computation setup, we first have formalize the computation model of the workers. To formalize all possible cases, we propose using the following computation model, called the universal computation model.
For all E [n]. we consider a non-negative continuous almost everywhere function e; RR - R4¹ called a computation power of worker
Assumption 3.1. For all i [n], 04 is non-negative continuous almost everywhere.
Without loss of generality, we assume that the time starts from zero. Using the same reasoning as in physics, where the energy is the integral of power, in our domain, the number of stochastic gradients that worker i can calculate from time to to time t is the Riemann integral of the computation power v; followed by the floor operation (because we can not partially calculate a stochastic gradient);
U u (T) = [V((t)) Vi(t)),,
"# of stoch. grad. by worker in [4o, 411"
(5)
where we additionally define a mapping V, R -> R such that
vi(t) L' (;(T)dr.
(6)
For t to: Vi(ti) Vi(to) is called a computation work of worker from time to time t
Example 3.2 (Fixed Computation Model), Let us consider the simplest example and take the performances that do not change through time, i... vx(t) 2 E 14 for all 2 0. If we take to 0, then
V (T( (V((t2) Vi(to)] [utt]]
This formula formalizes simple logic that it takes 1/U; seconds to find one stochastic gradient in worker i because [ty x 1/0z] = 1, 2/v, seconds to find two stochastic gradients in worker i because [1 2/v,] = 2, and forth. The higher the power v, the less time takes to find new stochastic gradient. (7) provides the number of stochastic gradients under the fixed computation model when reparametrized with v; = 1/T.- However, the fixed computation model limited; for visual comparison, see Figures and 2. Section 5.1 has more examples.
Theorem 3.3 (c.g. (Bartle & Sherbert, 2000)). For all E [n]], V4 is continuous and non-decreasing on 1 if v; is non-negative continuous almost everywhere (Assumption 3.1).
Notations: R4, : [0, oo), R = [0, oo). N: {1, 21, }, No = (0, 1, 2....... [m] = (1...., ............ II is possible to consider the Lchesgue integral and assume that the functions {r.) are measurable, but will stick with the Riemann integral for simplicity.
4

---

Published as a conference paper at ICLR 2025
Notice this theorem can hold even if e; is discontinuous. In general, the computation powers {8} can be even random. Indeed, we can assume that v, : R4 x 52 - R4 is a stochastic computation power, where ! sample space of probability space. Then, all the following results hold when conditioned over all randomness in {vi), assuming that the sources of randomness are statistically independent. Without loss of generality, continue assuming that dy
IR+ 1 for all [n].
For all [n], let define the generalized inverse function Vi- R - E such that
(S) min {t 2 0
Vi(1) S}
(8)
for all S E RT. V, is strongly increasing, then Vi- is the standard inverse function of V,,
PRELIMINARIES
Before presenting our main results, we formalize the concepts of time and time complexity. This section is somewhat technical; readers not interested in the proof details may skip ahead to Sections and 6.
Recall that in the classical approach of deriving lower bounds, we examine the following protocol (Nemirovskij Yudin, 1983; Nesterov, 2018; Carmon et al., 2020):
Protocol Classical Oracle Protocol
Input: function f E F, oracle O(f), algorithm A E A
2: for k 0. O...., 00 do
3: x A (g'
2 = A for
4: g++1 O(**)
5: end for
Where we want to find the worst-case oracle complexity formalized by
inf sup sup inf kk SEAJeFocoly oco())
k
E V
[P] se)
Protocol is reasonable way to establish lower bounds and compare algorithms, but it is not convenient for analyzing parallel algorithms. order to analyze parallel and asynchronous algorithms, Tyurin & Richtárik (2023) proposed to use the time multiple oracles protocol:
Protocol Time Multiple Oracles Protocol
1: Input: function f (or functions f.). oracles {0:)_ E O(f), algorithm A = { E A
2: sf 0 for all E [n]
3: for k = 0. O...., 00 do
4: (E++1, j6+1 k- x² )--) = A (g) 9h.
th+1 th
5: (s.11, gb+1) Opt (1 I sjetis cbtt1)
DVj + pk+
8 k+1
8
6: end for
Unlike the classical protocol where an algorithm returns a new point a based on the current information g ......"* ......"'. this protocol requires algorithm to return time +++1, index of an oracle f++1, a control variable c+1, and a new point z² the parallel setting, algorithms have access many workers/oracles. In every iteration, algorithm has the freedom to choose any oracle using ++1 and call the oracle at a point z* The role of control variables (c*+1) will be clear later.
The main idea is that algorithm controls time and decides when it is ready go forward using time sequence [ J. Let us introduce an oracle that emulates the behavior of real worker, and then will provide clarifications. For all i [m]] we consider the mapping
We the standard convention min oc.

---

Published as a conference paper at ICLR 2025
O R4
R
R
R x {0,1)) x (0.1)
RR+ x R x {0,1))
x R
such that
time
point
imput
stop computation
oulpui state
output vector
(1, 1),
0), c 0, 8q = 0,
(Stt 1),
0), 0, 8q 1, V.((t) -V((s) < 1,
O,(t, x. Sur sy).
gi {,t)), c = 0, 0g = 1, Vi(t) Vi(ss) 2 (9)
((0,0,0), ((0,0,0),
0), 1,
where De_,1,6 is some distribution that can depend on sz,t, - De.. and g, : R x Rd is mapping. This oracle return different outputs depending
input it receives: i) if 0, O, then the oracle is only starting the calculation of a stochastic gradient, and memorizes the time when it called in the variable s;; ii) if 0, 1, (i(() Vi((s) 1, then the oracle is still calculating; iii) if c = 0, Sq = 1, ((t) (s,) 2 1, then the oracle has finished the calculation and returns gi (3 {,
the point 5y where the calculation was initialized. The condition (t) - (s() 2 1 means that "at the current time t, the oracle is ready to return the stochastic gradient that began to be calculated at time st The control variable allows algorithms to stop the calculations at any time they want if they pass 1.
The oracles (9) force algorithms increase times; otherwise, they will not get stochastic gradients and enough information to find an e-stationary point. Using Protocol 2, we consider the time complexity measure
inf sup sup inf { fEA (O.D)
||] <e S.
s: = {K { Nol S 51
1
0
E
inf KES.
(10)
where the sequences t a are generated by Protocol 2. This measure takes algorithm and function classes and returns the worst-case time complexity. We refer to (Tyurin & Richtárik, 2023)[Sections 3-5] for more details.
In this work, we consider zero-respecting algorithms formalized by the definition below. Definition 4.1 (Algorithm Class Ar). Let us consider Protocol 2. We say that an algorithm A {A* (c Je=o is a zero-respecting algorithm, if
1. 4 Rd x ... x Rdd
R2
[n] x (0, IRd Ak 2 1,,1 E R2o x [n] x (0. 13 x Rd
2. supp (x*) C U supp (g") for all & E No, where (upp(x)= = {i E [d] 24 + 0).
3. for all ls > 1 and g¹ ..... g E Rd, we have gh+1 2 the where + and th are defined as
(th+1 ..) A (g)
and (+* A (gg ......-.1!.
The first condition defines the domain and range, the second condition is the definition of zero- respecting algorithm (Carmon et al., 2020), the third condition ensures that the algorithm return non-decreasing sequence of times (Tyurin & Richtárik, 2023).
HOMOGENEOUS SETUP
We are ready to present our lower bound in the homogeneous setup. Let us also provide a simplified and informal version of the theorem, followed by the formal one.
Theorem (Informal Formulation of Thcorem 5.1). Let Assumptions 1.1, 1.2, 1.3, and 3.1 hold. It is impossible to converge faster than 1/2 x t [/xx 4 seconds, where the sequence {tx} is defined in (11) and ei is universal constant.
Theorem 5.1. Consider Protocol 2. We take computation powers {v:} such that Assumption 3.1 holds, and fix L, A, 0 and o² > 0 that satisfy the inequality < é' LA. For any algorithm A E Ans there exist a function f. which satisfy Assumptions 1.1, 1.2 and f(0) f < A. and stochastic gradient mappings {g:} in (9), which satisfy Assumption 1.3, i.e Eg (9i(2 E, ()] Vf(xx) and

---

Published as a conference paper at ICLR 2025
Method 3 Rennala SGD
Method 4 Malenia SGD
1: Input: point z", stepsize y, batch size S
1: Input: point x), stepsize % parameter S
2: for k = 0, I,.... K do
2: for k = 0, I,..., K 1 do
3: Ask all workers to calculate stochastic gra-
3: Ask all workers to calculate stochastic gra- dients x.
dients x*
4: Init g" = and
4:
Init of =0 and B; = 0
5:
while < S do
5:
while (+ B.
do
6:
Wait for the next worker
7:
Receive calculated stochastic gradient
6:
Wait for the next worker j Update B, = B, +
ffr" 5 V
8:
+ ;V = 8
8:
Receive a calculated stochastic gradient V. ck Lt,B,)
Ask this worker to calculate a stochastic gradient at z. 10: end while
9:
9:
of - - + V ,5,nn
10:
Ask this worker calculate stochastic gradient at x end while
11:
x k++1_ x² 79
12: Stop all the workers' caleulations
11:
13: end for
12:
g = = -
n
(In practice, instead of x+*1 -r (Line 11), 13:
k-1 x² 79*
one can use any other update technique, including 14: Stop all the workers' calculations
ADAM (Kingma & Ba, 2015), AdaGrra (Duchi 15: end for
al., 2011), and SGD with momentum (Polyak, 1964; Nesterov, 1983))
(a): practice worker i can store gf
(e E,1) V (( S o² for all 8, E Rdd, i [nx] such that E inf
kES.
holds, where Se = {K No th st).
2 1 [11x
and
{ t 0: Σ [i(t) - V2(t 2 max {| (11}
:g:=min
(to -
(11)
for all 2 O. The quantities d, 01 and 02 universal constants. The sequences x² and the defined in Protocol 2.
Unlike most previous works (c.g., (Nesterov, 2018; Arjevani et al., 2022; Tyurin & Richtárik, 2023)), the obtained lower bound is implicit. This, we believe, is expected due to the generality of our assumptions about the universal computation model. To find the lower bound, one must determine the minimum of the set in (11) one by one (t, 12, ......) to get 1/2 x t & x LA/sj-- Computationally, this problem is not difficult since the function Σ [V((t) Vi(+e is non-decreasing: thus, for instance, we can employ the bisection method.
5.1 OPTIMAL ALGORITHM
The natural question is whether the lower bound is tight. The answer is yes (as usual, up to constant factors). The lower bound can be matched by Rennala SGD (Method 3) (Tyurin & Richtárik, 2023).
In every iteration, the method collects batch of size S, and performs gradient-like step once the batch has been collected. The following result was proved in (Tyurin & Richtárik, 2023). The proof technique simple and follows the classical analysis of SGD (Ghadimi & Lan, 2013; Khaled & Richtárik, 2022) since the logic of Rennala SGD is equivalent to the steps k+1 I 7/s ΣS fx(a*; ( Ex), where {Er} are i.i.d. samples.
Theorem 5.2. [(Tyurin Richtárík, 2023)] Let Assumptions I.I, 1.2, and 1.3 hold. We take 1/2L and batch size 5 max / 1} in Method 3. For all K 2 24LA/e, get V Se.
K- E
WWe the standard convention (0) xc.

---

Published as a conference paper at ICLR 2025
The following result is new and proves the time complexity of Rennala SGD. Theorem 5.3. Consider the assumptions and the parameters from Theorem 5.2, plus Assumption 3.1. Then Method 3 (Rennala SGD) converges after most 8 {م22م] seconds, where
4. = min {
max {
1 0: Σ (V()) -
Vi( -
(to =0= Ak (12)
Up to constant factors, Theorem 5.1 together with Theorem 5.3 provide the tight time complexity for the problem (1) in the homogeneous setup. As we noted in Section 5, the obtained result implicit, we do not get closed-form expression for f124L4/=] in Theorem 5.3. That said, the sequence & is mathematically rigorous, and we can provide explicit formulas in some cases. Surprisingly, Rennala SGD gets the optimal complexity automatically, without prior knowledge about the computation powers {&² J. Therefore, the absence of a closed-form expression irrelevant for practical implementations and is only of theoretical interest.
Example 5.4. [Fixed Computation Model] Consider Example 3.2 with (t(t) = Us E R4 for all I 12 0, E [ni. Then, for all [n], V1( v.l and
2uza θ
min mE(n]
m Σ
Un
(4A
LA
LAge me²
(13)
m
is a permutation such that Un, 2
Ux
The proof's of the examples are in Section I.
In Example 3.2, we discuss that T; = 1/u, is the time required to find one stochastic gradient worker If we reparametrize (13) with vi 1/T,, then we get the time complexity (4). Thus, Example 5.4 restores the optimal time complexity obtained by Tyurin & Richtárik (2023) for the fixed computation model, where the smaller the computation times т; (the higher the computation powers vz), the smaller the complexities. Notice that if ti is small enough for some worker j. then it is possible that the complexity (13) will depend on Vy, meaning that this worker potentially does contribute to an optimization process because it is too slow. We can immediately derive more general result:
Example 5.5. [Nonlinear Trend] Assume that (t))) = 24 x g(t) with v; > for all i E [r]] and
continuous almost everywhere positive" function g(l) R2
- R.,. Then
F = G-1
C1
min mE[m]
1 m
Σ
m
Uns
)
LA + LAg")
(14)
where æ is a permutation such that Usr, depend on other parameters but is bounded).
2 Un,, G(t) == So g(T)dr, and e₁ e [1/4,4] (can
Example 5.5 illustrates many practical cases. For example, the computation powers can vary according to the function g(t) = 1.01 + sin(t), causing them periodically increase and decrease. Then G(t) 1.01t - cos 1, which is invertible, and we can obtain a formula for the optimal time complexity using (14).
Let us consider an example where all workers have the same performances, but any worker can randomly shut down and, after a while, become available again. We could have chosen virtually any (even random) example, but for the sake of simplicity, let us consider the following example gain basic intuition.
Example 5.6. ["Random" Outages] Assume that
(t) v, LE [ki 1), (k- +1]
#=1
(15)
0, otherwise,
0, k; N, and h > 0 for all i E [n:. Then
LA + Loo0)
min me(n]
(16)
m
Kins
where क is permutation such that kin 5... k
'e can relax these assumptions measurability and non-negativity, but the proof will be more technical.
8

---

Published as a conference paper at ICLR 2025
In this example, worker is active in the time intervals [0, 1), [Ky, K2 + +1]. [2k,, 2h, + 1], and so forth. The parameter k, characterizes how often the worker's ' outages occur.
The formula (16) says that the more worker is inactive (the larger ky). the more time it takes to solve the problem. Due to the min operation in (16), the formula indicates that some workers can be igmored if their &ę are too large. In general, we could have analyzed (15) with [>=[sttatts.. ( where the pairs {startz.j, end are arbitrarily (random) values on R,, but would get less interpretable formulas.
6 HETEROGENEOUS SETUP
We now consider the heterogencous setup discussed in Section 1, and present our first lower bound:
Theorem 6.1. Consider Protocol 2. We take computation powers {e,} such that Assumption 3.1 holds, and fix L, A, 0 and o² 2 0 that satisfy the inequality < è' LA. For any algorithm A E Aus there exist functions {fr)i=ı where the function f= 1 > i=1 fi satisfies Assumptions 1.1, 1.2 and f(0) f - A, and stochastic gradient mappings {9:)==1 i= in (9), which satisfy Assumption 1.4, i.e.
Eg [st:
f(xx)) and E=) Vf((s )11 S o² for all sy E Rd E [n], and
t 2 O, such that El inf [[](<>>]||
holds, where S. =- { E No 1t S ft.
KES.
x log
and
max for o 1)
tu = min 1
1 Σ
C3
Va(t)-Vi(L Vi
log
1)
(17)
for all lo 2 1 (1) =0) 0). The quantities d, o1, C22 and e3 are universal constants. The sequences x and t are defined in Protocol 2.
Unlike (12) where the dependencies on {Vi} are mean-like, the dependencies in (17) are harmonic- like. Since the heterogeneous setting is more general and complicated, this leads to worse guarantees. Looking ahead, up to logarithmic and constants factors, the obtained lower bound is tight and attained by Malenia SGD (Tyurin & Richtárik, 2023) (see Section 6.
We asked ourselves if getting a tight lower bound without the logarithmic terms is possible. The answer is affirmative, but instead of taking one group of predefined worst-case deterministic func- tions {fi). the following construction samples random functions {f+] The fact that the functions {f.) random helps prove tight lower bound (the main difference between the theorems is highlighted in bold). This lower bound is fundamental and can not be bypassed by any parallel and asynchronous method (Zheng et al., 2017; Gu et al., 2021; Mishchenko et al., 2022; Islamov et al., 2024). We provide informal and formal versions of the theorem:
Theorem (Informal Formulation of Theorem 6.2). Let Assumptions 1.1, 1.2, 1.4, and 3.1 hold. is impossible to converge faster than 1/2 x 4[ [ seconds, where the sequence {Lx is defined in (18) and Cj is a universal constant.
Theorem 6.2. Consider Protocol 2. We take computation powers {0x} such that Assumption 3.1 holds, and fix T., A, E > and a² 2 0 that satisfy the inequality <, el L.A. For any algorithm A E An, we sample ) from some distribution of functions, where the function f == 1 + fo satisfies Assumptions 1.1, 1.2 and f(0) ff" <. A deterministically, and there exist stochastic gradient mappings {g: 1 in (9), which satisfy Assumption 1.4, i.e., Eg [g:(s E, t)] f((ss)
and Bellgg((s;; {, V[((s=)]1)) S o² for all 82 Rdd [n], and t 2 0, such that || > holds", where S. = {k No <t].
E inf kES.
t = 14 [ax
We take the expectation all randomness.

---

Published as a conference paper at ICLR 2025
and
4=:minn min 12 120: (
les (V) vi(l--1)) ")- max (2xx
(18)
for all 2 =0). The quantities d', ci2 c2, and eg are universal constants. The sequences x and th are defined in Protocol 2.
6.1 OPTIMAL METHOD
The obtained lower bound is tight since it is matched by Malenia SGD (Tyurin & Richtárik, 2023). This method is closely related Rennala SGD with similar structure, and mathematically. it is the vanilla SGD method with proper batch collection strategy (see Method 3). However, essential algorithmic changes must be applied to make it work with heterogeneous functions. The following theorem was proved by Tyurin & Richtárik (2023).
Theorem 6.3. [(Tyurin Richtárik, 2023)/ Let Assumptions I.1, 1.2, and 1.4 hold. We take take eS
S max { { and = min { 2La2 θ (1/L) in Method then after K 2 24AL/e
iterations the method guarantees that K SK-1
E
ff(x"))
S.
This is new theorem analyzing Malenia SGD with the universal computation model:
Theorem 6.4. Consider the assumptions and the parameters from Theorem 6.3, plus Assumption 3.1. Then Method 4 (Malenia SGD) converges after at most ( seconds, where
E. = min 120: E [V((t) - Vi(Fa-1)--t) 2 max
20 nE
1}}
(Fo =0) (19)
for all k 21
Up constant factors, Theorem 6.2 and Theorem 6.4 provide the optimal time complexity in the heterogeneous setting. The result implicit, which is not problem in practice since Malenia SGD does not require {Vi} to reach the optimality. Let consider examples where we can get explicit formula.
Example 6.5. [Fixed Computation Model the Heterogeneous Setting] Assume that (t) = V2 with 0; 0 for all i [n]. Then
=
max 1 + (+ iE|n]
(20)
Example 6.6. [Nonlinear Trend in the Heterogeneous Setting] Assume that v((1) 02 g(() with
> 0 for all i E [n] and a continuous almost everywhere positive function g(t) RT - R.. Then
Taanal = G-1 G-1 ((-
o nE
max iEla
(21)
where G(I) = S/ ((T)dr, and e E [1/4,4] 4] (can depend on other parameters but bounded).
Example 6.5 shows that our result recovers the optimal complexity derived in (Tyurin & Richtárik, 2023). However, our time complexity works with virtually any computation model.
7 CONCLUSION
To the best of our knowledge, this is the first work that provides optimal time complexities under virtually arbitrary computation behavior workers in the distributed setting. We believe that our lower bounds, Theorems 5.1 and 6.2, and upper bounds, Theorems 5.3 and 6.4, close important problem in parallel optimization. Our approach and techniques have the potential to serve as a foundation for solving other mathematical questions from parallel and asynchronous optimization in the future. One interesting question determining the optimal time complexities when the universal computation model is correlated with the randomness from stochastic gradients.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. Advances Neural Information Processing Systems, 28, 2015.
Yossi Arjevani, Ohad Shamir, and Nathan Srebro. A tight convergence analysis for stochastic gradient descent with delayed updates. Algorithmic Learning Theory, pp. 111-132. PMLR, 2020.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, pp. 1-50, 2022.
Robert G Bartle and Donald R Sherbert. Introduction to real analysis, volume 2. Wiley New York, 2000.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223-31, 2018.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):71-120, 2020.
Alon Cohen, Amit Daniely, Yoel Drori, Tomer Koren, and Mariano Schain. Asynchronous stochastic optimization robust to arbitrary delays. Advances Neural Information Processing Systems, 34: 9024-9035. 2021.
Andrew Cotter, Ohad Shamir, Nati Srebro, and Karthik Sridharan. Better mini-batch algorithms via accelerated gradient methods. Advances in Neural Information Processing Systems, 24, 2011.
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc' aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, et al. Large scale distributed deep networks. Advances in Neural Information Processing Systems, 25, 2012.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7), 2011.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal Optimization, ((()):234122666 2013.
Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume MIT Press, 2016.
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. SGD: General analysis and improved rates. In International Conference Machine Learning, pp. 5200-5209. PMLR, 2019.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: Training imagenet in hour. arXiv preprini arXiv: 1:Xiv:/706.026777 2017.
Xinran Gu, Kaixuan Huang, Jingzhao Zhang, and Longbo Huang. Fast federated learning in the presence of arbitrary device unavailability. Advances in Neural Information Processing Systems, 34:12052-12264, 2021.
Cristóbal Guzmán and Arkadi Nemirovski. On lower complexity bounds for large-scale smooth convex optimization. Journal of Complexity, 31(1):1-14, 2015.
Filip Hanzely, Slavomír Hanzely, Samuel Horváth, and Peter Richtárik. Lower bounds and optimal algorithms for personalized federated learning. Advances in Neural Information Processing Systems, 33:2304-2315, 2020.
Xinmeng Huang, Yiming Chen, Wotao Yin, and Kun Yuan. Lower bounds and nearly optimal algo- rithms in distributed learning with communication compression. Advances in Neural Information Processing Systems, 2022.
11

---

Published as a conference paper at ICLR 2025
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pp. 448 456.. PMLR. 2015.
Rustem Islamov, Mher Safaryan, and Dan Alistarh. AsGrad: A sharp unified analysis asynchronous- SGD algorithms. In International Conference on Artificial Intelligence and Statistics, pp. 649-657.
PMLR, 2024.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-210, 2021.
Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. Transactions on Machine Learning Research, 2022.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 2015.
Anastasia Koloskova, Sebastian U Stich, and Martin Jaggi. Sharper convergence guarantees for asynchronous SGD for distributed and federated learning. Advances in Neural Information Processing Systems, 2022.
Guanghui Lan. First-order and stochustic optimization methods for machine learning. Springer, 2020.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-60, 2020.
Yucheng Lu and Christopher De Sa. Optimal complexity in decentralized training. In International Conference on Machine Learning, pp. 7111-7123. PMLR, 2021.
Ruben Mayer and Hans-Aroo Jacobsen. Scalable deep learning on distributed infrastructures: Challenges, techniques, and tools. ACM Computing Surveys (CSUR), 53(1):1-37, 2020.
Konstantin Mishchenko, Francis Bach, Mathieu Even, and Blake Woodworth. Asynchronous SGD beats minibatch SGD under arbitrary delays. Advances in Neural Information Processing Systems, 2022.
Katta G Murty and Santosh N Kabadi. Some NP-complete problems in quadratic and nonlinear programming. Technical report, 1985.
Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Yurii Nesterov. A method of solving a convex programming problem with convergence rate o (1/k**
2). Doklady Akademii Nauk SSSR, 269(3))543, 1983.
Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964.
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild!: A lock-free approach to parallelizing stochastic gradient descent. Advances in Neural Information Processing Systems, 24, 2011.
Herbert Robbins and Sutton Monro. stochastic approximation method. The Annals of Mathematical Statistics, pp. 400-407, 1951.
Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In International Conference Machine Learning, pp. 3027-3036. PMLR, 2017.
12

---

Published as a conference paper at ICLR 2025
Robin M Schmidt, Frank Schneider, and Philipp Hennig. Descending through crowded valley- benchmarking deep learning optimizers. In International Conference on Machine Learning, pP- 9367-9376. PMLR, 2021.
Alexander Tyurin and Peter Richtárik. Optimal time complexities of parallel stochastic optimization methods under a fixed computation model. Advances in Neural Information Processing Systems, 2023.
Alexander Tyurin and Peter Richtárik. On the optimal time complexities in decentralized stochastic asynchronous optimization. arXiv preprint 162., 2024.
Alexander Tyurin, Kaja Gruntkowska, and Peter Richtárik. Freya PAGE: First optimal time complexity for large-scale nonconvex finite-sum optimization with heterogeneous asynchronous computations. arXiv preprint a5X5::2005./555, 2024a.
Alexander Tyurin, Marta Pozzi, Ivan Ilin, and Peter Richtárik. Shadowheart SGD: Distributed asynchronous SGD with optimal time complexity under arbitrary computation and communication heterogeneity. arXiv preprint 20w::2002.0485. 2024b.
Blake Woodworth, Jialei Wang. Adam Smith, Brendan McMahan, and Nati Srebro. Graph oracle models, lower bounds, and gaps for parallel stochastic optimization. Advances in Neural Information Processing Systems, 31, 2018.
Shuxin Zheng, Qi Meng, Taifeng Wang, Wei Chen, Nenghai Yu, Zhi-Ming Ma, and Tie- Yan Liu. Asynchronous stochastic gradient descent with delay compensation. In International conference on machine learming, pp. 4120-4129. PMLR, 2017.
13

---

Published as a conference paper at ICLR 2025
CONTENTS
Introduction
1.1
Problem setup
1.2
Related Work
2
Contributions
3
Universal Computation Model
4
Preliminaries
5
Homogeneous Setup
5.1
Optimal algorithm
Heterogeneous Setup
6.1
Optimal method
10
7
Conclusion
10
Proof Techniques
15
A.1 Proof techniques in the homogeneous setup
15
A.2 Proof techniques the heterogeneous setup
15
B Proof of Theorem 5.3
16
C Proof of Theorem 6.4
16
Proof of Theorem 5.1
17
E Proof of Theorem 6.1
21
F Proof of Theorem 6.2
26
Auxiliary Lemmas
32
H Convex Setting
38
H.1 Homogeneous setup and nonsmooth case
39
H.2
Homogeneous setup and smooth case
39
H.3 Heterogeneous setup and nonsmooth case
40
H.4 Heterogeneous setup and smooth case
40
I Proof of Examples
41
L.1
Homogeneous setup
1.2 Heterogeneous setup
42
14

---

Published as a conference paper at ICLR 2025
A PROOF TECHNIQUES
A. PROOF TECHNIQUES IN THE HOMOGENEOUS SETUP
The proof of the upper bound (Theorem 5.3) is relatively simple and uses only (5). The proof of the lower bound (Theorem 5.1) is standard at the beginning: we assume that the workers store the "worst-case" function from (Carmon et al., 2020) and have access to oracles that calculate the exact gradient but zero out the last non-zero coordinate with some probability (Arjevani et al., 2022). The next steps are new and can be briefly described in the following way. The workers calculate in parallel; thus, they can calculate at most >;= i=1 [V)( stochastic gradients by time I. At the same time, the oracles zero out the last coordinate with a probability p using i.i.d. Bernoulli random variables. Therefore, the workers cannot get point with a non-zero first coordinate carlier than f := min {t 2 : Ex=1 [v] 2 7/) seconds, where {n are i.i.d geometrie random variables. Using the same reasoning, the workers cannot get a point with a non-zero hehh coordinate earlier than f4 = min (t 2 0 >i=1 [V((t) Vi(ta-1) 2 Mk seconds, and T = 1.2/.. With high probability, the large chunk (at least a quarter of T = LA/e) of {ne is not significantly smaller than l/P se max (10'/ .1. Finally, with high probability, at least a quarter of indices from the set [T] satisfy
1
ty 2 min t 0
LVv(() - -1(())((ttt))) 2 max {10%/7
(22)
Note that all lower bounds in stochastic optimization ultimately reduce to the concentration analysis of the sum of random variables. Tyurin & Richtárik (2023) approach this by analyzing the sum E minje[n] Ty]li. where Fi are ii.d. geometric random variables. In our case, we cannot directly apply this reduction anymore because the computation powers vary over time. Therefore, we found non-trivial modification: we have to reduce the problem to the concentration analysis of the sum of indicators: Σj= M[n ] and investigate this sum, which represents the number of indices that satisfy (22).
A.2 PROOF TECHNIQUES IN THE HETEROGENEOUS SETUP
The proofs in the heterogeneous setup are more technical, so we suggest first understanding the idea in the homogeneous setting. Unlike the homogeneous setting, where all workers have access to stochastic gradients of the same function, the heterogeneous setting offers more freedom in designing the worst-case construction. We can allocate the worst-case functions from (Carmon et al., 2020) in almost any desired manner. We consider S functions {hy} such that h;(z) RSxT + R and hy depends only on the juh block xÿ E R of x = [x], [.,,s.,,ss E RRST where T ~ LA/s, and consider the optimization problem with f(x) 1/4 E5 (x). As usual, the designed oracles zero out the last non-zero coordinate of calculated gradients, and algorithm cannot find an e-solution before at least roughly half of the functions {h are "solved," requiring non-zer values in the last coordinates of the corresponding blocks. The main question is how to distribute the functions {hy) among the workers. Intuitively, the slower a worker, the more functions we want to assign to this worker. This intuition works, and in Theorem 6.1, we take the first K "parts" of all the functions } , and assign the "parts" of the first C (fi) functions to the first worker, the "parts" of the second 01/ /V2 (12) functions the second worker, and so forth, where i & 4 from (18), C1 is a constant such that Σ / (f,) S. The next K "parts" we assign proportionally to (V, (fz) V (f1)), and so forth. In total, the allocation of the functions (hy} is dynamic since one function can be stored on many workers. For all [S], the "parts" of hy can be distributed among different workers according to [V:). By taking the appropriate values S, K, and other parameters, we can ensure the lower bound in Theorem 6.1 holds.
However, Theorem 6. is only tight up to logarithmic factors because the allocation of {h is predefined. In response, we propose a construction where the functions {h₂} are allocated based on the randomness we receive from the oracles that calculate stochastic gradients in the proof of Theorem 6.2. The idea is to track the Bernoulli random variables, which zero out the last coordinates, and use them in the construction. We ensure that the workers still receive unbiased and o variance bounded stochastic gradients.
15

---

Published as a conference paper at ICLR 2025
B PROOF OF THEOREM 5.3
Theorem 5.3, Consider the assumptions and the parameters from Theorem 5.2, plus Assumption 3.1. Then Method 3 (Rennala SGD) converges after most 8 (مea seconds, where
4. min 120: Σ [V((1) (100)-V(TTRD))) V((T--1)) max {[ :1)
(To =0) Ak 2 (12)
Proof. From Theorem 5.2, know that Method converges after
24LA
iterations. The algorithm waits for S = max [c]]] 1} stochastic gradients from all the workers in
every iteration. The workers work in parallel and after seconds they guarantee to calculate
Σ LV(()))
stochastic gradients (see the discussion of the universal computation model in Section 3). means they will calculate the first 5 = max o2/=], stochastic gradients after at most
4 = min 120: Σ [V(()) 2 max {
seconds, where the min operation is well-defined due to Lemma G.I. After at most & seconds, the algorithm stops the calculations in the workers and asks them start the calculation of new batch of S stochastic gradients that will take at most
E2 = min t 0
Σ - - v.(+1) 2 max
] is the number of stochastic gradients that worker i can calculate from time 7 to time (see (5)). Using the same reasoning, it will take at most / 2224 seconds to finish all calculations.
seconds because [Vi(() Vi(T1)]
C PROOF OF THEOREM 6.4
Theorem 6.4. Consider the assumptions and the parameters from Theorem 6.3, plus Assumption 3.1. Then Method 4 (Malenia SGD) converges after most Erestel seconds, where
t min :20: (.EL [V((t) - vi(fa-1)1-1) max
20² ne 11}]
(fo 0) (19)
for all k 2
Proof. From Theorem 6.3, we know that Method converges after
24LA
the first iteration, the algorithm waits for the moment when iterations.
n S
B
Since
0 -
20²
S = max
."
n
<
max
n
16

---

Published as a conference paper at ICLR 2025
get
n
ne 2x
min
5
According to the computation model, after seconds, worker i can calculate
B; = [V[(t]
stochastic gradients meaning that
B
[V((t)
Therefore, the algorithm exits the first iteration after most
ne 22
4 min 12 0::0:
S min
[i(()]
202
min
120:
max
Vi(()]
seconds, where we use Lemma G.I.
The second iteration will start least after in seconds. Since, after / seconds, worker can calculate at least
[V((0) - V.(
stochastic gradients the second iteration. Using the same reasoning as the first iteration, the algorithm exits the second iteration after at most
1
12
1/2 = min 120:
max 2
[i(t))
vi(hi]]
ne
seconds. We can continue and show that it will take at most f 22241 seconds to finish all calculations.
D PROOF OF THEOREM 5.1
In our lower bound proofs, we employ the following well-known function. Let us define
prog(z) maxçi 0 x + 0} (xo 1).
For any N, Carmon et (2020); Arjevani et al. (2022) define function Fr R R such that
T Σ
-
((x=)))(xx.)).
(23)
where F, is the jth coordinate of a vector x E Rd and
0,
x < 1/2,
and Φ(x) = Ve 1 e dt.
(xx = exp (1
12x-1
x 2 1/2,
In the proofs, we will only use the results from the following lemma.
Lemma D.1 (Carmon al. (2020); Arjevani et (2022)). The function Fr satisfies:
1. Fr(0) inf ZERE Fr(x) < AT, where A 12.
17

---

Published as a conference paper at ICLR 2025
2. The function Fr is 11-omooth, where 1 152.
3. For all x E R?, [ Too: where 7o0 23.
4. For all x E R²,, prog V (x)) - prog(2) + 1.
5. For all x E R", if prog(2) 2) < T, then [Fr(z)]l > 1.
We are ready to prove our first main result.
Theorem 5.1. Consider Protocol 2. take computation powers {u:} such that Assumption 3. holds, and fix L, A >> O and o² 2 0 that satisfy the inequality & <, T.A. For any algorithm A E An, there exist a function f, which satisfy Assumptions 1.1, 1.2 and f(0) - S A, and stochastic gradient mappings {gi} in (9), which satisfy Assumption 1.3, i.e., Eg (9 5.t] = ff(=.) and
Eg elllgg E {,1) [8+))11 & o² for all 85 E R.d, i E [n]] such that E inf KES,
||<](>>)|| >
holds, where S. = (K No st},
= x [A1
and
Σ Vi(1) Vi(4-11) 2 x max {1
2
4= min 1 12 0:
(Lo = 0)
(11)
for all k 2 O. The quantities c', c1, and Co are universal constants. The sequences x² and th are defined in Protocol 2.
Proof.
(Part 1). In the first part of the proof we use the same idea as in (Carmon et al., 2020; Arjevani al., 2022; Tyurin & Richtárik, 2023; Huang et al., 2022; Lu & De Sa, 2021). We will construct "worst-case" function. Let us take any X > 0, T E N and take the function
LA2 FT
I
((x) =
4
We have show that satisfy Assumptions 1.1, 1.2 and f(0)
f A. Indeed,
(V/(x) -/O1=
LA
VF
Fr
y/
LA
L. 1/
vll
Ve, E ER,
4
X
where smoothhssss of Fr. (Lemma D.1). Let us take
Ah
==
L
then
LX² (0)
LX
f(0) inf ZER
f(z) =
(Fr
inf ZER"
Fr(x))
<A.
1
4
Next, construct a stochastic gradient mapping that satisfy Assumption 1.3. As in (Arjevani et al., 2022), for all e [n)) let us take
[g, = [f(()), (1+ 1 > prog(z)) (5.m (/m-1))
1)
Ve E RT.
(24)
and { are i..dd from Berouilli(p) for all E [n], where E (0, 1]. We denote [v], as the jth index of vector v E R². This mapping satisfy Assumption 1.3 since
E ()) [V]())) (1 + 1 [i > pr))(x))
[ - 11) [V[(())
p
We the standard convention min(0) oc.
18

---

Published as a conference paper at ICLR 2025
for all j [T], and
[19 (1; 6,1) [
S
max [V[(,)] _E[m]
2 E
{s (
E
27
because the difference is non-zero only in one coordinate. Therefore
[Vf(x)] (1 p)
L2X²
V FT ( 2 (1 (1p)
E (1) V
Up
22 7ec (1 p)
S 50²
Up
where we take into account Lemma D.I and choose
1,2
p = min
{ 0212
We also choose to ensure that
22l1
X
_2X² [V/('|] =
= 28 Pr ạ
V FT
for all x E RR. Using Lemma D.I, prog(x) T, then |VFr( > Thus
[ > 2=1 [prog(z) (z) < T]
(25)
Using the choice of X, one can casily show that
AL
T = 2El1 A
(26)
and
1207 0²
min
.1
(27)
The inequality (25) implies
inf \(( 25 inf 1 [prog(=*) < <T]. RES,
(28)
kES;
where fx* j Jk=o are defined in Protocol 2.
(Part 2). The last inequality in (28) says that if an algorithm wants find an ststiionaary point of the function f, then it is necessary to return point x" such that the last coordinate of x is not zero. All algorithms start with the point x0 = 0, and the only way to discover a new non-zero coordinate is through the oracles (9) since the family of algorithms Aur is zero-respecting. The function f is a zero-chain (Arjevani et al., 2022) meaning that prog( FT)))) < prog(z) + for all x E I (Lemma D. Therefore, the oracles can reveal the next non-zero coordinate with the probability due the construction (24).
For all E [mz] oracle O emulates the behavior of real computation process that calculate at most
[Vi(tt) vi(ot)]
stochastic gradients in the time interval (to, t1). Effectively, the condition Vi(t) Vi(st) 2 1 ensures that sufficient time passes before worker receives a new stochastic gradient.
All workers work in parallel and ask the oracles to return new stochastic gradients. Thus, for all t 2 0, in the interval [0, t), all workers can can calculate at most
Σ [V((t)
19

---

Published as a conference paper at ICLR 2025
stochastic gradients. At the same time, the stochastic mapping (24) is constructed that the last potentially non-zero coordinate is zeroed out using i..d. Bernoulli random variables with the parameter p. All workers have to wait for the moment when one of the oracles samples Bernoulli random variables equals to 1. Therefore, the workers have to calculate at least 7n stochastic gradients, where ?/1 is a geometric random variable with the parameter p. Finally, workers can progress to the first non-zero coordinate after at least
conclude that the
4 == inf { 120 Σ [V.00 2 min 120: Σ LVV(1) 2 m
seconds, where Lemma G.I. In order to get second non-zero coordinate, the workers should continue calculating stochastic gradients at points with the progress equals to one. Using the same reasoning, the workers progress the second non-zero coordinate after least
12 = min
120 120:
Σ [V((1) ==1
V(())) 72
seconds, where 1/2 is a geometric random variable with the parameter p. Because worker i first gets point with the progress equals one, which takes at least i seconds, and then can calculate most
[V((t) Vi(t1)]
stochastic gradients by time / 2 O. We continue: let define
t. = min
t 0
Σ
(v((t) - Vi(++11) Th
(to = 0),
and take i..d. {m T= geometric random variables with the probability p. We can conclude that all algorithms from Arr require least fr seconds get a point where the Th coordinate non-zero. (Part 3).
is left to find concentration bound for ty. Using Lemma G.2 with we have
p for all i [T],
T
F
Σ
5
log 6
4p
for all 5 (0, 1] (Note: Clearly, Lemma G.2 too redundant for the current case when (m)) are i.i.d,, but we will use the lemma in other proof where the generality is justified). Since
T + log
T-1 1
2
2
With a probability at least 1/2, there exist
T-1 indices such that 1 >
1 i.e.
4p
{ i
T-1
[T]
17.
>
4p
With a probability at least 1/2, there exist
I j1 < j2 < ...
$1
S such that Bis >
for
4p
all k E [[===]]
]] Using proof by induction, let us show that
1
f 2 to min 120:
vi((t) - (s(to-1)
(to = 0)
(29)
4p
for all k
-|-
Recall the definition of 1n- Using it, we have
1/ = min
t t Σ
Vi(t) V.(t,, 2 2mh
i=1
20

---

Published as a conference paper at ICLR 2025
Using v1( 0 and Mh 2 1 4p
we get
[i(1 2
Vi(t) - V.(t,- My 2 4p
and
1
f/ 21 min
t t 0
Vi(t)] N
4p
Thus, have proved the base case. Assume that (29) holds for k- 1. Note that
f/ min t 0 Vi(t) V. ()] nin
Using Tii 2 1p: f1 2 k) the induction assumption ()(-1) 2 Lk-11 and the fact that the
functions (V/) are non-decreasing, we get
2 Vi(tia-1) 2 Vi(ti(a-u) ) Vi(ta-1)
and
Vi(1) - V.(4+111 2 Σ [V((1) --:( -1] 2 Mhu 2
1
4p
Therefore
n
1
1/ 4
120:
Vi(t) Vi(Le- 1) 2
4p
In total, with probability at least 1/2, due to (26) and (27), we have
tr 2 ابجرار 2 ببج 2 4 [ax الهي
where
{| 2
1 |1}
t. = min t 0:
Σ vi(tt Vi 2 x max
(to = 0)
(30)
and C₁, 02 are universal constants. Recall that br is necessary number of seconds to get a point where the Th coordinate is non-zero. Due to (28),
IE
inf SE
> 2&P (tr t) 2 2&P tr 2 ([xx ( 2e
for
t [cxxx 4
The first inequality follows from the fact that if (T 1, then the set S, = {k: No 1c < { contains the indices of iterations from Protocol 2 where all returned by the algorithm points have prog(-) less than T.
E PROOF OF THEOREM 6.
Theorem 6.1. Consider Protocol 2. We take computation powers {v;} such that Assumption 3.1 holds, and fix L, A, 0 and o² > 0 that satisfy the inequality < C.A.A For any algorithm A E Aus there exist functions {fr)z= where the function f= 1 Et f. satisfies Assumptions 1.1, 1.2 and f(0) f < A, and stochastic gradient mappings {9;
t=1 {=i in (9), which satisfy Assumption 1.4, i.e.
21

---

Published as a conference paper at ICLR 2025
2g [gi(5zi (s2) and Es(llg(saiE..t) - V I o² for all Be E ER, [n], and
for
t 2 O, such that E[ inf
[f((=>)] > holds, where St = { E No 1t st).
kES.
24
lug
and
1
44 := -mini 1200
1 - Li=1
C3
log
2 max
62
(17)
for all 2 1 (to = 0). The quantities d', C1, c22 and 03 are universal constants. The sequences x and th are defined in Protocol 2.
Proof. As in Theorem 5.1, we base our proof on the function (x) from Section D. Let us fix any algorithm Azr First, define S N functions such that, for all j [S], we have hz(z) R + R and
nLX² (x(2)
FT
Ij
(31)
1
where T, S, and À are defined later. We assume that x as the jth block of a vector x [.i,..., Øg] RSXT
[30,, Jsl E RST We define x; E IR? The function hy depends only on a subset of variables z, from æ. We construct a function f RSX + such that
f(x)
n Σ
h()).
(32)
While the final structure of the local stochastic functions fi is not yet defined, during the proof, we will ensure that (32) holds.
(Step Fa,L) First, show that f satisfies Assumptions 1.1, 1.2 and f(0) < A. Let show that the function is L-smooth. Indeed, we have
S
2
9
[ - V
Vh,
Vh+(r))
=
Vh₂(2)
Vh((2)12
nT
n²
S
1
Fj
aL>
y/i X
V
FT
V
Fr
n
h
4
where I1-11, is the Euclidean norm w.r.t jth block. Then,
[V/(x) - 2 2²x²
S
FT
VT
11
11
2
S
1,2
5
|
3il1 = 122 || -y1
Fi
1=1
where the last inequality due to Lemma D.1. Let us take
Ah
T
(33)
LX
then
1 $
22
< LX
f(0)
inf x
f(x)
(FT (0)
inf FT(x))
<A.
ZER?
i=1
where the first inequality due to Lemma D.I.
22

---

Published as a conference paper at ICLR 2025
(Step 2: Construction of local functions fi) Each function (x) depends only on T coordinates of the 7th block. We split these T coordinates into T 1 groups with T = [T/K], where choose K later. For all [T + 1], let take any
S 1 S Sw,1 S .... S Sw,n-1 S Sw,n = 5 1.
(34)
is convenient to define the length of each segment: ann, == Sunt (w.(f-1) for all w E [T+ 1] and
i [n]. Also, we take any times
to = 0 S S ... 1tp S 1 =
(35)
associated with the coordinates' groups. We construct functions in the following way. For all E [n], we define
81.-1
[((x): = (-V(1)((33))+
Σ j=S1((1-1)
-2.-1
+...
j= 1=
+ V -
+...
17,-1
(V -aa +...
j (=
+ V -
7411-1
Σ
-
(=
V(--,,,T-)) |b -
and
f((x) nLA2
where Zjz the 7th coordinate of αz E I.T"
Let us explain the idea. For all E [S), we take the function hú from (31), which consists of T parts with the structure V )0(
- (r),)) (x and distribute these parts between the workers according to the predefined segments {sw,s). The first K parts of the function h, will be stored worker i such that $1, J < $1.1, the second K parts will be stored in worker is
such that (2,-121)) S < 82.12: and on. One can easily show that Ej= hi Ei= Si.
(Step 3: Time-dependent stochastic oracles)
We now construct a stochastic oracle. Let us take
am n
22
2
Pwoi min
(36)
σ 2213
for all w E [ 1], E [n). The stochastic mapping takes a point x, random variable &, a time f, and returns
[g, E, f1 := [
prog(a,) A m - +1 +1=
w(e)] +1=w(e]
Eym
15mm-1)) Vx E RST
(37)
++1
K
Pro(e),s
where [x] is the th coordinate of the jth block of R8XT, tEmmbim are i.idd from (ernoull(ppu(t).)) and wt)) [T' is the index such that (()(()-1) St tw(()-
The idea is almost the same as (Arjevani et al., 2022): we also zero out the last potentially non zero coordinate with the probability Pu((),- However, we only zero out coordinate if it belongs the
23

---

Published as a conference paper at ICLR 2025
parts from the set {(K - (t) + 1..... Kw(t)), where w(t) is associated with the current time interval (1):(())):: fa((t) where the current time belongs to.
( (
- 1)] = 0 and
Then, (1; 1) is unbiased because E&g
Sw(ta-11
T2
FT (2) 12 (1 Pw(t)
Eg [1) V((())
x
Σ
PPP(())))
because, due the condition
+ w(l), we only consider the blocks from the sum
Ej -
Using Lemma D.I, we have V/ (x)]l I ree for all IR and
Amo(t), 2 (1- Pan(t),)) 0²
Eg (19)(
[
where the last inequality follows from the choice of Purs in (36).
(Step 4: Analysis of Protocol)
Using the definition of f, we get
[h,
Σ 2
FFT Ez
|
n²
2
8
1 [prog (I,) < <
(38)
for all x (.i,.... Fn] E R In the last inequality, Lemma D.I. Let us take
4al2
A
(39)
I
ensure that
8
48 S
4E
inf LES:
||v
inf RES.
(prog(zz)) < <T) 2
Σ
inf (roog(a)) < 7], (40)
S
S
kES,
==1
where x are points defined in Protocol 2. Using Markov's inequality, we get
inf 1 (prog())) < < kES,
P
inf 1l [prog(x;)) < <7 -
8
keS,
(41)
P
sup 1 [prog(())) 17
1=1 ke9,
2
< 2E
sup 1 prog (2)) keS,
2 T
E sup [prog(= T
kES.
(Step 5: Bound on the expectations)
In this step of the proof, we fix j E [S], and consider the function hy from (31).
Recall that worker can calculate [V((t)] stochastic gradients time t. Therefore, it takes at least
min ft 2 [Vi(t) 2 n) 2 (n)
seconds calculate 7) N stochastic gradients, where the definition (8).
24

---

Published as a conference paper at ICLR 2025
By the construction of the functions {ft), the first K parts of hy belong worker d1,j such that $1,61,,- -1 $1,11., While the algorithm A is returning times t such that to = 0 S t < fg by the construction of the stochastic mapping (37), whenever the algorithm calls oracle Os,,, the oracle zeros out the last potentially non-zero coordinate with the probability P1,i,,;" However, due to the condition m== + w(t), the stochastic mapping will zero out the first coordinates only t 4. Thus, the time required to progress to the R coordinate in the block I, is at least
K
4 = min E1, Van
Σ
seconds, where (m......) } are i.i.d. geometric random variables with the probability P1, Because either the algorithm returns th 2 f1, or it keeps returning t < f, but then A should calculate at least v=1 ,.. stochastic gradients since the stochastic mapping zeros out the last potentially non-zero coordinate, and should wait times for the "lucky" (E = 1) draws of Bernoulli random variables.
Using the same reasoning, for all w E [T], it will take at least
K
Tho + Vinis (o ((o-raa)
t = min Ess Fi
(fo. = 0)
(42)
seconds to progress to the X th coordinate in the block Zj, where ( } are i..d. geo- metric random variables with the probability Pw.i.g:: and f..j is the index the worker such that $w -1 S < Sw,f... Because either the algorithm returns t 2 twr or keeps returning th < fwo but then A should first progress to the (w 1) x thhh coordinate, which takes at least 6w-1. seconds,
and then should calculate at least Σ K ==1 Mar,iu..y.o stochastic gradients. This will take at least
K
min 12 0
[Vim. (t) Vin.s (fw-11))
(cont. of Vinas) min 1200 0 Vi (1) Vieis -1g)
V-1 kund
Vini, (fw)
seconds.
Using Lemma G.3, with a probability at least - -e----- K/2, we have
K
g 2
8p
for all w E (T). Using these inequalities and (42), we get
f 2 min
Ewe Vinl
+ Vinig
(43)
8p
for all w [T).
Note that (Fw
17 1m sw.i we +))i(()) and S are free parameters with the conditions (34) and (35). Due to (36) and (39), we have
Puri = min 4e42 am,
52
Therefore, we can use Lemma G.4: we can find (twr 18
- wee.::eee())) and S such that
V. (
K 8ps.: ) 2 & for all i E [n]. With a probability at least Te- K/2 with the chosen parameters,
we have
K
min (4,4) h }
f 2 min h, Vin
8pi.in,
25

---

Published as a conference paper at ICLR 2025
Using proof by induction, with probability least 1 - Te-ky2, let us prove that fw.j tw for all E (T) with the parameters from Lemma G.4. The base case has been proved. Assume that
tw-11 1jj 2 1m-1,
then, using (43), we get
fw.j 2 min Ew Vinis ( 8p
K
+ Viw,, (fo-2)) (
min tw. Viuls (
K 8p
+ Viwis (fw-1)
In Lemma G.4, we show that V;²
K_ + Vi(tw-1)) 2 tu for all i E [n]. Thus
Eu min prrm Eur = =
(Step Choose a parameter K)
In the previous step. we prove that, with a probability at least 1 - Te-K/2, the algorithm requires at least b seconds progress to the K Thh coordinate (K x T T), where by defined in in the proof of Lemma G.4.
Let us take
K = [2 log 47',
then, with a probability least 3/4, the algorithm will require at least Ey seconds to get non-zero last coordinate in the block æ.-- Thus
1 4
E
sup KEE
1 (prog(z)) 2 m1
for j [n]] and for s 1T. substitute these inequalities to (41) and (40), and get
46
1
P
inf (prog(a;)) < <T) - 25
$ 2
kES:
and
8
inf kes.
[f(()))
E
4s
inf 1 (prog(a7)) <T]
> 2&P
4s Σ
inf KES.
1 (prog(x)))
< <T]
> 25
2x 2E
S
kes;
S
L=
im
for all
1
(60)
1
t 5
t
2 bq
2
where
T
(33),
Ci x LA
T
2 log 4T
log
LA
for some universal constant where we use the assumption < è' LA of the theorem. Finally, since Typ 2 L. for all w E [7] with the chosen K, where the later sequence is defined in (17), we can take
t
2
F PROOF OF THEOREM 6.2
Theorem 6.2. Consider Protocol 2. We take computation powers {v,} such that Assumption 3.1 holds, and fix L, A, > and x² 2 that satisfy the inequality E < LA. For any algorithm A E Aur sample {fs = from some distribution of functions, where the function Eh
26

---

Published as a conference paper at ICLR 2025
satisfies Assumptions 1.1, 1.2 and f(0) f v A deterministically, and there exist stochastic gradient mappings {gili=1 in (9), which satisfy Assumption 1.4, i.e. Eg (sx E, t)] = fs(=s)
and (s {, Vf((s=)l11 I o² for all
R [n], and t 2 0, such that
inf [[]{{>]]|] > e holds", where St = {k Nolt sth. KES,
24 20 12 1
and
:=:= min 120:: (+E Cs (V) Vi(t, 1)))=
2 max for d² ne 11} (18)
for all k 2 (to = 0). The quantities c', C12 C22 and are universal constants. The sequences x² and th are defined in Protocol 2.
Proof. We base proof on the function (2) from Section D. Let fix any algorithm A E Aa- First, we define S E functions such that, for all j E [S], we have h,(x) RSx + R and
nL>² h
h₂(x)
Fr
(44)
where T, S, and À defined later. We assume that 1x1 ................................ Jsl RST We define zj E I as the jth block of vector .F.....,E5) RSXT The function h2 depends only on subset of variables zj from x. We construct function RSxT + such that
S
f(x) = Σ (()).
(45)
While the final structure of the local stochastic functions ʃi is not yet defined, during the proof, we will ensure that (45) holds.
(Step 1: f e FA.L)
have to show that f satisfies Assumptions 1.1, 1.2 and f(0) - f < A. This step is exactly the same in the proof of Theorem 6.1. It is sufficient take
Ah
T=
(46)
LXPSA
(Step Construction of local functions fi and stochastic mappings) Unlike the proof of Theorem 6.1 where the functions are predetermined, in this construction the functions } depend on sequences random variables and are constructed algorithmically in the following way.
For all w E [T'+ + 1], let us take any
Sw.0 = < sw,1 S ... S Sw,n-1 Swn, S 1,
.....
(47)
and define aw,y == Sw,s (w.(i-1). We also take any Puri for all w E [T], á [n], and any times
to =0 5 ... < Tr < [ x
(48)
associated with (we(T+)) and (Pw., Jwe(T]- We construct the functions (f.) using the algorithm below.
We take the expectation all randomness.
27

---

Published as a conference paper at ICLR 2025
Algorithm 5 "Resisting allocation" of the functions {hş}
1: fx)) f- for all [rx] for j L...... S do
2:
3: Current time window w: =
4:
for = . do
5:
Find iu such that Swoiing-1 Sj < Swskm.
6:
Set bj.m (w, bm:.)
7:
Update fin., + fin (x) + nLd? ii (v (- - (15,0 = 0 for all E [S)
(-
V
(Simm))
Fiam
8:
Draw an infinite i.i.d. sequence (fj.m.s).o s==1 Find the first moment when E,,,, 1, I.c., Ti. inf(s 2 1 Ej.m, 1}
100, from Bernouli((p::sw.))
9:
10:
if Vi (Ni. Vi (fw-1)) tu then
11: w w +1
12: end if
13: end for
14:
end for
As in the proof Theorem 6.1, the stochastic mapping takes a point æ; a random variable č, time f, and returns
f(()))j [+(())lim
Puita. m = prog(n,) 1A by.m = (w) d),
(49)
otherwise,
where (zliam is the th coordinate of the jth block of æ E RSXT , < (EI.... ........ss,, &s is the "next" 100 (see Alg. 5), and w(l) E [T] the index such that
random variable from ( ((w(0)1) S Tw(e)-
Let us clarify what we mean by the "next" random variable. In Line 8 of Alg. 5, we draw an infinite ii.d. sequence ) from Bernouli(pw.h...) For the first time when the mapping &i has to take the "next" random variable from { (p)g(() Jec it takes (1 For the second time, it takes (j.(pmg(ss)++))) and so forth.
100
For all E [n]. the mapping Is in the oracle O, zeroes out the coordinate m of the gradient V (x) corresponding
prog(z;)) (Ix) (idea is the same in (Arjevani al., 2022)). However, only zero out this coordinate if the corresponding part of the function hy is stored on worker i at the time (condition bj.m (t)(t)
We now explain the idea. For all E [n], deterministically. we have
nLA
$1,4
1(x))
Σ
-VD()
1
1=
where Fj. is the 4hh coordinate of xy E IRT. Thus, the first part (V(1)((z1) of the functions (44) (see (23)) are allocated according the values {s1,))
As always, we rely on the fact that the algorithm is zero-resse respeeespg,,,gg, meaning that at the beginning, it starts with the point d0 0. While - = 0, it does not matter where we allocate the other parts the functions hy. The main idea is to decide the allocation based on the random variables (S.m,, from Alg. By the construction of the functions {ft), the first part of h, belongs to worker i1,) such that 8 $1,6 S < 81.11, The oracle On,, zeroes out the first coordinate the j block of gradients with the probability P1,i., (see (49)).
In Alg, 5, we consider two cases: If Vir, (my.) E1, then in the next iteration of Alg. 5, allocate the second part of the function h, to the same worker (ikk, i1.j i.c.
(x) + (x) 11
nLA²
(w(-2x))
(- Φ
I4.2
-4.1
122
2
A
28

---

Published as a conference paper at ICLR 2025
Otherwise, if Vi, (17.1) 2 81, then increment the parameter in Alg. 5 and allocate the second part worker 82.j
nLA² (2) t fiz. (1) +
(v
35,1
422 A
J
)²
Φ
V
1
A
where f2, such that $2,6, j $2,$2.1
The mapping Ii is unbiased and variinnnc bounded. If m >> prog(z)) + 1, then [Vf((z))am = deterministically due to Lemma D.1. If m prog( (z)(z)) and by.m (w(t), 2). then we have to show that
&
Eg
[i((z))im
Pwit),
for all E [S], m (T). Notice that due the construction in Alg. 5, the gradient fa can depend on a since the random variables affect the allocation of parts starting from
V
A y
Fjm++
(-
Jjm++
[2
V
(50)
23
- F3T (-xx² V
FJTT-1
V
X
A
However, i) the jth block does no depend on Eyr,meeer with + j. m' E [T], 2 1 ii) all the previous parts in the jth block depend only on (s =mm and iii) all the parts from (50) are zero because m prog(x,) + 1. Therefore
E i Eg Pw((),
E
Eg [Vf(()) x
[Ff(())
Pio(A). E
[i(())) Be,
(Po(t))
For m pprog(z;) + and bj.m # (wo(t,,), we have
Bg [l.. : E, ).mmmm]= Egg ([V)())))) Eg [V i)) mi For prog(1;))
[((())]j..
have
Eg (=; 1. = Using the same reasoning, we have
2 Eg, [V)(())
fz(z)) (x)1
Eg - -
----1
E,
Eg
Σ
(IV (z))mm))
Per(t),
j.m by.m (t)) m- cammpoog(220 px) (+))+1
- (1-1) 27
E
Σ
([V((())) )2 Eg Pin(t)
j.m: by (((())) m=prog(2,)+1
(1 Pw(())s)
Σ
([V((()))
Piott,
j.m: j.m:bym (w((),), m=progee,)+
Σ
([VF ( (2))
2 n222222 (1 ---P(())))
17Pmn(t,,
j.m: by (w))).))
m=ppg(xr)++
29

---

Published as a conference paper at ICLR 2025
Due to Lemma D.I, get [/Fr (z)]l I 2 for all R and
n² L2 x2 (1 Pmoti,a)
J.m == (w))), m pm)
Ow(t), 1,2 1,222 180 (1 Pw(t))s)
because, due the condition 6j. (w)t), i), we only consider the blocks from the (I): Sw((), - 1} (see Alg. 5), take one coordinate from each block, and recall that aw(t), Su((), (w(t),(i-1)- Using the choice
1 700
Por min
(51)
0217
for all [T], [n], get
Eg - 5
(Step 3: Analysis of Protocol) Mirroring the proof of Theorem 6.1, using
4el?
A
(52)
L2S
one can show
inf RES,
\
||
45
Σ
inf kES:
1 [prog(=;) 2].
(53)
5
where r² are points defined in Protocol 2, and
4
2
P
E
inf KES.
[(prog(at)
< 7 S 2a
E
sup 1 [prog(2))) > 27
(54)
S
kES,
(Step 4: Bound on the expectations)
The time required progress (get a non-zero value) the 1th coordinate in the block x, is at least
min 1, Ki.g (1..))
seconds, where Vi= is defined in (8) and 77.1 is a geometric random variable with the probability P1.i..: Because, due the condition by. = (1, = (w(t), i), the mapping (49) zeroes out the first coordinate only if the algorithm returns 1 < E1 and it,j i. Therefore, either the algorithm returns t > i and (49) does not zero out the coordinate of gradients, or it keeps returning th < [1 but then should calculate at least 77.1 stochastic gradients in worker i1,, since the stochastic mapping zeros out the potentially non-zero coordinate in (49).
Recall that the "resisting" allocator (Alg. 5) tracks the random variable Vjj. Opt. V (7,,1) < &,, then Alg. 5 allocates the second part of the function hy to the same worker f1.j, meaning that the time required to progress (get non-zero value) to the 2th coordinate in the block vy is at least
min F1. V.n. (1g.1 + (22) 2 min {T, V... (1h22)
seconds, where 722 is geometric random variable with the probability P1. Opt. 2: If V-1 (mg.) L1 then allocate the second part worker i2.j, where iz,j such that
30

---

Published as a conference paper at ICLR 2025
-1, Sj $1.22.5 meaning that the time required to progress (get non-zero value) to the 2 coordinate in the block 2 is at least
12, 12.5 (1/.2 + (i,,((t))
seconds, where 73. is a geometric random variable with the probability p2, because either the algorithm returns 1 2 l2, or it keeps returning e* < l2, but then A should first progress to the 1 coordinate, which takes at least & seconds, and then should calculate least 7/.2 stochastic gradients. This will take at least
min { 1200: [Vi,, (t) - Vi2,, (fi)] 2 nj.2]
(cont. Vez,g min {t 2 Vi2,, (1) Via., (11) = T1j22
12.3 (1122 V22., (f2)
seconds. Notice that the parameter of the geometric random variable 7/5,2 depends on the previous randomness.
In the case Opt. 1, we can only conclude that the algorithm will require at least to = seconds to get non-zero value in the Th coordinate. In the case Opt. 2, we have better guarantees and can infer that the algorithm will require at least [ 2 l seconds to get non-zero value in the 7 coordinate because the inequality V (1g,1) I1 holds. Hence, the condition in Line 10 of Alg. determines a necessary time to get the Th with non-zero value.
For all [m]. have the following Markov process that generalizes previous discussion.
Algorithm 6 Markov process in the j"h block
1: Current time window Wm =
2:
for m ,,..., do
3: Find he such that Swm. -1 S j < Swmpimm o
4: Draw infinite i.i.d. sequence {fj.m, 100 from Bernoullipp Prom Smmes
5:
Find the first moment when Ej.m. 1, i.e., Ti.m inf Ejmm,
6:
if V. (75.m + Viwn (fwm -1)) 2 tum then
7:
Wm+11 f- Wm +1
8: else
9:
Wm++1 f- Wm
10: end if
11:
end for
12:
Return: 1(WT-1) is necessary time to get the 7th non-zero coordinate the jth block
The provided random Markov process determines the time E(wy-1) required to get the 7 non-zero coordinate in the j block.
For all [m]) m E [T), Vi. has the geometric distribution with the parameter Poem Ss which depends only on the previous random variables 17.,,,... -- Therefore, we can use Lemma G.2 and get
T
S T + log 6 <
PP
Σ
7j.m
4pwm
for (0, 1]. The last inequality means that with probability at least 3/4, there exist S my < m2 < ... < T < T such that
Mj.ma
(55)
4pwmm dome
Speting Swing
for all & [[T>2]]
31

---

Published as a conference paper at ICLR 2025
Due to (51) and (52), have
4 un
Pwù == min
02S
Recall that (Tw ( (sm,)) weelT+ (el( and are free parameters with the only conditions (47) and (48). Therefore, we can use Lemma G.4 with K 1 and ensure that there exist parameters such that
Vi(lw---) (
V (ppn.
Eyp.
for all w [T], E [n]. Putting the last inequality, (55), and Line of Alg. together, we can conclude that, with probability at least 8/4, the value of wT 1 is greater equal to T-2 since the condition in Line 6 of Alg. will hold at least _ times.
(Step 5: Endgame) In the previous step, we prove that, with a probability at least 3/4, the algorithm requires at least f T- seconds to progress the thh coordinate of the 7th block, where Ep is defined in the proof of Lemma G.4.
Thus
1
F
sup S.
1
[prog m1
for all j E [n]] and for all S _
2-2
We substitute these inequalities to (54) and (53), and get
46
1 2
P
inf (prog(x;)) < <T - 2$ kES:
and
s
inf kES.
[13]
E
45
inf 1 (prog(a))) <T]
> 2&P
45
Σ
inf [prog(a.) < <T) > KES,
28
26
S
kES,
5 1=1
1=1
for all
(60)
t 2
t
Using the assumption E < d'LA of the theorem, (46), and (52), we get
T - 2
LA
C1 x
E
for some universal constant C1.
Finally, since E., 2 tw for all E [T', where the later sequence is defined in (18), can take
2 1 1
G AUXILIARY LEMMAS
Lemma G.1. Let V1 ET - RT is continuous and non-decreasing function for all i [n]. For all n, bi...., bn E R2,00 the minimums of the sets
t t20: Σ Vi(t) b,l 21
32

---

Published as a conference paper at ICLR 2025
and
1 n
-1
120:
21
Vi(t)
bil
exist, considering the convention min(0) oo.
Proof. We now focus on the first set. If the set is empty, then the minimum is oo by the convention. Otherwise, let define
L := inf
120:
Σ
[i(1)
b.j 2
< 00.
==1
the minimum does not exist, then
vi(()) b:j <.
For all E [ro], the functions V; is continuous and non-decreasing meaning that there exists 6; > 0 such that
[V((t) 6,] [Vi + b.j.
for all 0 S.a 8 S 6; Let us take 8 = min 8; >>> 0, then
<<(r)
Σ
ViL+ 8) b:
Vi( - b: <
This contradicts the fact that is the infimum. The reasoning for the second set is the same.
Lemma G.2. Let 2 1 and {m 1 are geometric random variables such that given mi..... 77s-1 Ni Geometric Scometric(Pt.m...... mp..........)) and the probability Pi.......h-. E (0, depends only ....... T/--1
for all E [T]. Then
P
1K
< + log 2
<8
4pt.m M
f=1
for all d E (0,1). 1].
Proof. Let us consider the simplified notation ps = Pi.m..... and take any T, > 0. Using Chernoff's method, we get
1
1
P
1
ST
P
1i
sT
4p;
4p;
Σr
1n:>
4pc
(56)
Tf
11
1: 4p1
111
7
where we the definition of conditional expectation.
For all E [T]. we now consider the 7th expectation separately:
x1
e
M/-1
1
11.
171 1.....7-11
11
71
7h-1
4p
4p;
33

---

Published as a conference paper at ICLR 2025
1 App
(1 - +)
" S
...... 7h-1 + t
Due the assumption of our theorem, given ........ 11 77s is geometric random variable with the parameter = P........... Therefore
E
81 m> Tp.
71
7/-
(1 -)
(1 1
pi) क,द + te,
where (1 pi)
Apc if p;
and
0. Since 1 1-1 (1-p)15) S s for p (0.1]
Aps
and S 2 0, get
E
11 4p4
m 77-1
$ (1-E ->ppp)
t
4pi
Σ (1 - E ))p x
- = -(1- t
4p;
Let us take then
E
9:
Apl
M
nh-
s (1 - -1-) (1 -1/2
We substitute the last inequality and the chosen value of 8 to (56) and get
P
m
1
T
S c
4p
For all (0, 1], we can take
T
T=
+ log
to ensure that
T
T I
P
1
>
+
log 5
6.
4p:
2
Lemma G.3. Let m......,, M.KK Geometric(pt): 92,1...., 12,K Geometric(ps),
1........ 2I, ~ Geometric(pp) are mutually independent geometric random variables. Then
K
})
K
P
U kE[T
Σ
The
S
< <Te-KK
K/2
8pk
Proof. Let us fix any av 2 for & E [T]. Using the union bound, we get
K S an |
U
Ma.j
IP
Ma.. S ag
(57)
kE[T]
A=1
For all E (7] and > 0, we obtain the following series of inequalities:
K
K
P
Thet S
=
P
mk 2 - sak
= P
EKK aid 2 e -sah
==1
/=1
34

---

Published as a conference paper at ICLR 2025
S < -
EEzz mk.) me.
where we use Markov's 's inequality. Since the random variables are mutually independent, we have
K
IP
Σ Me S ag
c (E [e(c))))))
mml1])
c
Pk
ppk)
where we use the moment-gent geenertggnn function of the geometric random variables. Since pa. 2 0 and e 1 for all I,, get
K
P
ma.
S
ax
00
(
Let us take 8 = 4pp to ensure that
K
S4ppas-R K
M S ax
j=1
We can take ag
K 8pz
to get
K
K
P
ake
S
Se- K/2
8pk
It is left to substitute the last inequality to (57).
Lemma G.4. For all T K E N, there exist non negative parameters (fw) and S E N such that
1.
S E1 8w,1 S ... S 8w,n-1 S 8w. =S+1
Vi E [T + 1],
(58)
io 0 < T1 S $ 4 l++1 = co.
2.
V-- + Vi(tu-1)) 2 2
(59)
8p
for all w E [T], i E [n],
3.
n
2
Ew 2 Ew = min
120:
2 max
TTo = 0)
(1) (((fm-1))
32 en
(60)
for all w E [T],
where
4 aw
Purk == min
(61)
g2S
aw,d = Sw.i
(1) and E, 22. are arbitrarily non constants.
We have the free parameters (Tvr tion
Proof.
and S E N with the only condi-
0m,00 Sw.1 ... Sw,n-1 5 Sw,n S
Vw [ + 1].
(62)
to = 0 < f < ... 2 < 1 = co.
35

---

Published as a conference paper at ICLR 2025
We now choose values of these parameters to ensure that (59) holds. Instead of {sw,ah will work with {aw,sh ,, then one can restore {sw,i) using the definition Ow,i == Sw.s sw,(i-1) We have to ensure that
Σ
Owii S
(63)
holds for w E [T + 1] to get (62). It sufficient validate that
Pws 8(Vi(tw) - Vi(
(to = 0)
w [T] to guarantee that
K
Vi
+ Vi(fuo-1) Fu
8p
for all w [T). Due to (61), it is sufficient to find (www) (1w), and S such that (63) holds and
a mm
4
min
S
(63)
K ((V(
min
(64)
Limi ,0,
(f(
for all E [n] and for all w E [7].
Assume that - defined (lo 0), and let us now consider w (7]. Let us define
K (f((w-))
w = max V
+
(65)
JEIn|
16
and
Ko²
2 min
t 12 0:
Σ
64 6
(66)
n2 (Vi Vi(
==
Opt. 1: If > En then we take En = iy aw,s = 0 for all + jr, and aw.j = 1, where
K
jr arg max Vi-
+ v2((w-1))
(67)
JE[n!
16
Opt. 2: P. S Py then we take an = Py, and?
max
{ ([w) - v((Tw-1)3
iE(n)
0u,i
(68)
Vi (fw) Vi(Fuo-1)
for all E [n]- For T + 1, take ā 0 for all i 1, and 0w,1 1.
We choose the following S:
S = max we wE(T+]]
Σ Twee
and for all w Arg max [+1] i= aw.s), we take aw,s == aw,s Let us take any such that
72
Eim awos S, then, for all w [T 1]. there exists the smallest kw 2 2 that yields
Σ kww x awii 2 S.
V6, (F.)) > v1(Fw-1) for all [n] since Ene 2 El and Vi(FFo) K V.(F.--) for all i E [m], due to (65)
and the definition
36

---

Published as a conference paper at ICLR 2025
Opt. 1: E. p. then take awy' == kw aw. kww and Awo = kw Ow,t for all 8 8 jr (j" from (67)) to ensure that ii=1 aws =
Opt. 2: If I t there exist Two, E {0,.... Dwi that if we take
Orei (kiw 1) x Ouri + Twis
then we guarantee the equality Ei= Omri = S.
It is left ensure that (64) holds.
Opt. 1: If 2e M. then (64) holds since
mu 4 Lim1 0n 1 =0 Vi
min
and
K for = j",
min
51< 8(Vi(tw) Vi(fw
Li=1
am,
where the last inequality due to the definition (8) and the choice of f.p
K
Vg-
+ Vi-((Tu-
(Iw-t
16
Opt. 2: F I Pyy then (64) holds since
Owii
< 2 aw..
S (Niw 1) Ei= aw,
E awn
2i=1 0w
because kw 2 2. Using (68) and
2 [x] > E for all 2 1, we get
awo Ei= deg
Ve(ton) Vi(bu-1]
(66)
Ko²
64m2e (V: (tw) Vi(fw-1))
Vi(t.. Vilk 1)
The last inequality ensures that (64) holds. In total, we have T. = max (7,, Pa..
is left prove (60). Let us define
1
f. = min
t 0
max 32
(fo = 0).
16(V - Vi 1))
(69)
We know that to = < to = O. Using a proof by induction and assuming Tw-1 S Im- we have
T, min
2 max jEin]
V
(
16
K
vz((u--))
n
(6(V fi
1
max
32 en
0²
K
min
max V
K
+ Vy vi(Cu-1)
1
1
min
32 En o²
JE
16
16(V V.(lm-
because if
2 max 3272.e' }. ,then, necessarily, 16(V, (1)
10( (1000)-V,,, C. 11)
Vi(tn--1)) 2 K for all E [n). Then
7n min {
12
max V--1 sE[n]
+ V2((n=1))
3272 2
en
16
16( V, TT 1))
o²
K
37

---

Published as a conference paper at ICLR 2025
because Σ
I for all t max V (16 + vi((w-1))
Further
-o1 12
jEIn|
R
tw S min
t 2 max JE(m|
v
K
v2((u-1))
1
1
16
71
16(V (i(fw-1))
o²
K
n
σ²
S min
t max V jEInl
+ (j((u-1)
Σ
S 64
16
n
2
%00
V.(Tw-1))
because Ew-1 S tw {Vi} are non-decreasing, and
[x]
2hz for all 1. Then
Tu S min
1 max jE(n)
V
(16
K Vi(lm-1))
+
Ko²
S 664
maxx(T (T [2 I..
16
2 vi(fw-1))
due to the definitions (65), (66) of L 72
wi and tw-
Lemma G.5. (Tyurin et al., 2024a) (S24tion Section K] Consider a sequence 0o > 01 2 2 Un and fix
some S > O. For all j [n], define
g(i)
Σ
1/
(8 5).
Let Frax be the largest index such that min ((tو g Fmmax) For Fmax n, we have
jEin]
min
g(i)
jE(n]
Viioa +1)
2. Let j" be any index such that min g(j) g(i*). ). For jr < n, we have
je(m
1
min g(i) <
jE(n|
v(+++1)
3. Let Juin be the smallest index such that min ((j) = g. Then
jE(m]
min g(i).
U/a
jE
4. Let j be any index such that min g(j) g(j") ) Then
3c(m
< min g()).
0z-
jEin]
H CONVEX SETTING
In the convex setting, the time complexities do not change significantly in conceptual sense compared to the nonconvex case. Therefore, we will provide a somewhat less detailed description in this section. The obtained time complexities also hinge the sequences (12) and (19). The only difference is the number of iterations that the methods do in each particular setup.
Using the same reasoning in other sections and (Tyurin & Richtárik, 2023)nS B], conjecture that the following results are optimal up to constant factors. It is sufficient to use an appropriate "difficult" function (Guzmán & Nemirovski, 2015; Nesterov, 2018; Woodworth et al., 2018 8) designed for the convex domain instead of (23).
We the following assumptions:
38

---

Published as a conference paper at ICLR 2025
Assumption H.1. The function is convex and attains minimum at point x" R
Assumption H.2. The function f is M --Lisschitz, i..,
If(x) - f(v)l - M I| yll. Vz, y E R
for some M E oo].
Assumption H.3 (Homogeneous setup). For all [n], worker can only calculate V (f E). For all Rd, stochastic (sub)gradients V fx; {) are unbiased and are o--varrance-bouunde, i.e..
Eg (v;;); E)] (z) and Egg
[ Eg [f(x;)
where o² 2 0.
Assumption H.4 (Heterogeneous setup). For all E [n], worker can only calculate (z; For all E IR e [n] stochastic (sub)gradients [z; E,) are unbiased and are ve-variance-boundee,
i.., Eg, (x;&( (z) and Eg, (V, - Es, [Vf EJIl S o², where x² 2 0.
We consider four cases.
H.1 HOMOGENEOUS SETUP AND NONSMOOTH CASE
Theorem H.5. [(Tyurin & Richtárik, 2023) Let Assumptions H.1, H.2 and H.3 hold. Choose any & > O. Let us take the batch size S = max ([o2/M²] stepsize MM+0*TS E 22T2: N²
Method Then after K 2M R²/2" iterations the method guarantees E [[ - f(x)) S, where K
K Ekzo xt and R I| - -
Theorem H.6. Consider the assumptions and the parameters from Theorem H.5, plus Assumption 3.1. Then Method 3 (Rennala SGD) converges after at most [ n2 seconds, where the sequence by is
defined in (12).
Proof.
The proof is identical the proof of Theorem 5.3.
H.2
HOMOGENEOUS SETUP AND SMOOTH CASE
In the homogeneous and smooth case, we can use an accelerated technique (Nesterov, 1983; Lan, 2020). Instead of Line 11 of Method
the following steps suggested by Lan (2020):
7 7. (I+ +111
a++1 22 + 2)
y A+1 = (1 - - + axt1u', (u== = x0)
1+1 = r 7k+1
(70)
sk g
1+1 (1-04+1 )ar + 0041
A new method with these steps is called the Accelerated Rennala SGD method (Tyurin & Richtárik, 2023).
Theorem H.7. [[Tyurin & Richtárik, 2023)] Let Assumptions H.I, 1.1 and 1.3 hold. Choose any
Let us take the batch size max (R2)) .1. and 9
1/2 +K+
min
Accelerated Method 3 (Accelerated Rennala SGD), then after || 20 iterations the method guarantees that [f(a f(x') 8, where
aR3s
IL
K
S.T.R. Vs
Theorem H.8. Consider the assumptions and the parameters from Theorem H.7, plus Assumption 3.1. Then Accelerated Method 3 (Accelerated Rennala SGD) converges after at most & " seconds,
where the sequence la is defined in (12).
Proof. The proof is identical to the proof of Theorem 5.3.
39

---

Published as a conference paper at ICLR 2025
H.3 HETEROGENEOUS SETUP AND NONSMOOTH CASE
Consider the heterogeneous setup discussed in Section 1.
Theorem H.9. Let Assumptions H.1, H.2, and H.4 hold. Choose any > O. Let us take
max {1 ||///|] , and y M2+02/8 E 2M2 M2 in Method 4, then after K 2 2M2
iterations the method guarantees that IE [](*)] f(x*) S where ak --0
1 Ek=o xt and
R
R
Proof.
Notice that Malenia SGD is equivalent to the classical SGD method with the step
B, (f,(t"
A+1
where the variance of the unbiased gradient estimator can be bounded in the following way:
B
1
1
0²
Bes
v((ot)
Bj
n2
B3
i=1
j=1
In Method 4, we ensure that
2 n² By
Therefore
5.
27
n
B
o²
Ege
n
B
-
S
5
Thus, we can use the classical result from the literature (e.g. (Lan, 2020)). We get
E [f((*)]] f(x") S
2M
x² 1012
r² (M²
xz
x 1
2
?²
2
for the stepsize
6
7
M +
2M M
where we use the fact that S 2 //M2.
Theorem H.10. Consider the assumptions and the parameters from Theorem H.9, plus Assump- tion 3.1. Then Method 4 (Malenia SGD) converges after at most & n2 seconds, where the sequence Ty is defined in (19).
Proof. The proof is identical to the proof of Theorem 6.4.
H.4 HRTEROGENEOUS SETUP AND SMOOTH CASE
Using the same idea in Section H.2. we will modify Malenia SGD and, instead of Line 13 from Algorithm 4, we use the lines (70). Such a method is called Accelerated Malenia SGD.
Theorem H.11. Let Assumptions H.1 and 1.1, and 1.4 hold. Choose any
0. Let us take
= max {[(2 (3)3) mm. and y min
in Accelerated iterations the method guarantees that V2
1
3 [o)
1/22
47.
Method 4 (Accelerated Malenia SGD), then after K 2 [f(x f(=*) E E, where
8vLR
x 20
Proof. Accelerated Malenia SGD is equivalent to the classical accelerated stochastic gradient method with mini- batch from (Lan, 2020). The proof repeats the proofs of Theorem H.7 and Theorem H.9.
40

---

Published as a conference paper at ICLR 2025
Theorem H.12. Consider the assumptions and the parameters from Theorem H.11, plus Assump- tion 3.1. Then Accelerated Method (Accelerated Malenia SGD) converges after at most t FTVTT seconds, where the sequence Eg is defined in (19).
vs
Proof. The proof is identical to the proof of Theorem 6.4.
I PROOF OF EXAMPLES
L.1 HOMOGENEOUS SETUP
Example 5.4. [Fixed Computation Model] Consider Example 3.2 with v;()) U, R2 for all
t t 0, E [n]. Then, for all i E [n], Vt(() ú,t and
T ZILA
+
min mE(n]
Un;
LA
LAg²
ms²
(13)
is a permutation such that UT. 2 ... 2 Ux. The proof's of the examples are in Section I.
Proof. Clearly, Vi(() = So vidT = vst. Substituting this to (12), we get is =
min (t 2 0 Ei [1i(t - Tx-1)) max 5 such that
// 1}} (To 0). Equivalently, we have to find
n [u: 2 max {10%// .13
8 min 2
Σ
(71)
and obtain l = Tx-1 kō. Let us show that
By/ S < 82
(72)
where ı is permutation such that U. 2 ... 2 Uxa,, and the 8. is defined as
0
min %Ein]
Eim Una
(5²+)) =cx cx
(Ein U ( (5)+)))
(73)
where j* is the largest index that minimizes the formula, and >> is constant. Using Lemma G.5, we obtain 1/ 1/(4um;)
) S 0./4 < 11(4unn)+))) where we define 1/u041 = zo for convenience. Thus
//,344 +1 5
Σ
Un, Bypal S
22m 81/2 1
max { o" [
where the first inequality due to [x|
<
2x
for all x 2 1/4. Therefore 8 2 8. On the other hand
L.G.S.1v2%
Σ U,, 84]
Un, 84 (73) ( +3*) max .1]
.1.
We can conclude that 5 < 5g. and using the inequality 5 2 8. we have proved (72). It is left to use the equality T = k:5.
Example 5.5. [Nonlinear Trend] Assume that (t) U/ gt() with > 0 for all i [n] and
continuous almost everywhere "o function g(t)
R + R.. Then
( LA + _وg7) )
dTanee1 = G-1
C1
min
1 m
Σ
Unz
(14)
mE[n]
where is permutation such that Uny ... Un,, G(t) = So g(T)dr, and eı E [1/4, 4] (can
depend on other parameters but is bounded).
JeWe can relax these assumptions measurability and non-negativity, but the proof will be more technical.
41

---

Published as a conference paper at ICLR 2025
Proof. We have Vt(t) fu (gg())d7 vtG(t). We substitute this equality (12) and get é min {t 2 0: Di=1 (v((t - G(tx-1))] 2 max (f='/=], Since G(t) is continuous and in- creasing, one can show that G(T+) = min { 1120 - [us(t G(Ix-1)) 2 max [[="/[].1]] Therefore G(tx)= = + G(tx-1) = kd and fy = G (kö), where ő defined in (71). Using (72). get (14).
Example 5.6. ["Random" Outages]
Assume that
U, E 1,, (N: +
(t)
f=1
(15)
0,
otherwise,
> 0, kg N, and h4 > 0 for all i e [n]. Then
)(())))))))))))
min me(ni
(4a + mo?
(16)
m
Mig
where π is permutation such that Kims .... ki...
Proof Sketch. We have Vi(I) = 1o (i(T)d = v x meeasure of intervals before the time 1] ~ vt/k.-
We substitute it to (12) and get 7 == min { 2 0 Σ L't/k; vi, 1ok,-//k] 2 max { (10% .1]
Using the same reasoning as in Example 5.4, one can easily get (16).
1.2 HETEROGENEOUS SETUP
Example 6.5. [Fixed Computation Model in the Heterogeneous Setting] Assume that (t) U/ with 0; > 0 for all E [n]. Then
1 T = 0 max 1 + (+ [iE|n]
En 1 o²
(20)
Proof. Clearly, Vi(t) = vod = v,t. Substituting this to (19), we get &
min 2 0: (1/2 Ei= [vi(1 - 1 2 max f20"/ne, 13}. Equivalently, we have to find
such that
8- = min 8 820: 1/6 Σ [0,01 < min (nc/202, 1}
(74)
and calculate & = 8 + 4- kō. Let show that
81/4 5 505 84
(75)
where the J. is defined as
8. := c (maxie(n) en + ( Ex vi) ne
2)
0²
(76)
and c > 0 is constant. Since 5a 2 maxie[n] " we have [1:64]
2 rids for all E [x] and 2
n
2
(76)
12
0
1
71
0;04
1 + 2v;
En
wi:)
1
o²
ne
< min
1
min
202 1
nE
nl i=1
2v;
-
n
1
22
Thus 8 < 84. On the other hand, let us show that 1 D
[urdya] > min mm//20² 1}.
If max 1/e. > ( Di 1/x))2/ne, then dz/a 1/2 maxie(n) 1/0r, [uzdya] 0 for j
42

---

Published as a conference paper at ICLR 2025
arg [|]] 1/4, and
1 Ei= b
00 2 ne/20?. If maxielal 1/8,
C 3/vz) 0 02/ne,
n
then since [2] $ x for all x 0, get
1
(1rdyy)) (76) 1
2
nE
1=1
1=1
02
B
-i==
8i
ne
g²
2g
Therefore 1 Ugbyya]
min {ne/2>?, 1}, meaning 8 2 61/4-
Example 6.6. [Nonlinear Trend in the Heterogeneous Setting] Assume that 0t(1) = U gt) with
2 > 0 for all i E [n] and a continuous almost everywhere positive function g(t R + R Then
247A
G-1 (c1
max iiEn vi
( Ei
o² RE
(21)
where G(t) == So (())dT, and cı [1/4, 4] (can depend on other parameters but is bounded).
Proof.
We have (i(t) = So (o(())d = ,,G(t). We substitute this equality to (19)
and get to
min 0 E+E La (G(t) G(fx-1)))-") max 2a Since G(f) is continuous and increasing, one can
ne 1
show that G(fx)
min
120: 0: [1 E Lt (t - G( G(b--)))) 2 max
2n
Therefore G(f))
+ G(Tx-1) = kō and l = -A:),, where ó defined in (74). Using (75), we get (21).
43


Reviews:
[{"review_id": "i9fV86XN3M", "reviewer": "Reviewer_uBjW", "summary": "The paper provides new lower bounds for parallel optimization where the workers can have arbitrary delays. While this setting has been studied in many previous works, and there are known optimal analyses of algorithms such as asynchronous SGD, the paper studies a more general computation model where the delays are not only arbitrary but can also evolve in a structured or unstructured manner over time. Under this model, the paper provides tight lower bounds for many problems of interest, such as periodic delay patterns (common in cross-device federated learning), random device outages, etc. The paper studies homogeneous and heterogeneous distributed setups, matching the best-known upper bounds (up to log factors) in both settings. Overall, the paper closes important gaps in parallel optimization and I support accepting the paper.", "questions": "1. I am unsure if I understand the difference between Theorems 6.1 and 6.2. Why does it matter if the functions are randomized v/s not? The inner/max player can always put all their weight on the worst functions for a given algorithm.\n2. Can the authors comment on what Theorem 6.2 (or 6.1) implies for the partial participation setting in Federated learning (as studied in papers such as [[1]](https://arxiv.org/abs/2008.03606), [[2]](https://openreview.net/forum?id=SNElc7QmMDe)), where sampling from a meta distribution of users is standard?\n3. Could the authors provide a detailed comparison against [[3]](https://arxiv.org/abs/2305.12387) regarding the main difference in the lower bound proof techniques while highlighting which delayed feedback settings can not be captured by their lower bound? It also seems that much notational/computational heavy loading was already done in this published paper.\n4. One benefit of the graph oracle framework [[4]](https://arxiv.org/abs/1805.10222) is that it is easier to describe the information flow between different oracle queries between different time steps and agents, compared to using the states like the authors do in their computational model. Could the authors describe what can be captured in their model that can not be captured in the graph oracle model? What do their lower bounds say about existing gaps in the graph oracle framework?\n5. Can the authors highlight in their proof sketches or at least in the appendix why the techniques used in the heterogeneous setting can not recover the homogeneous results under some notion of data heterogeneity? For instance, second or first-order heterogeneity notions combined [[2]](https://openreview.net/forum?id=SNElc7QmMDe) could help interpolate between these two settings (given the hard instances are similar to the usual zero-distributed lower bounds). Or is there any other restriction on the adversary that would make the lower-bound construction less pessimistic?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. **Closes significant gaps**: The paper closes critical gaps in parallel optimization by providing lower bounds that match the convergence rates for existing algorithms, meaning they are tight. I like that the paper makes these connections explicit, providing relevant corollaries for upper bounds where needed. \n2. **Good writing**: The paper's writing is clear and rigorously describes all results. In notationally heavy parts, such as while introducing the computation model, the paper provides the rough intuition for each term/unit/state, which is very helpful. \n3. **Exhaustive coverage**: Another good thing is that the paper considers both homogeneous and heterogeneous settings relevant to applications like federated learning, which is uncommon in much of the literature on asynchronous optimization, which focuses on data center settings. Overall, the paper's coverage is exhaustive, with both non-convex and convex results.", "weaknesses": "There are no significant weaknesses in this paper, but I think the following may help improve the writing and exposition:\n1. See my question about [[3]](https://arxiv.org/abs/2305.12387) below.\n2. See my question about the graph-oracle framework [[4]](https://arxiv.org/abs/1805.10222). Adding a comparison in the appendix would make the paper even more exhaustive.\n3. Since the paper does not consider data heterogeneity, it can not recover the homogeneous lower bound. For instance, in the fixed computational power model, (19) can not recover (12). From reading the proof, I raise this issue because the heterogeneity across the workers (in the lower bound) looks pretty adversarial, and it is unclear to me what practical settings will have such heterogeneity. Theoretically, I understand there is no reason the lower bound would not use the full power of the adversary. This is why, theoretically, I think the fully heterogeneous setting is a bit too pessimistic. For instance, if we restrict the heterogeneity to disallow arbitrary division of data blocks ($h_j$'s), the lower bound should be worse (i.e., go down).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "agDu7W1dXe", "reviewer": "Reviewer_H1r6", "summary": "This work studies distributed stochastic optimization in a parallel and asynchronous setting. In the literature, there is an assumption that all workers operate at a stable and uniform speed, which is unrealistic in practice. This work extends the framework to account for arbitrary computational capacities of workers, capturing their instability and time-varying nature. It then analyzes this generalized framework by deriving both lower and upper bounds.", "questions": "Do you also consider a model for communication bandwidth? From what I understand, when a worker computes a stochastic gradient, it is broadcast to all other workers. Do you account for situations where there is a communication bandwidth bottleneck or where, due to stragglers, communication may completely fail, preventing the message from being broadcast?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-The paper considers a realistic scenario for analyzing distributed stochastic gradient descent by introducing a universal computation model. This model is general and can capture unstable, time-varying random workers.\n\n- It defines a class of algorithms within this new framework and derives tight lower bounds achievable by optimal algorithms.\n\n- The paper also connects previously developed algorithms for distributed stochastic gradient descent, showing that they remain optimal in this new setting.", "weaknesses": "The paper lacks numerical results and experiments, which would strengthen its contributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "biAp7gV448", "reviewer": "Reviewer_FEY6", "summary": "This paper analyzes the time and oracle complexities of distrusted stochastic gradient descent. To approach this problem, the authors proposed a general computation model where the stochastic gradient is accessed through a set of workers that have different computational speed. In contrast to the classical oracle complexity results for SGD, this work considers an additional level of complexity that the time spent for each oracle access may be different. Then, the authors proved lower bound for the time complexity under the proposed setting and then provided two algorithms that match the lower bound.", "questions": "I am happy to hear from the author's response to my main concern that how this work adds significant value over [1]. If the authors convince me to change my mind during the rebuttal process, then I expect the authors to incorporate those discussion into the final version of the paper.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper offers a very detailed analysis for distributed SGD \n- I agree with the author's claim that their proposed computation model is in some sense \"universal\" because it greatly extends the model considered by the previous works such as [1].\n- For the proposed setting, this paper offers matching lower and upper bound, thus provides a complete narrative for this problem.\n\nI appreciate that the author does a good job explaining all of the mathematically technically and despite the verbosity required for the very general setting, the definitions in this paper do not take major effort to follow.\n\nThe introduction is direct and concise and I immediately know what kind of results I should expect to see in the technical sections.\n\n[1] Tyurin A, Richtárik P. Optimal time complexities of parallel stochastic optimization methods under a fixed computation model. Advances in Neural Information Processing Systems. 2024.", "weaknesses": "In terms of organization, I suggest that the examples should be moved forward. Currently, the statements of Theorem 5.1 and 6.1 are very long and hard to digest. Having the examples immediately following these theorems would be appreciated. Also, since Them 5.1 and 6.1 are implicit due to the generality of the setting, it could be useful to make some plots for a specific problem instance (say for the fixed computation model) so it is easier to parse the implications of these results.\n\nFor equations (12) (13) and (15), I think the minimum is always at $m=1$ and therefore redundant?\n\nThe proof sketch in Section 7 is not helpful at all. In particular, I want to see the \"worst case function\" being spelled out. From reading the full proof, this step is highly nontrivial and I would like to see some intuition. Also, on line 486, I think you meant \"first coordinate.\" The random variables $\\eta_k$ should be defined earlier in that paragraph. Lastly, I don't understand Section 7.2 at all even after multiple re-reads, in particular, I am left with a feeling with that something important was left out between lines 517 and 522.\n\nLastly and most importantly, **I do not think this paper has sufficient delta from earlier work [1].** \n- From what I can tell, Theorems 6.4 and A.2 from [1] correspond exactly to Examples 5.4 and 6.5. Since the problem setup is quite complicated, it is important for the authors to justify that the added generality actually leads to some meaningful implications. Not having any further examples beyond 6.5 for the heterogeneous setting does not help the cause.\n- And there seem to be a major reuse of proof techniques between the two papers. The proof of Theorem 5.1 up to equation (25) is almost a line-by-line reproduction of the existing analysis in [1]. While I am in no way suggesting any ill intent from the authors, I want to hear from the authors what are the main technical difficulties going from [1] to their proofs.\n\nIn light of these observations, I am hesitant to recommend  an accept because this paper seems to a straight extension of an earlier work [1] that added a lot of mathematical complexity but without too much of new insights. I think the amount of new contribution is insufficient for a new conference paper but could be worthwhile as a journal submission. So I will give score of **5** for the time-being.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WqvBIka7UJ", "reviewer": "Reviewer_EWQJ", "summary": "The paper addresses the challenges and establishes optimal time complexities for distributed stochastic optimization methods that utilize parallel and asynchronous computation. The authors introduce a universal computation model that captures the real-world scenarios of fluctuating computation speeds, hardware and network delays, and other irregularities often encountered in parallel computing environments. They apply this model to demonstrate tight lower bounds for both synchronous and asynchronous optimization methods, and highlight that these bounds are closely matched by the Rennala SGD and Malenia SGD methods.", "questions": "1. Does the computation power characterize server’s computation speed? \n2. In Methods 3 and 4, is the communication time between the workers and the server taken into account? In practical systems, it may take a significantly longer amount of time for a worker to transmit a gradient than to compute it. How does the universal computation model account for this?\n3. Line 209: What does $\\mathcal{D}$ mean?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper proposes a new computation model that more realistically simulates the computational irregularities of distributed systems, which advances over previous models that assumed stable and uniform computation speeds.\n2. The analysis encompasses a broad range of stochastic optimization methods and considers both homogeneous and heterogeneous computing environments.", "weaknesses": "1. The theoretical results, while comprehensive, may be too complex to be applied to practical algorithms. This complexity could limit their usability for practitioners who require simpler and more accessible tools for system design and analysis. Consequently, the tight lower bounds for time complexities are primarily of theoretical interest and provide limited insight into the potential performance improvements achievable with parallel stochastic optimization methods.\n2. The paper does not provide sufficient discussion on the limitations of the universal computation model. Are there any properties in parallel or distributed systems that fall outside the scope of this universal model?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)