Tight Time Complexities in Parallel Stochastic Optimization with Arbitrary Computation Dynamics

## Abstract

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 ) .

## 1 Introduction

Optimization is one of the main workhorses in machine learning (ML), data science (DS), and federated learning (FL) (Bottou et al., ; Kairouz et al., ). These fields rely on stochastic optimization methods, with notable examples including the stochastic gradient descent method (SGD) (Robbins & Monro, ) and ADAM (Kingma & Ba, ), which are considered to be the de facto choices for solving large-scale optimization problems (Schmidt et al., ). 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., ; Mayer & Jacobsen, ). However, it brings many challenges, including *computation heterogeneity*: many workers/CPUs/GPUs/phones work in parallel but with varying computation speeds, fluctuating performance over time, and potential disconnections due to hardware and network delays (Li et al., ).

### 1.1 Problem setup

Unconstrained smooth optimization problems that arise in ML, DS, and FL are described by

$$ $\displaystyle\textstyle\min\limits_{x\in\mathbb{R}^{d}}f(x),$ (1) $$

where $f\,:\,\mathbb{R}^{d}\rightarrow\mathbb{R}$ with the following standard assumptions:

###### Assumption 1.1 .

$f$ is differentiable & $L$–smooth, i.e., $\left\|\nabla f(x)-\nabla f(y)\right\|\leq L\left\|x-y\right\|$, $\forall x,y\in\mathbb{R}^{d}.$

###### Assumption 1.2 .

There exist $f^{*}\in\mathbb{R}$ such that $f(x)\geq f^{*}$ for all $x\in\mathbb{R}^{d}$.

In the nonconvex world, we want to find an $\varepsilon$–stationary point, a (random) vector $\bar{x}\in\mathbb{R}^{d}$ such that ${\rm\mathbb{E}}[\|\nabla f(\bar{x})\|^{2}]\leq\varepsilon,$ since, in general, it is intractable to find a global minimum in the nonconvex setting (Nemirovskij & Yudin, ; Murty & Kabadi, ). We analyze convex functions in Section G.

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 a problem arises when the computation cost of an exact gradient is huge or even infeasible due to batch normalization (Ioffe & Szegedy, ), dropout, random data augmentation, and many other handcrafted and naturally occurring noise sources that do not allow to calculate a gradient (Goodfellow et al., ).

Assume that $n$ workers work asynchronously in parallel and calculate stochastic gradients. We focus on two setups:
Homogeneous setup. For all $i\in[n],$ worker $i$ has access to an unbiased stochastic gradients $\nabla f(x;\xi)$ with $\sigma^{2}$-variance-bounded variances, where $\xi$ is a random variable from some distribution $\mathcal{D}$ on $\mathbb{S}_{\xi}.$ In ML and FL, this would mean that all workers have access to the *same data*.

###### Assumption 1.3 (Homogeneous setup) .

For all $i\in[n],$ worker $i$ can only calculate $\nabla f(x;\xi)$ and ${\rm\mathbb{E}}_{\xi}[\nabla f(x;\xi)]=\nabla f(x)$ and
${\rm\mathbb{E}}_{\xi}[\|\nabla f(x;\xi)-\nabla f(x)\|^{2}]\leq\sigma^{2}$ for all $x\in\mathbb{R}^{d},$ where $\sigma^{2}\geq 0.$

Heterogeneous setup.
Unlike the previous setup, we assume that
$\textstyle f(x)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(x)$
in this setting,
where $f_{i}\,:\,\mathbb{R}^{d}\rightarrow\mathbb{R}$ for all $i\in[n],$ and worker $i$ can only access stochastic gradients $\nabla f_{i}(x;\xi_{i})$ of the local function $f_{i},$ where $\xi_{i}$ is a random variable from some distribution $\mathcal{D}_{i}$ on $\mathbb{S}_{\xi}.$ In ML and FL, this would mean that all workers have access to *different data*.

###### Assumption 1.4 (Heterogeneous setup) .

For all $i\in[n],$ worker $i$ can only calculate $\nabla f_{i}(x;\xi_{i}),$ and ${\rm\mathbb{E}}_{\xi_{i}}[\nabla f_{i}(x;\xi_{i})]=\nabla f_{i}(x)$ and
${\rm\mathbb{E}}_{\xi_{i}}[\|\nabla f_{i}(x;\xi_{i})-\nabla f_{i}(x)\|^{2}]\leq
\sigma^{2}$ for all $x\in\mathbb{R}^{d},$ where $\sigma^{2}\geq 0.$

###### Assumption 1.1 .

###### Assumption 1.2 .

###### Assumption 1.3 (Homogeneous setup) .

###### Assumption 1.4 (Heterogeneous setup) .

### 1.2 Related Work

Oracle complexity with *one worker*. The optimal (dimension-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. (); Carmon et al. () showed that the optimal oracle complexity is
$\textstyle\operatorname{O}\left(\nicefrac{{L\Delta}}{{\varepsilon}}+\nicefrac{
{\sigma^{2}L\Delta}}{{\varepsilon^{2}}}\right)$
achieved by SGD, i.e., $x^{k+1}=x^{k}-\gamma\nabla f(x^{k};\xi^{k}),$ where $\xi^{k}$ are i.i.d. random samples, $\Delta:=f(x^{0})-f^{*},$ $x^{0}\in\mathbb{R}^{d}$ is a starting point, $\gamma=\Theta\left(\min\{\nicefrac{{1}}{{L}},\nicefrac{{\varepsilon}}{{L\sigma
^{2}}}\}\right)$ is a step size.

Oracle complexities with $n$ *workers*. There were several approaches, e.g., (Scaman et al., ; Arjevani et al., ; Lu & De Sa, ), to generalize the classical oracle complexity (Nemirovskij & Yudin, ; Arjevani et al., ) to the parallel setup with $n$ workers. In the homogeneous convex setup, the most relevant to our setup work (Woodworth et al., ), 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, ; Hanzely et al., ; Lu & De Sa, ).

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. *It 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. (); Koloskova et al. () showed that the celebrated Asynchronous SGD method (Recht et al., ; Dean et al., ) with the proposer step sizes can provably improve Minibatch SGD in the homogeneous setup. Assume for now that worker $i$ requires at most $\tau_{i}$ seconds to calculate one stochastic gradient for all $i\in[n].$
Minibatch SGD is the iterative process $x^{k+1}=x^{k}-\nicefrac{{\gamma}}{{n}}\sum_{i=1}^{n}\nabla f(x^{k};\xi^{k}_{i}),$ where $\gamma$ is a stepsize, $\xi^{k}_{i}$ are i.i.d. samples, and $\nabla f(x^{k};\xi^{k}_{i})$ are calculated in parallel. This method converges after $\operatorname{O}\left(\nicefrac{{L\Delta}}{{\varepsilon}}+\nicefrac{{\sigma^{2
}L\Delta}}{{n\varepsilon^{2}}}\right)$ iterations (Cotter et al., ; Goyal et al., ; Gower et al., ) and after

$$ $\displaystyle\textstyle\operatorname{O}\left(\max\limits_{i\in[n]}\tau_{i} \times\left(\frac{L\Delta}{\varepsilon}+\frac{\sigma^{2}L\Delta}{n\varepsilon^ {2}}\right)\right)$ (2) $$

seconds because this method waits for the slowest worker with the time $\max_{i\in[n]}\tau_{i}.$ Using Asynchronous SGD, the time complexity (2) can be improved to

$$ $\displaystyle\textstyle\operatorname{O}\left(\left(\frac{1}{n}\sum\limits_{i=1 }^{n}\frac{1}{\tau_{i}}\right)^{-1}\left(\frac{L\Delta}{\varepsilon}+\frac{ \sigma^{2}L\Delta}{n\varepsilon^{2}}\right)\right),$ (3) $$

where the dependence on the processing times is harmonic (Mishchenko et al., ). An alternative method that also achieves this time complexity is Picky SGD (Cohen et al., ).

Subsequently, Tyurin & Richtárik () formalized the notion of time complexity using the *time oracle protocol*, and under the assumption that worker $i$ requires at most $\tau_{i}$ seconds to calculate one stochastic gradient for all $i\in[n],$ proved that the time complexity lower bound is

$$ $\displaystyle\textstyle\Theta\left(\min\limits_{m\in[n]}\left[\left(\frac{1}{m }\sum\limits_{i=1}^{m}\frac{1}{\tau_{\pi_{i}}}\right)^{-1}\left(\frac{L\Delta} {\varepsilon}+\frac{\sigma^{2}L\Delta}{m\varepsilon^{2}}\right)\right]\right)$ (4) $$

seconds in the homogeneous setup, where $\pi$ is a permutation that sorts $\tau_{i}:$ $\tau_{\pi_{1}}\leq\dots\leq\tau_{\pi_{n}}.$ Moreover, they developed a new method, Rennala SGD, that achieves the lower bound in the homogeneous setup. Under the bounded computation and communication assumptions, Tyurin et al. (); Tyurin & Richtárik () provided optimal time complexities in a setup where the communication time between the workers cannot be ignored.

## 2 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.

$\spadesuit$ We consider a new computation paradigm, for which we coin the name *universal computation model*, that includes virtually all possible computation scenarios that can appear in practical distributed, parallel, and asynchronous optimization environments.

$\clubsuit$ 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, ) 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, ) (see Theorem 6.4). The proofs of the lower bounds are based on new proof techniques and constructions (see Section 7 for an overview).

In Section G, 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 to 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 $i\in[n],$ we consider a non-negative *continuous almost everywhere* function $v_{i}\,:\,\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$(^1^11Notations: $\mathbb{R}_{+}:=[0,\infty),$ $\mathbb{R}^{\infty}_{+}:=[0,\infty],$ $\mathbb{N}:=\{1,2,3,\dots\},$ $\mathbb{N}_{0}:=\{0,1,2,\dots\},$ $[n]:=\{1,\dots,n\}.$) called a *computation power* of worker $i.$

###### Assumption 3.1 .

For all $i\in[n],$ $v_{i}$ 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 a time $t_{0}$ to a time $t_{1}$ is the Riemann integral(^2^22It is possible to consider the Lebesgue integral and assume that the functions $\{v_{i}\}$ are measurable, but we will stick with the Riemann integral for simplicity.) of the computation power $v_{i}$ followed by the floor operation (because we can not partially calculate a stochastic gradient):

$$ $\displaystyle\textnormal{``\# of stoch. grad. by worker $i$ in $[t_{0},t_{1}]$ ''}=\left\lfloor\int_{t_{0}}^{t_{1}}v_{i}(\tau)d\tau\right\rfloor=\left\lfloor V _{i}(t_{1})-V_{i}(t_{0})\right\rfloor,$ (5) $$

where we additionally define a mapping $V_{i}\,:\,\mathbb{R}^{\infty}_{+}\rightarrow\mathbb{R}_{+}^{\infty}$ such that

$$ $\displaystyle V_{i}(t):=\int_{0}^{t}v_{i}(\tau)d\tau.$ (6) $$

For $t_{1}\geq t_{0},$ $V_{i}(t_{1})-V_{i}(t_{0})$ is called a *computation work* of worker $i$ from a time $t_{0}$ to a time $t_{1}.$

###### Example 3.2 (Fixed Computation Model) .

Let us consider the simplest example and take the performances that do not change through time, i.e., $v_{i}(t)=v_{i}\in\mathbb{R}_{+}$ for all $t\geq 0.$ If we take $t_{0}=0,$ then

$$ $\displaystyle\left\lfloor\int_{t_{0}}^{t_{1}}v_{i}(\tau)d\tau\right\rfloor= \left\lfloor V_{i}(t_{1})-V_{i}(t_{0})\right\rfloor=\left\lfloor v_{i}t_{1} \right\rfloor.$ $$

This formula formalizes simple logic that it takes $1/v_{i}$ seconds to find one stochastic gradient in worker $i$ because $\left\lfloor v_{i}\times 1/v_{i}\right\rfloor=1,$ $2/v_{i}$ seconds to find two stochastic gradients in worker $i$ because $\left\lfloor v_{i}\times 2/v_{i}\right\rfloor=2,$ and so forth. The higher the power $v_{i}$, the less time it takes to find a new stochastic gradient. Section 5.1 has more examples.

###### Theorem 3.3 (e.g. (Bartle & Sherbert, 2000 ) ) .

For all $i\in[n],$ $V_{i}$ is continuous and non-decreasing on $\mathbb{R}_{+}$ if $v_{i}$ is non-negative continuous almost everywhere (Assumption 3.1).

Notice this theorem can hold even if $v_{i}$ is *discontinuous*.
In general, the computation powers $\{v_{i}\}$ can be even random. Indeed, we can assume that $v_{i}\,:\,\mathbb{R}_{+}\times\Omega\to\mathbb{R}_{+}$ is a *stochastic computation power*, where $\Omega$ a sample space of a probability space. Then, all the following results hold when conditioned over all randomness in $\{v_{i}\},$ assuming that the sources of randomness are statistically independent. Without loss of generality, we continue assuming that $v_{i}\,:\,\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$ for all $i\in[n].$  For all $i\in[n],$ let us define the generalized inverse function(^3^33We use the standard convention $\min\{\emptyset\}=\infty.$) $V_{i}^{-1}\,:\,\mathbb{R}^{\infty}_{+}\rightarrow\mathbb{R}_{+}^{\infty}$ such that

$$ $\displaystyle\textstyle V_{i}^{-1}(S)=\min\left\{t\geq 0\,:\,V_{i}(t)=S\right\}$ (7) $$

for all $S\in\mathbb{R}^{\infty}_{+}.$ If $V_{i}$ is strongly increasing, then $V_{i}^{-1}$ is the standard inverse function of $V_{i}.$

###### Assumption 3.1 .

###### Example 3.2 (Fixed Computation Model) .

###### Theorem 3.3 (e.g. (Bartle & Sherbert, 2000 ) ) .

## 4 Preliminaries

Before we present our main results, we have to formalize the notion of time and time complexity.
Recall that in the classical approach of deriving lower bounds, we examine the following protocol (Nemirovskij & Yudin, ; Nesterov, ; Carmon et al., ):

Figure: Protocol 1 Classical Oracle Protocol

Where we want to find the worst-case oracle complexity formalized by

$$ $\displaystyle\textstyle\inf\limits_{A\in\mathcal{A}}\sup\limits_{f\in\mathcal{ F}}\sup\limits_{(O,\mathcal{D})\in\mathcal{O}(f)}\inf\left\{k\in\mathbb{N}\, \middle|\,{\mathbb{E}}\left[\left\|\nabla f(x^{k})\right\|^{2}\right]\leq \varepsilon\right\}.$ $$

Protocol 1 is a reasonable way to establish lower bounds and compare algorithms, but it is not convenient for analyzing parallel algorithms. In order to analyze parallel and asynchronous algorithms, Tyurin & Richtárik () proposed to use the time multiple oracles protocol:

Figure: Protocol 2 Time Multiple Oracles Protocol

Unlike the classical protocol where an algorithm returns a new point $x^{k}$ based on the current information $g^{1},\dots,g^{k},$ this protocol requires an algorithm to return a time $t^{k+1},$ an index of an oracle $i^{k+1}$, a control variable $c^{k+1}$, and a new point $x^{k}.$ In the parallel setting, algorithms have access to many workers/oracles. In every iteration, an algorithm has the freedom to choose any oracle using $i^{k+1},$ and call the oracle at a point $x^{k}.$ The role of control variables $\{c^{k+1}\}$ will be clear later.

*The main idea is that an algorithm controls time and decides when it is ready to go forward using a time sequence $\{t^{k+1}\}.$* Let us introduce an oracle that emulates the behavior of a real worker, and then we will provide clarifications. For all $i\in[n],$ we consider the mapping

$$ $\displaystyle O_{i}\,:\,$ $\displaystyle\underbrace{\mathbb{R}_{+}}_{\textnormal{time}}\times\underbrace{ \mathbb{R}^{d}}_{\textnormal{point}}\times\underbrace{(\mathbb{R}_{+}\times \mathbb{R}^{d}\times\{0,1\})}_{\textnormal{input state}}\times\underbrace{\{0, 1\}}_{\textnormal{stop computation}}\rightarrow\underbrace{(\mathbb{R}_{+} \times\mathbb{R}^{d}\times\{0,1\})}_{\textnormal{output state}}\times \underbrace{\mathbb{R}^{d}}_{\textnormal{output vector}}\textnormal{such that}$ $$

$$ $\displaystyle\begin{split}&O_{i}(t,x,(s_{t},s_{x},s_{q}),c)=\left\{\begin{ aligned} &((t,x,1),&0),\quad&c=0,s_{q}=0,\\ &((s_{t},s_{x},1),&0),\quad&c=0,s_{q}=1,V_{i}(t)-V_{i}(s_{t})<1,\\ &((0,0,0),&g_{i}(s_{x};\xi,t)),\quad&c=0,s_{q}=1,V_{i}(t)-V_{i}(s_{t})\geq 1, \\ &((0,0,0),&0),\quad&c=1,\end{aligned}\right.\end{split}$ (8) $$

where $\mathcal{D}_{s_{x},t,i}$ is some distribution that can depend on $s_{x},$$t$, $\xi\sim\mathcal{D}_{s_{x},t,i},$ and $g_{i}\,:\,\mathbb{R}^{d}\times\mathbb{S}_{\xi}\times\mathbb{R}_{+}\to\mathbb{R
}^{d}$ is a mapping. This oracle can return different outputs depending on an input it receives: i) if $c=0,s_{q}=0,$ then the oracle is only starting the calculation of a stochastic gradient, and it memorizes the time when it was called in the variable $s_{t}$; ii) if $c=0,s_{q}=1,V_{i}(t)-V_{i}(s_{t})<1,$ then the oracle is still calculating; iii) if $c=0,s_{q}=1,V_{i}(t)-V_{i}(s_{t})\geq 1,$ then the oracle has finished the calculation and returns $g_{i}(s_{x};\xi,t)$ at the point $s_{x}$ where the calculation was initialized. The condition $V_{i}(t)-V_{i}(s_{t})\geq 1$ means that “at the current time $t,$ the oracle is ready to return the stochastic gradient that began to be calculated at time $s_{t}$.”
The control variable $c$ allows algorithms to stop the calculations at any time they want if they pass $c=1.$

The oracles (8) force algorithms to increase times; otherwise, they will not get stochastic gradients and enough information to find an $\varepsilon$–stationary point. Using Protocol 2, we consider the time complexity measure

$$ $\displaystyle\begin{split}&\textstyle\inf\limits_{A\in\mathcal{A}}\sup\limits_ {f\in\mathcal{F}}\sup\limits_{(O,\mathcal{D})\in\mathcal{O}(f)}\inf\left\{t \geq 0\,\middle|\,{\mathbb{E}}\left[\inf\limits_{k\in S_{t}}\left\|\nabla f(x^ {k})\right\|^{2}\right]\leq\varepsilon\right\},\textstyle S_{t}:=\left\{k\in \mathbb{N}_{0}\middle|t^{k}\leq t\right\}\end{split}$ (9) $$

where the sequences $t^{k}$ and $x^{k}$ 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, )[Sections 3–5] for more details.

In this work, we consider zero-respecting algorithms formalized by the definition below.

###### Definition 4.1 (Algorithm Class $\mathcal{A}_{\textnormal{zr}}$ ) .

Let us consider Protocol 2. We say that an algorithm $A=\{A^{k}\}_{k=0}^{\infty}$ is a zero-respecting algorithm, if

- 1.
$A^{k}\,:\,\underbrace{\mathbb{R}^{d}\times\dots\times\mathbb{R}^{d}}_{k
\textnormal{ times}}\rightarrow{\mathbb{R}_{\geq 0}}\times[n]\times\{0,1\}
\times\mathbb{R}^{d}\quad\forall k\geq 1,A^{0}\in{\mathbb{R}_{\geq 0}}\times[n
]\times\{0,1\}\times\mathbb{R}^{d},$
- 2.
$\textnormal{supp}\left(x^{k}\right)\subseteq\bigcup_{j=1}^{k}\textnormal{supp}
\left(g^{j}\right)$ for all $k\in\mathbb{N}_{0},$ where $\textnormal{supp}(x):=\{i\in[d]\,|\,x_{i}\neq 0\},$
- 3.
for all $k\geq 1$ and $g^{1},\dots,g^{k}\in\mathbb{R}^{d},$ we have $t^{k+1}\geq t^{k},$ where $t^{k+1}$ and $t^{k}$ are defined as $(t^{k+1},\cdot)=A^{k}(g^{1},\dots,g^{k})$ and $(t^{k},\cdot)=A^{k-1}(g^{1},\dots,g^{k-1}).$

The first condition defines the domain and range, the second condition is the definition of a zero-respecting algorithm (Carmon et al., ), the third condition ensures that the algorithm return a non-decreasing sequence of times (Tyurin & Richtárik, ).

###### Definition 4.1 (Algorithm Class 𝒜 zr subscript 𝒜 zr \mathcal{A}_{\textnormal{zr}} caligraphic_A start_POSTSUBSCRIPT zr end_POSTSUBSCRIPT ) .

## 5 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 the Lower Bound) .

Let Assumptions 1.1, 1.2, 1.3, and 3.1 hold. It is impossible to converge faster than $\nicefrac{{1}}{{2}}\times\underline{t}_{\left\lceil c_{1}\times\frac{L\Delta}{
\varepsilon}\right\rceil}$ seconds, where the sequence $\{\underline{t}_{k}\}$ is defined in (10) and $c_{1}$ is a universal constant.

###### Theorem 5.1 .

Consider Protocol 2. We take computation powers $\{v_{i}\}$ such that Assumption 3.1 holds, and fix $L,\Delta,\varepsilon>0$ and $\sigma^{2}\geq 0$ that satisfy the inequality $\varepsilon<c^{\prime}L\Delta$. For any algorithm $A\in\mathcal{A}_{\textnormal{zr}},$ there exist a function $f,$ which satisfy Assumptions 1.1, 1.2 and $f(0)-f^{*}\leq\Delta$, and stochastic gradient mappings $\{g_{i}\}$ in (8), which satisfy Assumption 1.3,
i.e., ${\mathbb{E}}_{\xi}\left[g_{i}(s_{x};\xi,t)\right]=\nabla f(s_{x})$ and ${\mathbb{E}_{\xi}}[\left\|g_{i}(s_{x};\xi,t)-\nabla f(s_{x})\right\|^{2}]\leq
\sigma^{2}$ for all $s_{x}\in\mathbb{R}^{d},i\in[n]$
such that ${\mathbb{E}}\big{[}\inf\limits_{k\in S_{t}}\left\|\nabla f(x^{k})\right\|^{2}
\big{]}~{}>~{}\varepsilon$ holds,
where $S_{t}:=\left\{k\in\mathbb{N}_{0}\,|\,t^{k}\leq t\right\},$

