Distributed Optimization for Overparameterized Problems: Achieving Optimal Dimension Independent Communication Complexity
Authors: Bingqing Song
Ioannis Tsaknakis
Chung-Yiu Yau
Hoi To Wai
Mingyi Hong
Venue: NeurIPS 2022 Accept (2022)
Keywords: Distributed Optimization
Overparameterized Problem
Quantization

Abstract: Decentralized optimization are playing an important role in applications such as training large machine learning models, among others. Despite its superior practical performance, there has been some lack of fundamental understanding about its theoretical properties. In this work, we address the following open research question: To train an overparameterized model over a set of distributed nodes, what is the {\it minimum} communication overhead (in terms of the bits got exchanged) that the system needs to sustain, while still achieving (near) zero training loss? We show that for a class of overparameterized models where the number of parameters $D$ is much larger than the total data samples $N$, the best possible communication complexity is ${\Omega}(N)$, which is independent of the problem dimension $D$. Further, for a few specific overparameterized models (i.e., the linear regression, and certain multi-layer neural network with one wide layer), we develop a set of algorithms which uses certain linear compression followed by adaptive quantization, and show that they achieve dimension independent, and sometimes near optimal, communication complexity. To our knowledge, this is the first time that dimension independent communication complexity has been shown for distributed optimization.

Distributed Optimization for Overparameterized
Problems: Achieving Optimal Dimension Independent Communication Complexity
Bingqing Song Department of ECE University of Minnesota email: song04096umn. edu
loannis Tsaknakis Department of ECE University of Minnesota email: tsakn001 @umn
Chung-Yin Yiu Yau Department of SEEM
Hoi-To Wai Department of SEEM Chinese University Hong Kong email :etl::hhwwiiio.m @cuhk edu hk
Chinese University of Hong Kong email: cyyaudse. cuhk. edu. hk
Mingyi Hong Department of ECE University of Minnesota email :mhonggumn... edu
Abstract
Decentralized optimization are playing an important role in applications such training large machine learning models, among others. Despite its superior practical performance, there has been some lack fundamental understanding about its theoretical properties. In this work, we address the following open research question: To train an overparameterized model over set of distributed nodes, what is the minimumm communication overhead (in terms of the bits got exchanged) that the system needs to sustain, while still achieving (near) zero training loss? We show that for a class of overparameterized models where the number of parameters D is much larger than the total data samples N, the best possible communication complexity (2V), which independent of the problem dimension D. Further, for few specific overparameterized models (i.e., the linear regression, and certain multi-layer neural network with one wide layer), we develop a set of algorithms which uses certain linear compression followed by adaptive quantization, and show that they achieve dimension independent, near-optimal communication complexity. To our knowledge, this is the first time that dimension independent communication complexity has been shown for distributed optimization.
Introduction
The research of decentraalized/diisribueee optimization has recently gained tremendous momentum, partly due to the fact that a well-designed decenntralizedddisttibue algorithm is capble of training large-scale machine learning models, by utilizing massively distributed computation and data re- sources. In a typical decentralized optimization setting, multiple local agents hold small to moderately sized datasets, and they collaborate by iteratively solving their local problems while sharing some information with other agents. The majority of the state-of-the-an dissribuueed/deeemrraiize optimiza- tion algorithms deeply rooted in classical consensus-bai and Luo, 1987], where the agents repetitively share the local optimization variables, or the gradients of local functions, so reach an optimal consensual solution.
approaches [Tsitsiklis, 1984, Tsitsiklis
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

It is important to note that in those classical settings, the agents typically solve small-scale problems where the problem dimension (i.e., the dimension of the optimization variable, and the gradients) is relatively small (e.g., in the order of hundreds or thousands). Therefore, it is reasonable that the agents should iteratively share their local parameters/gradients to improve the quality of the models. However, many modern learning models are in the overparameterized regime with very high-dimensional parameters [He et al., 2016, Vaswani et al., 2017], such as deep and/or wide neural networks. This practice poses some significant challenges to the classical consensus-based approaches, because by directly sharing the model parameters and/or gradients, the communication burden increases as problem size increases.
line of recent works have been developed, which adopt strategies such as gradient/model compres- sion, lazy communication, etc, and they are able to significantly reduce the overall communication complexities [Xu et al., 2020, Sun et al., 2020, Li et al., 2019, Karimireddy et al., 2019]. few works focus on designing compressors [Safaryan et al., 2020, Horváth et al., 2019, Beznosikov et al., 2020, Konečný et al., 2016, Safaryan et al., 2021] Although the majority of these works are able to reduce per round communication burden, it is by no means clear if, to achieve certain solution quality, the total amount of communication can be saved. In fact, it has been shown in [Arjevani and Shamir, 2015], that the total communication achievable is dependent on the problem dimension, which could be huge. More importantly, there is a general lack of fundamental understanding about the performance limits for decentralized and distributed optimization, when the models are 'large'. Without such characterization, it is by no means clear if the existing algorithms are optimal in reducing the communication complexities.
In this work, we focus on distributed optimization for 'large' machine learning models (i.e., overpa- rameterized problems, to be defined shortly), and we ask the following question:
What is the best possible communication complexity (in terms of number of bits needed to obtain certain solution accuracy), achievable by any distributed algorithms for a class of overparameterizeed problems? Which class of algorithms achieves such complexity bounds?
Related Works A number of recent works are devoted to reducing the communication cost in distributee/ddeenntraiized optimization by combining the optimization algorithms with compression, e.g.. sparsificiiat,n,, quantization, etc. For the distributed setting with the server-worker architecture, relevant works include [Alistarh et al., 2017, Wen et al., 2017, Wang et al., 2018, Bernstein et al., 2018, Haddadpour et al., 2021, Mishchenko et al., 2019, Gorbunov et al., 2021]; see [Richtárik et al., 2021] for a recent survey. For the decentralized setting without a central server, recent works such as [Koloskova et al., 2019, Reisizadeh et al., 2019, Tang et al., 2018, Vogels et al., 2020, Magnússon et al., 2020] proposed algorithms that utilize error compensation, low-rank compression, etc. While they have demonstrated appealing performance in practice, the theoretical guarantees do not scale for overparameterized problems. For instance, [Koloskova et al., 2019] showed an O + 1/ ? iteration complexity upper bound for their algorithm. The quantity 1/w is the compressor parameter which is at least D(VD), where D is the problem dimension.
Lower communication complexity bounds for distributed optimization problems have been studied since the 1980s. There are two major categories of lower bound results in literature depending on how we count the "communication" required to reach a solution of given accuracy, i.e., 1) in terms of the number of communication rounds, or 2) in terms of the number of bits got communicated. The first category is not directly related to the current work; we refer to readers to Appendix A for discussions. In second category, the first lower bound is given in [T and Luo, 1987] where the authors consider a distributed setting with two nodes and provide a Q (D log (D/e)) bound for the class of quadratic objectives, where is the solution accuracy, and D is the variable dimension. In [Zhang ct al., 2013] lower communication bounds are derived for certain statistical estimation tasks, such as linear and probit regression. Moreover, in [Vempala et al., 2020] the communication complexity of several distributed optimization tasks is studied, including Ep regression, linear, semidefinite and convex optimization. In [Korhonen and Alistarh, 202 I]. an 52 (KD log (D/e)) bound is derived for quadratic problems on a multi-node setting, for both deterministic and randomized protocols, where K is the number of clients.
Recently, overparameterized problem has drawn great research interests. has been showed that re- markable performance can be achieved with overparameterized networks [Jacot et al., 2018, Du et al., 2019, Allen-Zhu et al., 2019]. Some recent works study the overparameterization of decentralized problems, which guarantee the global convergence [Huang et al., 2021, Deng et al., 2022]. However,
2

