Improving the Worst-Case Bidirectional Communication Complexity for Nonconvex Distributed Optimization under Function Similarity

Authors: kaja  gruntkowska
alexander  tyurin kaust
skoltech ‡ peter
richtárik  kaust
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-08 11:43:42

Abstract: Effective communication between the server and workers plays a key role in distributed optimization. In this paper, we focus on optimizing communication, uncovering inefficiencies in prevalent downlink compression approaches. Considering first the pure setup where the uplink communication costs are negligible, we introduce MARINA-P, a novel method for downlink compression, employing a collection of correlated compressors. Theoretical analysis demonstrates that MARINA-P with permutation compressors can achieve a server-to-worker communication complexity improving with the number of workers, thus being provably superior to existing algorithms. We further show that MARINA-P can serve as a starting point for extensions such as methods supporting bidirectional compression: we introduce M3, a method combining MARINA-P with uplink compression and a momentum step, achieving bidirectional compression with provable improvements in total communication complexity as the number of workers increases. Theoretical findings align closely with empirical experiments, underscoring the efficiency of the proposed algorithms.

Main paper: 
 introduction: 
 In federated learning (McMahan et al., 2017; Konečný et al., 2016) and large-scale machine learning (Ramesh et al., 2021; OpenAI, 2023) , a typical environment consists of multiple devices working together to train a model. Facilitating this collaborative process requires the transmission of substantial information (e.g., gradients, current model) between these devices. In the centralized framework, communication takes place via a server. As a result, practical challenges arise due to the large size of machine learning models and network speed limitations, potentially creating a communication bottleneck (Kairouz et al., 2021; Wang et al., 2023a) . One possible strategy to reduce this communication burden is to use lossy compression (Seide et al., 2014; Alistarh et al., 2017) . Our paper focuses on this research direction.We consider the following nonconvex distributed optimization task:EQUATIONwhere x ∈ R d is the vector of parameters of the model, n is the number of workers and f i : R d → R, i ∈ [n] := {1, . . . , n} are smooth nonconvex functions. We investigate the scenario where the functions f i are stored on n distinct workers, each directly connected to the server via some communication port (Kairouz et al., 2021) . At present, we operate under the following generic assumptions: Assumption 1.1. The function f is L-smooth, i.e., ∥∇f (x) -∇f (y)∥ ≤ L ∥x -y∥ ∀x, y ∈ R d .Assumption 1.2. There exists f * ∈ R such that f (x) ≥ f * ∀x ∈ R d .In the nonconvex world, our goal is to find a (possibly) random point x such that E[∥∇f (x)∥ 2 ] ≤ ε. We refer to such a point an ε-stationary point.Before we discuss more advanced optimization methods, let us consider the simplest baseline: the gradient descent (GD) (Lan, 2020), which iteratively performs updates x t+1 = x t -γ∇f (x t ) = x tγ /n n i=1 ∇f i (x t ). In the distributed setting, the method can be implemented as follows: each worker calculates ∇f i (x t ) and sends it to the server where the gradients are aggregated, after which the server takes the step and broadcasts x t+1 back to the workers. With step size γ = 1 /L, GD finds an ε-stationary point after O δ 0 L /ε steps, where δ 0 := f (x 0 ) -f * for a starting point x 0 . Since at each step the workers and the server send Θ(d) coordinates/bits, the worker-to-server (w2s, uplink) and server-to-worker (s2w, downlink) communication costs areO dδ 0 L ε .(2)Definition 1.3. The worker-to-server (w2s) and server-to-worker (s2w) communication complexities of a method are the expected number of coordinates/floats that a worker sends to the server and that the server sends to a worker, respectively, to find an ε-solution. The total communication complexity is the sum of these complexities.Unbiased compressors. In this work, to perform lossy compression, we employ mappings from the following family: Definition 1.4. A stochastic mapping C : R d → R d is an unbiased compressor if there exists ω ≥ 0 such thatEQUATIONWe denote the family of such mappings by U(ω). A canonical example is the RandK ∈ U( d /K -1) sparsifier, which preserves K random coordinates of a vector scaled by d /K (Beznosikov et al., 2020) . More examples can be found in Wangni et al. (2018) ; Beznosikov et al. (2020) ; Szlendak et al. (2021) ; Horváth et al. (2022) . A larger family of compressors, called biased compressors, also exists (see Section B). In this paper, we implicitly assume that compressors are mutually independent across iterations of algorithms.Worker-to-server compression scales with n. Many previous works ignore the s2w communication costs and focus solely on w2s compression, assuming that broadcasting is free. For nonconvex objective functions, the current state-of-the-art w2s communication complexities are achieved by the MARINA and DASHA methods (Gorbunov et al., 2021; Szlendak et al., 2021; Tyurin and Richtárik, 2023b) . Here, two additional assumptions are needed:Assumption 1.5. The function f i is L i -smooth. We define L 2 := 1 n n i=1 L 2 i and L max := max i∈[n] L i .Assumption 1.6. For all C ∈ U(ω), all calls of C are mutually independent. 4Under Assumptions 1.1, 1.2, 1.5, 1.6, and considering the RandK compressor with K ≤ d / √ n as an example, the w2s communication complexity of both methods isEQUATIONwhere we use the facts that L ≤ L and ω = d /K -1 for RandK. The key observation is that when comparing (2) and ( 4), one sees that (4) can be √ n times smaller if L ≈ L. Consequently, the communication complexity of MARINA/DASHA scales with the number of workers n, and can provably improve the worker-to-server communication complexity O dδ 0 L /ε achieved by GD.Server-to-worker compression does not scale with n. In certain applications, the significance of s2w communication cannot be ignored. In 4G LTE and 5G networks, w2s and s2w communication speeds can be almost the same (Huang et al., 2012) or differ by at most a factor of 10 ( Narayanan et al., 2021) . Although important, this issue is often overlooked and that is why it is the s2w communication that this work places a central emphasis on.There exist many papers using communication compression techniques to reduce the s2w communication (Zheng et al., 2019; Liu et al., 2020; Philippenko and Dieuleveut, 2021; Fatkhullin et al., 2021; Gruntkowska et al., 2023; Tyurin and Richtárik, 2023a) . However, to the best of our knowledge, under Assumptions 1.1, 1.2, 1.5, and 1.6, in the worst case, all previous theoretical s2w communication guarantees are greater or equal to (2). As an example, let us consider the result from Gruntkowska et al. (2023) [Theorem E.3 ]. If the server employs operators from U(ω) and we ignore w2s compression, the method from Gruntkowska et al. (2023) converges in O (ω+1)δ 0 L /ε iterations. Thus, with RandK, the s2w communication complexity is O K × (ω+1)δ 0 L /ε = O dδ 0 L /ε . Another method, called CORE, proposed by Yue et al. (2023) , achieves s2w and w2s communication complexities equal to O r1(f )δ 0 L /ε , where r 1 (f ) is a uniform upper bound of the trace of the Hessian. When r 1 (f ) ≤ dL, CORE can improve on GD. However, this complexity does not scale with n and requires an additional assumption about the Hessian of f .As with MARINA-P, we provide the analysis of M3 under the Polyak-Łojasiewicz condition.Theorem E.8. Let Assumptions 1.1, 1.2, 1.5, 4.2 and D.9 be satisfied and suppose that the compressorsEQUATION)LettingΨ t = δ t + κ g t - 1 n n i=1 ∇f i (z t i ) 2 + η z t -w t 2 + ν 1 n n i=1 z t i -w t i 2 + ρ w t -x t 2 + τ 1 n n i=1 w t i -x t 2 , where κ = 2γ p D , η = 8γL 2 B β , ν = 8γL 2 A β + 24γω D βL 2 max np D , ρ = 128γL 2 B 1 p P + p P β 2 and τ = 128γL 2 A 1 p P + p P β 2 + 384γω D L 2 max np D (β + p P ), M3 ensures that for each T ≥ 1 E Ψ T ≤ (1 -γµ) T Ψ 0 .Corollary E.9. Let C t i ∈ P(0) for all i ∈ [n] (e.g. PermK), choose p P = 1/(ω P + 1), p D = 1/(ω D + 1) andβ = min n ω D ω P (ω D + 1) 1/3 , 1 . Then, in the view of Theorem E.8, Algorithm 2 ensures that E f (x T ) -f * ≤ ε after O   max    1+ ω D ω P (ω D +1) n 1/3 + ω D (ω D +1) n Lmax+ √ ω P (ω P +1)L A µ , ω P + 1, ω D + 1, ω D ω P (ω D +1) n 1/3    log Ψ 0 ε   iterations.Corollary E.10. Let C t i be the PermK compressors and Q t i be the independent (Assumption 1.6) RandK compressors, both with K = d /n. Then, in the view of Corollary E.9, the total communication complexity isO dL max n 1/3 µ + dL A µ + d log Ψ 0 ε .Theorem E.8. Let Assumptions 1.1, 1.2, 1.5, 4.2 and D.9 be satisfied and suppose that the compressorsEQUATION)LettingΨ t = δ t + κ g t - 1 n n i=1 ∇f i (z t i ) 2 + η z t -w t 2 + ν 1 n n i=1 z t i -w t i 2 + ρ w t -x t 2 + τ 1 n n i=1 w t i -x t 2 , where κ = 2γ p D , η = 8γL 2 B β , ν = 8γL 2 A β + 24γω D βL 2 max np D , ρ = 128γL 2 B 1 p P + p P β 2 and τ = 128γL 2 A 1 p P + p P β 2 + 384γω D L 2 max np D (β + p P ), M3 ensures that for each T ≥ 1 E Ψ T ≤ (1 -γµ) T Ψ 0 .Proof. Starting as in the proof of Theorem E.1, we haveE δ t+1 + κE   g t+1 - 1 n n i=1 ∇f i (z t+1 i ) 2   + ηE z t+1 -w t+1 2 + νE 1 n n i=1 z t+1 i -w t+1 i 2 + ρE w t+1 -x t+1 2 + τ E 1 n n i=1 w t+1 i -x t+1 2 ≤ E δ t - γ 2 E ∇f (x t ) 2 - 1 2γ - L 2 E x t+1 -x t 2 + γE   g t - 1 n n i=1 ∇f i (z t i ) 2   + 2γL 2 A 1 n n i=1 E z t i -w t i 2 + E w t i -x t 2 + 2γL 2 B E z t -w t 2 + E w t -x t 2 + κ ω D L 2 max n 4p P β 2 E 1 n n i=1 w t i -x t 2 + 3β 2 E 1 n n i=1 z t i -w t i 2 + 3(ω P + 1)β 2 E x t+1 -x t 2 + κ(1 -p D )E   g t - 1 n n i=1 ∇f i (z t i ) 2   + η 1 - β 2 E z t -w t 2 + 4 1 β + θ E x t+1 -x t 2 + 4p P 1 + p P β E w t -x t 2 + ν 1 - β 2 E 1 n n i=1 z t i -w t i 2 + 4 1 β + ω P E x t+1 -x t 2 + 4p P 1 + p P β E 1 n n i=1 w t i -x t 2 + ρ(1 -p P ) E w t -x t 2 + θE x t+1 -x t 2 + τ (1 -p P ) E 1 n n i=1 w t i -x t 2 + ω P E x t+1 -x t 2for some κ, η, ν, ρ, τ ≥ 0. This time, we let κ = 2γ p D and η =8γL 2 B β , which gives γ + κ(1 -p D ) = κ 1 -p D 2 and 2γL 2 B + η(1 -β /2) = η 1 -β 4 . Hence E δ t+1 + κE   g t+1 - 1 n n i=1 ∇f i (z t+1 i ) 2   + ηE z t+1 -w t+1 2 + νE 1 n n i=1 z t+1 i -w t+1 i 2 + ρE w t+1 -x t+1 2 + τ E 1 n n i=1 w t+1 i -x t+1 2 ≤ E δ t - γ 2 E ∇f (x t ) 2 - 1 2γ - L 2 E x t+1 -x t 2 + κ 1 - p D 2 E   g t - 1 n n i=1 ∇f i (z t i ) 2   + η 1 - β 4 E z t -w t 2 + 2γL 2 A 1 n n i=1 E z t i -w t i 2 + E w t i -x t 2 + 2γL 2 B E w t -x t 2 + 2γ p D ω D L 2 max n 4p P β 2 E 1 n n i=1 w t i -x t 2 + 3β 2 E 1 n n i=1 z t i -w t i 2 + 3(ω P + 1)β 2 E x t+1 -x t 2 + 8γL 2 B β 4 1 β + θ E x t+1 -x t 2 + 4p P 1 + p P β E w t -x t 2 + ν 1 - β 2 E 1 n n i=1 z t i -w t i 2 + 4 1 β + ω P E x t+1 -x t 2 + 4p P 1 + p P β E 1 n n i=1 w t i -x t 2 + ρ (1 -p P )E w t -x t 2 + θE x t+1 -x t 2 + τ (1 -p P )E 1 n n i=1 w t i -x t 2 + ω P E x t+1 -x t 2 .Rearranging the termsE δ t+1 + κE   g t+1 - 1 n n i=1 ∇f i (z t+1 i ) 2   + ηE z t+1 -w t+1 2 + νE 1 n n i=1 z t+1 i -w t+1 i 2 + ρE w t+1 -x t+1 2 + τ E 1 n n i=1 w t+1 i -x t+1 2 ≤ E δ t - γ 2 E ∇f (x t ) 2 - 1 2γ - L 2 E x t+1 -x t 2 + κ 1 - p D 2 E   g t - 1 n n i=1 ∇f i (z t i ) 2   + η 1 - β 4 E z t -w t 2 + ν 1 - β 2 + 2γL 2 A + 6γω D β 2 L 2 max np D E 1 n n i=1 z t i -w t i 2 + 6γω D (ω P + 1)β 2 L 2 max np D + ρθ + 32γL 2 B β 1 β + θ + 4ν 1 β + ω P + τ ω P E x t+1 -x t 2 + ρ(1 -p P ) + 2γL 2 B + 32γL 2 B p P β 1 + p P β E w t -x t 2 + τ (1 -p P ) + 2γL 2 A + 4νp P 1 + p P β + 8γω D p P β 2 L 2 max np D E 1 n n i=1 w t i -x t 2 .Considering the coefficient of E ∥w t -x t ∥ 2 and using the inequality xy ≤ x 2 +y 2 2 for all x, y ≥ 0, we getρ(1 -p P ) + 2γL 2 B + 32γL 2 B p P β 1 + p P β ≤ ρ(1 -p P ) + 32γL 2 B 1 + p P β + p 2 P β 2 ≤ ρ(1 -p P ) + 64γL 2 B 1 + p 2 P β 2 = ρ 1 - p P 2 ,where we define ρ = 128γL 2 B 1 p P + p P β 2 . Substituting this choice of ρ, we obtainE δ t+1 + κE   g t+1 - 1 n n i=1 ∇f i (z t+1 i ) 2   + ηE z t+1 -w t+1 2 + νE 1 n n i=1 z t+1 i -w t+1 i 2 + ρE w t+1 -x t+1 2 + τ E 1 n n i=1 w t+1 i -x t+1 2 ≤ E δ t - γ 2 E ∇f (x t ) 2 - 1 2γ - L 2 E x t+1 -x t 2 + κ 1 - p D 2 E   g t - 1 n n i=1 ∇f i (z t i ) 2   + η 1 - β 4 E z t -w t 2 + ρ 1 - p P 2 E w t -x t 2 + ν 1 - β 2 + 2γL 2 A + 6γω D β 2 L 2 max np D E 1 n n i=1 z t i -w t i 2 + 6γω D (ω P + 1)β 2 L 2 max np D + 128γL 2 B 1 p P + p P β 2 θ + 32γL 2 B β 1 β + θ + 4ν 1 β + ω P + τ ω P E x t+1 -x t 2 + τ (1 -p P ) + 2γL 2 A + 4νp P 1 + p P β + 8γω D p P β 2 L 2 max np D E 1 n n i=1 w t i -x t 2 .Similarly, taking ν =8γL 2 A β + 24γω D βL 2 max np D gives ν 1 -β 2 + 2γL 2 A + 6γω D β 2 L 2 max np D = ν 1 -β 4 , so E δ t+1 + κE   g t+1 - 1 n n i=1 ∇f i (z t+1 i ) 2   + ηE z t+1 -w t+1 2 + νE 1 n n i=1 z t+1 i -w t+1 i 2 + ρE w t+1 -x t+1 2 + τ E 1 n n i=1 w t+1 i -x t+1 2 ≤ E δ t - γ 2 E ∇f (x t ) 2 - 1 2γ - L 2 E x t+1 -x t 2 + κ 1 - p D 2 E   g t - 1 n n i=1 ∇f i (z t i ) 2   + η 1 - β 4 E z t -w t 2 + ρ 1 - p P 2 E w t -x t 2 + ν 1 - β 4 E 1 n n i=1 z t i -w t i 2 + 6γω D (ω P + 1)β 2 L 2 max np D + 128γL 2 B 1 p P + p P β 2 θ + 32γL 2 B β 1 β + θ + 4 8γL 2 A β + 24γω D βL 2 max np D 1 β + ω P + τ ω P E x t+1 -x t 2 + τ (1 -p P ) + 2γL 2 A + 4 8γL 2 A β + 24γω D βL 2 max np D p P 1 + p P β + 8γω D p P β 2 L 2 max np D E 1 n n i=1 w t i -x t 2 .Considering the last bracket, we haveEQUATION)where the last bracket can be bounded asI := 6γω D (ω P + 1)β 2 L 2 max np D + 128γL 2 B 1 p P + p P β 2 θ + 32γL 2 B β 1 β + θ + 4 8γL 2 A β + 24γω D βL 2 max np D 1 β + ω P + 128γω P L 2 A 1 p P + p P β 2 + 384γω D ω P L 2 max np D (β + p P ) = 6γω D (ω P + 1)β 2 np D + 96γω D β np D 1 β + ω P + 384γω D ω P np D (β + p P ) L 2 max + 32γ β 1 β + ω P + 128γω P 1 p P + p P β 2 L 2 A + 128γ 1 p P + p P β 2 θ + 32γ β 1 β + θ L 2 B = 6γω D (ω P + 1)β 2 np D + 96γω D np D + 96γω D ω P β np D + 384γω D ω P β np D + 384γω D ω P p P np D L 2 max + 32γ β 2 + 32γω P β + 128γω P p P + 128γω P p P β 2 L 2 A + 128γθ p P + 128γp P θ β 2 + 32γ β 2 + 32γθ β L 2 B . (35) We next consider the coefficients of L 2 B , L 2 A and L 2 max . First, for L 2 B , we have 128γθ p P + 128γp P θ β 2 + 32γ β 2 + 32γθ β ≤ 128γ θ p P 1 + p P β + p 2 P β 2 + 1 β 2 ≤ 256γ θ p P + θp P β 2 + 1 β 2 = 256γ θ p P + 1 + θp P β 2 .Next, the coefficient of L 2 A can be bounded as 32γβ 2 + 32γω P β + 128 p P + 128γω P p P β 2 ≤ 128γ 1 β 2 + ω P p P 1 + p P β + p 2 P β 2 ≤ 256γ ω P p P + ω P p P β 2 + 1 β 2 ≤ 256γ ω P p P + 1 + ω P p P β 2 ,and for L 2 max we obtain6γω D (ω P + 1)β 2 np D + 96γω D np D + 96γω D ω P β np D + 384γω D ω P β np D + 384γω D ω P p P np D ≤ 384γω D (ω P + 1)β 2 np D + 1 np D + ω P β np D + ω P p P np D ≤ 768γω D 1 np D + ω P β np D + ω P p P np D = 768γ ω D ω P β np D + ω D (1 + ω P p P ) np D since (ω P +1)β 2 np D ≤ 1 np D + ω P β np D .Substituting these inequalities to (34) and ( 35), we getE δ t+1 + κE   g t+1 - 1 n n i=1 ∇f i (z t+1 i ) 2   + ηE z t+1 -w t+1 2 + νE 1 n n i=1 z t+1 i -w t+1 i 2 + ρE w t+1 -x t+1 2 + τ E 1 n n i=1 w t+1 i -x t+1 2 ≤ E δ t - γ 2 E ∇f (x t ) 2 - 1 2γ - L 2 E x t+1 -x t 2 + κ 1 - p D 2 E   g t - 1 n n i=1 ∇f i (z t i ) 2   + η 1 - β 4 E z t -w t 2 + ρ 1 - p P 2 E w t -x t 2 + ν 1 - β 4 E 1 n n i=1 z t i -w t i 2 + τ 1 - p P 2 E 1 n n i=1 w t i -x t 2 + 768γ θ p P + 1 + θp P β 2 L 2 B + ω P p P + 1 + ω P p P β 2 L 2 A + ω D ω P β np D + ω D (1 + ω P p P ) np D L 2 max E x t+1 -x t 2 .By collecting all the terms w.r.t. E x t+1 -x t 2 , using the step size γ from the theorem and Lemma H.2, we obtainE Ψ t+1 = E δ t+1 + κE   g t+1 - 1 n n i=1 ∇f i (z t+1 i ) 2   + ηE z t+1 -w t+1 2 + νE 1 n n i=1 z t+1 i -w t+1 i 2 + ρE w t+1 -x t+1 2 + τ E 1 n n i=1 w t+1 i -x t+1 2 ≤ E δ t - γ 2 E ∇f (x t ) 2 + κ 1 - p D 2 E   g t - 1 n n i=1 ∇f i (z t i ) 2   + η 1 - β 4 E z t -w t 2 + ρ 1 - p P 2 E w t -x t 2 + ν 1 - β 4 E 1 n n i=1 z t i -w t i 2 + τ 1 - p P 2 E 1 n n i=1 w t i -x t 2 .Lastly, Assumption D.9 givesE Ψ t+1 = E δ t+1 + κE   g t+1 - 1 n n i=1 ∇f i (z t+1 i ) 2   + ηE z t+1 -w t+1 2 +νE 1 n n i=1 z t+1 i -w t+1 i 2 + ρE w t+1 -x t+1 2 +τ E 1 n n i=1 w t+1 i -x t+1 2Ass.D.9,( 33)≤ (1 -γµ) E δ t + κ (1 -γµ) E   g t - 1 n n i=1 ∇f i (z t i ) 2   +η (1 -γµ) E z t -w t 2 + ν (1 -γµ) E 1 n n i=1 z t i -w t i 2 +ρ (1 -γµ) E w t -x t 2 + τ (1 -γµ) E 1 n n i=1 w t i -x t 2 = (1 -γµ) E Ψ tIt remains to apply the last inequality iteratively to finish the proof.Corollary E.9. Let C t i ∈ P(0) for all i ∈ [n] (e.g. PermK), choose p P = 1/(ω P + 1), p D = 1/(ω D + 1) andβ = min n ω D ω P (ω D + 1) 1/3 , 1 .Then, in the view of Theorem E.8, Algorithm 2 ensures thatE f (x T ) -f * ≤ ε after O   max    1+ ω D ω P (ω D +1) n 1/3 + ω D (ω D +1) n Lmax+ √ ω P (ω P +1)L A µ , ω P + 1, ω D + 1, ω D ω P (ω D +1) n 1/3    log Ψ 0 ε   iterations.Proof. Note that Ψ T ≥ f (x T ) -f * . In view of condition (33) from Theorem E.8, the step size satisfiesγ = Θ min    L + θ p P + 1 + θp P β 2 L 2 B + ω P p P + 1 + ω P p P β 2 L 2 A + ω D ω P β np D + ω D (1 + ω P p P ) np D L 2 max -1 , p P 2µ , p D 2µ , β 4µ .Therefore, since θ = 0, the algorithm converges afterT = O   max    L+ 1 β 2 L 2 B + ω P p P + 1+ω P p P β 2 L 2 A + ω D ω P β np D + ω D (1+ω P p P ) np D L 2 max µ , 1 p P , 1 p D , 1 β    log Ψ 0 ε   iterations.Using the choice of p P and p D , we have T = O   max    L+ 1 β 2 (L 2 B +L 2 A )+ω P (ω P +1)L 2 A + ω D (ω D +1)ω P β n + ω D (ω D +1) n L 2 max µ , ω P + 1, ω D + 1, 1 β    log Ψ 0 ε   .The experiments were prepared in Python. The distributed environment was emulated on a machine with Intel(R) Xeon(R) Gold 6226R CPU @ 2.90GHz and 64 cores.We consider close-to-homogeneous quadratic optimization problem with A i = (1 + ξ i )I d , where ξ i ∼ N (0, 0.01) for all i ∈ [n], and d = 1000. We run two algorithms from Table 1 , M3 and CORE, and check whether theory matches practice. In M3, we use PermK followed by the natural compressor C nat (Horváth et al., 2022) (composition of two unbiased compressors) on the server's side, and RandK followed by C nat on the workers' side. We use K = ⌊d/n⌋ ∈ {1, 10, 100} for n ∈ {1000, 100, 10}. In CORE, the number of communicated coordinates is set to 10. We run each experiment 5 times with different seeds and plot the average to reduce the noise factor. Only the step size is fine-tuned for each algorithm.The results are presented in Figure 2 . As expected, CORE does not change its behavior as the number of workers increases from 10 to 100; this is expected since CORE does not depend on n. At the same time, M3 does improve with n, which supports our findings from Theorem 5.1.We now compare MARINA-P, M3, CORE, EF21-P + DCGD, and GD on a non-convex autoencoder problem. We train it on the MNIST dataset (LeCun et al., 2010) with objective function f (D, E) :=1 m m i=1 ∥DEb i -b i ∥ 2 + λ 2 ∥DE -I∥ 2 F , where D ∈ R d1×d2 , E ∈ R d2×d1 , b i ∈ R d1 are samples,d 1 = 784 is the number of features, d 2 = 16 is the size of the encoding space, λ = 0.001 is a regularizer, and m = 60 000 is the number of samples. The dimension of the problem is d = 25 088.We randomly split the dataset among n = 100 workers. For MARINA-P and M3, we take PermK followed by the natural compressor C nat on the server's side. On the workers' side, M3 uses RandK and C nat . For EF21-P + DCGD, we take RandK with C nat on both the workers' and server's sides. In each case, K = ⌊d/n⌋ = 250. For CORE, we set the number of communicated coordinates to 100.As in previous experiments, we only fine-tune the step size, repeat each experiment 5 times, and plot the average results.The results are presented in Figure 3 . All methods with bidirectional compression: M3, CORE, and EF21-P + DCGD, converge much faster than GD. MARINA-P converges fastest only in the first plot. This is expected since it compresses only from the server to the workers. M3, CORE, and EF21-P + DCGD have similar convergence rates in both metrics, with M3 performing better in the low accuracy regime.The aim of this set of experiments is to empirically test our results under Assumption 4.2. We consider the problem of quadratic minimization with varying level of heterogeneity between the n functions stored on the workers. The goal is to minimize the squared norm of the gradient of n i=1 f i , where the functions f i are of formf i (x) = 1 2 x T A i x + b T i x.Here, A i are d × d matrices generated following the procedure in Algorithm 3, and b i denotes a standard normal vector in R d . The constants L A and L B from Assumption 4.2 (in this case, by Theorem 4.8L A = √ 2 max i∈[n] ∥A i -A∥ and L B = √ 2 1 n n i=1 ∥A i ∥) are controlled by parameters v i and σ 2 i . In particular, for σ 2 i = 0, all workers hold the same matrix A i , and hence in this case L A = 0.We compare the following algorithms:1. MARINA-P with PermK compressors, 2. MARINA-P with RandK compressors, 3. MARINA-P with SameRandK compressor, 4. EF21-P with TopK compressor, 5. GD.In all compressed methods, we set K = d /n and use p = k /d in MARINA-P.The step sizes are tuned from 2 i , i ∈ Z multiples of the values predicted by the theory (indicated by ×1, ×2, . . . in the plots). We fix d = 300 and generate optimization tasks with n ∈ {10, 100, 900}. The results are presented in Figures 4, 5, 6 .The empirical results align well with the theory. Among the algorithms tested, MARINA-P with PermK compressor exhibits the best performance, while MARINA-P with SameRandK converges the slowest and comparable to GD. MARINA-P with RandK compressor and EF21-P achieve performance levels somewhere in between. Notably, the differences between the runs of MARINA-P with different compressors become more pronounced as the value of n increases. As anticipated, the performance of MARINA-P with RandK and PermK compressors improves with an increase in the number of workers, while the performance of EF21-P does not follow the same behaviour. Specifically, for n = 10, EF21-P outperforms MARINA-P with RandK compressor, but this pattern reverses for both n = 100 and n = 1000.Algorithm 3 Heterogeneous quadratic problem generation1: Parameters: v 0 , . . . , v 4 ∈ R + , σ 0 , . . . , σ 4 ∈ R ≥0 . 2: Let X = 1 4      2 -1 0 -1 . . . . . . . . . . . . -1 0 -1 2      ∈ R 300×300 , 3: for k = 0, . . . , 4 do 4: Generate ξ i ∼ N (0, σ 2 k ) ∩ [-v 0 , v 0 ] for i ∈ [n]5:for l = 0, . . . , 4 do6: Set A k,l i = (v l + ξ i )X for i ∈ [n] 7: Sample b k,l i ∼ N (0, I d ) for i ∈ [n] 8:end for 9: Output: matrices A k,l i , vectors b k,l i , i ∈ [n], k, l ∈ [4].f(x t ) 2 f(x 0 ) 2 L 2 A = 1, L 2 B =f(x t ) 2 f(x 0 ) 2 L 2 A = 1, L 2 B =f(x t ) 2 f(x 0 ) 2 L 2 A = 1, L 2 B =f(x t ) 2 f(x 0 ) 2 L 2 A = 0, L 2 B = 100, n=100, d=300EQUATIONEQUATIONEQUATIONEQUATIONf(x t ) 2 f(x 0 ) 2 L 2 A = 10, L 2 B = 100, n=100, d=300EQUATIONf(x t ) 2 f(x 0 ) 2 L 2 A = 100, L 2 B = 100, n=100, d=300EQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONf(x t ) 2 f(x 0 ) 2 L 2 A = 100, L 2 B = 100000, n=900, d=300EQUATIONwhere 2022)). The function F T satisfies:Ψ(x) = 0, x ≤ 1/2, exp 1 - 1 (2x-1) 2 , x ≥ 1/2,1. F T (0) -inf x∈R T F T (x) ≤ ∆ 0 T, where ∆ 0 = 12.2. The function F T is l 1 -smooth, where l 1 = 152. 
contributions: 
 In our work, we aim to investigate whether the server-to-worker and total communication complexities (2) of the vanilla GD method can be improved. We make the following contributions:1. We start by proving the impossibility of devising a method where the server communicates with the workers using unbiased compressors U(ω) (or biased compressors from Section B) and achieves an iteration rate faster than Ω (ω+1)Lδ 0 /ε (Theorem 3.1) under Assumptions 1.1, 1.2 and 1.6. This result provides a lower bound for any method that applies such compressors to vectors sent from the server to the workers in every iteration. Moreover, we prove a more general iteration lower bound of Ω (ω+1)Lδ 0 /ε for all methods where the server zeroes out a coordinate with probability 1 /(ω+1) (see Remark 3.2).2. In view of this result, it is clear that an extra assumption is needed to break the lower bound Ω (ω+1)Lδ 0 /ε . In response, we introduce a novel assumption termed "Functional (L A , L B ) Inequality" (see Assumption 4.2). We prove that this assumption is relatively weak and holds, for instance, under the local smoothness of the functions f i (see Assumption 1.5).3. We develop a new method for downlink compression, MARINA-P, and show that under our new assumption, along with Assumptions 1.1 1.2, and 1.6, it can achieve the iteration rate ofO δ 0 L ε + δ 0 L A (ω+1) ε + δ 0 L B (ω+1) √ nε(see Theorem D.1 with p = 1 /(ω+1) + Lemma A.5). Notably, when L A is small and n ≫ 1, this complexity is provably superior to Θ( (δ 0 L(ω+1)) /ε) and the complexities of the previous compressed methods. In this context, L A serves as a measure of the similarity between the functions f i , and can be bounded by the "variance" of the Hessians of the functions f i (see Theorem 4.8). Thus, MARINA-P is the first method whose iteration complexity can provably improve with the number of workers n.4. Moreover, MARINA-P can achieve the s2w communication complexity ofO dδ 0 L nε + dδ 0 L A ε .When L A is small and n ≫ 1, this communication complexity is provably superior to (2) and the communication complexities of the previous compressed methods.5. Our theoretical improvements can be combined with techniques enhancing the w2s communication complexities. In particular, by combining MARINA-P with MARINA (Gorbunov et al., 2021) and adding the crucial momentum step, we develop a new method, M3, that guarantees a total communication complexity (s2w + w2s) ofO dδ 0 Lmax n 1/3 ε + dδ 0 L A ε .When n ≫ 1 and in the close-to-homogeneous regime, i.e., when L A is small, this complexity is better than (2) and the complexities of the previous bidirectionally compressed methods.6. Our theoretical results are supported by numerical experiments (see Section F). 
lower bound under smoothness: 
 Let us first investigate the possibility of improving the iteration complexity O (ω+1)δ 0 L /ε under Assumptions 1.1,1.2 and 1.6. In Section G, we consider a family of methods that include those proposed in Zheng et al. (2019) ; Liu et al. (2020) ; Philippenko and Dieuleveut (2021) ; Fatkhullin et al. (2021) ; Gruntkowska et al. (2023) , where the server communicates with workers using unbiased/biased compressors, and establish that Theorem 3.1 (Slightly Less Formal Reformulation of Theorem G.5). Under Assumptions 1.1, 1.2 and 1.6, all methods in which the server communicates with clients using different and independent unbiased compressors from U (ω) and sends one compressed vector to each worker cannot converge before Ω (ω+1)Lδ 0 /ε iterations.Remark 3.2. The theorem remains applicable to biased compressors B (α) (see Section B) with a lower bound of Θ Lδ 0 /αε . This is because if C ∈ U(ω), then (ω + 1) -1 C ∈ B (ω + 1) -1 . We also establish a more general result (Theorem G.4): "all methods in which the server zeroes out a coordinate with probability ≤ p independently across iterations cannot converge before Ω Lδ 0 /pε iterations."This lower bound is tight up to a constant factor. For instance, under exactly the same assumptions, the EF21-P mechanism from Gruntkowska et al. (2023) converges after Θ (ω+1)Lδ 0 /ε iterations. Unlike (4), this convergence rate does not scale with n, and Theorem 3.1 leaves no room for improvement. Consequently, breaking the lower bound requires an additional assumption about the structure of the problem. Before presenting our candidate assumption, we first introduce the ingredients needed to leverage it to the fullest extent: our novel downlink compression method and the type of compressors we shall employ.x ∈ R T , ∥∇F T (x)∥ ∞ ≤ γ ∞ , where γ ∞ = 23. 4. For all x ∈ R T , prog(∇F T (x)) ≤ prog(x) + 1. 5. For all x ∈ R T , if prog(x) < T, then ∥∇F T (x)∥ > 1, where prog(x) := max{i ≥ 0 | x i ̸ = 0} (x 0 ≡ 1).The function is a standard function that is used to establish lower bounds in the nonconvex world (Carmon et al., 2020; Arjevani et al., 2022; Lu and De Sa, 2021; Tyurin and Richtárik, 2023c) .Our lower bound applies to the family of methods with the following structure:Protocol 4 Protocol 1: Input: functions f 1 , . . . , f n ∈ F, algorithm A, probability p 2: for k = 0, . . . , ∞ do 3:Server calculates a new point:x k = B k 1 (g 1 1 , . . . , g k 1 , . . . , g 1 n , . . . , g k n ) 4:Server aggregates all available information:s k i = B k 2,i (g 1 1 , . . . , g k 1 , . . . , g 1 n , . . . , g k n ) 5:Server sends sparsified vectors sk i to the workers, where[s k i ] j = [s k i ] j × η k i,j ,and η k i,j is a random variable such that P η k i,j ̸ = 0 ≤ p for all j ∈ [d ′ ] and for all i ∈ [n]. We define d ′ := dim(dom(f 1 )), and [•] j means the j th coordinate.Workers aggregate all available local information and calculate gradients:g k+1 i = L k i (s 0 i , . . . , sk i ) (L ki has access to the gradient oracle of f i and can call it as many times as it wants according to the rules (37) and (38)) 7:Workers send g k+1 i to the server 8: end for We consider the following standard classes of functions and algorithms: Definition G.2. Let the function f : R d → R be differentiable, L-smooth (i.e., ∥∇f (x) -∇f (y)∥ ≤ L ∥x -y∥ for all x, y ∈ R d ), and f (0) -inf x∈R d f (x) ≤ δ 0 . We denote the family of functions that satisfy these properties by F δ 0 ,L . Definition G.3. Consider Protocol 4.EQUATIONwe haveEQUATIONfor all k ∈ N 0 and for all i ∈ [n], where supp(x):= {i ∈ [d] | x i ̸ = 0}.We denote the set of all algorithms that satisfy these properties by A zr .The first three properties define the domains of the mapping. The last property is a standard assumption for a zero-respecting algorithm. Assumption (38) allows the mappings L k i to calculate gradients. Theorem G.4. Consider Protocol 4.Assume that the sets {η 0 i,j } i∈[n],j∈[d ′ ] , {η 1 i,j } i∈[n],j∈[d ′ ] , . . . , {η k i,j } i∈[n],j∈[d ′ ] , . . . are mutually independent (the variables within one set can be dependent). Let p > 0, L, δ 0 , ε > 0, n ≥ 2 be any numbers such that cε < Lδ 0 . Then, for any algorithm A ∈ A zr , there exists a function f ∈ F δ 0 ,L and functions f 1 , . . . , f n such that f i (x) := nLλ 2 l 1 F i x λ .The idea is that we take the first block from (36) to the first worker, the second block to the second worker, . . . , (n + 1) th block to the first worker, and so on. Then, one can show that1 n n i=1 f i (x) = f (x).Using Lemma G.1, we obtainEQUATIONThe functions f i are zero-chain (Arjevani et al., 2022) : for all i ∈ [n], if prog(x) = j and (j mod n)+ 1 = i, then prog(∇f i (x)) ≤ j + 1, and for all i ∈ [n], if prog(x) = j and (j mod n) + 1 ̸ = i, then prog(∇f i (x)) ≤ j. Using the zero-chain property and the fact that we consider the family of zero-respecting algorithms:1. The first non-zero coordinate can be discovered only by the first worker.2. Assume that max k j=1 max n i=1 prog g j i = j ≥ 1. An algorithm can discover one new non-zero coordinate in the (j + 1) th position only if the (j mod n + 1) th worker gets a non-zero j th coordinate from the server. This is by the construction of the functions f i . Note that for n ≥ 2, one worker cannot discover two consecutive coordinates.Let us define Then, we haveP prog(x k ) ≥ T ≤ P   k-1 j=0 ξ j ≥ T -1   .Assume that G j is the σ-algebra generated by all randomness up to the j th iteration (inclusive). Then, ξ j is G j -measurable, and, by the construction of Line 5 of Protocol 4, P ξ j+1 = 1 G j ≤ p, where we also use the assumption of the theorem that the sets of random variables are mutually independent. Using the standard approach with the Chernoff method (Arjevani et al., 2022; Lu and De Sa, 2021; Huang et al., 2022) , one can show that Using (40), we haveE ∇f (x k ) 2 > 2εP ∇f (x k ) 2 > 2ε ≥ 2εP L 2 λ 2 l 2 1 1[prog(x) < T ] ≥ 2ε .Let us take λ = √ 2εl1L . ThenEQUATIONFrom ( 41) with ρ = 1 2 , we getE ∇f (x k ) 2 > 2εP (prog(x) < T ) ≥ ε (43) for all k ≤ T -1 -log 2 2p .From (39), one can conclude that T = Lδ 0 l 1 2εl 2 1 ∆ 0 . By the theorem's assumption, Lδ 0 ≥ cε. One can choose a universal constant c such that (42) holds fork ≤ Θ T p = Θ Lδ 0 εp ,where Θ hides only a universal constant.Protocol 5 is exactly the same as Protocol 4 except for Line 5 and describes the family of methods that send compressed vectors from the server to the workers.Protocol 5 Protocol with Compressors 1: Input: functions f 1 , . . . , f n ∈ F, algorithm A, compressors C 1 , . . . , C n 2: for k = 0, . . . , ∞ do 3:Server calculates a new point: x k = B k 1 (g 1 1 , . . . , g k 1 , . . . , g 1 n , . . . , g k n )4:Server aggregates all available information: s k i = B k 2,i (g 1 1 , . . . , g k 1 , . . . , g 1 n , . . . , g k n )5:Server sends compressed vectors sk i = C i (s k i ) to the workers 6:Workers aggregate all available local information and calculate gradients:g k+1 i = L k i (s 0 i , . . . , sk i ) (L ki has access to the gradient oracle of f i and can call it as many times as it wants according to the rules (37) and ( 38)) 7:Workers send g k+1 i to the server 8: end for Theorem G.5. Consider Protocol 5. Let ω ≥ 0, L, δ 0 , ε > 0, n ≥ 2 be any numbers such that cε < Lδ 0 . Then for any algorithm A ∈ A zr , there exists a function f ∈ F δ 0 ,L , functions f 1 , . . . , f n such that f = 1 n n i=1 f i , and i.i.d. compressors C 1 , . . . , C n ∈ U(ω) such that E ∇f (x k ) 2 > ε for all k ≤ ĉ (ω + 1)Lδ 0 ε .The quantities c and ĉ are universal constants.Proof. We can use the result of Theorem G.4. It is sufficient to construct an appropriate compressor. Let us define p := 1 /ω+1. We define the following compressor:[C(x)] j := 1 p x j , j ∈ S, 0, j ̸ ∈ S, ∀j ∈ [T ],where S is a random subset of [T ] and each element from [T ] appears with probability p independently. Then, C is unbiased: E S [[C(x)] j ] = x j ∀j ∈ R TFor all x, y, x 1 , . . . , x m ∈ R d , s > 0 and α ∈ (0, 1], we have:EQUATIONEQUATIONEQUATIONEQUATION)Variance decomposition: For any random vector X ∈ R d and any non-random vector c ∈ R d , we haveEQUATION)Tower property: For any random variables X and Y , we haveEQUATIONJensen's inequality: If f is a convex function and X is a random variable, thenEQUATIONLemma H.1 (Lemma 2 of Li et al. (2021) ). Suppose that function f is L-smooth and let x t+1 = x t -γg t . Then for any g t ∈ R d and γ > 0, we have • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).f (x t+1 ) ≤ f (x t ) - γ 2 ∇f (x t ) 2 - 1 2γ - L 2 x t+1 -x t 2 + γ 2 g t -∇f (x t ) 2 . 
the marina-p method: 
 Let us first recall the MARINA method (Gorbunov et al., 2021; Szlendak et al., 2021) :EQUATIONwhere g 0 = ∇f (x 0 ). Motivated by MARINA, we design its primal counterpart, MARINA-P (Algorithm 1), operating in the primal space of the model parameters, as outlined in (6).At each iteration of MARINA-P, the workers calculate ∇f i (w t i ) and transmit it to the server. The server then averages the gradients and updates the global model x t . Subsequently, with some (typically small) probability p, the master sends the non-compressed vector x t+1 to all workers. Otherwise, the i th worker receives a compressed vector C t i (x t+1 -x t ). Each worker then uses the received message to compute w t+1 i locally. Importantly, C t 1 (x t+1 -x t ), . . . , C t n (x t+1 -x t ) can differ, and this distinction will form the basis of our forthcoming advancements.The MARINA-P Method: Initialize vectors x 0 , w 0 1 , . . . , w 0 n ∈ R d , step size γ > 0, probability 0 < p ≤ 1 and compressors C t 1 , . . . , C t n ∈ U(ω P ) for all t ≥ 0. The method iteratesg t = 1 n n i=1 ∇f i (w t i ), x t+1 = x t -γg t , c t ∼ Bernoulli(p), w t+1 i = x t+1 if c t = 1, w t i + C t i (x t+1 -x t ) if c t = 0 for all i ∈ [n]. (6)We denote w t := 1 /n n i=1 w t i . See the implementation in Algorithm 1.Comparing ( 5) and ( 6), MARINA-P and MARINA are dual methods: both learn control variables (w t i and g t i ), compress the differences (x t+1 -x t and ∇f i (x t+1 ) -∇f i (x t )), and with some probability p send non-compressed vectors (x t+1 and ∇f i (x t+1 )). However, unlike MARINA, which compresses vectors sent from workers to server and operates in the dual space of gradients, MARINA-P compresses messages sent from server to workers and operates in the primal space of arguments.Let us take RandK ∈ U( d /K -1) as an example. If we set p = (ω + 1)-1 = K /d to balance heavy communications of x t+1 and light communications of C t i in (6), MARINA-P averages sending pd + (1 -p)K ≤ 2K coordinates per iteration. Then, the lower bound from Theorem G.4 implies that at least Ω (ω+1)δ 0 L /ε iterations of the algorithm are needed.At first glance, it seems that MARINA-P does not offer any extra benefits compared to previous methods, and that is true -we could not expect to break the lower bound. However, as we shall soon see, under an extra assumption, MARINA-P can achieve a communication complexity that improves with n.Existing algorithms performing s2w compression share a common characteristic: at each iteration, the server broadcasts the same message to all workers (Zheng et al., 2019; Liu et al., 2020; Fatkhullin et al., 2021; Gruntkowska et al., 2023; Tyurin and Richtárik, 2023a) . 5 In contrast, in w2s compression methods, each worker sends to the server a different message, specific to the data stored on that particular device. An analogous approach can be taken in the s2w communication: intuitively, sending n distinct messages would convey more information, potentially leading to theoretical improvements. This indeed proves to be the case. While the usual approach of the server broadcasting the same vector to all clients does not lead to an improvement over (2), allowing these vectors to differ enables a well-crafted method to achieve communication complexity that improves with n (see Corollary D.4).In Appendix A we provide a detailed discussion of the topic and compare the theoretical complexities of MARINA-P when the server employs three different compression techniques: a) uses one compressor and sends the same vector to all clients, b) uses a collection of independent compressors, or c) uses a collection of correlated compressors. We now turn to presenting the technique that gives the best theoretical s2w communication complexity out of these, namely the use of a set of correlated compressors. et al. (2021) propose compressors that will play a key role in our new theory. For clarity of presentation, we shall assume that d ≥ n and n|d.6 Definition 4.1 (PermK (for d ≥ n and n|d)). Assume that d ≥ n and d = qn, where q ∈ N >0 . Let π = (π 1 , . . . , π d ) be a random permutation of {1, . . . , d}. For all x ∈ R d and each i ∈ {1, 2, . . . , n}, we defineC i (x) := n × qi j=q(i-1)+1x πj e πj .Unpacking this definition: when the server compresses a vector using a PermK compressor, it randomly partitions its coordinates across the workers, so that each client receives a sparse vector containing a random subset of entries of the input vector. Like RandK, PermK is also a sparsifier. However, unlike RandK, it does not allow flexibility in choosing K, as it is fixed to d /n. Furthermore, it can be shown (Lemma A.6) that C i ∈ U(n -1) for all i ∈ [n].An appealing property of PermK is the fact that1 n n i=1 C i (x) = x (7)for all x ∈ R d deterministically. Here, it is important to note that by design, compressors C i from Definition 4.1 are correlated, and do not satisfy Assumption 1.6. This correlation proves advantageous - Szlendak et al. (2021) show that MARINA with PermK compressors performs provably better than with i.i.d. RandK compressors.We are finally ready to present our first result showing that the s2w communication complexity can scale with the number of workers n. To explain the intuition behind our approach, let us consider the simplest (and somewhat impractical) choice of functions f i -the homogeneous quadratics:EQUATIONwhere A ∈ R d×d is a symmetric but not necessarily positive semidefinite matrix, b ∈ R d and c ∈ R.We now investigate the operation of MARINA-P with PermK compressors. With probability p, we haveEQUATION= x t+1 + (w t -x t ). Hence, if we initialize w 0 i = x 0 for all i ∈ [n], an inductive argument shows that w t = x t deterministically for all t ≥ 0. Then, substituting the gradients of f i to (6), one getsg t = 1 n n i=1 (Aw t i + b) = Aw t + b = Ax t + b = ∇f (x t )for all t ≥ 0. Therefore, MARINA-P with PermK compressor in this setting is essentially a smart implementation of vanilla GD! Indeed, for p ≤ 1 /n, MARINA-P with PermK sends on average ≤ 2d /n coordinates to each worker, so the s2w communication complexity is2d n × O δ 0 L ε GD rate = O dδ 0 L nε , which is n times smaller than in (2)! 4.4 Functional (L A , L B ) InequalityFrom the discussion in Section 3, we know that to improve (2), an extra assumption about the structure of the problem is needed. Building on the example from Section 4.3, we introduce the Functional (L A , L B ) Inequality.Table 1 : The worst case communication complexities to find an ε-stationary point. For simplicity, we compare the complexities with non-homogeneous quadratics:f i (x) = 1 2 x ⊤ A i x + b ⊤ i x + c i , where A i ∈ R d×d is symmetric but not necessarily positive semidefinite, b i ∈ R d and c i ∈ R for i ∈ [n]. We denote A = 1 n n i=1 A i .Server-to-Workers Communication Complexities (s2w)GD and other compressed methods (a) ≥ dδ 0 ∥A∥ ε CORE (Yue et al., 2023) δ 0 trA εwith independent RandK (b) (Corollary D.4)dδ 0 1 n n i=1 ∥Ai∥ √ nε + dδ 0 max i∈[n] ∥Ai-A∥ ε MARINA-P with PermK (b)(Corollary 4.7)dδ 0 ∥A∥ nε + dδ 0 max i∈[n] ∥Ai-A∥ εTotal Communication Complexities (s2w + w2s) with PermK and RandK (b) (Theorem 5.1)dδ 0 max i∈[n]∥Ai∥n 1/3 ε + dδ 0 max i∈[n]∥Ai-A∥ εThe complexities of MARINA-P and M3 with PermK are better when n > 1 and in close-to-homogeneous regimes, i.e., when max i∈[n] ∥Ai -A∥ is small. (a) including EF21-P (Gruntkowska et al., 2023) , dist-EF-SGD (Zheng et al., 2019) , DORE (Liu et al., 2020) , MCM (Philippenko and Dieuleveut, 2021) , and EF21-BC (Fatkhullin et al., 2021) . (b) This table only showcases the results for RandK and PermK. A more general result for all compressors is provided in Sections D and E.Assumption 4.2 (Functional (L A , L B ) Inequality). There exist constants L A , L B ≥ 0 such that1 n n i=1 (∇f i (x + u i ) -∇f i (x)) 2 ≤ L 2 A 1 n n i=1 ∥u i ∥ 2 + L 2 B 1 n n i=1 u i 2 (9) for all x, u 1 , . . . , u n ∈ R d .Remark 4.3. A similar assumption, termed "Heterogeneity-driven Lipschitz Condition on Averaged Gradients", is proposed in Wang et al. (2023b) . Our assumption aligns with theirs when L B = 0. However, our formulation proves to be more powerful. The possibility that L B > 0 becomes instrumental in driving the enhancements we introduce.Assumption 4.2 is defined for all functions together, and intuitively, it tries to capture the similarities between the functions f i . For n = 1, inequality (9) reduces to∥∇f (x) -∇f (y)∥ 2 ≤ L 2 A + L 2 B ∥x -y∥ 2 ∀x, y ∈ R d , equivalent to standard L-smoothness (Assumption 1.1) with L 2 = L 2 A + L 2 B .The Functional (L A , L B ) Inequality is reasonably weak also for n > 1, as the next theorem shows.Theorem 4.4. For all i ∈ [n], assume that the functions f i are L i -smooth (Assumption 1.5). Then, Assumption 4.2 holds with L A = L max and L B = 0.Therefore, Assumption 4.2 holds whenever the functions f i are smooth, which is a standard assumption in the literature. Now, returning to the example from Section 4.3, Theorem 4.5. For all i ∈ [n], assume that the functions f i are homogeneous quadratics defined in (8). Then, Assumption 4.2 holds with L A = 0 and L B = ∥A∥ .Under Assumption 1.5, no information about the similarity of the functions f i is available, yielding L B = 0 and L A > 0 in Theorem 4.4. However, once we have some information limiting heterogeneity, L A can decrease. Notably, L A = 0 for homogeneous quadratics. As we shall see in Section 4.5, the values L A and L B significantly influence the s2w communication complexity of MARINA-P, with lower L A values leading to greatly improved performance.We are ready to present our main convergence result, focusing on the PermK compressor from Section 4.2. This choice simplifies the presentation, but our approach generalizes to a much larger class of compression operators. The full theoretical framework, covering all unbiased compressors, is detailed in Appendix D.Theorem 4.6. Let Assumptions 1.1, 1.2 and 4.2 be satisfied. Setw 0 i = x 0 for all i ∈ [n]. Take PermK as C t i and γ = L + L A ω P ( 1 /p -1) -1, where ω P = n -1 (Lemma A.6). Then, MARINA-P finds an ε-stationary point afterO δ 0 ε L + L A ω P /p iterations.Corollary 4.7. Let p = K /d ≡ 1 /n. Then, in the view of Theorem 4.6, the average s2w communication complexity of MARINA-P with PermK compressor isEQUATION)The key observation is that (10) is independent of L B , and only depends on L A . This particular property is specific to correlated compressors with parameter θ = 0 (defined in Appendix A), such as PermK. A similar result holds for independent RandK compressors (see Corollary D.4), but the convergence rate is worse and depends on L B . Nevertheless, this dependence improves with n.When L A = 0, which is the case for homogeneous quadratics, the step size bound from Theorem 4.6 simplifies to γ ≤ 1 /L, the standard GD stepsize (recall that in this case our method reduces to GD).Most importantly, (10) scales with the number of workers n! Even when L A > 0, for sufficiently big n, (10) can improve (2) to O dδ 0 L A /ε .Let us now investigate how the constants L A and L B change in the general case. EQUATION)for all i ∈ [n]. Then, Assumption 4.2 holds with L A = √ 2 max i∈[n] D i ≤ 2 √ 2 max i∈[n] L i and L B = √ 2 1 n n i=1 L i .Intuitively, (11) measures the similarity between the functions f i . The above theorem yields a more refined result than Theorem 4.4: it is always true that max i∈[n] D i ≤ 2 max i∈[n] L i , and, in fact, max i∈[n] D i can be much smaller, as the next result shows.Theorem 4.9. Assume thatf i (x) = 1 2 x ⊤ A i x + b ⊤ i x + c i , where A i ∈ R d×d is symmetric but not necessarily positive semidefinite, b i ∈ R d and c i ∈ R for i ∈ [n]. Define A = 1 n n i=1 A i . Then, Assumption 4.2 holds with L A = √ 2 max i∈[n] ∥A i -A∥ and L B = √ 2 1 n n i=1 ∥A i ∥ .Thus, L A is less than or equal to √ 2 max i∈[n] ∥A i -A∥ , which serves as a measure of similarity between the matrices. The smaller the values of ∥A i -A∥ (indicating greater similarity among the functions f i ), the smaller the L A value.In the view of this theorem, the s2w communication complexity of MARINA-P with PermK on non-homogeneous quadratics isEQUATION)Since the corresponding complexity of GD isEQUATIONin the close-to-homogeneous regimes (i.e., when max i∈[n] ∥A i -A∥ is small), the complexity (12) can be provably much smaller than (13). The same reasoning applies to the general case when the The M3 Method (M3 = MARINA-P + Momentum + MARINA): Initialize vectors x 0 , w 0 i , g 0 i , z 0 i ∈ R d for all i ∈ [n], step size γ > 0, probabilities 0 < p P , p D ≤ 1 and compressors C t 1 , . . . , C t n ∈ U(ω P ) ∩ P(θ) a , Q t 1 , . . . , Q t n ∈ U(ω D ) for all t ≥ 0. The method iteratesx t+1 = x t -γg t , w t+1 i =x t+1 with probability p P ,EQUATIONwhere the probabilistic decisions are the same for all i ∈ [n], i.e., one coin is tossed for all workers (as in ( 5) and ( 6)), and the coins for the first and second probabilistic decisions with p P and p D are independent. We denotew t := 1 /n n i=1 w t i , g t := 1 /n n i=1 g t i , z t := 1 /n n i=1 z t i .See the implementation in Algorithm 2.a By P(θ) we denote a family of correlated compressors (defined in Appendix A). It includes, among others, PermK compressors. functions f i are not quadratics: MARINA-P improves with the number of workers n in the regimes when D i are small (see Theorem 4.8).Let us note that there is another method, CORE, by Yue et al. (2023) , that can also provably outperform GD, achieving the s2w communication complexity of Ω δ 0 trA /ε on non-homogeneous quadratics. Neither their method nor ours universally provides the best possible communication guarantees. Our method excels in the close-to-homogeneous regimes: for example, if we takeA i = L i I for all i ∈ [n], and define L = 1 /n n i=1 L i , then the complexity of CORE is Ω dδ 0 L /ε , while ours is O dδ 0 L nε + dδ 0 max i∈[n] |Li-L| ε. Hence, our guarantees are superior in regimes wheremax i∈[n] |L i -L| ≪ L.One interesting research direction is to develop a universally better method combining the benefits of both approaches. 
m3: a new bidirectional method: 
 In the previous sections, we introduce a new method that provably improves the server-to-worker communication, but ignores the worker-to-server communication overhead. Our aim now is to treat MARINA-P as a starting point for developing methods applicable to more practical scenarios, by combining it with techniques that compress in the opposite direction. Since the theoretical state-ofthe-art w2s communication complexity is obtained by MARINA (see Section 1.1), our next research step was to combine the two and analyze "MARINA + MARINA-P", but this naive approach did not yield communication complexity guarantees surpassing (2) in any regime. It became apparent that some "buffer" step between these two techniques is needed, and this step turned out to be the momentum. Our new method, M3 (Algorithm 2), is described in (14).M3 combines (5), (6), and the momentum stepz t+1 i = βw t+1 i + (1 -β)z t i, which is the key to our improvements. A similar technique is used to reduce the variance in Fatkhullin et al. (2023) . Let us explain how M3 works in practice. First, the server calculates x t+1 . Depending on the first probabilistic decision, it sends either x t+1 or C t i (x t+1 -x t ) to the workers, who then calculate w t+1 i locally. Next, the workers compute z t+1 i , and depending on the second probabilistic decision, they send either ∇f i (z t+1 i) or Q t i (∇f i (z t+1 i ) -∇f i (z t i ))back to the server. The server aggregates the received vectors and calculates g t+1 . As in MARINA, p P and p D are chosen in such a way that the 0.0 0.2 0.4 0.6 0.8 1.0 1.2 1.4 # bits / n (s-to-w) 1e5 non-compressed communication does not negatively affect the communication complexity. Therefore, the method predominantly transmits compressed information, with only a marginal probability of sending uncompressed vectors.For simplicity, we consider PermK in the role of C t i and RandK in the role of Q t i . The general theory for all unbiased compressors is presented in Section E.Theorem 5.1. Let Assumptions 1.1, 1.2, 1.5 and 4.2 be satisfied. Take γ = L +34 nL A + n 2/3 L B + n 2/3 L max -1 , p D = p P = 1 /n, β = n -2/3 , w 0 i = z 0 i = x 0 and g 0 i = ∇f i (x 0 ) for all i ∈ [n].Then MARINA-P with C t i =PermK and Q t i = RandK with K = d /n finds an ε-stationary point after O δ 0 ε n 2/3 L max + nL A iterations. The total communication complexity isEQUATIONOnce again, we observe improvement with the number of workers n, and the obtained complexity (15) can be provably smaller than (2). Indeed, in scenarios like federated learning, where the number of workers (e.g., mobile phones) is typically large (Kairouz et al., 2021; Chowdhery et al., 2023) , the first term can be significantly smaller than dδ 0 L /ε. The second term can also be small in close-tohomogeneous regimes (see Section 4). 
experimental highlights: 
 This section presents insights from the experiments, with further details and additional results in Appendix F. The experiment aims to empirically test the theoretical results from Section 4. We consider a quadratic optimization problem, where the functions f i are as defined in Theorem 4.9 and A i ∈ R 300×300 . We compare GD, MARINA-P sending the same message compressed using a single RandK compressor to all workers ("SameRandK" from Appendix A), MARINA-P with independent RandK compressors, MARINA-P with PermK compressors, and EF21-P with TopK compressor. We consider n ∈ {10, 100, 1000} and fine-tune the step size for each algorithm. The results, presented in Figure 1 , align closely with the theory, with MARINA-P using PermK compressors consistently performing best. Moreover, the convergence rate of MARINA-P with PermK and independent RandK compressors improves with n. Since this is not the case for EF21-P, even though it outperforms MARINA-P with independent RandK compressors for n = 10, it falls behind for n ∈ {100, 1000}. A Three unbiased ways to compressThe main focus of this paper is handling the server-to-worker communication costs. To explain better where the improvements outlined in the main part of this paper come from, let us first consider the scenario where uplink communication cost is negligible but downilnk communication cost is not. While we do no necessarily say that this is a realistic setup, examining it first enables us to understand how downlink compression should be performed, capturing all the intricacies.Existing algorithms with lossy s2w and w2s communication have a certain common feature. The compression mechanism employed on the clients is very different from the one used on the server: while each client transmits to the server a different message, specific to the data stored on each device, the server broadcasts the same update to all clients. We want to question this algorithmic step and suggest to the reader that if compression is applied multiple times and each worker receives its individual update, then intuitively more information can be transmitted. A well-designed algorithm should be able to take advantage of this.One can depart from the usual approach of sending the same update to all workers in two ways: a) compress the update n times independently, or b) produce n such updates in a correlated way.Either way, the server broadcasts n different compressed messages rather than one, and sends a different update to each worker. The key discovery here is that both a) and b) are mathematically provably better than the prevalent approach of sending the same update to all clients. This is a crucial improvement in a system where the above setup is a good approximation of reality.And even if it is not, and the current model is not perfectly capturing the reality, we can accept it for now, as it allows us to focus on the novel aspects of the approach. With that said, these considerations can serve as a starting point for thinking about bidirectional compression: having focused on the simplified setup and equipped with knowledge on how the compression on the master should be performed, we employ this mechanism in more complex scenarios (see Section 5).Let us now describe the three possible ways to perform compression on the server."Same" compressors. The prevalent approach in downlink compression is to transmit the same update to all workers. To illustrate this, let us call a collection C 1 , . . . , C n of compressors "SameRandK" if for all i ∈ [n] we have C i = C for some RandK compressor C. Now, consider one iteration t of MARINA-P with SameRandK compressor. The server calculatesC t i (x t+1 -x t ) for i ∈ [n], but in this case, C t 1 (x t+1 -x t ) = . . . = C t n (x t+1 -x t ) = C t (x t+1 -x t ).Thus, applying a collection of SameRandK compressors to some vector x ∈ R d is equivalent to using a single RandK compression operator and transmitting the same message C(x) to all workers. Independent Compressors. Rather than setting C i (x) = C(x) for all i ∈ [n], one can break the dependency between the messages and allow the compressors to differ. For illustrational purposes, suppose that C i , i ∈ [n] are independent RandK compressors (Assumption 1.6). Then, applying such a collection of mappings to the vector of interest x ∈ R d , one obtains n distinct and independent sparse vectors C 1 (x), . . . , C n (x). Remark A.1. We are aware of only one method that uses n distinct compressors in downlink compression, Rand-MCM by Philippenko and Dieuleveut (2021) . Given the absence of results in the non-convex case, let us compare the communication complexities of Rand-MCM and M3 under the Polyak-Łojasiewicz condition (Assumption D.9), which holds under strong convexity. In the strongly convex case, the proved iteration complexity of Rand-MCM isΩ L max µ ω 3/2 P + ω P ω 1/2 D √ n + ω D n log δ 0 ε .Assuming for simplicity that the server and the workers use RandK compressors with K = d /n, this gives the total communication complexity ofΩ d n × L max µ ω 3/2 P + ω P ω 1/2 D √ n + ω D n log δ 0 ε = Ω d √ nL max µ log δ 0 ε ,which is getting worse as the number of workers n increases. Meanwhile, by Corollary E.10, the total communication complexity of M3 (where C t i are the PermK compressors andQ t i are independent RandK compressors, both with K = d/n) under the Polyak-Łojasiewicz condition is O dL max n 1/3 µ + dL A µ + d log δ 0 ε .Since n is typically large, the total communication complexity of M3 can be much better than that of Rand-MCM.Correlated Compressors. In their work, Szlendak et al. (2021) introduce an alternative class of compressors, which satisfy the following condition: Definition A.2 (AB-inequality (Szlendak et al., 2021) ). There exist constants A, B ≥ 0 such that the random operators C 1 , . . .C n satisfy E [C i (x)] = x, E   1 n n i=1 C i (x i ) - 1 n n i=1 x i 2   ≤ A 1 n n i=1 ∥x i ∥ 2 -B 1 n n i=1 x i 2 (16) for all x, x 1 , . . . , x n ∈ R d . If these conditions hold, we write {C i } n i=1 ∈ U(A, B).Following on this idea, we introduce the concept of a collection of correlated compressors.). There exists a constant θ ≥ 0 such that the random operators C 1 , . . . C n satisfy:EQUATIONfor all x ∈ R d . If these conditions hold, we write {C i } n i=1 ∈ P(θ).Definition A.3 will play a key role in our upcoming advancements. But what makes this assumption reasonable?First, it is easy to note that condition ( 17) is weaker than (16). Indeed, if {C i } (u) = u + ζ u , and C 2 (u) = u -ζ u . Then 1 2 (C 1 (u) + C 2 (u)) = u, so C 1 (u) and C 2 (u) satisfy Definition A.3 with θ = 0. However, for u 1 ̸ = u 2 , by the properties of Cauchy distribution we have E 1 2 (C 1 (u) + C 2 (u)) - 1 2 (u 1 + u 2 ) 2 = E 1 2 (ζ 1 + ζ 2 ) 2 = 1 4 E ζ 2 1 + ζ 2 2 + 2ζ 1 ζ 2 = ∞.Thus, C 1 (u) and C 2 (u) do not satisfy Definition A.2.In fact, the condition specified in Definition A.3 does not impose any restrictions on the compressor class when working with unbiased compressors. This is because, for any set of compressors C 1 , . . . , C n ∈ U(ω), there exists θ ≥ 0 such that {C i } n i=1 ∈ P(θ), as shown in the following lemma. Lemma A.5.1. Let C 1 , . . . , C n be a collection of compressors such that C i ∈ U(ω) for all i ∈ [n]. Then {C i } n i=1 ∈ P(ω).2. Let us further assume that C 1 , . . . , C n are independent (Assumption 1.6). Then {C i } n i=1 ∈ P( ω /n).1. Jensen's inequality givesE   1 n n i=1 C i (u) -u 2   (50) ≤ 1 n n i=1 E ∥C i (u) -u∥ 2 Def.1.4 ≤ 1 n n i=1 ω ∥u∥ 2 = ω ∥u∥ 2 , so θ = ω.2. Using independence of compressors, we haveE   1 n n i=1 C i (u) -u 2   = 1 n 2 n i=1 E ∥C i (u) -u∥ 2 Def.1.4 ≤ 1 n 2 n i=1 ω ∥u∥ 2 = ω n ∥u∥ 2 .Thus θ = ω /n.However, the true advantages of employing correlated compressors become apparent when the definition holds with θ = 0, as in the case of PermK compressors.Lemma A.6. Let C 1 , . . . , C n be a collection of a) SameRandK, b) independent RandK, c) PermK compressors. Then a) {C i } n i=1 ∈ P(ω) and C i ∈ U(ω) where ω = d /K -1 for all i ∈ [n], b) {C i } n i=1 ∈ P( ω /n) and C i ∈ U(ω) where ω = d /K -1 for all i ∈ [n], c) {C i } n i=1 ∈ P(0) and C i ∈ U(ω) where ω = n -1 for all i ∈ [n].Proof. Unbiasedness follows easily from definitions of compressors (the proof for PermK compressors can be found in Szlendak et al. (2021) ). That RandK ∈ U( d /K -1) (and hence trivially SameRandK ∈ U( d /K -1)) is a well-known fact. Next, the fact that a) {C i } n i=1 ∈ P(ω) for SameRandK compressors and b) {C i } n i=1 ∈ P( ω /n) for independent RandK compressors follows directly from Lemma A.5.To compute ω for PermK compressor, first assume that d ≥ n. Then E ∥C i (x)∥ 2 = n ∥x∥ 2 (Szlendak et al., 2021) , soE ∥C i (x) -x∥ 2 (48) = E ∥C i (x)∥ 2 -∥x∥ 2 = (n -1) ∥x∥ 2 .Similarly, suppose that d ≤ n, and write n as n = qd + r, where q ∈ N >0 and 0 ≤ r < d. Then Szlendak et al., 2021) , and henceE ∥C i (x)∥ 2 = n /q ∥x∥ 2 (E ∥C i (x) -x∥ 2 (48) = E ∥C i (x)∥ 2 -∥x∥ 2 = n q -1 ∥x∥ 2 ≤ (n -1) ∥x∥ 2 .In both cases ω = n -1.Finally, by construction of PermK, we have1 n n i=1 C i (x) = x, implying θ = 0.In what follows, when considering the PermK compressor, we shall assume for simplicity that d ≥ n.The results for d < n are analogous.In addition to unbiased compressors (Definition 1.4), the literature of compressed methods distinguishes another class of mappings:Algorithm 1 MARINA-P 1: Input: initial model x 0 ∈ R d (stored on the server), initial model shifts w 0 1 = . . . = w 0 n = x 0 (stored on the workers), step size γ > 0, probability 0 < p ≤ 1, compressors C t 1 , . . . , C t n ∈ U(ω P )2: for t = 0, . . . , T do 3:for i = 1, . . . , n in parallel do 4:Calculate ∇f i (w t i ) and send it to the server Workers evaluate the gradients at the current model estimate 5:end for On the server:6:g t = 1 n n i=1 ∇f i (w t i )Server averages the messages received from the workers 7:x t+1 = x t -γg tServer takes a gradient-type step to update the global model 8:Sample c t ∼ Bernoulli(p) 9: if c t = 0 then 10: Send C t i (x t+1 -x t ) to worker i for i ∈ [n]Server sends compressed messages to all workers w.p. 1 -p 11:else 12: Send x t+1 to worker i for i ∈ [n]Server sends the same uncompressed message to all workers w.p. pend if On the workers:14:for i = 1, . . . , n in parallel do 15:w t+1 i = x t+1 if c t = 1, w t i + C t i (x t+1 -x t ) if c t = 0Worker i updates its local model shift 16:EQUATIONThe family of such compressors is denoted by B(α). It is well-known that if C ∈ U(ω), then (ω + 1) -1 C ∈ B (ω + 1) -1 , meaning that the family of biased compressors is broader. A canonical example is the TopK ∈ B( K /d) compressor, which preserves the K largest in magnitude coordinates of the input vector (Beznosikov et al., 2020) .We first prove the results from Section 4, starting with calculating the constants L A and L B from Assumption 4.2 in some special cases. Theorem 4.4. For all i ∈ [n], assume that the functions f i are L i -smooth (Assumption 1.5). Then, Assumption 4.2 holds with L A = L max and L B = 0.Proof. From Assumption 1.5 it follows that1 n n i=1 (∇f i (x + u i ) -∇f i (x)) 2 (50) ≤ 1 n n i=1 ∥∇f i (x + u i ) -∇f i (x)∥ 2 Ass.1.5 ≤ 1 n n i=1 L 2 i ∥u i ∥ 2 ≤ L 2 max 1 n n i=1 ∥u i ∥ 2 ,so Assumption 4.2 holds with L A = L max and L B = 0.Theorem 4.5. For all i ∈ [n], assume that the functions f i are homogeneous quadratics defined in (8). Then, Assumption 4.2 holds with L A = 0 and L B = ∥A∥ .Proof. It is easy to verify that1 n n i=1 (∇f i (x + u i ) -∇f i (x)) 2 = 1 n n i=1 (A(x + u i ) + b -(Ax + b)) 2 = A 1 n n i=1 u i 2 ≤ ∥A∥ 2 1 n n i=1 u i 2 ,meaning that Assumption 4.2 holds with L A = 0 and L B = ∥A∥.Lemma C.1. Let Assumption 1.5 hold. Then, there exist constants L A , L B ≥ 0 such that Assumption 4.2 holds andL 2 A + L 2 B ≤ L 2 max .Proof. Assumption 1.5 gives1 n n i=1 (∇f i (x + u i ) -∇f i (x)) 2 (50) ≤ 1 n n i=1 ∥∇f i (x + u i ) -∇f i (x)∥ 2 Ass.1.5 ≤ 1 n n i=1 L 2 i ∥u i ∥ 2 ≤ L 2 max 1 n n i=1 ∥u i ∥ 2 ,and hence Assumption 4.2 holds with L 2 A = L 2 max and L 2 B = 0.Remark C.2. Under Assumption 4.2 we have1 n n i=1 (∇f i (x + u i ) -∇f i (x)) 2 Ass.4.2 ≤ L 2 A 1 n n i=1 ∥u i ∥ 2 + L 2 B 1 n n i=1 u i 2 Ass.1.5 ≤ L 2 A + L 2 B 1 n n i=1 ∥u i ∥ 2 ,so, in principle, one could always set L 2 B = 0. However, the bound could be tightened by decreasing L A and increasing L B . The smaller L A , the better the performance of our algorithms (see Corollaries D.4 and E.3). Now, we proceed to prove the result that relates the values of L A and L B to the Hessians of the functions f i .Theorem 4.8. Assume that the functions f i are twice continuously differentiable, L i -smooth (Assumption 1.5), and that there existD i ≥ 0 such that sup z1,...,zn∈R d ∇ 2 f i (z i ) -1 n n j=1 ∇ 2 f j (z j ) ≤ D i (11) for all i ∈ [n]. Then, Assumption 4.2 holds with L A = √ 2 max i∈[n] D i ≤ 2 √ 2 max i∈[n] L i and L B = √ 2 1 n n i=1 L i .Proof. By the fundamental theorem of calculus,∇f i (x + u i ) -∇f i (x) = 1 0 ∇ 2 f i (x + tu i )u i dt = 1 0 ∇ 2 f i (x + tu i )dt u i = Q i u i ,whereQ i = 1 0 ∇ 2 f i (x + tu i )dt. Letting Q = 1 n n i=1 Q i , we can write 1 n n i=1 (∇f i (x + u i ) -∇f i (x)) 2 = 1 n n i=1 Q i u i 2 = 1 n n i=1 (Q i -Q) u i + Q 1 n n i=1 u i 2 (44) ≤ 2 1 n n i=1 (Q i -Q) u i 2 + 2 Q 1 n n i=1 u i 2 (50) ≤ 2 1 n n i=1 ∥(Q i -Q) u i ∥ 2 + 2 ∥Q∥ 2 1 n n i=1 u i 2 ≤ 2 1 n n i=1 ∥Q i -Q∥ 2 ∥u i ∥ 2 + 2 ∥Q∥ 2 1 n n i=1 u i 2 .Further,∥Q i -Q∥ = 1 0 ∇ 2 f i (x + tu i )dt - 1 n n j=1 1 0 ∇ 2 f j (x + tu j )dt = 1 0 ∇ 2 f i (x + tu i )dt - 1 0 1 n n j=1 ∇ 2 f j (x + tu j )dt = 1 0 1 n n j=1 ∇ 2 f i (x + tu i ) -∇ 2 f j (x + tu j ) dt ≤ 1 0 ∇ 2 f i (x + tu i ) - 1 n n j=1 ∇ 2 f j (x + tu j ) dt ≤ 1 0 D i dt = D i ,and∥Q∥ = 1 n n j=1 1 0 ∇ 2 f j (x + tu j )dt = 1 0 1 n n j=1 ∇ 2 f j (x + tu j )dt ≤ 1 0 1 n n j=1 ∇ 2 f j (x + tu j ) dt (50) ≤ 1 0 1 n n j=1 ∇ 2 f j (x + tu j ) dt ≤ 1 0 1 n n j=1 L j dt = 1 n n j=1 L j .By combining the above, we get1 n n i=1 (∇f i (x + u i ) -∇f i (x)) 2 ≤ 2 1 n n i=1 D 2 i ∥u i ∥ 2 + 2   1 n n j=1 L j   2 1 n n i=1 u i 2 ≤ 2 max i D 2 i ∥u i ∥ 2 + 2   1 n n j=1 L j   2 1 n n i=1 u i 2 ,which means that Assumption 4.2 holds withL 2 A = 2(max i D 2 i ) and L 2 B = 2 1 n n i=1 L i 2 .Remark C.3. Clearly, if Assumption 1.5 holds, i.e., if there existsL i ≥ 0 such that sup zi∈R d ∇ 2 f i (z i ) ≤ L i for all i ∈ [n], then there exists D i such that sup z1,...,zn∈R d ∇ 2 f i (z i ) -1 n n j=1 ∇ 2 f j (z j ) ≤ D i, which means that this latter condition is not restrictive. Indeed,∇ 2 f i (z i ) - 1 n n j=1 ∇ 2 f j (z j ) ≤ ∇ 2 f i (z i ) + 1 n n j=1 ∇ 2 f j (z j ) ≤ ∇ 2 f i (z i ) + 1 n n j=1 ∇ 2 f j (z j ) ≤ L i + 1 n n j=1 L j .However, D i can be small even if the constants {L i } are large, as the next theorem shows.Theorem 4.9. Assume thatf i (x) = 1 2 x ⊤ A i x + b ⊤ i x + c i , where A i ∈ R d×d is symmetric but not necessarily positive semidefinite, b i ∈ R d and c i ∈ R for i ∈ [n]. Define A = 1 n n i=1 A i . Then, Assumption 4.2 holds with L A = √ 2 max i∈[n] ∥A i -A∥ and L B = √ 2 1 n n i=1 ∥A i ∥ .Proof. In this case ∇ 2 f i (z i ) ≡ A i , and the result easily follows from Theorem 4.8.As promised, we now present a result generalizing Theorem 4.6 to all unbiased compressors.Theorem D.1. Let Assumptions 1.1, 1.2 and 4.2 be satisfied and suppose that{C t i } n i=1 ∈ P(θ) (Def. A.3) and C t i ∈ U(ω P ) (Def. 1.4) for all i ∈ [n]. Let 0 < γ ≤ 1 L + (L 2 A ω P + L 2 B θ) 1 p -1 . Letting Ψ t = f (x t ) -f * + γL 2 A 2p 1 n n i=1 w t i -x t 2 + γL 2 B 2p w t -x t 2 , for each T ≥ 1 we have T -1 t=0 1 T E ∇f (x t ) 2 ≤ 2Ψ 0 γT .Let us provide some important examples:Theorem D.2. Let Assumptions 1.1, 1.2 and 4.2 be satisfied. Chooseγ =            L + (L 2 A + L 2 B ) ω P /p -1 for SameRandK compressors L + L 2 A + L 2 B/n ω P /p -1 for independent RandK compressors L + L A ω P /p -1for PermK compressors and set w 0 i = x 0 for all i ∈ [n]. Then MARINA-P finds an ε-stationary point afterT =                        O   δ 0 L+ (L 2 A +L 2 B ) ω P/p ε   for SameRandK compressors O   δ 0 L+ (L 2 A + L 2 B/n) ω P/p ε   for independent RandK compressors O δ 0 L+L A √ ω P/p ε for PermK compressors iterations.Remark D.3.• The result for PermK compressors proves Theorem 4.6.• The above theorem demonstrates the complexities for a) SameRandK, b) independent RandK and c) PermK compressors. However, the result applies to any families of compressors such that for all t ≥ 0 we have a)C t 1 = . . . = C t n = C t ∈ U(ω P ), b) C t 1 , . . . , C t n ∈ U(ω P ) are independent, and c) C t 1 , . . . , C t n ∈ U(ω P ) ∩ P(θ), respectively.We now derive the communication complexities: Corollary D.4. Let us take p = 1 /n and set K = d /n (corresponding to the sparsification level of a PermK compressor). Then, in the view of Theorem D.2, the average s2w communication complexity of MARINA-P isEQUATIONRemark D.5.• The result for PermK compressors proves Corollary 4.7.• The key observation from ( 19) is the dependence on L A and L B . In particular, if L A ≈ 0 (which is the case, e.g., for homogeneous quadratics), the above communication complexities are         O δ 0 ε d L n + L B for SameRandK compressors, O δ 0 ε d L n + L B √ n for independent RandK compressors, O δ 0 ε d L n for PermK compressors.Hence, only by sending different messages to different clients, one obtains complexities improving with n. In particular, for PermK, the complexity scales linearly with the number of workers.To prove the results from the previous section, we first establish several identities and inequalities satisfied by the sequences {w t 1 , . . . , w t n } t≥0 . We start by studying the evolution of the quantity∥w t i -x t ∥ 2 .In what follows, E t [•] denotes the expectation conditioned on the first t iterations.Lemma D.6. Let C t i ∈ U(ω P ) for all i ∈ [n]. Then 1 n n i=1 E w t+1 i -x t+1 2 ≤ (1 -p) 1 n n i=1 E w t i -x t 2 + (1 -p)ω P E x t+1 -x t 2 .Proof. In the view of definition of w t+1 , we getE t w t+1 i -x t+1 2 = (1 -p)E t w t i + C t i (x t+1 -x t ) -x t+1 2 (48) = (1 -p)E t C t i (x t+1 -x t ) -(x t+1 -x t ) 2 + (1 -p)E t w t i -x t 2 Def.1.4 ≤ (1 -p)ω P x t+1 -x t 2 + (1 -p) w t i -x t 2. Averaging, taking expectation and using the tower property, we get the result. This lemma is less powerful: it is not an identity, and hence some information is lost. Moreover, it focuses on a single client i, and is therefore not able to take advantage of the correlation among the compressors. On the other hand, it can be used in the convergence analysis without any need to restrict the function class.Next, we study the evolution of the quantity ∥w t -x t ∥ 2 .Lemma D.7.Let {C t i } n i=1 ∈ P(θ). Then E w t+1 -x t+1 2 ≤ (1 -p)E w t -x t 2 + (1 -p)θE x t+1 -x t 2 .Proof. In the view of definition of w t+1 , we getE t w t+1 -x t+1 2 = E t   1 n n i=1 w t+1 i -x t+1 2   = (1 -p)E t   1 n n i=1 (w t i + C t i (x t+1 -x t )) -x t+1 2   = (1 -p)E t   1 n n i=1 C t i (x t+1 -x t ) -(x t+1 -x t ) -x t + w t 2   (48) = (1 -p)E t   1 n n i=1 C t i (x t+1 -x t ) -(x t+1 -x t ) 2   + (1 -p)E t w t -x t 2 Def.A.3 ≤ (1 -p)θ x t+1 -x t 2 + (1 -p) w t -x t 2 .Taking expectation and using the tower property, we get the result.This lemma is more powerful since it is able to take advantage of the correlation among the compressors. Indeed, if θ = 0 (as in the case of PermK compressors), then it becomes an identity:E w t+1 -x t+1 2 = (1 -p)E w t -x t 2 .We now prove convergence of MARINA-P in the general case. Theorem D.1. Let Assumptions 1.1, 1.2 and 4.2 be satisfied and suppose that{C t i } n i=1 ∈ P(θ) (Def. A.3) and C t i ∈ U(ω P ) (Def. 1.4) for all i ∈ [n]. Let 0 < γ ≤ 1 L + (L 2 A ω P + L 2 B θ) 1 p -1 . Letting Ψ t = f (x t ) -f * + γL 2 A 2p 1 n n i=1 w t i -x t 2 + γL 2 B 2p w t -x t 2 , for each T ≥ 1 we have T -1 t=0 1 T E ∇f (x t ) 2 ≤ 2Ψ 0 γT .Proof. First, combining the inequalities in Lemmas D.6 and D.7, we getEQUATION)Next, using Assumption 4.2, we haveE g t -∇f (x t ) 2 = E   1 n n i=1 ∇f i (w t i ) -∇f i (x t ) 2   Ass.4.2 ≤ L 2 A 1 n n i=1 E w t i -x t 2 + L 2 B E   1 n n i=1 w t i -x t 2   .Combining the above inequality with Lemma H.1 givesEQUATION)By adding inequalities ( 20) and ( 21), we getE Ψ t+1 = E δ t+1 + γL 2 A 2p 1 n n i=1 E w t+1 i -x t+1 2 + γL 2 B 2p E w t+1 -x t+1 2 ≤ E δ t - γ 2 E ∇f (x t ) 2 - 1 2γ - L 2 E x t+1 -x t 2 + γ 2 L 2 A 1 n n i=1 E w t i -x t 2 + L 2 B E w t -x t 2 + γL 2 A 2p (1 -p) 1 n n i=1 E w t i -x t 2 + γL 2 B 2p (1 -p)E w t -x t 2 + γ 2p L 2 A ω P + L 2 B θ (1 -p)E x t+1 -x t 2 = E Ψ t - γ 2 E ∇f (x t ) 2 - 1 2γ - L 2 - γ 2p L 2 A ω P + L 2 B θ (1 -p) E x t+1 -x t 2 ≤ E Ψ t - γ 2 E ∇f (x t ) 2 ,where in the last line we use the assumption on the step size and Lemma H.2. Summing up the above inequality for t = 0, 1, . . . , T -1 and rearranging the terms, we get1 T T -1 t=0 E ∇f (x t ) 2 ≤ 2 γT E Ψ 0 -E Ψ T ≤ 2Ψ 0 γT .With the above result, we can establish the iteration and communication complexities of MARINA-P for three different compression schemes described in Appendix A. First, let us prove a result when independent compressors are used.Theorem D.8. Let Assumptions 1.1, 1.2 and 4.2 be satisfied and suppose that C t 1 , . . . , C t n is a collection of independent compressors (Assumption 1.6) such thatC t i ∈ U(ω) for all i ∈ [n], t ∈ N. Choose γ = L + L 2 A + L 2 B/n ω P /p -1and set w 0 i = x 0 for all i ∈ [n]. Then MARINA-P finds an ε-stationary point afterT = O    δ 0 L + L 2 A + L 2 B/n ω P /p ε    iterations.Proof. In view of Theorem D.1, the step size satisfies the inequalityγ ≤ 1 L + (L 2 A ω P + L 2 B θ) 1 p -1 .Since by Lemma A.5, when the compressors are independent we have θ = ω P /n, the algorithm converges inEQUATIONiterations.Theorem D.2. Let Assumptions 1.1, 1.2 and 4.2 be satisfied. Chooseγ =            L + (L 2 A + L 2 B ) ω P /p -1 for SameRandK compressors L + L 2 A + L 2 B/n ω P /p -1 for independent RandK compressors L + L A ω P /p -1for PermK compressors and set w 0 i = x 0 for all i ∈ [n]. Then MARINA-P finds an ε-stationary point afterT =                        O   δ 0 L+ (L 2 A +L 2 B ) ω P/p ε   for SameRandK compressors O   δ 0 L+ (L 2 A + L 2 B/n) ω P/p ε   for independent RandK compressors O δ 0 L+L A √ ω P/p ε for PermK compressors iterations.Proof. In view of Theorem D.1, the step size is such thatγ ≤ 1 L + (L 2 A ω P + L 2 B θ) 1 p -1.We now use Lemma A.6 and substitute the vales of θ specific to each compression type.For SameRandK, we have θ = ω P , so the algorithm converges afterEQUATIONiterations. Following the same reasoning as in the proof of Theorem D.8, for RandK we haveEQUATIONFinally, for PermK we have θ = 0, soEQUATIONThe result follows from the fact that w 0 i = x 0 for all i ∈ [n].Corollary D.4. Let us take p = 1 /n and set K = d /n (corresponding to the sparsification level of a PermK compressor). Then, in the view of Theorem D.2, the average s2w communication complexity of MARINA-P isEQUATIONProof. The expected number of floats a server is relaying to each client at each iteration of MARINA-P ispd + (1 -p)k = d n + n -1 n k ≤ 2d n .Next, using the results from Lemma A.6, our choice of compressors and parameters gives ω P = d /K -1 = n -1 in each of the three cases. Hence, substituting p = 1 /n in ( 23), ( 24) and ( 25), we obtain the following server-to-worker communication complexities:1. for SameRandK compressors:d n × δ 0 ε L + ω P (L 2 A + L 2 B ) 1 p -1 = δ 0 ε d n L + d n (L 2 A + L 2 B ) (n -1) 2 = O δ 0 ε d n L + d L 2 A + L 2 B ,2. for RandK compressors:d n × δ 0 ε L + ω P L 2 A + L 2 B n 1 p -1 = δ 0 ε d n L + d n L 2 A + L 2 B n (n -1) 2 = O δ 0 ε d n L + d L 2 A + L 2 B n ,3. for PermK compressors:d n × δ 0 ε L + L 2 A ω P 1 p -1 = δ 0 ε d n L + d n L A (n -1) 2 = O δ 0 ε d n L + dL A . D.3 Polyak-Łojasiewicz condition D.3To complete the theory, we now establish a convergence result for MARINA-P under the Polyak-Łojasiewicz assumption. Assumption D.9 (Polyak-Łojasiewicz condition). The function f satisfies Polyak-Łojasiewicz (PŁ) condition with parameter µ, i.e., for all x ∈ R d there exists x * ∈ arg minEQUATION)Theorem D.10. Let Assumptions 1.1, 1.2, 4.2 and D.9 be satisfied and suppose thatEQUATIONEQUATION)LettingEQUATIONfor each T ≥ 1 we haveE Ψ T ≤ (1 -γµ) T Ψ 0 .Corollary D.11. Let C t i ∈ P(0) for all i ∈ [n] (e.g. PermK), choose p = 1/(ω P + 1). Then, in the view of Theorem D.10, Algorithm 1 ensures thatE f (x T ) -f * ≤ ε after O max L + L A ω P µ , ω P + 1 log Ψ 0 ε iterations.Corollary D.12. Let C t i be the PermK compressors (K = d /n). Then, in the view of Corollary D.11, the s2w communication complexity of MARINA-P with PermK isO dL nµ + dL A µ + d log Ψ 0 ε .Theorem D.10. Let Assumptions 1.1, 1.2, 4.2 and D.9 be satisfied and suppose thatEQUATIONEQUATION)LettingEQUATIONfor each T ≥ 1 we haveE Ψ T ≤ (1 -γµ) T Ψ 0 .Proof. We proceed similarly as in the proof of Theorem D.1. Combining the inequalities in Lemmas D.6 and D.7 givesEQUATION)By adding inequalities ( 21) and ( 29), we getE Ψ t+1 = E δ t+1 + γL 2 A p 1 n n i=1 E w t+1 i -x t+1 2 + γL 2 B p E w t+1 -x t+1 2 ≤ E δ t - γ 2 E ∇f (x t ) 2 - 1 2γ - L 2 E x t+1 -x t 2 + γ 2 L 2 A 1 n n i=1 E w t i -x t 2 + L 2 B E w t -x t 2 + γL 2 A p (1 -p) 1 n n i=1 E w t i -x t 2 + γL 2 B p (1 -p)E w t -x t 2 + γ p L 2 A ω P + L 2 B θ (1 -p)E x t+1 -x t 2 = E δ t - γ 2 E ∇f (x t ) 2 - 1 2γ - L 2 - γ p L 2 A ω P + L 2 B θ (1 -p) E x t+1 -x t 2 +γL 2 A 1 p - 1 2 1 n n i=1 E w t i -x t 2 + γL 2 B 1 p - 1 2 E w t -x t 2Ass.D.9,( 27)≤ (1 -γµ) E δ t + γL 2 A p (1 -γµ) 1 n n i=1 E w t i -x t 2 + γL 2 B p (1 -γµ) E w t -x t 2 = (1 -γµ) E Ψ t ,where the last inequality follows from the Polyak-Łojasiewicz condition, Lemma H.2 and our choice of γ. Applying the above inequality iteratively, we finish the proof.Corollary D.11. Let C t i ∈ P(0) for all i ∈ [n] (e.g. PermK), choose p = 1/(ω P + 1). Then, in the view of Theorem D.10, Algorithm 1 ensures thatE f (x T ) -f * ≤ ε after O max L + L A ω P µ , ω P + 1 log Ψ 0 ε iterations.Proof. In view of Theorem D.10, the step size satisfiesEQUATION       .Therefore, since θ = 0 and p = 1/(ω P + 1), the algorithm converges afterT = max        L + 2 (L 2 A ω P + L 2 B θ) 1 p -1 µ , 2 p        log Ψ 0 ε = O max L + L A ω P µ , ω P + 1 log Ψ 0 ε iterations.Corollary D.12. Let C t i be the PermK compressors (K = d /n). Then, in the view of Corollary D.11, the s2w communication complexity of MARINA-P with PermK isO dL nµ + dL A µ + d log Ψ 0 ε .Proof. For PermK, ω P = n -1. Therefore, the iteration complexity isO max L + L A n µ , n log Ψ 0 ε .Since the expected number of floats the server is relaying to each client ispd + (1 -p)k = d n + n -1 n k ≤ 2d n ,the server-to-worker communication complexity isO max d n L + dL A µ , d log Ψ 0 ε .We now move on to the bidirectionally compressed method. Below is a generalization of Theorem 5.1 to all unbiased compressors.Theorem E.1. Let Assumptions 1.1, 1.2, 1.5 and 4.2 hold and suppose that the compressorsQ t i ∈ U(ω D ) satisfy Assumption 1.6, {C t i } n i=1 ∈ P(θ) and C t i ∈ U(ω P ) for all i ∈ [n]. Let γ > 0 be such that γ ≤ L + 288 θ p P + 1+θp P β 2 L 2 B + ω P p P + 1+ω P p P β 2 L 2 A + ω D ω P β np D + ω D (1+ω P p P ) np D L 2 max -1.LettingΨ t = δ t + κ g t - 1 n n i=1 ∇f i (z t i ) 2 + η z t -w t 2 + ν 1 n n i=1 z t i -w t i 2 + ρ w t -x t 2 + µ 1 n n i=1 w t i -x t 2 , where κ = γ p D , η = 4γL 2 B β , ν = 4γL 2 A β + 6γω D βL 2 max np D , ρ = 32γL 2 B 1 p P + p P β 2 and µ = 32γL 2 A 1 p P + p P β 2 + 48γω D L 2 max np D (β + p P ), M3 ensures that 1 T T -1 t=0 E ∇f (x t ) 2 = O Ψ 0 γT .We now simplify the above result by considering θ = 0.Corollary E.2. Let C t i ∈ P(0) for all i ∈ [n] (e.g. PermK), choose p P = 1/(ω P + 1), p D = 1/(ω D + 1) andβ = min n ω D ω P (ω D + 1) 1/3 , 1 .Then, in the view of Theorem E.1, the iteration complexity isO Ψ 0 ε L max + ω D ω P (ω D + 1) n 1/3 L max + ω D (ω D + 1) n L max + ω P (ω P + 1)L A .We now give the bound for the total communication complexity of M3.Corollary E.3. Let C t i be the PermK compressors and Q t i be the independent (Assumption 1.6) RandK compressors, both with K = d /n. Then, in the view of Corollary E.2, the iteration complexity isO Ψ 0 ε n 2/3 L max + nL A ,and the total communication complexity isO Ψ 0 ε dL max n 1/3 + dL A .Remark E.4. The above result proves the complexities from Theorem 5.1.1: Input: initial model x 0 ∈ R d (stored on the server), initial model shifts w 0 i = z 0 i = x 0 , i ∈ [n] (stored on the workers), initial gradient estimators g 0 = ∇f (x 0 ) (stored on the sever), step size γ > 0, probabilities 0< p P , p D ≤ 1, compressors C t 1 , . . . , C t n ∈ U(ω P ) ∩ P(θ), Q t 1 , . . . , Q t n ∈ U(ω D) for all t ≥ 0. 2: for t = 0, . . . , T do 3: For i ∈ [n], send C t i (x t+1 -x t ) to worker i if c t P = 0 and x t+1 otherwise 6:x t+1 = x t -γg tfor i = 1, . . . , n in parallel do 7:w t+1 i = x t+1 if c t P = 1, w t i + C t i (x t+1 -x t ) if c t P = 0,Worker i updates its local model shift 8:z t+1 i = βw t+1 i + (1 -β)z t i Worker i takes the momentum step 9: Send Q t i (∇f i (z t+1 i ) -∇f i (z t i )) to the server if c t D = 0 and ∇f i (z t+1 i ) otherwise 10:end for 11:if c t D = 1 then 12: g t+1 = 1 n n i=1 f i (z t+1 i ) 13:else 14:g t+1 = g t + 1 n n i=1 Q t i (∇f i (z t+1 i ) -∇f i (z t i ))15:end if 16: end for (maintaining only the sequence g t in the implementation is sufficient; the sequences g t i from ( 14) are virtual)Similar to our approach from the previous section, we start by establishing several inequalities satisfied by the sequences {w t 1 , . . . , w t n } t≥0 , {z t 1 , . . . , z t n } t≥0 and {g t 1 , . . . , g t n } t≥0 . Lemma E.5. Let C t i ∈ U(ω P ) for all i ∈ [n] and {C t i } n i=1 ∈ P(θ). ThenE t w t+1 i -z t i 2 ≤ (x t+1 -x t ) -p P (w t i -x t ) + (w t i -z t i ) 2 + p P w t i -x t 2 + ω P x t+1 -x t 2 for all i ∈ [n], andE t w t+1 -z t 2 ≤ (x t+1 -x t ) -p P (w t -x t ) + (w t -z t ) 2 + p P w t -x t 2 + θ x t+1 -x t 2 .Proof. Using the definition of w t+1 i , we haveE t w t+1 i = x t+1 + (1 -p P )(w t i -x t ) and hence E t w t+1 i -z t i 2 (48) = x t+1 + (1 -p P )(w t i -x t ) -z t i 2 +E t w t+1 i -(x t+1 + (1 -p P )(w t i -x t )) 2 = (x t+1 -x t ) -p P (w t i -x t ) + (w t i -z t i ) 2 +E t w t+1 i -(x t+1 + (1 -p P )(w t i -x t )) 2 .Using the definition of w t+1 i again, we getE t w t+1 i -z t i 2 = (x t+1 -x t ) -p P (w t i -x t ) + (w t i -z t i ) 2 +p P x t+1 -(x t+1 + (1 -p P )(w t i -x t )) 2 +(1 -p P )E t w t i + C t i (x t+1 -x t ) -(x t+1 + (1 -p P )(w t i -x t )) 2 = (x t+1 -x t ) -p P (w t i -x t ) + (w t i -z t i ) 2 + p P (1 -p P ) 2 w t i -x t 2 +(1 -p P )E t C t i (x t+1 -x t ) -(x t+1 -x t ) + p P (w t i -x t ) 2 (48) = (x t+1 -x t ) -p P (w t i -x t ) + (w t i -z t i ) 2 + p P (1 -p P ) 2 w t i -x t 2 +(1 -p P )p 2 P w t i -x t 2 + (1 -p P )E t C t i (x t+1 -x t ) -(x t+1 -x t ) 2 Def.1.4 ≤ (x t+1 -x t ) -p P (w t i -x t ) + (w t i -z t i ) 2 + p P w t i -x t 2 + ω P x t+1 -x t 2 .Using the same reasoning, we now prove the second inequality:E t w t+1 -z t 2 (48) = x t+1 + (1 -p P )(w t -x t ) -z t 2 + E t w t+1 -(x t+1 + (1 -p P )(w t -x t )) 2 = (x t+1 -x t ) -p P (w t -x t ) + (w t -z t ) 2 +E t w t+1 -(x t+1 + (1 -p P )(w t -x t )) 2 = (x t+1 -x t ) -p P (w t -x t ) + (w t -z t ) 2 + p P (1 -p P ) 2 w t -x t 2 +(1 -p P )E t   w t + 1 n n i=1 C t i (x t+1 -x t ) -(x t+1 + (1 -p P )(w t -x t )) 2   = (x t+1 -x t ) -p P (w t -x t ) + (w t -z t ) 2 + p P (1 -p P ) 2 w t -x t 2 +(1 -p P )E t   1 n n i=1 C t i (x t+1 -x t ) -(x t+1 -x t ) + p P (w t -x t ) 2   (48) = (x t+1 -x t ) -p P (w t -x t ) + (w t -z t ) 2 + p P (1 -p P ) 2 w t -x t 2 +(1 -p P )E t   1 n n i=1 C t i (x t+1 -x t ) -(x t+1 -x t ) 2   + p 2 P (1 -p P ) w t -x t 2 Def.A.3 ≤ (x t+1 -x t ) -p P (w t -x t ) + (w t -z t ) 2 + p P w t -x t 2 + θ x t+1 -x t 2 .Lemma E.6. Let Assumption 1.5 hold. Furthermore, suppose that the compressorsQ t i ∈ U(ω D ) satisfy Assumption 1.6 and that C t i ∈ U(ω P ) for i ∈ [n]. Then E   g t+1 - 1 n n i=1 ∇f i (z t+1 i ) 2   ≤ ω D L 2 max n 4p P β 2 E 1 n n i=1 w t i -x t 2 + 3β 2 E 1 n n i=1 z t i -w t i 2 + 3(ω P + 1)β 2 E x t+1 -x t 2 + (1 -p D )E   g t - 1 n n i=1 ∇f i (z t i ) 2   .Proof. First, from the definition of g t+1 i , we getE   g t+1 - 1 n n i=1 ∇f i (z t+1 i ) 2   = (1 -p D )E   1 n n i=1 g t i + Q t i (∇f i (z t+1 i ) -∇f i (z t i )) -∇f i (z t+1 i ) 2  and henceEQUATIONLet us consider the first term separately:E 1 n n i=1 z t+1 i -z t i 2 = E 1 n n i=1 βw t+1 i + (1 -β)z t i -z t i 2 = β 2 E 1 n n i=1 w t+1 i -z t i 2 .Using the result from Lemma E.5, we haveE 1 n n i=1 z t+1 i -z t i 2 ≤ β 2 E 1 n n i=1 (x t+1 -x t ) -p P (w t i -x t ) + (w t i -z t i ) 2 +β 2 E p P 1 n n i=1 w t i -x t 2 + ω P x t+1 -x t 2 (45) ≤ β 2 E 3 n n i=1 w t i -z t i 2 + 4p P 1 n n i=1 w t i -x t 2 + (ω P + 3) x t+1 -x t 2 ,where in the last line we use the fact that p P ≤ 1. It remains to substitute the above inequality in (30).Lemma E.7. Let C t i ∈ U(ω P ) for all i ∈ [n] and {C t i } n i=1 ∈ P(θ). Then E z t+1 i -w t+1 i 2 ≤ 1 - β 2 E z t i -w t i 2 + 4 1 β + ω P E x t+1 -x t 2 + 4p P 1 + p P β E w t i -x t 2for all i ∈ [n], andE z t+1 -w t+1 2 ≤ 1 - β 2 E z t -w t 2 + 4 1 β + θ E x t+1 -x t 2 + 4p P 1 + p P β E w t -x t 2 .Proof. From the definition of z t+1 i , we getE z t+1 i -w t+1 i 2 = E βw t+1 i + (1 -β)z t i -w t+1 i 2 = (1 -β) 2 E w t+1 i -z t i 2 .Then, Lemma E.5 givesE z t+1 i -w t+1 i 2 ≤ (1 -β) 2 E (x t+1 -x t ) -p P (w t i -x t ) + (w t i -z t i ) 2 +(1 -β) 2 E p P w t i -x t 2 + ω P x t+1 -x t 2(44),( 46),( 47)≤ 1 - β 2 E w t i -z t i 2 + 2 β E (x t+1 -x t ) -p P (w t i -x t ) 2 +E p P w t i -x t 2 + ω P x t+1 -x t 2 (45) ≤ 1 - β 2 E w t i -z t i 2 + 4 β E x t+1 -x t 2 + 4p 2 P β E w t i -x t 2 +E p P w t i -x t 2 + ω P x t+1 -x t 2 ≤ 1 - β 2 E w t i -z t i 2 + 4 1 β + ω P E x t+1 -x t 2 +4p P 1 + p P β E w t i -x t 2 .The second inequality is proved almost in the same way. First,E z t+1 -w t+1 2 = (1 -β) 2 E w t+1 -z t 2 ,and using Lemma E.5, we obtainE z t+1 -w t+1 2 ≤ (1 -β) 2 E (x t+1 -x t ) -p P (w t -x t ) + (w t -z t ) 2 + p P w t -x t 2 + θ x t+1 -x t 2 (44) ≤ 1 - β 2 E w t -z t 2 + 2 β E (x t+1 -x t ) -p P (w t -x t ) 2 +E p P w t -x t 2 + θ x t+1 -x t 2 (45) ≤ 1 - β 2 E w t -z t 2 + 4 1 β + θ E x t+1 -x t 2 + 4p 2 P β E w t -x t 2 + E p P w t -x t 2 ≤ 1 - β 2 E w t -z t 2 + 4 1 β + θ E x t+1 -x t 2 +4p P 1 + p P β E w t -x t 2 .Theorem E.1. Let Assumptions 1.1, 1.2, 1.5 and 4.2 hold and suppose that the compressorsQ t i ∈ U(ω D ) satisfy Assumption 1.6, {C t i } n i=1 ∈ P(θ) and C t i ∈ U(ω P ) for all i ∈ [n]. Let γ > 0 be such that γ ≤ L + 288 θ p P + 1+θp P β 2 L 2 B + ω P p P + 1+ω P p P β 2 L 2 A + ω D ω P β np D + ω D (1+ω P p P ) np D L 2 max -1.LettingΨ t = δ t + κ g t - 1 n n i=1 ∇f i (z t i ) 2 + η z t -w t 2 + ν 1 n n i=1 z t i -w t i 2 + ρ w t -x t 2 + µ 1 n n i=1 w t i -x t 2 , where κ = γ p D , η = 4γL 2 B β , ν = 4γL 2 A β + 6γω D βL 2 max np D , ρ = 32γL 2 B 1 p P + p P β 2 and µ = 32γL 2 A 1 p P + p P β 2 + 48γω D L 2 max np D (β + p P ), M3 ensures that 1 T T -1 t=0 E ∇f (x t ) 2 = O Ψ 0 γT .Proof. Lemma H.1 givesE δ t+1 ≤ E δ t - γ 2 E ∇f (x t ) 2 - 1 2γ - L 2 E x t+1 -x t 2 + γ 2 E g t -∇f (x t ) 2 (44) ≤ E δ t - γ 2 E ∇f (x t ) 2 - 1 2γ - L 2 E x t+1 -x t 2 +γE   g t - 1 n n i=1 ∇f i (z t i ) 2   + γE   1 n n i=1 ∇f i (z t i ) -∇f i (x t ) 2   (4.2) ≤ E δ t - γ 2 E ∇f (x t ) 2 - 1 2γ - L 2 E x t+1 -x t 2 +γE   g t - 1 n n i=1 ∇f i (z t i ) 2   + γL 2 A 1 n n i=1 E z t i -x t 2 + γL 2 B E z t -x t 2 (44) ≤ E δ t - γ 2 E ∇f (x t ) 2 - 1 2γ - L 2 E x t+1 -x t 2 +γE   g t - 1 n n i=1 ∇f i (z t i ) 2   + 2γL 2 A 1 n n i=1 E z t i -w t i 2 + E w t i -x t 2 +2γL 2 B E z t -w t 2 + E w t -x t 2 .Let κ, η, ν, ρ, µ ≥ 0 be some non-negative numbers that we define later. Using Lemmas D.6, D.7, E.6 and E.7, we getE δ t+1 + κE   g t+1 - 1 n n i=1 ∇f i (z t+1 i ) 2   + ηE z t+1 -w t+1 2 + νE 1 n n i=1 z t+1 i -w t+1 i 2 + ρE w t+1 -x t+1 2 + µE 1 n n i=1 w t+1 i -x t+1 2 ≤ E δ t - γ 2 E ∇f (x t ) 2 - 1 2γ - L 2 E x t+1 -x t 2 + γE   g t - 1 n n i=1 ∇f i (z t i ) 2   + 2γL 2 A 1 n n i=1 E z t i -w t i 2 + E w t i -x t 2 + 2γL 2 B E z t -w t 2 + E w t -x t 2 + κ ω D L 2 max n 4p P β 2 E 1 n n i=1 w t i -x t 2 + 3β 2 E 1 n n i=1 z t i -w t i 2 + 3(ω P + 1)β 2 E x t+1 -x t 2 + κ(1 -p D )E   g t - 1 n n i=1 ∇f i (z t i ) 2   + η 1 - β 2 E z t -w t 2 + 4 1 β + θ E x t+1 -x t 2 + 4p P 1 + p P β E w t -x t 2 + ν 1 - β 2 E 1 n n i=1 z t i -w t i 2 + 4 1 β + ω P E x t+1 -x t 2 + 4p P 1 + p P β E 1 n n i=1 w t i -x t 2 + ρ(1 -p P ) E w t -x t 2 + θE x t+1 -x t 2 + µ(1 -p P ) E 1 n n i=1 w t i -x t 2 + ω P E x t+1 -x t 2 . Taking κ = γ p D and η = 4γL 2 B β , we get γ + κ(1 -p D ) = κ and 2γL 2 B + η(1 -β /2) = η, which gives E δ t+1 + κE   g t+1 - 1 n n i=1 ∇f i (z t+1 i ) 2   + ηE z t+1 -w t+1 2 + νE 1 n n i=1 z t+1 i -w t+1 i 2 + ρE w t+1 -x t+1 2 + µE 1 n n i=1 w t+1 i -x t+1 2 ≤ E δ t - γ 2 E ∇f (x t ) 2 - 1 2γ - L 2 E x t+1 -x t 2 + κE   g t - 1 n n i=1 ∇f i (z t i ) 2   + ηE z t -w t 2 + 2γL 2 A 1 n n i=1 E z t i -w t i 2 + E w t i -x t 2 + 2γL 2 B E w t -x t 2 + γ p D ω D L 2 max n 4p P β 2 E 1 n n i=1 w t i -x t 2 + 3β 2 E 1 n n i=1 z t i -w t i 2 + 3(ω P + 1)β 2 E x t+1 -x t 2 + 4γL 2 B β 4 1 β + θ E x t+1 -x t 2 + 4p P 1 + p P β E w t -x t 2 + ν 1 - β 2 E 1 n n i=1 z t i -w t i 2 + 4 1 β + ω P E x t+1 -x t 2 + 4p P 1 + p P β E 1 n n i=1 w t i -x t 2 + ρ (1 -p P )E w t -x t 2 + θE x t+1 -x t 2 + µ (1 -p P )E 1 n n i=1 w t i -x t 2 + ω P E x t+1 -x t 2 .We rearrange the terms to obtainE δ t+1 + κE   g t+1 - 1 n n i=1 ∇f i (z t+1 i ) 2   + ηE z t+1 -w t+1 2 + νE 1 n n i=1 z t+1 i -w t+1 i 2 + ρE w t+1 -x t+1 2 + µE 1 n n i=1 w t+1 i -x t+1 2 ≤ E δ t - γ 2 E ∇f (x t ) 2 - 1 2γ - L 2 E x t+1 -x t 2 + κE   g t - 1 n n i=1 ∇f i (z t i ) 2   + ηE z t -w t 2 + ν 1 - β 2 + 2γL 2 A + 3γω D β 2 L 2 max np D E 1 n n i=1 z t i -w t i 2 + 3γω D (ω P + 1)β 2 L 2 max np D + ρθ + 16γL 2 B β 1 β + θ + 4ν 1 β + ω P + µω P E x t+1 -x t 2 + ρ(1 -p P ) + 2γL 2 B + 16γL 2 B p P β 1 + p P β E w t -x t 2 + µ(1 -p P ) + 2γL 2 A + 4νp P 1 + p P β + 4γω D p P β 2 L 2 max np D E 1 n n i=1 w t i -x t 2 .We now consider the coefficient of the term E ∥w t -x t ∥ 2 . Using the inequality xy ≤ x 2 +y 2 2 for all x, y ≥ 0, we getρ(1 -p P ) + 2γL 2 B + 16γL 2 B p P β 1 + p P β ≤ ρ(1 -p P ) + 16γL 2 B 1 + p P β + p 2 P β 2 ≤ ρ(1 -p P ) + 32γL 2 B 1 + p 2 P β 2 = ρ for ρ = 32γL 2 B 1 p P + p P β 2 .With this choice of ρ, we obtainE δ t+1 + κE   g t+1 - 1 n n i=1 ∇f i (z t+1 i ) 2   + ηE z t+1 -w t+1 2 + νE 1 n n i=1 z t+1 i -w t+1 i 2 + ρE w t+1 -x t+1 2 + µE 1 n n i=1 w t+1 i -x t+1 2 ≤ E δ t - γ 2 E ∇f (x t ) 2 - 1 2γ - L 2 E x t+1 -x t 2 + κE   g t - 1 n n i=1 ∇f i (z t i ) 2   + ηE z t -w t 2 + ρE w t -x t 2 + ν 1 - β 2 + 2γL 2 A + 3γω D β 2 L 2 max np D E 1 n n i=1 z t i -w t i 2 + 3γω D (ω P + 1)β 2 L 2 max np D + 32γL 2 B 1 p P + p P β 2 θ + 16γL 2 B β 1 β + θ + 4ν 1 β + ω P + µω P E x t+1 -x t 2 + µ(1 -p P ) + 2γL 2 A + 4νp P 1 + p P β + 4γω D p P β 2 L 2 max np D E 1 n n i=1 w t i -x t 2 .Next, taking ν =4γL 2 A β + 6γω D βL 2 max np D gives E δ t+1 + κE   g t+1 - 1 n n i=1 ∇f i (z t+1 i ) 2   + ηE z t+1 -w t+1 2 + νE 1 n n i=1 z t+1 i -w t+1 i 2 + ρE w t+1 -x t+1 2 + µE 1 n n i=1 w t+1 i -x t+1 2 ≤ E δ t - γ 2 E ∇f (x t ) 2 - 1 2γ - L 2 E x t+1 -x t 2 + κE   g t - 1 n n i=1 ∇f i (z t i ) 2   + ηE z t -w t 2 + ρE w t -x t 2 + νE 1 n n i=1 z t i -w t i 2 + 3γω D (ω P + 1)β 2 L 2 max np D + 32γL 2 B 1 p P + p P β 2 θ + 16γL 2 B β 1 β + θ + 4 4γL 2 A β + 6γω D βL 2 max np D 1 β + ω P + µω P E x t+1 -x t 2 + µ(1 -p P ) + 2γL 2 A + 4 4γL 2 A β + 6γω D βL 2 max np D p P 1 + p P β + 4γω D p P β 2 L 2 max np D E 1 n n i=1 w t i -x t 2 .Let us consider the last bracket:µ(1 -p P ) + 2γL 2 A + 4 4γL 2 A β + 6γω D βL 2 max np D p P 1 + p P β + 4γω D p P β 2 L 2 max np D = µ(1 -p P ) + 2γL 2 A + 16γp P L 2 A β + 24γω D p P βL 2 max np D + 16γp 2 P L 2 A β 2 + 24γω D p 2 P L 2 max np D + 4γω D p P β 2 L 2 max np D ≤ µ(1 -p P ) + 16γL 2 A 1 + p P β + p 2 P β 2 + 24γω D p P L 2 max np D β + p P + β 2 ≤ µ(1 -p P ) + 32γL 2 A 1 + p 2 P β 2 + 48γω D p P L 2 max np D (β + p P ) = µ for µ = 32γL 2 A 1 p P + p P β 2 + 48γω D L 2 max np D (β + p P ) .For this choice, we getE δ t+1 + κE   g t+1 - 1 n n i=1 ∇f i (z t+1 i ) 2   + ηE z t+1 -w t+1 2 + νE 1 n n i=1 z t+1 i -w t+1 i 2 + ρE w t+1 -x t+1 2 + µE 1 n n i=1 w t+1 i -x t+1 2 ≤ E δ t - γ 2 E ∇f (x t ) 2 - 1 2γ - L 2 E x t+1 -x t 2 + κE   g t - 1 n n i=1 ∇f i (z t i ) 2   + ηE z t -w t 2 + νE 1 n n i=1 z t i -w t i 2 + ρE w t -x t 2 + µE 1 n n i=1 w t i -x t 2 + 3γω D (ω P + 1)β 2 L 2 max np D + 32γL 2 B 1 p P + p P β 2 θ + 16γL 2 B β 1 β + θ + 4 4γL 2 A β + 6γω D βL 2 max np D 1 β + ω P + 32γω P L 2 A 1 p P + p P β 2 + 48γω D ω P L 2 max np D (β + p P ) E x t+1 -x t 2 .(31) Let us simplify the last bracket. I := 3γω D (ω P + 1)β 2 L 2 max np D + 32γL 2 B 1 p P + p P β 2 θ + 16γL 2 B β 1 β + θ + 4 4γL 2 A β += 144γ ω D ω P β np D + ω D (1 + ω P p P ) np D since (ω P +1)β 2 np D ≤ 1 np D + ω P β np D .Substituting these inequalities to ( 31) and ( 32), we getE δ t+1 + κE   g t+1 - 1 n n i=1 ∇f i (z t+1 i ) 2   + ηE z t+1 -w t+1 2 + νE 1 n n i=1 z t+1 i -w t+1 i 2 + ρE w t+1 -x t+1 2 + µE 1 n n i=1 w t+1 i -x t+1 2 ≤ E δ t - γ 2 E ∇f (x t ) 2 - 1 2γ - L 2 E x t+1 -x t 2 + κE   g t - 1 n n i=1 ∇f i (z t i ) 2   + ηE z t -w t 2 + νE 1 n n i=1 z t i -w t i 2 + ρE w t -x t 2 + µE 1 n n i=1 w t i -x t 2 + 144γ θ p P + 1 + θp P β 2 L 2 B + ω P p P + 1 + ω P p P β 2 L 2 A + ω D ω P β np D + ω D (1 + ω P p P ) np D L 2 max E x t+1 -x t 2 .By collecting all the terms w.r.t. E x t+1 -x t 2 , using the step size γ from the theorem and Lemma H.2, we obtainE Ψ t+1 = E δ t+1 + κE   g t+1 - 1 n n i=1 ∇f i (z t+1 i ) 2   + ηE z t+1 -w t+1 2 + νE 1 n n i=1 z t+1 i -w t+1 i 2 + ρE w t+1 -x t+1 2 + µE 1 n n i=1 w t+1 i -x t+1 2 ≤ E δ t - γ 2 E ∇f (x t ) 2 + κE   g t - 1 n n i=1 ∇f i (z t i ) 2   + ηE z t -w t 2 + νE 1 n n i=1 z t i -w t i 2 + ρE w t -x t 2 + µE 1 n n i=1 w t i -x t 2 = E Ψ t - γ 2 E ∇f (x t ) 2 .It remains to rearrange and sum the last inequality for t = 0, . . . , T -1.Corollary E.2. Let C t i ∈ P(0) for all i ∈ [n] (e.g. PermK), choose p P = 1/(ω P + 1), p D = 1/(ω D + 1) andβ = min n ω D ω P (ω D + 1) 1/3 , 1 .Then, in the view of Theorem E.1, the iteration complexity isO Ψ 0 ε L max + ω D ω P (ω D + 1) n 1/3 L max + ω D (ω D + 1) n L max + ω P (ω P + 1)L A .Proof. By Theorem E.1, up to a constant factor, the algorithm converges afterT := Ψ 0 ε L + θ p P + 1 + θp P β 2 L 2 B + ω P p P + 1 + ω P p P β 2 L 2 A + ω D ω P β np D + ω D (1 + ω P p P ) np D L 2 max = Ψ 0 ε L + 1 β 2 L 2 B + ω P p P + 1 + ω P p P β 2 L 2 A + ω D ω P β np D + ω D (1 + ω P p P ) np D L 2 max ≤ Ψ 0 ε L + L 2 B β 2 + ω P p P + 2 β 2 L 2 A + ω D ω P β np D + 2ω D np D L 2 max ≤ Ψ 0 ε L + L 2 B β 2 + ω P (ω P + 1) + 2 β 2 L 2 A + ω D ω P (ω D + 1)β n + 2ω D (ω D + 1) n L 2 max ≤ 2Ψ 0 ε   L + L 2 A + L 2 B β 2 + ω D ω P (ω D + 1)β n L 2 max + ω D (ω D + 1) n L 2 max + ω P (ω P + 1)L 2 A  iterations, where we use the choice of p P and p D . Using Lemma C.1, we haveL 2 A + L 2 B ≤ L 2 maxand henceT ≤ 2Ψ 0 ε L + 1 β 2 + ω D ω P (ω D + 1)β n L 2 max + ω D (ω D + 1) n L 2 max + ω P (ω P + 1)L 2 A ≤ 4Ψ 0 ε   L + 1 + ω D ω P (ω D + 1) n 2/3 L 2 max + ω D (ω D + 1) n L 2 max + ω P (ω P + 1)L 2 A   ≤ 8Ψ 0 ε L max + ω D ω P (ω D + 1) n 1/3 L max + ω D (ω D + 1) n L max + ω P (ω P + 1)L A ,where we substitute our choice of β.Corollary E.3. Let C t i be the PermK compressors and Q t i be the independent (Assumption 1.6) RandK compressors, both with K = d /n. Then, in the view of Corollary E.2, the iteration complexity isO Ψ 0 ε n 2/3 L max + nL A ,and the total communication complexity isO Ψ 0 ε dL max n 1/3 + dL A .Proof. The choice of compressors and parameters ensures that ω P = ω D = n -1 (Lemma A.6). Thus, the iteration complexity isO Ψ 0 ε L max + ω D ω P (ω D + 1) n 1/3 L max + ω D (ω D + 1) n L max + ω P (ω P + 1)L A = O Ψ 0 ε L max + n 2/3 L max + √ nL max + nL A = O Ψ 0 ε n 2/3 L max + nL A .Since p P = p D = 1/n and K = d/n, on average, the algorithm sends ≤ 2d n coordinates in both directions. Therefore, the total communication complexity isO d n × Ψ 0 ε n 2/3 L max + nL A = O Ψ 0 ε d n 1/3 L max + dL A . E.3 Polyak-Łojasiewicz condition E.3. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: Section F Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.This assumptions means that if an algorithm calls a compressor C at some points x1, . . . , xm, then C(x1), . . . , C(xm) are i.i.d.A notable exception form this rule is the MCM method (Philippenko and Dieuleveut, 2021) -see Appendix A.The general definition of PermK for d mod n ̸ = 0 is presented in(Szlendak et al., 2021)[App. I]. 
 
 Appendix:  


Decision: Unlike most papers in federated learning/distributed optimization, this paper studies the downlink communication cost (server to users). The paper presents a theoretical analysis on the required number communication rounds and shows that, under no assumption on the functions stored at the distributed workers, the communication cost cannot be improved with respect to a naive approach. But, if the hessian of the individual functions are "aligned", improvements in communication complexity can be achieved. In particular, they propose a downlink compression scheme called MARINA-P, which uses the interesting idea of sending correlated compression versions to the users. The reviewers agree that the paper provides a meaningful contribution in a relatively unexplored aspect of distributed optimization.

Reviews: review: paper_summary: paper_summary: This paper deals with the downlink (server-to-client) communication cost in federated learning (FL). The main motivation of the paper is to provide a theoretical analysis of the total communication cost with downlink compression. This is achieved considering unbiased or a certain class of biased lossy compression algorithms at the server. First, the authors present an impossibility result (i.e., a converse theorem), showing that faster than certain rate is not possible if the server employs an unbiased compressor (or biased compressor as specified in the paper). Then, they proposed a downlink compression method called MARINA-P, which achieves better iteration than those in the literature. This method, basically, transmits an uncompressed model with a small probability p to all the clients, while the compressed model update is transmitted otherwise. The main twist in the proposed scheme is to transmit different compressed versions to the clients, rather than sending the same compression. In particular, an orthogonal sparse subset of the parameters are sent to each client, so that they together can recover all the parameters. This way, each parameter is considered at least by one of the workers.  Here, the compressed versions transmitted to the users become correlated. The authors show that this correlated compression approach achieves the best convergence rate. Finally, they extend this framework by combining downlink compression with uplink compression using MARINA together with a momentum step.
strength_weakness: strength_weakness: I would say that the lack of any empirical results is the main weakness of the paper. While it is interesting to obtain the theoretical convergence guarantees, one also wonders how these three different compression schemes would perform in practice (for scenarios that satisfy the assumptions, as well as those that do not). 

Also, only sparsification type compression methods are considered. What about quantization? Can the arguments be easily extended to the case with quantization?
questions: questions: - While the authors have covered most of the relevant literature, as far as I'm aware, one missing paper that I am aware of is the following:

M. Mohammadi Amiri, D. Gündüz, S. R. Kulkarni, and H. V. Poor, "Federated Learning With Quantized Global Model Updates" arXiv preprint arXiv:2006.10672, Jun 2020. 

Here, not only the authors consider downlink communication, but they actually transmit different updates to different clients. Instead of compressing the difference with rest to the previous global model, here the authors compress the difference with respect to the model updated by the client. This way the gap to the new global model is potentially lower. I can't say how the convergence rates compare, but I would like the authors to comment on the pros/cons of this approach compared to their own. 

- How limiting is the assumption that the calls to the compressor are independent? There are some works in the literature that consider time-correlated sparsification, and show improved results (which also makes sense as the sparsity pattern should not change drastically from one iteration to the next). Please provide some comments in the paper if this may be a significant limitation on the practical performance of the considered class of compressors.
limitations: limitations: As mentioned above: 
- lack of numerical comparisons,
- one missing reference
paper_summary: paper_summary: This paper addresses optimizing server-to-worker communication in distributed optimization by introducing MARINA-P, a novel method using correlated compressors for downlink compression. The study identifies inefficiencies in current downlink compression approaches and shows that MARINA-P can reduce communication complexity as the number of workers increases. Additionally, MARINA-P serves as a foundation for bidirectional compression methods. The paper also presents M3, which combines MARINA-P with uplink compression and a momentum step, further improving total communication complexity. Both theoretical analyses and empirical experiments validate the efficiency of the proposed algorithms.
strength_weakness: strength_weakness: The compressor model (Definition 1.4), while standard in the federated learning literature, is somewhat contrived. It is primarily defined in its current form to facilitate analysis. It remains unclear whether the main conclusions derived under this model can be directly translated to the information-theoretic setting (quantization plus entropy coding), where compression efficiency is measured in terms of bits per sample.
questions: questions: The role of L_B is not completely clear, as it does not prominently affect communication complexities compared to L_A. Is it that by isolating L_B from L_A, one can effectively reduce L_A  and, consequently, the communication complexities as well? Moreover, the class of functions for which L_B is known to be positive is quite restricted (Theorem 4.5). It would be beneficial to find more general examples.
limitations: limitations: The paper does not explicitly address its limitations. The only related point is that the proposed method does not consistently outperform the CORE method by Yue et al. (2023) in terms of performance (p. 8).
paper_summary: paper_summary: This paper presents methods to improve communication efficiency in distributed optimization, particularly focusing on the server-to-worker (s2w) communication costs, which are often overlooked. The authors first present a lower bound on the required round of communication.  They used it to state that under no assumption between the individual functions stored at the distributed workers, the s2w communication loads can not be improved compared to the naive design. Then, the authors provide an algorithm and analysis showing that when the hessian of the individual functions are similar or aligned, improvements in communication complexity can be achieved.
strength_weakness: strength_weakness: 1. The authors use the lower bound on the rounds communication to claim a lower bound on the communication load. However, there is a gap in this argument: The authors state that since the rounds of communication are lower bounded by a certain function, the overall communication load is lower bounded by d times that function, given that the full gradient contains d entries. But if a compressor is used as assumed by the authors, where the server can deliver an unbiased function that has fewer entries, it is totally possible that the communication load is smaller than d times the rounds of communication, violating this claimed bound. 

Therefore, I have to suggest a weak rejection. I'm happy to raise my score if this issue can be appropriately fixed.

2. The concept of functional $(L_A, L_B)$ inequality can be simplified since only L_A is used in the main results. It can be stated such as the functions satisfy an $L_A$ condition, if we can find $L_B$ such that ineq. (9) is satisfied.
questions: questions: Is there any connection between $L_A$ and the Hessians of the individual functions, similar to the smoothness parameter $L$, which can be interpreted as the largest eigenvalue of the Hessian of f?
limitations: limitations: See weekness
paper_summary: paper_summary: Differently from other papers in the field of federated learning, the authors consider the problem of uplink compression - from the server to the workers. The main contributions of the paper are MARINA-P and its variants. These optimization schemes leverage PermK sparsification to reduce the communication complexity in the uplink. When combined with momentum, MARINA-P achieves a total communication complexity that, in the case of $n>>1$ and for close-to-homogeneous clients, is smaller than competing state-of-the-art alternatives.
strength_weakness: strength_weakness: - The main weakness of the paper is the assumption of data homogeneity. While I understand that this assumption is necessary, it would be interesting to include experimental evidence in the main text showing how MARINA-P performs with heterogeneous data.
- The following might be erroneous, but to me seems like that the overall number of coordinates sent in the uplink is $d$. From the discussion in Section 4.5 it seems like that the parameter vector is permuted and divided into non-overlapping chunks, and each chunk is sent to a different client. As such, it looks like that the \emph{overall} number of coordinates sent to the server is $d$.
questions: questions: - Related to my previous point, how many coordinates are sent into the uplink at each round from the server to all users? i.e. what is the support of $\sum^n_{i=1} \mathcal{C}_i(x)$?
- Is MARINA-P compatible with client selection? Meaning, is it possible to apply MARINA-P if, at each round, the number of users varies or a different subset is chosen?
- Would it be possible to compare MARINA-P to other state-of-the-art schemes that use masking to reduce communication (e.g., SPARSE RANDOM NETWORKS FOR COMMUNICATION-EFFICIENT FEDERATED LEARNING)?"
limitations: limitations: Limitations are adequately discussed in the text.

Comments: comment: I have read the authors’s response and the proposed revision would address my earlier concern. I have raised my score for the manuscript.
I have read all the reviews and the authors' responses. I thank the authors for the detailed explanations. I believe it is a solid contribution on a relatively less explored aspect of distributed learning. The techniques are not necessarily new, but I think their application is rigorous and seems correct. I retain my original score.
I am happy with the authors's response and will keep my original score.
Thank you for the question.

We agree that the number of bits that the server produces on the way out is the same in both cases. However, the number of bits that the server sends to *one worker* will be different. For MARINA-P with PermK, it is $d / n$ instead of $d.$ In Definition 1.3, we say "The server-to-worker (s2w) communication complexity of a method is the expected number of coordinates/floats the server sends to **a worker** to find an $\varepsilon$–solution." This definition is consistent with the fact that the downlink communication issue stems from the clients' download speed. Hence, the critical factor is the size of the message each client receives.
 
To clarify further, imagine a tree (graph) with a central node (server) and $n$ child nodes (clients). Each worker is connected to the server by a unique edge. In this setup, the server-to-worker (s2w) communication complexity of a method is measured by the expected number of coordinates/floats the main node transmits through each edge to each of the connected workers. 

We hope this answers your question. If you have any more, please do not hesitate to ask.
First, we would like to thank the reviewer for a quick response!

We still believe that there is no mathematical gap in our assertions, as the sentence _This result gives no hope for improving the communication complexity (2) in the worst case_ is not a strong mathematical statement. What we intended to say is that _This result **indicates** it is not possible to improve the communication complexity (2) in the worst case_, which means that while we cannot be certain the bound is impossible to break with *any technique*, it is definitely not possible with approaches like the Rand$K$ compressor due the lower bound theorem.

Nevertheless, we agree that this can lead to misunderstandings. Therefore, we propose to rewrite the contributions section in the following way (changes are in **bold**):

1. We start by proving the impossibility of devising a method where the server communicates with the workers using unbiased compressors $\mathbb{U}(\omega)$ (or biased compressors from Section B) and achieves an iteration rate faster than $\Omega\left(\frac{(\omega + 1) L \delta^0}{\varepsilon}\right)$ (Theorem 3.1) under Assumptions 1.1, 1.2, and 1.6. 
~~**This result gives no hope for improving the communication complexity (2) in the worst case**~~. 
**This result provides a lower bound for any method that applies such compressors to vectors sent from the server to the workers in every iteration. Moreover, we prove a more general iteration lower bound of
$\Omega\left(\frac{(\omega + 1)L \delta^0}{\varepsilon}\right)$ for all methods where the server zeroes out a coordinate with probability $1 / (\omega + 1)$ (see Remark 3.2).**
2. In view of this results, it is clear that an extra assumption is needed to break the lower bound $\Omega\left(\frac{(\omega + 1) L \delta^0}{\varepsilon}\right).$ In response, we introduce a novel assumption termed "Functional $(L_A, L_B)$ Inequality" (see Assumption 4.2). We prove that this assumption is relatively weak and holds, for instance, under the local smoothness of the functions $f_i$ (see Assumption 1.5).
3. We develop a new method for downlink compression, MARINA-P, and show that, under our new assumption, **along with Assumptions 1.1, 1.2 and 1.6, it can achieve the iteration rate of**
\begin{align*}
    \textstyle O\left(\frac{\delta^0 L}{\varepsilon} + \frac{\delta^0 L_A (\omega + 1)}{\varepsilon} + \frac{\delta^0 L_B (\omega + 1)}{\varepsilon \sqrt{n}}\right).
\end{align*}
**(see Theorem D.1 with $p = 1 / (\omega + 1)$ + Lemma A.5)**.
Notably, when $L_A$ is small and $n \gg 1,$ this **iteration** complexity is provably superior to **$\Theta(\frac{\delta^0 L (\omega + 1)}{\varepsilon})$** and the complexities of the previous compressed methods. In this context, $L_A$ serves as a measure of the similarity between the functions $f_i$, and can be bounded by the ``variance'' of the Hessians of the functions $f_i$ (see Theorem 4.8). Thus, MARINA-P is the first method whose **iteration** complexity can provably improve with the number of workers $n$.
4. **Moreover, MARINA-P can achieve the s2w communication complexity of**
\begin{align*}
    \textstyle O\left(\frac{d \delta^0 L}{n \varepsilon} + \frac{d \delta^0 L_A}{\varepsilon}\right).
\end{align*}
**When $L_A$ is small and $n \gg 1,$ this communication complexity is provably superior to (2) and the communication complexities of the previous compressed methods.**
5. Our theoretical improvements can be combined with techniques enhancing the w2s communication complexities. In particular, by combining MARINA-P with MARINA (Gorbunov et al., 2021) and adding the crucial momentum step, we develop a new method, M3, that guarantees a total communication complexity (s2w + w2s) of
\begin{align*}
    \textstyle O\left(\frac{d \delta^0 L_{\max}}{n^{1/3} \varepsilon} + \frac{d \delta^0 L_A}{\varepsilon}\right).
\end{align*}
When $n > 1$ and in the close-to-homogeneous regime, i.e., when $L_A$ is small, this **communication** complexity is better than (2) and the complexities of the previous bidirectionally compressed methods.
6. Our theoretical results are supported by numerical experiments (see Section F).

Additionally, we will change Lines 122-123 to "Let us first investigate the possibility of improving the iteration complexity $O\left(\frac{(\omega + 1)\delta^0 L}{\varepsilon}\right)$ under Assumptions 1.1, 1.2, and 1.6."

These extra 4-5 sentences fully resolve any potential misunderstandings and clarify our contributions. These are very minor adjustments that can be easily incorporated into the camera-ready version of the paper.

We believe that we have resolved the concerns and will happily answer any additional questions.
Thank you for your detailed response! Regarding the number of bits sent by the server to the workers: The channel from the server to the workers is broadcast, meaning that whatever the server transmits is received by all workers. Therefore, whether the server sends the same vector to all devices (as normally done) or sending different chunks of the vector to different device (as in MARINA-P), the number of bits and communication cost remain the same. Could you clarify under which communication model MARINA-P is more efficient?
I have read the reviewer's response. Let me first clarify that my comment on the gap is due to the statements in the contributions in Section 2 rather than Section 3. The first contribution states: "This result gives no hope for improving the communication complexity (2) in the worst case." but the worst case in equation (2) refers to the communication cost instead of rounds of communication, i.e., $d\delta^0L/\epsilon$ vs the $(\omega+1)\delta^0L/\epsilon$ in the manuscript. This difference is precisely where the gap happens and the only way to make sense of it is to have a lower bound on communication cost rather than the rounds of communication. 

Similarly, the second main contribution in Section 2 uses the $(\omega+1)\delta^0L/\epsilon$ lower bound to provide a motivation to introduce extra assumptions, but the third main contribution again shows an upper bound in communication complexity, so the same gap happens. 

As explained by the author, the attempt to bridge this gap is different but similar to the spirit of the example provided by the reviewer, which is to take some "worst cases" over the designs rather than the problem scenarios. I believe we can agree that this is not a convincing argument, as the author's response clarified this is not proof as well. However, the issue of the manuscript is that by reading Section 2, it hints at the opposite, as explained above. For clarity and readability, the reviewer recommends the authors revise related statements to ensure that all claims in the paper exactly reflect the technical contributions.