$$ $\textstyle t=\frac{1}{2}\times\underline{t}_{\left\lfloor c_{1}\times\frac{L \Delta}{\varepsilon}\right\rfloor},$ $$

and(^4^44We use the standard convention $\min\{\emptyset\}=\infty.$)

$$ $\displaystyle\textstyle\underline{t}_{k}:=\min\left\{t\geq 0\,:\,\sum\limits_{ i=1}^{n}\left\lfloor V_{i}(t)-V_{i}(\underline{t}_{k-1})\right\rfloor\geq c_{2 }\times\max\left\{\left\lceil\frac{\sigma^{2}}{\varepsilon}\right\rceil,1 \right\}\right\}\qquad(\underline{t}_{0}=0)$ (10) $$

for all $k\geq 0.$ The quantities $c^{\prime},c_{1},$ and $c_{2}$ are universal constants. The sequences $x^{k}$ and $t^{k}$ are defined in Protocol 2.

Unlike most previous works (e.g., (Nesterov, ; Arjevani et al., ; Tyurin & Richtárik, )), 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 (10) one by one ($\underline{t}_{1},\underline{t}_{2},\underline{t}_{3},\dots$) to get $\nicefrac{{1}}{{2}}\times\underline{t}_{\left\lfloor c_{1}\times L\Delta/
\varepsilon\right\rfloor}.$ Computationally, this problem is not difficult since the function $\sum_{i=1}^{n}\left\lfloor V_{i}(t)-V_{i}(\underline{t}_{k-1})\right\rfloor$ is non-decreasing; thus, for instance, we can employ the bisection method.

###### Theorem (Informal Formulation of the Lower Bound) .

###### Theorem 5.1 .

### 5.1 Optimal algorithm

Figure: Method 3 Rennala SGD

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, ). In every iteration, the method collects a batch of size $S,$ and performs a gradient-like step once the batch has been collected. The following result was proved in (Tyurin & Richtárik, ). The proof technique is simple and follows the classical analysis of SGD (Ghadimi & Lan, ; Khaled & Richtárik, ) since the logic of Rennala SGD is equivalent to the steps $x^{k+1}=x^{k}-\nicefrac{{\gamma}}{{S}}\sum_{i=1}^{S}\nabla f(x^{k};\xi_{i}),$ where $\{\xi_{i}\}$ are i.i.d. samples.

###### Theorem 5.2 .

[(Tyurin & Richtárik, )]
Let Assumptions 1.1, 1.2, and 1.3 hold. We take
$\gamma=1/2L$ and batch size $S=\max\{\left\lceil\nicefrac{{\sigma^{2}}}{{\varepsilon}}\right\rceil,1\}$ in Method 3.
For all
$K\geq 24L\Delta/\varepsilon,$
we get $\frac{1}{K}\sum_{k=0}^{K-1}{\mathbb{E}}\left[\left\|\nabla f(x^{k})\right\|^{2
}\right]\leq\varepsilon.$

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 at most $\bar{t}_{\left\lceil\frac{24L\Delta}{\varepsilon}\right\rceil}$ seconds, where

$$ $\displaystyle\textstyle\bar{t}_{k}:=\min\left\{t\geq 0\,:\,\sum\limits_{i=1}^{ n}\left\lfloor V_{i}(t)-V_{i}(\bar{t}_{k-1})\right\rfloor\geq\max\left\{\left \lceil\frac{\sigma^{2}}{\varepsilon}\right\rceil,1\right\}\right\}\qquad(\bar{ t}_{0}\equiv 0)\quad\forall k\geq 1.$ (11) $$

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 is implicit, we do not get a closed-form expression for $\bar{t}_{\left\lceil 24L\Delta/\varepsilon\right\rceil}$ in Theorem 5.3. That said, the sequence $\bar{t}_{k}$ 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 $\{v_{i}\}.$ Therefore, the absence of a closed-form expression is irrelevant for practical implementations and is only of theoretical interest.

###### Example 5.4 .

[Fixed Computation Model]
Consider Example 3.2 with $v_{i}(t)=v_{i}\in\mathbb{R}_{+}$ for all $t\geq 0,i\in[n].$ Then, for all $i\in[n],$ $V_{i}(t)=v_{i}t$ and

$$ $\displaystyle\textstyle\bar{t}_{\left\lceil\frac{24L\Delta}{\varepsilon}\right \rceil}=\Theta\left(\min\limits_{m\in[n]}\left(\frac{1}{m}\sum\limits_{i=1}^{m }v_{\pi_{i}}\right)^{-1}\left(\frac{L\Delta}{\varepsilon}+\frac{L\Delta\sigma^ {2}}{m\varepsilon^{2}}\right)\right),$ (12) $$

$\pi$ is a permutation such that $v_{\pi_{1}}\geq\dots\geq v_{\pi_{n}}.$ The proofs of the examples are in Section H.

In Example 3.2, we discuss that $\tau_{i}=\nicefrac{{1}}{{v_{i}}}$ is the time required to find one stochastic gradient in worker $i.$ If we reparametrize (12) with $v_{i}=\nicefrac{{1}}{{\tau_{i}}}$, then we get the time complexity (4). Thus, Example 5.4 restores the optimal time complexity obtained by Tyurin & Richtárik () for the fixed computation model, where the smaller the computation times $\tau_{i}$ (the higher the computation powers $v_{i}$), the smaller the complexities. Notice that if $v_{j}$ is small enough for some worker $j,$ then it is possible that the complexity (12) will not depend on $v_{j},$ meaning that this worker potentially does not contribute to an optimization process because it is too slow.
We can immediately derive a more general result:

###### Example 5.5 .

[Nonlinear Trend]
Assume that $v_{i}(t)=v_{i}\times g(t)$ with $v_{i}>0$ for all $i\in[n]$ and a continuous almost everywhere positive(^5^55We can relax these assumptions to *measurability and non-negativity*, but the proof will be more technical.) function $g(t)\,:\,\mathbb{R}_{+}^{\infty}\to\mathbb{R}_{+}.$ Then

$$ $\displaystyle\textstyle\bar{t}_{\left\lceil\frac{24L\Delta}{\varepsilon}\right \rceil}=G^{-1}\left(c_{1}\cdot\min\limits_{m\in[n]}\left(\frac{1}{m}\sum \limits_{i=1}^{m}v_{\pi_{i}}\right)^{-1}\left(\frac{L\Delta}{\varepsilon}+ \frac{L\Delta\sigma^{2}}{m\varepsilon^{2}}\right)\right),$ (13) $$

where $\pi$ is a permutation such that $v_{\pi_{1}}\geq\dots\geq v_{\pi_{n}},$ $G(t):=\int_{0}^{t}g(\tau)d\tau,$ and $c_{1}\in[1/4,4]$ (can depend on other parameters but is bounded).

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 t+1,$ which is invertible, and we can obtain a formula for the optimal time complexity using (13).

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 to gain a basic intuition.

###### Example 5.6 .

[“Random” Outages]
Assume that

$$ $\displaystyle\textstyle v_{i}(t)=\begin{cases}v,&t\in\bigcup\limits_{i=1}^{ \infty}[k_{i}(i-1),(k_{i}(i-1)+1)]\\ 0,&\textnormal{otherwise},\end{cases},$ (14) $$

$v>0,$ $k_{i}\in\mathbb{N},$ and $h_{i}>0$ for all $i\in[n].$
Then

$$ $\displaystyle\textstyle\bar{t}_{\left\lceil\frac{24L\Delta}{\varepsilon}\right \rceil}\approx\Theta\left(\min\limits_{m\in[n]}\left(\frac{1}{m}\sum\limits_{i =1}^{m}\frac{v}{k_{\pi_{i}}}\right)^{-1}\left(\frac{L\Delta}{\varepsilon}+ \frac{L\Delta\sigma^{2}}{m\varepsilon^{2}}\right)\right),$ (15) $$

where $\pi$ is a permutation such that $k_{\pi_{1}}\leq\dots\leq k_{\pi_{n}}.$

In this example, worker $i$ is active in the time intervals $[0,1],$ $[k_{i},k_{i}+1],$ $[2k_{i},2k_{i}+1],$ and so forth. The parameter $k_{i}$ characterizes how often the worker’s outages occur.

The formula (15) says that the more worker $i$ is inactive (the larger $k_{i}$), the more time it takes to solve the problem. Due to the $\min$ operation in (15), the formula indicates that some workers can be ignored if their $k_{i}$ are too large.
In general, we could have analyzed (14) with $\bigcup_{i=1}^{\infty}[\textnormal{start}_{k,i},\textnormal{end}_{k,i}],$ where the pairs $\{\textnormal{start}_{k,i},\textnormal{end}_{k,i}\}$ are arbitrarily (random) values on $\mathbb{R}_{+},$ but would get less interpretable formulas.

###### Theorem 5.2 .

###### Theorem 5.3 .

###### Example 5.4 .

###### Example 5.5 .

###### Example 5.6 .

## 6 Heterogeneous Setup

We now consider the heterogeneous setup discussed in Section 1, and present our first lower bound:

###### Theorem 6.1 .

Consider Protocol 2. We take computation powers $\{v_{i}\}$ such that Assumption 3.1 holds, and fix $L,\Delta,\varepsilon>0$ and $\sigma^{2}\geq 0$ that satisfy the inequality $\varepsilon<c^{\prime}L\Delta$. For any algorithm $A\in\mathcal{A}_{\textnormal{zr}},$ there exist functions $\{f_{i}\}_{i=1}^{n},$ where the function $f=\frac{1}{n}\sum_{i=1}^{n}f_{i}$ satisfies Assumptions 1.1, 1.2 and $f(0)-f^{*}\leq\Delta$, and stochastic gradient mappings $\{g_{i}\}_{i=1}^{n}$ in (8), which satisfy Assumption 1.4,
i.e., ${\mathbb{E}}_{\xi}\left[g_{i}(s_{x};\xi,t)\right]=\nabla f_{i}(s_{x})$ and ${\mathbb{E}_{\xi}}[\left\|g_{i}(s_{x};\xi,t)-\nabla f_{i}(s_{x})\right\|^{2}]
\leq\sigma^{2}$ for all $s_{x}\in\mathbb{R}^{d},i\in[n],$ and $t\geq 0,$
such that ${\mathbb{E}}\big{[}\inf\limits_{k\in S_{t}}\left\|\nabla f(x^{k})\right\|^{2}
\big{]}>\varepsilon$ holds,
where $S_{t}:=\left\{k\in\mathbb{N}_{0}\,|\,t^{k}\leq t\right\},$

$$ $\displaystyle\textstyle t=\frac{1}{2}\underline{t}_{\left\lfloor\frac{c_{1} \times\frac{L\Delta}{\varepsilon}}{\color[rgb]{1,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{1,0,0}\log\frac{L\Delta}{\varepsilon}}\right\rfloor}$ $$

and

$$ $\displaystyle\textstyle\underline{t}_{k}:=\min\left\{t\geq 0\,:\,\left(\frac{1 }{n}\sum_{i=1}^{n}\left\lfloor c_{3}\times\frac{V_{i}\left(t\right)-V_{i}( \underline{t}_{k-1})}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{ rgb}{1,0,0}\log\left(\frac{L\Delta}{\varepsilon}\right)}\right\rfloor^{-1} \right)^{-1}\geq\max\left\{c_{2}\times\frac{\sigma^{2}}{n\varepsilon},1\right \}\right\}$ (16) $$

for all $k\geq 1$ $(\underline{t}_{0}\equiv 0).$ The quantities $c^{\prime},c_{1},$ $c_{2},$ and $c_{3}$ are universal constants. The sequences $x^{k}$ and $t^{k}$ are defined in Protocol 2.

Unlike (11) where the dependencies on $\{V_{i}\}$ are *mean-like*, the dependencies in (16) 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, ) (see Section 6.1).

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 functions $\{f_{i}\}$, the following construction samples random functions $\{f_{i}\}$.
The fact that the functions $\{f_{i}\}_{i=1}^{n}$ are random helps to prove a 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., ; Gu et al., ; Mishchenko et al., ; Islamov et al., ).

###### Theorem 6.2 .

Consider Protocol 2. We take computation powers $\{v_{i}\}$ such that Assumption 3.1 holds, and fix $L,\Delta,\varepsilon>0$ and $\sigma^{2}\geq 0$ that satisfy the inequality $\varepsilon<c^{\prime}L\Delta$. For any algorithm $A\in\mathcal{A}_{\textnormal{zr}},$ we sample $\{f_{i}\}_{i=1}^{n}$ from some distribution of functions, where the function $f=\frac{1}{n}\sum_{i=1}^{n}f_{i}$ satisfies Assumptions 1.1, 1.2 and $f(0)-f^{*}\leq\Delta$ deterministically, and there exist stochastic gradient mappings $\{g_{i}\}_{i=1}^{n}$ in (8), which satisfy Assumption 1.4,
i.e., ${\mathbb{E}}_{\xi}\left[g_{i}(s_{x};\xi,t)\right]=\nabla f_{i}(s_{x})$ and ${\mathbb{E}_{\xi}}[\left\|g_{i}(s_{x};\xi,t)-\nabla f_{i}(s_{x})\right\|^{2}]
\leq\sigma^{2}$ for all $s_{x}\in\mathbb{R}^{d},i\in[n],$ and $t\geq 0,$
such that ${\mathbb{E}}\big{[}\inf\limits_{k\in S_{t}}\left\|\nabla f(x^{k})\right\|^{2}
\big{]}>\varepsilon$ holds(^6^66We take the expectation over all randomness.),
where $S_{t}:=\left\{k\in\mathbb{N}_{0}\,|\,t^{k}\leq t\right\},$

$$ $\displaystyle\textstyle t=\frac{1}{2}\underline{t}_{\left\lfloor c_{1}\times \frac{L\Delta}{\varepsilon}\right\rfloor}$ $$

and

$$ $\displaystyle\textstyle\underline{t}_{k}:=\min\left\{t\geq 0\,:\,\left(\frac{1 }{n}\sum_{i=1}^{n}\left\lfloor c_{3}\times\left(V_{i}\left(t\right)-V_{i}( \underline{t}_{k-1})\right)\right\rfloor^{-1}\right)^{-1}\geq\max\left\{c_{2} \times\frac{\sigma^{2}}{n\varepsilon},1\right\}\right\}$ (17) $$

for all $k\geq 1$ $(\underline{t}_{0}\equiv 0)$. The quantities $c^{\prime},c_{1},$ $c_{2},$ and $c_{3}$ are universal constants. The sequences $x^{k}$ and $t^{k}$ are defined in Protocol 2.

###### Theorem 6.1 .

###### Theorem 6.2 .

### 6.1 Optimal method

The obtained lower bound is tight since it is matched by Malenia SGD (Tyurin & Richtárik, ). This method is closely related to Rennala SGD with a similar structure, and mathematically, it is the vanilla SGD method with a 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 ().

###### Theorem 6.3 .

[(Tyurin & Richtárik, )]
Let Assumptions 1.1, 1.2, and 1.4 hold. We take take $S=\max\left\{\left\lceil\nicefrac{{\sigma^{2}}}{{\varepsilon}}\right\rceil,n
\right\},$ and
$\gamma=\min\left\{\frac{1}{L},\frac{\varepsilon S}{2L\sigma^{2}}\right\}=
\Theta\left(1/L\right)$ in Method 4,
then after $K\geq 24\Delta L/\varepsilon$
iterations the method guarantees that $\frac{1}{K}\sum_{k=0}^{K-1}{\mathbb{E}}\left[\left\|\nabla f(x^{k})\right\|^{2
}\right]\leq\varepsilon.$

This is a 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 $\bar{t}_{\left\lceil\frac{24L\Delta}{\varepsilon}\right\rceil}$ seconds, where

$$ $\displaystyle\textstyle\bar{t}_{k}:=\min\left\{t\geq 0\,:\,\left(\frac{1}{n} \sum_{i=1}^{n}\left\lfloor V_{i}(t)-V_{i}(\bar{t}_{k-1})\right\rfloor^{-1} \right)^{-1}\geq\max\left\{\frac{2\sigma^{2}}{n\varepsilon},1\right\}\right\} \quad(\bar{t}_{0}\equiv 0)$ (18) $$

for all $k\geq 1.$

Up to constant factors, Theorem 6.2 and Theorem 6.4 provide the optimal time complexity in the heterogeneous setting. The result is implicit, which is not a problem in practice since Malenia SGD does not require $\{V_{i}\}$ to reach the optimality. Let us consider an example where we can get an explicit formula.

###### Example 6.5 .

[Fixed Computation Model in the Heterogeneous Setting]
Assume that $v_{i}(t)=v_{i}$ with $v_{i}>0$ for all $i\in[n].$ Then

$$ $\displaystyle\textstyle\bar{t}_{\left\lceil\frac{24L\Delta}{\varepsilon}\right \rceil}=\Theta\left(\max\limits_{i\in[n]}\frac{1}{v_{i}}+\left(\frac{1}{n}\sum _{i=1}^{n}\frac{1}{v_{i}}\right)\frac{\sigma^{2}}{n\varepsilon}\right).$ (19) $$

This example shows that our result recovers the optimal complexity derived in (Tyurin & Richtárik, ). However, our time complexity works with virtually any computation model.

###### Theorem 6.3 .

###### Theorem 6.4 .

###### Example 6.5 .

## 7 Proof Techniques

### 7.1 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., ) and have access to oracles that calculate the exact gradient but zero out the last coordinate with some probability (Arjevani et al., ). 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 $\sum_{i=1}^{n}\left\lfloor V_{i}(t)\right\rfloor$ stochastic gradients by a time $t.$ 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 a point with a non-zero first coordinate earlier than $t_{1}:=\min\left\{t\geq 0\,:\,\sum_{i=1}^{n}\left\lfloor V_{i}(t)\right\rfloor
\geq\eta_{1}\right\}$ seconds. Using the same reasoning, the workers cannot get a point with a non-zero $k$^th coordinate earlier than $t_{k}:=\min\left\{t\geq 0\,:\,\sum_{i=1}^{n}\left\lfloor V_{i}(t)-V_{i}(t_{k-1
})\right\rfloor\geq\eta_{k}\right\}$ seconds, where $\{\eta_{k}\}_{k=1}^{T}$ are i.i.d. geometric random variables, and $T\approx\nicefrac{{L\Delta}}{{\varepsilon}}.$ With high probability, the large chunk (at least a quarter of $T\approx\nicefrac{{L\Delta}}{{\varepsilon}}$) of $\{\eta_{k}\}$ is not significantly smaller than $\nicefrac{{1}}{{p}}\approx\max\left\{\left\lceil\nicefrac{{\sigma^{2}}}{{
\varepsilon}}\right\rceil,1\right\}.$ Finally, with high probability, at least a quarter of indices from the set $[T]$ satisfy $t_{k}\geq\min\left\{t\geq 0\,:\,\sum_{i=1}^{n}\left\lfloor V_{i}(t)-V_{i}(t_{k
-1})\right\rfloor\gtrapprox\max\left\{\left\lceil\nicefrac{{\sigma^{2}}}{{
\varepsilon}}\right\rceil,1\right\}\right\}.$

### 7.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., ) in almost any desired manner. We consider $S$ functions $\{h_{j}\}$ such that $h_{j}(x)\,:\,\mathbb{R}^{S\times T}\to\mathbb{R}$ and $h_{j}$ depends only on the $j$^th block $x_{j}\in\mathbb{R}^{T}$ of $x=[x_{1},\dots,x_{S}]\in\mathbb{R}^{S\times T},$ where $T\approx L\Delta/\varepsilon,$ and consider the optimization problem with $f(x)=\nicefrac{{1}}{{n}}\sum_{j=1}^{S}h_{j}(x).$ As usual, the designed oracles zero out the last non-zero coordinate of calculated gradients, and an algorithm cannot find an $\varepsilon$-solution before at least roughly half of the functions $\{h_{j}\}$ are “solved,” requiring non-zero values in the last coordinates of the corresponding blocks. The main question is how to distribute the functions $\{h_{j}\}$ 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 $\{h_{j}\},$ and assign the “parts” of the first $c_{1}/V_{1}\left(\bar{t}_{1}\right)$ functions to the first worker, the “parts” of the second $c_{1}/V_{2}\left(\bar{t}_{1}\right)$ functions to the second worker, and so forth, where $\bar{t}_{1}\approx\underline{t}_{1}$ from (17), $c_{1}$ is a constant such that $\sum_{i=1}^{n}c_{1}/V_{i}\left(\bar{t}_{1}\right)=S.$ The next $K$ “parts” we assign proportionally to $c_{2}/(V_{i}\left(\bar{t}_{2}\right)-V_{i}\left(\bar{t}_{1}\right)),$ and so forth. In total, the allocation of the functions $\{h_{j}\}$ is dynamic since one function can be stored on many workers. For all $j\in[S],$ the “parts” of $h_{j}$ can be distributed among different workers according to $\{V_{i}\}.$ By taking the appropriate values $S,K,$ and other parameters, we can ensure the lower bound in Theorem 6.1 holds.

However, Theorem 6.1 is only tight up to logarithmic factors because the allocation of $\{h_{j}\}$ is *predefined*. In response, we propose a construction where the functions $\{h_{j}\}$ 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 $\sigma$–variance bounded stochastic gradients.

## 8 Conclusion

To the best of our knowledge, this is the first work that provides optimal time complexities under virtually arbitrary computation behavior of 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 an 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.

## Appendix A Proof of Theorem 5.3

See 5.3

###### Proof.

From Theorem 5.2, we know that Method 3 converges after

$$ $\displaystyle\left\lceil\frac{24L\Delta}{\varepsilon}\right\rceil$ $$

iterations. The algorithm waits for $S=\max\{\left\lceil\nicefrac{{\sigma^{2}}}{{\varepsilon}}\right\rceil,1\}$ stochastic gradients from all the workers in every iteration. The workers work in parallel and after $t$ seconds they guarantee to calculate

$$ $\displaystyle\sum_{i=1}^{n}\left\lfloor V_{i}(t)\right\rfloor$ $$

stochastic gradients (see the discussion of the universal computation model in Section 3). It means they will calculate the first $S=\max\{\left\lceil\nicefrac{{\sigma^{2}}}{{\varepsilon}}\right\rceil,1\}$ stochastic gradients after at most

$$ $\displaystyle\bar{t}_{1}:=\min\left\{t\geq 0\,:\,\sum_{i=1}^{n}\left\lfloor V_ {i}(t)\right\rfloor\geq\max\left\{\left\lceil\frac{\sigma^{2}}{\varepsilon} \right\rceil,1\right\}\right\},$ $$

seconds, where the $\min$ operation is well-defined due to Lemma F.1. After at most $\bar{t}_{1}$ seconds, the algorithm stops the calculations in the workers and asks them to start the calculation of a new batch of $S$ stochastic gradients that will take at most

$$ $\displaystyle\bar{t}_{2}:=\min\left\{t\geq 0\,:\,\sum_{i=1}^{n}\left\lfloor V_ {i}(t)-V_{i}(\bar{t}_{1})\right\rfloor\geq\max\left\{\left\lceil\frac{\sigma^{ 2}}{\varepsilon}\right\rceil,1\right\}\right\},$ $$

seconds because $\left\lfloor V_{i}(t)-V_{i}(\bar{t}_{1})\right\rfloor$ is the number of stochastic gradients that worker $i$ can calculate from time $\bar{t}_{1}$ to time $t$ (see (5)). Using the same reasoning, it will take at most $\bar{t}_{\left\lceil\frac{24L\Delta}{\varepsilon}\right\rceil}$ seconds to finish all calculations.
∎

###### Proof.

## Appendix B Proof of Theorem 6.4

See 6.4

###### Proof.

From Theorem 6.3, we know that Method 4 converges after

$$ $\displaystyle\left\lceil\frac{24L\Delta}{\varepsilon}\right\rceil$ $$

iterations. In the first iteration, the algorithm waits for the moment when

$$ $\displaystyle\frac{1}{n}\sum_{i=1}^{n}\frac{1}{B_{i}}\leq\frac{n}{S}.$ $$

Since

$$ $\displaystyle S=\max\left\{\left\lceil\frac{\sigma^{2}}{\varepsilon}\right \rceil,n\right\}\leq\max\left\{\frac{2\sigma^{2}}{\varepsilon},n\right\},$ $$

we get

$$ $\displaystyle\frac{n}{S}\geq\min\left\{\frac{n\varepsilon}{2\sigma^{2}},1 \right\}.$ $$

According to the computation model, after $t$ seconds, worker $i$ can calculate

$$ $\displaystyle B_{i}=\left\lfloor V_{i}(t)\right\rfloor$ $$

stochastic gradients meaning that

$$ $\displaystyle\frac{1}{n}\sum_{i=1}^{n}\frac{1}{B_{i}}=\frac{1}{n}\sum_{i=1}^{n }\frac{1}{\left\lfloor V_{i}(t)\right\rfloor}.$ $$

Therefore, the algorithm exits the first iteration after at most

$$ $\displaystyle\bar{t}_{1}$ $\displaystyle:=\min\left\{t\geq 0\,:\,\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\left \lfloor V_{i}(t)\right\rfloor}\leq\min\left\{\frac{n\varepsilon}{2\sigma^{2}}, 1\right\}\right\}$ $\displaystyle=\min\left\{t\geq 0\,:\,\left(\frac{1}{n}\sum_{i=1}^{n}\frac{1}{ \left\lfloor V_{i}(t)\right\rfloor}\right)^{-1}\geq\max\left\{\frac{2\sigma^{2 }}{n\varepsilon},1\right\}\right\}$ $$

seconds, where we use Lemma F.1.

The second iteration will start at least after $\bar{t}_{1}$ seconds. Since, after $t$ seconds, worker $i$ can calculate at least

$$ $\displaystyle\left\lfloor V_{i}(t)-V_{i}(\bar{t}_{1})\right\rfloor$ $$

stochastic gradients in the second iteration. Using the same reasoning as in the first iteration, the algorithm exits the second iteration after at most

$$ $\displaystyle\bar{t}_{2}:=\min\left\{t\geq 0\,:\,\left(\frac{1}{n}\sum_{i=1}^{ n}\frac{1}{\left\lfloor V_{i}(t)-V_{i}(\bar{t}_{1})\right\rfloor}\right)^{-1} \geq\max\left\{\frac{2\sigma^{2}}{n\varepsilon},1\right\}\right\}$ $$

seconds. We can continue and show that it will take at most $\bar{t}_{\left\lceil\frac{24L\Delta}{\varepsilon}\right\rceil}$ seconds to finish all calculations.
∎

###### Proof.

## Appendix C Proof of Theorem 5.1

In our lower bound proofs, we employ the following well-known function.
Let us define

$$ $\displaystyle\textnormal{prog}(x):=\max\{i\geq 0\,|\,x_{i}\neq 0\}\quad(x_{0} \equiv 1).$ $$

For any $T\in\mathbb{N},$ Carmon et al. (); Arjevani et al. () define a function $F_{T}\,:\,\mathbb{R}^{T}\to\mathbb{R}$ such that

$$ $\displaystyle F_{T}(x)=-\Psi(1)\Phi(x_{1})+\sum_{i=2}^{T}\left[\Psi(-x_{i-1}) \Phi(-x_{i})-\Psi(x_{i-1})\Phi(x_{i})\right],$ (20) $$

where $x_{i}$ is the $i$^th coordinate of a vector $x\in\mathbb{R}^{d}$ and

$$ $\displaystyle\Psi(x)=\begin{cases}0,&x\leq 1/2,\\ \exp\left(1-\frac{1}{(2x-1)^{2}}\right),&x\geq 1/2,\end{cases}\quad\textnormal {and}\quad\Phi(x)=\sqrt{e}\int_{-\infty}^{x}e^{-\frac{1}{2}t^{2}}dt.$ $$

In the proofs, we will only use the results from the following lemma.

###### Lemma C.1 ( Carmon et al. ( 2020 ); Arjevani et al. ( 2022 ) ) .

The function $F_{T}$ satisfies:

- 1.
$F_{T}(0)-\inf_{x\in\mathbb{R}^{T}}F_{T}(x)\leq\Delta^{0}T,$ where $\Delta^{0}=12.$
- 2.
The function $F_{T}$ is $l_{1}$–smooth, where $l_{1}=152.$
- 3.
For all $x\in\mathbb{R}^{T},$ $\left\|\nabla F_{T}(x)\right\|_{\infty}\leq\gamma_{\infty},$ where $\gamma_{\infty}=23.$
- 4.
For all $x\in\mathbb{R}^{T},$ $\textnormal{prog}(\nabla F_{T}(x))\leq\textnormal{prog}(x)+1.$
- 5.
For all $x\in\mathbb{R}^{T},$ if $\textnormal{prog}(x)<T,$ then $\left\|\nabla F_{T}(x)\right\|>1.$

We are ready to prove our first main result.

See 5.1

###### Proof.

(Part 1). In the first part of the proof we use the same idea as in (Carmon et al., ; Arjevani et al., ; Tyurin & Richtárik, ; Huang et al., ; Lu & De Sa, ).
We will construct a “worst-case” function. Let us take any $\lambda>0,$ $T\in\mathbb{N}$ and take the function

$$ $f(x):=\frac{L\lambda^{2}}{l_{1}}F_{T}\left(\frac{x}{\lambda}\right).$ $$

We have to show that $f$ satisfy Assumptions 1.1, 1.2 and $f(0)-f^{*}\leq\Delta.$ Indeed,

$$ $\displaystyle\left\|\nabla f(x)-\nabla f(y)\right\|=\frac{L\lambda}{l_{1}} \left\|\nabla F_{T}\left(\frac{x}{\lambda}\right)-\nabla F_{T}\left(\frac{y}{ \lambda}\right)\right\|\leq L\lambda\left\|\frac{x}{\lambda}-\frac{y}{\lambda} \right\|=L\left\|x-y\right\|\quad\forall x,y\in\mathbb{R}^{d},$ $$

where $l_{1}$–smoothness of $F_{T}$ (Lemma C.1).
Let us take

$$ $T=\left\lfloor\frac{\Delta l_{1}}{L\lambda^{2}\Delta^{0}}\right\rfloor,$ $$

then

$$ $\displaystyle f(0)-\inf_{x\in\mathbb{R}^{T}}f(x)=\frac{L\lambda^{2}}{l_{1}}(F_ {T}\left(0\right)-\inf_{x\in\mathbb{R}^{T}}F_{T}(x))\leq\frac{L\lambda^{2} \Delta^{0}T}{l_{1}}\leq\Delta.$ $$

Next, we construct a stochastic gradient mapping that satisfy Assumption 1.3. As in (Arjevani et al., ), for all $i\in[n],$ let us take

$$ $\displaystyle[g_{i}(x;\xi,t)]_{j}:=[\nabla f(x)]_{j}\left(1+\mathbbm{1}\left[j >\textnormal{prog}(x)\right]\left(\frac{\xi_{j,m}}{p}-1\right)\right)\quad \forall x\in\mathbb{R}^{T},$ (21) $$

and $\{\xi_{j}\}$ are i.i.d. from $\textnormal{Bernouilli}(p)$ for all $i\in[n],$ where $p\in(0,1].$ We denote $[v]_{j}$ as the $j$^th index of a vector $v\in\mathbb{R}^{T}.$
This mapping satisfy Assumption 1.3 since

$$ ${\mathbb{E}}\left[[g_{i}(x;\xi,t)]_{j}\right]=[\nabla f(x)]_{j}\left(1+ \mathbbm{1}\left[i>\textnormal{prog}(x)\right]\left(\frac{{\mathbb{E}}\left[ \xi_{j}\right]}{p}-1\right)\right)=[\nabla f(x)]_{j}$ $$

for all $j\in[T],$ and

$$ $\displaystyle{\mathbb{E}}\left[\left\|g_{i}(x;\xi,t)-\nabla f(x)\right\|^{2} \right]\leq\max_{j\in[T]}\left|[\nabla f(x)]_{j}\right|^{2}{\mathbb{E}}\left[ \left(\frac{\xi_{j}}{p}-1\right)^{2}\right]$ $$

because the difference is non-zero only in one coordinate. Therefore

$$ $\displaystyle{\mathbb{E}}\left[\left\|g_{i}(x;\xi,t)-\nabla f(x)\right\|^{2}\right]$ $\displaystyle\leq\frac{\left\|\nabla f(x)\right\|_{\infty}^{2}(1-p)}{p}=\frac{ L^{2}\lambda^{2}\left\|\nabla F_{T}\left(\frac{x}{\lambda}\right)\right\|_{ \infty}^{2}(1-p)}{l_{1}^{2}p}$ $\displaystyle\leq\frac{L^{2}\lambda^{2}\gamma_{\infty}^{2}(1-p)}{l_{1}^{2}p} \leq\sigma^{2},$ $$

where we take into account Lemma C.1 and choose

$$ $p=\min\left\{\frac{L^{2}\lambda^{2}\gamma_{\infty}^{2}}{\sigma^{2}l_{1}^{2}},1 \right\}.$ $$

We also choose

$$ $\lambda=\frac{\sqrt{2\varepsilon}l_{1}}{L}$ $$

to ensure that

$$ $\displaystyle\left\|\nabla f(x)\right\|^{2}=\frac{L^{2}\lambda^{2}}{l_{1}^{2}} \left\|\nabla F_{T}\left(\frac{x}{\lambda}\right)\right\|^{2}=2\varepsilon \left\|\nabla F_{T}\left(\frac{x}{\lambda}\right)\right\|^{2}$ $$

for all $x\in\mathbb{R}^{T}.$ Using Lemma C.1, if $\textnormal{prog}(x)<T,$ then $\left\|\nabla F_{T}(x)\right\|>1.$ Thus

$$ $\displaystyle\left\|\nabla f(x)\right\|^{2}>2\varepsilon\mathbbm{1}\left[ \textnormal{prog}(x)<T\right]$ (22) $$

Using the choice of $\lambda,$ one can easily show that

$$ $\displaystyle T=\left\lfloor\frac{\Delta L}{2\varepsilon l_{1}\Delta^{0}}\right\rfloor$ (23) $$

and

$$ $\displaystyle p=\min\left\{\frac{2\varepsilon\gamma_{\infty}^{2}}{\sigma^{2}}, 1\right\}.$ (24) $$

The inequality (22) implies

$$ $\displaystyle\inf_{k\in S_{t}}\left\|\nabla f(x^{k})\right\|^{2}>2\varepsilon \inf_{k\in S_{t}}\mathbbm{1}\left[\textnormal{prog}(x^{k})<T\right],$ (25) $$

where $\{x^{k}\}_{k=0}^{\infty}$ are defined in Protocol 2.
(Part 2). The last inequality in (25) says that if an algorithm wants to find an $\varepsilon$–stationary point of the function $f,$ then it is necessary to return a point $x^{k}$ such that the last coordinate of $x^{k}$ is not zero. All algorithms start with the point $x^{0}=0,$ and the only way to discover a new non-zero coordinate is through the oracles (8) since the family of algorithms $\mathcal{A}_{\textnormal{zr}}$ is zero-respecting. The function $f$ is a zero-chain (Arjevani et al., ) meaning that $\textnormal{prog}(\nabla F_{T}(x))\leq\textnormal{prog}(x)+1$ for all $x\in\mathbb{R}^{T}$ (Lemma C.1). Therefore, the oracles can reveal the next non-zero coordinate with the probability $p$ due the construction (21).

For all $i\in[n],$ oracle $O_{i}$ emulates the behavior of a real computation process that can calculate at most

$$ $\displaystyle\left\lfloor V_{i}(t_{1})-V_{i}(t_{0})\right\rfloor$ $$

stochastic gradients in the time interval $[t_{0},t_{1}].$ Effectively, the condition $V_{i}(t)-V_{i}(s_{t})\geq 1$ ensures that sufficient time passes before worker $i$ receives a new stochastic gradient.

All workers work in parallel and ask the oracles to return new stochastic gradients. Thus, for all $t\geq 0,$ in the interval $[0,t],$ all workers can can calculate at most

$$ $\displaystyle\sum_{i=1}^{n}\left\lfloor V_{i}(t)\right\rfloor$ $$

stochastic gradients. At the same time, the stochastic mapping (21) is constructed so that the last potentially non-zero coordinate is zeroed out using i.i.d. Bernoulli random variables with the parameter $p$. All workers have to wait for the moment when one of the oracles samples a Bernoulli random variables equals to $1.$ Therefore, the workers have to calculate at least $\eta_{1}$ stochastic gradients, where $\eta_{1}$ is a *geometric random variable* with the parameter $p$. Finally, we can conclude that the workers can progress to the first non-zero coordinate after at least

$$ $\displaystyle t_{1}:=\inf\left\{t\geq 0\,:\,\sum_{i=1}^{n}\left\lfloor V_{i}(t )\right\rfloor\geq\eta_{1}\right\}=\min\left\{t\geq 0\,:\,\sum_{i=1}^{n}\left \lfloor V_{i}(t)\right\rfloor\geq\eta_{1}\right\}$ $$

seconds, where we use Lemma F.1. In order to get a 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 can progress to the second non-zero coordinate after at least

$$ $\displaystyle t_{2}:=\min\left\{t\geq 0\,:\,\sum_{i=1}^{n}\left\lfloor V_{i}(t )-V_{i}(t_{1})\right\rfloor\geq\eta_{2}\right\}$ $$

seconds, where $\eta_{2}$ is a *geometric random variable* with the parameter $p.$ Because worker $i$ first gets a point with the progress equals to one, which takes at least $t_{1}$ seconds, and then can calculate at most

$$ $\displaystyle\left\lfloor V_{i}(t)-V_{i}(t_{1})\right\rfloor$ $$

stochastic gradients by a time $t\geq 0.$ We continue: let us define

$$ $\displaystyle t_{i}:=\min\left\{t\geq 0\,:\,\sum_{i=1}^{n}\left\lfloor V_{i}(t )-V_{i}(t_{i-1})\right\rfloor\geq\eta_{i}\right\}\qquad(t_{0}\equiv 0),$ $$

and take i.i.d. $\{\eta_{i}\}_{i=1}^{T}$ geometric random variables with the probability $p.$ We can conclude that all algorithms from $\mathcal{A}_{\textnormal{zr}}$ require at least $t_{T}$ seconds to get a point where the $T$^th coordinate is non-zero.
(Part 3).
It is left to find a concentration bound for $t_{T}.$ Using Lemma F.2 with $p_{i,\eta_{1},\dots,\eta_{i-1}}=p$ for all $i\in[T],$ we have

$$ $\displaystyle\mathbb{P}\left(\sum_{i=1}^{T}\mathbbm{1}\left[\eta_{i}>\frac{1}{ 4p}\right]\leq\frac{T}{2}+\log\delta\right)\leq\delta$ $$

for all $\delta\in(0,1]$ (Note: Clearly, Lemma F.2 is too redundant for the current case when $\{\eta_{i}\}_{i=1}^{T}$ are i.i.d., but we will use the lemma in other proof where the generality is justified).

Since

$$ $\displaystyle\frac{T}{2}+\log\frac{1}{2}\geq\left\lfloor\frac{T-1}{2}\right\rfloor.$ $$

With a probability at least $\nicefrac{{1}}{{2}},$ there exist $\left\lfloor\frac{T-1}{2}\right\rfloor$ indices such that $\eta_{i}>\frac{1}{4p},$ i.e.,

$$ $\displaystyle\left|\left\{i\in[T]\,\middle|\,\eta_{i}>\frac{1}{4p}\right\} \right|\geq\left\lfloor\frac{T-1}{2}\right\rfloor.$ $$

With a probability at least $\nicefrac{{1}}{{2}},$ there exist $1\leq j_{1}<j_{2}<\dots<j_{\left\lfloor\frac{T-1}{2}\right\rfloor}\leq T$ such that $\eta_{j_{k}}>\frac{1}{4p}$ for all $k\in\left[\left\lfloor\frac{T-1}{2}\right\rfloor\right].$ Using a proof by induction, let us show that

$$ $\displaystyle t_{j_{k}}\geq\underline{t}_{k}:=\min\left\{t\geq 0\,:\,\sum_{i=1 }^{n}\left\lfloor V_{i}(t)-V_{i}(\underline{t}_{k-1})\right\rfloor\geq\frac{1} {4p}\right\}\qquad(\underline{t}_{0}=0)$ (26) $$

for all $k\in\left[\left\lfloor\frac{T-1}{2}\right\rfloor\right].$

Recall the definition of $t_{j_{1}}.$ Using it, we have

$$ $\displaystyle t_{j_{1}}=\min\left\{t\geq 0\,:\,\sum_{i=1}^{n}\left\lfloor V_{i }(t)-V_{i}(t_{j_{1}-1})\right\rfloor\geq\eta_{j_{1}}\right\}.$ $$

Using $V_{i}(t_{j_{1}-1})\geq 0$ and $\eta_{j_{1}}\geq\frac{1}{4p},$ we get

$$ $\displaystyle\sum_{i=1}^{n}\left\lfloor V_{i}(t)\right\rfloor\geq\sum_{i=1}^{n }\left\lfloor V_{i}(t)-V_{i}(t_{j_{1}-1})\right\rfloor\geq\eta_{j_{1}}\geq \frac{1}{4p}$ $$

and

$$ $\displaystyle t_{j_{1}}\geq\underline{t}_{1}=\min\left\{t\geq 0\,:\,\sum_{i=1} ^{n}\left\lfloor V_{i}(t)\right\rfloor\geq\frac{1}{4p}\right\}.$ $$

Thus, we have proved the base case. Assume that (26) holds for $k-1.$ Note that

$$ $\displaystyle t_{j_{k}}=\min\left\{t\geq 0\,:\,\sum_{i=1}^{n}\left\lfloor V_{i }(t)-V_{i}(t_{j_{k}-1})\right\rfloor\geq\eta_{j_{k}}\right\}.$ $$

Using $\eta_{j_{k}}\geq\frac{1}{4p},$ $t_{j_{k}-1}\geq t_{j_{(k-1)}},$ the induction assumption $t_{j_{(k-1)}}\geq\underline{t}_{k-1},$ and the fact that the functions $\{V_{i}\}$ are non-decreasing, we get

$$ $\displaystyle V_{i}(t_{j_{k}-1})\geq V_{i}(t_{j_{(k-1)}})\geq V_{i}(\underline {t}_{k-1})$ $$

and

$$ $\displaystyle\sum_{i=1}^{n}\left\lfloor V_{i}(t)-V_{i}(\underline{t}_{k-1}) \right\rfloor\geq\sum_{i=1}^{n}\left\lfloor V_{i}(t)-V_{i}(t_{j_{k}-1})\right \rfloor\geq\eta_{j_{k}}\geq\frac{1}{4p}.$ $$

Therefore

$$ $\displaystyle t_{j_{k}}\geq\underline{t}_{k}=\min\left\{t\geq 0\,:\,\sum_{i=1} ^{n}\left\lfloor V_{i}(t)-V_{i}(\underline{t}_{k-1})\right\rfloor\geq\frac{1}{ 4p}\right\}.$ $$

In total, with a probability at least $\nicefrac{{1}}{{2}},$ due to (23) and (24), we have

$$ $\displaystyle t_{T}\geq t_{j_{\left\lfloor\frac{T-1}{2}\right\rfloor}}\geq \underline{t}_{\left\lfloor\frac{T-1}{2}\right\rfloor}\geq\underline{t}_{\left \lfloor c_{1}\times\frac{L\Delta}{\varepsilon}\right\rfloor},$ $$

where

$$ $\displaystyle\underline{t}_{k}:=\min\left\{t\geq 0\,:\,\sum_{i=1}^{n}\left \lfloor V_{i}(t)-V_{i}(\underline{t}_{k-1})\right\rfloor\geq c_{2}\times\max \left\{\left\lceil\frac{\sigma^{2}}{\varepsilon}\right\rceil,1\right\}\right\} \qquad(\underline{t}_{0}=0)$ (27) $$

and $c_{1},c_{2}$ are universal constants. Recall that $t_{T}$ is a necessary number of seconds to get a point where the $T$^th coordinate is non-zero. Due to (25),

$$ $\displaystyle{\mathbb{E}}\left[\inf_{k\in S_{t}}\left\|\nabla f(x^{k})\right\| ^{2}\right]>2\varepsilon\mathbb{P}\left(t_{T}>t\right)\geq 2\varepsilon\mathbb {P}\left(t_{T}\geq\underline{t}_{\left\lfloor c_{1}\times\frac{L\Delta}{ \varepsilon}\right\rfloor}\right)\geq\varepsilon$ $$

for

$$ $\displaystyle t=\frac{1}{2}\times\underline{t}_{\left\lfloor c_{1}\times\frac{ L\Delta}{\varepsilon}\right\rfloor}.$ $$

The first inequality follows from the fact that if $t_{T}>t,$ then the set $S_{t}:=\left\{k\in\mathbb{N}_{0}\,|\,t^{k}\leq t\right\}$ contains the indices of iterations from Protocol 2 where all returned by the algorithm points have $\textnormal{prog}(\cdot)$ less than $T.$
∎

###### Lemma C.1 ( Carmon et al. ( 2020 ); Arjevani et al. ( 2022 ) ) .

###### Proof.

## Appendix D Proof of Theorem 6.1

See 6.1

###### Proof.

As in Theorem 5.1, we base our proof on the function $F_{T}(x)$ from Section C. Let us fix any algorithm $A\in\mathcal{A}_{\textnormal{zr}}.$
First, we define $S\in\mathbb{N}$ functions such that, for all $j\in[S],$ we have $h_{j}(x)\,:\,\mathbb{R}^{S\times T}\to\mathbb{R}$ and

$$ $\displaystyle h_{j}(x)=\frac{nL\lambda^{2}}{l_{1}}F_{T}\left(\frac{x_{j}}{ \lambda}\right),$ (28) $$

where $T,$ $S,$ and $\lambda$ are defined later. We assume that $x=[x_{1},\dots,x_{S}]\in\mathbb{R}^{S\times T}.$ We define $x_{j}\in\mathbb{R}^{T}$ as the $j$^th block of a vector $x=[x_{1},\dots,x_{S}]\in\mathbb{R}^{S\times T}.$ The function $h_{j}$ depends only on a subset of variables $x_{j}$ from $x.$ We construct a function $f\,:\,\mathbb{R}^{S\times T}\to\mathbb{R}$ such that

$$ $\displaystyle f(x)=\frac{1}{n}\sum_{i=1}^{S}h_{i}(x).$ (29) $$

While the final structure of the local stochastic functions $f_{i}$ is not yet defined, during the proof, we will ensure that (29) holds.

(Step 1: $f\in\mathcal{F}_{\Delta,L}$)
First, we show that $f$ satisfies Assumptions 1.1, 1.2 and $f(0)-f^{*}\leq\Delta.$ Let us show that the function $f$ is $L$-smooth. Indeed, we have

$$ $\displaystyle\left\|\nabla f(x)-\nabla f(y)\right\|^{2}$ $\displaystyle=\frac{1}{n^{2}}\left\|\sum_{i=1}^{S}\left(\nabla h_{i}(x)-\nabla h _{i}(y)\right)\right\|^{2}=\frac{1}{n^{2}}\sum_{i=1}^{S}\left\|\nabla h_{i}(x) -\nabla h_{i}(y)\right\|^{2}$ $\displaystyle=\frac{1}{n^{2}}\sum_{i=1}^{S}\left\|\frac{nL\lambda}{l_{1}} \nabla F_{T}\left(\frac{x_{i}}{\lambda}\right)-\frac{nL\lambda}{l_{1}}\nabla F _{T}\left(\frac{y_{i}}{\lambda}\right)\right\|_{i}^{2},$ $$

where $\left\|\cdot\right\|_{j}$ is the Euclidean norm w.r.t. $j$^th block. Then,

$$ $\displaystyle\left\|\nabla f(x)-\nabla f(y)\right\|^{2}$ $\displaystyle=\frac{L^{2}\lambda^{2}}{l_{1}^{2}}\sum_{i=1}^{S}\left\|\nabla F_ {T}\left(\frac{x_{i}}{\lambda}\right)-\nabla F_{T}\left(\frac{y_{i}}{\lambda} \right)\right\|_{i}^{2}\leq L^{2}\sum_{i=1}^{S}\left\|x_{i}-y_{i}\right\|_{i}^ {2}=L^{2}\left\|x-y\right\|^{2},$ $$

where the last inequality due to Lemma C.1.
Let us take

$$ $\displaystyle T=\left\lfloor\frac{\Delta l_{1}}{L\lambda^{2}S\Delta^{0}}\right\rfloor$ (30) $$

then

$$ $\displaystyle f(0)-\inf_{x\in\mathbb{R}^{S\times T}}f(x)=\frac{1}{n}\sum_{i=1} ^{S}\frac{nL\lambda^{2}}{l_{1}}(F_{T}\left(0\right)-\inf_{x\in\mathbb{R}^{T}}F _{T}(x))\leq\frac{L\lambda^{2}S\Delta^{0}T}{l_{1}}\leq\Delta,$ $$

where the first inequality due to Lemma C.1.

(Step 2: Construction of local functions $f_{i}$)
Each function $h_{i}(x)$ depends only on $T$ coordinates of the $i$^th block. We split these $T$ coordinates into $\bar{T}+1$ groups with $\bar{T}:=\left\lfloor\nicefrac{{T}}{{K}}\right\rfloor,$ where we choose $K$ later.
For all $w\in[\bar{T}+1],$ let us take any

$$ $\displaystyle s_{w,0}\equiv 1\leq s_{w,1}\leq\dots\leq s_{w,n-1}\leq s_{w,n} \equiv S+1.$ (31) $$

It is convenient to define the length of each segment: $a_{w,i}:=s_{w,i}-s_{w,(i-1)}$ for all $w\in[\bar{T}+1]$ and $i\in[n].$ Also, we take any times

$$ $\displaystyle\bar{t}_{0}\equiv 0\leq\bar{t}_{1}\leq\dots\leq\bar{t}_{\bar{T}} \leq\bar{t}_{\bar{T}+1}\equiv\infty$ (32) $$

associated with the coordinates’ groups. We construct functions in the following way. For all $i\in[n],$ we define

$$ $\displaystyle\widehat{f}_{i}(x):=\sum_{j=s_{1,(i-1)}}^{s_{1,i}-1}\left(-\Psi(1 )\Phi(x_{j,1})+\dots+\Psi(-x_{j,K-1})\Phi(-x_{j,K})-\Psi(x_{j,K-1})\Phi(x_{j,K })\right)$ $\displaystyle\quad+\sum_{j=s_{2,(i-1)}}^{s_{2,i}-1}\left(\Psi(-x_{j,K})\Phi(-x _{j,K+1})-\Psi(x_{j,K})\Phi(x_{j,K+1})+\dots\right.$ $\displaystyle\qquad\qquad\qquad\quad+\left.\Psi(-x_{j,2K-1})\Phi(-x_{j,2K})- \Psi(x_{j,2K-1})\Phi(x_{j,2K})\right)$ $\displaystyle\quad+\dots$ $\displaystyle\quad+\sum_{j=s_{\bar{T},(i-1)}}^{s_{\bar{T},i}-1}\left(\Psi(-x_{ j,(\bar{T}-1)K})\Phi(-x_{j,(\bar{T}-1)K+1})-\Psi(x_{j,(\bar{T}-1)K})\Phi(x_{j, (\bar{T}-1)K+1})+\dots\right.$ $\displaystyle\qquad\qquad\qquad\quad+\left.\Psi(-x_{j,\bar{T}K-1})\Phi(-x_{j, \bar{T}K})-\Psi(x_{j,\bar{T}K-1})\Phi(x_{j,\bar{T}K})\right)$ $\displaystyle\quad+\sum_{j=s_{\bar{T}+1,(i-1)}}^{s_{\bar{T}+1,i}-1}\left(\Psi( -x_{j,\bar{T}K})\Phi(-x_{j,\bar{T}K+1})-\Psi(x_{j,\bar{T}K})\Phi(x_{j,\bar{T}K +1})+\dots\right.$ $\displaystyle\qquad\qquad\qquad\quad+\left.\Psi(-x_{j,T-1})\Phi(-x_{j,T})-\Psi (x_{j,T-1})\Phi(x_{j,T})\right)$ $$

and

$$ $\displaystyle f_{i}(x):=\frac{nL\lambda^{2}}{l_{1}}\widehat{f}_{i}\left(\frac{ x}{\lambda}\right),$ $$

where $x_{j,i}$ is the $i$^th coordinate of $x_{j}\in\mathbb{R}^{T}.$

Let us explain the idea. For all $j\in[S],$ we take the function $h_{j}$ from (28), which consists of $T$ parts with the structure $\Psi(-x_{j,\cdot})\Phi(-x_{j,\cdot})-\Psi(x_{j,\cdot})\Phi(x_{j,\cdot}),$ and distribute these parts between the workers according to the predefined segments $\{s_{w,i}\}.$ The first $K$ parts of the function $h_{j}$ will be stored in worker $i_{1}$ such that $s_{1,(i_{1}-1)}\leq j<s_{1,i_{1}},$ the second $K$ parts will be stored in worker $i_{2}$ such that $s_{2,(i_{2}-1)}\leq j<s_{2,i_{2}},$ and so on. One can easily show that $\sum_{j=1}^{S}h_{j}=\sum_{i=1}^{n}f_{i}.$
(Step 3: Time-dependent stochastic oracles)
We now construct a stochastic oracle. Let us take

$$ $\displaystyle p_{w,i}:=\min\left\{\frac{a_{w,i}n^{2}L^{2}\lambda^{2}\gamma_{ \infty}^{2}}{\sigma^{2}l_{1}^{2}},1\right\}$ (33) $$

for all $w\in[\bar{T}+1],i\in[n].$
The stochastic mapping takes a point $x,$ a random variable $\xi,$ a time $t,$ and returns

$$ $\displaystyle[g_{i}(x;\xi,t)]_{j,m}:=[\nabla f_{i}(x)]_{j,m}\times$ (34) $\displaystyle\times\left(1+\mathbbm{1}\left[m>\textnormal{prog}(x_{j})\wedge \left\lfloor\frac{m-1}{K}\right\rfloor+1=w(t)\right]\left(\frac{\xi_{j,m}}{p_{ w(t),i}}-1\right)\right)\quad\forall x\in\mathbb{R}^{S\times T},$ $$

where $[x]_{j,m}$ is the $m$^th coordinate of the $j$^th block of $x\in\mathbb{R}^{S\times T},$ $\{\xi_{j,m}\}_{j,m}$ are i.i.d. from $\textnormal{Bernoulli}(p_{w(t),i}),$ and $w(t)\in[\bar{T}]$ is the index such that $\bar{t}_{(w(t)-1)}\leq t<\bar{t}_{w(t)}.$

The idea is almost the same as in (Arjevani et al., ): we also zero out the last potentially non-zero coordinate with the probability $p_{w(t),i}.$ However, we only zero out a coordinate if it belongs to the parts from the set $\{(K-1)w(t)+1,\dots,Kw(t)\},$ where $w(t)$ is associated with the current time interval $[\bar{t}_{(w(t)-1)},\bar{t}_{w(t)})$ where the current time $t$ belongs to.

Then, $g_{i}(x;\xi,t)$ is unbiased because ${\mathbb{E}}_{\xi}\left[\left(\frac{\xi_{j,m}}{p_{w(t),i}}-1\right)\right]=0$ and

$$ $\displaystyle{\mathbb{E}}_{\xi}\left[\left\|g_{i}(x;\xi,t)-\nabla f_{i}(x) \right\|^{2}\right]$ $\displaystyle\leq\sum_{j=s_{w(t),(i-1)}}^{s_{w(t),i}-1}\frac{n^{2}L^{2}\lambda ^{2}\left\|\nabla F_{T}\left(\frac{x_{j}}{\lambda}\right)\right\|_{\infty}^{2} (1-p_{w(t),i})}{l_{1}^{2}p_{w(t),i}}$ $$

because, due the condition $\left\lfloor\frac{m-1}{K}\right\rfloor+1=w(t),$ we only consider the blocks from the sum $\sum_{j=s_{w(t),(i-1)}}^{s_{w(t),i}-1}.$
Using Lemma C.1, we have $\left\|\nabla F_{T}\left(x\right)\right\|_{\infty}^{2}\leq\gamma_{\infty}^{2}$ for all $x\in\mathbb{R}^{T}$ and

$$ $\displaystyle{\mathbb{E}}_{\xi}\left[\left\|g_{i}(x;\xi,t)-\nabla f_{i}(x) \right\|^{2}\right]$ $\displaystyle\leq\frac{a_{w(t),i}n^{2}L^{2}\lambda^{2}\gamma_{\infty}^{2}(1-p_ {w(t),i})}{l_{1}^{2}p_{w(t),i}}\leq\sigma^{2},$ $$

where the last inequality follows from the choice of $p_{w,i}$ in (33).

(Step 4: Analysis of Protocol)

Using the definition of $f,$ we get

$$ $\displaystyle\left\|\nabla f(x)\right\|^{2}$ $\displaystyle=\frac{1}{n^{2}}\sum_{i=1}^{S}\left\|\nabla h_{i}(x)\right\|^{2}= \sum_{i=1}^{S}\frac{L^{2}\lambda^{2}}{l_{1}^{2}}\left\|\nabla F_{T}\left(\frac {x_{i}}{\lambda}\right)\right\|^{2}$ $\displaystyle>\frac{L^{2}\lambda^{2}}{l_{1}^{2}}\sum_{i=1}^{S}\mathbbm{1}[ \textnormal{prog}(x_{i})<T]$ (35) $$

for all $x=[x_{1},\dots,x_{n}]\in\mathbb{R}^{T}.$ In the last inequality, we use Lemma C.1. Let us take

$$ $\displaystyle\lambda=\sqrt{\frac{4\varepsilon l_{1}^{2}}{L^{2}S}}.$ (36) $$

to ensure that

$$ $\displaystyle\inf_{k\in S_{t}}\left\|\nabla f(x^{k})\right\|^{2}>\inf_{k\in S_ {t}}\frac{4\varepsilon}{S}\sum_{i=1}^{S}\mathbbm{1}[\textnormal{prog}(x^{k}_{i })<T]\geq\frac{4\varepsilon}{S}\sum_{i=1}^{S}\inf_{k\in S_{t}}\mathbbm{1}[ \textnormal{prog}(x^{k}_{i})<T],$ (37) $$

where $x^{k}$ are points defined in Protocol 2.
Using Markov’s inequality, we get

$$ $\displaystyle\mathbb{P}\left(\frac{4\varepsilon}{S}\sum_{i=1}^{S}\inf_{k\in S_ {t}}\mathbbm{1}[\textnormal{prog}(x_{i}^{k})<T]\leq 2\varepsilon\right)$ (38) $\displaystyle=\mathbb{P}\left(\frac{1}{S}\sum_{i=1}^{S}\inf_{k\in S_{t}} \mathbbm{1}[\textnormal{prog}(x_{i}^{k})<T]\leq\frac{1}{2}\right)$ $\displaystyle=\mathbb{P}\left(\frac{1}{S}\sum_{i=1}^{S}\sup_{k\in S_{t}} \mathbbm{1}[\textnormal{prog}(x_{i}^{k})\geq T]\geq\frac{1}{2}\right)$ $\displaystyle\leq 2{\mathbb{E}}\left[\frac{1}{S}\sum_{i=1}^{S}\sup_{k\in S_{t} }\mathbbm{1}[\textnormal{prog}(x_{i}^{k})\geq T]\right]=\frac{2}{S}\sum_{i=1}^ {S}{\mathbb{E}}\left[\sup_{k\in S_{t}}\mathbbm{1}[\textnormal{prog}(x_{i}^{k}) \geq T]\right].$ $$

(Step 5: Bound on the expectations)

In this step of the proof, we fix $j\in[S],$ and consider the function $h_{j}$ from (28).

Recall that worker $i$ can calculate $\left\lfloor V_{i}(t)\right\rfloor$ stochastic gradients by a time $t.$ Therefore, it takes at least

$$ $\displaystyle\min\left\{t\geq 0\,:\,\left\lfloor V_{i}(t)\right\rfloor\geq\eta \right\}\geq V_{i}^{-1}(\eta)$ $$

seconds to calculate $\eta\in\mathbb{N}$ stochastic gradients, where we use the definition (7).

By the construction of the functions $\{f_{i}\},$ the first $K$ parts of $h_{j}$ belong to worker $i_{1,j}$ such that $s_{1,i_{1,j}-1}\leq j<s_{1,i_{1,j}}.$ While the algorithm $A$ is returning times $t^{k}$ such that $\bar{t}_{0}\equiv 0\leq t^{k}<\bar{t}_{1},$ by the construction of the stochastic mapping (34), whenever the algorithm calls oracle $O_{i_{1,j}},$ the oracle zeros out the last potentially non-zero coordinate with the probability $p_{1,i_{1,j}}.$ However, due to the condition $\left\lfloor\frac{m-1}{K}\right\rfloor+1=w(t),$ the stochastic mapping will zero out the first $K$ coordinates only if $t^{k}<\bar{t}_{1}.$ Thus, the time required to progress to the $K$^th coordinate in the block $x_{j}$ is at least

$$ $\displaystyle\hat{t}_{1,j}:=\min\left\{\bar{t}_{1},V^{-1}_{i_{1,j}}\left(\sum_ {v=1}^{K}\eta_{1,i_{1,j},v}\right)\right\}$ $$

seconds, where $\{\eta_{1,i_{1,j},v}\}$ are i.i.d. geometric random variables with the probability $p_{1,i_{1,j}}.$ Because either the algorithm returns $t^{k}\geq\bar{t}_{1},$ or it keeps returning $t^{k}<\bar{t}_{1},$ but then $A$ should calculate at least $\sum_{v=1}^{K}\eta_{1,i_{1,j},v}$ stochastic gradients since the stochastic mapping zeros out the last potentially non-zero coordinate, and $A$ should wait $K$ times for the “lucky” ($\xi=1$) draws of Bernoulli random variables.

Using the same reasoning, for all $w\in[\bar{T}],$ it will take at least

$$ $\displaystyle\hat{t}_{w,j}:=\min\left\{\bar{t}_{w},V^{-1}_{i_{w,j}}\left(\sum_ {v=1}^{K}\eta_{w,i_{w,j},v}+V_{i_{w,j}}(\hat{t}_{w-1,j})\right)\right\}\qquad( \hat{t}_{0,j}\equiv 0)$ (39) $$

seconds to progress to the $w\times K$^th coordinate in the block $x_{j},$
where $\{\eta_{w,i_{w,j},v}\}$ are i.i.d. geometric random variables with the probability $p_{w,i_{w,j}},$ and $i_{w,j}$ is the index of the worker such that $s_{w,i_{w,j}-1}\leq j<s_{w,i_{w,j}}.$
Because either the algorithm returns $t^{k}\geq\bar{t}_{w},$ or it keeps returning $t^{k}<\bar{t}_{w},$ but then $A$ should first progress to the $(w-1)\times K$^th coordinate, which takes at least $\hat{t}_{w-1,j}$ seconds, and then should calculate at least $\sum_{v=1}^{K}\eta_{w,i_{w,j},v}$ stochastic gradients. This will take at least

$$ $\displaystyle\min\left\{t\geq 0\,:\,\left\lfloor V_{i_{w,j}}(t)-V_{i_{w,j}}( \hat{t}_{w-1,j})\right\rfloor\geq\sum_{v=1}^{K}\eta_{w,i_{w,j},v}\right\}$ $\displaystyle\overset{(\textnormal{cont. of }V_{i_{w,j}})}{=}\min\left\{t\geq 0 \,:\,V_{i_{w,j}}(t)-V_{i_{w,j}}(\hat{t}_{w-1,j})=\sum_{v=1}^{K}\eta_{w,i_{w,j} ,v}\right\}$ $\displaystyle\overset{(\ref{eq:inv})}{=}V^{-1}_{i_{w,j}}\left(\sum_{v=1}^{K} \eta_{w,i_{w,j},v}+V_{i_{w,j}}(\hat{t}_{w-1,j})\right)$ $$

seconds.

Using Lemma F.3, with a probability at least $1-\bar{T}e^{-K/2},$ we have

$$ $\displaystyle\sum_{v=1}^{K}\eta_{w,i_{w,j},v}\geq\frac{K}{8p_{w,i_{w,j}}}$ $$

for all $w\in[\bar{T}].$
Using these inequalities and (39), we get

$$ $\displaystyle\hat{t}_{w,j}\geq\min\left\{\bar{t}_{w},V^{-1}_{i_{w,j}}\left( \frac{K}{8p_{w,i_{w,j}}}+V_{i_{w,j}}(\hat{t}_{w-1,j})\right)\right\},$ (40) $$

for all $w\in[\bar{T}].$

Note that $\{\bar{t}_{w}\}_{w=1}^{\bar{T}},$$\{s_{w,i}\}_{w\in[\bar{T}+1],i\in[n]},$ and $S$ are free parameters with the conditions (31) and (32). Due to (33) and (36), we have

$$ $\displaystyle p_{w,i}=\min\left\{\frac{4\varepsilon\gamma_{\infty}^{2}a_{w,i}n ^{2}}{\sigma^{2}S},1\right\}.$ $$

Therefore, we can use Lemma F.4: we can find $\{\bar{t}_{w}\}_{w=1}^{\bar{T}},$$\{s_{w,i}\}_{w\in[\bar{T}+1],i\in[n]},$ and $S$ such that $V^{-1}_{i}\left(\frac{K}{8p_{1,i}}\right)\geq\bar{t}_{1}$ for all $i\in[n].$
With a probability at least $1-\bar{T}e^{-K/2},$ with the chosen parameters, we have

$$ $\displaystyle\hat{t}_{1,j}\geq\min\left\{\bar{t}_{1},V^{-1}_{i_{1,j}}\left( \frac{K}{8p_{1,i_{1,j}}}\right)\right\}\geq\min\left\{\bar{t}_{1},\bar{t}_{1} \right\}=\bar{t}_{1}.$ $$

Using a proof by induction, with a probability at least $1-\bar{T}e^{-K/2},$ let us prove that $\hat{t}_{w,j}\geq\bar{t}_{w}$ for all $w\in[\bar{T}]$ with the parameters from Lemma F.4. The base case has been proved. Assume that

$$ $\hat{t}_{w-1,j}\geq\bar{t}_{w-1},$ $$

then, using (40), we get

$$ $\displaystyle\hat{t}_{w,j}\geq\min\left\{\bar{t}_{w},V^{-1}_{i_{w,j}}\left( \frac{K}{8p_{w,i_{w,j}}}+V_{i_{w,j}}(\hat{t}_{w-1,j})\right)\right\}\geq\min \left\{\bar{t}_{w},V^{-1}_{i_{w,j}}\left(\frac{K}{8p_{w,i_{w,j}}}+V_{i_{w,j}}( \bar{t}_{w-1})\right)\right\}.$ $$

In Lemma F.4, we show that $V^{-1}_{i}\left(\frac{K}{8p_{w,i}}+V_{i}(\bar{t}_{w-1})\right)\geq\bar{t}_{w}$ for all $i\in[n].$ Thus

$$ $\displaystyle\hat{t}_{w,j}\geq\min\left\{\bar{t}_{w},\bar{t}_{w}\right\}=\bar{ t}_{w}.$ $$

(Step 6: Choose a parameter $K$)
In the previous step, we prove that, with a probability at least $1-\bar{T}e^{-K/2},$ the algorithm requires at least $\bar{t}_{\bar{T}}$ seconds to progress to the $K\times\bar{T}$^th coordinate ($K\times\bar{T}\leq T$), where $\bar{t}_{\bar{T}}$ is defined in in the proof of Lemma F.4.

Let us take

$$ $\displaystyle K=\left\lfloor 2\log 4T\right\rfloor,$ $$

then, with a probability at least $3/4,$ the algorithm will require at least $\bar{t}_{\bar{T}}$ seconds to get a non-zero last coordinate in the block $x_{j}.$ Thus

$$ $\displaystyle{\mathbb{E}}\left[\sup_{k\in S_{t}}\mathbbm{1}[\textnormal{prog}( x_{j}^{k})\geq T]\right]\leq\frac{1}{4}$ $$

for all $j\in[n]$ and for all $t\leq\frac{1}{2}\bar{t}_{\bar{T}}.$ We substitute these inequalities to (38) and (37), and get

$$ $\displaystyle\mathbb{P}\left(\frac{4\varepsilon}{S}\sum_{i=1}^{S}\inf_{k\in S_ {t}}\mathbbm{1}[\textnormal{prog}(x_{i}^{k})<T]\leq 2\varepsilon\right)\leq \frac{1}{2}$ $$

and

$$ $\displaystyle{\mathbb{E}}\left[\inf_{k\in S_{t}}\left\|\nabla f(x^{k})\right\| ^{2}\right]>{\mathbb{E}}\left[\frac{4\varepsilon}{S}\sum_{i=1}^{S}\inf_{k\in S _{t}}\mathbbm{1}[\textnormal{prog}(x^{k}_{i})<T]\right]>2\varepsilon\mathbb{P} \left(\frac{4\varepsilon}{S}\sum_{i=1}^{S}\inf_{k\in S_{t}}\mathbbm{1}[ \textnormal{prog}(x_{i}^{k})<T]>2\varepsilon\right)\geq\varepsilon$ $$

for all

$$ $\displaystyle t\leq\frac{1}{2}\widetilde{t}_{\bar{T}}\overset{(\ref{eq: TToceJIF})}{\leq}\frac{1}{2}\bar{t}_{\bar{T}},$ $$

where

$$ $\displaystyle\bar{T}=\left\lfloor\frac{T}{\left\lfloor 2\log 4T\right\rfloor} \right\rfloor\overset{(\ref{eq:luOePAy}),(\ref{eq:JpjVFT})}{\geq}\left\lfloor \frac{c_{1}\times\frac{L\Delta}{\varepsilon}}{\log\frac{L\Delta}{\varepsilon}}\right\rfloor$ $$

for some universal constant $c_{1},$ where we use the assumption $\varepsilon<c^{\prime}L\Delta$ of the theorem. Finally, since $\widetilde{t}_{w}\geq\underline{t}_{w}$ for all $w\in[\bar{T}]$ with the chosen $K,$ where the later sequence is defined in (16),
we can take

$$ $\displaystyle t=\frac{1}{2}\underline{t}_{\left\lfloor\frac{c_{1}\times\frac{L \Delta}{\varepsilon}}{\log\frac{L\Delta}{\varepsilon}}\right\rfloor}.$ $$

∎

###### Proof.

## Appendix E Proof of Theorem 6.2

See 6.2

###### Proof.

We base our proof on the function $F_{T}(x)$ from Section C. Let us fix any algorithm $A\in\mathcal{A}_{\textnormal{zr}}.$
First, we define $S\in\mathbb{N}$ functions such that, for all $j\in[S],$ we have $h_{j}(x)\,:\,\mathbb{R}^{S\times T}\to\mathbb{R}$ and

$$ $\displaystyle h_{j}(x)=\frac{nL\lambda^{2}}{l_{1}}F_{T}\left(\frac{x_{j}}{ \lambda}\right),$ (41) $$

where $T,$ $S,$ and $\lambda$ are defined later. We assume that $x=[x_{1},\dots,x_{S}]\in\mathbb{R}^{S\times T}.$ We define $x_{j}\in\mathbb{R}^{T}$ as the $j$^th block of a vector $x=[x_{1},\dots,x_{S}]\in\mathbb{R}^{S\times T}.$ The function $h_{j}$ depends only on a subset of variables $x_{j}$ from $x.$ We construct a function $f\,:\,\mathbb{R}^{S\times T}\to\mathbb{R}$ such that

$$ $\displaystyle f(x)=\frac{1}{n}\sum_{i=1}^{S}h_{i}(x).$ (42) $$

While the final structure of the local stochastic functions $f_{i}$ is not yet defined, during the proof, we will ensure that (42) holds.

(Step 1: $f\in\mathcal{F}_{\Delta,L}$)
We have to show that $f$ satisfies Assumptions 1.1, 1.2 and $f(0)-f^{*}\leq\Delta.$ This step is exactly the same as in the proof of Theorem 6.1. It is sufficient to take

$$ $\displaystyle T=\left\lfloor\frac{\Delta l_{1}}{L\lambda^{2}S\Delta^{0}}\right\rfloor.$ (43) $$

(Step 2: Construction of local functions $f_{i}$ and stochastic mappings)
Unlike the proof of Theorem 6.1 where the functions are predetermined, in this construction the functions $\{f_{i}\}$ depend on sequences of random variables and are constructed algorithmically in the following way.

For all $w\in[T+1],$ let us take any

$$ $\displaystyle s_{w,0}\equiv 1\leq s_{w,1}\leq\dots\leq s_{w,n-1}\leq s_{w,n} \equiv S+1,$ (44) $$

and define $a_{w,i}:=s_{w,i}-s_{w,(i-1)}.$
We also take any $p_{w,i}>0$ for all $w\in[T],i\in[n],$ and any times

$$ $\displaystyle\bar{t}_{0}\equiv 0\leq\bar{t}_{1}\leq\dots\leq\bar{t}_{T}\leq \bar{t}_{T+1}\equiv\infty$ (45) $$

associated with $\{s_{w,\cdot}\}_{w\in[T+1]}$ and $\{p_{w,\cdot}\}_{w\in[T]}$. We construct the functions $\{f_{i}\}$ using the algorithm below.

Figure: Algorithm 5 “Resisting allocation” of the functions $\{h_{j}\}$

As in the proof of Theorem 6.1, the stochastic mapping takes a point $x,$ a random variable $\xi,$ a time $t,$ and returns

$$ $\displaystyle{}_{j,m}:=\begin{cases}[\nabla f_{i}(x)]_{j,m}\times\frac{\bar{ \xi}_{j}}{p_{w(t),i}},&m=\textnormal{prog}(x_{j})+1\wedge b_{j,m}=(w(t),i),\\ [\nabla f_{i}(x)]_{j,m},&\textnormal{otherwise},\end{cases}$ (46) $$

where $[x]_{j,m}$ is the $m$^th coordinate of the $j$^th block of $x\in\mathbb{R}^{S\times T},$
$\bar{\xi}\equiv(\bar{\xi}_{1},\dots,\bar{\xi}_{S}),$
$\bar{\xi}_{j}$ is the “next” random variable from $\{\xi_{j,(\textnormal{prog}(x_{j})+1),s}\}_{s=1}^{\infty}$ (see Alg. 5),
and $w(t)\in[T]$ is the index such that $\bar{t}_{(w(t)-1)}\leq t<\bar{t}_{w(t)}.$

Let us clarify what we mean by the “next” random variable. In {NoHyper}Line 8 of Alg. 5, we draw an infinite i.i.d. sequence $\{\xi_{j,m,s}\}_{s=1}^{\infty}$ from $\textnormal{Bernoulli}(p_{w,i_{w,j}}).$ For the first time when the mapping $g_{i}$ has to take the “next” random variable from $\{\xi_{j,(\textnormal{prog}(x_{j})+1),s}\}_{s=1}^{\infty},$ it takes $\xi_{j,(\textnormal{prog}(x_{j})+1),1}.$ For the second time, it takes $\xi_{j,(\textnormal{prog}(x_{j})+1),2},$ and so forth.

For all $i\in[n],$ the mapping $g_{i}$ in the oracle $O_{i}$ zeroes out the coordinate $m$ of the gradient $\nabla f_{i}(x)$ corresponding to $m=\textnormal{prog}(x_{j})+1$ (idea is the same as in (Arjevani et al., )). However, we only zero out this coordinate if the corresponding part of the function $h_{j}$ is stored on worker $i$ at the time $t$ (condition $b_{j,m}=(w(t),i)$).

We now explain the idea.
For all $i\in[n],$ deterministically, we have

$$ $\displaystyle f_{i}(x)=\frac{nL\lambda^{2}}{l_{1}}\sum_{j=s_{1,i-1}+1}^{s_{1,i }}-\Psi(1)\Phi\left(\frac{x_{j,1}}{\lambda}\right)+\dots.$ $$

where $x_{j,i}$ is the $i$^th coordinate of $x_{j}\in\mathbb{R}^{T}.$ Thus, the first part $-\Psi(1)\Phi(x_{1})$ of the functions (41) (see (20)) are allocated according to the values $\{s_{1,i}\}.$

As always, we rely on the fact that the algorithm is zero-respecting, meaning that at the beginning, it starts with the point $x^{0}=0.$ While $x^{k}=0,$ it does not matter where we allocate the other parts of the functions $h_{j}.$ The main idea is to decide the allocation based on the random variables $\{\xi_{j,m,s}\}_{s=1}^{\infty}$ from Alg. 5. By the construction of the functions $\{f_{i}\},$ the first part of $h_{j}$ belongs to worker $i_{1,j}$ such that $s_{1,i_{1,j}-1}\leq j<s_{1,i_{1,j}}.$ The oracle $O_{i_{1,j}}$ zeroes out the first coordinate of the $j$^th block of gradients with the probability $p_{1,i_{1,j}}$ (see (46)).

In Alg. 5, we consider two cases:
If $V^{-1}_{i_{1,j}}\left(\eta_{j,1}\right)<\bar{t}_{1},$ then in the next iteration of Alg. 5, we allocate the second part of the function $h_{j}$ to the same worker $i_{1,j},$ i.e.,

$$ $\displaystyle f_{i_{1,j}}(x)\leftarrow f_{i_{1,j}}(x)+\frac{nL\lambda^{2}}{l_{ 1}}\left(\Psi\left(-\frac{x_{j,1}}{\lambda}\right)\Phi\left(-\frac{x_{j,2}}{ \lambda}\right)-\Psi\left(\frac{x_{j,1}}{\lambda}\right)\Phi\left(\frac{x_{j,2 }}{\lambda}\right)\right).$ $$

Otherwise, if $V^{-1}_{i_{1,j}}\left(\eta_{j,1}\right)\geq\bar{t}_{1},$ then we increment the parameter $w$ in Alg. 5 and allocate the second part to worker $i_{2,j}:$

$$ $\displaystyle f_{i_{2,j}}(x)\leftarrow f_{i_{2,j}}(x)+\frac{nL\lambda^{2}}{l_{ 1}}\left(\Psi\left(-\frac{x_{j,1}}{\lambda}\right)\Phi\left(-\frac{x_{j,2}}{ \lambda}\right)-\Psi\left(\frac{x_{j,1}}{\lambda}\right)\Phi\left(\frac{x_{j,2 }}{\lambda}\right)\right),$ $$

where $i_{2,j}$ such that $s_{2,i_{,j}-1}\leq j<s_{2,i_{2,j}}.$

The mapping $g_{i}$ is unbiased and $\sigma^{2}$–variance bounded.
If $m>\textnormal{prog}(x_{j})+1,$ then $[\nabla f_{i}(x)]_{j,m}=0$ deterministically due to Lemma C.1.
If $m=\textnormal{prog}(x_{j})+1$ and $b_{j,m}=(w(t),i),$ then we have to show that

$$ $\displaystyle{\mathbb{E}}_{\bar{\xi}}\left[[\nabla f_{i}(x)]_{j,m}\times\frac{ \bar{\xi}_{j}}{p_{w(t),i}}\right]=[\nabla f_{i}(x)]_{j,m}$ $$

for all $j\in[S],m\in[T].$
Notice that due the construction in Alg. 5, the gradient $\nabla f_{i}(x)$ can depend on $\{\xi_{j,m,s}\}_{s=1}^{\infty}$ since the random variables affect the allocation of parts starting from

$$ $\displaystyle\Psi\left(-\frac{x_{j,m}}{\lambda}\right)\Phi\left(-\frac{x_{j,m+ 1}}{\lambda}\right)-\Psi\left(\frac{x_{j,m}}{\lambda}\right)\Phi\left(\frac{x_ {j,m+1}}{\lambda}\right),$ (47) $\displaystyle\Psi\left(-\frac{x_{j,m+1}}{\lambda}\right)\Phi\left(-\frac{x_{j, m+2}}{\lambda}\right)-\Psi\left(\frac{x_{j,m+1}}{\lambda}\right)\Phi\left( \frac{x_{j,m+2}}{\lambda}\right),$ $\displaystyle\dots$ $\displaystyle\Psi\left(-\frac{x_{j,T-1}}{\lambda}\right)\Phi\left(-\frac{x_{j, T}}{\lambda}\right)-\Psi\left(\frac{x_{j,T-1}}{\lambda}\right)\Phi\left(\frac{ x_{j,T}}{\lambda}\right).$ $$

However, i) the $j$^th block does no depend on $\xi_{j^{\prime},m^{\prime},s^{\prime}}$ with $j^{\prime}\neq j,m^{\prime}\in[T],s^{\prime}\geq 1$ ii) all the previous parts in the $j$^th block depend only on $\{\xi_{j,m^{\prime},s}\}_{m^{\prime}<m,s\geq 1},$ and iii) all the parts from (LABEL:eq:EHtZvQJEAH) are zero because $m=\textnormal{prog}(x_{j})+1.$ Therefore

$$ $\displaystyle{\mathbb{E}}_{\bar{\xi}}\left[[\nabla f_{i}(x)]_{j,m}\times\frac{ \bar{\xi}_{j}}{p_{w(t),i}}\right]$ $\displaystyle\overset{\textnormal{i)}}{=}{\mathbb{E}}_{\bar{\xi}_{j}}\left[[ \nabla f_{i}(x)]_{j,m}\times\frac{\bar{\xi}_{j}}{p_{w(t),i}}\right]$ $\displaystyle\overset{\textnormal{ii), iii)}}{=}[\nabla f_{i}(x)]_{j,m}{ \mathbb{E}}_{\bar{\xi}_{j}}\left[\frac{\bar{\xi}_{j}}{p_{w(t),i}}\right]=[ \nabla f_{i}(x)]_{j,m}.$ $$

For $m=\textnormal{prog}(x_{j})+1$ and $b_{j,m}\neq(w(t),i),$ we have

$$ $\displaystyle{\mathbb{E}}_{\bar{\xi}}\left[[g_{i}(x;\bar{\xi},t)]_{j,m}\right] ={\mathbb{E}}_{\bar{\xi}}\left[[\nabla f_{i}(x)]_{j,m}\right]\overset{ \textnormal{i)}}{=}{\mathbb{E}}_{\bar{\xi}_{j}}\left[[\nabla f_{i}(x)]_{j,m} \right]\overset{\textnormal{ii), iii)}}{=}[\nabla f_{i}(x)]_{j,m}.$ $$

For $m<\textnormal{prog}(x_{j})+1,$ we have

$$ $\displaystyle{\mathbb{E}}_{\bar{\xi}}\left[[g_{i}(x;\bar{\xi},t)]_{j,m}\right] ={\mathbb{E}}_{\bar{\xi}}\left[[\nabla f_{i}(x)]_{j,m}\right]\overset{ \textnormal{i)}}{=}{\mathbb{E}}_{\bar{\xi}_{j}}\left[[\nabla f_{i}(x)]_{j,m} \right]\overset{\textnormal{ii)}}{=}[\nabla f_{i}(x)]_{j,m}.$ $$

Using the same reasoning, we have

$$ $\displaystyle{\mathbb{E}}_{\bar{\xi}}\left[\left\|g_{i}(x;\bar{\xi},t)-\nabla f _{i}(x)\right\|^{2}\right]$ $\displaystyle={\mathbb{E}}_{\bar{\xi}}\left[\sum_{\begin{subarray}{c}j,m\,:\,b _{j,m}=(w(t),i),\\ m=\textnormal{prog}(x_{j})+1\end{subarray}}\left([\nabla f_{i}(x)]_{j,m}\right )^{2}\left(\frac{\bar{\xi}_{j}}{p_{w(t),i}}-1\right)^{2}\right]$ $\displaystyle=\sum_{\begin{subarray}{c}j,m\,:\,b_{j,m}=(w(t),i),\\ m=\textnormal{prog}(x_{j})+1\end{subarray}}\left([\nabla f_{i}(x)]_{j,m}\right )^{2}{\mathbb{E}}_{\bar{\xi}}\left[\left(\frac{\bar{\xi}_{j}}{p_{w(t),i}}-1 \right)^{2}\right]$ $\displaystyle=\sum_{\begin{subarray}{c}j,m\,:\,b_{j,m}=(w(t),i),\\ m=\textnormal{prog}(x_{j})+1\end{subarray}}\left([\nabla f_{i}(x)]_{j,m}\right )^{2}\frac{\left(1-p_{w(t),i}\right)}{p_{w(t),i}}$ $\displaystyle=\sum_{\begin{subarray}{c}j,m\,:\,b_{j,m}=(w(t),i),\\ m=\textnormal{prog}(x_{j})+1\end{subarray}}\left(\left[\nabla F_{T}\left(\frac {x_{j}}{\lambda}\right)\right]_{m}\right)^{2}\frac{n^{2}L^{2}\lambda^{2}\left( 1-p_{w(t),i}\right)}{l_{1}^{2}p_{w(t),i}}.$ $$

Due to Lemma C.1, we get $\left\|\nabla F_{T}\left(x\right)\right\|_{\infty}^{2}\leq\gamma_{\infty}^{2}$ for all $x\in\mathbb{R}^{T}$ and

$$ $\displaystyle{\mathbb{E}}_{\bar{\xi}}\left[\left\|g_{i}(x;\bar{\xi},t)-\nabla f _{i}(x)\right\|^{2}\right]$ $\displaystyle\leq\sum_{\begin{subarray}{c}j,m\,:\,b_{j,m}=(w(t),i),\\ m=\textnormal{prog}(x_{j})+1\end{subarray}}\frac{n^{2}L^{2}\lambda^{2}\gamma_{ \infty}^{2}\left(1-p_{w(t),i}\right)}{l_{1}^{2}p_{w(t),i}}$ $\displaystyle=\frac{a_{w(t),i}n^{2}L^{2}\lambda^{2}\gamma_{\infty}^{2}\left(1- p_{w(t),i}\right)}{l_{1}^{2}p_{w(t),i}}$ $$

because, due the condition $b_{j,m}=(w(t),i),$ we only consider the blocks from the set $\{s_{w(t),(i-1)},\dots,s_{w(t),i}-1\}$ (see Alg. 5), take one coordinate from each block, and recall that $a_{w(t),i}:=s_{w(t),i}-s_{w(t),(i-1)}.$ Using the choice

$$ $\displaystyle p_{w,i}:=\min\left\{\frac{a_{w,i}n^{2}L^{2}\lambda^{2}\gamma_{ \infty}^{2}}{\sigma^{2}l_{1}^{2}},1\right\}$ (48) $$

for all $w\in[T],i\in[n],$ we get

$$ $\displaystyle{\mathbb{E}}_{\bar{\xi}}\left[\left\|g_{i}(x;\bar{\xi},t)-\nabla f _{i}(x)\right\|^{2}\right]\leq\sigma^{2}.$ $$

(Step 3: Analysis of Protocol)

Mirroring the proof of Theorem 6.1, using

$$ $\displaystyle\lambda=\sqrt{\frac{4\varepsilon l_{1}^{2}}{L^{2}S}},$ (49) $$

one can show

$$ $\displaystyle\inf_{k\in S_{t}}\left\|\nabla f(x^{k})\right\|^{2}>\frac{4 \varepsilon}{S}\sum_{i=1}^{S}\inf_{k\in S_{t}}\mathbbm{1}[\textnormal{prog}(x^ {k}_{i})<T],$ (50) $$

where $x^{k}$ are points defined in Protocol 2, and

$$ $\displaystyle\mathbb{P}\left(\frac{4\varepsilon}{S}\sum_{i=1}^{S}\inf_{k\in S_ {t}}\mathbbm{1}[\textnormal{prog}(x_{i}^{k})<T]\leq 2\varepsilon\right)\leq \frac{2}{S}\sum_{i=1}^{S}{\mathbb{E}}\left[\sup_{k\in S_{t}}\mathbbm{1}[ \textnormal{prog}(x_{i}^{k})\geq T]\right].$ (51) $$

(Step 4: Bound on the expectations)

The time required to progress (get a non-zero value) to the $1$^th coordinate in the block $x_{j}$ is at least

$$ $\displaystyle\min\left\{\bar{t}_{1},V^{-1}_{i_{1,j}}\left(\eta_{j,1}\right)\right\}$ $$

seconds, where $V^{-1}_{i}$ is defined in (7) and $\eta_{j,1}$ is a geometric random variable with the probability $p_{1,i_{1,j}}.$
Because, due the condition $b_{j,1}\equiv(1,i_{1,j})=(w(t),i)$, the mapping (46) zeroes out the first coordinate only if the algorithm returns $t^{k}<\bar{t}_{1}$ and $i_{1,j}=i.$ Therefore, either the algorithm returns $t^{k}\geq\bar{t}_{1}$ and (46) does not zero out the coordinate of gradients,
or it keeps returning $t^{k}<\bar{t}_{1},$ but then $A$ should calculate at least $\eta_{j,1}$ stochastic gradients in worker $i_{1,j}$ since the stochastic mapping zeros out the potentially non-zero coordinate in (46).