---

the high communication cost caused by the large model is a key problem in decentralized algorithm. For example, the ReLU fully connected networks designed in the aforementioned two works are of widths (2N and 52 (((N1)) respectively, where N is the number of data samples available.
Contributions. This work addresses both questions in (Q). The contributions are highlighted below:
(i) Regarding to the best possible communication complexity (i.c., the communication complexity lower bound), we first show that for class of Polyak-Lojasiewe
(PL) problems, the communication which is similar to the known results for strongly convex problems.
lower bound is Ω D log(D) Further, we show that for a class of overparameterized models where the loss function is composition of a quadratic problem and some nonlinear functions, and that the number of parameters D is much larger than the total data samples N, the communication complexity lower bound becomes 2 K N log( /)),, which is independent of the problem dimension D.
(ii) We develop a distributed algorithm which can be used to optimize both classes of problems, in the setting where multiple clients are coordinated by a server. We show that the lower bound for the PL problem can be matched; while by using certain linear random compresiionddccoprestti scheme, followed by adaptive quantization, the lower bound for the overparameterized problem can be matched (up to log(D) factor) for two of its important special cases, i.e., linear regression, and certain multi-layer neural network with one wide layer. Further, we show that the proposed algorithm can be extended to a fully decentralized setting without the coordination of server.
To our knowledge, these are the first set of results that attempt to comprehensively address the issue of optimal communication complexities for overparameterized problems. We expect that results provided in this work will open doors for understanding more complex communication-efiee distributed algorithms, as well as larger classes of overparameterized problems.
2 The System Model
Consider a system having K distributed agents, and total of N samples {(X,, y:) Suppose each agent has N₂ data samples, with Ek= k=1 N₂ = N; let set 24 (resp. V&) collect agent k's data samples (resp. labels). They cooperatively solve an optimization problem of the following form:
min BEG
1(0:X:3)) = Σ (e,
where L : + is the local loss function for agent k; 0 the optimization variable, whose domain is θ C R.P For notational simplicity, we will ignore the reference for the data samples X, and Xg. 1/. whenever possible, i.c., we will write f(0) and f& (0) as the global and local loss functions.
Throughout the paper, we will consider a few special cases of (I), where the local function f& 's are overparameterized. The first of such problem class is referred to as the distributed PL problems. To introduce this class, let us provide few assumptions. Assumption 1. The local objective functions satisfy:
2psx (f) (0 & ( A V0, A Vk,
where 0x)) is a global minimum of (-): pk's 's some positive constants.
Assumption 2. There exists positive constants Lg 's and L, 2 1 such that:
(0) V fa (0')ll < La 110 0'1. [V - f (0')lI s 0'11, V0,0', V
Note that (2) is the so-called PL assumption, which was introduced in [Polyak, 1963]. It is weaker than strong convexity, while can still be used to ensure the linear convergence of gradient descent. It is also less restrictive than several other related conditions under which linear global convergence can be derived, such as the restricted secant inequality [Karmmi et al., 2016). The second inequality in (2) has also been used in the literature; see, e.g., [Oymak and Soltanolkotabi, 2019], in which such a bound for overparameterized network has been showed. Assumption 2 is the standard Lipschitz gradient condition.
Definition (Distributed PL problems). Consider problems of the form (1). Define:
K
Cp
[(0)
Σ
(O) (0( satisfies Assumptions 1 2, 2, V à E [K]
3

---

The second class of problems is referred to as the distributed overparameterized problem, where the loss function is a composition of least square loss and non-linear function. This form of loss function often appears in analyzing neural networks, see, e.g., [Oymak and Soltanolkotabi, 2019]. Definition 2 (Distributed overparameterized problems). Consider problems of the form (1). Define functions G+(-)= : : IN and constants by E RR N for all k. We call GR(-) overparameterized if for every by E TR,,Nx, there exists O E A such that G (0) by- Define the following class of problems:
K
Cop
[10)
Σ (0), (0) h=1
2 _ bu 11 Gz(.): - 12 overparameterized,
3 Communication Complexity Lower Bounds for Deterministic Algorithms
In this section we derive the communication complexity lower bounds for classes Cup and Cpl- Throughout this section and the paper, our focus is given to deterministic algorithms where no randomness is involved. All the proofs for results presented in this section are given in Appendix B.
We start with description of the coordinator model (also see [Braverman et al., 2013, Korhonen and Alistarh, 2021J), which will be used later as the basis of our derivation. Consider a set of K distinct nodes/agents, and a single coordinator node. Each node and the coordinator have a two-way communication channel, over which binary messages are exchanged. Consider a class of problems C of the form (I), that is f(0) >E' 2== (o). where each node k has access only to objective f0) Moreover, let II be a set protocols that are executed over the coordinator model. Then, given problem class C, a protocol π E II(e) takes as input problem E C, performs number of message exchanges (over the coordinator model), and outputs an 6-approximate solution Ø @ of problem (I). That is, the output 8 satisfies (where H" is point where the exact minimum is attained):
f(0*) S f(0) S f(0))+ +
Next, let us look at ı in more detail. We assume that for π E II()). it performs T(c) rounds of communication and computation, where during each round the following steps are carried out:
At round t 0, each agent/node k is given input the local objective fx (e.g., the data samples Xg. V%. assigned to each node);
At round 1 S t T(c).
The coordinator sends message m
c E {0, 1} to some node k.
(t)
Node lt sends message -- E (0, 1) to the coordinator.
(t)
At the final round (e)) the coordinator outputs an e-approximate solution.
Next, we define the communication complexity of the distributed protocol. Let us denote the total number of bits exchanged under protocol π, for problem e E C, as M ग., e); Use the following definition, which has been used extensively in related works such as [Tsitsiklis and Luo, 1987].
Definition 3 (Communication complexity). The communication complexity of protocol π over problem class C is defined as the maximum number of bits exchanged across the problems in C, i.e. M(C, c)) = maxeec Mc, π, Also, the communication complexity of problem class C. is the minimum communication complexity across all protocols that solve C, iee.
((C,))
-in (C, min max M ((c, e)). =EIl(()
xell(() CEC
Next, we derive communication complexity lower bounds for certain problem classes Our construction strategies follow those from [Korhonen and Alistarh, 2021]. that is, we will reduce a problem with known communication complexity, hard problem instances within classes of our interest. The main difference from the aforementioned work (which only deals with quadratic problems) is that, we need to construct hard PL and overparameterized problems instances.
Below we derive communication complexity lower bounds for the class of deterministic distributed problems where the local loss functions belong to the class of PL functions defined in Def. 1.
Theorem 3.1. Consider the problem class Cpt with given parameters K, D, for which it holds that 2 Q(1). Then we have M (Cpl. e) Ω(K D log (2)).

---

Note that the condition D/c = 92(1) is reasonable since we will mainly focus on the regime where D large. Next we consider Cop. We have the following communication complexity lower bound.
Theorem 3.2. Consider the problem class Cop, with given parameters K, D, e. for which it holds NN(KNNoo (2))
that N (2) Then we have that M (Cop.
Clearly, the lower bound for class Cop does not explicitly depend on the problem dimension D, while that for the Cpi does. This appears to be reasonable, partly because in the class of Cp1 the number of data samples N has not been explicitly modeled. Nevertheless, at this point it is not clear if such dimension inmtensioon-ndepeddeen lower bound is tight not, because match such a lower bound. To our knowledge, these are the first set of results that characterize the communication complexity for the classes Cpi and Cop: and they will serve to guide our subsequent algorithm development and analysis.
yet to find algorithm to
Algorithms Achieving the Optimal Communication Complexities
In this section, we design algorithms and analyze the achievable communication complexities, for the PL and the overparameterized problems in Def. 1 and 2. We will begin with the simple setting where all the agents are connected to a coordinator, and then extend to the case where the agents are decentralized. Throughout this section, for simplicity of exposition, we will assume that e = R.P.
Let us begin with a generic algorithm to deal with the server-agent setting. The algorithm is an adaptation of the classical quantize-then-cont then-communicate strategy ['Tiitikkiis and Luo, 1987, Magnússon al., 2020]. At each iteration, each agent first computes its gradient, followed by certain adaptive quantization scheme, before getting transmitted to the collaborating agents.
Specifically, at I-th iteration, each agent uses function F RRD RH# to compress the local gradient; Then the output is quantized as of. E R" (use the method in Def. 4). Each agent then shares of to the server, and the aggregated q' broadcast all agents. Each agent then uses function F: R + RD to process the received vector, and updates the local parameters. One key difference compared with [Tsitsiklis and Luo, 1987, Magnússon et al., 2020] is that, the algorithm uses a pair of compression and decompression functions F(.) and F(-) to process the gradients transmiited/received. We will see shortly that such a pair plays an important role in matching the lower bound. For the detailed steps, Algorithm below.
Algorithm Limited Communication Distributed Optimization Algorithm
1: Initialize: Fix F() and F(.). 7 > 0, 7 E R2, b Z4; set 02 = 00, choose of which can be represented by by bits for each entry, such thatllg F(V some constant independent of D.
(00)
C-DVVK' where C is
2: for f = 0, 1, do
K
-0-00(n( 3: Update: Each agent updates 0++1=00- =
nT(
Σ k=1
w) set gc+1 = =
4: Compute: The function of gradient of each agent 0k .+1 = F(V (1
5: Quantize: Each agent quantizes gf quant(g)
(g -t. 7., b). defined in Def. 4:
++1
6: Communicate: Each agent sends 9 the server;
7: Aggregation: The server collects q (ui 12
8: Broadcast: The server broadcasts q = (gl 92
1+1 2+1
to each agent;
9: end for
10: Return: Parameters AT.
In Algorithm 1, we note that as long as the initial solution 0 the same among all the agents, then 0 computed in the 'Update" step will always be the same across the agents. This is the reason that we can directly set 06+1 as 0t+1, Subsequently we will extend this algorithm to a fully decentralized setting, where precise consensus is no longer required. We choose the quantization method for the first iteration defined in Appendix C. In the subsequent iterations, we use the following adaptive quantization scheme; also see [Magnússon et al., 2020].
5

---

Definition 4. Fix E R, and let E N be an positive integer. Let quant: R x xR" x xR_ XN + R" be the quantization function defined component-wise as follows, where 8(r, := r/ (2 - 1). 6(r, b)
Pj Pj tr Pj r 25(r; c +r+00t))
if S 0j +r
(q,,n
if c otherwise.
8(r,b)
(6(r,b)
Essentially, the quantization scheme searches for a closest point on the grid (which has width 2r and is centered p (pI,...,PH)) The distance between the neighbor points on the grid is 0(r b).
Lemma 4.1. Fix p E IR tthn for all R Q E IR DxH such that ||c - pll.o S have
||quant (c,p,r, cllo 2
||Q quant (c,p.r,b--Q celo S 2 -1
4.1 Communication Complexity Upper Bounds for Cpi
We will begin with analyzing the class of problem Cpl. as defined in Def. 1, Before we proceed, let us make an additional assumption.
Assumption 3. Assume that each sa(.) is non-negative in its domain; Further, assume that the optimal objective value for problem (1) is zero, that is, there exists 0 E D such that f(00) = O.
The above 'zero loss' assumption has been used by a number of recent works to characterize problems with large number of parameters, e.g., in overparameterized neural network [Liu et al., 2022, Nguyen and Mondelli, 2020]; in optimization literature, this assumption is also used to improve the analysis of gradient- based algorithms; see, e.g. [Razaviyayn et al., 2019].
Lemma 4.2. Suppose Assumption 2 - 3 are satisfied, then we have the following inequality:
fV) & 2L f(0), A 0.
The above lemma shows that together with the PL condition, Assumptions 2, 3 imply:
2p. - (()) < [()) < 2T. f(0), VO
For convenience, throughout our analysis we set μ 1,
We will refer to the class of problems satisfying Assumption 1 as Eop. We note that Ep is strict subset of the class Cpl- Next, let us present our result for Cpt. The proof can be found in Appendix C. Theorem 4.1. Suppose Assumptions 3 are satisfied. Consider using Alg. I solve Cpti set
= ( .-=
-1 b,b= (-CCDD
max (logs(VCD + 1), F(x) = F(x) = x,
and C == max (V 16L/ Lå /M, 100). Then the following holds true:
f 1 s (1-1/(BL3) f (8'), 0,10
Further, to compule an e-optimal solution satisfying (3), each agent is required to transmit:
8b D 1 -e-'' L log(S (09))e bits/agent.
The quantization strategy at the first iteration (in Appendix C) requires by to be O [og(D)), conclude = O (ogg Thus Theorem 4.1 gives the total communication complexity for each agent as (olg (og())), which matches the lower bound in Theorem 3.1, up to a gap log(D).
4.2 Communication Complexity Upper Bounds for Cup
Next, we develop algorithms for the distributed overparameterized problem defined in Def. 2. Note that functions in the class Cap can be non-convex, therefore one may not be able to find an algorithm that can solve the entire class of problems in polynomial time. Our strategy is to identify special cases of Cop for which the analysis possible. Again, although these problems are restrictions of Cap- we do not expect the lower bound in Theorem 3.2 to be improved in either the dependency on N or e.

---

The Case for Quadratic Problems. Towards this end. let us consider an overparameterized quadratic
problem. To proceed, assume that each agent k has data tuple (Ag, by) with N₁ samples, where Ag R.NEXD is the feature matrix, and by E TR-Next is the label. Denote A == [A1;-..; Ax] E NRDD
where N -k=1 Nr. Suppose N < D. Then the generic problem (1) reduces to:
1 f(x) 2 A1 - =11²= 2 Σ
1| - ball".
(4)
Assuming that each Ag has full row rank, then the above problem is special case of Cop.
Next, we specialize Alg. 1. Recall that the lower bound derived in Theorem 3.2 is independent of D, so we cannot directly apply the algorithm we used for the class Cp.. in which each agent transmits a dimension D vector at every iteration. To proceed, let us consider the following linear compression scheme, in which we use a matrix B of size H x D to compress (resp. decompress) the gradients that get transmitted (resp. received), where H is fixed positive constant satisfying N < H particular, let us specialize the two processing operators in Alg. I as: F(x) Br, F(y)
< D. In
B y.
Further, define maax(-) and muin (-) (resp. (-ax(() and smin (-)) as the largest and smallest eigenvalues (resp. singular values) for a matrix. Then we have the following result; see Appendix D for proof.
Theorem 4.2. Consider using Alg. to solve the quadratic problem (4), with A being full row rank. Choose B such that rank (BA) N; set 1)-
2mim2) set b and C according to (30), and choose
(Z)i
F()) and F-)) as F(x) Bx, Fly) = B y. Then the following holds true:
f(0* s (1 - 10-k1/))) )
where i. is the condition number of the matrix Z == AB BAT given by s(Z) Tmax! ( to compute an c-optimal solution (3), each agent is required to transmit:
Janan (2) Further,
2b x² H (0)))(())/e) bitslagent.
(5)
In Theorem 4.2, it required that matrix BAT full rank, and this can be satisfied with probability 1 if we choose B to be random matrix. Further, the convergence rate depends on the condition number x xZZ). Although we have showed the per iteration communication cost can be reduced H by linear compression, it is not clear yet whether the dimension D can affect the value of x(Z). In the following, we show x(Z) is independent of D; The proof can be found Appendix
Proposition 1. Consider the matrices A and in Theorem 4.2, and define == AB BAT, Suppose i.dd NO 1), Y [H],j E [D]. Then the following holds:
each entry in B satisfies BRg
(I) The condition number is ()) is independent of D.
(2) Let AT = VEW be the compact form of SVD, where V E D satisfies VTV INi
Σ RNNN the diagonal matrix whose diagonal entries are singular values of A; and W E NNNN
is a unitary matrix. Then for any fixed A, we have
Smax (2) Smin (Σ)
VH VH+VNN VN + VH -N
)) 21 21-6
P x(Z) &
Proposition implies that, as long the compression matrix is standard normal, then (()) is independent of D. This means that the total bits required for each agent, as provided in (8), will only be dependent on N, H and log(f()))/e). but not on D. To further understand the dependency of k(Z) with N and H, let us treat the ratio between the largest and smallest singular values as
being fixed! !. Then set 2e R2/2 = 8 > 0, we have t = 22log()), so the upper bound for k
becomes <(AAT) VT+VN / log 3)
Assuming that N 4t2, 11 4N, then we can conclude
VB VN- /2 (o)
that (((((Z) < 49) > 1 1 8. Applying this result to (8), we can conclude that with probability 1 - 5, the total number of bits transmitted by each agent is 8b x*(AAA)
log(s(0")/e, Similarly in Theorem 4.1, b is in the order of O(log D)) (see Appendix C.). Therefore the total communication complexity of each agent can be reduced to O H log( D) log( ()) When H = @(N), then the complexity bound matches the lower bound in Theorem 3.2, up to a gap Ollog())) Additionally,
'This is reasonable, since even when analyzing strongly convex distributed problems, the dependency on the condition number is unavoidable; see [Magnússon al., 2020, Sec. III-C].
7

---

we note that by fixing the seed of random number generator, the random matrix B can be generated by each agent locally, without needing to transmit any information.
Decentralized Algorithm. We propose a fully decentralized algorithm for solving (4) with a communication complexity that approaches the lower bound in Theorem 3.2. Our idea is similar to Alg. I that adopts a dimension reduction step for compression, yet we shall encapsulate the Quantize, Communi cate, Aggregati on, Broadcast steps through a decentralized average consensus protocol with support for quantized communication.
In particular, we consider setting where K agents are represented as nodes connected graph (V, B) with doubly stochastic mixing matrix W E I Observe the following fact:
Fact Consider set of vectors .1...., UK E H held by K agents on (V, E). For any <> > 0, the CHOCO-GOSSIP protocol (Koloskova et al., 2019] is described as the map:
U1,..., 0K (HOCCO-GOSSIPPL,.....UU
such that Un is the vector available at agent k satisfying |6 K K-
-K- 23-1 S Let
E 110k - K- E/=
j= 0yl1 be the initial consensus error, the protocol requires at most
(82/8>w) log(E/e) rounds of quantized communication,
where 8 (W) and w (0, is controlled by the number of bits in the quantizer. Details about the THOCO-GOSSE protocol can be found in Appendix F.l.
We replace line 5-line Alg. by CHOCO-GOSSIP
GOSSIP to yield the decentralized algorithm:
Algorithm 2 Decentralized Gradient Descent with Compressed Comm. via Linear Compression
I: Input: step size 7): initial iterate 0" E IR
2: Initialize: 0 0 Vi E [K]
3: for t in ,,. 1 do
4: Compute: Each agent compute the compressed local gradient of fu
5: Consensus: Agents exchange gradients ...9k CHOCO-GOSSIP (9) 9K' 8+1
6: Update: Each agent updates 0z+1 = 01 (((())
7: end for
8: Output: the last iterate 8..
Theorem 4.3. Consider using Alg. 2 to solve the quadratic problem (4), with A being full row
rank. Choose B such that rank(Bar (AT) N; y
aminn Z) and choose F(-) and F(.) as
"o (Zy'
F(x) Bxx Fly) B y. For any T 2 1, the following holds true:
f(0f) S (1 1/4x²)² f(0") + O(()), k= K.
where &. was defined in Theorem 4.2, Moreover, suppose that A, B are constructed as in Proposition 1, compute an e-optimal solution (3), each agent is required transmit:
R H Hog H
1 + log logg11 (1+ VD + /H Vlo Vlgg1/C log !
log e
bits,
82
no max (2)
with probability at least 1 - C.
Proposition shows that the condition number is O()). To satisfy rank(BAT) N, we need H 2 N. Altogether, this yields the communication complexity O(N log( log[1/)))) to match Theorem 3.2 up log( D) factor.
The Case of Overparameterized Neural Network. We now explore the possibility of extending the analysis of quadratic problems
specific overparameterized neural network, still belonging to class Cop. We will customize Alg. to partially compress the gradients of the loss function. Our idea is to design F(-) (resp. F.)) so that we compress (resp. decompress) the gradient with respect to the parameters in the widest layer to O(N) bits, while directly quantize the remaining gradients. Note that for a few popular network architectures such Neural Tangent Kernel (NTK) [Huang

---

et al., 2021], the widest layer contains most of the parameters ((N Therefore, compressing these parameters into ((N) bits already represents significant communication. We will leave the design and analysis of more aggressive schemes which compress the parameters of all layers for future work.
To proceed, let first state the structure of the network. Let X NxN denote the data sample; let a(-) be an activation function; let O₃ E R xn; as the output of each layer, which can be expressed as
X O₂ a (O OL-IWE
1= 0
LE 1
1=
where Wi E R 1x44 is the weight matrix in I-th layer. Further, denote OL, as the output of the network for k-th agent. Let 0 = (Wi)( collect all the weights. Then objective function becomes
K f(0) Σ fa(0)
Σ 100 -yell.
(6)
Further, define the vectorized gradient of each layer as 1y vecl V Vw; and ur for each agent. Now we describe the assumptions on the network.
Assumption 4. (Pyramidal network topology) Let n1 2 N and 122 2 n3 ... nn n Assumption 5. (Activation function) Fix (0, 1) and p > O. Let satisfy that: (i)a'(x) e 1.. (ii) [a(x)] < [x] for every x E I, and (iii) a' is p-Lipschitz.
[V,
As showed [Nguyen and Mondelli, 2020], with Assumption 4 and 5, objective (6) belongs Cop- With the above Pyramidal structure, layer parameters, denoted as U2 "I x,2, As mentioned above, we will design F and F to compress and decompress u2. To proceed, Let us choose that N & H < m1. Then F and F are defined as:
the widest layer and contains the largest number of
In B fugg Xning where B E " such
0
I 1.
0
I
F(u))
Bu
I = 2, F(F(m))
B Buy 1 2,
I > 3.
I 3 3.
This means that we compress the parameters in the second layer, and perform usual gradient descent for the layers 1 2 3; further, the parameters in the first layer is left frozen at its initialization. Note that we freeze the first layer for some technical reasons, but layer freezing itself is a useful technique accelerate the training in practice, which can provide strong generalization ability [Yosinski et al., 2014, Advani et al., 2020].
Let us denote Of the output of the first hidden layer at initialization. We have the following result. Its proof as well as the expressions for various constants, can be found in Appendix G.
Theorem 4.4. (Informal) Consider using Alg. I to solve the quadratic problem (6), with X being full row rank. Suppose 0 is initialized properly (see Appendix G for details). Choose B such as rank( BOp = N; choose F-)) and F-)) as in (7). Then there exists stepsize T, constant o, C, such that to compute an c-ppimall solution (6), each agent is required to transmit:
4b no
(Hmg + = mmm+1) (og( bitslagent,
(8)
where T,, é are reluted to X, v,p p and singular values of the weight matrices at initialization.
Theorem 4.4 shows that we choose = ((N), and when mi is very large, then the total communication complexity can be reduced by factor of n2 H./H.
Preliminary Numerical Experiments. We conclude by presenting numerical experiment for the UCI Tom's 's Hardware" dataset using Alg. 2 where we applied (og(t++000) rounds of communication the t-th iteration for the CHOCD-COSSI subroutine; see Appendix F.I. We consider a ring network
with K 5 agents, each one has 500 or 1000 samples (thus making N 2500, or N 5000).
Available: https: htaps:://arcivee.. wic.iiiieeiieee.ei..e.om uci eec.eedumml
+media

---

1e10
86 Troom ted Aehheeeeeeeeee 30- M50
520 520 dio.
1000 Star (000
24645 d mendioee 500 ran del, (t-3003
dimnniira dats Ie-222
34840 1000 data, Ni-3030
2.0
Then
2014
6217
13961
24649
Oimersion
Figure 1: Overparameterized Kernel Regression with Alg. 2. Both figures show statistics of 5 random seeded nus.. (left) Training MSE against the number of bit transmitted on the whole network. (Right) Communication achieve 10" MSE training datasct, compared different dimensions of kernel features.
We construct D-dimensional features from the dataset as NTK features [Bietti and Mairal, 2019]. In Fig. train least square regression model in the overparameterized regime. We observe that the communication cost needed is proportional to the number of samples, instead of the feature dimension. Particularly, results indicate that the communication train MSE (of 10 10=4) is proportional to the number of training samples.
required reach target
Acknowledgments and Disclosure of Funding We sincerely thank the anonymous reviewers for the suggestions. M. Hong and B. Song are supported by NSF grants CIF-1910385 CMMI--12773 and CNS-2003033.
10

---

References
M. S. Advani, A. M. Saxe, and H. Sompolinsky. High-dimensional dynamics of generalization error in neural networks. Neural Networks, 132:428-4444 2020.
D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic. Qsgd: Communication-ffficcan sgd via gradient quantization and encoding. Advances in Neural Information Processing Systems, 30: 1709-1720, 2017.
Z. Allen-Zhu, Y. Li, and Song. convergence theory for deep learning via over- peeeraarameteiiztiion. In International Conference on Machine Learning, pages 242-252. PMLR, 2019.
Y. Arjevani and O. Shamir. Communication complexity of distributed convex learning and optimiza- tion. In Proceedings of NIPS, pages 1756-1764, 2015.
Bernstein, Y.-.. Wang, K. Azizzadenesheli, and A. Anandkumar. signsgd: Compressed optimisa- tion for non-convex problems. In International Conference Machine Learning, pages 560-569. PMLR, 2018.
A. Beznosikov, S. Horváth, P. Richtárik, and M. Safaryan. On biased compression for distributed learning. arXiv preprint arXiv:2002. 2020.
A. Bietti and Mairal. On the inductive bias of neural tangent kernels. In Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Ber Bucé, E. Fox, and R. Gamett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https /pppcceeinng...... neurips. cc seee/aper//ee/ 2019//20999/ file/ c4e (tffffe...3300111190233333aa33.. Pappee sopper.pdf.. pdf..
M. Braverman, F. Ellen, R. Oshman, T. Pitassi, and Vaikuntanathan. tight bound for set disjointness in the message-passingg model. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 668-677, 2013.
Y. Deng, M. M. Kamani, and M. Mahdavi. Local sgd optimizes overparameterized neural networks in polynomial time. In International Conference on Artificial Intelligence and Statistics, pages 1840-6861 PMLR, 2022.
S. Du, J. Lee, H. Li, L. Wang, and X. Zhai. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pages 1675-1685, PMLR, 2019.
E. Gorbunov, K. P. Burlachenko, Z. Li, and P. Richtárik. Marina: Faster non-convex distributed learning with compression. In International Conference on Machine Learning, pages 3788-3798. PMLR, 2021.
Haddadpour, M. M. Kamani, Mokhtari, and M. Mahdavi. Federated learning with compression: Unified analysis and sharp guarantees. In International Conference Artificial Intelligence and Statistics, pages 2350-2358. PMLR, 2021.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
S. Horváth, C.-Y. Ho, L. Horvath, A. N. Sahu, M. Canini, and P. Richtárik. Natural compression for distributed deep learning. arXiv preprint arXiv: 10988, 2019.
B. Huang. X. Li, Z. Song, and X. Yang. Fl-ntk: A neural tangent kernel-based framework for federated learning analysis. In International Conference on Machine Learning, pages 4423-4434. PMLR. 2021.
A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
H. Karimi, J. Nutini, and M. Schmidt. Linear convergence of gradient and proximal-gradient methods under the polsai--ojasiewicz condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 99. Springer, 2016.
11

---

S. P. Karimireddy, Q. Rebjock, S. Stich, and M. Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, pages 3252-3261. PMLR, 2019.
A. Koloskova, S. Stich, and M. Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, pages 3478-3487. PMLR, 2019.
J. Konečný, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05499 2016.
H. Korhonen and Alistarh. Towards tight communication lower bounds for distributed optimisa- tion. Advances in Neural Information Processing Systems, 34, 2021.
D. Kovalev, E. Gasanov, A. Gasnikov, and P. Richtarik. Lower bounds and optimal algorithms for smooth and strongly convex decentralized optimization over time-varying networks. Advances in Neural Information Processing Systems, 34, 2021.
D. Kovalev, A. Beznosikov, A. Sadiev, M. Persiianov, P. Richtárik, and A. V. Gasnikov. Optimal algorithms for decentralized stochastic variational inequalities. CoRR, abs/2202.02771, 2022. URL https: //arxi////xive// org/ aaaaaass//2// htlpb//2222.021122
J. Li, Y. Liu, and W. Wang. Distributed learning with random features. 2019.
arXiv preprint
arXiv:1906.031
C. Liu, I. Zhu, and M. Belkin. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 2022.
Y. Lu and C. De Sa. Optimal complexity in decentralized training. In International Conference on Machine Learning, pages 7111-7123. PMLR, 2021.
Magnússon, H. Shokri-Ghaare Ghadikolaei, and N. Li. On maintaining linear convergence of distributed learning and optimization under limited communication. IEEE Transactions on Signal Processing. 68:6101-6116, 2020.
K. Mishchenko, F. Gorbunov, M. Takáč, and P. Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv:
2019.
Q. N. Nguyen and M. Mondelli. Global convergence of deep networks with one wide layer followed by pyramidal topology. Advances in Neurul Information Processing Systems, 33:1 1961-11972, 2020.
S. Oymak and M. Soltanolkotabi. Overparameterrized nonlinear learning: Gradient descent takes the shortest path? In International Conference on Machine Learning, pages 4951-4960. PMLR, 2019.
K. K. Patel and A. Dieuleveut. Communication trade-offs for synchronized distributed sgd with large step size. arXiv preprint arXiv: / 11355, 2019.
B. T. Polyak. Gradient methods for the minimisation of functionals. USSR Computational Mathemat- ics and Mathematical Physics, 3(4):664-88 87888888 1963.
M. Razaviyayn, M. Hong, N. Reyhanian, and Z.-Q. Luo. linearly convergent doubly stochastic gauss-Seidel algorithm for solving linear equations and certain class of over-parameterized optimization problems. Mathematicul Programming, 176(1):465-466, 2019.
A. Reisizadeh, A. Mokhtari, H. Hassani, and R. Pedarsani. An exact quantized decentralized gradient descent algorithm. IEEE Transactions Signal Processing, 67(19):4934-4477 2019.
P. Richtárik, I. Sokolov, and I. Fatkhullin. Ef21: A new, simpler, theoretically better, and practically faster error feedback. Advances in Neural Information Processing Systems, volume 34, 2021.
M. Rudelson and R. Vershynin. Non-asymptotic theory of random matrices: extreme singular values. In Proceedings of the International Congress of Muthematicians 2010 (ICM 2010) (In 4 Volumes) Vol. Plenary Lectures and Ceremonies Vols. II-IV: Invited Lectures, pages 1576-1602. World Scientific, 2010.
12

---

M. Safaryan, E. Shulgin, and P. Richtárik. Uncertainty principle for communication compression in distributed and federated learning and the search for an optimal compressor. arXiv preprint wwXi:22002.08958, 2020.
M. Safaryan, F. Hanzely, and P. Richtárik. Smoothness matrices beat smoothness constants: bet- ter communication compression techniques for distributed optimization. Advances in Neural Information Processing Systems,
-277222,,2 2021.
K. Scaman, F. Bach, S. Bubeck, Y. Lee, and Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization in networks. arXiv preprint arXiv:1702.08704, 2017.
K. Scaman, F. Bach, S. Bubeck, L. Massoulić, and Y. T. Lee. Optimal algorithms for non-smooth distributed optimization networks. In Advances in Neural Information Processing Systems, pages 2740-22000 2749, 2018.
S. U. Stich and S. P. Karimireddy. The error-feedback framework: Better rates for sgd with delayed gradients and compressed communication. arXiv preprint arXiv: 1909.053000 2019.
U. Stich, J.-B. Cordonnier, and M. Jaggi. Sparsified sgd with memory. Advances in Neural Information Processing Systems, 31, 2018.
H. Sun and M. Hong. Distributed non-convex first-order optimization and information processing: Lower complexity bounds and rate optimal algorithms. IEEE Transactions on Signal processing. 67(22):5912-592 2019.
Sun, T. Chen, G. B. Giannakis, Q. Yang, and Z. Yang. Lazily aggregated quantized gradient innovation for communication-effcienn federated learning. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2020.
H. Tang, S. Gan, C. Zhang, T. Zhang, and J. Liu. Communication compression for decentralized training. Advances in Neural Information Processing Systems, 31, 2018.
J. N. Tsitsiklis. Problems in decentralized decision making and computation. Technical report, Massachusetts Inst of Tech Cambridge Lab for Information and Decision Systems, 1984.
J. N. Tsitsiklis and Z.-Q. Luo. Communication complexity of convex optimization. Journal of Complexity, 3(3):231 2433, 1987.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 2017.
S. S. Vempala, R. Wang, and D. P. Woodruff. The communication complexity of optimization. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1752-1752. SIAM, 2020.
T. Vogels, S. P. Karimireddy, and M. Jaggi. Practical low-rank communication compression in decentralized deep learning. Advances in Neural Information Processing Systems, volume 33, pages 4111114481, 2020.
H. Wang, S. Sievert, S. Liu, Z. Charles, D. Papailiopoulos, and S. Wright. Atomo: Communication- efficient learning via atomic sparsification. Advances in Neural Information Processing Systems, 31, 2018
J. Wang and G. Joshi. Cooperative sgd: A unified framework for the design and analysis of communication-effiiia sgd algorithms. arXiv preprint arXiv: (00iv:/808.0751171 2018.
W. Wen, C. Xu, F. Yan, C. Wu, Y. Wang, Y. Chen, and H. Li. Tergrra: Ternary gradients to reduce communication in distributed deep learning. Advances in neural information processing systems, 30, 2017.
H. Xu, C.-Y. Ho, A. M. Abdelmoniem, A. Dutta, E. H. Bergou, K. Karatsenidis, M. Canini, and P. Kalnis. Compressed communication for distributed deep learning: Survey and quantitative evaluation. Technical report, 2020.
13

---

J. Yosinski, J. Clune, Y. Bengio, and H. Lipson. How transferable are features in deep neural networks? Advances neural information processing systems, 27, 2014.
H. Yu, S. Yang, and Zhu. Parallel restarted sgd with faster convergence and less communica- tion: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages
2019.
Y. Zhang, J. Duchi, M. I. Jordan, and M. J. Wainwright. Information-theorriic lower bounds for distributed statistical estimation with communication constraints. Advances in Neural Information Processing Systems, 26, 2013.
14


Reviews:
[{"review_id": "OfrObbcIaR", "reviewer": "Reviewer_zULq", "summary": "This paper considers distributed (centralized and decentralized) smooth nonconvex (PL) minimization problems in the general case and in the special (quadratic) overparameterized case. The authors give lower bounds on the amount of information transferred in terms of dimension, number of agents, amount of data, and solution accuracy. Then the authors give an algorithm by which these lower bounds can be achieved. The algorithm uses an unusual but not new quantization. In general case (Section 4.1), the algorithm is no different from those already encountered in the community. In the quadratic-overparameterized case, the key is the use of an additional transformation $F$ and an inverse $\\tilde F$. The authors also give a decentralized version of the algorithm using a gossip protocol with compression.", "questions": "Please, see section \"Strengths And Weaknesses\"", "limitations": "No limitations and potential negative societal impact", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I was generally interested in dealing with this work. I was left with a mixed impression of the work. Below I will outline my thoughts, questions, and comments in the order of the paper. \n\n0) The paper is fairly easy to read, in some cases the presentation could have been improved (see below), but overall I had no problem getting into the results.\n\n1) Literature review: it seemed to me that a literature review could be more complete. In particular, one of the most active authors in the field of compressed optimization is P Richtarik. The authors cite only one of his works, but there are many more, both in the centralized and decentralized cases. This is important not only to note Richtarik's contributions, but also to compare your results with those available in the literature (see below, point 3).\n\n2) Lower bounds: I think it is important here to clarify which factors are important to us when deriving lower bounds: $N$, $K$, $D$, $e$, $L$, $\\mu$ and $B$, where $B$ is the number of bits used in the current data type (e.g. 32 or 64 bits). If I understand correctly, the bounds take into account the presence of $B$, but do not depend on it. I think it is important to reflect this. \n\n3) For me, the compressor from Definition 4 turned out to be new. It is not an invention of the authors, but I read the original paper about it. Thanks for this experience!\n\n4) Upper bounds in the $C_{pl}$ case: my feeling is that these are not good bounds. The authors' estimate (in terms of $L$, $M$, $\\mu$) is equal to $\\mathcal{O}\\left( \\frac{L^2 M^2}{\\mu^4}\\right)$, this is a very large number. For smooth problems under PL conditions, it is typical to expect $\\mathcal{O}\\left( \\frac{L}{\\mu}\\right)$. For example, the compression method from [1] has such results. If we remember about communications, then the estimate (in bits) from the work [1]  looks like \n$$\n\\mathcal{O}\\left( \\frac{BD}{\\sqrt{K}} \\cdot \\frac{L}{\\mu}\\right),\n$$\nwhere $K$ is a number of agents, $B$ is the number of bits used in the current data type (e.g. 32 or 64 bits). This is the square root of $K$ times better than for the uncompressed method. The authors' estimate is\n$$\n\\mathcal{O}\\left( D \\log_2 D \\cdot \\frac{L^2 M^2}{\\mu^4}\\right)\n$$\nEven if we forget about $L$,$\\mu$ and $M$, it is not obvious to me which is smaller $\\log_2 D$ or $\\frac{B}{\\sqrt{K}}$. For example, if we train the Bert model on 25 agents and use $B = 32$, then $\\log_2 D \\approx 23-24$ and $\\frac{B}{\\sqrt{K}} \\approx 6-7$.That's why I stress that comparison with other results is very important! There are many works, not only [1].\n\n5) The overparameterized case: this is the first time I met such an overparameterized assumption (Definition 2), although I saw many papers where simpler things are introduced as overparameterization. Therefore, Definition 2 is very specific and in the literature it occurred only 1 time. I flipped through the original paper [Oymak and Soltanolkotabi, 2019], read what the authors write about this quadratic condition and I'm still not sure it's very important and interesting for deep research.  My concerns are related to the fact that despite the improvements in convergence in terms of $N$ and $D$, in terms of $L$ and $\\mu$ we are far from good convergence estimates, namely $\\mathcal{O}\\left( \\frac{L^4}{\\mu^4}\\right)$. And this effect is noticeable both in the original paper and in the one under review.\nAt the moment the most important point of this paper is to understand how interesting this condition and the results around it: how wide a class of problems satisfies it (perhaps the authors will be able to add something here besides what is written in the work), what order of gain can be obtained for certain problems (due to the fact that we change $D$ to $N$, but lose significantly in $L/\\mu$) and so on. Now it seems to me that the game is not worth the candle.\n\n6) Decentralized results seemed to me bonus and not particularly interesting, it uses a multistep gossip protocol with compression, and the authors uses the classic sign compression, not special from Definition 4. The essence of this method is that it is a centralized method, but with a slight inexactness in averaging. It is obvious to me that this can be done.\n\n**Conclusion:**\n\nI am looking forward to the discussion process with the authors and fellow reviewers to discuss this work. This is important to me because so far I have mixed feelings, many questions, and have not taken a clear view of the paper. At this point, I will give a borderline reject to motivate  the authors to take an active part in the discussion.\n\n[1] Gorbunov E. et al. MARINA: Faster non-convex distributed learning with compression //International Conference on Machine Learning. – PMLR, 2021. – С. 3788-3798.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9FaYq_bJd5h", "reviewer": "Reviewer_NYA5", "summary": "This paper studies the communication complexity (bits communicated) of distributed optimization problems where the client objectives: \n1. satisfy the PL condition, or \n2. are overparameterized generalized quadratic functions.  \n\nIt provides lower bounds for these problems and first-order algorithms with appropriate compression/decompression. The proposed algorithm for PL objectives has optimal communication complexity up to logarithmic terms in the dimension of the problem. Similarly, for quadratic overparameterized objectives, it attains optimal communication complexity (up to logarithmic terms) with high probability. It can also be \"decentralized\" by using the CHOCO estimator proposed by Kolsokova et al. Finally, the paper also studies a stylized feed-forward neural network and shows that in a particular regime, their algorithm also attains optimal communication complexity for it. ", "questions": "1. I am nitpicking, but what leads to the extra $\\log(D)$ factor? Is it coming from initialization and unavoidable?\n\n2. Can the authors show a better upper bound for the neural networks? In practice, one doesn't use such a dramatic pyramidal structure. If not, do the authors expect a better lower bound for this specific class? Or a more specialized quantization is required? It would be good to discuss this aspect, even if the authors can't provide better results. \n\n3. Can the overparameterized class be extended to overparameterized generalized linear models? \n\n4. Can the authors comment on why they need the second inequality in (2)? My intuition is that this is not necessary for smooth functions. What's unique to the overparameterized setting? \n\n5. What are the significant differences in the quadratic setting from the analysis of Korhonen and Alistarh, 2021?  \n\n6. I agree that understanding the bit communication complexity is very important but in practice, reducing communication rounds is as much or often more important than lowering the bit complexity. It is because of the overheads involved in each communication between the (edge) device and the server. The communication model authors use in this paper can't capture this because each round transmits a single bit. What are the challenges to extending the current lower bound results to the [intermittent communication](https://arxiv.org/abs/1805.10222) setting to reconcile with existing results such by Arjevani and Shamir, etc.? Are there other communication models that make more sense and can better capture these aspects of communication? It is worth discussing in the paper in more detail.\n\n7. On the lines of the previous point, I'd like to see how the quantization schemes presented here work with local update algorithms commonly used to reduce communication rounds? The moonshot goal is to come up with an algorithm that can attain optimal bit and round complexity at the same time.   \n\n8. I would like to see more large-scale experiments. It would be even better if the authors could identify a regime where bit complexity is more critical than communication rounds and capture that in their experiments.    ", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written and clearly describes the problem and results. The results for PL functions and overparameterized quadratics are tight, which is excellent. The pyramidal neural model seemed a bit stylized, and for the usual widths used in practice, the upper bound shows no savings in communication. Overall, I like the paper but have some questions/concerns, due to which I have currently weakly accepted the paper.  \n\n   ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0RjsdSL0iOF", "reviewer": "Reviewer_NYne", "summary": "This paper studies an important problem in the distributed optimization:  To train an overparameterized model over a set of distributed nodes, what is the minimum number of bits required to reach zero loss. The paper gives lower bounds in two cases: PL and overparameterized case. Then it further gives multiple algorithm examples that can achieve the lower bound under certain conditions: the model is in general close to the structure of linear regression, and the quantization algorithm should be carefully designed.", "questions": "1. How will the current bounds adapt if we include the Lipschitz constants $L_k$ and $L$, will it lose tightness if the global function is  the average over all the local functions?\n\n2. Is it immediately clear if the tightness will still hold when the proposed algorithms are solving general convex/non-convex functions?", "limitations": "Please refer to the previous reviews.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper addresses the gap of bits complexity in distributed optimization, as many of the related papers focus on lower bounds on the communication rounds, especially in the decentralized case. The theoretical results in the paper look promising, since the paper finds the *(near) optimal* rates in two cases and two settings (with a central coordinator and fully decentralized). In terms of theory, this paper gives strong and new (to my knowledge) results. I did not check the proof line-by-line, but the asymptotic rates seem reasonable.\n\nOne concern about the theory is that I believe a discussion in terms of the Lipschitz constants should be included. In this paper, the main objective is the sum over all the local functions (not average). This implies the Lipschitz constants between local and global function might be implicitly related by a $N$ factor. I'm not sure if this would make the final bound hide an extra $N$, this should be clarified in the main paper.\n\nMy other concerns are on the settings and experiments. More specifically, I'd be interested in seeing how the bounds and tightness would adapt if we are dealing with general convex or non-convex functions (not necessarily PL or least square). On the other hand, this paper is clearly theory-driven, but more experimental results on different applications (models, datasets) would definitely be beneficial, as in small-scale applications, we wouldn't need communication compression or very large models in general.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept