Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction

## Abstract

Abstract We consider centralized distributed optimization in the classical federated learning setup, where n 𝑛 n italic_n workers jointly find an ε 𝜀 \varepsilon italic_ε –stationary point of an L 𝐿 L italic_L –smooth, d 𝑑 d italic_d –dimensional nonconvex function f 𝑓 f italic_f , having access only to unbiased stochastic gradients with variance σ 2 superscript 𝜎 2 \sigma^{2} italic_σ start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT . Each worker requires at most h ℎ h italic_h seconds to compute a stochastic gradient, and the communication times from the server to the workers and from the workers to the server are τ s subscript 𝜏 s \tau_{\textnormal{s}} italic_τ start_POSTSUBSCRIPT s end_POSTSUBSCRIPT and τ w subscript 𝜏 w \tau_{\textnormal{w}} italic_τ start_POSTSUBSCRIPT w end_POSTSUBSCRIPT seconds per coordinate, respectively. One of the main motivations for distributed optimization is to achieve scalability with respect to n 𝑛 n italic_n . For instance, it is well known that the distributed version of SGD has a variance-dependent runtime term h ⁢ σ 2 ⁢ L ⁢ Δ / n ⁢ ε 2 , ℎ superscript 𝜎 2 𝐿 Δ 𝑛 superscript 𝜀 2 \nicefrac{{h\sigma^{2}L\Delta}}{{n\varepsilon^{2}}}, / start_ARG italic_h italic_σ start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT italic_L roman_Δ end_ARG start_ARG italic_n italic_ε start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT end_ARG , which improves with the number of workers n , 𝑛 n, italic_n , where Δ := f ⁢ ( x 0 ) − f ∗ , assign Δ 𝑓 superscript 𝑥 0 superscript 𝑓 \Delta:=f(x^{0})-f^{*}, roman_Δ := italic_f ( italic_x start_POSTSUPERSCRIPT 0 end_POSTSUPERSCRIPT ) - italic_f start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT , and x 0 ∈ ℝ d superscript 𝑥 0 superscript ℝ 𝑑 x^{0}\in\mathbb{R}^{d} italic_x start_POSTSUPERSCRIPT 0 end_POSTSUPERSCRIPT ∈ blackboard_R start_POSTSUPERSCRIPT italic_d end_POSTSUPERSCRIPT is the starting point. Similarly, using unbiased sparsification compressors, it is possible to reduce both the variance-dependent runtime term and the communication runtime term from τ w ⁢ d ⁢ L ⁢ Δ / ε subscript 𝜏 w 𝑑 𝐿 Δ 𝜀 \tau_{\textnormal{w}}d\nicefrac{{L\Delta}}{{\varepsilon}} italic_τ start_POSTSUBSCRIPT w end_POSTSUBSCRIPT italic_d / start_ARG italic_L roman_Δ end_ARG start_ARG italic_ε end_ARG to τ w ⁢ d ⁢ L ⁢ Δ / n ⁢ ε + τ w ⁢ d ⁢ h ⁢ σ 2 / n ⁢ ε ⋅ L ⁢ Δ / ε , subscript 𝜏 w 𝑑 𝐿 Δ 𝑛 𝜀 ⋅ subscript 𝜏 w 𝑑 ℎ superscript 𝜎 2 𝑛 𝜀 𝐿 Δ 𝜀 \nicefrac{{\tau_{\textnormal{w}}dL\Delta}}{{n\varepsilon}}+\sqrt{\nicefrac{{%
\tau_{\textnormal{w}}dh\sigma^{2}}}{{n\varepsilon}}}\cdot\nicefrac{{L\Delta}}{%
{\varepsilon}}, / start_ARG italic_τ start_POSTSUBSCRIPT w end_POSTSUBSCRIPT italic_d italic_L roman_Δ end_ARG start_ARG italic_n italic_ε end_ARG + square-root start_ARG / start_ARG italic_τ start_POSTSUBSCRIPT w end_POSTSUBSCRIPT italic_d italic_h italic_σ start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT end_ARG start_ARG italic_n italic_ε end_ARG end_ARG ⋅ / start_ARG italic_L roman_Δ end_ARG start_ARG italic_ε end_ARG , which also benefits from increasing n . 𝑛 n. italic_n . However, once we account for the communication from the server to the workers τ s subscript 𝜏 s \tau_{\textnormal{s}} italic_τ start_POSTSUBSCRIPT s end_POSTSUBSCRIPT , we prove that it becomes infeasible to design a method using unbiased random sparsification compressors that scales both the server-side communication runtime term τ s ⁢ d ⁢ L ⁢ Δ / ε subscript 𝜏 s 𝑑 𝐿 Δ 𝜀 \tau_{\textnormal{s}}d\nicefrac{{L\Delta}}{{\varepsilon}} italic_τ start_POSTSUBSCRIPT s end_POSTSUBSCRIPT italic_d / start_ARG italic_L roman_Δ end_ARG start_ARG italic_ε end_ARG and the variance-dependent runtime term h ⁢ σ 2 ⁢ L ⁢ Δ / ε 2 , ℎ superscript 𝜎 2 𝐿 Δ superscript 𝜀 2 \nicefrac{{h\sigma^{2}L\Delta}}{{\varepsilon^{2}}}, / start_ARG italic_h italic_σ start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT italic_L roman_Δ end_ARG start_ARG italic_ε start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT end_ARG , better than poly-logarithmically in n 𝑛 n italic_n , even in the homogeneous (i.i.d.) case, where all workers access the same function or distribution. Indeed, when τ s ≃ τ w , similar-to-or-equals subscript 𝜏 s subscript 𝜏 w \tau_{\textnormal{s}}\simeq\tau_{\textnormal{w}}, italic_τ start_POSTSUBSCRIPT s end_POSTSUBSCRIPT ≃ italic_τ start_POSTSUBSCRIPT w end_POSTSUBSCRIPT , our lower bound is Ω ~ ⁢ ( min ⁡ { h ⁢ ( σ 2 n ⁢ ε + 1 ) ⁢ L ⁢ Δ ε + τ s ⁢ d ⁢ L ⁢ Δ ε , h ⁢ L ⁢ Δ ε + h ⁢ σ 2 ⁢ L ⁢ Δ ε 2 } ) . ~ Ω ℎ superscript 𝜎 2 𝑛 𝜀 1 𝐿 Δ 𝜀 subscript 𝜏 s 𝑑 𝐿 Δ 𝜀 ℎ 𝐿 Δ 𝜀 ℎ superscript 𝜎 2 𝐿 Δ superscript 𝜀 2 \textstyle\tilde{\Omega}\left(\min\left\{h\left(\frac{\sigma^{2}}{n\varepsilon%
}+1\right)\frac{L\Delta}{\varepsilon}+{\color[rgb]{%
0.92578125,0.578125,0.0546875}\definecolor[named]{pgfstrokecolor}{rgb}{%
0.92578125,0.578125,0.0546875}\tau_{\textnormal{s}}d\frac{L\Delta}{\varepsilon%
}},\;h\frac{L\Delta}{\varepsilon}+{\color[rgb]{0.92578125,0.578125,0.0546875}%
\definecolor[named]{pgfstrokecolor}{rgb}{0.92578125,0.578125,0.0546875}h\frac{%
\sigma^{2}L\Delta}{\varepsilon^{2}}}\right\}\right). over~ start_ARG roman_Ω end_ARG ( roman_min { italic_h ( divide start_ARG italic_σ start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT end_ARG start_ARG italic_n italic_ε end_ARG + 1 ) divide start_ARG italic_L roman_Δ end_ARG start_ARG italic_ε end_ARG + italic_τ start_POSTSUBSCRIPT s end_POSTSUBSCRIPT italic_d divide start_ARG italic_L roman_Δ end_ARG start_ARG italic_ε end_ARG , italic_h divide start_ARG italic_L roman_Δ end_ARG start_ARG italic_ε end_ARG + italic_h divide start_ARG italic_σ start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT italic_L roman_Δ end_ARG start_ARG italic_ε start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT end_ARG } ) . To establish this result, we construct a new “worst-case” function and develop a new lower bound framework that reduces the analysis to the concentration of a random sum, for which we prove a concentration bound. These results reveal fundamental limitations in scaling distributed optimization, even under the homogeneous (i.i.d.) assumption.

## 1 Introduction

[Uncaptioned image]: x1.png

We focus on the classical federated learning setup, where $n$ workers, such as CPUs, GPUs, servers, or mobile devices, are connected to a central server via a communication channel (Konečný et al., 2016; McMahan et al., 2017). All workers collaboratively solve a common optimization problem in a distributed fashion by computing stochastic gradients and sharing this information with the server, which then propagates it to other workers. Together, they aim to minimize a smooth nonconvex objective function defined as

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

where $f\,:\,\mathbb{R}^{d}\rightarrow\mathbb{R}$ and $d$ is the dimension of $f$. We assume that $d$ is huge, which is indeed the case in modern machine learning and large language model training (Brown et al., 2020; Touvron et al., 2023).

We consider the *homogeneous* (i.i.d.) setting, where all workers have access to stochastic gradients of the same underlying function $f$. As the reader will see, the homogeneous setting assumption is a challenge, not a limitation of our work: all results
extend, potentially with even stronger implications, to the more general *heterogeneous* (non-i.i.d.) case, when each worker $i$ works with $f_{i}\neq f.$ We consider the 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}$. We define $\Delta:=f(x^{0})-f^{*},$ where $x^{0}$ is a starting point of methods.

For all $i\in[n],$ worker $i$ calculates unbiased stochastic gradients $\nabla f(x;\xi)$ with $\sigma^{2}$-variance-bounded variances, where $\xi$ is a random variable with some distribution $\mathcal{D}_{\xi}.$

###### Assumption 1.3 (Homogeneous setting) .

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

The goal in the nonconvex world is to find an $\varepsilon$–stationary point, a (random) point $\bar{x}\in\mathbb{R}^{d}$ such that ${\rm\mathbb{E}}[\|\nabla f(\bar{x})\|^{2}]\leq\varepsilon$ (Nemirovskij & Yudin, 1983; Murty & Kabadi, 1985).
We also consider a realistic computation and communication scenario:

###### Assumption 1.4 .

Each of the $n$ workers requires at most $h$ seconds to compute a stochastic gradient, and communication *from the server to any worker* (s2w communication) takes at most $\tau_{\textnormal{s}}$ seconds per coordinate, and communication *from any worker to the server* (w2s communication) takes at most $\tau_{\textnormal{w}}$ seconds per coordinate.

For instance, under Assumption [1.4](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem4), it takes $d\times\tau_{\textnormal{s}}$ and $d\times\tau_{\textnormal{w}}$ seconds to send a vector $v\in\mathbb{R}^{d}$ from the server to any worker and from any worker to the server, respectively. We consider settings with bidirectional communication costs, where communication in both directions requires time. Typically, especially in the early stages of federated learning algorithm development, most works assume that communication *from the server to the workers* is free, i.e., $\tau_{\textnormal{s}}=0,$ which is arguably not true in practice: communication over the Internet or 4G/5G networks can be costly in both directions (Huang et al., 2012; Narayanan et al., 2021).

###### Assumption 1.1 .

###### Assumption 1.2 .

###### Assumption 1.3 (Homogeneous setting) .

###### Assumption 1.4 .

### 1.1 Related work

1. Communication is free. Let us temporarily assume that communication does not take time, i.e., $\tau_{\textnormal{s}}=0$ and $\tau_{\textnormal{w}}=0.$ Then, in this scenario, the theoretically fastest strategy is to run the Synchronized SGD method, i.e., $x^{k+1}=x^{k}-\frac{\gamma}{n}\sum_{i=1}^{n}\nabla f(x^{k};\xi^{k}_{i}),$ where $\gamma=\Theta(\min\{\nicefrac{{1}}{{L}},\nicefrac{{\varepsilon n}}{{L\sigma^{2
}}}\}),$ $\{\xi^{k}_{i}\}$ are i.i.d., and $\{\nabla f(x^{k};\xi^{k}_{i})\}$ are computed in parallel by the workers, which send to the server that aggregates and calculates $x^{k+1}.$ One can show that the time complexity of this method is
$\textstyle\mathcal{O}\bigl{(}h\bigl{(}\frac{L\Delta}{\varepsilon}+\frac{\sigma
^{2}L\Delta}{n\varepsilon^{2}}\bigr{)}\bigr{)},$
because it requires $\mathcal{O}\bigl{(}\frac{L\Delta}{\varepsilon}+\frac{\sigma^{2}L\Delta}{n
\varepsilon^{2}}\bigr{)}$ iterations (Lan, 2020), and each iteration takes at most $h$ seconds due to Assumption [1.4](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem4). Moreover, this result is *optimal and can not be improved* (Arjevani et al., 2022; Tyurin & Richtárik, 2023b).

Observation 1: One obvious but important observation is that the second “statistical term” in the complexity bound scales with $n$. The larger the number of workers $n$, the smaller the overall time complexity of Synchronized SGD, with a linear improvement in $n$. This is a theoretical justification for the importance of distributed optimization and the use of many workers.

2. Worker-to-server communication can not be ignored. For now, consider the setup where communication from workers to the server takes $\tau_{\textnormal{w}}>0$ seconds, while communication from the server to the workers is free, i.e., $\tau_{\textnormal{s}}=0.$ In this scenario, the described version of Synchronized SGD has a suboptimal $\mathcal{O}\bigl{(}h\bigl{(}\frac{L\Delta}{\varepsilon}+\frac{\sigma^{2}L
\Delta}{n\varepsilon^{2}}\bigr{)}+{\color[rgb]{0.92578125,0.578125,0.0546875}
\definecolor[named]{pgfstrokecolor}{rgb}{0.92578125,0.578125,0.0546875}\tau_{
\textnormal{w}}d\bigl{(}\frac{L\Delta}{\varepsilon}+\frac{\sigma^{2}L\Delta}{n
\varepsilon^{2}}\bigr{)}}\bigr{)}$ time complexity, because it takes $h$ seconds to calculate a stochastic gradient and $\tau_{\textnormal{w}}d$ seconds to send the stochastic gradients of size $d$ to the server, which calculates $x^{k+1}.$ However, if we slightly modify this method and consider Batch Synchronized SGD:

$$ $\displaystyle\phantom{\textnormal{{\sf Batch Synchronized SGD}}}\textstyle x^{ k+1}=x^{k}-\frac{\gamma}{n}\sum\limits_{i=1}^{n}\frac{1}{b}\sum\limits_{j=1}^{ b}\nabla f(x^{k};\xi^{k}_{ij})$ ( Batch Synchronized SGD ) $$

with $b=\Theta(\nicefrac{{\sigma^{2}}}{{\varepsilon n}})$ and $\gamma=\Theta(\nicefrac{{1}}{{L}}),$ then the time complexity becomes

$$ $\displaystyle\textstyle\mathcal{O}\left(h\left(\frac{L\Delta}{\varepsilon}+ \frac{\sigma^{2}L\Delta}{n\varepsilon^{2}}\right)+{\color[rgb]{ 0.92578125,0.578125,0.0546875}\definecolor[named]{pgfstrokecolor}{rgb}{ 0.92578125,0.578125,0.0546875}\tau_{\textnormal{w}}d\frac{L\Delta}{\varepsilon }}\right),$ (2) $$

because the number of iterations reduces to $\mathcal{O}\left(\nicefrac{{L\Delta}}{{\varepsilon}}\right).$ In other words, each worker, instead of immediately sending a gradient, locally aggregates a batch of size $b$ to reduce the number of communications. It turns out that the last complexity can be improved further with the help of unbiased compressors:

###### Definition 1.5 .

A mapping $\mathcal{C}\,:\,\mathbb{R}^{d}\times\mathbb{S}_{\nu}\rightarrow\mathbb{R}^{d}$ with a distribution $\mathcal{D}_{\nu}$ is an unbiased compressor if there exists $\omega\geq 0$ such that
$\mathbb{E}_{\nu}[\mathcal{C}(x;\nu)]=x$ and $\mathbb{E}_{\nu}[\left\|\mathcal{C}(x;\nu)-x\right\|^{2}]\leq\omega\left\|x
\right\|^{2}$
for all $x\in\mathbb{R}^{d}$. We $\mathbb{U}(\omega)$ denote the family of such compressors. The community uses the shorthand $\mathcal{C}(x;\nu)\equiv\mathcal{C}(x),$ which we also follow.

A standard example of an unbiased compressor is Rand$K$ $\in\mathbb{U}(\nicefrac{{d}}{{K}}-1),$ which selects $K$ random coordinates of the input vector $x$, scales them by $\nicefrac{{d}}{{K}}$, and sets the remaining coordinates to zero (see Def. [A.1](https://arxiv.org/html/2506.23836v1#A1.Thmtheorem1)). Numerous other examples of unbiased compressors have been explored in the literature (Beznosikov et al., 2020; Xu et al., 2021; Horváth et al., 2022; Szlendak et al., 2021).
Using the seminal ideas (Seide et al., 2014), we can construct a modified version of QSGD (Alistarh et al., 2017) (special case of Shadowheart SGD from (Tyurin et al., 2024)), which we call Batch QSGD:

$$ $\displaystyle\phantom{\textnormal{{\sf Batch QSGD}}}\textstyle x^{k+1}=x^{k}- \frac{\gamma}{nbm}\sum\limits_{i=1}^{n}\sum\limits_{k=1}^{m}\mathcal{C}_{ik} \left(\sum\limits_{j=1}^{b}\nabla f(x^{k};\xi^{k}_{ij})\right),$ ( Batch QSGD ) $$

where worker $i$ sends $m$ compressed vectors $\{\mathcal{C}_{ik}(\cdot)\}_{k\in[m]}$ to the server, which aggregates and calculates $x^{k+1}.$ With Rand$K$ and proper parameters(^1^11$b=\Theta(\frac{t^{*}}{h}),$ $m=\Theta(\frac{t^{*}}{\tau_{\textnormal{w}}}),$ $t^{*}=\Theta\left(\max\left\{h,\tau_{\textnormal{w}},\frac{\tau_{\textnormal{w }}d}{n},\frac{h\sigma^{2}}{n\varepsilon},\sqrt{\frac{d\tau_{\textnormal{w}}h \sigma^{2}}{n\varepsilon}}\right\}\right),$ $\gamma=\Theta(\frac{1}{L}),$ $K=1$ in Rand$K$)
(Tyurin et al., 2024), we can improve ([2](https://arxiv.org/html/2506.23836v1#S1.E2)) to

$$ $\displaystyle\textstyle\mathcal{O}\left(h\left(1+\frac{\sigma^{2}}{n \varepsilon}\right)\frac{L\Delta}{\varepsilon}+\tau_{\textnormal{w}}\left( \frac{d}{n}+1\right)\frac{L\Delta}{\varepsilon}+\sqrt{\frac{d\tau_{\textnormal {w}}h\sigma^{2}}{n\varepsilon}}\frac{L\Delta}{\varepsilon}\right).$ (3) $$

Observation 2: As in Observation 1, unlike ([2](https://arxiv.org/html/2506.23836v1#S1.E2)), the time complexity ([3](https://arxiv.org/html/2506.23836v1#S1.E3)) scales with the number of workers $n,$ which once again justifies the use of many workers in the optimization of ([1](https://arxiv.org/html/2506.23836v1#S1.E1)). The “statistical term” $\nicefrac{{h\sigma^{2}L\Delta}}{{n\varepsilon^{2}}}$ and the “communication term” $\nicefrac{{\tau_{\textnormal{w}}dL\Delta}}{{n\varepsilon}}$ improve linearly with $n,$ while the “coupling term” $\sqrt{\nicefrac{{d\tau_{\textnormal{w}}h\sigma^{2}}}{{n\varepsilon}}}\nicefrac
{{L\Delta}}{{\varepsilon}}$ improves with the square root of $n,$ which can reduce the effect of $d$ and $\nicefrac{{\sigma^{2}}}{{\varepsilon}}$ for reasonably large $n.$

A high-level explanation for why the dependence on $d$ improves with $n$ is that all workers use i.i.d. and unbiased compressors $\{\mathcal{C}_{ik}\},$ which allow them to collaboratively explore more coordinates. This effect is similar to Synchronized SGD, where the variance ${\rm\mathbb{E}}_{\xi}[\|\frac{1}{n}\sum_{i=1}^{n}\nabla f(x;\xi^{k}_{i})-
\nabla f(x)\|^{2}]\leq\frac{\sigma^{2}}{n}$ also improves with $n.$ There are many other compressed methods that also improve with $n,$ including DIANA (Mishchenko et al., 2019), Accelerated DIANA (Li et al., 2020), MARINA (Gorbunov et al., 2021), DASHA (Tyurin & Richtárik, 2023a), and FRECON (Zhao et al., 2021).

3. Both communications can not be ignored. Consider a more practical scenario, and our main point of interest, where the communication time from the server to the workers is $\tau_{\textnormal{s}}>0.$ In this case, [Batch QSGD](https://arxiv.org/html/2506.23836v1#S1.Ex2) requires

$$ $\displaystyle\textstyle\mathcal{O}\left(h\left(1+\frac{\sigma^{2}}{n \varepsilon}\right)\frac{L\Delta}{\varepsilon}+\tau_{\textnormal{w}}\left( \frac{d}{n}+1\right)\frac{L\Delta}{\varepsilon}+\sqrt{\frac{d\tau_{\textnormal {w}}h\sigma^{2}}{n\varepsilon}}\frac{L\Delta}{\varepsilon}+{\color[rgb]{ 0.92578125,0.578125,0.0546875}\definecolor[named]{pgfstrokecolor}{rgb}{ 0.92578125,0.578125,0.0546875}\tau_{\textnormal{s}}d\frac{L\Delta}{\varepsilon }}\right)$ (4) $$

seconds because the server has to send $x^{k}\in\mathbb{R}^{d}$ of size $d$ to the workers in every iteration.

Observation 3: If $\tau_{\textnormal{s}}\simeq\tau_{\textnormal{w}}$, then ([4](https://arxiv.org/html/2506.23836v1#S1.E4)) asymptotically equals $\mathcal{O}\left(h\left(\nicefrac{{L\Delta}}{{\varepsilon}}+\nicefrac{{\sigma^
{2}L\Delta}}{{n\varepsilon^{2}}}\right)+\tau_{\textnormal{s}}d\nicefrac{{L
\Delta}}{{\varepsilon}}\right),$ reducing to ([2](https://arxiv.org/html/2506.23836v1#S1.E2)), as in the method that does not compress at all! The “communication term” $\tau_{\textnormal{s}}d\nicefrac{{L\Delta}}{{\varepsilon}}$ does not improve with $n.$

We now arrive at our main research question:

> In the first case (1. Communication is free) and the second case (2. Worker-to-server communication can not be ignored), it is possible to design a method that scales the complexity with the number of workers $n,$ while improving the dependencies on $d$ and $\nicefrac{{\sigma^{2}}}{{\varepsilon}}.$ Can we design a similarly efficient method for the third case (3. Both communications can not be ignored) using unbiased compressors, where the communication time from the server to the workers cannot be ignored, and where the dependence on both $d$ and $\nicefrac{{\sigma^{2}}}{{\varepsilon}}$ improves with $n,$ either linearly or with the square root of $n$? At least, can this be achieved in the simplest homogeneous setting, where all workers have access to the same function, a scenario that arguably represents the simplest form of distributed optimization?

We know for certain that the answer is “No” in the *heterogeneous case*, due to the result of Gruntkowska et al. (2024), who proved that the iteration complexity does not improve with the number of workers $n$ under Assumptions [1.1](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem1) and [1.2](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem2). However, the homogeneous setting is “easier,” giving us hope that the workers can exploit the fact that they all have access to the same distribution.

###### Definition 1.5 .

### 1.2 Contributions

$\spadesuit$ Lower bound. Surprisingly, the answer is “No” to our main research question, even in the *homogeneous case*. We prove the following theorem.

###### Theorem 1.6 (Informal Formulation of Theorems 4.2 and D.1 ) .

Let Assumptions [1.1](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem1), [1.2](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem2), [1.3](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem3), and [1.4](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem4) hold. It is infeasible to find an $\varepsilon$–stationary point faster than

$$ $\displaystyle\textstyle\tilde{\Omega}\left(\min\left\{h\left(\frac{\sigma^{2}} {n\varepsilon}+1\right)\frac{L\Delta}{\varepsilon}+\tau_{\textnormal{w}}\left( \frac{d}{n}+1\right)\frac{L\Delta}{\varepsilon}+\sqrt{\frac{d\tau_{\textnormal {w}}h\sigma^{2}}{n\varepsilon}}\frac{L\Delta}{\varepsilon}+{\color[rgb]{ 0.92578125,0.578125,0.0546875}\definecolor[named]{pgfstrokecolor}{rgb}{ 0.92578125,0.578125,0.0546875}\tau_{\textnormal{s}}d\frac{L\Delta}{\varepsilon }},h\frac{L\Delta}{\varepsilon}+{\color[rgb]{0.92578125,0.578125,0.0546875} \definecolor[named]{pgfstrokecolor}{rgb}{0.92578125,0.578125,0.0546875}h\frac{ \sigma^{2}L\Delta}{\varepsilon^{2}}}\right\}\right)$ (5) $$

seconds (up to logarithmic factors), using unbiased compressors (Def. [1.5](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem5)) based on random sparsification, for all $L,\Delta,\varepsilon,n,\sigma^{2},d,\tau_{\textnormal{w}},\tau_{\textnormal{s}
},h>0$ such that $L\Delta\geq\tilde{\Theta}(\varepsilon)$ and dimension $d\geq\tilde{\Theta}\left(\nicefrac{{L\Delta}}{{\varepsilon}}\right).$

Because of the $\min$, the bound shows that it is possible to improve either the dependence on $d$ or the dependence on $\nicefrac{{\sigma^{2}}}{{\varepsilon}}$ as the number of workers $n$ increases, but not both simultaneously. The lower bound is matched either by [Batch QSGD](https://arxiv.org/html/2506.23836v1#S1.Ex2) or by the non-distributed SGD method (without any communication or cooperation). Moreover, if $\tau_{\textnormal{s}}\simeq\tau_{\textnormal{w}},$ the lower bound becomes $\tilde{\Omega}\left(\min\left\{h\left(\frac{\sigma^{2}}{n\varepsilon}+1\right)
\frac{L\Delta}{\varepsilon}+{\color[rgb]{0.92578125,0.578125,0.0546875}
\definecolor[named]{pgfstrokecolor}{rgb}{0.92578125,0.578125,0.0546875}\tau_{
\textnormal{s}}d\frac{L\Delta}{\varepsilon}},h\frac{L\Delta}{\varepsilon}+{
\color[rgb]{0.92578125,0.578125,0.0546875}\definecolor[named]{pgfstrokecolor}{
rgb}{0.92578125,0.578125,0.0546875}h\frac{\sigma^{2}L\Delta}{\varepsilon^{2}}}
\right\}\right),$ which can be matched by [Batch Synchronized SGD](https://arxiv.org/html/2506.23836v1#S1.Ex1) with the complexity ([2](https://arxiv.org/html/2506.23836v1#S1.E2)) (without compression) or by the non-distributed SGD method.

$\clubsuit$ New “worst-case” function. To prove the lower bound, as we explain in Section [2.3](https://arxiv.org/html/2506.23836v1#S2.SS3), we needed a new “worst-case” function construction (see Section [3](https://arxiv.org/html/2506.23836v1#S3)). We designed a new function $F_{T,K,a}$ in ([9](https://arxiv.org/html/2506.23836v1#S3.E9)), which extends the ideas by Carmon et al. (2020). Proving its properties in Lemmas [3.1](https://arxiv.org/html/2506.23836v1#S3.Thmtheorem1) and [3.2](https://arxiv.org/html/2506.23836v1#S3.Thmtheorem2), as well as designing the function itself, can be an important contribution on its own.

Proof technique. Using the new function, we develop a new proof technique and explain how the problem of establishing the lower bound reduces to a statistical problem (see Section [4](https://arxiv.org/html/2506.23836v1#S4)), where we need to prove a concentration bound for a special sum ([13](https://arxiv.org/html/2506.23836v1#S4.E13)), which represents the minimal possible random time required to find an $\varepsilon$–stationary point. Combining this result with the proven properties, we obtain our main result ([11](https://arxiv.org/html/2506.23836v1#S4.E11)).

Improved analysis when $\tau_{\textnormal{w}}>0.$ To obtain the complete lower bound, we extended and improved the result by Tyurin et al. (2024), which was limited for our scenario and required additional modifications to finally obtain ([5](https://arxiv.org/html/2506.23836v1#S1.E5)) (see Sections [D](https://arxiv.org/html/2506.23836v1#A4) and [5](https://arxiv.org/html/2506.23836v1#S5) for details).

###### Theorem 1.6 (Informal Formulation of Theorems 4.2 and D.1 ) .

## 2 Preliminaries

For better comprehension of our new idea, we now present arguably one of the most important worst-case functions by Carmon et al. (2020), which is widely used to prove lower bounds in nonconvex optimization. It has been used by Arjevani et al. (2022; 2020) to derive lower bounds in the stochastic setting, by Lu & De Sa (2021) in the decentralized setting, by Tyurin & Richtárik (2023b; 2024); Tyurin et al. (2024) in the asynchronous setting, by Huang et al. (2022) to show the lower iteration bound for unidirectional compressed methods, and by Li et al. (2021) in problems with a nonconvex-strongly-concave structure.

For any $T\in\mathbb{N},$ Carmon et al. (2020) define $F_{T}\,:\,\mathbb{R}^{T}\to\mathbb{R}$ such that (^2^22similarly $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]$ because $\Psi(-1)=0.$)

$$ $\displaystyle\textstyle F_{T}(x):=\sum\limits_{i=1}^{T}\left[\Psi(-x_{i-1}) \Phi(-x_{i})-\Psi(x_{i-1})\Phi(x_{i})\right],$ (6) $$

where $x_{0}\equiv 1,$ $x_{i}$ is the $i$^th coordinate of $x\in\mathbb{R}^{T},$

$$ $\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.$ (7) $$

Notice that this function has a “chain–like” structure. If a method starts from $x^{0}=0$ and computes the gradient of $F_{T},$ then the gradient will have a non-zero value only in the first coordinate (use that $\Psi(0)=\Psi^{\prime}(0)=0$). Thus, by computing a single gradient, any “reasonable” method can “discover” at most one coordinate. At the same time, if the method wants to find an $\varepsilon$–stationary point, it should eventually discover the $T$^th coordinate. These two facts imply that every “reasonable” method should compute the gradient of $F_{T}$ at least $T$ times. In the construction, Carmon et al. (2020) take $T=\Theta\left(\frac{L\Delta}{\varepsilon}\right).$ This construction is a “more technical” version of the celebrated quartic optimization construction from (Nesterov, 2018), which has similar properties.
Let us define $\textnormal{prog}(x):=\max\{i~{}\geq~{}0\,|\,x_{i}\neq 0\}\,\,(x_{0}\equiv 1),$ then the following lemma is a formalization of the described properties.

###### Lemma 2.1 ( Carmon et al. ( 2020 ) ) .

The function $F_{T}$ satisfies:

- 1.
For all $x\in\mathbb{R}^{T},$ $\textnormal{prog}(\nabla F_{T}(x))\leq\textnormal{prog}(x)+1.$
- 2.
For all $x\in\mathbb{R}^{T},$ if $\textnormal{prog}(x)<T,$ then $\left\|\nabla F_{T}(x)\right\|>1.$

Actually, in most proofs, the structure of ([6](https://arxiv.org/html/2506.23836v1#S2.E6)) is not needed, and it is sufficient to work with Lemmas [2.1](https://arxiv.org/html/2506.23836v1#S2.Thmtheorem1) and Lemma [2.2](https://arxiv.org/html/2506.23836v1#S2.Thmtheorem2) from below, where the latter allows us to show that a scaled version of $F_{T}$ satisfies Assumptions [1.1](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem1) and [1.2](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem2).

###### Lemma 2.2 ( Carmon et al. ( 2020 ) ) .

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 $\ell_{1}$–smooth, where $\ell_{1}:=152.$
- 3.
For all $x\in\mathbb{R}^{T},$ $\left\|\nabla F_{T}(x)\right\|_{\infty}\leq\gamma_{\infty},$ where $\gamma_{\infty}:=23.$

Hence, one of the main results by Carmon et al. (2020) was to show that it is infeasible to find an $\varepsilon$–stationary point without calculating $\mathcal{O}\left(\frac{L\Delta}{\varepsilon}\right)$ gradients of a function satisfying Assumptions [1.1](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem1) and [1.2](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem2). In turn, the classical gradient descent (GD) method matches this lower bound.

###### Lemma 2.1 ( Carmon et al. ( 2020 ) ) .

###### Lemma 2.2 ( Carmon et al. ( 2020 ) ) .

### 2.1 Family of distributed methods

In our lower bound, we focus on the family of methods described by Protocol [1](https://arxiv.org/html/2506.23836v1#alg1). This protocol takes an algorithm as input and runs the standard functions of the workers and the server: the workers compute stochastic gradients locally, the server aggregates them asynchronously and in parallel, and sends compressed information back based on the local information. For now, notice that we ignore the communication times from the workers to the server in Protocol [1](https://arxiv.org/html/2506.23836v1#alg1), assuming that $\tau_{\textnormal{w}}=0.$ If we start considering this cost, then the following lower bounds can only increase.

For all $i\in[n],$ the algorithm can choose any point, based on the local information $I_{i},$ at which worker $i$ will start computing a stochastic gradient. It can also choose any point $s^{k}_{i},$ based on the server’s local information $I,$ along with the corresponding compressor $\mathcal{C}^{k}_{i},$ which will be sent to worker $i.$ This protocol captures the behavior of virtually any asynchronous optimization process with workers connected to a server. We work with *zero-respecting* algorithms, as defined below.

###### Definition 2.3 .

We say that an algorithm $A$ that follows Protocol [1](https://arxiv.org/html/2506.23836v1#alg1) is *zero-respecting* if it does not explore or assign non-zero values to any coordinate unless at least one of the available local vectors contains a non-zero value in that coordinate. The family of such algorithms we denote as $\mathcal{A}_{\textnormal{zr}}.$

This is the standard assumption (Carmon et al., 2020) that generalizes the family of methods working with the span of vectors (Nesterov, 2018) and holds for the majority of methods, including GD, Adam (Kingma & Ba, 2015), DORE (Liu et al., 2020), EF21-P (Gruntkowska et al., 2023), MARINA-P, and M3 (Gruntkowska et al., 2024).

###### Definition 2.3 .

### 2.2 Previous Lower Bound in the Heterogeneous Setting

Let us return back to our main question. In order to show that it is impossible to scale with $n$ in the *heterogeneous setting*, Gruntkowska et al. (2024) have proposed to use scaled versions of

$$ $\displaystyle\textstyle G_{j}(x):=n\times\sum\limits_{1\leq i\leq T\textnormal { and }(i-1)\bmod n=j-1}^{T}\left[\Psi(-x_{i-1})\Phi(-x_{i})-\Psi(x_{i-1})\Phi (x_{i})\right]$ $$

for all $j\in[n],$ worker $i$ has access only a scaled version of $G_{i}$ for all $i\in[n].$ The idea is that the first block from ([6](https://arxiv.org/html/2506.23836v1#S2.E6)) belongs to the first worker, the second block to the second worker, $\dots$, and the $(n+1)$^th block to the first worker again, and so on. Notice that $F_{T}(x)=\frac{1}{n}\sum_{i=1}^{n}G_{i}(x).$

Figure: Protocol 1

Notice one important property of this construction: only one worker at a time can discover the next coordinate. In other words, if the server sends a new iterate to all workers, only one worker, after computing the gradient, can make progress to the next coordinate.

The next step in (Gruntkowska et al., 2024), in the proof of the lower bound theorem, was to analyze Protocol [1](https://arxiv.org/html/2506.23836v1#alg1).
They consider(^4^44In general, they presented a more general setting where the server can zero out coordinates with any probability, capturing not only Rand$K$ with $K=1$ and $p=\nicefrac{{1}}{{d}},$ but also Rand$K$ with $K>1$ and other compressors.) Rand$K$ with $K=1.$
Then, since the compressor sends only one coordinate with probability
$p=\nicefrac{{1}}{{d}},$
the probability that the server sends the last non-zero coordinate to the worker responsible for the current block of ([6](https://arxiv.org/html/2506.23836v1#S2.E6)) that can progress to the new coordinate is also $p.$ Thus, the number of *consecutive* coordinates that the server has to send to the workers is at least $\sum_{j=1}^{T}\eta_{j},$ where $\eta_{j}$ is a geometric-like random variable with $\mathbb{P}\left(\eta_{j}=m\middle|\eta_{j-1},\dots,\eta_{1}\right)\leq p(1-p)^
{m-1}$ for all $m\geq 1.$ Using classical tools from statistical analysis, one can show that $\sum_{j=1}^{T}\eta_{j}\gtrsim\nicefrac{{T}}{{p}}\simeq d\nicefrac{{L\Delta}}{{
\varepsilon}}$ with high probability. Thus, under Assumption [1.4](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem4), the communication time complexity cannot be better than
$\textstyle\Omega\left({\color[rgb]{0.92578125,0.578125,0.0546875}\definecolor[
named]{pgfstrokecolor}{rgb}{0.92578125,0.578125,0.0546875}\tau_{\textnormal{s}
}d\nicefrac{{L\Delta}}{{\varepsilon}}}\right),$
which does not improve with $n.$

### 2.3 Failure of the previous construction in the homogeneous setting

However, in the *homogeneous* setting, if we want to reuse the idea, arguably the only option we have is to assign (scaled) $F_{T}$ to all workers to ensure that they all have the same function. But in this case, the arguments from Section [2.2](https://arxiv.org/html/2506.23836v1#S2.SS2) no longer apply, because all workers can simultaneously progress to the next coordinate, since they have access to all blocks of ([6](https://arxiv.org/html/2506.23836v1#S2.E6)).

Indeed, if the server sends i.i.d. Rand$K$ compressors with $K=1,$ then the number of consecutive coordinates that the server has to send before the workers receive the last non-zero coordinate is $\sum_{j=1}^{T}\min\limits_{i\in[n]}\eta_{ji},$ where $\mathbb{P}\left(\eta_{ji}=m\middle|\{\eta_{kj}\}_{k<i}\right)\leq p(1-p)^{m-1}$ for all $m,j\geq 1,i\in[n].$ The $\min\limits_{i\in[n]}$ operation appears because it is sufficient to wait for the first “luckiest” worker. Analyzing this sum, we can only show that

$$ $\displaystyle\textstyle\tau_{\textnormal{s}}\sum\limits_{j=1}^{T}\min\limits_{ i\in[n]}\eta_{ji}\gtrsim\tau_{\textnormal{s}}\frac{d}{n}\frac{L\Delta}{ \varepsilon},$ (8) $$

with high probability, which scales with $n$ due to $\min.$

There are two options: either $\Omega(\tau_{\textnormal{s}}\nicefrac{{dL\Delta}}{{n\varepsilon}})$ is tight and it is possible to find a method that matches it, or we need to find another way to improve the lower bound. To prove the latter, we arguably need a different fundamental construction from ([6](https://arxiv.org/html/2506.23836v1#S2.E6)), which we propose in the next section.

## 3 A New “Worst-Case” Function

In this section, we give a less technical description of our lower bound construction and the main theorem from Section [B](https://arxiv.org/html/2506.23836v1#A2).
Instead of ([6](https://arxiv.org/html/2506.23836v1#S2.E6)), we propose to use another “worst-case” function. For any $T,K\in\mathbb{N},$ and $e\geq a>1,$ we define the function $F_{T,K,a}\,:\,\mathbb{R}^{T}\to\mathbb{R}$ such that

$$ $\displaystyle\textstyle F_{T,K,a}(x)=-\sum\limits_{i=1}^{T}\Psi_{a}(x_{i-K}) \dots\Psi_{a}(x_{i-2})\Psi_{a}(x_{i-1})\Phi(x_{i})+\sum\limits_{i=1}^{T}\Gamma (x_{i}),$ (9) $$

$$ $\displaystyle\Psi_{a}(x)=\begin{cases}0,&x\leq 1/2,\\ \exp\left(\log a\cdot\left(1-\frac{1}{(2x-1)^{2}}\right)\right),&x>1/2,\end{ cases}\qquad\Phi(x)=\sqrt{e}\int_{-\infty}^{x}e^{-\frac{1}{2}t^{2}}dt,$ (10) $$

$$ $\displaystyle\Gamma(x)=\begin{cases}-xe^{1/x+1},&x<0,\\ 0,&x\geq 0,\end{cases}$ $$

and $x_{0}=\dots=x_{-K+1}\equiv 1.$ The main modification is that instead of the block $-\Psi(x_{i-1})\Phi(x_{i}),$ we use $-\Psi_{a}(x_{i-K})\dots\Psi_{a}(x_{i-2})\Psi_{a}(x_{i-1})\Phi(x_{i})$ (ignore $a$ for now). In the previous approach, it was sufficient for a worker to have $x_{i-1}\neq 0$ to discover the next $i$^th coordinate. However, in our new construction, the worker needs $x_{i-1}\neq 0,x_{i-2}\neq 0,\dots,x_{i-K+1}\neq 0$ for that. With this modification, it is not sufficient for the “luckiest” worker to get the non-zero $i-1$^th coordinate to discover the next coordinate: to progress to the $i$th coordinate, the worker should also have non-zero $i-2$^th, …, $i-K+1$^th coordinates.

Next, we remove the positive blocks $\Psi(x_{i-1})\Phi(x_{i}),$ which we believe was introduced to prevent the methods from ascending, exploring negative values of $x_{i},$ and finding a nearby stationary point “above.” Instead, we introduce $\Gamma(x_{i}),$ which serves the same purpose: if a method starts exploring negative values, this term prevents it from reaching a stationary point there. Let us define

$$ $\displaystyle\textnormal{prog}^{K}(x):=\max\{i\geq 0\,|\,x_{i}\neq 0,x_{i-1} \neq 0,\dots,x_{i-K+1}\neq 0\}.$ $$

Instead of Lemma [2.1](https://arxiv.org/html/2506.23836v1#S2.Thmtheorem1), we prove the following lemma:

###### Lemma 3.1 (Lemmas B.4 and B.5 ) .

The function $F_{T,K,a}$ satisfies:

- 1.
For all $x\in\mathbb{R}^{T},$ $\textnormal{prog}^{1}(\nabla F_{T,K,a}(x))\leq\max\{\textnormal{prog}^{K}(x)+1
,\textnormal{prog}^{1}(x)\}.$
- 2.
For all $x\in\mathbb{R}^{T},$ if $\textnormal{prog}^{K}(x)<T,$ then $\left\|\nabla F_{T,K,a}(x)\right\|>1.$

The function $F_{T,K,a}$ remains smooth. However, by multiplying with additional $\Psi$ terms, we alter its geometry and make it more chaotic: the difference $F_{T,K,a}(0)-\inf_{x\in\mathbb{R}^{T}}F_{T,K,a}(x),$ the smoothness constant, and the maximum $\ell_{\infty}$–norm may increase. To mitigate this, we introduce the parameter $a$ in ([10](https://arxiv.org/html/2506.23836v1#S3.E10)) that allows us to control these properties. Notice that if $a=e,$ then $\Psi_{a}(x)=\Psi(x)$ for all $x\in\mathbb{R}^{T},$ where $\Psi$ is defined in ([7](https://arxiv.org/html/2506.23836v1#S2.E7)). Instead of Lemma [2.2](https://arxiv.org/html/2506.23836v1#S2.Thmtheorem2), we prove

###### Lemma 3.2 (Lemmas B.6 , B.7 , and B.8 ) .

The function $F_{T}$ satisfies:

- 1.
$F_{T,K,a}(0)-\inf_{x\in\mathbb{R}^{T}}F_{T,K,a}(x)\leq\Delta^{0}(K,a)\cdot T,$ where $\Delta^{0}(K,a):=\sqrt{2\pi e}\cdot a^{K}.$
- 2.
The function $F_{T,K,a}$ is $\ell_{1}(K,a)$–smooth, where $\ell_{1}(K,a):=12\sqrt{2\pi}e^{5/2}\cdot\frac{K^{2}a^{K}}{\log a}.$
- 3.
For all $x\in\mathbb{R}^{T},$ $\left\|\nabla F_{T,K,a}(x)\right\|_{\infty}\leq\gamma_{\infty}(K,a),$ where $\gamma_{\infty}(K,a):=6\sqrt{2\pi}e^{3/2}\cdot\frac{Ka^{K}}{\sqrt{\log a}}.$

Figure: Figure 1: The functions $\Psi_{a}(x)$ and $\Gamma(x)$, along with their derivatives $\Phi^{\prime}_{a}(x)$ and $\Gamma^{\prime}(x)$. The plots of $\Phi(x)$ and $\Phi^{\prime}(x)$ are shown in (Carmon et al., 2020).
Refer to caption: x2.png

Taking $K=1$ and $a=e,$ up to constant factors, Lemmas [3.1](https://arxiv.org/html/2506.23836v1#S3.Thmtheorem1) and [3.2](https://arxiv.org/html/2506.23836v1#S3.Thmtheorem2) reduce to Lemmas [2.1](https://arxiv.org/html/2506.23836v1#S2.Thmtheorem1) and [2.2](https://arxiv.org/html/2506.23836v1#S2.Thmtheorem2). The larger the value of $K,$ the larger the bounds in Lemma [3.2](https://arxiv.org/html/2506.23836v1#S3.Thmtheorem2), and this growth can be exponential if $a=e.$ However, with a proper choice of $1<a\ll e,$ we can mitigate the increase caused by $K.$

###### Lemma 3.1 (Lemmas B.4 and B.5 ) .

###### Lemma 3.2 (Lemmas B.6 , B.7 , and B.8 ) .

## 4 Lower Bound with Server-to-Worker (S2W) Communication

We now present informal and formal versions of our main result:

###### Theorem 4.1 (Informal Formulation of Theorem 4.2 ) .

Let Assumptions [1.1](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem1), [1.2](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem2), [1.3](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem3), and [1.4](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem4) hold. It is infeasible to find an $\varepsilon$–stationary point faster than

$$ $\displaystyle\textstyle\tilde{\Omega}\left(\min\left\{{\color[rgb]{ 0.92578125,0.578125,0.0546875}\definecolor[named]{pgfstrokecolor}{rgb}{ 0.92578125,0.578125,0.0546875}\tau_{\textnormal{s}}d\frac{L\Delta}{\varepsilon }},h\frac{L\Delta}{\varepsilon}+{\color[rgb]{0.92578125,0.578125,0.0546875} \definecolor[named]{pgfstrokecolor}{rgb}{0.92578125,0.578125,0.0546875}h\frac{ \sigma^{2}L\Delta}{\varepsilon^{2}}}\right\}\right)$ (11) $$

seconds (up to logarithmic factors),
using unbiased compressors (Def. [1.5](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem5)) based on random sparsification,
for all $L,\Delta,\varepsilon,n,\sigma^{2},d,\tau_{\textnormal{s}},h>0$ such that $L\Delta\geq\tilde{\Theta}(\varepsilon)$ and dimension $d\geq\tilde{\Theta}(\nicefrac{{L\Delta}}{{\varepsilon}}).$

###### Theorem 4.2 .

Let $L,\Delta,\varepsilon,n,\sigma^{2},d,\tau_{\textnormal{s}},h>0$ be any numbers such that $\bar{c}_{1}\varepsilon\log^{4}(n+1)<L\Delta$ and dimension $d\geq\bar{c}_{3}\frac{L\Delta}{\log^{3}(n+1)\varepsilon}.$ Consider Protocol [1](https://arxiv.org/html/2506.23836v1#alg1).
For all $i\in[n]$ and $k\geq 0,$ compressor $\mathcal{C}^{k}_{i}$ selects and transmits $P^{k}_{i}$ *uniformly random coordinates without replacement, scaled by any constants(^5^55To potentially preserve unbiasedness. For instance, Rand$K$ scales by $\nicefrac{{d}}{{K}}.$)*,
where $P^{k}_{i}\in\{0,\dots,d\}$ may vary across each compressor (^6^66For instance, the compressors can be Rand$K$ (see Def. [A.1](https://arxiv.org/html/2506.23836v1#A1.Thmtheorem1)) with any $K\in[d]$, Perm$K$ (Szlendak et al., 2021), Identity compressor when $P^{k}_{i}=d.$).
Then, for any algorithm $A\in\mathcal{A}_{\textnormal{zr}}$ (Def. [2.3](https://arxiv.org/html/2506.23836v1#S2.Thmtheorem3)), there exists a function $f\,:\,\mathbb{R}^{d}\to\mathbb{R}$ such that $f$ is $L$-smooth, i.e., $\left\|\nabla f(x)-\nabla f(y)\right\|\leq L\left\|x-y\right\|$ for all $x,y\in\mathbb{R}^{d},$ and $f(0)-\inf_{x\in\mathbb{R}^{d}}f(x)\leq\Delta,$ exists a stochastic gradient oracles that satisfies Assumption [1.3](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem3), and
${\mathbb{E}}\left[\inf_{y\in S_{t}}\left\|\nabla f(y)\right\|^{2}\right]>\varepsilon$
for all

$$ $\displaystyle\textstyle t\leq\bar{c}_{2}\times\left(\frac{1}{\log^{3}(n+1)} \cdot\frac{L\Delta}{\varepsilon}\right)\min\left\{\frac{1}{\log(n+1)}\cdot\tau _{\textnormal{s}}d,\max\left\{h,\frac{1}{\log^{3}(n+1)}\cdot\frac{h\sigma^{2}} {\varepsilon}\right\}\right\},$ (12) $$

where
$S_{t}$ is the set of all possible points that can be constructed by $A$ up to time $t$ based on $I$ and $\{I_{i}\}.$
The quantities $\bar{c}_{1},$ $\bar{c}_{2},$ and $\bar{c}_{3}$ are universal constants.

The formulation of Theorem [4.2](https://arxiv.org/html/2506.23836v1#S4.Thmtheorem2) is standard in the literature. However, following Tyurin & Richtárik (2023b), we present the lower bound in terms of *time complexities* rather than *iteration complexities*. Then, following Huang et al. (2022); He et al. (2023); Tyurin et al. (2024), we consider a subfamily of unbiased compressors based from Definition [1.5](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem5) on random sparsification to prove the lower bound; this is standard practice for taking the “worst-case” compressors from the family (similarly to taking the “worst-case” functions (Carmon et al., 2020; Nesterov, 2018)). Moreover, due to the uncertainty principle (Safaryan et al., 2022), all unbiased compressors exhibit variance and communication cost comparable to those of the Rand$K$ sparsifier in the worst case (up to constant factors).

The main observation in Theorems [4.1](https://arxiv.org/html/2506.23836v1#S4.Thmtheorem1) and [4.2](https://arxiv.org/html/2506.23836v1#S4.Thmtheorem2) is that it is not possible to scale both $d$ and $\nicefrac{{\sigma^{2}}}{{\varepsilon}}$ by more than $\log^{4}(n+1)$ and $\log^{6}(n+1),$ respectively. Asymptotically, this scaling is significantly worse than the linear $n$ and square-root $\sqrt{n}$ scalings discussed in Section [1.1](https://arxiv.org/html/2506.23836v1#S1.SS1). For instance, if $n=10{,}000$ and $d$ is increased by a factor of $10$, we have to increase $n$ by a factor of $10^{3}$ (two factors more) to ensure that $\nicefrac{{\tau_{\textnormal{s}}d}}{{\log^{4}(n+1)}}$ does not change.

###### Theorem 4.1 (Informal Formulation of Theorem 4.2 ) .

###### Theorem 4.2 .

### 4.1 Proof Sketch

We illustrate the main idea behind the proof and how the new “worst-case” function helps to almost eliminate the scaling with $n$. Consider the first $K$ coordinates of $F_{T,K,a}$ (which is scaled in the proof to satisfy Assumptions [1.1](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem1) and [1.2](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem2)). Recall that, due to Lemma [3.1](https://arxiv.org/html/2506.23836v1#S3.Thmtheorem1), the only way to discover the $K+1$^th coordinate in any worker is to ensure that all of the first $K$ coordinates are non-zero.

Reduction to a statistical problem. There are only two options by which a worker may discover a new non-zero coordinate: through local stochastic computations or through communication from the server. In the first option, a worker computes a stochastic gradient, which takes $h$ seconds. However, due to the construction of stochastic gradients (Arjevani et al., 2022), even if the computation is completed, the worker will not make progress or discover a new non-zero coordinate, as it will be zeroed out with probability $p_{\sigma}=\Theta\left(\nicefrac{{\varepsilon\cdot\gamma_{\infty}^{2}(K,a)}}{{
\sigma^{2}}}\right).$ In the second option, due to the condition of Theorem [4.2](https://arxiv.org/html/2506.23836v1#S4.Thmtheorem2), a worker receives a stream of uniformly sampled coordinates $\nu_{1},\nu_{2},\dots$ (workers get different streams), and the worker can discover a new non-zero coordinate only if random variable $\nu_{i}\in[K]$, which satisfies
$\mathbb{P}\left(\nu_{i}\in[K]\middle|\nu_{1},\dots,\nu_{i-1}\right)\leq
\nicefrac{{K}}{{T-i+1}}\leq p_{K}:=\nicefrac{{2K}}{{T}}$ for all $i\leq\nicefrac{{T}}{{2}}.$

Next, we define two sets of random variables: (i) let $\eta_{1,i,k}$ denote the number of stochastic gradient computations until the first moment when a coordinate is not zeroed out in the stochastic gradient oracle (see ([26](https://arxiv.org/html/2506.23836v1#A3.E26))), after the moment when the $(k-1)$^th coordinate is no longer zeroed out in worker $i$; (ii) let $\mu_{1,i,k}$ be the number of received coordinates until the moment when the last received coordinate belongs to $[K]$, after the $(k-1)$^th time this has happened. In other words, $\eta_{1,i,1}$ is the number of stochastic gradient computations until the moment when the algorithm receives a “lucky” stochastic gradient where the last coordinate is not zeroed out. The random variable $\eta_{1,i,2}$ is the number of computations until it happens for the second time, and so on. Similarly, $\mu_{1,i,1}$ is the position of the first coordinate from the stream sent by the server to worker $i$ that belongs to $[K]$. The random variable $\mu_{1,i,2}$ refers to the second time this occurs, and so on.
By definition, the sequences $\{\eta_{1,i,k}\}$ and $\{\mu_{1,i,k}\}$ follow *approximately* geometric-like distributions with parameters $p_{\sigma}$ and $p_{K},$ respectively.

To discover all of the first $K$ coordinates, either the first or the second process must uncover at least $\nicefrac{{K}}{{2}}$ coordinates. If worker $i$ has discovered fewer than $\nicefrac{{K}}{{2}}$ coordinates through stochastic gradient computations, and fewer than $\nicefrac{{K}}{{2}}$ coordinates through receiving them from the server, then it will not be able to cover all $K$ coordinates. Thus, the algorithm should wait at least
$\min_{i\in[n]}\left\{\min\left\{h\sum_{k=1}^{\frac{K}{2}}\eta_{1,i,k},\tau_{
\textnormal{s}}\sum_{k=1}^{\frac{K}{2}}\mu_{1,i,k}\right\}\right\}$
seconds until the moment when it can potentially discover the $K+1$^th coordinate,
where the outer minimum $\min_{i\in[n]}$ appears because it is sufficient for the algorithm to wait for the first “luckiest” worker. Repeating the same arguments $B:=\left\lfloor\nicefrac{{T}}{{K}}\right\rfloor$ times, the algorithms requires at least

$$ $\displaystyle\textstyle t_{B}:=\sum\limits_{b=1}^{B}\min\limits_{i\in[n]}\left \{\min\left\{h\sum\limits_{k=1}^{K/2}\eta_{b,i,k},\tau_{\textnormal{s}}\sum \limits_{k=1}^{K/2}\mu_{b,i,k}\right\}\right\}$ (13) $$

seconds to discover the $T$^th coordinate and potentially find an $\varepsilon$–stationary point, where the sequences $\{\eta_{b,i,k}\}$ and $\{\mu_{b,i,k}\}$ follow *approximately* geometric-like distributions with $p_{\sigma}$ and $p_{K},$ respectively.

Analysis of the concentration. Hence, we have reduced the lower bound to the analysis of the sum $t_{B}.$ Recall ([8](https://arxiv.org/html/2506.23836v1#S2.E8)), where the lower bound improves with $n$ due to $\min_{i\in[n]}.$ In ([13](https://arxiv.org/html/2506.23836v1#S4.E13)), we also get $\min_{i\in[n]}.$ However, and this is the main reason for the new construction, there are two sums $\sum_{k=1}^{K/2},$ which allows us to mitigate the influence of the $\min_{i\in[n]}.$ In particular, we can show that
$\textstyle t_{B}~{}\gtrsim~{}\frac{BK}{n^{1/K}}\min\left\{\nicefrac{{h}}{{p_{
\sigma}}},\nicefrac{{\tau_{\textnormal{s}}}}{{p_{K}}}\right\}$
with high probability. Notice that the first fraction improves with $n^{\frac{1}{K}}$ instead of $n$ due to the sums; thus, the larger $K,$ the smaller the influence of $n.$

Putting it all together. However, we cannot take $K$ too large due to Lemma [3.2](https://arxiv.org/html/2506.23836v1#S3.Thmtheorem2). Substituting the choice of $T,p_{\sigma},$ and $p_{K}$ (defined in the proof of Theorem [4.2](https://arxiv.org/html/2506.23836v1#S4.Thmtheorem2) to ensure that Assumptions [1.1](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem1), [1.2](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem2), and [1.3](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem3) are satisfied and the scaled version of $F_{T,K,a}$ has the squared norm larger than $\varepsilon$ while the $T$^th is not discovered), we can show that

$$ $\displaystyle\textstyle t_{B}\gtrsim\frac{L\Delta}{n^{1/K}\cdot\Delta^{0}(K,a) \cdot\ell_{1}(K,a)\cdot\varepsilon}\min\left\{\max\left\{h,\frac{h\sigma^{2}}{ \varepsilon\cdot\gamma_{\infty}^{2}(K,a)}\right\},\frac{\tau_{\textnormal{s}}d }{K}\right\},$ $$

with high probability, where $\Delta^{0}(K,a),\ell_{1}(K,a),$ and $\gamma_{\infty}(K,a)$ are defined in Lemma [3.2](https://arxiv.org/html/2506.23836v1#S3.Thmtheorem2). The final step is to choose $K=\Theta\left(\log n\right)$ and $a=1+\nicefrac{{1}}{{K}}$ to obtain the result of Theorem [4.2](https://arxiv.org/html/2506.23836v1#S4.Thmtheorem2).

## 5 Lower Bound with Both W2S and S2W Communication

In the previous section, we provide the lower bound without taking into account the communication cost $\tau_{\textnormal{w}}.$ Combining Theorem [4.2](https://arxiv.org/html/2506.23836v1#S4.Thmtheorem2) with our new Theorem [D.1](https://arxiv.org/html/2506.23836v1#A4.Thmtheorem1), which extends the result by Tyurin et al. (2024) for our setup, we can obtain the complete lower bound ([5](https://arxiv.org/html/2506.23836v1#S1.E5)) from Theorem [1.6](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem6) with $\tau_{\textnormal{w}}>0$ and $\tau_{\textnormal{s}}>0.$ Notice that if $\tau_{\textnormal{s}}\simeq\tau_{\textnormal{w}},$ then the lower bound is
$\textstyle\tilde{\Omega}\left(\min\left\{h\left(\frac{\sigma^{2}}{n\varepsilon
}+1\right)\frac{L\Delta}{\varepsilon}+{\color[rgb]{
0.92578125,0.578125,0.0546875}\definecolor[named]{pgfstrokecolor}{rgb}{
0.92578125,0.578125,0.0546875}\tau_{\textnormal{s}}d\frac{L\Delta}{\varepsilon
}},h\frac{L\Delta}{\varepsilon}+{\color[rgb]{0.92578125,0.578125,0.0546875}
\definecolor[named]{pgfstrokecolor}{rgb}{0.92578125,0.578125,0.0546875}h\frac{
\sigma^{2}L\Delta}{\varepsilon^{2}}}\right\}\right).$
Up to logarithmic factors, under Assumptions [1.1](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem1), [1.2](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem2), [1.3](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem3), and [1.4](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem4), it is infeasible to improve both $d$ and $\nicefrac{{\sigma^{2}}}{{\varepsilon}}$ as $n$ increases.

### 5.1 Algorithms almost matching the lower bound

Due to the $\min,$ there are two regimes in which the lower bound ([5](https://arxiv.org/html/2506.23836v1#S1.E5)) operates. If the second term is smaller in ([5](https://arxiv.org/html/2506.23836v1#S1.E5)), then the lower bound is $\tilde{\Omega}\left(\frac{hL\Delta}{\varepsilon}+{\color[rgb]{
0.92578125,0.578125,0.0546875}\definecolor[named]{pgfstrokecolor}{rgb}{
0.92578125,0.578125,0.0546875}\frac{h\sigma^{2}L\Delta}{\varepsilon^{2}}}
\right),$ which is matched by the vanilla SGD method run locally (without any communication or cooperation). Otherwise, if the first term is smaller, then the lower bound is matched by [Batch QSGD](https://arxiv.org/html/2506.23836v1#S1.Ex2), which has the matching complexity ([4](https://arxiv.org/html/2506.23836v1#S1.E4)) (up to logarithmic factors). Moreover, in the latter case, if $\tau_{\textnormal{s}}\simeq\tau_{\textnormal{w}},$ the lower bound becomes $\tilde{\Omega}\left(\min\left\{h\left(\frac{\sigma^{2}}{n\varepsilon}+1\right)
\frac{L\Delta}{\varepsilon}+{\color[rgb]{0.92578125,0.578125,0.0546875}
\definecolor[named]{pgfstrokecolor}{rgb}{0.92578125,0.578125,0.0546875}\tau_{
\textnormal{s}}d\frac{L\Delta}{\varepsilon}}\right\}\right),$ which can be matched by [Batch Synchronized SGD](https://arxiv.org/html/2506.23836v1#S1.Ex1) with the complexity ([2](https://arxiv.org/html/2506.23836v1#S1.E2)); thus, if $\tau_{\textnormal{s}}\simeq\tau_{\textnormal{w}},$ then unbiased sparsified compression is not needed at all, as it cannot help due to the lower bound.

## 6 Conclusion

We prove nearly tight lower bounds for centralized distributed optimization under the computation and communication Assumption [1.4](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem4). We show that *even in the homogeneous scenario*, it is not possible to scale both $d$ and $\nicefrac{{\sigma^{2}}}{{\varepsilon}}$ by more than poly-logarithmic factors in $n.$
The lower bounds are tight only up to logarithmic factors. Thus, a possible challenging direction is to improve the powers of the logarithms, or even eliminate the logarithms entirely. The latter (if at all possible) may be very challenging and would likely require entirely different constructions and techniques. Another limitation is that the lower bounds are constructed using random sparsifiers. Due to the uncertainty principle (Safaryan et al., 2022), we conjecture that the bounds also hold for the entire family of unbiased compressors, but proving this would require more sophisticated constructions.

In practice, however, biased compressors, including Top$K$ and Rank$K$ (Alistarh et al., 2018; Vogels et al., 2019), exhibit significantly better compression properties than those predicted by worst-case analysis (Beznosikov et al., 2020). When used on the server side in combination with EF or EF21-P (Gruntkowska et al., 2023; Tyurin et al., 2024), they may help mitigate the pessimistic term ${\color[rgb]{0.92578125,0.578125,0.0546875}\definecolor[named]{pgfstrokecolor}
{rgb}{0.92578125,0.578125,0.0546875}\tau_{\textnormal{s}}d\nicefrac{{L\Delta}}
{{\varepsilon}}}.$

## References

- Alistarh et al. (2017)
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic.
QSGD: Communication-efficient SGD via gradient quantization and encoding.
In *Advances in Neural Information Processing Systems (NIPS)*, pp.  1709–1720, 2017.
- Alistarh et al. (2018)
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli.
The convergence of sparsified gradient methods.
*Advances in Neural Information Processing Systems*, 31, 2018.
- Arjevani et al. (2020)
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Ayush Sekhari, and Karthik Sridharan.
Second-order information in non-convex stochastic optimization: Power and limitations.
In *Conference on Learning Theory*, pp.  242–299. PMLR, 2020.
- Arjevani et al. (2022)
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth.
Lower bounds for non-convex stochastic optimization.
*Mathematical Programming*, pp.  1–50, 2022.
- Beznosikov et al. (2020)
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan.
On biased compression for distributed learning.
*arXiv preprint arXiv:2002.12410*, 2020.
- Brown et al. (2020)
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.
Language models are few-shot learners.
In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), *Advances in Neural Information Processing Systems*, volume 33, pp.  1877–1901. Curran Associates, Inc., 2020.
URL [https://proceedings.neurips.cc/paper/2020/file/1457c0d6bfcb4967418bfb8ac142f64a-Paper.pdf](https://proceedings.neurips.cc/paper/2020/file/1457c0d6bfcb4967418bfb8ac142f64a-Paper.pdf).
- Carmon et al. (2020)
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford.
Lower bounds for finding stationary points i.
*Mathematical Programming*, 184(1):71–120, 2020.
- Gorbunov et al. (2021)
Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, and Peter Richtárik.
MARINA: Faster non-convex distributed learning with compression.
In *38th International Conference on Machine Learning*, 2021.
- Gruntkowska et al. (2023)
Kaja Gruntkowska, Alexander Tyurin, and Peter Richtárik.
EF21-P and friends: Improved theoretical communication complexity for distributed optimization with bidirectional compression.
In *International Conference on Machine Learning*, pp.  11761–11807. PMLR, 2023.
- Gruntkowska et al. (2024)
Kaja Gruntkowska, Alexander Tyurin, and Peter Richtárik.
Improving the worst-case bidirectional communication complexity for nonconvex distributed optimization under function similarity.
In *Advances in Neural Information Processing Systems*, 2024.
- He et al. (2023)
Yutong He, Xinmeng Huang, and Kun Yuan.
Unbiased compression saves communication in distributed optimization: When and how much?
*Advances in Neural Information Processing Systems*, 36:47991–48020, 2023.
- Horváth et al. (2022)
Samuel Horváth, Chen-Yu Ho, Ľudovít Horváth, Atal Narayan Sahu, Marco Canini, and Peter Richtárik.
Natural compression for distributed deep learning.
In *Mathematical and Scientific Machine Learning*, pp.  129–141. PMLR, 2022.
- Huang et al. (2012)
Junxian Huang, Feng Qian, Alexandre Gerber, Z Morley Mao, Subhabrata Sen, and Oliver Spatscheck.
A close examination of performance and power characteristics of 4g lte networks.
In *Proceedings of the 10th international conference on Mobile systems, applications, and services*, pp.  225–238, 2012.
- Huang et al. (2022)
Xinmeng Huang, Yiming Chen, Wotao Yin, and Kun Yuan.
Lower bounds and nearly optimal algorithms in distributed learning with communication compression.
*Advances in Neural Information Processing Systems*, 2022.
- Kingma & Ba (2015)
Diederik P Kingma and Jimmy Ba.
Adam: A method for stochastic optimization.
*International Conference on Learning Representations*, 2015.
- Konečný et al. (2016)
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon.
Federated learning: Strategies for improving communication efficiency.
*arXiv preprint arXiv:1610.05492*, 2016.
- Lan (2020)
Guanghui Lan.
*First-order and stochastic optimization methods for machine learning*.
Springer, 2020.
- Li et al. (2021)
Haochuan Li, Yi Tian, Jingzhao Zhang, and Ali Jadbabaie.
Complexity lower bounds for nonconvex-strongly-concave min-max optimization.
*Advances in Neural Information Processing Systems*, 34:1792–1804, 2021.
- Li et al. (2020)
Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtárik.
Acceleration for compressed gradient descent in distributed and federated optimization.
In *International Conference on Machine Learning*, 2020.
- Liu et al. (2020)
Xiaorui Liu, Yao Li, Jiliang Tang, and Ming Yan.
A double residual compression algorithm for efficient distributed learning.
In *International Conference on Artificial Intelligence and Statistics*, pp.  133–143. PMLR, 2020.
- Lu & De Sa (2021)
Yucheng Lu and Christopher De Sa.
Optimal complexity in decentralized training.
In *International Conference on Machine Learning*, pp.  7111–7123. PMLR, 2021.
- McMahan et al. (2017)
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.
Communication-efficient learning of deep networks from decentralized data.
In *Artificial intelligence and statistics*, pp.  1273–1282. PMLR, 2017.
- Mishchenko et al. (2019)
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik.
Distributed learning with compressed gradient differences.
*arXiv preprint arXiv:1901.09269*, 2019.
- Murty & Kabadi (1985)
Katta G Murty and Santosh N Kabadi.
Some NP-complete problems in quadratic and nonlinear programming.
Technical report, 1985.
- Narayanan et al. (2021)
Arvind Narayanan, Xumiao Zhang, Ruiyang Zhu, Ahmad Hassan, Shuowei Jin, Xiao Zhu, Xiaoxuan Zhang, Denis Rybkin, Zhengxuan Yang, Zhuoqing Morley Mao, et al.
A variegated look at 5g in the wild: performance, power, and qoe implications.
In *Proceedings of the 2021 ACM SIGCOMM 2021 Conference*, pp.  610–625, 2021.
- Nemirovskij & Yudin (1983)
Arkadij Semenovič Nemirovskij and David Borisovich Yudin.
Problem complexity and method efficiency in optimization.
1983.
- Nesterov (2018)
Yurii Nesterov.
*Lectures on convex optimization*, volume 137.
Springer, 2018.
- Safaryan et al. (2022)
Mher Safaryan, Egor Shulgin, and Peter Richtárik.
Uncertainty principle for communication compression in distributed and federated learning and the search for an optimal compressor.
*Information and Inference: A Journal of the IMA*, 11(2):557–580, 2022.
- Seide et al. (2014)
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu.
1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs.
In *Fifteenth Annual Conference of the International Speech Communication Association*, 2014.
- Szlendak et al. (2021)
Rafał Szlendak, Alexander Tyurin, and Peter Richtárik.
Permutation compressors for provably faster distributed nonconvex optimization.
In *International Conference on Learning Representations*, 2021.
- Touvron et al. (2023)
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al.
Llama: Open and efficient foundation language models.
*arXiv preprint arXiv:2302.13971*, 2023.
- Tyurin & Richtárik (2023a)
Alexander Tyurin and Peter Richtárik.
DASHA: Distributed nonconvex optimization with communication compression, optimal oracle complexity, and no client synchronization.
*11th International Conference on Learning Representations (ICLR)*, 2023a.
- Tyurin & Richtárik (2023b)
Alexander Tyurin and Peter Richtárik.
Optimal time complexities of parallel stochastic optimization methods under a fixed computation model.
*Advances in Neural Information Processing Systems*, 2023b.
- Tyurin & Richtárik (2024)
Alexander Tyurin and Peter Richtárik.
On the optimal time complexities in decentralized stochastic asynchronous optimization.
*Advances in Neural Information Processing Systems*, 37, 2024.
- Tyurin et al. (2024)
Alexander Tyurin, Marta Pozzi, Ivan Ilin, and Peter Richtárik.
Shadowheart SGD: Distributed asynchronous SGD with optimal time complexity under arbitrary computation and communication heterogeneity.
*Advances in Neural Information Processing Systems*, 37, 2024.
- Vogels et al. (2019)
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi.
PowerSGD: Practical low-rank gradient compression for distributed optimization.
In *Neural Information Processing Systems*, 2019.
- Xu et al. (2021)
Hang Xu, Chen-Yu Ho, Ahmed M Abdelmoniem, Aritra Dutta, El Houcine Bergou, Konstantinos Karatsenidis, Marco Canini, and Panos Kalnis.
Grace: A compressed communication framework for distributed machine learning.
In *2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS)*, pp.  561–572. IEEE, 2021.
- Zhao et al. (2021)
Haoyu Zhao, Konstantin Burlachenko, Zhize Li, and Peter Richtárik.
Faster rates for compressed federated learning with client-variance reduction.
*arXiv preprint arXiv:2112.13097*, 2021.

## Appendix A Auxiliary Facts and Notations

###### Definition A.1 (Rand $K$ ) .

Assume that $S$ is a random subset of $[d]$ such that $|S|=K$ for some $K\in[d]$. A stochastic mapping $\mathcal{C}\,:\,\mathbb{R}^{d}\times\mathbb{S}_{\nu}\rightarrow\mathbb{R}^{d}$ is called Rand$K$ if

$$ $\displaystyle\mathcal{C}(x;S)=\frac{d}{K}\sum_{j\in S}x_{j}e_{j},$ $$

where $\{e_{i}\}_{i=1}^{d}$ denotes the standard unit basis. The set $S$ can be produced with a uniform sampling of $[d]$ without replacement.

###### Definition A.1 (Rand K 𝐾 K italic_K ) .

### A.1 Notations

$\mathbb{N}:=\{1,2,\dots\};$ $\left\|x\right\|$ is the output of the standard Euclidean norm for all $x\in\mathbb{R}^{d}$; $\left\langle x,y\right\rangle=\sum_{i=1}^{d}x_{i}y_{i}$ is the standard dot product; $\left\|A\right\|$ is the standard spectral/operator norm for all $A\in\mathbb{R}^{d\times d};$ $g=\mathcal{O}(f):$ exist $C>0$ such that $g(z)\leq C\times f(z)$ for all $z\in\mathcal{Z};$ $g=\Omega(f):$ exist $C>0$ such that $g(z)\geq C\times f(z)$ for all $z\in\mathcal{Z};$ $g=\Theta(f):$ $g=\mathcal{O}(f)$ and $g=\Omega(f);$ $g=\widetilde{\mathcal{O}}(f),g=\widetilde{\Omega}(f),g=\widetilde{\Theta}(f):$ the same as $g=\mathcal{O}(f),g=\Omega(f),g=\Theta(f),$ respectively, but up to logarithmic factors; $g\simeq h:$ $g$ and $h$ are equal up to universal positive constants; $g\gtrsim h:$ $g$ greater or equal to $h$ up to universal positive constants.

## Appendix B Lower Bound

### B.1 New Construction

For any $T,K\in\mathbb{N},$ and $e\geq a>1$ we define the function $F_{T,K,a}\,:\,\mathbb{R}^{T}\to\mathbb{R}$ such that

$$ $\displaystyle F_{T,K,a}(x)=-\sum_{i=1}^{T}\Psi_{a}(x_{i-K})\dots\Psi_{a}(x_{i- 2})\Psi_{a}(x_{i-1})\Phi(x_{i})+\sum_{i=1}^{T}\Gamma(x_{i}),$ (14) $$

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

$$ $\displaystyle\Psi_{a}(x)=\begin{cases}0,&x\leq 1/2,\\ \exp\left(\log a\cdot\left(1-\frac{1}{(2x-1)^{2}}\right)\right),&x>1/2,\end{ cases}\qquad\Phi(x)=\sqrt{e}\int_{-\infty}^{x}e^{-\frac{1}{2}t^{2}}dt,$ $$

and

$$ $\displaystyle\Gamma(x)=\begin{cases}-xe^{1/x+1},&x<0,\\ 0,&x\geq 0.\end{cases}$ $$

We assume that $x_{0}=\dots=x_{-K+1}\equiv 1.$ Importantly, throughout the lower bound analysis, we assume that $e\geq a>1$, even if this assumption is not explicitly stated in all theorems.

We additionally define

$$ $\displaystyle\textnormal{prog}^{K}(x):=\max\{i\geq 0\,|\,x_{i}\neq 0,x_{i-1} \neq 0,\dots,x_{i-K+1}\neq 0\}$ $\displaystyle(x_{0}=\dots=x_{-K+1}\equiv 1),$ $$

which extends $\textnormal{prog}(x)\equiv\textnormal{prog}^{1}(x):=\max\{i\geq~{}0\,|\,x_{i}
\neq 0\}\,\,(x_{0}\equiv 1).$

### B.2 Auxiliary Lemmas

In this section, we list useful properties of the functions $\Phi,$ $\Gamma,$ $\Psi_{a},$ and $F_{T,K,a}.$ We prove them in Section [B.3](https://arxiv.org/html/2506.23836v1#A2.SS3).

###### Lemma B.1 ( Carmon et al. ( 2020 ) ) .

Function $\Phi$ is twice differentiable and satisfies

$$ $\displaystyle 0\leq\Phi(x)\leq\sqrt{2\pi e},\quad 0\leq\Phi^{\prime}(x)\leq \sqrt{e},\textnormal{ and }\left|\Phi^{\prime\prime}(x)\right|\leq 27$ $$

for all $x\in\mathbb{R}.$ Moreover, $\Phi^{\prime}(x)>1$ for all $-1<x<1.$

###### Lemma B.2 .

Function $\Gamma$ is twice differentiable and satisfies

$$ $\displaystyle 0\leq\Gamma(x),\quad-e<\Gamma^{\prime}(x)\leq 0,\textnormal{ and }0\leq\Gamma^{\prime\prime}(x)\leq 27e^{-2}$ $$

for all $x\in\mathbb{R}.$ Moreover, $\Gamma^{\prime}(x)\leq-2$ for all $x\leq-1.$

###### Lemma B.3 .

Function $\Psi_{a}$ is twice differentiable and satisfies

$$ $\displaystyle 0\leq\Psi_{a}(x)<a,\quad 0\leq\Psi_{a}^{\prime}(x)\leq\frac{2e}{ \sqrt{\log a}},\textnormal{ and }\left|\Psi^{\prime\prime}_{a}(x)\right|\leq \frac{56e}{\log a}$ $$

for all $x\in\mathbb{R}$ and $1<a\leq e.$ Moreover, $\Psi_{a}(x)\geq 1$ for all $x\geq 1$ and $1<a\leq e.$

###### Lemma B.4 .

For all $x\in\mathbb{R}^{T},$ $\textnormal{prog}^{1}(\nabla F_{T,K,a}(x))\leq\max\{\textnormal{prog}^{K}(x)+1
,\textnormal{prog}^{1}(x)\}.$

###### Lemma B.5 .

For all $x\in\mathbb{R}^{T},$ if $\textnormal{prog}^{K}(x)<T,$ then $\left\|\nabla F_{T,K,a}(x)\right\|>1.$

###### Lemma B.6 .

Function $F_{T,K,a}$ satisfies

$$ $\displaystyle F_{T,K,a}(0)-\inf_{x\in\mathbb{R}^{T}}F_{T,K,a}(x)\leq\Delta^{0} (K,a)\cdot T,$ $$

where $\Delta^{0}(K,a):=\sqrt{2\pi e}\cdot a^{K}.$

###### Lemma B.7 .

For all $x\in\mathbb{R}^{T},$ $\left\|\nabla F_{T,K,a}(x)\right\|_{\infty}\leq\gamma_{\infty}(K,a),$ where $\gamma_{\infty}(K,a):=6\sqrt{2\pi}e^{3/2}\cdot\frac{Ka^{K}}{\sqrt{\log a}}.$

###### Lemma B.8 .

The function $F_{T,K,a}$ is $\ell_{1}(K,a)$–smooth, i.e., $\left\|\nabla^{2}F_{T,K,a}(x)\right\|\leq\ell_{1}(K,a)$
for all $x\in\mathbb{R}^{T},$ where $\ell_{1}(K,a):=12\sqrt{2\pi}e^{5/2}\cdot\frac{K^{2}a^{K}}{\log a}.$

###### Lemma B.1 ( Carmon et al. ( 2020 ) ) .

###### Lemma B.2 .

###### Lemma B.3 .

###### Lemma B.4 .

###### Lemma B.5 .

###### Lemma B.6 .

###### Lemma B.7 .

###### Lemma B.8 .

### B.3 Proof of lemmas

See [B.2](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem2)

###### Proof.

The first fact is due to $\lim\limits_{\Delta\to 0}\frac{\Gamma(\Delta)}{\Delta}=0,$ $\Gamma^{\prime}(0)=0,$ and $\lim\limits_{\Delta\to 0}\frac{\Gamma^{\prime}(\Delta)}{\Delta}=0.$ $\Gamma$ is clearly non-negative. Next, for all $x\leq 0,$

$$ $\displaystyle\Gamma^{\prime}(x)=-e^{1/x+1}+\frac{e^{1/x+1}}{x}$ $$

and

$$ $\displaystyle\Gamma^{\prime\prime}(x)=-\frac{e^{1/x+1}}{x^{3}}.$ $$

Thus, $\Gamma^{\prime}$ is strongly increasing for all $x\leq 0,$ and $\lim\limits_{x\to-\infty}\Gamma^{\prime}(x)=-e<\Gamma^{\prime}(x)\leq 0.$ Next, $\Gamma^{\prime\prime}(x)\geq 0$ for all $x\leq 0,$ and $\max\limits_{x\leq 0}\Gamma^{\prime\prime}(x)=27e^{-2}$ for all $x\leq 0.$
∎

See [B.3](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem3)

###### Proof.

The differentiability at $x=\frac{1}{2}$ follows from $\lim\limits_{\Delta\to 0}\frac{\Psi_{a}(\frac{1}{2}+\Delta)}{\Delta}=0$ for all $a>1.$ For all $x\leq\frac{1}{2},$ $\Psi^{\prime}_{a}(x)=0.$ For all $x>\frac{1}{2},$ we get

$$ $\displaystyle 0\leq\Psi^{\prime}_{a}(x)$ $\displaystyle=\frac{4\log a}{(2x-1)^{3}}\exp\left(\log a\left(1-\frac{1}{(2x-1 )^{2}}\right)\right)$ $\displaystyle=\frac{4a}{\sqrt{\log a}}\times\frac{\log^{3/2}a}{(2x-1)^{3}}\exp \left(-\frac{\log a}{(2x-1)^{2}}\right).$ $$

Taking $t=\frac{\log^{1/2}a}{(2x-1)}>0$ and using $t^{3}e^{-t^{2}}\leq\frac{1}{2},$ we get

$$ $\displaystyle\Psi^{\prime}_{a}(x)$ $\displaystyle\leq\frac{4a}{\sqrt{\log a}}\times\frac{1}{2}\leq\frac{2e}{\sqrt{ \log a}}$ $$

since $a\leq e.$

Clearly, $\Psi_{a}(x)\geq 0$ for all $x\in\mathbb{R},$ and $\Psi_{a}$ is non-decreasing. Moreover it is strongly monotonic for all $x>\frac{1}{2}.$ Thus $\Psi_{a}(x)<\lim\limits_{x\to\infty}\Psi_{a}(x)=a$ for all $x\in\mathbb{R}.$

The twice differentiability at $x=\frac{1}{2}$ follows from $\lim\limits_{\Delta\to 0}\frac{\Psi^{\prime}_{a}(\frac{1}{2}+\Delta)}{\Delta}=0$ for all $a>1.$ For all $x\leq\frac{1}{2},$ $\Psi^{\prime\prime}_{a}(x)=0.$ For all $x>\frac{1}{2},$ taking the second derivative and using simple algebra, we get

$$ $\displaystyle\left|\Psi^{\prime\prime}_{a}(x)\right|$ $\displaystyle=\left|-\frac{8\log a\times(3(2x-1)^{2}-2\log a)}{(2x-1)^{6}}\exp \left(\log a\left(1-\frac{1}{(2x-1)^{2}}\right)\right)\right|$ $\displaystyle=\left|\frac{8a\log a\times(3(2x-1)^{2}-2\log a)}{(2x-1)^{6}}\exp \left(-\frac{\log a}{(2x-1)^{2}}\right)\right|$ $\displaystyle\leq\left|\frac{24a\log a}{(2x-1)^{4}}\exp\left(-\frac{\log a}{(2 x-1)^{2}}\right)\right|+\left|\frac{16a\log^{2}a}{(2x-1)^{6}}\exp\left(-\frac{ \log a}{(2x-1)^{2}}\right)\right|$ $\displaystyle=\frac{24a}{\log a}\times\frac{\log^{2}a}{(2x-1)^{4}}\exp\left(- \frac{\log a}{(2x-1)^{2}}\right)+\frac{16a}{\log a}\times\frac{\log^{3}a}{(2x- 1)^{6}}\exp\left(-\frac{\log a}{(2x-1)^{2}}\right).$ $$

Taking $t=\frac{\log a}{(2x-1)^{2}}>0$ and using $t^{2}e^{-t}\leq 1$ and $t^{3}e^{-t}\leq 2,$

$$ $\displaystyle\left|\Psi^{\prime\prime}_{a}(x)\right|\leq\frac{24a}{\log a} \times 1+\frac{16a}{\log a}\times 2\leq\frac{56e}{\log a}$ $$

since $a\leq e.$
∎

See [B.4](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem4)

###### Proof.

Let $j=\textnormal{prog}^{K}(x)$ and $p=\textnormal{prog}^{1}(x),$ then

$$ $\displaystyle F_{T,K,a}(x)$ $\displaystyle=-\sum_{i=1}^{j+1}\Psi_{a}(x_{i-K})\dots\Psi_{a}(x_{i-2})\Psi_{a} (x_{i-1})\Phi(x_{i})$ $\displaystyle\quad-\sum_{i=j+2}^{T}\Psi_{a}(x_{i-K})\dots\Psi_{a}(x_{i-2})\Psi _{a}(x_{i-1})\Phi(x_{i})$ $\displaystyle\quad+\sum_{i=1}^{p}\Gamma(x_{i})+\sum_{i=p+1}^{T}\Gamma(x_{i}).$ $$

Since $j=\textnormal{prog}^{K}(x),$ for all $i\geq j+2,$ at least one of the values $x_{i-K},\dots,x_{i-2},x_{i-1}$ is zero. Noting that $\Psi_{a}(0)=\Psi_{a}^{\prime}(0)=0,$ the gradient of the second sum is zero. The first sum depends only on the first $j+1$ coordinates; thus, the gradient of the first sum is non-zero in at most the $(j+1)$^th coordinate.

Since $p=\textnormal{prog}^{1}(x),$ the gradient of the last sum is zero because $\Gamma^{\prime}(0)=0.$ And the gradient of the third sum has a non-zero value in at most the $p$^th coordinate.
∎

See [B.5](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem5)

###### Proof.

For all $j\in[T],$ the partial derivative of $F_{T,K,a}$ with respect to $x_{j}$ is

$$ $\displaystyle\frac{\partial F_{T,K,a}}{\partial x_{j}}(x)=\Big{[}$ $\displaystyle-\Psi_{a}(x_{j-K})\dots\Psi_{a}(x_{j-1})\Phi^{\prime}(x_{j})$ (15) $\displaystyle-\Psi_{a}(x_{j-K+1})\dots\Psi_{a}(x_{j-1})\Psi^{\prime}_{a}(x_{j} )\Phi(x_{j+1})$ $\displaystyle-\dots$ $\displaystyle-\Psi^{\prime}_{a}(x_{j})\Psi_{a}(x_{j+1})\dots\Psi_{a}(x_{\min\{ j+K,T\}-1})\Phi(x_{\min\{j+K,T\}})\Big{]}+\Gamma^{\prime}(x_{j}).$ $$

We now take the smallest $j\in[T]$ for which $x_{j}<1$ and ${x_{j-1}}\geq 1,\dots,{x_{j-K}}\geq 1.$

If such $j$ does not exists, then ${x_{1}}\geq 1$ due to ${x_{0}}=\dots={x_{-K+1}}\equiv 1.$ Then ${x_{2}}\geq 1,$ and so on. Meaning that ${x_{j}}\geq 1$ for all $j\in[T],$ which contradicts the assumption of the theorem that $\textnormal{prog}^{K}(x)<T.$

Fixing such $j,$ consider ([15](https://arxiv.org/html/2506.23836v1#A2.E15)).
There are two cases.
*Case 1: $x_{j}>-1.$* Note that $\Psi,\Phi,\Psi^{\prime},\Phi^{\prime}\geq 0$ are non-negative and $\Gamma^{\prime}\leq 0$ is non-positive. Thus

$$ $\displaystyle\frac{\partial F_{T,K,a}}{\partial x_{j}}(x)\leq-\Psi_{a}(x_{j-K} )\dots\Psi_{a}(x_{j-2})\Psi_{a}(x_{j-1})\Phi^{\prime}(x_{j}).$ $$

Since ${x_{j-1}}\geq 1,\dots,{x_{j-K}}\geq 1$ and $1>x_{j}>-1$ (see Lemmas [B.1](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem1) and [B.3](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem3)), we get

$$ $\displaystyle\frac{\partial F_{T,K,a}}{\partial x_{j}}(x)<-1.$ $$

*Case 2: $x_{j}\leq-1.$* Note that $\Psi,\Phi,\Psi^{\prime},\Phi^{\prime}\geq 0$ are non-negative. Thus

$$ $\displaystyle\frac{\partial F_{T,K,a}}{\partial x_{j}}(x)\leq\Gamma^{\prime}(x _{j}).$ $$

Since $x_{j}\leq-1$ (see Lemma [B.2](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem2)), we get

$$ $\displaystyle\frac{\partial F_{T,K,a}}{\partial x_{j}}(x)<-1.$ $$

Finally, we can conclude that

$$ $\displaystyle\left\|\nabla F_{T,K,a}(x)\right\|\geq\left|\frac{\partial F_{T,K ,a}}{\partial x_{j}}(x)\right|>1.$ $$

∎

See [B.6](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem6)

###### Proof.

Since $\Gamma(0)=0$ and $\Psi_{a},\Phi\geq 0,$ we get $F_{T,K,a}(0)\leq 0.$
Next, due to $\Gamma(x)\geq 0,$ $0\leq\Phi(x)\leq\sqrt{2\pi e}$ and $0\leq\Psi_{a}(x)\leq a$ for all $x\in\mathbb{R}^{d},$

$$ $\displaystyle F_{T,K,a}(x)\geq-\sum_{i=1}^{T}\Psi_{a}(x_{i-K})\dots\Psi_{a}(x_ {i-2})\Psi_{a}(x_{i-1})\Phi(x_{i})\geq-T\sqrt{2\pi e}\cdot a^{K}$ $$

for all $x\in\mathbb{R}^{T}.$
∎

See [B.7](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem7)

###### Proof.

Using ([15](https://arxiv.org/html/2506.23836v1#A2.E15)),

$$ $\displaystyle\left|\frac{\partial F_{T,K,a}}{\partial x_{j}}(x)\right|\leq\Big {|}$ $\displaystyle\Psi_{a}(x_{j-K})\dots\Psi_{a}(x_{j-1})\Phi^{\prime}(x_{j})$ (16) $\displaystyle+\Psi_{a}(x_{j-K+1})\dots\Psi_{a}(x_{j-1})\Psi^{\prime}_{a}(x_{j} )\Phi(x_{j+1})$ $\displaystyle+\dots$ $\displaystyle+\Psi^{\prime}_{a}(x_{j})\Psi_{a}(x_{j+1})\dots\Psi_{a}(x_{\min\{ j+K,T\}-1})\Phi(x_{\min\{j+K,T\}})\Big{|}+\left|\Gamma^{\prime}(x_{j})\right|.$ $$

Thus,

$$ $\displaystyle\left|\frac{\partial F_{T,K,a}}{\partial x_{j}}(x)\right|\leq a^{ K}\sqrt{e}+Ka^{K-1}\sqrt{2\pi e}\frac{2e}{\sqrt{\log a}}+e\leq 6\sqrt{2\pi}e^{ 3/2}\frac{Ka^{K}}{\sqrt{\log a}}$ (17) $$

due to Lemmas [B.1](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem1), [B.2](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem2), and [B.3](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem3).
∎

See [B.8](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem8)

###### Proof.

Taking the second partial derivative in ([15](https://arxiv.org/html/2506.23836v1#A2.E15)),

$$ $\displaystyle\frac{\partial^{2}F_{T,K,a}}{\partial x_{j}^{2}}(x)=\Big{[}$ $\displaystyle-\Psi_{a}(x_{j-K})\dots\Psi_{a}(x_{j-1})\Phi^{\prime\prime}(x_{j})$ (18) $\displaystyle-\Psi_{a}(x_{j-K+1})\dots\Psi_{a}(x_{j-1})\Psi^{\prime\prime}_{a} (x_{j})\Phi(x_{j+1})$ $\displaystyle-\dots$ $\displaystyle-\Psi^{\prime\prime}_{a}(x_{j})\Psi_{a}(x_{j+1})\dots\Psi_{a}(x_{ \min\{j+K,T\}-1})\Phi(x_{\min\{j+K,T\}})\Big{]}+\Gamma^{\prime\prime}(x_{j}).$ $$

Due to Lemmas [B.1](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem1), [B.2](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem2), and [B.3](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem3),

$$ $\displaystyle\left|\frac{\partial^{2}F_{T,K,a}}{\partial x_{j}^{2}}(x)\right| \leq\left[27a^{K}+K\times\frac{56\sqrt{2\pi}e^{3/2}a^{K-1}}{\log a}\right]+27e ^{-2}\leq 168\sqrt{2\pi}e^{3/2}\cdot\frac{Ka^{K}}{\log a}$ (19) $$

Clearly, for all $\min\{j+K,T\}<i\leq T,$

$$ $\displaystyle\frac{\partial^{2}F_{T,K,a}}{\partial x_{j}\partial x_{i}}(x)=0$ (20) $$

due to the construction of $F_{T,K,a}.$
Next, for all $j<i\leq\min\{j+K,T\},$

$$ $\displaystyle\frac{\partial^{2}F_{T,K,a}}{\partial x_{j}\partial x_{i}}(x)= \Big{[}$ $\displaystyle-\Psi_{a}(x_{i-K})\dots\Psi_{a}(x_{j-1})\Psi^{\prime}_{a}(x_{j}) \Psi_{a}(x_{j+1})\dots\Psi_{a}(x_{i-1})\Phi^{\prime}(x_{i})$ $\displaystyle-\Psi_{a}(x_{i-K+1})\dots\Psi_{a}(x_{j-1})\Psi^{\prime}_{a}(x_{j} )\Psi_{a}(x_{j+1})\dots\Psi_{a}(x_{i-1})\Psi^{\prime}_{a}(x_{i})\Phi(x_{i+1})$ $\displaystyle-\dots$ $\displaystyle-\Psi^{\prime}_{a}(x_{j})\Psi_{a}(x_{j+1})\dots\Psi_{a}(x_{i-1}) \Psi^{\prime}_{a}(x_{i})\Psi_{a}(x_{i+1})\dots\Psi_{a}(x_{\min\{j+K,T\}-1}) \Phi(x_{\min\{j+K,T\}})\Big{]},$ $$

and

$$ $\displaystyle\left|\frac{\partial^{2}F_{T,K,a}}{\partial x_{j}\partial x_{i}}( x)\right|\leq\frac{2e^{3/2}a^{K-1}}{\sqrt{\log a}}+(K-1)\times\frac{4\sqrt{2 \pi}e^{5/2}a^{K-2}}{\log a}\leq 4\sqrt{2\pi}e^{5/2}\cdot\frac{Ka^{K}}{\log a}$ (21) $$

for all $i\neq j\in[T]$ due to Lemmas [B.1](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem1) and [B.3](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem3) and $e\geq a>1$

Notice that $\nabla^{2}F_{T,K,a}$ is $(2K+1)$–diagonal Hessian. Repeating a textbook analysis for completeness and denoting temporary ${\bm{H}}:=\nabla^{2}F_{T,K,a}$, we will show that

$$ $\displaystyle\left\|\nabla^{2}F_{T,K,a}(x)\right\|\leq(2K+1)\max_{i,j\in[T]} \left|\frac{\partial^{2}F_{T,K,a}}{\partial x_{j}\partial x_{i}}(x)\right|.$ (22) $$

for all $x\in\mathbb{R}^{T}.$ Indeed, for all $x\in\mathbb{R}^{T}$ such that $\left\|x\right\|\leq 1,$

$$ $\displaystyle\left|x^{\top}{\bm{H}}x\right|=\left|\sum_{i=1}^{T}x_{i}\sum_{j=1 }^{T}x_{j}{\bm{H}}_{ij}\right|=\left|\sum_{i=1}^{T}x_{i}\sum_{j=\max\{i-K,1\}} ^{\min\{i+K,T\}}x_{j}{\bm{H}}_{ij}\right|\leq\max_{i,j\in[T]}\left|{\bm{H}}_{ ij}\right|\left(\sum_{i=1}^{T}\left|x_{i}\right|\sum_{j=\max\{i-K,1\}}^{\min\{ i+K,T\}}\left|x_{j}\right|\right),$ $$

where the second equality due to ${\bm{H}}$ is $(2K+1)$–diagonal. Using the Cauchy–Schwarz inequality,

$$ $\displaystyle\left|x^{\top}{\bm{H}}x\right|\leq\max_{i,j\in[T]}\left|{\bm{H}}_ {ij}\right|\sqrt{\sum_{i=1}^{T}x_{i}^{2}\sum_{i=1}^{T}\left(\sum_{j=\max\{i-K, 1\}}^{\min\{i+K,T\}}\left|x_{j}\right|\right)^{2}}\leq\max_{i,j\in[T]}\left|{ \bm{H}}_{ij}\right|\sqrt{\sum_{i=1}^{T}\left(\sum_{j=\max\{i-K,1\}}^{\min\{i+K ,T\}}\left|x_{j}\right|\right)^{2}}$ $$

since $\left\|x\right\|\leq 1.$ Next, using Jensen’s inequality and $\left\|x\right\|\leq 1,$

$$ $\displaystyle\left|x^{\top}{\bm{H}}x\right|$ $\displaystyle\leq\max_{i,j\in[T]}\left|{\bm{H}}_{ij}\right|\sqrt{(2K+1)\sum_{i =1}^{T}\sum_{j=\max\{i-K,1\}}^{\min\{i+K,T\}}x_{j}^{2}}\leq\max_{i,j\in[T]} \left|{\bm{H}}_{ij}\right|\sqrt{(2K+1)^{2}\sum_{i=1}^{T}x_{i}^{2}}$ $\displaystyle\leq(2K+1)\max_{i,j\in[T]}\left|{\bm{H}}_{ij}\right|.$ $$

We have proved ([22](https://arxiv.org/html/2506.23836v1#A2.E22)). It is left to combine ([22](https://arxiv.org/html/2506.23836v1#A2.E22)), ([21](https://arxiv.org/html/2506.23836v1#A2.E21)), and ([19](https://arxiv.org/html/2506.23836v1#A2.E19)).

∎

###### Proof.

###### Proof.

###### Proof.

###### Proof.

###### Proof.

###### Proof.

###### Proof.

## Appendix C Proof of Theorem 4.2

See [4.2](https://arxiv.org/html/2506.23836v1#S4.Thmtheorem2)

###### Proof.

(Step 1: Construction). Using the construction from Section [B.1](https://arxiv.org/html/2506.23836v1#A2.SS1), we define a scaled version of it.
Let us take any $\lambda>0,$ $d,T\in\mathbb{N},$ $d\geq T,$ and take the function $f\,:\,\mathbb{R}^{d}\to\mathbb{R}$ such that

$$ $f(x):=\frac{L\lambda^{2}}{\ell_{1}(K,a)}F_{T,K,a}\left(\frac{x_{[T]}}{\lambda} \right),$ $$

where $\ell_{1}(K,a)$ is defined in Lemma [B.8](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem8) and
$x_{[T]}\in\mathbb{R}^{T}$ is the vector with the first $T$ coordinates of $x\in\mathbb{R}^{d}.$ Notice that the last $d-T$ coordinates are artificial.

First, we have to show that $f$ is $L$-smooth and $f(0)-\inf_{x\in\mathbb{R}^{d}}f(x)\leq\Delta,$ Using Lemma [B.8](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem8),

$$ $\displaystyle\left\|\nabla f(x)-\nabla f(y)\right\|$ $\displaystyle=\frac{L\lambda}{\ell_{1}(K,a)}\left\|\nabla F_{T,K,a}\left(\frac {x_{[T]}}{\lambda}\right)-\nabla F_{T,K,a}\left(\frac{y_{[T]}}{\lambda}\right) \right\|\leq L\lambda\left\|\frac{x_{[T]}}{\lambda}-\frac{y_{[T]}}{\lambda}\right\|$ $\displaystyle=L\left\|x_{[T]}-y_{[T]}\right\|\leq L\left\|x-y\right\|\quad \forall x,y\in\mathbb{R}^{d}.$ $$

Let us take

$$ $T=\left\lfloor\frac{\Delta\cdot\ell_{1}(K,a)}{L\lambda^{2}\cdot\Delta^{0}(K,a) }\right\rfloor.$ $$

Due to Lemma [B.6](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem6),

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

where $\Delta^{0}(K,a)$ is defined in Lemma [B.6](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem6).
We also choose

$$ $\displaystyle\lambda=\frac{\sqrt{2\varepsilon}\ell_{1}(K,a)}{L}$ (23) $$

to ensure that

$$ $\displaystyle\left\|\nabla f(x)\right\|^{2}=\frac{L^{2}\lambda^{2}}{\ell_{1}^{ 2}(K,a)}\left\|\nabla F_{T,K,a}\left(\frac{x_{[T]}}{\lambda}\right)\right\|^{2 }=2\varepsilon\left\|\nabla F_{T,K,a}\left(\frac{x_{[T]}}{\lambda}\right) \right\|^{2}>2\varepsilon\cdot\mathbbm{1}\left[\textnormal{prog}^{K}(x_{[T]})< T\right],$ (24) $$

where the last inequality due to Lemma [B.5](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem5). Note that

$$ $\displaystyle T=\left\lfloor\frac{L\Delta}{2\Delta^{0}(K,a)\cdot\ell_{1}(K,a) \cdot\varepsilon}\right\rfloor.$ (25) $$

(Step 2: Stochastic Oracle).
We take the stochastic oracle construction form (Arjevani et al., 2022). For all $j\in[d],$

$$ $\displaystyle[\nabla f(x;\xi)]_{j}:=\nabla_{j}f(x)\left(1+\mathbbm{1}\left[j> \textnormal{prog}^{1}(x)\right]\left(\frac{\xi}{p_{\sigma}}-1\right)\right) \quad\forall x\in\mathbb{R}^{d},$ (26) $$

and $\mathcal{D}_{\xi}=\textnormal{Bernouilli}(p_{\sigma})$ for all $j\in[n],$ where $p_{\sigma}\in(0,1].$
We denote $[x]_{j}$ as the $j$^th index of a vector $x\in\mathbb{R}^{d}.$
It is left to show this mapping is unbiased and $\sigma^{2}$-variance-bounded. Indeed,

$$ ${\mathbb{E}}\left[[\nabla f(x,\xi)]_{i}\right]=\nabla_{i}f(x)\left(1+\mathbbm{ 1}\left[i>\textnormal{prog}^{1}(x)\right]\left(\frac{{\mathbb{E}}\left[\xi \right]}{p_{\sigma}}-1\right)\right)=\nabla_{i}f(x)$ $$

for all $i\in[d],$ and

$$ $\displaystyle{\mathbb{E}}\left[\left\|\nabla f(x;\xi)-\nabla f(x)\right\|^{2} \right]\leq\max_{j\in[d]}\left|\nabla_{j}f(x)\right|^{2}{\mathbb{E}}\left[ \left(\frac{\xi}{p_{\sigma}}-1\right)^{2}\right]$ $$

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

$$ $\displaystyle{\mathbb{E}}\left[\left\|\nabla f(x,\xi)-\nabla f(x)\right\|^{2}\right]$ $\displaystyle\leq\frac{\left\|\nabla f(x)\right\|_{\infty}^{2}(1-p_{\sigma})}{ p_{\sigma}}=\frac{L^{2}\lambda^{2}\left\|F_{T,K,a}\left(\frac{x_{[T]}}{\lambda }\right)\right\|_{\infty}^{2}(1-p_{\sigma})}{\ell^{2}_{1}(K,a)p_{\sigma}}$ $\displaystyle\leq\frac{L^{2}\lambda^{2}\gamma_{\infty}^{2}(K,a)(1-p_{\sigma})} {\ell^{2}_{1}(K,a)p_{\sigma}},$ $$

where we use Lemma [B.7](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem7) in the last inequality. Taking

$$ $\displaystyle p_{\sigma}=\min\left\{\frac{L^{2}\lambda^{2}\gamma_{\infty}^{2}( K,a)}{\sigma^{2}\ell_{1}^{2}(K,a)},1\right\}\overset{(\ref{eq:lambda})}{=}\min \left\{\frac{2\varepsilon\gamma_{\infty}^{2}(K,a)}{\sigma^{2}},1\right\},$ (27) $$

we ensure that ${\mathbb{E}}\left[\left\|\nabla f(x,\xi)-\nabla f(x)\right\|^{2}\right]\leq
\sigma^{2}.$

(Step 3: Reduction to the Analysis of Concentration).
At the beginning, due to Definition [2.3](https://arxiv.org/html/2506.23836v1#S2.Thmtheorem3), $s^{0}_{i}=0$ for all $i\in[n].$ Thus, if $k=0,$ all workers can receive zero vectors from the server. Thus, at the beginning, all workers can only calculate stochastic gradients at the point zero.

Let $t^{1,i}$ denote the earliest time at which all of the first $K$ coordinates become non-zero in the local information available to worker $i$. In other words, $t^{1,i}$ is the first time when worker $i$ has *discovered* all of the first $K$ coordinates. Consequently, prior to time

$$ $\displaystyle t_{1}:=\min_{i\in[n]}t_{1,i}$ (28) $$

neither the server nor any worker is able to discover (filled with non-zero values) the $(K+1)$^th and subsequent coordinates due to Lemma [B.4](https://arxiv.org/html/2506.23836v1#A2.Thmtheorem4).

There are two options by which a worker may discover a new non-zero coordinate: through local stochastic computations or through communication from the server.
Option 1: In the first option, a worker computes a stochastic gradient, which takes $h$ seconds. However, due to the construction of stochastic gradients, even if the computation is completed, the worker will not make progress or discover a new non-zero coordinate, as it will be zeroed out with probability $p_{\sigma}$.
Let $\eta_{1,i,1}$ be the number of stochastic gradients computations(^7^77It is possible that $\mathbb{P}\left(\eta_{1,i,1}=\infty\right)>0$ if, for instance, the algorithm decides to stop calculating stochastic gradients. And even $\mathbb{P}\left(\eta_{1,i,1}=\infty\right)=1$ if it does not calculate at all.) until the first moment when a coordinate is not zeroed out in ([26](https://arxiv.org/html/2506.23836v1#A3.E26)) in worker $i.$ Assume that $\xi_{1},\xi_{2},\dots$ is a stream of i.i.d. random Bernoulli variables from ([26](https://arxiv.org/html/2506.23836v1#A3.E26)) in worker $i$ (all workers have different streams), then

$$ $\displaystyle\mathbb{P}\left(\eta_{1,i,1}\leq t\right)$ $\displaystyle\leq\sum_{k=1}^{\left\lfloor t\right\rfloor}\mathbb{P}\left(\xi_{ k}=1,\xi_{k-1}=0,\dots,\xi_{1}=0\right)=\sum_{k=1}^{\left\lfloor t\right \rfloor}p_{\sigma}(1-p_{\sigma})^{j-1}\leq tp_{\sigma}.$ $$

for all $t\geq 0.$ Similarly, let $\eta_{1,i,k}$ denote the number of stochastic gradient computations until the first moment when a coordinate is not zeroed out in ([26](https://arxiv.org/html/2506.23836v1#A3.E26)), after the moment when the $(k-1)$^th coordinate is no longer zeroed out in worker $i.$ In other words, worker $i$ should calculate $\eta_{1,i,1}$ stochastic gradients to discover the first coordinate, calculate $\eta_{1,i,2}$ stochastic gradients to discover the second coordinate, and so on. Since the draws of $\xi$ in ([26](https://arxiv.org/html/2506.23836v1#A3.E26)) are i.i.d., we can conclude that

$$ $\displaystyle\mathbb{P}\left(\eta_{1,i,k}\leq t\middle|\eta_{1,i,k-1},\dots, \eta_{1,i,1}\right)\leq tp_{\sigma}$ $$

for all $k\geq 1$ and $t\geq 0.$
Option 2: In the second option, worker $i$ receives $P\in\{0,\dots,d\}$ random coordinates with the set of indices $\{\nu_{1,1},\dots,\nu_{1,P}\}$ *without replacement*, where it takes $\tau_{\textnormal{s}}$ seconds to receive one coordinate. Then, the worker receives $\bar{P}\in\{0,\dots,d\}$ random coordinates with the set of indices $\{\nu_{2,1},\dots,\nu_{2,\bar{P}}\}$ *without replacement*, and so on (all workers get different sets; we drop the indices of the workers in the notations).

Consequently, the worker receives a stream of coordinate indices
$(\nu_{1},\nu_{2},\dots)$
where we concatenated the sets of indices, preserving the exact order in which the server sampled them. Note that all workers have different streams, and we now focus on one worker.

Notice that

$$ $\displaystyle\mathbb{P}\left(\nu_{1}\in[K]\right)=\frac{K}{d}$ $$

since $\nu_{1}$ is uniformly random coordinate from the set $[d].$ Next,

$$ $\displaystyle\mathbb{P}\left(\nu_{2}\in[K]\middle|\nu_{1}\right)\leq\frac{K}{d -1},$ $$

because either $\nu_{1}\in[K]$, in which case the probability is $\frac{K-1}{d-1}$, or $\nu_{1}\not\in[K]$, in which case the probability is $\frac{K}{d-1}$. Using the same reasoning,

$$ $\displaystyle\mathbb{P}\left(\nu_{i}\in[K]\middle|\nu_{1},\dots,\nu_{i-1} \right)\leq\frac{K}{d-i+1}.$ $$

for all $i\leq d.$

Hence, the worker receives a stream of coordinates $\nu_{1},\nu_{2},\dots$ such that $\mathbb{P}\left(\nu_{i}\in[K]\middle|\nu_{1},\dots,\nu_{i-1}\right)\leq\frac{K
}{d-i+1}$ for all $i\leq d.$
Let $\mu_{1,i,1}$ be the number of received coordinates until the moment when the last received coordinate belongs to $[K]$ in worker $i.$
Similarly, let $\mu_{1,i,k}$ be the number of received coordinates until the moment when the last received coordinate belongs to $[K]$, after the $(k-1)$^th time this has happened in worker $i.$ In other words, worker $i$ should receive $\mu_{1,i,1}$ coordinates to obtain a coordinate that belongs to $[K]$. To get the next coordinate that belongs to $[K]$, the worker should receive $\mu_{1,i,2}$ coordinates, and so on.
Then,

$$ $\displaystyle\mathbb{P}\left(\mu_{1,i,1}=j\right)$ $\displaystyle=\mathbb{P}\left(\nu_{j}\in[K],\nu_{j-1}\not\in[K],\dots,\nu_{1} \not\in[K]\right)$ $\displaystyle=\mathbb{P}\left(\nu_{j}\in[K]\middle|\nu_{j-1}\not\in[K],\dots, \nu_{1}\not\in[K]\right)\mathbb{P}\left(\nu_{j-1}\not\in[K],\dots,\nu_{1}\not \in[K]\right)\leq\frac{K}{d-j+1}$ $$

for all $1\leq j\leq d,$ and

$$ $\displaystyle\mathbb{P}\left(\mu_{1,i,1}\leq t\right)=\sum_{j=1}^{\left\lfloor t \right\rfloor}\mathbb{P}\left(\mu_{1,i,1}=j\right)\leq\frac{Kt}{d-t+1}.$ (29) $$

for all $0\leq t\leq d.$
Similarly,

$$ $\displaystyle\mathbb{P}\left(\mu_{1,i,k}=j\middle|\mu_{1,i,k-1},\dots,\mu_{1,i ,1}\right)$ $\displaystyle=\mathbb{P}\left(\nu_{u+j}\in[K],\nu_{u+j-1}\not\in[K],\dots,\nu_ {u+1}\not\in[K]\middle|\nu_{u}\in[K],\dots,\nu_{1}\not\in[K]\right)$ $\displaystyle\leq\frac{K}{\max\{d-u,0\}-j+1},$ $$

where $u=\sum_{j=1}^{k-1}\mu_{1,i,j},$ for all $j\leq\max\{d-u,0\}.$ Thus,

$$ $\displaystyle\mathbb{P}\left(\mu_{1,i,k}\leq t\middle|\mu_{1,i,k-1},\dots,\mu_ {1,i,1}\right)\leq\frac{Kt}{\max\{d-\sum_{j=1}^{k-1}\mu_{1,i,j},0\}-t+1},$ $$

for all $0\leq t\leq\max\{d-\sum_{j=1}^{k-1}\mu_{1,i,j},0\}.$

Recall that the workers can discover new non-zero coordinates only through the stochastic processes discussed above. To discover all of the first $K$ coordinates, either the first or the second process must uncover at least $\frac{K}{2}$ coordinates(^8^88At the end of the proof, we take $K\textnormal{ mod }2=0.$). If worker $i$ has discovered fewer than $\frac{K}{2}$ coordinates through stochastic gradient computations and fewer than $\frac{K}{2}$ coordinates through receiving coordinates from the server, then it will not be able to cover all $K$ coordinates. Hence,

$$ $\displaystyle t_{1}\geq\min_{i\in[n]}\left\{\min\left\{h\sum_{k=1}^{\frac{K}{2 }}\eta_{1,i,k},\tau_{\textnormal{s}}\sum_{k=1}^{\frac{K}{2}}\mu_{1,i,k}\right \}\right\},$ $$

where $t_{1}$ is defined in ([28](https://arxiv.org/html/2506.23836v1#A3.E28)). This is because $h\sum_{k=1}^{\frac{K}{2}}\eta_{1,i,k}$ is the time required to obtain $\frac{K}{2}$ “lucky” stochastic gradients, those for which the coordinates are not zeroed out, and $\tau_{\textnormal{s}}\sum_{k=1}^{\frac{K}{2}}\mu_{1,i,k}$ is the time required to receive $\frac{K}{2}$ “lucky” coordinates that belong to $[K]$.

Once the workers have discovered the first $K$ coordinates, the discovery process repeats for the set $\{K+1,\dots,2K\}$, which similarly requires at least

$$ $\displaystyle\min_{i\in[n]}\left\{\min\left\{h\sum_{k=1}^{\frac{K}{2}}\eta_{2, i,k},\tau_{\textnormal{s}}\sum_{k=1}^{\frac{K}{2}}\mu_{2,i,k}\right\}\right\}$ $$

seconds, where $\{\eta_{b,i,k}\}$ and $\{\mu_{b,i,k}\}$ are random variables such that

$$ $\displaystyle\mathbb{P}\left(\eta_{b,i,k}\leq t\middle|\eta_{b,i,k-1},\dots, \eta_{b,i,1},\mathcal{G}_{b-1}\right)\leq tp_{\sigma}$ (30) $$

for all $b\geq 1,k\geq 1,$ $i\in[n],t\geq 0,$ and

$$ $\displaystyle\mathbb{P}\left(\mu_{b,i,k}\leq t\middle|\mu_{b,i,k-1},\dots,\mu_ {b,i,1},\mathcal{G}_{b-1}\right)\leq\frac{Kt}{\max\{d-\sum_{j=1}^{k-1}\mu_{b,i ,j},0\}-t+1}$ (31) $$

for all $b\geq 1,k\geq 1,$ $i\in[n],$ and $t\leq\max\{d-\sum_{j=1}^{k-1}\mu_{b,i,j},0\},$ where $\mathcal{G}_{b-1}$ is the sigma-algebra generated by $\{\eta_{b^{\prime},i,k}\}_{i\in[n],k\in[\frac{K}{2}],b^{\prime}<b}$ and $\{\mu_{b^{\prime},i,k}\}_{i\in[n],k\in[\frac{K}{2}],b^{\prime}<b}$ and $u=\sum_{j=1}^{k-1}\mu_{b,i,j}.$

More formally, $\eta_{2,i,k}$ can be defined as the number of stochastic gradient computations until the first moment when a coordinate is not zeroed out in ([26](https://arxiv.org/html/2506.23836v1#A3.E26)), after the moment when the $(k-1)$^th coordinate is no longer zeroed out, when $\textnormal{prog}^{K}$ of the input points to the stochastic gradients is $\geq K,$ and $\mu_{2,i,k}$ be the number of received coordinates until the moment when the last received coordinate belongs to $\{K+1,\dots,2K\}$, after the $(k-1)$^th time this has happened, when $\textnormal{prog}^{1}$ of the input points to the compressor is $\geq K+1,$ and so on.

We define

$$ $\displaystyle p_{K}:=\frac{2K}{d}.$ (32) $$

Finally, to discover the $T$^th coordinates it takes at least

$$ $\displaystyle\sum_{b=1}^{B}\min_{i\in[n]}\left\{\min\left\{h\sum_{k=1}^{\frac{ K}{2}}\eta_{b,i,k},\tau_{\textnormal{s}}\sum_{k=1}^{\frac{K}{2}}\mu_{b,i,k} \right\}\right\}$ $$

seconds, where $B=\left\lfloor\frac{T}{K}\right\rfloor.$ It it left to use the following lemma.

###### Lemma C.1 .

Let $\{\eta_{b,i,j}\}_{i,j,b\geq 0}$ and $\{\mu_{b,i,j}\}_{i,j,b\geq 0}$ be random variables such that

$$ $\displaystyle\mathbb{P}\left(\eta_{b,i,k}\leq t\middle|\eta_{b,i,k-1},\dots, \eta_{b,i,1},\mathcal{G}_{b-1}\right)\leq tp_{\sigma}$ (33) $$

for all $b\geq 1,k\geq 1,$ $i\in[n],t\geq 0,$ and

$$ $\displaystyle\mathbb{P}\left(\mu_{b,i,k}\leq t\middle|\mu_{b,i,k-1},\dots,\mu_ {b,i,1},\mathcal{G}_{b-1}\right)\leq\frac{Kt}{\max\{d-\sum_{j=1}^{k-1}\mu_{b,i ,j},0\}-t+1},$ (34) $$

for all $b\geq 1,k\geq 1,$ $i\in[n],$ $0\leq t\leq\max\{d-\sum_{j=1}^{k-1}\mu_{b,i,j},0\},$ and $1\leq K\leq d,$ where $\mathcal{G}_{b-1}$ is the sigma-algebra generated by $\{\eta_{b^{\prime},i,k}\}_{i\in[n],k\in[\frac{K}{2}],b^{\prime}<b}$ and $\{\mu_{b^{\prime},i,k}\}_{i\in[n],k\in[\frac{K}{2}],b^{\prime}<b}.$ Then

$$ $\displaystyle\mathbb{P}\left(\sum_{b=1}^{B}\min_{i\in[n]}\left\{\min\left\{h \sum_{k=1}^{\frac{K}{2}}\eta_{b,i,k},\tau_{\textnormal{s}}\sum_{k=1}^{\frac{K} {2}}\mu_{b,i,k}\right\}\right\}\leq\bar{t}\right)\leq\delta$ $$

with

$$ $\displaystyle\bar{t}:=\frac{BK+\log\delta}{e^{4}(2n)^{2/K}(4+\frac{2}{K}\log(2 n))}\min\left\{\frac{h}{p_{\sigma}},\frac{\tau_{\textnormal{s}}}{p_{K}}\right\},$ (35) $$

where

$$ $\displaystyle p_{K}:=\frac{2K}{d}.$ $$

(Step 4: Endgame).
Thus, with probability at least $1-\delta$, any zero-respecting algorithm requires at least $\bar{t}$ seconds to discover the $T$^th coordinate. Since $\textnormal{prog}^{K}(x)\leq\textnormal{prog}^{1}(x)$ for all $x\in\mathbb{R}^{T}$, and due to ([24](https://arxiv.org/html/2506.23836v1#A3.E24)),

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

where $S_{t}$ is the set of all possible candidate points to be an $\varepsilon$–stationary point up to time $t,$ which can be computed by $A.$ Taking $\delta=\frac{1}{2},$

$$ $\displaystyle{\mathbb{E}}\left[\inf_{y\in S_{t}}\left\|\nabla f(y)\right\|^{2} \right]>2\varepsilon{\mathbb{E}}\left[\inf_{y\in S_{t}}\mathbbm{1}\left[ \textnormal{prog}^{1}(y_{[T]})<T\right]\right]\geq\varepsilon,$ $$

for $t=\frac{1}{2}\bar{t}$ because $\textnormal{prog}^{1}(y_{[T]})<T$ for all $y\in S_{t}$ with probability at least $\frac{1}{2}.$

It is left to choose $K$ and $a,$ and substitute all quantities to $\bar{t}.$ Using $B=\left\lfloor\frac{T}{K}\right\rfloor,$

$$ $\displaystyle\bar{t}=\frac{\left\lfloor\frac{T}{K}\right\rfloor K-\log 8}{e^{4 }(2n)^{2/K}(4+\frac{2}{K}\log(2n))}\min\left\{\frac{h}{p_{\sigma}},\frac{\tau_ {\textnormal{s}}}{p_{K}}\right\}$ $\displaystyle\geq\frac{T-K-\log 8}{e^{4}(2n)^{2/K}(4+\frac{2}{K}\log(2n))}\min \left\{\frac{h}{p_{\sigma}},\frac{\tau_{\textnormal{s}}}{p_{K}}\right\}.$ $$

Due to ([25](https://arxiv.org/html/2506.23836v1#A3.E25)), ([27](https://arxiv.org/html/2506.23836v1#A3.E27)), and ([32](https://arxiv.org/html/2506.23836v1#A3.E32)),

$$ $\displaystyle\bar{t}\geq\frac{\left\lfloor\frac{L\Delta}{2\Delta^{0}(K,a)\cdot \ell_{1}(K,a)\cdot\varepsilon}\right\rfloor-K-\log 8}{e^{4}(2n)^{2/K}(4+\frac{ 2}{K}\log(2n))}\min\left\{\max\left\{h,\frac{h\sigma^{2}}{2\varepsilon\gamma_{ \infty}^{2}(K,a)}\right\},\frac{\tau_{\textnormal{s}}d}{2K}\right\}.$ $$

Using the definitions of $\Delta^{0}(K,a),$ $\gamma_{\infty}(K,a),$ and $\ell_{1}(K,a),$

$$ $\displaystyle\bar{t}$ $\displaystyle\geq\left(e^{4}(2n)^{2/K}\left(4+\frac{2}{K}\log(2n)\right)\right )^{-1}\left(\left\lfloor\frac{L\Delta\log a}{48\pi e^{3}K^{2}a^{2K}\varepsilon }\right\rfloor-K-\log 8\right)\min\left\{\max\left\{h,\frac{h\sigma^{2}\log a} {144\pi e^{3}K^{2}a^{2K}\varepsilon}\right\},\frac{\tau_{\textnormal{s}}d}{2K} \right\}.$ $$

We can take any $a$ from the interval $(1,e].$ We choose $a=1+\frac{1}{K},$ then $\log a=\log\left(1+\frac{1}{K}\right)\geq\frac{1}{2K}$ for all $K\geq 1,$ $a^{2K}\leq e^{2}$ for all $K\geq 1,$ and

$$ $\displaystyle\bar{t}$ $\displaystyle\geq\left(e^{4}(2n)^{2/K}\left(4+\frac{2}{K}\log(2n)\right)\right )^{-1}\left(\left\lfloor\frac{L\Delta}{96\pi e^{5}K^{3}\varepsilon}\right \rfloor-K-\log 8\right)\min\left\{\max\left\{h,\frac{h\sigma^{2}}{288\pi e^{5} K^{3}\varepsilon}\right\},\frac{\tau_{\textnormal{s}}d}{2K}\right\}.$ $$

Taking $K=2\left\lceil 2\log(2n)\right\rceil,$ $(2n)^{2/K}\leq e,$ $K\leq 16\log(n+1)$ and

$$ $\displaystyle\bar{t}$ $\displaystyle\geq\frac{1}{5e^{5}}\left(\left\lfloor\frac{L\Delta}{96\cdot 8^{4 }\pi e^{5}\log^{3}(n+1)\varepsilon}\right\rfloor-32\log(n+1)\right)\min\left\{ \max\left\{h,\frac{h\sigma^{2}}{288\cdot 8^{4}\pi e^{5}\log^{3}(n+1) \varepsilon}\right\},\frac{\tau_{\textnormal{s}}d}{32\log(n+1)}\right\}$ $\displaystyle\geq\frac{1}{5e^{5}}\left(\frac{L\Delta}{96\cdot 8^{4}\pi e^{5} \log^{3}(n+1)\varepsilon}-36\log(n+1)\right)\min\left\{\max\left\{h,\frac{h \sigma^{2}}{288\cdot 8^{4}\pi e^{5}\log^{3}(n+1)\varepsilon}\right\},\frac{ \tau_{\textnormal{s}}d}{32\log(n+1)}\right\}.$ $$

We assume $\frac{L\Delta}{\varepsilon}\geq\bar{c}_{1}\log^{4}(n+1)$ for a universal constant $\bar{c}_{1}.$ Taking $\bar{c}_{1}$ large enough, one can see that

$$ $\displaystyle\bar{t}$ $\displaystyle\geq\frac{1}{5e^{5}}\left(\frac{L\Delta}{2\cdot 96\cdot 8^{4}\pi e ^{5}\log^{3}(n+1)\varepsilon}\right)\min\left\{\max\left\{h,\frac{h\sigma^{2}} {288\cdot 8^{4}\pi e^{5}\log^{3}(n+1)\varepsilon}\right\},\frac{\tau_{ \textnormal{s}}d}{32\log(n+1)}\right\}.$ $$

For a small enough universal $\bar{c}_{2},$ we get the inequality

$$ $\displaystyle\bar{t}$ $\displaystyle\geq\bar{c}_{2}\times\left(\frac{L\Delta}{\log^{3}(n+1) \varepsilon}\right)\min\left\{\max\left\{h,\frac{h\sigma^{2}}{\log^{3}(n+1) \varepsilon}\right\},\frac{\tau_{\textnormal{s}}d}{\log(n+1)}\right\},$ $$

which finishes the proof. Notice that we can take

$$ $\displaystyle d\geq T=\left\lfloor\frac{L\Delta\log a}{48\pi e^{3}K^{2}a^{2K} \varepsilon}\right\rfloor=\Theta\left(\frac{L\Delta}{\log^{3}(n+1)\varepsilon} \right).$ $$

∎

###### Proof.

###### Lemma C.1 .

### C.1 Main Concentration Lemma

See [C.1](https://arxiv.org/html/2506.23836v1#A3.Thmtheorem1)

###### Proof.

Let us temporarily define $\beta_{b,i}:=\min\left\{h\sum_{k=1}^{\frac{K}{2}}\eta_{b,i,k},\tau_{
\textnormal{s}}\sum_{k=1}^{\frac{K}{2}}\mu_{b,i,k}\right\}.$ Using Chernoff’s method, we get

$$ $\displaystyle\mathbb{P}\left(\sum_{b=1}^{B}\min_{i\in[n]}\beta_{b,i}\leq\bar{t }\right)=\mathbb{P}\left(\exp\left(-\sum_{b=1}^{B}\lambda\min_{i\in[n]}\beta_{ b,i}\right)\geq\exp\left(-\lambda\bar{t}\right)\right)$ (36) $\displaystyle\leq\exp\left(\lambda\bar{t}\right){\mathbb{E}}\left[\exp\left(- \sum_{b=1}^{B}\lambda\min_{i\in[n]}\beta_{b,i}\right)\right]$ $\displaystyle=\exp\left(\lambda\bar{t}\right){\mathbb{E}}\left[{\mathbb{E}} \left[\left.\exp\left(-\lambda\min_{i\in[n]}\beta_{B,i}\right)\right|\mathcal{ G}_{B-1}\right]\exp\left(-\sum_{b=1}^{B-1}\lambda\min_{i\in[n]}\beta_{b,i} \right)\right]$ $$

for all $\lambda>0$ since $\beta_{1,i},\dots,\beta_{B-1,i}$ are $\mathcal{G}_{B-1}$–measurable. Consider the inner expectation separately:

$$ $\displaystyle{\mathbb{E}}\left[\left.\exp\left(-\lambda\min_{i\in[n]}\beta_{B, i}\right)\right|\mathcal{G}_{B-1}\right]={\mathbb{E}}\left[\left.\max_{i\in[n] }\exp\left(-\lambda\beta_{B,i}\right)\right|\mathcal{G}_{B-1}\right]\leq\sum_{ i=1}^{n}{\mathbb{E}}\left[\left.\exp\left(-\lambda\beta_{B,i}\right)\right| \mathcal{G}_{B-1}\right],$ $$

where we bound $\max$ by $\sum.$ Using the temporal definitions of $\{\beta_{B,i}\},$

$$ $\displaystyle{\mathbb{E}}\left[\left.\exp\left(-\lambda\min_{i\in[n]}\beta_{B, i}\right)\right|\mathcal{G}_{B-1}\right]$ (37) $\displaystyle\leq\sum_{i=1}^{n}{\mathbb{E}}\left[\left.\exp\left(-\lambda\min \left\{h\sum_{k=1}^{\frac{K}{2}}\eta_{B,i,k},\tau_{\textnormal{s}}\sum_{k=1}^{ \frac{K}{2}}\mu_{B,i,k}\right\}\right)\right|\mathcal{G}_{B-1}\right]$ $\displaystyle=\sum_{i=1}^{n}{\mathbb{E}}\left[\left.\max\left\{\exp\left(- \lambda h\sum_{k=1}^{\frac{K}{2}}\eta_{B,i,k}\right),\exp\left(-\lambda\tau_{ \textnormal{s}}\sum_{k=1}^{\frac{K}{2}}\mu_{B,i,k}\right)\right\}\right| \mathcal{G}_{B-1}\right]$ $\displaystyle\leq\underbrace{\sum_{i=1}^{n}{\mathbb{E}}\left[\left.\exp\left(- \lambda h\sum_{k=1}^{\frac{K}{2}}\eta_{B,i,k}\right)\right|\mathcal{G}_{B-1} \right]}_{I_{1}:=}+\underbrace{\sum_{i=1}^{n}{\mathbb{E}}\left[\left.\exp\left (-\lambda\tau_{\textnormal{s}}\sum_{k=1}^{\frac{K}{2}}\mu_{B,i,k}\right)\right |\mathcal{G}_{B-1}\right]}_{I_{2}^{\frac{K}{2}}:=}.$ $$

Using the tower property,

$$ $\displaystyle I_{1}=\sum_{i=1}^{n}{\mathbb{E}}\left[\left.\underbrace{{\mathbb {E}}\left[\left.\exp\left(-\lambda h\eta_{B,i,\frac{K}{2}}\right)\right|\eta_{ B,i,\frac{K}{2}-1},\dots,\eta_{B,i,1},\mathcal{G}_{B-1}\right]}_{J_{1}:=}\exp \left(-\lambda h\sum_{k=1}^{\frac{K}{2}-1}\eta_{B,i,k}\right)\right|\mathcal{G }_{B-1}\right].$ (38) $$

Next,

$$ $\displaystyle J_{1}$ $\displaystyle:={\mathbb{E}}\left[\left.\exp\left(-\lambda h\eta_{B,i,\frac{K}{ 2}}\right)\right|\eta_{B,i,\frac{K}{2}-1},\dots,\eta_{B,i,1},\mathcal{G}_{B-1}\right]$ $\displaystyle\leq\exp\left(-\lambda t\right)\mathbb{P}\left(h\eta_{B,i,\frac{K }{2}}>t\middle|\eta_{B,i,\frac{K}{2}-1},\dots,\eta_{B,i,1},\mathcal{G}_{B-1}\right)$ $\displaystyle\quad+\mathbb{P}\left(h\eta_{B,i,\frac{K}{2}}\leq t\middle|\eta_{ B,i,\frac{K}{2}-1},\dots,\eta_{B,i,1},\mathcal{G}_{B-1}\right)$ $\displaystyle=\exp\left(-\lambda t\right)+(1-\exp\left(-\lambda ht\right)) \mathbb{P}\left(h\eta_{B,i,\frac{K}{2}}\leq t\middle|\eta_{B,i,\frac{K}{2}-1}, \dots,\eta_{B,i,1},\mathcal{G}_{B-1}\right)$ $\displaystyle\leq\exp\left(-\lambda t\right)+\mathbb{P}\left(h\eta_{B,i,\frac{ K}{2}}\leq t\middle|\eta_{B,i,\frac{K}{2}-1},\dots,\eta_{B,i,1},\mathcal{G}_{B -1}\right)$ $\displaystyle=\exp\left(-\lambda t\right)+\mathbb{P}\left(\eta_{B,i,\frac{K}{2 }}\leq\frac{t}{h}\middle|\eta_{B,i,\frac{K}{2}-1},\dots,\eta_{B,i,1},\mathcal{ G}_{B-1}\right)$ $$

for all $t\geq 0.$ Due to ([33](https://arxiv.org/html/2506.23836v1#A3.E33)),

$$ $\displaystyle J_{1}\leq\exp\left(-\lambda t\right)+\frac{tp_{\sigma}}{h}.$ $$

Substituting to ([38](https://arxiv.org/html/2506.23836v1#A3.E38)),

$$ $\displaystyle I_{1}\leq\sum_{i=1}^{n}\left(\exp\left(-\lambda t\right)+\frac{ tp_{\sigma}}{h}\right){\mathbb{E}}\left[\left.\exp\left(-\lambda h\sum_{k=1}^{ \frac{K}{2}-1}\eta_{B,i,k}\right)\right|\mathcal{G}_{B-1}\right].$ $$

Using the same arguments $\frac{K}{2}-1$ times, we obtain

$$ $\displaystyle I_{1}\leq n\left(\exp\left(-\lambda t\right)+\frac{tp_{\sigma}}{ h}\right)^{\frac{K}{2}}$ (39) $$

for all $t\geq 0.$ The analysis of $I_{2}^{K/2}$ a little bit more evolved. For all $1\leq j\leq\frac{K}{2},$

$$ $\displaystyle I_{2}^{j}$ $\displaystyle:=\sum_{i=1}^{n}{\mathbb{E}}\left[\left.\exp\left(-\lambda\tau_{ \textnormal{s}}\sum_{k=1}^{j}\mu_{B,i,k}\right)\right|\mathcal{G}_{B-1}\right]$ $\displaystyle=\sum_{i=1}^{n}{\mathbb{E}}\left[\left.\underbrace{{\mathbb{E}} \left[\left.\exp\left(-\lambda\tau_{\textnormal{s}}\mu_{B,i,j}\right)\right| \mu_{B,i,j-1},\dots,\mu_{B,i,1},\mathcal{G}_{B-1}\right]\exp\left(-\lambda\tau _{\textnormal{s}}\sum_{k=1}^{j-1}\mu_{B,i,k}\right)}_{K_{2}:=}\right|\mathcal{ G}_{B-1}\right]$ $$

and $I_{2}^{0}=n.$
Let us define $u=\sum_{k=1}^{j-1}\mu_{B,i,k}.$ If $u\geq\frac{d}{2},$ then

$$ $\displaystyle K_{2}={\mathbb{E}}\left[\left.\exp\left(-\lambda\tau_{ \textnormal{s}}\mu_{B,i,j}\right)\right|\mu_{B,i,j-1},\dots,\mu_{B,i,1}, \mathcal{G}_{B-1}\right]\exp\left(-\lambda\tau_{\textnormal{s}}u\right)\leq \exp\left(-\frac{\lambda\tau_{\textnormal{s}}d}{2}\right)$ $$

Otherwise, if $u<\frac{d}{2},$ then, for all $t\geq 0,$

$$ $\displaystyle{\mathbb{E}}\left[\left.\exp\left(-\lambda\tau_{\textnormal{s}} \mu_{B,i,j}\right)\right|\mu_{B,i,j-1},\dots,\mu_{B,i,1},\mathcal{G}_{B-1}\right]$ $\displaystyle\leq\exp\left(-\lambda t\right)+\mathbb{P}\left(\mu_{B,i,j}\leq \frac{t}{\tau_{\textnormal{s}}}\middle|\mu_{B,i,j-1},\dots,\mu_{B,i,1}, \mathcal{G}_{B-1}\right)$ $\displaystyle\leq\exp\left(-\lambda t\right)+\frac{K\frac{t}{\tau_{\textnormal {s}}}}{d-u-\frac{t}{\tau_{\textnormal{s}}}+1}\leq\exp\left(-\lambda t\right)+ \frac{2Kt}{\tau_{\textnormal{s}}d-2t}$ $$

due to ([34](https://arxiv.org/html/2506.23836v1#A3.E34)) and $u<\frac{d}{2}.$ Combining both cases,

$$ $\displaystyle K_{2}\leq\max\left\{\left(\exp\left(-\lambda t\right)+\frac{2Kt} {\tau_{\textnormal{s}}d-2t}\right)\exp\left(-\lambda\tau_{\textnormal{s}}\sum_ {k=1}^{j-1}\mu_{B,i,k}\right),\exp\left(-\frac{\lambda\tau_{\textnormal{s}}d}{ 2}\right)\right\}$ $$

for all $t<\frac{\tau_{\textnormal{s}}d}{2}$ and $u\geq 0,$ and

$$ $\displaystyle I_{2}^{j}$ $\displaystyle\leq\left(\exp\left(-\lambda t\right)+\frac{2Kt}{\tau_{ \textnormal{s}}d-2t}\right)\sum_{i=1}^{n}{\mathbb{E}}\left[\left.\exp\left(- \lambda\tau_{\textnormal{s}}\sum_{k=1}^{j-1}\mu_{B,i,k}\right)\right|\mathcal{ G}_{B-1}\right]+n\exp\left(-\frac{\lambda\tau_{\textnormal{s}}d}{2}\right)$ $\displaystyle=\left(\exp\left(-\lambda t\right)+\frac{2Kt}{\tau_{\textnormal{s }}d-2t}\right)I_{2}^{j-1}+n\exp\left(-\frac{\lambda\tau_{\textnormal{s}}d}{2} \right),$ (40) $$

where we use the inequality $\max\{a,b\}\leq a+b$ for all $a,b\geq 0.$
Substituting ([39](https://arxiv.org/html/2506.23836v1#A3.E39)) to ([37](https://arxiv.org/html/2506.23836v1#A3.E37)),

$$ $\displaystyle{\mathbb{E}}\left[\left.\exp\left(-\lambda\min_{i\in[n]}\beta_{B, i}\right)\right|\mathcal{G}_{B-1}\right]\leq n\left(\exp\left(-\lambda t\right )+\frac{tp_{\sigma}}{h}\right)^{\frac{K}{2}}+I_{2}^{\frac{K}{2}},$ $$

where $t,\lambda\geq 0$ are free parameters. Taking $t=\frac{4+\frac{2}{K}\log(2n)}{\lambda},$

$$ $\displaystyle{\mathbb{E}}\left[\left.\exp\left(-\lambda\min_{i\in[n]}\beta_{B, i}\right)\right|\mathcal{G}_{B-1}\right]\leq n\left(\frac{e^{-4}}{(2n)^{2/K}}+ \frac{(4+\frac{2}{K}\log(2n))p_{\sigma}}{\lambda h}\right)^{\frac{K}{2}}+I_{2} ^{\frac{K}{2}}.$ $$

Choosing $\lambda=e^{4}(2n)^{2/K}(4+\frac{2}{K}\log(2n))\max\left\{\frac{p_{\sigma}}{h},
\frac{p_{K}}{\tau_{\textnormal{s}}}\right\},$

$$ $\displaystyle{\mathbb{E}}\left[\left.\exp\left(-\lambda\min_{i\in[n]}\beta_{B, i}\right)\right|\mathcal{G}_{B-1}\right]\leq n\left(\frac{2e^{-4}}{(2n)^{2/K}} \right)^{\frac{K}{2}}+I_{2}^{\frac{K}{2}}=\frac{1}{2}\left(2e^{-4}\right)^{ \frac{K}{2}}+I_{2}^{\frac{K}{2}}.$ $$

With this choice of $\lambda$ and $t$ in ([40](https://arxiv.org/html/2506.23836v1#A3.E40)), we get

$$ $\displaystyle I_{2}^{j}$ $\displaystyle\leq\left(\frac{3e^{-4}}{(2n)^{2/K}}\right)I_{2}^{j-1}+n\exp\left (-e^{4}(2n)^{2/K}(4K+2\log(2n))\right)$ $\displaystyle\leq\left(\frac{3e^{-4}}{(2n)^{2/K}}\right)I_{2}^{j-1}+e^{-4e^{4} K}\leq n\left(\frac{3e^{-4}}{(2n)^{2/K}}\right)^{j}+2e^{-4e^{4}K}$ $$

for all $j\geq 1$ because $t\leq\frac{\tau_{\textnormal{s}}d}{2e^{4}(2n)^{2/K}K},$ $\lambda=\frac{4+\frac{2}{K}\log(2n)}{t}\geq 2e^{4}(2n)^{2/K}(4+\frac{2}{K}\log
(2n))\frac{K}{\tau_{\textnormal{s}}d}.$ In the third inequality, we unrolled the recursion with $I^{0}_{2}=n$ and use $\sum_{j=0}^{\infty}\left(\frac{3e^{-4}}{(2n)^{2/K}}\right)^{j}\leq 2.$

Finally, $I_{2}^{K/2}\leq\frac{1}{2}\left(3e^{-4}\right)^{\frac{K}{2}}+2e^{-2e^{4}K}\leq
\frac{1}{2}e^{-K}$ and

$$ $\displaystyle{\mathbb{E}}\left[\left.\exp\left(-\lambda\min_{i\in[n]}\beta_{B, i}\right)\right|\mathcal{G}_{B-1}\right]\leq\frac{1}{2}\left(2e^{-4}\right)^{ \frac{K}{2}}+I_{2}^{K/2}\leq\frac{1}{2}e^{-K}+\frac{1}{2}e^{-K}\leq e^{-K}.$ $$

Substituting the last inequality to ([36](https://arxiv.org/html/2506.23836v1#A3.E36)) and repeating the steps $B-1$ more times, we get

$$ $\displaystyle\mathbb{P}\left(\sum_{b=1}^{B}\min_{i\in[n]}\beta_{b,i}\leq\bar{t }\right)\leq\exp\left(\lambda\bar{t}-BK\right).$ $$

It is left to take $\bar{t}=\frac{BK+\log\delta}{\lambda}.$
∎

###### Proof.

## Appendix D Main Theorem with Worker-to-Server Communication

Figure: Protocol 2

In this section, we extend the result of Theorem [4.2](https://arxiv.org/html/2506.23836v1#S4.Thmtheorem2) by taking into account the communication time $\tau_{\textnormal{w}}.$ Instead of Protocol [1](https://arxiv.org/html/2506.23836v1#alg1), we consider Protocol [2](https://arxiv.org/html/2506.23836v1#alg2). However, in this section, we ignore the communication times from the server to the workers and assume that $\tau_{\textnormal{s}}=0,$ which will be sufficient to obtain an almost tight lower bound if combined with Theorem [4.2](https://arxiv.org/html/2506.23836v1#S4.Thmtheorem2).

Tyurin et al. (2024) consider a similar setup with $\tau_{\textnormal{s}}=0.$ However, their protocol does not allow the workers to modify the iterate computed by the server and operates in the primal space. For instance, the workers are not allowed to run local steps. Moreover, $\bar{P}^{k}_{i}$ are fixed in their version of Protocol [2](https://arxiv.org/html/2506.23836v1#alg2). We improve upon this in the following theorem:

###### Theorem D.1 .

Let $L,\Delta,\varepsilon,\sigma^{2},n,d,\tau_{\textnormal{w}},h>0$ be any numbers such that $\varepsilon<c_{1}L\Delta$ and $d\geq\frac{\Delta L}{c_{2}\varepsilon}.$ Consider Protocol [2](https://arxiv.org/html/2506.23836v1#alg2). For all $i\in[n]$ and $k\geq 0,$ compressor $\bar{\mathcal{C}}^{k}_{i}$ selects and transmits $\bar{P}^{k}_{i}$ *uniformly random coordinates without replacement, scaled by any constants*,
where $\bar{P}^{k}_{i}\in\{0,\dots,d\}$ may vary across each compressor.
For any algorithm $A\in\mathcal{A}_{\textnormal{zr}},$ there exists a function $f\,:\,\mathbb{R}^{d}\to\mathbb{R}$ such that $f$ is $L$-smooth, $f(0)-\inf_{x\in\mathbb{R}^{d}}f(x)\leq\Delta,$ exists a stochastic gradient oracle that satisfies Assumption [1.3](https://arxiv.org/html/2506.23836v1#S1.Thmtheorem3), and
${\mathbb{E}}\left[\inf_{y\in S_{t}}\left\|\nabla f(y)\right\|^{2}\right]>\varepsilon$
for all

$$ $t\leq c_{3}\times\frac{L\Delta}{\varepsilon\log(n+1)}\cdot\min\left\{\max\left \{\frac{h\sigma^{2}}{n\varepsilon},\frac{\tau_{\textnormal{w}}d}{n},\sqrt{ \frac{h\sigma^{2}\tau_{\textnormal{w}}d}{n\varepsilon}},h,\tau_{\textnormal{w} }\right\},\max\left\{\frac{h\sigma^{2}}{\varepsilon},h\right\}\right\},$ $$

where
$S_{t}$ is the set of all possible points that can be constructed by $A$ up to time $t$ based on $I$ and $\{I_{i}\}.$ The quantities $c_{1},$ $c_{2},$ and $c_{3}$ are universal constants.

###### Proof.

The proof closely follows the analysis from (Tyurin et al., 2024; Tyurin & Richtárik, 2024) and the proof of Theorem [4.2](https://arxiv.org/html/2506.23836v1#S4.Thmtheorem2), but with some important modifications. In this proof, it is sufficient to work with ([6](https://arxiv.org/html/2506.23836v1#S2.E6)) and Lemmas [2.1](https://arxiv.org/html/2506.23836v1#S2.Thmtheorem1) and [2.2](https://arxiv.org/html/2506.23836v1#S2.Thmtheorem2).

Let us fix $\lambda>0$ and define the function $f\,:\,\mathbb{R}^{d}\to\mathbb{R}$ such that

$$ $f(x):=\frac{L\lambda^{2}}{\ell_{1}}F_{T}\left(\frac{x_{[T]}}{\lambda}\right),$ $$

where the function $F_{T}$ is given in ([6](https://arxiv.org/html/2506.23836v1#S2.E6)) and $x_{[T]}\in\mathbb{R}^{T}$ is the vector with the first $T$ coordinates of $x\in\mathbb{R}^{d}.$ Notice that the last $d-T$ coordinates are artificial.

First, we have to show that $f$ is $L$-smooth and $f(0)-\inf_{x\in\mathbb{R}^{d}}f(x)\leq\Delta.$ Using Lemma [2.2](https://arxiv.org/html/2506.23836v1#S2.Thmtheorem2),

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

Taking

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

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

due to Lemma [2.2](https://arxiv.org/html/2506.23836v1#S2.Thmtheorem2).

Next, we construct a stochastic gradient mapping. For our lower bound, we define

$$ $\displaystyle[\nabla f(x;\xi)]_{j}:=\nabla_{j}f(x)\left(1+\mathbbm{1}\left[j> \textnormal{prog}(x)\right]\left(\frac{\xi}{p_{\sigma}}-1\right)\right)\quad \forall x\in\mathbb{R}^{d},$ (41) $$

and let $\mathcal{D}_{\xi}=\textnormal{\emph{Bernoulli}}(p_{\sigma})$ for all $j\in[n],$ where $p_{\sigma}\in(0,1].$
We denote $[x]_{j}$ as the $j$^th coordinate of a vector $x\in\mathbb{R}^{d}.$
We choose

$$ $p_{\sigma}:=\min\left\{\frac{L^{2}\lambda^{2}\gamma_{\infty}^{2}}{\sigma^{2} \ell_{1}^{2}},1\right\}.$ $$

Then this mapping is unbiased and $\sigma^{2}$-variance-bounded.
Indeed,

$$ ${\mathbb{E}}\left[[\nabla f(x,\xi)]_{i}\right]=\nabla_{i}f(x)\left(1+\mathbbm{ 1}\left[i>\textnormal{prog}(x)\right]\left(\frac{{\mathbb{E}}\left[\xi\right]} {p_{\sigma}}-1\right)\right)=\nabla_{i}f(x)$ $$

for all $i\in[d],$ and

$$ $\displaystyle{\mathbb{E}}\left[\left\|\nabla f(x;\xi)-\nabla f(x)\right\|^{2} \right]\leq\max_{j\in[d]}\left|\nabla_{j}f(x)\right|^{2}{\mathbb{E}}\left[ \left(\frac{\xi}{p_{\sigma}}-1\right)^{2}\right]$ $$

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

$$ $\displaystyle{\mathbb{E}}\left[\left\|\nabla f(x,\xi)-\nabla f(x)\right\|^{2}\right]$ $\displaystyle\leq\frac{\left\|\nabla f(x)\right\|_{\infty}^{2}(1-p_{\sigma})}{ p_{\sigma}}=\frac{L^{2}\lambda^{2}\left\|F_{T}\left(\frac{x_{[T]}}{\lambda} \right)\right\|_{\infty}^{2}(1-p_{\sigma})}{\ell^{2}_{1}p_{\sigma}}$ $\displaystyle\leq\frac{L^{2}\lambda^{2}\gamma_{\infty}^{2}(1-p_{\sigma})}{\ell ^{2}_{1}p_{\sigma}}\leq\sigma^{2},$ $$

where we use Lemma [2.2](https://arxiv.org/html/2506.23836v1#S2.Thmtheorem2).

Taking

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

we ensure that

$$ $\displaystyle\left\|\nabla f(x)\right\|^{2}=\frac{L^{2}\lambda^{2}}{\ell_{1}^{ 2}}\left\|\nabla F_{T}\left(\frac{x_{[T]}}{\lambda}\right)\right\|^{2}>2 \varepsilon\mathbbm{1}\left[\textnormal{prog}(x_{[T]})<T\right]$ (42) $$

for all $x\in\mathbb{R}^{d},$ where we use Lemma [2.1](https://arxiv.org/html/2506.23836v1#S2.Thmtheorem1). Thus

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

and

$$ $p_{\sigma}=\min\left\{\frac{2\varepsilon\gamma_{\infty}^{2}}{\sigma^{2}},1 \right\}.$ $$

Using the same reasoning as in Tyurin et al. (2024) and our Theorem [4.2](https://arxiv.org/html/2506.23836v1#S4.Thmtheorem2), we define two sets of random variables. Let $\eta_{1,i}$ be the first computed stochastic gradient when the oracle draws a “successful” Bernoulli trial in ([41](https://arxiv.org/html/2506.23836v1#A4.E41)) at worker $i.$ Then,

$$ $\displaystyle\mathbb{P}\left(\eta_{1,i}\leq t\right)\leq\sum_{i=1}^{\left \lfloor t\right\rfloor}(1-p_{\sigma})^{i-1}p_{\sigma}\leq p_{\sigma}\left \lfloor t\right\rfloor$ $$

for $t\geq 0,$ and

$$ $\displaystyle\mathbb{P}\left(\eta_{1,i}\leq t\right)\leq\min\{p_{\sigma}\left \lfloor t\right\rfloor,1\}$ $$

For all $i\in[n],$ the server receives a stream of coordinates from worker $i.$ Let $\mu_{1,i}$ be the number of received coordinates by the server from worker $i$ until the moment when the index of the last received coordinate is $1$.
Let us define

$$ $\displaystyle p_{d}:=\frac{2}{d}.$ $$

Similarly to the proof of Theorem [4.2](https://arxiv.org/html/2506.23836v1#S4.Thmtheorem2) with $K=1$ (see ([29](https://arxiv.org/html/2506.23836v1#A3.E29))),

$$ $\displaystyle\mathbb{P}\left(\mu_{1,i}\leq t\middle|\eta_{1,i}\right)=\sum_{j= 1}^{\left\lfloor t\right\rfloor}\mathbb{P}\left(\mu_{1,i,1}=j\right)\leq\frac{ \left\lfloor t\right\rfloor}{d-t+1}.$ $$

for all $t\leq d.$ Thus,

$$ $\displaystyle\mathbb{P}\left(\mu_{1,i}\leq t\middle|\eta_{1,i}\right)\leq \begin{cases}\frac{\left\lfloor t\right\rfloor}{d-t+1},&t\leq\frac{d}{2}\\ 1,&t>\frac{d}{2}\\ \end{cases}\leq\begin{cases}\left\lfloor t\right\rfloor p_{d},&t\leq\frac{d}{2 }\\ 1,&t>\frac{d}{2}\end{cases}\leq\min\{2\left\lfloor t\right\rfloor p_{d},1\}$ $$

for all $t\geq 0.$

There are two ways in which worker $i$ can discover the first coordinate. Either the worker is “lucky” and draws a successful Bernoulli random variable locally, or it gets to discover the first coordinate through the server. Thus, worker $i$ requires at least

$$ $\displaystyle y_{1,i}:=\min\left\{h\eta_{1,i},\min_{j\in[n],j\neq i}\left\{h \eta_{1,j}+\tau_{\textnormal{w}}\mu_{1,j}\right\}\right\}=\min_{j\in[n]}\left \{h\eta_{1,j}+\mathbbm{1}[i\neq j]\tau_{\textnormal{w}}\mu_{1,j}\right\}$ $$

seconds because $h\eta_{1,i}$ is the minimal time to discover the first coordinate locally, and $\min_{j\in[n],j\neq i}\left\{h\eta_{1,j}+\tau_{\textnormal{w}}\mu_{1,j}\right\}$ is the minimal time to discover the first coordinate from other workers via the server, which can transmit (for free since $\tau_{\textnormal{s}}=0$) it to worker $i.$

Using the same reasoning, worker $i$ requires at least

$$ $\displaystyle y_{k,i}:=\min_{j\in[n]}\left\{h\eta_{k,j}+\mathbbm{1}[i\neq j] \tau_{\textnormal{w}}\mu_{k,j}+y_{k-1,j}\right\}$ $$

seconds to discover the $k$^th coordinate for all $k\geq 2,$ where

$$ $\displaystyle\mathbb{P}\left(\eta_{k,i}\leq t\middle|\mathcal{G}_{k-1}\right) \leq\min\{\left\lfloor t\right\rfloor p_{\sigma},1\}$ (44) $$

for all $k\geq 1,$ $i\in[n],$ and $t\geq 0,$ and

$$ $\displaystyle\mathbb{P}\left(\mu_{k,i}\leq t\middle|\eta_{k,i},\mathcal{G}_{k- 1}\right)\leq\min\{2\left\lfloor t\right\rfloor p_{d},1\}$ (45) $$

for all $k\geq 1,$ $i\in[n],$ and $t\geq 0,$ where $\mathcal{G}_{k-1}$ is the sigma-algebra generated by $\{\eta_{k^{\prime},i}\}_{i\in[n],k^{\prime}<k}$ and $\{\mu_{k^{\prime},i}\}_{i\in[n],k^{\prime}<k}.$ Thus, the first possible time when the workers and the server can discover the $T$^th coordinate is

$$ $\displaystyle y_{T}:=\min_{i\in[n]}y_{T,i}.$ $$

For this random variable, we prove the lemma below (see Section [D.1](https://arxiv.org/html/2506.23836v1#A4.SS1)).

###### Lemma D.2 .

Let $\{\eta_{k,i}\}_{i,k\geq 0}$ and $\{\mu_{k,i}\}_{i,k\geq 0}$ be random variables such that

$$ $\displaystyle\mathbb{P}\left(\eta_{k,i}\leq t\middle|\mathcal{G}_{k-1}\right) \leq\min\{\left\lfloor t\right\rfloor p_{\sigma},1\}$ (46) $$

for all $k\geq 1,$ $i\in[n],$ and $t\geq 0,$ and

$$ $\displaystyle\mathbb{P}\left(\mu_{k,i}\leq t\middle|\eta_{k,i},\mathcal{G}_{k- 1}\right)\leq\min\{2\left\lfloor t\right\rfloor p_{d},1\},$ (47) $$

for all $k\geq 1,$ $i\in[n],$ and $t\geq 0,$ where $\mathcal{G}_{k-1}$ is the sigma-algebra generated by $\{\eta_{k^{\prime},i}\}_{i\in[n],k^{\prime}<k}$ and $\{\mu_{k^{\prime},i}\}_{i\in[n],k^{\prime}<k}.$ Then

$$ $\displaystyle\mathbb{P}\left(y_{T}\leq\bar{t}\right)\leq\delta$ $$

with

$$ $\displaystyle\bar{t}:=\frac{T-\log n+\log\delta}{32\log(8n)}\cdot\min\left\{ \max\left\{\frac{h}{p_{\sigma}n},\frac{\tau_{\textnormal{w}}}{p_{d}n},\frac{ \sqrt{h\tau_{\textnormal{w}}}}{\sqrt{p_{\sigma}p_{d}n}},h,\tau_{\textnormal{w} }\right\},\frac{h}{p_{\sigma}}\right\},$ (48) $$

where

$$ $\displaystyle y_{T}:=\min_{i\in[n]}y_{T,i},$ $$

$$ $\displaystyle y_{k,i}:=\min_{j\in[n]}\left\{h\eta_{k,j}+\mathbbm{1}[i\neq j] \tau_{\textnormal{w}}\mu_{k,j}+y_{k-1,j}\right\}$ $$

for all $k\geq 1,i\in[n]$ and $y_{0,i}=0$ for all $i\in[n].$

Thus, with probability at least $1-\delta$, any zero-respecting algorithm requires at least $\bar{t}$ seconds to discover the last coordinate.
Due to ([42](https://arxiv.org/html/2506.23836v1#A4.E42)),

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

where $S_{t}$ is the set of all possible candidate points to be an $\varepsilon$–stationary point up to time $t,$ which can be computed by $A.$ Taking $\delta=\frac{1}{2},$

$$ $\displaystyle{\mathbb{E}}\left[\inf_{y\in S_{t}}\left\|\nabla f(y)\right\|^{2} \right]>2\varepsilon{\mathbb{E}}\left[\inf_{y\in S_{t}}\mathbbm{1}\left[ \textnormal{prog}(y_{[T]})<T\right]\right]\geq\varepsilon,$ $$

for $t=\frac{1}{2}\bar{t}$ because $\textnormal{prog}(y_{[T]})<T$ for all $y\in S_{t}$ with probability at least $\frac{1}{2}.$ It is left to substitute all quantities:

$$ $\displaystyle t=\frac{\left\lfloor\frac{\Delta L}{2\varepsilon\ell_{1}\Delta^{ 0}}\right\rfloor-\log n+\log\frac{1}{2}}{64\log(8n)}\cdot\min\left\{\max\left \{\frac{h}{n}\max\left\{\frac{\sigma^{2}}{2\varepsilon\gamma_{\infty}^{2}},1 \right\},\frac{\tau_{\textnormal{w}}d}{2n},\frac{\sqrt{hd\tau_{\textnormal{w}} }}{\sqrt{2n}}\sqrt{\frac{\sigma^{2}}{2\varepsilon\gamma_{\infty}^{2}}},h,\tau_ {\textnormal{w}}\right\},h\max\left\{\frac{\sigma^{2}}{2\varepsilon\gamma_{ \infty}^{2}},1\right\}\right\}.$ $$

Since $\ell_{1},\Delta^{0},\gamma_{\infty}$ are universal constants, assuming $\varepsilon<c_{1}L\Delta$ for some small universal $c_{1}>0,$ we get

$$ $\displaystyle t\geq c_{3}\times\frac{L\Delta}{\varepsilon\log(n+1)}\cdot\min \left\{\max\left\{\frac{h\sigma^{2}}{n\varepsilon},\frac{\tau_{\textnormal{w}} d}{n},\sqrt{\frac{h\sigma^{2}\tau_{\textnormal{w}}d}{n\varepsilon}},h,\tau_{ \textnormal{w}}\right\},\max\left\{\frac{h\sigma^{2}}{\varepsilon},h\right\}\right\}$ $$

for some small universal $c_{3}>0.$ Notice that we can take any dimension $d$ such that

$$ $\displaystyle d\geq T=\Theta\left(\frac{L\Delta}{\varepsilon}\right).$ $$

∎

###### Theorem D.1 .

###### Proof.

###### Lemma D.2 .

### D.1 Main Concentration Lemma

See [D.2](https://arxiv.org/html/2506.23836v1#A4.Thmtheorem2)

###### Proof.

Using the Chernoff method for any $s>0$ and $k\geq 1$, we get

$$ $\displaystyle\mathbb{P}\left(y_{k}\leq\bar{t}\right)$ $\displaystyle=\mathbb{P}\left(-sy_{k}\geq-s\bar{t}\right)=\mathbb{P}\left(e^{- sy_{k}}\geq e^{-s\bar{t}}\right)\leq e^{s\bar{t}}{\mathbb{E}}\left[e^{-sy_{k}}\right]$ $\displaystyle=e^{s\bar{t}}{\mathbb{E}}\left[\exp\left(-s\min_{j\in[n]}y_{k,j} \right)\right]=e^{s\bar{t}}{\mathbb{E}}\left[\max_{j\in[n]}\exp\left(-sy_{k,j} \right)\right].$ $$

Bounding the maximum by the sum,

$$ $\displaystyle\mathbb{P}\left(y_{k}\leq t\right)$ $\displaystyle\leq e^{st}\sum_{j=1}^{n}{\mathbb{E}}\left[\exp\left(-sy_{k,j} \right)\right]\leq ne^{st}\max_{j\in[n]}{\mathbb{E}}\left[\exp\left(-sy_{k,j} \right)\right].$ (49) $$

We focus on the last exponent separately. For all $i\in[n],$

$$ $\displaystyle{\mathbb{E}}\left[\exp\left(-sy_{k,i}\right)\right]$ $\displaystyle={\mathbb{E}}\left[\exp\left(-s\min_{j\in[n]}\left\{h\eta_{k,j}+ \mathbbm{1}[i\neq j]\tau_{\textnormal{w}}\mu_{k,j}+y_{k-1,j}\right\}\right)\right]$ (50) $\displaystyle={\mathbb{E}}\left[\max_{j\in[n]}\exp\left(-s\left(h\eta_{k,j}+ \mathbbm{1}[i\neq j]\tau_{\textnormal{w}}\mu_{k,j}+y_{k-1,j}\right)\right)\right]$ $\displaystyle\leq\sum_{j=1}^{n}{\mathbb{E}}\left[\exp\left(-s\left(h\eta_{k,j} +\mathbbm{1}[i\neq j]\tau_{\textnormal{w}}\mu_{k,j}+y_{k-1,j}\right)\right)\right]$ $\displaystyle=\sum_{j=1}^{n}{\mathbb{E}}\left[\underbrace{{\mathbb{E}}\left[ \left.\exp\left(-s\left(h\eta_{k,j}+\mathbbm{1}[i\neq j]\tau_{\textnormal{w}} \mu_{k,j}\right)\right)\right|\mathcal{G}_{k-1}\right]}_{I_{1}:=}\exp\left(-sy _{k-1,j}\right)\right]$ $$

Considering the inner expectation separately:

$$ $\displaystyle I_{1}$ $\displaystyle={\mathbb{E}}\left[\left.\exp\left(-s\left(h\eta_{k,j}+\mathbbm{1 }[i\neq j]\tau_{\textnormal{w}}\mu_{k,j}\right)\right)\right|\mathcal{G}_{k-1}\right]$ $\displaystyle\leq\exp\left(-st\right)+\mathbb{P}\left(h\eta_{k,j}+\mathbbm{1}[ i\neq j]\tau_{\textnormal{w}}\mu_{k,j}\leq t\middle|\mathcal{G}_{k-1}\right)$ $$

for all $t\geq 0.$ Using the properties of condition expectations,

$$ $\displaystyle I_{1}$ $\displaystyle\leq\exp\left(-st\right)+\mathbb{P}\left(h\eta_{k,j}\leq t, \mathbbm{1}[i\neq j]\tau_{\textnormal{w}}\mu_{k,j}\leq t\middle|\mathcal{G}_{k -1}\right)$ $\displaystyle=\exp\left(-st\right)+{\mathbb{E}}\left[\left.\mathbbm{1}\left[h \eta_{k,j}\leq t\right]\mathbbm{1}\left[\mathbbm{1}[i\neq j]\tau_{\textnormal{ w}}\mu_{k,j}\leq t\right]\right|\mathcal{G}_{k-1}\right]$ $\displaystyle=\exp\left(-st\right)+{\mathbb{E}}\left[\left.{\mathbb{E}}\left[ \left.\mathbbm{1}\left[\mathbbm{1}[i\neq j]\tau_{\textnormal{w}}\mu_{k,j}\leq t \right]\right|\eta_{k,j},\mathcal{G}_{k-1}\right]\mathbbm{1}\left[h\eta_{k,j} \leq t\right]\right|\mathcal{G}_{k-1}\right]$ $\displaystyle=\exp\left(-st\right)+{\mathbb{E}}\left[\left.\mathbb{P}\left( \mathbbm{1}[i\neq j]\tau_{\textnormal{w}}\mu_{k,j}\leq t\middle|\eta_{k,j}, \mathcal{G}_{k-1}\right)\mathbbm{1}\left[h\eta_{k,j}\leq t\right]\right| \mathcal{G}_{k-1}\right].$ $$

If $i=j,$ then we bound the probability by $1$ and get

$$ $\displaystyle I_{1}$ $\displaystyle\leq\exp\left(-st\right)+{\mathbb{E}}\left[\left.\mathbbm{1}\left [h\eta_{k,j}\leq t\right]\right|\mathcal{G}_{k-1}\right]$ $\displaystyle=\exp\left(-st\right)+\mathbb{P}\left(h\eta_{k,j}\leq t\middle| \mathcal{G}_{k-1}\right)$ $\displaystyle\leq\exp\left(-st\right)+\left\lfloor\frac{t}{h}\right\rfloor p_{ \sigma},$ $$

for all $t\geq 0,$ where we use ([46](https://arxiv.org/html/2506.23836v1#A4.E46)). Otherwise, if $i\neq j,$ using ([47](https://arxiv.org/html/2506.23836v1#A4.E47)) and ([46](https://arxiv.org/html/2506.23836v1#A4.E46)),

$$ $\displaystyle I_{1}$ $\displaystyle\leq\exp\left(-st\right)+{\mathbb{E}}\left[\left.\min\left\{1,2 \left\lfloor\frac{t}{\tau_{\textnormal{w}}}\right\rfloor p_{d}\right\}\mathbbm {1}\left[h\eta_{k,j}\leq t\right]\right|\mathcal{G}_{k-1}\right]$ $\displaystyle=\exp\left(-st\right)+\min\left\{1,2\left\lfloor\frac{t}{\tau_{ \textnormal{w}}}\right\rfloor p_{d}\right\}\mathbb{P}\left(h\eta_{k,j}\leq t \middle|\mathcal{G}_{k-1}\right)$ $\displaystyle\leq\exp\left(-st\right)+\min\left\{1,2\left\lfloor\frac{t}{\tau_ {\textnormal{w}}}\right\rfloor p_{d}\right\}\min\left\{1,\left\lfloor\frac{t}{ h}\right\rfloor p_{\sigma}\right\}$ $$

for all $t\geq 0.$ Substituting the inequalities to ([50](https://arxiv.org/html/2506.23836v1#A4.E50)),

$$ $\displaystyle{\mathbb{E}}\left[\exp\left(-sy_{k,i}\right)\right]$ $\displaystyle=\sum_{j\neq i}\left(\exp\left(-st\right)+\min\left\{1,2\left \lfloor\frac{t}{\tau_{\textnormal{w}}}\right\rfloor p_{d}\right\}\min\left\{1, \left\lfloor\frac{t}{h}\right\rfloor p_{\sigma}\right\}\right){\mathbb{E}} \left[\exp\left(-sy_{k-1,j}\right)\right]$ $\displaystyle+\quad\left(\exp\left(-st\right)+\min\left\{1,\left\lfloor\frac{t }{h}\right\rfloor p_{\sigma}\right\}\right){\mathbb{E}}\left[\exp\left(-sy_{k- 1,i}\right)\right].$ $$

for all $i\in[n]$ and $t\geq 0.$ Thus,

$$ $\displaystyle\max_{i\in[n]}{\mathbb{E}}\left[\exp\left(-sy_{k,i}\right)\right]$ $\displaystyle\leq\left[(n-1)\left(\exp\left(-st\right)+\min\left\{1,2\left \lfloor\frac{t}{\tau_{\textnormal{w}}}\right\rfloor p_{d}\right\}\min\left\{1, \left\lfloor\frac{t}{h}\right\rfloor p_{\sigma}\right\}\right)+\left(\exp\left (-st\right)+\min\left\{1,\left\lfloor\frac{t}{h}\right\rfloor p_{\sigma}\right \}\right)\right]$ $\displaystyle\quad\times\max_{i\in[n]}{\mathbb{E}}\left[\exp\left(-sy_{k-1,i} \right)\right]$ $\displaystyle=\left[n\exp\left(-st\right)+(n-1)\left(\min\left\{1,2\left \lfloor\frac{t}{\tau_{\textnormal{w}}}\right\rfloor p_{d}\right\}\min\left\{1, \left\lfloor\frac{t}{h}\right\rfloor p_{\sigma}\right\}\right)+\min\left\{1, \left\lfloor\frac{t}{h}\right\rfloor p_{\sigma}\right\}\right]\max_{i\in[n]}{ \mathbb{E}}\left[\exp\left(-sy_{k-1,i}\right)\right].$ $$

Taking $s=\frac{\log(8n)}{t},$ we get

$$ $\displaystyle\max_{i\in[n]}{\mathbb{E}}\left[\exp\left(-sy_{k,i}\right)\right]$ (51) $\displaystyle\leq\left[\frac{1}{8}+\underbrace{(n-1)\left(\min\left\{1,2\left \lfloor\frac{t}{\tau_{\textnormal{w}}}\right\rfloor p_{d}\right\}\min\left\{1, \left\lfloor\frac{t}{h}\right\rfloor p_{\sigma}\right\}\right)}_{I_{2}:=}+ \underbrace{\min\left\{1,\left\lfloor\frac{t}{h}\right\rfloor p_{\sigma}\right \}}_{I_{3}:=}\right]\max_{i\in[n]}{\mathbb{E}}\left[\exp\left(-sy_{k-1,i} \right)\right].$ $$

Next, we take $t=\min\{t_{1},t_{2}\},$ where

$$ $\displaystyle t_{1}:=\max\left\{\frac{h}{32p_{\sigma}n},\frac{\tau_{ \textnormal{w}}}{32p_{d}n},\frac{\sqrt{h\tau_{\textnormal{w}}}}{32\sqrt{p_{ \sigma}p_{d}n}},\frac{h}{32},\frac{\tau_{\textnormal{w}}}{32}\right\},$ $$

and

$$ $\displaystyle t_{2}:=\frac{h}{32p_{\sigma}}$ $$

to ensure that

$$ $I_{3}\leq\min\left\{1,\frac{t_{2}p_{\sigma}}{h}\right\}\leq\frac{1}{16}.$ $$

There are five possible values of $t_{1}.$

If $t_{1}=\frac{h}{32p_{\sigma}n},$ then

$$ $\displaystyle I_{2}\leq(n-1)\min\left\{1,\frac{t_{1}p_{\sigma}}{h}\right\}\leq \frac{1}{16},$ $$

If $t_{1}=\frac{\tau_{\textnormal{w}}}{32p_{d}n},$ then

$$ $\displaystyle I_{2}\leq(n-1)\min\left\{1,\frac{2t_{1}p_{d}}{\tau_{\textnormal{ w}}}\right\}\leq\frac{1}{16}.$ $$

If $t_{1}=\frac{\sqrt{h\tau_{\textnormal{w}}}}{32\sqrt{p_{\sigma}p_{d}n}},$ then

$$ $\displaystyle I_{2}\leq(n-1)\frac{2t_{1}^{2}p_{d}p_{\sigma}}{\tau_{\textnormal {w}}h}\leq\frac{1}{16}.$ $$

If $t_{1}=\frac{h}{32},$ then

$$ $\displaystyle I_{2}\leq(n-1)\min\left\{1,\left\lfloor\frac{t_{1}}{h}\right \rfloor p_{\sigma}\right\}=0.$ $$

Finally, if $t_{1}=\frac{\tau_{\textnormal{w}}}{32},$ then

$$ $\displaystyle I_{2}\leq(n-1)\min\left\{1,2\left\lfloor\frac{t_{1}}{\tau_{ \textnormal{w}}}\right\rfloor p_{d}\right\}=0.$ $$

Thus, using ([51](https://arxiv.org/html/2506.23836v1#A4.E51)), we obtain

$$ $\displaystyle\max_{i\in[n]}{\mathbb{E}}\left[\exp\left(-sy_{k,i}\right)\right] \leq\left[\frac{1}{8}+\frac{1}{16}+\frac{1}{16}\right]\max_{i\in[n]}{\mathbb{E }}\left[\exp\left(-sy_{k-1,i}\right)\right]\leq e^{-1}\max_{i\in[n]}{\mathbb{E }}\left[\exp\left(-sy_{k-1,i}\right)\right]$ $$

for our choice of $t.$ Unrolling the recursion and using $y_{0,i}=0$ for all $i\in[n],$

$$ $\displaystyle\max_{i\in[n]}{\mathbb{E}}\left[\exp\left(-sy_{k,i}\right)\right] \leq e^{-k}.$ $$

We substitute it to ([49](https://arxiv.org/html/2506.23836v1#A4.E49)), to get

$$ $\displaystyle\mathbb{P}\left(y_{k}\leq\bar{t}\right)\leq e^{s\bar{t}+\log n-k}.$ $$

It is left to choose $\bar{t}=\frac{k-\log n+\log\delta}{s}.$
∎

###### Proof.

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 4
presentation: 2
questions: 1)Theorem 4.2 contains only $\tau_s$, but no $\tau_w$. Theorem E.1, on the contrary, contains $\tau_w$, but no $\tau_s$. Could the authors clarify, how they correctly combine lower bound, that involve both s2w and w2s communications?

2)Could authors specify more, how does the heterogeneous setup fail under the consideration of s2w communications?
soundness: 3
strengths: 1)Addressing not only w2s, but also s2w communications is important and not usually done in optimization.

2)Modifying the worst-case function and using novel techniques to prove the lower bounds.
summary: In the paper the authors discuss the influence of both worker to server (w2s) and server to worker (s2w) communications on the overall complexity of solving the distributed optimization problem. The authors propose a new worst-case function, that is required to prove the lower bounds for this setup.
weaknesses: 1)The class of zero-respecting protocols is quite restricting, as it does not contain sketchings, dithered quantizations, and so on. 

2)Theorems 4.2 and E.1 seems to be proven only for RandK compressors, rather than for any unbiased zero-respecting.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: I checked all the theorems, except for key Lemma D.1. Therefore, I don't have any major or minor comments, and for this reason, I marked a low level of confidence.
soundness: 3
strengths: 1) This paper is well written, and all the results are clarified.

2) This paper provides a new construction for lower bounds.

3) The result of this paper provides theoretical evidence and a quality comparison with previous works.
summary: This paper presents lower bounds for centralized federated learning under $L$-smoothness, where communication time is important. It contains a new construction of lower bounds with theoretical guarantees.

 I think this paper may be accepted.
weaknesses: **Typos:** 

1). p. 5 line 228. It seems “quartic” $\to$ “quadratic”

2). P. 7 line 377. I think, $F_T \to F_{T, K, a}$

3). P. 22 line 1146. $j \to k$

---

confidence: 4
contribution: 4
initial_rating: 6
presentation: 3
questions: 1. Because section 2.1 is not super clear, does the class of algorithms considered here allow simultaneous queries (multiple queries at the same random seed) or not? What about local update algorithms? Can the queries be adaptive to the information on each machine locally or not? I would like the authors to comment on the results of [Patel et al.](https://openreview.net/pdf?id=SNElc7QmMDe), which may provide better upper bounds when simultaneous queries are permitted. 
2. In the vein of the previous question, can the authors use their hard instance to give better lower bounds in the setting when computation and communication times are not critical, and we are looking at oracle complexity? Specifically, I want to understand whether the new technique can actually demonstrate that the convergence rate of SCAFFOLD and MB-SGD is tight in the oracle complexity sense. For more context, see [Table 1](https://openreview.net/pdf?id=SNElc7QmMDe) of Patel et al. and note that there is no lower bound for the single query model (their Theorem 3.2 can not demarcate between single and multiple queries).   
3. How is the result in this paper morally different from [Woodworth et al.](https://arxiv.org/abs/2102.01583)? Should I view the consequence of the result as just the time-complexity version of their result? If so, can the authors comment on whether they believe non-convexity is actually critical to their construction? If not, is it possible to get a similar dichotomy between mini-batch and single-machine SGD in the convex setting as well? That would complete the picture in the homogeneous setting.
soundness: 4
strengths: The paper is well-written; it provides a comprehensive survey of the current landscape of results and algorithms, ultimately highlighting the gap in existing rates when it comes to time complexity, thereby motivating the central question of the paper. The paper also does a good job of summarizing the technical preliminaries and clearly expresses the novel technical idea. As mentioned above, the dichotomy between mini-batch and single machine SGD is a somewhat surprising result in the non-convex setting. It provides clarity on existing gaps and guides future research.
summary: This paper presents new lower bounds for centralized distributed non-convex optimization of smooth functions. This is an active area, where convergence guarantees for finding approximate stationary points using first-order stochastic oracles have been studied extensively in the past several years. The key difference in this paper's setting is that, instead of examining oracle, communication, or iteration complexity, the paper focuses on time complexity in a model where each machine has the same computation speed and potentially different up (to the server) and down (from the server) communication times. The paper considers the homogeneous setting, for which it is more challenging to establish lower bounds, as one can not benefit from the usual round complexity constructions, which force machines to depend on each other for growing the coordinate span of their model. 

The most remarkable, and perhaps astonishing, result that the paper shows is that when the up and down communication times are comparable, the optimal time complexity is attained by the best of (uncompressed) mini-batch SGD and single-machine SGD. Given the attention this research area has received, a plethora of algorithms have been devised and analyzed, including compression algorithms. However, the fact that one of the two simplest algorithms is min-max optimal provides a firm foundation for the optimization theory in this area. Notably, this result is comparable to the seminal work of [Woodworth et al.](https://arxiv.org/abs/2102.01583), which also reveals the same dichotomy for homogeneous smooth convex optimization, but without considering computation and communication times. 

Additionally, the paper presents a lower bound in the case where up and down communication require different times. In that setting, the bound is still matched by either one of the most natural compression algorithms, mini-batch QSGD or single machine SGD. The hard instance for the lower bound follows the serial hard instance due to Carmon et al., which in turn follows the chain function of Nesterov. The authors make the original hard instance more complex by altering the process of discovering the next coordinate. 

Overall, besides minor writing issues, I don't have any significant concerns with the paper and recommend accepting it. Once the authors address the writing issues, I am happy to increase my score.
weaknesses: 1. I believe the paper can do a more thorough job of reviewing the relevant literature. For instance, the morally most similar paper due to [Woodworth et al.](https://arxiv.org/abs/2102.01583) is not discussed. Similarly, several other interesting related threads are not discussed, such as multi-point oracles and variance reduction, which present natural improvements in the non-convex setting and where, in the oracle complexity model, (almost) min-max rates [are known](https://openreview.net/forum?id=SNElc7QmMDe). 
2. While the lower bound of the paper is surprising, I believe it is essential to highlight that the lower bound itself does not indicate or explain the "limited scalability of centralized distributed optimization". Firstly, the lower bound considers a specific setting of homogeneous non-convex optimization. It is very well possible that under additional assumptions, such as higher-order smoothness and/or some notion of quasi-convexity, we might expect different results and optimal algorithms. I would encourage the authors to read the future directions presented by [Woodworth et al.](https://arxiv.org/abs/2102.01583), which indeed motivated many exciting follow-up results. I recommend that the authors temper the conclusions to be drawn from the results, and instead use these to either motivate why other settings might be interesting to study or show empirical evidence that centralized distributed optimization has indeed plateaued (the latter is very unlikely to be the case).
3. It is essential to underline that while in optimization theory the variance reduction due to averaging across the clients is usually the only justification for collaboration, that is a very narrow view. In a sense, the model under which such rates are provided is actually too restrictive to demonstrate the other benefits of collaboration. For instance, in the same vein as the hard instance of this paper, collaboration can help clients discover parts of the loss landscape that are inaccessible to individual clients. This effect does not appear in the stochastic optimization setup where fresh samples are used, and there is no distribution shift between the training and test distributions. Both of these effects are unavoidable in practice. Similarly, there is ample evidence that collaboration can have a regularization effect. This has been studied in the context of local update algorithms ([1](https://openreview.net/forum?id=dOoPSZFDiRB), [Section 4.3](https://arxiv.org/pdf/2507.00195)), but it may also be true in general for other forms of collaboration. 

Overall, in the last two points, I aim to emphasize that it is crucial to note that the paper examines a specific theoretical model, which does provide some evidence for what we might observe in real experiments. However, ultimately, that is a particular model, which can not capture all aspects of empirical training. 

4. I believe the presentation and definition of distributed zero respecting algorithms (whole of section 2.1) can be made much more crisp by introducing an oracle model. I recommend that the authors check the definitions in [Patel et al.](https://openreview.net/forum?id=SNElc7QmMDe) and other similar papers. Protocol 1 is quite confusing, and I especially don't like how the authors present two parallel for loops sequentially. I believe it is ambiguous to say what it means to calculate the next point, based on some information. This can be made more rigorous by considering a coordinate span, like the papers in this area do.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: 1.Given the pessimistic results for unbiased compressors when τs > 0, does this imply that biased compressors (e.g., TopK) are a fundamentally better choice in practical scenarios with communication bottlenecks?
2.Can the current analysis framework be extended to provide lower bounds for biased compressors? What are the main challenges in doing so, or would a completely new approach be required?
3.How should a practitioner interpret these results when designing a distributed system? For instance, in a network with symmetric communication costs (τs ≈ τw), does your lower bound suggest that investing in the studied forms of compression is futile and methods like Batch Synchronized SGD are preferable?
soundness: 3
strengths: 1.The explicit consideration of bidirectional communication costs (τs and τw) is a powerful and novel contribution, reflecting a more realistic model of distributed systems.
2.The paper makes a significant theoretical contribution by constructing a new lower bound that clarifies the scalability limits of a specific class of optimization algorithms.
3.The construction of a novel "worst-case" function and the associated proof framework is a strong technical achievement.
summary: This paper investigates the fundamental limitations of centralized distributed optimization within the federated learning framework. It establishes a new lower bound on the time complexity for finding an ε-stationary point of smooth non-convex functions. A key aspect of the work is the explicit inclusion of bidirectional communication costs, particularly the server-to-worker  communication time. The paper reveals fundamental limitations in scaling distributed optimization.
weaknesses: 1.The paper's discussion on the practical implications of its pessimistic results for unbiased compressors is too brief. It would be significantly strengthened by a more detailed exploration of how this points to the potential superiority of biased compressors in real-world scenarios.
2.The practical takeaways for system designers and practitioners are not stated explicitly enough. The paper should offer clearer guidance on how these theoretical results should inform practical decisions (e.g., algorithm selection based on network characteristics).
3.The scope is limited to unbiased compressors, while many state-of-the-art methods use biased ones. The paper should better position itself regarding this gap between its theoretical setting and common practice.
4.The notation is dense. A table of key symbols and their definitions in the appendix would improve the paper's readability.