Recall that the “resisting” allocator (Alg. 5) tracks the random variable $\eta_{j,1}.$
Opt. 1: If $V^{-1}_{i_{1,j}}\left(\eta_{j,1}\right)<\bar{t}_{1},$ then Alg. 5 allocates the second part of the function $h_{j}$ to the same worker $i_{1,j},$ meaning
that the time required to progress (get a non-zero value) to the $2$^th coordinate in the block $x_{j}$ is at least

$$ $\displaystyle\min\left\{\bar{t}_{1},V^{-1}_{i_{1,j}}\left(\eta_{j,1}+\eta_{j,2 }\right)\right\}\geq\min\left\{\bar{t}_{1},V^{-1}_{i_{1,j}}\left(\eta_{j,2} \right)\right\}$ $$

seconds, where $\eta_{j,2}$ is a geometric random variable with the probability $p_{1,i_{1,j}}.$
Opt. 2: If $V^{-1}_{i_{1,j}}\left(\eta_{j,1}\right)\geq\bar{t}_{1},$ then we allocate the second part to worker $i_{2,j},$ where $i_{2,j}$ such that $s_{1,i_{2,j}-1}\leq j<s_{1,i_{2,j}},$ meaning that the time required to progress (get a non-zero value) to the $2$^th coordinate in the block $x_{j}$ is at least

$$ $\displaystyle\min\left\{\bar{t}_{2},V^{-1}_{i_{2,j}}\left(\eta_{j,2}+V_{i_{2,j }}(\bar{t}_{1})\right)\right\}$ $$

seconds, where $\eta_{j,2}$ is a geometric random variable with the probability $p_{2,i_{2,j}},$ because either the algorithm returns $t^{k}\geq\bar{t}_{2},$ or it keeps returning $t^{k}<\bar{t}_{2},$ but then $A$ should first progress to the $1$^th coordinate, which takes at least $\bar{t}_{1}$ seconds, and then should calculate at least $\eta_{j,2}$ stochastic gradients. This will take at least

$$ $\displaystyle\min\left\{t\geq 0\,:\,\left\lfloor V_{i_{2,j}}(t)-V_{i_{2,j}}( \bar{t}_{1})\right\rfloor\geq\eta_{j,2}\right\}$ $\displaystyle\overset{(\textnormal{cont. of }V_{i_{2,j}})}{=}\min\left\{t\geq 0 \,:\,V_{i_{2,j}}(t)-V_{i_{2,j}}(\bar{t}_{1})=\eta_{j,2}\right\}$ $\displaystyle\overset{(\ref{eq:inv})}{=}V^{-1}_{i_{2,j}}\left(\eta_{j,2}+V_{i_ {2,j}}(\bar{t}_{1})\right)$ $$

seconds. Notice that the parameter of the geometric random variable $\eta_{j,2}$ depends on the previous randomness.

In the case Opt. 1, we can only conclude that the algorithm $A$ will require at least $\bar{t}_{0}\equiv 0$ seconds to get a non-zero value in the $T$^th coordinate. In the case Opt. 2, we have better guarantees and can infer that the algorithm $A$ will require at least $\bar{t}_{1}\geq\bar{t}_{1}$ seconds to get a non-zero value in the $T$^th coordinate because the inequality $V^{-1}_{i_{1,j}}\left(\eta_{j,1}\right)\geq\bar{t}_{1}$ holds. Hence, the condition in {NoHyper}Line 10 of Alg. 5 determines a necessary time to get the $T$^th with a non-zero value.

For all $j\in[m],$ we have the following Markov process that generalizes our previous discussion.

Figure: Algorithm 6 Markov process in the $j$^th block

The provided random Markov process determines the time $\bar{t}_{(w_{T}-1)}$ required to get the $T$^th non-zero coordinate in the $j$^th block.

For all $j\in[m],m\in[T],$ $\eta_{j,m}$ has the geometric distribution with the parameter $p_{w_{m},i_{w_{m},j}},$ which depends only on the previous random variables $\eta_{j,1},\dots,\eta_{j,m-1}.$ Therefore, we can use Lemma F.2 and get

$$ $\displaystyle\mathbb{P}\left(\sum_{m=1}^{T}\mathbbm{1}\left[\eta_{j,m}>\frac{1 }{4p_{w_{m},i_{w_{m},j}}}\right]\leq\frac{T}{2}+\log\delta\right)\leq\delta$ $$

for all $\delta\in(0,1].$ The last inequality means that with a probability at least $\nicefrac{{3}}{{4}},$ there exist $1\leq m_{1}<m_{2}<\dots<m_{\left\lfloor\frac{T-2}{2}\right\rfloor}\leq T$ such that

$$ $\displaystyle\eta_{j,m_{k}}>\frac{1}{4p_{w_{m_{k}},i_{w_{m_{k}},j}}}\geq\frac{ 1}{8p_{w_{m_{k}},i_{w_{m_{k}},j}}}$ (52) $$

for all $k\in\left[\left\lfloor\frac{T-2}{2}\right\rfloor\right].$

Due to (48) and (49), we have

$$ $\displaystyle p_{w,i}:=\min\left\{\frac{4\varepsilon\gamma_{\infty}^{2}a_{w,i} n^{2}}{\sigma^{2}S},1\right\}.$ $$

Recall that $\{\bar{t}_{w}\}_{w\in[\bar{T}]},$$\{s_{w,i}\}_{w\in[\bar{T}+1],i\in[n]},$ and $S\in\mathbb{N}$ are free parameters with the only conditions (44) and (45). Therefore, we can use Lemma F.4 with $K=1$ and ensure that there exist parameters such that

$$ $\displaystyle V^{-1}_{i}\left(\frac{1}{8p_{w,i}}+V_{i}(\bar{t}_{w-1})\right) \geq\bar{t}_{w}.$ $$

for all $w\in[T],i\in[n].$ Putting the last inequality, (52), and {NoHyper}Line 6 of Alg. 6 together, we can conclude that, with a probability at least $\nicefrac{{3}}{{4}},$ the value of $w_{T}-1$ is greater or equal to $\left\lfloor\frac{T-2}{2}\right\rfloor$ since the condition in {NoHyper}Line 6 of Alg. 6 will hold at least $\left\lfloor\frac{T-2}{2}\right\rfloor$ times.

(Step 5: Endgame)
In the previous step, we prove that, with a probability at least $\nicefrac{{3}}{{4}},$ the algorithm requires at least $\bar{t}_{\left\lfloor\frac{T-2}{2}\right\rfloor}$ seconds to progress to the $T$^th coordinate of the $j$^th block, where $\bar{t}_{\bar{T}}$ is defined in the proof of Lemma F.4.

Thus

$$ $\displaystyle{\mathbb{E}}\left[\sup_{k\in S_{t}}\mathbbm{1}[\textnormal{prog}( x_{j}^{k})\geq T]\right]\leq\frac{1}{4}$ $$

for all $j\in[n]$ and for all $t\leq\frac{1}{2}\bar{t}_{\left\lfloor\frac{T-2}{2}\right\rfloor}.$ We substitute these inequalities to (51) and (50), and get

$$ $\displaystyle\mathbb{P}\left(\frac{4\varepsilon}{S}\sum_{i=1}^{S}\inf_{k\in S_ {t}}\mathbbm{1}[\textnormal{prog}(x_{i}^{k})<T]\leq 2\varepsilon\right)\leq \frac{1}{2}$ $$

and

$$ $\displaystyle{\mathbb{E}}\left[\inf_{k\in S_{t}}\left\|\nabla f(x^{k})\right\| ^{2}\right]>{\mathbb{E}}\left[\frac{4\varepsilon}{S}\sum_{i=1}^{S}\inf_{k\in S _{t}}\mathbbm{1}[\textnormal{prog}(x^{k}_{i})<T]\right]>2\varepsilon\mathbb{P} \left(\frac{4\varepsilon}{S}\sum_{i=1}^{S}\inf_{k\in S_{t}}\mathbbm{1}[ \textnormal{prog}(x_{i}^{k})<T]>2\varepsilon\right)\geq\varepsilon$ $$

for all

$$ $\displaystyle t\leq\frac{1}{2}\widetilde{t}_{\left\lfloor\frac{T-2}{2}\right \rfloor}\overset{(\ref{eq:TToceJIF})}{\leq}\frac{1}{2}\bar{t}_{\left\lfloor \frac{T-2}{2}\right\rfloor}.$ $$

Using the assumption $\varepsilon<c^{\prime}L\Delta$ of the theorem, (43), and (49), we get

$$ $\displaystyle\left\lfloor\frac{T-2}{2}\right\rfloor\geq\left\lfloor c_{1} \times\frac{L\Delta}{\varepsilon}\right\rfloor$ $$

for some universal constant $c_{1}.$

Finally, since $\widetilde{t}_{w}\geq\underline{t}_{w}$ for all $w\in[T],$ where the later sequence is defined in (17),
we can take

$$ $\displaystyle t=\frac{1}{2}\underline{t}_{\left\lfloor c_{1}\times\frac{L \Delta}{\varepsilon}\right\rfloor}.$ $$

∎

###### Proof.

## Appendix F Auxiliary Lemmas

###### Lemma F.1 .

Let $V_{i}\,:\,\mathbb{R}^{\infty}_{+}\to\mathbb{R}^{\infty}_{+}$ is a continuous and non-decreasing function for all $i\in[n].$ For all $\eta,b_{1},\dots,b_{n}\in\mathbb{R}^{\infty}_{+},$ the minimums of the sets

$$ $\displaystyle\left\{t\geq 0\,:\,\sum_{i=1}^{n}\left\lfloor V_{i}(t)-b_{i} \right\rfloor\geq\eta\right\}$ $$

and

$$ $\displaystyle\left\{t\geq 0\,:\,\left(\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\left \lfloor V_{i}(t)-b_{i}\right\rfloor}\right)^{-1}\geq\eta\right\}$ $$

exist, considering the convention $\min\{\emptyset\}=\infty.$

###### Proof.

We now focus on the first set. If the set is empty, then the minimum is $\infty$ by the convention.
Otherwise, let us define

$$ $\displaystyle\underline{t}:=\inf\left\{t\geq 0\,:\,\sum_{i=1}^{n}\left\lfloor V _{i}(t)-b_{i}\right\rfloor\geq\eta\right\}<\infty.$ $$

If the minimum does not exist, then

$$ $\displaystyle\sum_{i=1}^{n}\left\lfloor V_{i}(\underline{t})-b_{i}\right \rfloor<\eta.$ $$

For all $i\in[n],$ the functions $V_{i}$ is continuous and non-decreasing meaning that there exists $\delta_{i}>0$ such that

$$ $\displaystyle\left\lfloor V_{i}(\underline{t})-b_{i}\right\rfloor=\left\lfloor V _{i}(\underline{t}+\delta)-b_{i}\right\rfloor.$ $$

for all $0\leq\delta\leq\delta_{i}.$ Let us take $\delta=\min\limits_{i\in[n]}\delta_{i}>0,$ then

$$ $\displaystyle\sum_{i=1}^{n}\left\lfloor V_{i}(\underline{t}+\delta)-b_{i} \right\rfloor=\sum_{i=1}^{n}\left\lfloor V_{i}(\underline{t})-b_{i}\right \rfloor<\eta.$ $$

This contradicts the fact that $\underline{t}$ is the infimum. The reasoning for the second set is the same.
∎

###### Lemma F.2 .

Let $T\geq 1$ and $\{\eta_{i}\}_{i=1}^{T}$ are geometric random variables such that given $\eta_{1},\dots,\eta_{i-1},$ $\eta_{i}~{}\sim~{}\textnormal{Geometric}(p_{i,\eta_{1},\dots,\eta_{i-1}})$ and the probability $p_{i,\eta_{1},\dots,\eta_{i-1}}\in(0,1]$ depends only on $\eta_{1},\dots,\eta_{i-1}$ for all $i\in[T].$
Then

$$ $\displaystyle\mathbb{P}\left(\sum_{i=1}^{T}\mathbbm{1}\left[\eta_{i}>\frac{1}{ 4p_{i,\eta_{1},\dots,\eta_{i-1}}}\right]\leq\frac{T}{2}+\log\delta\right)\leq\delta$ $$

for all $\delta\in(0,1].$

###### Proof.

Let us consider the simplified notation $p_{i}\equiv p_{i,\eta_{1},\dots,\eta_{i-1}}$ and take any $\bar{T},s>0.$
Using Chernoff’s method, we get

$$ $\displaystyle\mathbb{P}\left(\sum_{i=1}^{T}\mathbbm{1}\left[\eta_{i}>\frac{1}{ 4p_{i}}\right]\leq\bar{T}\right)$ $\displaystyle=\mathbb{P}\left(-s\sum_{i=1}^{T}\mathbbm{1}\left[\eta_{i}>\frac{ 1}{4p_{i}}\right]\geq-s\bar{T}\right)$ (53) $\displaystyle\leq e^{s\bar{T}}{\mathbb{E}}\left[e^{-s\sum_{i=1}^{T}\mathbbm{1} \left[\eta_{i}>\frac{1}{4p_{i}}\right]}\right]$ $\displaystyle=e^{s\bar{T}}{\mathbb{E}}\left[\prod_{i=1}^{T}{\mathbb{E}}\left[ \left.e^{-s\mathbbm{1}\left[\eta_{i}>\frac{1}{4p_{i}}\right]}\right|\eta_{1}, \dots,\eta_{i-1}\right]\right],$ $$

where we use the definition of conditional expectation.

For all $i\in[T],$ we now consider the $i$^th expectation separately:

$$ $\displaystyle{\mathbb{E}}\left[\left.e^{-s\mathbbm{1}\left[\eta_{i}>\frac{1}{4 p_{i}}\right]}\right|\eta_{1},\dots,\eta_{i-1}\right]$ $\displaystyle=\mathbb{P}\left(\eta_{i}\leq\frac{1}{4p_{i}}\middle|\eta_{1}, \dots,\eta_{i-1}\right)+e^{-s}\mathbb{P}\left(\eta_{i}>\frac{1}{4p_{i}}\middle |\eta_{1},\dots,\eta_{i-1}\right)$ $\displaystyle=(1-e^{-s})\mathbb{P}\left(\eta_{i}\leq\frac{1}{4p_{i}}\middle| \eta_{1},\dots,\eta_{i-1}\right)+e^{-s}.$ $$

Due the assumption of our theorem, given $\eta_{1},\dots,\eta_{i-1},$ $\eta_{i}$ is a geometric random variable with the parameter $p_{i}\equiv p_{i,\eta_{1},\dots,\eta_{i-1}}.$ Therefore

$$ $\displaystyle{\mathbb{E}}\left[\left.e^{-s\mathbbm{1}\left[\eta_{i}>\frac{1}{4 p_{i}}\right]}\right|\eta_{1},\dots,\eta_{i-1}\right]=(1-e^{-s})\left(1-(1-p_{ i})^{\left\lfloor\frac{1}{4p_{i}}\right\rfloor}\right)+e^{-s},$ $$

where $1-(1-p_{i})^{\left\lfloor\frac{1}{4p_{i}}\right\rfloor}=0$ if $p_{i}=1$ and $\left\lfloor\frac{1}{4p_{i}}\right\rfloor=0.$ Since $1-(1-p)^{\left\lfloor S\right\rfloor}\leq p\left\lfloor S\right\rfloor$ for all $p\in(0,1]$ and $S\geq 0,$ we get

$$ $\displaystyle{\mathbb{E}}\left[\left.e^{-s\mathbbm{1}\left[\eta_{i}>\frac{1}{4 p_{i}}\right]}\right|\eta_{1},\dots,\eta_{i-1}\right]$ $\displaystyle\leq(1-e^{-s})p_{i}\left\lfloor\frac{1}{4p_{i}}\right\rfloor+e^{-s}$ $\displaystyle\leq(1-e^{-s})p_{i}\times\frac{1}{4p_{i}}+e^{-s}=(1-e^{-s})\frac{ 1}{4}+e^{-s}.$ $$

Let us take $s=1,$ then

$$ $\displaystyle{\mathbb{E}}\left[\left.e^{-s\mathbbm{1}\left[\eta_{i}>\frac{1}{4 p_{i}}\right]}\right|\eta_{1},\dots,\eta_{i-1}\right]\leq(1-e^{-1})\frac{1}{4} +e^{-1}\leq e^{-1/2}.$ $$

We substitute the last inequality and the chosen value of $s$ to (53) and get

$$ $\displaystyle\mathbb{P}\left(\sum_{i=1}^{T}\mathbbm{1}\left[\eta_{i}>\frac{1}{ 4p_{i}}\right]\leq\bar{T}\right)\leq e^{\bar{T}-\frac{T}{2}}.$ $$

For all $\delta\in(0,1],$ we can take

$$ $\displaystyle\bar{T}=\frac{T}{2}+\log\delta$ $$

to ensure that

$$ $\displaystyle\mathbb{P}\left(\sum_{i=1}^{T}\mathbbm{1}\left[\eta_{i}>\frac{1}{ 4p_{i}}\right]\leq\frac{T}{2}+\log\delta\right)\leq\delta.$ $$

∎

###### Lemma F.3 .

Let $\eta_{1,1},\dots,\eta_{1,K}\sim\textnormal{Geometric}(p_{1}),$ $\eta_{2,1},\dots,\eta_{2,K}\sim\textnormal{Geometric}(p_{2}),$ …, $\eta_{\bar{T},1},\dots,\eta_{\bar{T},K}\sim\textnormal{Geometric}(p_{\bar{T}})$ are mutually independent geometric random variables. Then

$$ $\displaystyle\mathbb{P}\left(\bigcup_{k\in[\bar{T}]}\left\{\sum_{j=1}^{K}\eta_ {k,j}\leq\frac{K}{8p_{k}}\right\}\right)\leq\bar{T}e^{-K/2}.$ $$

###### Proof.

Let us fix any $a_{k}\geq 0$ for all $k\in[\bar{T}].$ Using the union bound, we get

$$ $\displaystyle\mathbb{P}\left(\bigcup_{k\in[\bar{T}]}\left\{\sum_{j=1}^{K}\eta_ {k,j}\leq a_{k}\right\}\right)\leq\sum_{k=1}^{\bar{T}}\mathbb{P}\left(\sum_{j= 1}^{K}\eta_{k,j}\leq a_{k}\right).$ (54) $$

For all $k\in[\bar{T}]$ and $s>0,$ we obtain the following series of inequalities:

$$ $\displaystyle\mathbb{P}\left(\sum_{j=1}^{K}\eta_{k,j}\leq a_{k}\right)$ $\displaystyle=\mathbb{P}\left(-s\sum_{j=1}^{K}\eta_{k,j}\geq-sa_{k}\right)= \mathbb{P}\left(e^{-s\sum_{j=1}^{K}\eta_{k,j}}\geq e^{-sa_{k}}\right)$ $\displaystyle\leq e^{sa_{k}}{\mathbb{E}}\left[e^{-s\sum_{j=1}^{K}\eta_{k,j}} \right],$ $$

where we use Markov’s inequality. Since the random variables are mutually independent, we have

$$ $\displaystyle\mathbb{P}\left(\sum_{j=1}^{K}\eta_{k,j}\leq a_{k}\right)$ $\displaystyle\leq e^{sa_{k}}\left({\mathbb{E}}\left[e^{-s\eta_{k,1}}\right] \right)^{K}=e^{sa_{k}}\left(\frac{p_{k}}{e^{s}-(1-p_{k})}\right)^{K},$ $$

where we use the moment-generating function of the geometric random variables. Since $p_{k}\geq 0$ and $e^{s}\geq 1+s$ for all $s\in\mathbb{R},$ we get

$$ $\displaystyle\mathbb{P}\left(\sum_{j=1}^{K}\eta_{k,j}\leq a_{k}\right)\leq e^{ sa_{k}}\left(\frac{p_{k}}{s}\right)^{K}.$ $$

Let us take $s=4p_{k}$ to ensure that

$$ $\displaystyle\mathbb{P}\left(\sum_{j=1}^{K}\eta_{k,j}\leq a_{k}\right)\leq e^{ 4p_{k}a_{k}-K}.$ $$

We can take $a_{k}=\frac{K}{8p_{k}}$ to get

$$ $\displaystyle\mathbb{P}\left(\sum_{j=1}^{K}\eta_{k,j}\leq\frac{K}{8p_{k}} \right)\leq e^{-K/2}.$ $$

It is left to substitute the last inequality to (54).
∎

###### Lemma F.4 .

For all $\bar{T},K\in\mathbb{N},$ there exist non-negative parameters $\{\bar{t}_{w}\}_{w\in[\bar{T}]},$$\{s_{w,i}\}_{w\in[\bar{T}+1],i\in[n]},$ and $S\in\mathbb{N}$ such that

- 1.
$\begin{gathered}s_{w,0}\equiv 1\leq s_{w,1}\leq\dots\leq s_{w,n-1}\leq s_{w,n}
\equiv S+1\quad\forall w\in[\bar{T}+1],\\
\bar{t}_{0}\equiv 0\leq\bar{t}_{1}\leq\dots\leq\bar{t}_{\bar{T}}\leq\bar{t}_{
\bar{T}+1}\equiv\infty.\end{gathered}$
(55)
- 2.
$\displaystyle V^{-1}_{i}\left(\frac{K}{8p_{w,i}}+V_{i}(\bar{t}_{w-1})\right)
\geq\bar{t}_{w}.$
(56)
for all $w\in[\bar{T}],i\in[n],$
- 3.
$\displaystyle\bar{t}_{w}\geq\widetilde{t}_{w}:=\min\left\{t\geq 0\,:\,\left(
\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\left\lfloor\frac{16(V_{i}\left(t\right)-V_{
i}(\widetilde{t}_{w-1}))}{K}\right\rfloor}\right)^{-1}\geq\max\left\{\frac{
\sigma^{2}}{32\gamma_{\infty}^{2}\varepsilon n},1\right\}\right\}\qquad(
\widetilde{t}_{0}\equiv 0)$
(57)
for all $w\in[\bar{T}],$

where

$$ $\displaystyle p_{w,i}:=\min\left\{\frac{4\varepsilon\gamma_{\infty}^{2}a_{w,i} n^{2}}{\sigma^{2}S},1\right\},$ (58) $$

$a_{w,i}:=s_{w,i}-s_{w,(i-1)},$ and $\varepsilon,\gamma_{\infty}^{2},\sigma^{2}$ are arbitrarily non-negative constants.

###### Proof.

We have the free parameters $\{\bar{t}_{w}\}_{w\in[\bar{T}]},$$\{s_{w,i}\}_{w\in[\bar{T}+1],i\in[n]},$ and $S\in\mathbb{N}$ with the only condition

$$ $\begin{gathered}s_{w,0}\equiv 1\leq s_{w,1}\leq\dots\leq s_{w,n-1}\leq s_{w,n} \equiv S+1\quad\forall w\in[\bar{T}+1],\\ \bar{t}_{0}\equiv 0\leq\bar{t}_{1}\leq\dots\leq\bar{t}_{\bar{T}}\leq\bar{t}_{ \bar{T}+1}\equiv\infty.\end{gathered}$ (59) $$

We now choose values of these parameters to ensure that (56) holds. Instead of $\{s_{w,i}\},$ we will work with $\{a_{w,i}\},$ then one can restore $\{s_{w,i}\}$ using the definition $a_{w,i}:=s_{w,i}-s_{w,(i-1)}.$ We have to ensure that

$$ $\displaystyle\sum_{i=1}^{n}a_{w,i}=S$ (60) $$

holds for all $w\in[\bar{T}+1]$ to get (59).
It is sufficient to validate that

$$ $\displaystyle p_{w,i}<\frac{K}{8(V_{i}(\bar{t}_{w})-V_{i}(\bar{t}_{w-1}))} \qquad(\bar{t}_{0}\equiv 0)$ $$

for all $w\in[\bar{T}]$ to guarantee that

$$ $\displaystyle V^{-1}_{i}\left(\frac{K}{8p_{w,i}}+V_{i}(\bar{t}_{w-1})\right) \geq\bar{t}_{w}$ $$

for all $w\in[\bar{T}].$
Due to (58), it is sufficient to find $\{a_{w,i}\},$ $\{\bar{t}_{w}\},$ and $S$ such that (60) holds and

$$ $\displaystyle\min\left\{\frac{a_{w,i}n^{2}4\varepsilon\gamma_{\infty}^{2}}{S \sigma^{2}},1\right\}$ $\displaystyle\overset{(\ref{eq:lOuQCvNGUaR})}{=}\min\left\{\frac{a_{w,i}n^{2}4 \varepsilon\gamma_{\infty}^{2}}{\sum_{i=1}^{n}a_{w,i}\sigma^{2}},1\right\}< \frac{K}{8(V_{i}(\bar{t}_{w})-V_{i}(\bar{t}_{w-1}))}$ (61) $$

for all $i\in[n]$ and for all $w\in[\bar{T}].$
Assume that $\bar{t}_{w-1}$ is defined ($\bar{t}_{0}\equiv 0$), and let us now consider $w\in[\bar{T}].$
Let us define

$$ $\displaystyle\bar{t}_{w}^{1}:=\max\limits_{j\in[n]}V^{-1}_{j}\left(\frac{K}{16 }+V_{j}(\bar{t}_{w-1})\right)$ (62) $$

and

$$ $\displaystyle\bar{t}_{w}^{2}:=\min\left\{t\geq 0\,:\,\sum_{i=1}^{n}\frac{K \sigma^{2}}{n^{2}4\varepsilon\gamma_{\infty}^{2}\left(V_{i}\left(t\right)-V_{i }(\bar{t}_{w-1})\right)}=64\right\}.$ (63) $$

Opt. 1: If $\bar{t}_{w}^{1}>\bar{t}_{w}^{2},$ then we take $\bar{t}_{w}=\bar{t}_{w}^{1},$ $\bar{a}_{w,i}:=0$ for all $i\neq j^{*},$ and $\bar{a}_{w,j^{*}}:=1,$ where

$$ $\displaystyle j^{*}=\arg\max\limits_{j\in[n]}V^{-1}_{j}\left(\frac{K}{16}+V_{j }(\bar{t}_{w-1})\right).$ (64) $$

Opt. 2: If $\bar{t}_{w}^{1}\leq\bar{t}_{w}^{2},$ then we take $\bar{t}_{w}=\bar{t}_{w}^{2},$ and (^7^77$V_{i}\left(\bar{t}_{w}\right)>V_{i}(\bar{t}_{w-1})$ for all $i\in[n]$ since $\bar{t}_{w}\geq\bar{t}_{w}^{1}$ and $V_{i}(\bar{t}_{w})\geq\frac{K}{16}+V_{i}(\bar{t}_{w-1})$ for all $i\in[n],$ due to (62) and the definition (7).)

$$ $\displaystyle\bar{a}_{w,i}:=\left\lfloor\frac{\max\limits_{i\in[n]}\left\{V_{i }\left(\bar{t}_{w}\right)-V_{i}(\bar{t}_{w-1})\right\}}{V_{i}\left(\bar{t}_{w} \right)-V_{i}(\bar{t}_{w-1})}\right\rfloor$ (65) $$

for all $i\in[n].$

For $w=\bar{T}+1,$ we take $\bar{a}_{w,i}:=0$ for all $i\neq 1,$ and $\bar{a}_{w,1}:=1.$

We choose the following $S:$

$$ $\displaystyle S=\max_{w\in[\bar{T}+1]}\left(\sum_{i=1}^{n}\bar{a}_{w,i}\right),$ $$

and for all $w\in\operatorname*{Arg\,max}_{w\in[\bar{T}+1]}\left(\sum_{i=1}^{n}\bar{a}_{w,i
}\right),$ we take $a_{w,i}:=\bar{a}_{w,i}.$
Let us take any $w$ such that $\sum_{i=1}^{n}\bar{a}_{w,i}<S,$ then, for all $w\in[\bar{T}+1],$ there exists the smallest $k_{w}\geq 2$ that yields

$$ $\displaystyle\sum_{i=1}^{n}k_{w}\times\bar{a}_{w,i}\geq S.$ $$

Opt. 1: If $\bar{t}_{w}^{1}>\bar{t}_{w}^{2},$ then we take $a_{w,j^{*}}:=k_{w}\times\bar{a}_{w,j^{*}}=k_{w}$ and $a_{w,i}:=k_{w}\times\bar{a}_{w,i}=0$ for all $i\neq j^{*}$ ($j^{*}$ from (64)) to ensure that $\sum_{i=1}^{n}a_{w,i}=S.$
Opt. 2: If $\bar{t}_{w}^{1}\leq\bar{t}_{w}^{2},$ there exist $r_{w,i}\in\{0,\dots,\bar{a}_{w,i}\}$ that if we take

$$ $\displaystyle a_{w,i}:=(k_{w}-1)\times\bar{a}_{w,i}+r_{w,i},$ $$

then we guarantee the equality $\sum_{i=1}^{n}a_{w,i}=S.$

It is left to ensure that (F) holds.

Opt. 1: If $\bar{t}_{w}^{1}>\bar{t}_{w}^{2},$ then
(F) holds since

$$ $\displaystyle\min\left\{\frac{a_{w,i}n^{2}4\varepsilon\gamma_{\infty}^{2}}{ \sum_{i=1}^{n}a_{w,i}\sigma^{2}},1\right\}=0\quad\forall i\neq j^{*}$ $$

and

$$ $\displaystyle\min\left\{\frac{a_{w,i}n^{2}4\varepsilon\gamma_{\infty}^{2}}{ \sum_{i=1}^{n}a_{w,i}\sigma^{2}},1\right\}\leq 1<\frac{K}{8(V_{i}(\bar{t}_{w}) -V_{i}(\bar{t}_{w-1}))}\textnormal{ for }i=j^{*},$ $$

where the last inequality due to the definition (7) and the choice of $\bar{t}_{w}^{1}$:

$$ $\displaystyle V_{j^{*}}(\bar{t}_{w}^{1})=\frac{K}{16}+V_{j^{*}}(\bar{t}_{w-1}) <\frac{K}{8}+V_{j^{*}}(\bar{t}_{w-1}).$ $$

Opt. 2: If $\bar{t}_{w}^{1}\leq\bar{t}_{w}^{2},$ then
(F) holds since

$$ $\displaystyle\frac{a_{w,i}}{\sum_{i=1}^{n}a_{w,i}}$ $\displaystyle\leq\frac{k_{w}\bar{a}_{w,i}}{(k_{w}-1)\sum_{i=1}^{n}\bar{a}_{w,i }}\leq 2\frac{\bar{a}_{w,i}}{\sum_{i=1}^{n}\bar{a}_{w,i}}$ $$

because $k_{w}\geq 2.$ Using (65) and $x\geq\left\lfloor x\right\rfloor\geq\frac{x}{2}$ for all $x\geq 1$, we get

$$ $\displaystyle\frac{a_{w,i}}{\sum_{i=1}^{n}a_{w,i}}\leq 4\frac{\frac{1}{V_{i} \left(\bar{t}_{w}\right)-V_{i}(\bar{t}_{w-1})}}{\sum_{i=1}^{n}\frac{1}{V_{i} \left(\bar{t}_{w}\right)-V_{i}(\bar{t}_{w-1})}}\overset{(\ref{eq:ginRrbVSB})}{ \leq}\frac{K\sigma^{2}}{64n^{2}\varepsilon\gamma_{\infty}^{2}\left(V_{i}\left( \bar{t}_{w}\right)-V_{i}(\bar{t}_{w-1})\right)}.$ $$

The last inequality ensures that (F) holds. In total, we have $\bar{t}_{w}=\max\{\bar{t}_{w}^{1},\bar{t}_{w}^{2}\}.$

It is left to prove (57). Let us define

$$ $\displaystyle\widetilde{t}_{w}$ $\displaystyle:=\min\left\{t\geq 0\,:\,\left(\frac{1}{n}\sum_{i=1}^{n}\frac{1}{ \left\lfloor\frac{16(V_{i}\left(t\right)-V_{i}(\widetilde{t}_{w-1}))}{K}\right \rfloor}\right)^{-1}\geq\max\left\{\frac{\sigma^{2}}{32\gamma_{\infty}^{2} \varepsilon n},1\right\}\right\}\qquad(\widetilde{t}_{0}\equiv 0).$ (66) $$

We know that $\widetilde{t}_{0}\equiv 0\leq\bar{t}_{0}\equiv 0.$ Using a proof by induction and assuming $\widetilde{t}_{w-1}\leq\bar{t}_{w-1},$ we have

$$ $\displaystyle\widetilde{t}_{w}$ $\displaystyle=\min\left\{t\geq\max\limits_{j\in[n]}V^{-1}_{j}\left(\frac{K}{16 }+V_{j}(\widetilde{t}_{w-1})\right)\,:\,\left(\frac{1}{n}\sum_{i=1}^{n}\frac{1 }{\left\lfloor\frac{16(V_{i}\left(t\right)-V_{i}(\widetilde{t}_{w-1}))}{K} \right\rfloor}\right)^{-1}\geq\max\left\{\frac{\sigma^{2}}{32\gamma_{\infty}^{ 2}\varepsilon n},1\right\}\right\}$ $\displaystyle=\min\left\{t\geq\max\limits_{j\in[n]}V^{-1}_{j}\left(\frac{K}{16 }+V_{j}(\widetilde{t}_{w-1})\right)\,:\,\frac{1}{n}\sum_{i=1}^{n}\frac{1}{ \left\lfloor\frac{16(V_{i}\left(t\right)-V_{i}(\widetilde{t}_{w-1}))}{K}\right \rfloor}\leq\min\left\{\frac{32\gamma_{\infty}^{2}\varepsilon n}{\sigma^{2}},1 \right\}\right\}$ $$

because if $\left(\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\left\lfloor\frac{16(V_{i}\left(t
\right)-V_{i}(\widetilde{t}_{w-1}))}{K}\right\rfloor}\right)^{-1}\geq\max\left
\{\frac{\sigma^{2}}{32\gamma_{\infty}^{2}\varepsilon n},1\right\},$ then, necessarily, $16(V_{i}\left(t\right)-V_{i}(\widetilde{t}_{w-1}))\geq K$ for all $i\in[n].$
Then

$$ $\displaystyle\widetilde{t}_{w}$ $\displaystyle=\min\left\{t\geq\max\limits_{j\in[n]}V^{-1}_{j}\left(\frac{K}{16 }+V_{j}(\widetilde{t}_{w-1})\right)\,:\,\frac{1}{n}\sum_{i=1}^{n}\frac{1}{ \left\lfloor\frac{16(V_{i}\left(t\right)-V_{i}(\widetilde{t}_{w-1}))}{K}\right \rfloor}\leq\frac{32\gamma_{\infty}^{2}\varepsilon n}{\sigma^{2}}\right\}$ $$

because $\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\left\lfloor\frac{16(V_{i}\left(t\right)-V_{
i}(\widetilde{t}_{w-1}))}{K}\right\rfloor}\leq 1$ for all $t\geq\max\limits_{j\in[n]}V^{-1}_{j}\left(\frac{K}{16}+V_{j}(\widetilde{t}_{w-
1})\right).$
Further

$$ $\displaystyle\widetilde{t}_{w}$ $\displaystyle\leq\min\left\{t\geq\max\limits_{j\in[n]}V^{-1}_{j}\left(\frac{K} {16}+V_{j}(\bar{t}_{w-1})\right)\,:\,\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\left \lfloor\frac{16(V_{i}\left(t\right)-V_{i}(\bar{t}_{w-1}))}{K}\right\rfloor} \leq\frac{32\gamma_{\infty}^{2}\varepsilon n}{\sigma^{2}}\right\}$ $\displaystyle\leq\min\left\{t\geq\max\limits_{j\in[n]}V^{-1}_{j}\left(\frac{K} {16}+V_{j}(\bar{t}_{w-1})\right)\,:\,\sum_{i=1}^{n}\frac{\sigma^{2}}{n^{2}4 \varepsilon\gamma_{\infty}^{2}\frac{(V_{i}\left(t\right)-V_{i}(\bar{t}_{w-1})) }{K}}\leq 64\right\}$ $$

because $\widetilde{t}_{w-1}\leq\bar{t}_{w-1},$ $\{V_{i}\}$ are non-decreasing, and $\left\lfloor x\right\rfloor\geq\frac{x}{2}$ for all $x\geq 1.$ Then

$$ $\displaystyle\widetilde{t}_{w}$ $\displaystyle\leq\min\left\{t\geq\max\limits_{j\in[n]}V^{-1}_{j}\left(\frac{K} {16}+V_{j}(\bar{t}_{w-1})\right)\,:\,\sum_{i=1}^{n}\frac{K\sigma^{2}}{n^{2}4 \varepsilon\gamma_{\infty}^{2}(V_{i}\left(t\right)-V_{i}(\bar{t}_{w-1}))}\leq 6 4\right\}\leq\max\{\bar{t}_{w}^{1},\bar{t}_{w}^{2}\}=\bar{t}_{w}$ $$

due to the definitions (62), (63) of $\bar{t}_{w}^{1},$$\bar{t}_{w}^{2},$ and $\bar{t}_{w}.$
∎

###### Lemma F.5 .

(Tyurin et al., )[Section K]
Consider a sequence $\infty>v_{1}\geq\ldots\geq v_{n}$ and fix some $S>0$. For all $j\in[n]$, define

$$ $g(j):=\left(\sum_{i=1}^{j}v_{i}\right)^{-1}\left(S+j\right).$ $$

- 1.
Let $j^{*}_{\max}$ be the largest index such that $\min\limits_{j\in[n]}g(j)=g(j^{*}_{\max}).$ For $j^{*}_{\max}<n,$ we have
$\displaystyle\min_{j\in[n]}g(j)<\frac{1}{v_{(j^{*}_{\max}+1)}}.$
- 2.
Let $j^{*}$ be any index such that $\min\limits_{j\in[n]}g(j)=g(j^{*}).$ For $j^{*}<n,$ we have
$\displaystyle\min_{j\in[n]}g(j)\leq\frac{1}{v_{(j^{*}+1)}}.$
- 3.
Let $j^{*}_{\min}$ be the smallest index such that $\min\limits_{j\in[n]}g(j)=g(j^{*}_{\min})$. Then
$\displaystyle\frac{1}{v_{j^{*}_{\min}}}<\min_{j\in[n]}g(j).$
- 4.
Let $j^{*}$ be any index such that $\min\limits_{j\in[n]}g(j)=g(j^{*}).$ Then
$\displaystyle\frac{1}{v_{j^{*}}}\leq\min_{j\in[n]}g(j).$

###### Lemma F.1 .

###### Proof.

###### Lemma F.2 .

###### Proof.

###### Lemma F.3 .

###### Proof.

###### Lemma F.4 .

###### Proof.

###### Lemma F.5 .

## Appendix G Convex Setting

In the convex setting, the time complexities do not change significantly in a 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 on the sequences (11) and (18). The only difference is the number of iterations that the methods do in each particular setup.

Using the same reasoning as in other sections and (Tyurin & Richtárik, )[Section B], we conjecture that the following results are optimal up to constant factors. It is sufficient to use an appropriate “difficult” function (Guzmán & Nemirovski, ; Nesterov, ; Woodworth et al., ) designed for the convex domain instead of (20).

We use the following assumptions:

###### Assumption G.1 .

The function $f$ is convex and attains a minimum at some point $x^{*}\in\mathbb{R}^{d}.$

###### Assumption G.2 .

The function $f$ is $M$–Lipschitz, i.e.,

$$ $\left|f(x)-f(y)\right|\leq M\left\|x-y\right\|,\quad\forall x,y\in\mathbb{R}^{d}$ $$

for some $M\in(0,\infty].$

###### Assumption G.3 (Homogeneous setup) .

For all $i\in[n],$ worker $i$ can only calculate $\nabla f(x;\xi).$ For all $x\in\mathbb{R}^{d},$ stochastic (sub)gradients $\nabla f(x;\xi)$ are unbiased and are $\sigma^{2}$-variance-bounded, i.e.,
${\mathbb{E}}_{\xi}\left[\nabla f(x;\xi)\right]\in\partial f(x)$ and
${\mathbb{E}}_{\xi}\left[\left\|\nabla f(x;\xi)-{\mathbb{E}}_{\xi}\left[\nabla f
(x;\xi)\right]\right\|^{2}\right]\leq\sigma^{2},$ where $\sigma^{2}\geq 0.$

###### Assumption G.4 (Heterogeneous setup) .

For all $i\in[n],$ worker $i$ can only calculate $\nabla f_{i}(x;\xi_{i}).$ For all $x\in\mathbb{R}^{d},i\in[n]$ stochastic (sub)gradients $\nabla f_{i}(x;\xi_{i})$ are unbiased and are $\sigma^{2}$-variance-bounded, i.e.,
${\mathbb{E}}_{\xi_{i}}\left[\nabla f_{i}(x;\xi_{i})\right]\in\partial f_{i}(x)$ and
${\mathbb{E}}_{\xi_{i}}\left[\left\|\nabla f_{i}(x;\xi_{i})-{\mathbb{E}}_{\xi_{
i}}\left[\nabla f_{i}(x;\xi_{i})\right]\right\|^{2}\right]\leq\sigma^{2},$ where $\sigma^{2}\geq 0.$

We consider *four* cases.

###### Assumption G.1 .

###### Assumption G.2 .

###### Assumption G.3 (Homogeneous setup) .

###### Assumption G.4 (Heterogeneous setup) .

### G.1 Homogeneous setup and nonsmooth case

###### Theorem G.5 .

[(Tyurin & Richtárik, )]
Let Assumptions G.1, G.2 and G.3 hold. Choose any $\varepsilon>0.$ Let us take the batch size $S=\max\left\{\left\lceil\nicefrac{{\sigma^{2}}}{{M^{2}}}\right\rceil,1\right\},$
stepsize $\gamma=\frac{\varepsilon}{M^{2}+\sigma^{2}/S}\in\left[\frac{\varepsilon}{2M^{2
}},\frac{\varepsilon}{M^{2}}\right]$ in Method 3.
Then after $K\geq\nicefrac{{2M^{2}R^{2}}}{{\varepsilon^{2}}}$
iterations the method guarantees ${\mathbb{E}}\left[f(\widehat{x}^{K})\right]-f(x^{*})\leq\varepsilon,$ where $\widehat{x}^{K}=\frac{1}{K}\sum_{k=0}^{K-1}x^{k}$ and $R=\left\|x^{*}-x^{0}\right\|.$

###### Theorem G.6 .

Consider the assumptions and the parameters from Theorem G.5, plus Assumption 3.1. Then Method 3 (Rennala SGD) converges after at most $\bar{t}_{\left\lceil\frac{2M^{2}R^{2}}{\varepsilon^{2}}\right\rceil}$ seconds, where the sequence $\bar{t}_{k}$ is defined in (11).

###### Proof.

The proof is identical to the proof of Theorem 5.3.
∎

###### Theorem G.5 .

###### Theorem G.6 .

###### Proof.

### G.2 Homogeneous setup and smooth case

In the homogeneous and smooth case, we can use an accelerated technique (Nesterov, ; Lan, ). Instead of {NoHyper}Line 11 of Method 3, we use the following steps suggested by Lan ():

$$ $\displaystyle\gamma_{k+1}=\gamma\cdot(k+1),\quad\alpha_{k+1}=2/(k+2)$ (67) $\displaystyle y^{k+1}=(1-\alpha_{k+1})x^{k}+\alpha_{k+1}u^{k},\qquad(u^{0}=x^{ 0})$ $\displaystyle u^{k+1}=u^{k}-\frac{\gamma_{k+1}}{s^{k}}g^{k},$ $\displaystyle x^{k+1}=(1-\alpha_{k+1})x^{k}+\alpha_{k+1}u^{k+1}.$ $$

A new method with these steps is called the Accelerated Rennala SGD method (Tyurin & Richtárik, ).

###### Theorem G.7 .

[(Tyurin & Richtárik, )]
Let Assumptions G.1, 1.1 and 1.3 hold. Choose any $\varepsilon>0.$ Let us take the batch size $S=\max\left\{\left\lceil(\sigma^{2}R)/(\varepsilon^{3/2}\sqrt{L})\right\rceil,
1\right\},$
and $\gamma=\min\left\{\frac{1}{4L},\left[\frac{3R^{2}S}{4\sigma^{2}(K+1)(K+2)^{2}}
\right]^{1/2}\right\}$ in Accelerated Method 3 (Accelerated Rennala SGD),
then after $K\geq\frac{8\sqrt{L}R}{\sqrt{\varepsilon}}$
iterations the method guarantees that ${\mathbb{E}}\left[f(x^{K})\right]-f(x^{*})\leq\varepsilon,$ where $R=\left\|x^{*}-x^{0}\right\|.$

###### Theorem G.8 .

Consider the assumptions and the parameters from Theorem G.7, plus Assumption 3.1. Then Accelerated Method 3 (Accelerated Rennala SGD) converges after at most $\bar{t}_{\left\lceil\frac{8\sqrt{L}R}{\sqrt{\varepsilon}}\right\rceil}$ seconds, where the sequence $\bar{t}_{k}$ is defined in (11).

###### Proof.

The proof is identical to the proof of Theorem 5.3.
∎

###### Theorem G.7 .

###### Theorem G.8 .

###### Proof.

### G.3 Heterogeneous setup and nonsmooth case

Consider the heterogeneous setup discussed in Section 1.

###### Theorem G.9 .

Let Assumptions G.1, G.2, and G.4 hold. Choose any $\varepsilon>0.$ Let us take $S=\max\left\{\left\lceil\nicefrac{{\sigma^{2}}}{{M^{2}}}\right\rceil,n\right\},$ and
$\gamma=\frac{\varepsilon}{M^{2}+\sigma^{2}/S}\in\left[\frac{\varepsilon}{2M^{2
}},\frac{\varepsilon}{M^{2}}\right]$ in Method 4,
then after $K\geq\nicefrac{{2M^{2}R^{2}}}{{\varepsilon^{2}}}$
iterations the method guarantees that ${\mathbb{E}}\left[f(\widehat{x}^{K})\right]-f(x^{*})\leq\varepsilon,$ where $\widehat{x}^{K}=\frac{1}{K}\sum_{k=0}^{K-1}x^{k}$ and $R=\left\|x^{*}-x^{0}\right\|.$

###### Proof.

Notice that Malenia SGD is equivalent to the classical SGD method with the step

$$ $\displaystyle x^{k+1}=x^{k}-\gamma\frac{1}{n}\sum_{j=1}^{n}\frac{1}{B_{j}}\sum _{i=1}^{B_{j}}\nabla f_{j}(x^{k};\xi^{k}_{j,i}),$ $$

where the variance of the unbiased gradient estimator can be bounded in the following way:

$$ $\displaystyle{\mathbb{E}}_{\xi^{k}}\left[\left\|\frac{1}{n}\sum_{j=1}^{n}\frac {1}{B_{j}}\sum_{i=1}^{B_{j}}\nabla f_{j}(x^{k};\xi^{k}_{j,i})-\nabla f(x^{k}) \right\|^{2}\right]\leq\frac{\sigma^{2}}{n^{2}}\left(\sum_{j=1}^{n}\frac{1}{B_ {j}}\right).$ $$

In Method 4, we ensure that $\left(\sum_{j=1}^{n}\frac{1}{B_{j}}\right)\leq\frac{n^{2}}{S}.$ Therefore

$$ $\displaystyle{\mathbb{E}}_{\xi^{k}}\left[\left\|\frac{1}{n}\sum_{j=1}^{n}\frac {1}{B_{j}}\sum_{i=1}^{B_{j}}\nabla f_{j}(x^{k};\xi^{k}_{j,i})-\nabla f(x^{k}) \right\|^{2}\right]\leq\frac{\sigma^{2}}{S}.$ $$

Thus, we can use the classical result from the literature (e.g. (Lan, )). We get

$$ $\displaystyle{\mathbb{E}}\left[f(\widehat{x}^{K})\right]-f(x^{*})\leq\varepsilon$ $$

if

$$ $K\geq\frac{2M^{2}\left\|x^{*}-x^{0}\right\|^{2}}{\varepsilon^{2}}\geq\frac{(M^ {2}+\frac{\sigma^{2}}{S})\left\|x^{*}-x^{0}\right\|^{2}}{\varepsilon^{2}}$ $$

for the stepsize

$$ $\gamma=\frac{\varepsilon}{M^{2}+\frac{\sigma^{2}}{S}}\in\left[\frac{ \varepsilon}{2M^{2}},\frac{\varepsilon}{M^{2}}\right],$ $$

where we use the fact that $S\geq\nicefrac{{\sigma^{2}}}{{M^{2}}}.$
∎

###### Theorem G.10 .

Consider the assumptions and the parameters from Theorem G.9, plus Assumption 3.1. Then Method 4 (Malenia SGD) converges after at most $\bar{t}_{\left\lceil\frac{2M^{2}R^{2}}{\varepsilon^{2}}\right\rceil}$ seconds, where the sequence $\bar{t}_{k}$ is defined in (18).

###### Proof.

The proof is identical to the proof of Theorem 6.4.
∎

###### Theorem G.9 .

###### Proof.

###### Theorem G.10 .

###### Proof.

### G.4 Heterogeneous setup and smooth case

Using the same idea as in Section G.2, we will modify Malenia SGD and, instead of {NoHyper}Line 13 from Algorithm 4, we use the lines (67). Such a method is called Accelerated Malenia SGD.

###### Theorem G.11 .

Let Assumptions G.1 and 1.1, and 1.4 hold. Choose any $\varepsilon>0.$ Let us take $S=\max\left\{\left\lceil(\sigma^{2}R)/(\varepsilon^{3/2}\sqrt{L})\right\rceil,
n\right\},$
and $\gamma=\min\left\{\frac{1}{4L},\left[\frac{3R^{2}S}{4\sigma^{2}(K+1)(K+2)^{2}}
\right]^{1/2}\right\}$ in Accelerated Method 4 (Accelerated Malenia SGD),
then after $K\geq\frac{8\sqrt{L}R}{\sqrt{\varepsilon}}$
iterations the method guarantees that ${\mathbb{E}}\left[f(x^{K})\right]-f(x^{*})\leq\varepsilon,$ where $R=\left\|x^{*}-x^{0}\right\|.$

###### Proof.

Accelerated Malenia SGD is equivalent to the classical accelerated stochastic gradient method with a mini-batch from (Lan, ). The proof repeats the proofs of Theorem G.7 and Theorem G.9.
∎

###### Theorem G.12 .

Consider the assumptions and the parameters from Theorem G.11, plus Assumption 3.1. Then Accelerated Method 4 (Accelerated Malenia SGD) converges after at most $\bar{t}_{\left\lceil\frac{8\sqrt{L}R}{\sqrt{\varepsilon}}\right\rceil}$ seconds, where the sequence $\bar{t}_{k}$ is defined in (18).

###### Proof.

The proof is identical to the proof of Theorem 6.4.
∎

###### Theorem G.11 .

###### Proof.

###### Theorem G.12 .

###### Proof.

## Appendix H Proof of Examples

### H.1 Homogeneous setup

See 5.4

###### Proof.

Clearly, $V_{i}(t)=\int_{0}^{t}v_{i}d\tau=v_{i}t.$ Substituting this to (11), we get
$\bar{t}_{k}=\min\left\{t\geq 0\,:\,\sum_{i=1}^{n}\left\lfloor v_{i}(t-\bar{t}_
{k-1})\right\rfloor\geq\max\left\{\left\lceil\nicefrac{{\sigma^{2}}}{{
\varepsilon}}\right\rceil,1\right\}\right\}(\bar{t}_{0}\equiv 0).$ Equivalently, we have to find $\bar{\delta}$ such that

$$ $\displaystyle\textstyle\bar{\delta}=\min\left\{\delta\geq 0\,:\,\sum\limits_{i =1}^{n}\left\lfloor v_{i}\delta\right\rfloor\geq\max\left\{\left\lceil \nicefrac{{\sigma^{2}}}{{\varepsilon}}\right\rceil,1\right\}\right\}$ (68) $$

and obtain $\bar{t}_{k}=\bar{\delta}+\bar{t}_{k-1}=k\bar{\delta}.$ Let us show that

$$ $\displaystyle\textstyle\bar{\delta}_{\nicefrac{{1}}{{4}}}\leq\bar{\delta}\leq \bar{\delta}_{4}$ (69) $$

where $\pi$ is a permutation such that $v_{\pi_{1}}\geq\dots\geq v_{\pi_{n}},$ and the $\bar{\delta}_{\cdot}$ is defined as

$$ $\displaystyle\textstyle\bar{\delta}_{c}:=c\times\min\limits_{j\in[n]}\left( \sum_{i=1}^{j}v_{\pi_{i}}\right)^{-1}\left(\frac{\sigma^{2}}{\varepsilon}+j \right)=c\times\left(\sum_{i=1}^{j^{*}}v_{\pi_{i}}\right)^{-1}\left(\frac{ \sigma^{2}}{\varepsilon}+j^{*}\right),$ (70) $$

where $j^{*}$ is the largest index that minimizes the formula, and $c>0$ is a constant. Using Lemma F.5, we obtain $1/(4v_{\pi_{j}^{*}})\leq\bar{\delta}_{\nicefrac{{1}}{{4}}}<1/(4v_{\pi_{(j^{*}+
1)}}),$ where we define $\nicefrac{{1}}{{v_{n+1}}}\equiv\infty$ for convenience. Thus

$$ $\displaystyle\textstyle\sum\limits_{i=1}^{n}\left\lfloor v_{i}\bar{\delta}_{ \nicefrac{{1}}{{4}}}\right\rfloor\overset{\bar{\delta}_{\nicefrac{{1}}{{4}}}< \nicefrac{{1}}{{v_{j^{*}+1}}}}{=}\sum\limits_{i=1}^{j^{*}}\left\lfloor v_{\pi_ {i}}\bar{\delta}_{\nicefrac{{1}}{{4}}}\right\rfloor\leq\sum\limits_{i=1}^{j^{* }}\left(2v_{\pi_{i}}\bar{\delta}_{\nicefrac{{1}}{{2}}}-\frac{1}{2}\right) \overset{(\ref{eq:uBHiaI})}{=}\frac{\sigma^{2}}{2\varepsilon}<\max\left\{\left \lceil\frac{\sigma^{2}}{\varepsilon}\right\rceil,1\right\},$ $$

where the first inequality due to $\left\lfloor x\right\rfloor\leq 2x-\frac{1}{2}$ for all $x\geq\nicefrac{{1}}{{4}}.$ Therefore $\bar{\delta}\geq\bar{\delta}_{\nicefrac{{1}}{{4}}}.$ On the other hand

$$ $\displaystyle\textstyle\sum\limits_{i=1}^{n}\left\lfloor v_{i}\bar{\delta}_{4} \right\rfloor\geq\sum\limits_{i=1}^{j^{*}}\left\lfloor v_{\pi_{i}}\bar{\delta} _{4}\right\rfloor\overset{L.\ref{lemma:techn1},\bar{\delta}_{4}\geq\nicefrac{{ 1}}{{v_{j^{*}}}}}{\geq}\frac{1}{2}\sum\limits_{i=1}^{j^{*}}v_{\pi_{i}}\bar{ \delta}_{4}\overset{(\ref{eq:uBHiaI})}{=}2\left(\frac{\sigma^{2}}{\varepsilon} +j^{*}\right)\geq\max\left\{\left\lceil\frac{\sigma^{2}}{\varepsilon}\right \rceil,1\right\}.$ $$

We can conclude that $\bar{\delta}\leq\bar{\delta}_{4},$ and using the inequality $\bar{\delta}\geq\bar{\delta}_{\nicefrac{{1}}{{4}}}$, we have proved (69). It is left to use the equality $\bar{t}_{k}=k\bar{\delta}.$
∎

See 5.5

###### Proof.

We have $V_{i}(t)=\int_{0}^{t}v_{i}g(\tau)d\tau=v_{i}G(t).$ We substitute this equality to (11) and get
$\bar{t}_{k}=\min\left\{t\geq 0\,:\,\sum_{i=1}^{n}\left\lfloor v_{i}(G(t)-G(
\bar{t}_{k-1}))\right\rfloor\geq\max\left\{\left\lceil\nicefrac{{\sigma^{2}}}{
{\varepsilon}}\right\rceil,1\right\}\right\}.$
Since $G(t)$ is continuous and increasing, one can show that
$\textstyle G(\bar{t}_{k})=\min\left\{t\geq 0\,:\,\sum_{i=1}^{n}\left\lfloor v_
{i}(t-G(\bar{t}_{k-1}))\right\rfloor\geq\max\left\{\left\lceil\nicefrac{{
\sigma^{2}}}{{\varepsilon}}\right\rceil,1\right\}\right\}.$ Therefore $G(\bar{t}_{k})=\bar{\delta}+G(\bar{t}_{k-1})=k\bar{\delta}$ and $\bar{t}_{k}=G^{-1}(k\bar{\delta}),$ where $\bar{\delta}$ is defined in (68). Using (69), we get (13).
∎

See 5.6

###### Proof Sketch.

We have $V_{i}(t)=\int_{0}^{t}v_{i}(\tau)d=v\times\mathbbm{1}\left[\textnormal{measure
of intervals before the time }t\right]\approx\nicefrac{{vt}}{{k_{i}}}.$ We substitute it to (11) and get $\bar{t}_{k}:=\min\left\{t\geq 0\,:\,\sum_{i=1}^{n}\left\lfloor\nicefrac{{vt}}{
{k_{i}}}-\nicefrac{{v\bar{t}_{k-1}}}{{k_{i}}}\right\rfloor\geq\max\left\{\left
\lceil\nicefrac{{\sigma^{2}}}{{\varepsilon}}\right\rceil,1\right\}\right\}.$ Using the same reasoning as in Example 5.4, one can easily get (15).
∎

###### Proof.

###### Proof.

###### Proof Sketch.

### H.2 Heterogeneous setup

See 6.5

###### Proof.

Clearly, $V_{i}(t)=\int_{0}^{t}v_{i}d\tau=v_{i}t.$ Substituting this to (18), we get $\bar{t}_{k}:=\min\left\{t\geq 0\,:\,(\nicefrac{{1}}{{n}}\sum_{i=1}^{n}\left
\lfloor v_{i}(t-\bar{t}_{k-1})\right\rfloor^{-1})^{-1}\geq\max\left\{\nicefrac
{{2\sigma^{2}}}{{n\varepsilon}},1\right\}\right\}.$ Equivalently, we have to find $\bar{\delta}$ such that
$\bar{\delta}=\min\left\{\delta\geq 0\,:\,\nicefrac{{1}}{{n}}\sum_{i=1}^{n}
\left\lfloor v_{i}\delta\right\rfloor^{-1}\leq\min\left\{\nicefrac{{n
\varepsilon}}{{2\sigma^{2}}},1\right\}\right\}$
and calculate $\bar{t}_{k}=\delta+\bar{t}_{k-1}=k\bar{\delta}.$ Let us show that

$$ $\displaystyle\textstyle\bar{\delta}_{\nicefrac{{1}}{{4}}}\leq\bar{\delta}\leq \bar{\delta}_{4}$ $$

where the $\bar{\delta}_{\cdot}$ is defined as

$$ $\displaystyle\textstyle\bar{\delta}_{c}:=c\times\left(\max_{i\in[n]}\frac{1}{v _{i}}+\left(\frac{1}{n}\sum_{i=1}^{n}\frac{1}{v_{i}}\right)\frac{\sigma^{2}}{n \varepsilon}\right)$ (71) $$

and $c>0$ is a constant.
Since $\bar{\delta}_{4}\geq\max_{i\in[n]}\frac{1}{v_{i}},$ we have $\left\lfloor v_{i}\delta_{4}\right\rfloor\geq\frac{v_{i}\delta_{4}}{2}$ for all $i\in[n]$ and

$$ $\displaystyle\frac{1}{n}\sum_{i=1}^{n}\left\lfloor v_{i}\delta_{4}\right \rfloor^{-1}\leq\frac{1}{n}\sum_{i=1}^{n}\frac{2}{v_{i}\delta_{4}}\overset{( \ref{eq:neZpKwdjesRZeQSQ})}{\leq}\frac{1}{n}\sum_{i=1}^{n}\frac{1}{1+2v_{i} \left(\frac{1}{n}\sum_{i=1}^{n}\frac{1}{v_{i}}\right)\frac{\sigma^{2}}{n \varepsilon}}$ $\displaystyle\leq\min\left\{\frac{1}{n}\sum_{i=1}^{n}\frac{1}{2v_{i}\left( \frac{1}{n}\sum_{i=1}^{n}\frac{1}{v_{i}}\right)\frac{\sigma^{2}}{n\varepsilon} },1\right\}=\min\left\{\frac{n\varepsilon}{2\sigma^{2}},1\right\}.$ $$

Thus $\bar{\delta}\leq\bar{\delta}_{4}.$ On the other hand, let us show that $\frac{1}{n}\sum_{i=1}^{n}\left\lfloor v_{i}\delta_{\nicefrac{{1}}{{4}}}\right
\rfloor^{-1}>\min\left\{\nicefrac{{n\varepsilon}}{{2\sigma^{2}}},1\right\}.$ If $\max_{i\in[n]}\nicefrac{{1}}{{v_{i}}}>\left(\frac{1}{n}\sum_{i=1}^{n}\nicefrac
{{1}}{{v_{i}}}\right)\nicefrac{{\sigma^{2}}}{{n\varepsilon}},$ then $\delta_{\nicefrac{{1}}{{4}}}<\nicefrac{{1}}{{2}}\max_{i\in[n]}\nicefrac{{1}}{{
v_{i}}},$ $\left\lfloor v_{j}\delta_{\nicefrac{{1}}{{4}}}\right\rfloor=0$ for $j=\arg\max_{i\in[n]}\nicefrac{{1}}{{v_{i}}},$ and $\frac{1}{n}\sum_{i=1}^{n}\left\lfloor v_{i}\delta_{\nicefrac{{1}}{{4}}}\right
\rfloor^{-1}=\infty\geq\nicefrac{{n\varepsilon}}{{2\sigma^{2}}}.$ If $\max_{i\in[n]}\nicefrac{{1}}{{v_{i}}}\leq\left(\frac{1}{n}\sum_{i=1}^{n}
\nicefrac{{1}}{{v_{i}}}\right)\nicefrac{{\sigma^{2}}}{{n\varepsilon}},$ then since $\left\lfloor x\right\rfloor\leq x$ for all $x\geq 0,$ we get

$$ $\displaystyle\frac{1}{n}\sum_{i=1}^{n}\left\lfloor v_{i}\delta_{\nicefrac{{1}} {{4}}}\right\rfloor^{-1}\geq\frac{1}{n}\sum_{i=1}^{n}(v_{i}\delta_{\nicefrac{{ 1}}{{4}}})^{-1}\overset{(\ref{eq:neZpKwdjesRZeQSQ})}{\geq}\frac{1}{n}\sum_{i=1 }^{n}\frac{2}{v_{i}\left(\frac{1}{n}\sum_{i=1}^{n}\frac{1}{v_{i}}\right)\frac{ \sigma^{2}}{n\varepsilon}}>\frac{n\varepsilon}{2\sigma^{2}}.$ $$

Therefore $\frac{1}{n}\sum_{i=1}^{n}\left\lfloor v_{i}\delta_{\nicefrac{{1}}{{4}}}\right
\rfloor^{-1}>\min\left\{\nicefrac{{n\varepsilon}}{{2\sigma^{2}}},1\right\},$ meaning $\bar{\delta}\geq\delta_{\nicefrac{{1}}{{4}}}.$
∎

###### Proof.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
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.
2. 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?
3. 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.
4. 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?
5. 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?
soundness: 4
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. 
2. **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. 
3. **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.
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.
weaknesses: There are no significant weaknesses in this paper, but I think the following may help improve the writing and exposition:
1. See my question about [[3]](https://arxiv.org/abs/2305.12387) below.
2. 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.
3. 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).

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
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?
soundness: 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.

- It defines a class of algorithms within this new framework and derives tight lower bounds achievable by optimal algorithms.

- The paper also connects previously developed algorithms for distributed stochastic gradient descent, showing that they remain optimal in this new setting.
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.
weaknesses: The paper lacks numerical results and experiments, which would strengthen its contributions.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
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.
soundness: 3
strengths: This paper offers a very detailed analysis for distributed SGD 
- 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].
- For the proposed setting, this paper offers matching lower and upper bound, thus provides a complete narrative for this problem.

I 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.

The introduction is direct and concise and I immediately know what kind of results I should expect to see in the technical sections.

[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.
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.
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.

For equations (12) (13) and (15), I think the minimum is always at $m=1$ and therefore redundant?

The 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.

Lastly and most importantly, **I do not think this paper has sufficient delta from earlier work [1].** 
- 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.
- 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.

In 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.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: 1. Does the computation power characterize server’s computation speed? 
2. 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?
3. Line 209: What does $\mathcal{D}$ mean?
soundness: 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.
2. The analysis encompasses a broad range of stochastic optimization methods and considers both homogeneous and heterogeneous computing environments.
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.
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.
2. 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?

Meta-review: The paper provides new lower bounds for parallel optimization in scenarios where workers can experience arbitrary delays. The proposed framework accounts for arbitrary computational capacities of workers, capturing their instability and time-varying nature. The paper derives tight lower bounds for synchronous and asynchronous optimization methods in homogeneous and heterogeneous settings and highlights that these bounds are matched by Rennala SGD and Malenia SGD methods (up to logarithmic factors in some cases).

The results extend prior work [1], which focused on a "fixed computation model" and derived analogous tightness results for Rennala SGD and Malenia SGD in homogeneous and heterogeneous settings.

While all reviewers agree that this paper is technically sophisticated and sound, they debated whether the contributions beyond [1] provide sufficient novelty and value to the community. Reviewer uBjW strongly supports acceptance, arguing that the universal computation model itself is an independent and non-trivial contribution that closes important gaps in parallel optimization. In contrast, reviewer FEY6 believes that the overlap in the general setup and ideas with [1] diminishes the value of the new results, noting that the technical approach is very similar, with only some parts of the proof (e.g., concentration inequalities) requiring modification.

The opinions on the paper remained divided after the discussion. 

To some extent, I agree with reviewer FEY6 that the additional novelty compared to [1] is modest, and perhaps a comprehensive journal publication would have provided the most value to the community. However, two reviewers argue that the paper can also stand alone as a publication at ICLR.

[1]: A. Tyurin, P. Richtarik. Optimal Time Complexities of Parallel Stochastic Optimization Methods Under a Fixed Computation Model, https://arxiv.org/abs/2305.12387

Decision: Accept (Poster)