DGD^2: A Linearly Convergent Distributed Algorithm For High-dimensional Statistical Recovery
Authors: Marie Maros
Gesualdo Scutari
Venue: NeurIPS 2022 Accept (2022)
Keywords: Distributed optimization
convex optimization
high-dimensional statistics
linear convergence

Abstract: We study linear regression from data distributed over a network of agents (with no master node) under high-dimensional scaling, which allows the ambient dimension to grow faster than the sample size. We propose a novel decentralization of the projected gradient algorithm whereby agents iteratively update their local estimates by a “double-mixing” mechanism, which suitably combines averages of iterates and gradients of neighbouring nodes. Under standard assumptions on the statistical model and network connectivity, the proposed method enjoys global linear convergence up to the statistical precision of the model. This improves on guarantees of (plain) DGD algorithms, whose iteration complexity grows undesirably with the ambient dimension. Our technical contribution is a novel convergence analysis that resembles (albeit different) algorithmic stability arguments extended to high-dimensions and distributed setting, which is of independent interest.

DGD²: A Linearly Convergent Distributed Algorithm For High-dimensional Statistical Recovery
Marie Maros
Gesualdo Scutari
School Industrial Engineering Purdue University nmaros@purdue edu
School Industrial Engineering
Purdue University gscutar1@purdue edu
Abstract
We study linear regression from data distributed over a network of agents (with no master node) under high- digenssiill scaling, which allows the ambient dimension to grow faster than the sample size. We propose novel decentralization projected gradient algorithm whereby agents iteratively update their local estimates by a "double-mixing" mechanism, which suitably combines averages of iterates and gradients of neighbouring nodes. Under standard assumptions on the statistical model and network connectivity, the proposed method enjoys global linear con- vergence up the statistical precision of the model. This improves on guarantees of (plain) DGD algorithms, whose iteration complexity grows undesirably with the ambient dimension. Our technical contribution is novel convergence anal- ysis that resembles (albeit different) algorithmic stability arguments extended to digh-dimmnssoos and distributed setting, which is of independent interest.
the
1 Introduction
Consider M-cstimation over a network of y agents, modeled as an undirected graph with no server (termed mesh network). Each agent owns sample of n i.id observations. drawn from unknown, common distribution on C IP,, and collected in the set S.. Agents aim at minimizing the total empirical loss over N samples, resulting in the following empirical risk minimization (ERM):
((0) A 1 m Σ C.()),
E argmin BED:R(0)ER
with ((
A
Σ JES:
(x) 9-)33
2n
where (9) is the empirical loss of agent i, with xy E Rd being the vector of predictors and z E R the associated response; R is (convex) regularizer (with R > 0) controlling the complexity of the solution; and Q is some (convex) subset of I...
The ERM (1) is surrogate of the minimization of the (strongly convex) population loss
8" argmin E(0) A -E (n 1)
BER4
are interested estimation problems that are underdetermined, meaning that the ambient dimen- sion d exceeds (and grows faster than) the total sample size N. Therefore, assume that 0* lies in smaller subset of Ω or well approximated by a member of it-the regularizer R in (1) enforces this constraint. Instances of such M-estimation problems include l conossttaddeed sparse linear models, low-rank matrix recovery via nuclear norm, and matrix regression with soft-rank constraints [2].
Our goal is to study statistical and computational guarantees of first-order distributed algorithms for (1). The benchmark is the centralized Projected Gradient Algorithm (PGA) [2]: under suitably
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

restricted notions of strong convexity and smoothness of L (see Sec. 2)-which hold with high probability for a variety of statistical models-as well as conditions for statistical consistency-e.r log d/N (11 for s-sparsity-the iterates {0') generated by the PGA (starting from 0*) satisfy:
||0d 0 s X 1000 01 o(10 9- 112)
with À E (0, 1). In words: the optimization error ||0 - 0|| decays linearly with rate A. up to a tolerance of smaller order than the statistical error of the model, ||0 0-1 Therefore every limit point of {Ø*) } is within the statistical error from 0*. This is the the best one can hope for statistically (ignoring lower order terms) and computationally (within first-order, non accelcrated methods).
The PGA not implementable on mesh networks: agents cannot compute locally the full gradient VC. This calls for the design of distributed algorithms. The following questions arise naturally:
(Q1) Can (3) be achieved by distributed algorithms? Of primary interest is the regime wherein the local sample size n is not sufficient for statistical consistency while the total one N is so.
(Q2) How do sample rate and convergence rate scale with the model parameters (d, nu, N) and network parameters (connectivity, size m, and topology)?
As documented next, current literature does not provide satisfactory answer to the above ques- tions for the majority of distributed algorithms. In a nutshell, most of existing studies are of pure optimization type, they lack statistical analysis, and break down under digh-dimensional scaling d/N +00.
1.1 Related works
The ERM (1) is an instance of (non strongly) convex optimization problem- several distributed algorithms are applicable. Early decentralizations of the PGA have been proposed in [18, 19]; when applied to (I), they reduce the following distributed gradient descent (DGD):
0
II
Σ JEN.
/y 0 aVL, i= 1, I...,,,,,
(4)
(0(R()S
where of is the estimate from agent i of the common variable 0 at iteration t; (0, 1] is the stepsize: N; is the set of neighbors of agent é; mij' 's are suitably chosen nonnegative weights; and llan
is the Euclidean projection of its argument onto the convex set (0 E Ω R(0) I R). Subsequent works [33, 34, 7] extended convergence analyses of (4) to other classes of loss functions, and [5, 6, 24] proposed alternative forms of mixing of local and neighboring information.
When applied to the minimization of average loss f(0) 1/m E.n f((0), convergence guar- antees of the above DGD-like algorithms, including (4), can be roughly summarized as follows: (i) when fi smooth, strongly convex, DGD schemes using constant stepsize converge at linear rate, but only to a neighborhood of the minimizer of the average-loss ff [33, 34]. Convergence to the exact minimizer is achieved employing diminishing stepsize rules, at the price of slower sublinear rate [34, 12]. These results are unsatisfactory when applied to the ERM (1). First, for fix d and N, they would predict sublinear convergence rate, as the loss L is convex but not strongly convex (recall d > N); this would suggest a negative answer to (Q1) conclusion that seems to be confuted by recent experiments [28, Fig. 11, showing instead linear convergence of DGD (4) up tolerance. optimization Second, when d grows faster than N-the typical situation in high-dimension-theee studies break down. In fact, they all require globul smoothness of the loss functions L3 's and C, property that no longer holds under the -igh--imensional scaling d/N + co: for commonly used designs of predictors x; 's, the Lipschitz constant of V grows indefinitely with d/N [30].
statistical study of a DGD-like algorithm solving the LASSO problem (in the Lagrangian form) over mesh networks recently proposed in [13]: For standard statistical models of predictors, the iterates generated by the algorithm enter an e-neighborhood of a statistically optimal estimate after
(1- d m² logm- loog -
iterations,
(5)
where o E [0, 1) is a measure of the connectivity of the network and x is the condition number of the data covariance matrix (population loss). This improves classical optimization analyses, showing

---

that this instance of DGD achieves centralized statistical accuracy at a linear rate. However, this rate scales as (d). In this paper, we prove that the DGD scheme (4) applied to (1) inherits the same undersirable scaling of the rate-see Appendix H. This would provide a negative answer to (Q1).
A natural question is whether other distributed algorithms offer a more favorable rate scaling, in particular those employing some form of correction of the local gradient direction in the agents' updates. Examples include: primal-dual schemes [27, 25, 26, 14] and gradient tracking methods [21, 17, 32. 8, 29]. However convergence of these algorithms in high-dimension has not been investigated. For fixed d and N, with d NN existing analyses predict pessimistic sublinear convergence rate of those methods applied to (1). Furthermore, with the exception of [28], they lack of any statistical analysis and, as those for DGD methods, they break down under high-dimension scaling, d/N growing. The very recent work [28] studied the LASSO problem over networks and proposed a decentralization of PGA based on gradient tracking, termed NeLLASSO. Under suitable assumptions, the scheme is proved to reach a neighborhood of statistically optimal estimate of an s-sparse parameter at linear rate. The analysis of NetLASSO is ad-hoc, as it builds on the specific dynamics of the iigorithm-hence questions (Q1) and (Q2) remain open for other distributed algorithms. Furthermore, [28] seems to suggest that gradient-trckkng is needed to achieve dimension independent (lincar) convergenee rates over mesh networks. In this paper we prove that gradient tracking is actually not necessary.
1.2 Major contributions
To cope with the 'speed-accuracy dilemma' of DGD in high-dimensions, propose a new distributed algorithm whereby agents update their local estimate and optimization directions via a moublee-ixiing mechanism, aiming enforcing consensus both iterates and local gradients. We termed the algorithm DGD?. At the high-level, our approach brings a new perspective to the design of distributed algorithms in high-dimension: the ultimate goal is not solving the ERM (1) exactly but reaching instead an estimate of 0* within the statisticul error. This can significantly relax the algorithmic design. For instance, contrary what one might infer from [28], pradient-tracking is not needed to efficiently achieve statistically optimal solutions, as our design and analysis prove.
(i) Algorithm design:
(ii) Statistical guarantees: We identify deterministic conditions under which the iterates generated by DGD2 converge at linear rate to a limit point that is within a fixed tolcrance from the unknown parameter 8* When customized to statistical models including sparse lincar regression with & regularization, low-rank matrix recovery with nuclear norm, and matrix completion our conditions hold with high-probability, and the tolerance becomes of the order of the statistical error || 0* I|- For such models, DGD2 enters an e-neighborhood of statistically optimal estimate of 6* after
o (K- log
k =_ -lg(m 1 =) iterations (gradient calls) and O
1
PI-p"
K) log
communications,
(6)
for any p E 1). The former matches the rate of PGA; the latter compares favorably with the complexity of DGD in (5), which instcad degrades with d. Finally, (6) is showed to be invariant under high-dimensional scaling d/N - co, as long as 0 0+1 = O()). All this addresses (Q1) and (Q2). Quite interestingly, it also shows that gradient-tracking as in [28] is not needed in high-dimensions.
(iii) New convergence analysis: We put forth a new analysis, inspired by the idea of algorithmic stability for stochastic optimization [4, 9]-note that that theory is not applicable in high-dimensions and distributed setting. Leveraging the more favorable landscape of the population risk, our approach contrasts the trajectory of DGD² to that of "virtual" DGD² instancc applied to population (penalized) variant of the ERM, and establishes conditions for the two trajectories to stay within the desired tolerance while letting DGD2 inherit fast linear converge of its population counterpart. This contrasts with existing works of distributed algorithms in high-dimension [13, 28], whose convergence is established on the empirical landscape, splitting thus the estimation error |10) 0+1 between optimization |[0] Ø|| and statistical ||Ø I' errors. This makes the analysis very algorithmic- dependent and hard to extend to other solution methods (see remark in Sec. 4.2 for technical details). On the contrary, our approach leads to simpler proofs, potentially applicable to other distributed algorithms than DGD2 in high-dimensions (e.g.. primal-dual), An example is given in Appendix H. where convergence of a variant of DGD in [13] applied to the constrained LASSO problem is provided. Our approach will be applied to other distributed algorithms in future works.
3

---

2
Setup and Background
We develop our analyses under the following assumptions.
Assumption The population risk & is j-strrongyy convex and L-smooth on I&, with μ, (0, The condition number is _ L/p.
We consider regularizers R in ERM (I) that are decomposable [2]. Let E Ω be the so-called parameter subspace, capturing constraints from the model (e.g., vectors with particular support or a subspace of low-rank matrices); and let M be the perturbation subspace, representing the deviations from the model subspace M. Decomposability is defined as follows.
Assumption 2 ([30)) (i) R Ω - is a norm, with Ω C Rd convex. Furthermore, given a that is, R(x+y)
subspace pair (M,,--) such that M E M: (ii) i (M,M- )-decoposabbl,, (MMMMM)deccooposslll
R(x)+ RRy), for all E M and y E M and (iit) When M + {0). R is (MM)-iisshhitz over M T (M) A supee (0) @||| If M {0}. set V ((())) 0.
with respect some norm
Fast convergence of the PGA relies the empirical risk C satisfying suitably restricted notions of
strong convexity and smoothness [2]. Under Assumption 1, this can be enforced by controlling the deviation of the Hessian V of L from the Hessian V L of the population loss L, along certain directions, as stated below. Note that V L > 0 is the covariance matrix of the predictors x. while V = (1/N)X" X, with X 3 32. ,
EYT > 0 such that Assumption 3. There exist 1g. 2g.2 Tg > and matrix E'
A V 7g,1 11 + R²² (A), AA E !/;
A A
- - V2
- (A), -T, VA E S!
Assumption 3 enforces curvature property V L along the directions A E Sz S Rd where (A) sufficiently small. In the distributed setting, we need also a local counterpart of Assumption 3, associated with the agents' Hessian matrices L (1/n)X, X with X; (xz))es;-
Assumption 4. There exist Te,1, 72, T8 > and a matrix Σ' T > 0 such that, for all i,
ATV A + T2 (A), YAE
A AVCCC-''C - -2 (AR
-
S2'.
The practical utility of Assumptions 3 and 4 is that they can be certified with high probability by a variety of random data generations. Here, consider the following widely used statistical models, which cover a variety of estimation tasks, such as sparse linear models with & regularization, low-rank matrix recovery with nuclear norm, and matrix regression with soft-rank constraints [15, 2, 30).
Assumption 5. The random predictors I, Rd are i.idd. and fulfill one of the following conditions:
(i) ~ No, Σ) and are i.i.d., for some Σ > 0;
(ii) are (72 - and ii.dd. with Σ > 0;
(iii) = Ej where j ~ uniform(1, d) and i..dd
Under Assumption 5 the curvature conditions in Assumptions 3 and hold with high probubility. The following lemma makes this formal under Assumption 5(i), and is minor modification of [2. Prop.
1, supplmenntarry) Similar results under Assumptions ((i))-iiii can be found in Appendix F.
Lemma Under Assumption 5(i), there exist universal constants co, C1 C2 > O such that, with probability at least 1 exp(-epppp N N + log and N ' 10, Assumptions 3 hold with parameters
3²= 7g.1 =12,, 1, Ty = 02 (x.)"(;.))) /N;
and so does Assumption 4 with parameters
Σ' L, 7e,1 - 1, V8.2 = 4m, Tt -2 (E(R(x)))) /n,
where R* is the dual norm of R. When R(-) || 111. (x.)) 9(max, 5 log(d).

---

Network setup: Agents are embedded in a communication network, modelled as an undirected graph g = (V.E) )) where the vertices V [m]] A (1..... m) correspond to the agents and E is the set of edges of the graph; (1 E & if and only if there a communication link between agents and j. The set of neighbors of each agent is denoted by N _ {j V (i,j) E E) U {i}. We focus on distributed algorithms using gossip weight matrices in their communication steps, as below.
Assumption 6. W [w]jk]==1 satisfies: (i) Waj > 0, if (i, E; otherwise Waj 0: furthermore,, W/s > 0, for all i E [m]; (ii) W = W and W1 = 1 (stochastic); and (iū) there holds -
|W -J J1 < 1, where J A 11 /m.
Assumption is standard in the literature of distributed algorithms and is satisfied by several weight matrices; see, e.g., [16]. Note that p < 1 holds true by construction for connected graphs. Roughly speaking, measures how fast the network mixes information; the smaller p. the faster the mixing.
3 Algorithm Design: DGD2
We begin providing some rationale on the new design. Our goal is to cope with the speed-accuraa dilemma of DGD (4)-see (5>-will retaining linear convergence to statistically optimal solutions.
It is convenient to rewrite (4) in matrix/vector form. Define the "augmented"" quantities:
A ((0) , TT,
((0)
(()))) and W&We & la.
i=1
with @ denoting the Kronecker product. Then, DGD (4) can be rewritten 0++1
II
(wo' am V(('))
(8)
Ωn R
where the projector operator is now intended acting block-wise on each d-dimensional block. is well-known that (8) can be interpreted as the iterate dynamics of the projected gradient algorithm (with stepsize m mx) applied to the following optimization problem [33]: using 0 - [(O1) ..... (0m) TT.
min
(())
+ m a 1012_
0,E R((0.) R, (sE[m)
The quadratic penalty in the objective aims at enforcing consensus among agents' variables 6; P,'s, as a 1.O. Our analysis (see Appendix H) shows that exact consensus is not needed; in fact, a = O(d is enough to drive the estimation error (1/ 1/m) 10 within an neighborhood of statistically optimal solution of (2) in a number of communications steps as (5). Numerical results confirm that a--(d=1) is necessary for statistical consistency.
This undesirable scaling of the rate (5) with d is a consequence of the restrictive condition (d- At a high level our goal is then clear: we need to ease such a constraint. Our idea is to share the consensus-achieving burden in (9) between a (the penalty term) and the first term (()).
Notice that at consensus, 0 J0, and thus C()) C(JO), where J e Ig. However, C(J0) (and its gradient) is not computable distributively, as agents cannot perform full averages in a single communication step, as subsumed by the operation JØ. We propose then approximate L(J0) by
L ((W0), where W A W 6o Ja. for some gossip matrix W (Assumption 6). The gradient of C(WO) is now additively separable across the agents and thus locally computable. We thus replace (9) with
min denn:RR(0 H. vie(m]
((WO)
+ 2 2ma
||01 w
(10)
Our new algorithm is obtained as projected gradient method applied to (10) (with stepsize ma):
g++1
II Ωn R(RRE
(we' am WVL(We)))
This algorithm is fully distributed. However, for arbitrary W and W, requires three communication
exchanges per iteration. This number can be reduced to two by choosing W W yielding
0++1_
II
(W(Wo' - a am V<(WO")))
(11)
an RR
The agent-level implementation is given in Algorithm 1. Two rounds of mixing (communications) performed by each agent; hence, we term the algorithm 2
5

---

Algorithm 1: DGD
Data: Any feasible 0% for all i = 1,.... E (0, 1]; Iterate = 1, 2....
[S.1]: Each agent exchanges of with Ni and updates
1/2 8
Σ
w VVC,
Σ
w
jEN;
JEN
[S.2]: Each agent exchanges
1+1/2
with N₁ and updates:
0 AN
11
II
Σ
ways 1/2
JEN.
4 Statisical-Computationn Guarantees
This section studies convergence of DGD?, Our first result (Theorem 1) establishes conditions under which the estimation error (1/ /m) Ei= |ll 11 shrinks linear rate up to some tolerance 2 In number of subsequent corollaries, we show that our conditions hold with high probability for the statistical models in Assumption 5, and the tolerance A within minimax statistical rates.
We begin introducing some notation. The tolerance A is composed of two terms, A and 2
(M
RI (6*)) R (VL(())
2
R (VL(())))
stat
Misspeciticatienn ettor
(MM 2
m3 p² max (R" (VL, R(II (f*)) %Elm]
3/2
P max R" (VC)(0")), jE(m)
112
where I_ (resp. I1,²) denotes the Euclidean projection onto the orthogonal complement of the subspace M (resp. onto Motic that A matches the tolerance achievable by the PGA in the centralized setting [2] star networks. The second term in A is zero if 6" E M (as in sparse vector recovery). On the other hand, A is a network dependent error, and the price for decentralization. Observe that the smaller p. the smaller A The overall tolerance is defined as
C(M,W) W)
R ( ((M,W) (1+ S(M, W) MV2(M)
(A + + +
2L
2L
where
To V2(M) p 1.5
(12)
Notice that A depends also the parameters Ty and Tæ (see Assumptions 3 and 4) via ((M, W). The first term in (12) accounts for the lack of strong convexity and smoothness in global sense of the empirical loss the same dependence is observed in the centralized setting [2]-while the second term, depending on a consequence of the distributed nature of the estimation.
We are now equipped to state the main convergence result.
Theorem 1. Consider the ERM problem (1) and associated population minimization (2), under Assumption 1, and regularity conditions in Assumptions 3 and 4 such that: R(00),
gg Σ' 1L
I and 2 (M) Tg Co.
(13)
for some constant Co > Let {(0) be the sequence generated by DGD2 with stepsize (2L) and gossip matrix W satisfying Assumption 6 and such that
-1
p S poly km max("t, Te,)
Tt
(14)
Tg

---

===1 110 -0- Then, the estimation error p² (1/m) Ei=
80 satisfies: for some constant C1 > 0,
r² S 1 - (8k) + Ci (S(M),
70 + (A9).
(15)
1- (C(M, W))/L
The expression of the constants, more general statement (Theorem 2), and its proof can be found in Appendix D. A sketch of the proof highlighting our new analysis is presented in Sec.4.2.
On the rate and tolerance: Theorem 1 guarantces lincar convergenee of the estimation error up to a tolerance O (A²). The contraction factor depends on the condition number x. of the population loss as well the network connectivity p and the tolerance parameters Ty and Tę via ((M, W latter being consequence of the lack of strong convexity and smoothness of the empirical loss globally. Notice that, for sufficiently small ((M, W), condition that holds for increasing sample size N and decreasing p. this rate is of the order of 1 - (8k)) which matches that of the PGA in the centralized setting. Referring to A², it will be shown the examples to follow (see Sect. 4.1) that, for a variety of statistical models A is of the order of the centralized statistical error, A = O(11@ 1²))))
On the conditions (13) and (14): Conditions in (13) are the same as those required in the centralized setting [2]; they are satisfied by a variety of statistical models (as those considered in See. 4.1); in particular, (MM) Tg I Co calls for minimum number of samples N which, for the models in Sec. 4.1, near (minimax) optimal. Notice that no extra conditions are imposed on the local samples size which can be small one. On the other hand, (14) is a consequence of the decontralization of the M-cstimation; it calls for a sufficiently connected network-the larger m or the more ill- illcconit the population loss (larger k), the smaller When the graph G is not part of the design and W is given, (14) can be enforced by employing multiple rounds of communications per gradient evaluations. For instance, given W satisfying Assumption 6, one can build new matrix, W = W whose associated p = || W - J|| = p satisfies (14); it is sufficient to choose
1080 ( rem" 1.5
== (1 p) log
f
Algorithm 1 is then implemented using the weights W, which results in K rounds of communications per iteration t, each one using the weights W. An E-estimate of 8r, with & O (A²). then achived in O (slog 1/e) and Ô (x(1 p) log 1/s) numbers of iterations (gradient evaluations) and communications, respectively, where Ō hides log-factors independent on the dimension If instead W is chosen according to Chebyshev polynomials [31]. the dependence on in the communication complexity can be improved to (1 - (11-p)-11 -)11/2
4.1 Statistical guarantees
We now develop some consequences of Theorem 1 for specific statistical models. Specifically, Corollary below considers (hard and (spare linear regression with ε regularization while Corollary deals with matrix completion problem. In Appendix C, study sub-Gaussian linear regression (Corollary 3) and matrix regression with nuclear norm constraint (Corollary 4).
1) Sparse vector regression: We assume that 0 is sparse. To capture hard- and weak-sparsity we let |10*1,, < Rg. with E 1]. Note that q = corresponds to vectors with support on a set of cardinality at most Ro (hard-sparsity); the case q E (0, 1] models approximate sparsity. We consider the following linear generation model over the network: y; = xr 6" + Wj. E S; and é E [m]) where wy (0, o²) is the measure noise and æy satisfies Assumption 5()). For convenience, we define me e max; (EEls) With this setup we have the following consequence of Theorem
Corollary 1. Consider the linear regression problem above via ERM (1), with R(-) = || lI R = 116* and Ω = Rd. Suppose that (13) holds, which becomes: V²(M) Ty
C₁ Rypp (logd/N)>-q/2 I Ca. for some constants Co, C1 > O, and given q [0, 1]. Let {(0))))) be the sequence generated by DGD² under the conditions of Theorem 1, where (14)
becomes P < (2(213/1)) for some constant C₁ > 0. Then, with probability at least
1 - co exp N + log(m))) for some co, C1 > 0 C3, C4 > 0, the the following holds:
r < X O (A?) + =o(A))
7

---

where
(8x)-1 1 + C3 (V [g//D) and
=
1- C3 (V (g/L)
1-3 logg dl
1/
25
(1 (1-8(a))
A Cg
112 1
and 8(4) - when q - 0, and otherwise.
Note that A above is (near) minimax optimal for either cases of = 0 and q (0, 1] [22]. Furthermore, the rate is invariant under high-dimensional scaling d/N -> oo and fixed m, as long as A stat (1), condition necessary for statistical consistency. This matches guarantees of the PGA in the centralized setting [2]. Also, (i) improves on communication complexity (5) of DGD (4) (applicable here when y - 0), which scales undesirably with d [13]; and (ii) compares favorably with [28], exhibiting same convergence rate order but sightly more favorable scaling of p with m (m12.5 vs. m²). This shows that gradient-tracking is not needed to match centralized statistical errors
2) Matrix Completion: this model. the observation yy is a noisy version of a randomly selected entry [0*] Ma))),()) of the unknown matrix @* E IPXP. We assume that ||0r| 4 S Rg. with q E [o, 1], and (e*)) denotes the i-th singular value of @ Note that = 0 corresponds to matrices O* with rank at most Rg while E (0, promotes matrices of all ranks but with relatively fast rate of decay of the singular values. Denoting by X; the p x p matrix with [X,] [X}la(]).6)) = and all the other entries zero, we can write: y, (X,, (*) + (a/d)u;j j E S and i E [m]) where (.-) is the trace inner product; w; are noise samples, assumed to be sub-exponential with parameter 1. i..dd,, and independent from X5; - vec(X,) satisfies Assumption 5(ii): a > is given, and d = p². This M-estimation can be written in the ERM form (1), with 0 = vec( () E IR with è E RPXP being the unknown matrix, and
where |10*|, -
veo(X;). We {e E IRPP; ||+|| w/p) of candidate matrices with bounded element-wise
choose the set Lo norm, with w 2 1. This eliminates matrices that concentrate too much their mass in a single position. With this setup, we can specialize Theorem as follows.
Corollary 2. Consider the ERM (1) solving the matrix completion problem above, with R(9)) ||||| and R = ||0 Suppose that (13) holds, which becomes: (p Jylog// p/N)
1/ 1-00/2 S Co. for some constant Co > and g E (0, 1]. Let {(0)m=)) be the sequence generated by DGD2 under the conditions of Theorem 1, where a reduces to
and (14) becomes p < C.m san-s,foe for some constant C₁ > 0. Then, with probability at least 1 cm + exp((ploo(()) (..o for some co > O, C2 there holds:
7 < (1 - 1/8)* o0 (A3), with A = C2Rl (p (plogn/N)² ( + o²)
Although quantitative aspects of the rates are different, Corollary 2 is analogous to Corollary 1: linear convergence guaranteed up to tolerance of the order of (near optimal) statistical minimax rates for the matrix completion problem under the soft-rank model [23]. The more demanding scaling of p with m 5.5 (vs. -2.5) is due to the slower rate the empirical loss concentrates around the population for such statistical models.
4.2 Sketch of proof of Theorem 1
We highlight here the key novelty of our convergence analysis see Appendix D for the full proof.
At the high level, our proof studies the dynamics of the estimation error r' (1/m) Σx= ||Ø| 1 using as potential function the following population instance of (10), which inherits the curvature properties of C:
m
(0) ((WO) + m 1017_w: with E(0)
D(O.).
(16)
m
Leveraging global strong- croong-convexity and smoothness of E, we establish the following decay for r'+1 (see Lemma 2 in Appendix E):
,+1 < Art + 2a(VL(Wo') -ECC://W)OOWWVVO)))- vā(Wo'),
(17)
8

---

invariance [
5000, 3050
10000L 4700
625
Estimation Enoor
20000,
1250
-4
-8
10
201
30
10
700
40
(b) Rate degrudation - Ais +
(d) Rate degradation
Afju 0.5
Estimation Enror
1250
2500
-4
Ai.. to 0.01
-4
Berations (1)
Dtenioons
Figure 1; Estimation errors vs. iterations, for DGD2 (solid lines) and NetLASSO (dotted lines): centralized statistical accuracy (horizontal dashed lines). (a) Rate invariance under d/N Growing A with and W fixed. (c) Fixed d, and m 1. with 4 (d) Same as (c) with p constant.
5, and A 0.2; (b)
for some À E (0, 1). The first term on the RHS is contractive, due to the strong convexity of E while the second term captures the discrepancy between the gradient of the empirical loss and that of the proxy population loss along the direction ( 0*). The rest of the proof boils down to carefully control this error term. This sensible; for instance, the approach used study algorithmic stability [4, 9] is not satisfactory here: it would upper bound the aforementioned inner product generating in particular the term
[VC(WO') V²
which grows indefinitely under d/n oo, the typical scaling in high-dimensions.
This suggests that the discrepancy of the gradients needs be controlled along the direction W(e* )* This is the core of our analysis. Under Assumptions 44-limittng the deviation of the empirical loss L from the population loss Ż along suitable directions and proper choices of the regularization value R and sufficiently small network connectivity p. prove that the inner product in (17) generates an error that preserves contraction (from the first term) while adding an overall tolerance, which can be made of the order of the statistical error.
Remark: Our proof differs from existing convergence studies of first-order methods in high- dimensions, both centralized [2] and distributed [13. 28]; they all use exclusively the empirical loss, decoupling the estimation error ||0 0*| in optimization || - Ql and statistical || 0- errors. While ||0 0* is known for several estimators the centralized setting [30], this is no longer the case for distributed ERM problems, e.g., as those arising from the design of some DGD- like algorithms [13]-which deal with lifted, penalized formulations-on primal-dual methods, based on saddle-point reformulations. This makes the analyses using the above decomposition problem- dependent and hard to generalize other formulations (algorithms). Our approach passing throughout the population loss bypasses this issue.
5 Numerical Results
We provide some numerical results validating our theoretical findings; more experiments (including on real data) be found in Appendix of the supporting material. All simulations are performed on a computer with an Intel i7-8650U CPU @ 1.9 GHz using 16 GB RAM running Windows 10.
We simulate the distributed s-sparse linear regression problem, in Corollary 1. We set 9 0. Ro s, Σ la, 2² 0.25, and R ||0*|]. The statistical error for this problem reads A A

---

log d/N. The communication network is generated using an Erdós-Rényi graph with agents and link activation probability p. Unspecified values above are given for each particular experiment, as needed. DGD is tuned according to the theory, NetLASSO. All curves are obtained using 10 repetitions via Montecarlo simulation.
1/(2L) 1/2: we use same stepsize for
(i) Dependence on A Fig. ((a): We set m 5, = 0.1 to generate base graph and W; we let W W with T 41, to achieve a connectivity of p 0.023 m -2.5 as required by Corollary 1. Wc plot the log-normalized cstimation error log (Il@* - 0- 1=12/|10" versus the iteration, for different values of d and N indicated in the legend and [vd], so that d grows faster than N while keeping A ~ 0.2. Dashed-line curves correspond to the solution to (1) obtained by PGA while solid-and dotted-line curves refer DGD² and NetLASSO, respectively. Fig. 1(b): We use the same fixed network W (m 5) as in Fig. (()) and plot the same quantities, now parametrized on the statistical error 2 E {1, 0.5, 0.2, 0.4, 0.01}. To do so, we fix d 20000, = -22-1111 12-1 log(d) and vary N accordingly, i.e., N E (50, 100, 250, 1250. 5000}. Discussion: Fig. ((a)-(b) validates (14): under 8, d/N growing, the convergence rate of DGD2 is linear and remains invariant, as long as A atat stays constant (Fig. 1.(a)) while algorithm's 's performance degrades when 2 increases (Fig. 1(b)). Note that DGD matches the rate of the centralized PGA and performs as good as NetLASSO without employing any gradient tracking.
(ii) Dependence on m and p. Fig. 1(c): We plot the same quantities as Fig. ((a), now parametrized 5000, s [vd], and N 2500 m n (this varying n)). We choose m E {50, 625, 1250, 2500) and generate the underlying graph such that p varies to satisfy the required condition p S m 2.5 For this, we set p = 0.8, resulting in a base graph with associated gossip Wm; we then build W m = W m. T = 7, and use such W.. in all the algorithms. Fig. 1(d): We use the same setup as in Fig. (cc) with the difference that the underlying graphs are generated so that P R 0.2, for all m. To achieve this we set the link activation probabilities to p E {0.87, 0.4, 0.22, 0.15) for the decreasing network
on m, for fixed
associated values of m. Discussion: Fig. ((c)-(d) demonstrates the necessity connectivity p for increasing m and fixed N, as predicted by out theory. In fact, under P S m 2.5 the convergence rate and statistical error remain roughly invariant, as m grows (Fig. 1(c)). On the other hand, all the algorithms break down if does not decrease with (Fig. 1(d)..
6 Concluding Remarks
We proposed DGD?, a decentralized scheme solving high-dimensional quadratic M-estimation problems over mesh networks, which employs double-mixing procedure averaging suitably iterates and local gradients. DGD2 converges linearly to statistically optimal solutions, without requiring any condition on the local sample size (but centralized statistical consistency); differently from DGD-like schemes, the rate is independent on the ambient dimension (under standard assumptions on statistical consistency of the estimators), Quite interestingly our results show that, despite common wisdom, centralized statistical consistency can be achieved over networks without employing any explicit gradient tracking mechanism but instead just mixing local gradients at sufficiently fast ratc. The analysis of other distributed algorithms for sigh-dimensional M-estimation problem remains task of future investigations.
Acknowledgments and Disclosure of Funding
Funding in direct support of this work: ONR Grant N. N00014-21-1-2673.
References
[1] A. Agarwal, S. Negahban, and M. J. Wainwright. Supplementary material: Fast global conver- gence of gradient methods for high -igh-iimnnsoonal statistical recovery. 2010.
[2] A. Agarwal, S. Negahban, and M.J. Wainwright. Fast global convergence of gradient methods for high-dimensional statistical recovery. The Annals of Statistics, pages 40(5): 2452-2482, 2012.
[3] R. Bai and M. Ghosh. NormalBetaPrinee Normal Beta Prime Prior, 2018. R package version 2.2.
10

---

[4] S. Balakrishnan, M.J. Wainwright, and B. Yu. Statistical guarantees for the em algorithm: From population to sample-based analysis. The Annals of Statistics, 45(1):77-120, 2017.
[5] A. I. Chen and A. Ozdaglar. fast distributed proximal- proximal-rradient method. 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 601-608, October 2012.
[6] J. Chen and A. H. Sayed. Diffusion adaptation strategics for distributed optimization and lcarning over networks. IEEE Transactions Signal Processing, 60(8):4289 4305, August 2012.
[7] A. Daneshmand, G. Scutari, and V. Kungurtsev. Sedond-order guarantees of distributed gradient algorithms. SIAM Journal Optimization, 30(4):3029-300 3068, January 2020.
[8] P. Di Lorenzo and G. Scutari. NEXT: In-network nonconvex optimization. IEEE Trans. Signal Inf. Process. Netw., 2(2): 2(2):100-36, June 2016.
[9] N. Ho, K. Khamaru, R. Dwivedi, M. J. Wainwright, M. I. Jordan, and B. Yu. Instability, compulational efficiency and statistical accuracy. arXiv preprint, arXiv:2005. 1411, 2020.
[10] D. Hsu, M. Kakade, and T. Zhang. An analysis of random design linear regression. arXiv preprint 106.vv1106.2363 2011.
[11] D. Jakovetić. A unification and generalization of exact distributed first-order methods. IEEE Transactions on Signal and Information Processing over Networks, 5(1):31-46, September 2019.
[12] D. Jakovetić, J. Xavier, and J.M.F. Moura. Fast distributed gradient methods. IEEE Transactions on Automatic Control, 59(5):1 131-1146, December 2014.
[13] Y. Ji, G. Scutari, Y. Sun, and Honnappa. Distributed sparse regression via penalization. arXiv preprint, arXiv:2111.0655 Nov. 2021.
[14] Z. Li, W. Shi, and M. Yan. A decentralized proximal-gradient method with network indepen- dent step-sizes and separated convergence rates. IEEE Transactions on Signal Processing, 67(17):44944406, 2019.
[15] P. Loh and M. J Wainwright. High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity. The Annals of Statistics, 4033): 2012.
[16] A. Nedić, A. Olshevsky, and M. G. Rabbat. Network topology and communication conpiiactiioocoommuuaatttoooonon tradeoffs in decentralized optimization. Proceedings of the IEEE, 106:953-976, 2018.
[17] A. Nedić, A. Olshevsky, and W. Shi. Achieving geometric convergence for distributed opti- mization over time-varying graphs. SIAM Journal on Optimization, 27(4)25577-2633, July 2016.
[18] A. Nedić and A. Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48-61, January 2009.
[19] A. Nedić, A. Ozdaglar, and P. A. Parrilo. Constrained consensus and optimization in multi-agent networks. IEEE Transactions on Automatic Control, 55(4):922-99) 9988, April 2010.
[20] Negahban and M. Wainwright. Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. The Journal of Machine Learning Research, 13(1):1665-169) 2012.
[21] G. Qu and N. Li. Harnessing smoothness to accelerate distributed optimization. IEEE Transac- tions on Control of Network Systems, 5(3): 1245-1200, April 2017.
[22] G. Raskutti, M.J. Wainwright, and B. Yu. Restricted eigenvalue properties for correlated gaussian designs. The Journal of Machine Learning Research, 11:2241-2259, 2010.
[23] N. Sahand and M.J. Wainwright. Estimation (near) low-rank matrices with noise and high-dimensional scaling. The Annals of Statistics, 1992) 2011,

---

[24] A. H. Sayed. Adaptation, learning, and optimization over networks. Foundations and Trends in Machine Leurning, 7:311-801, January 2014.
[25] W. Shi, Q. Ling, G. Wu, and W. Yin. EXTRA: An exact first-order algorithm for decentralized consensus optimization. SIAM Journal on Optimization, 25(2):944-95) 966, November 2015.
[26] W. Shi, Q. Ling, G. Wu, and W. Yin. A proximal gradient algorithm for decentralized composite optimization. IEEE Transactions on Signal Processing, 63(22))6013-6022, 2015.
[27] W. Shi, Q. Ling, K. Yuan, G. Wu, and W. Yin. On the linear convergence of the admm in decentralized consensus optimization. IEEE Transactions on Signal Processing, 62(7):1750- 1761, July 2014.
[28] Y. Sun, M. Maros, G. Scutari, and G. Cheng. High-dimensional inference over networks: Linear convergence and statistical guarantees. ArXiv preprint, arXiv:2201.085:0 Jan 2022.
[29] Y. Sun, G. Scutari, and A. Daneshmand. Distributed optimization based on gradient gradient-tracking revisited: Enhancing convergence rate via surrogation. SIAM J. on Optimization, 32(2):354 385, 2022.
[30] M. J. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint. Cambridge University Press, 2019. Cambridge Series Statistical and Probabilistic Mathematics.
[31] Auzinger Wien. Iterative solution of large linear systems. Lecture Notes, TU Wien, 2011.
[32] Xu, S. Zhu, Y. C. Soh, and Xie. Convergence asynchronous distributed gradient methods over stochastic networks. IEEE Transactions Automatic Control, 63(2):434-448, July 2018.
[33] K. Yuan, Q. Ling, and W. Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 1633):1835-1854 1854, January 2016.
[34] J. Zeng and W. Yin. On nonconvex decentralized gradient descent. IEEE Transactions on Signal Processing, 66(1 ():21)))2228444 June 2018.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] The limitations of our work
follow from the provided assumptions.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yss]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Supplementary Material
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [No]
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 5
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 5
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "rLFuGsBSVxo", "reviewer": "Reviewer_VuFR", "summary": "This paper analyzes DGD in a high-dimensional statistical estimation setting, which converges at the same rate as its centralized counterpart. This paper also provides several specific statistical estimation problems, and shows how the algorithm adapts to these problems.", "questions": "1. Line 22, should \"undetermined\" be \"underdetermined\"?", "limitations": "1. Is it possible to extend the analysis to stochastic updates?", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper analyzes DGD for high-dimensional statistical estimation problems, which is a novel setting.\n2. The analysis takes into account both the eigen gap of the weight matrix and the condition number.\n3. This paper shows how the general analysis can be applied to sparse vector regression and matrix completion problems.", "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": "mRWfOiO-oQh", "reviewer": "Reviewer_JZqb", "summary": "In this paper, the authors propose a distributed algorithm that converges linearly to the statistical precision for high-dimensional linear regression problems.", "questions": "1. There are two possible reasons to achieve the better dependency on d/N: (a) exchanging both parameters and gradients; (b) introducing multiple rounds of communication. The authors claim the reason is (a). Is it possible to show that even with (b), we cannot obtain the expected dependency on d/N?\n2. Related to the previous comment, can the authors give some insights about why (a) helps us improve the dependency on d/N?\n3. In the numerical experiments, the ratios d/N are not large. This contradicts with the motivation.\n", "limitations": "N/A.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Overall this is a good paper. The investigated problem is important. The favorable dependency on d/N is novel.\n2. I did not check the proofs, but the analysis seems sound.\n3. The presentation is smooth, although this paper is mathematically extensive.\n\nWeaknesses:\n\n1. There are two possible reasons to achieve the better dependency on d/N: (a) exchanging both parameters and gradients; (b) introducing multiple rounds of communication. The authors claim the reason is (a). Is it possible to show that even with (b), we cannot obtain the expected dependency on d/N?\n2. Related to the previous comment, can the authors give some insights about why (a) helps us improve the dependency on d/N?\n3. In the numerical experiments, the ratios d/N are not large. This contradicts with the motivation.\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": ["I don’t know"]}, "extra_text": {}}, {"review_id": "8RWvZ2OfHql", "reviewer": "Reviewer_5YHX", "summary": "This manuscript considers solving M-estimation problems over a network of agents, where the dimension d of the decision variable is much larger than the number of samples (d>>N), thus necessitating a regularizer that enforces the regularity of solution. Due to d>>N, the problem is usually ill-conditioned and do not have desirable strong convexity (why may be 0) and smoothness (which may grow unbounded with d). Thus, the authors design an algorithm building on DGD as well as a double-mixing scheme, which turns out to be enjoying a global linear convergence up to the statistical error of the model (independent of the dimension d by ignoring log factors), which is comparable to that of the centralized counterpart. The theoretical analysis they used to prove this result is based on the key idea that the gap between the gradient of ERM loss and population loss can be made arbitrarily small with multiple rounds of consensus (i.e., a sufficient number of mixing of gradients among agents). They have also developed similar statistical guarantees for several popular examples in M-estimation, such as sparse vector regression and Gassian matrix regression.", "questions": "- The proposed DGD^2 algorithm shares a very similar form with the adapt-then-combine (ATC) version of DGD algorithms. The reviewer would thus like to know if DGD of ATC version also works. If yes, this would save some communication cost since it only needs a single mixing at each iteration. If not, what is the key difference?\n\n- Will it be possible to extend the theoretical results developed in this work to stochastic algorithms which is necessary when it comes to large number of samples?\n\n- It seems that the algorithm needs to transmit variables of d dimension, incurring high communication burden as d is very large; will it be possible to reducing the communication cost?\n", "limitations": "It would be desirable if the authors can provide more insights in designing the algorithm and illustrate why the double mixing is needed to obtain the results. The reviewer guess that distributed algorithms may work as long as they employ an extra mixing on gradients.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very well written and easy to follow. The M-estimation problem considered under the high-dimension setting is very important and definitely of great interest to the machine learning community. The algorithm proposed, along with the corresponding proofs, is very interesting and seems new to the reviewer.  \n\nStrengths:\n- The paper proposes a new algorithm and proves that it enjoys a linear convergence up to a tolerance at the same order of statistical error without scaling with the dimension d. This is a new important result which is not known before to the best knowledge of the reviewer.\n- The techniques used for proving the main result seems novel and the reviewer have checked most of the proofs which seems correct. \n- The paper developed statistical guarantees for several popular examples in M-estimation, which may be beneficial to the machine learning community\n\nWeaknesses:\n- In the main result of Theorem 1, it requires an extra constraint (c.f. (14)) on the connectivity of the network, which is scaling with the condition number \\kappa and the number of nodes m. This requirement may be difficult to meet in the actual decentralized networks, especially when the value of \\kappa is large.\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": {}}]

Author rebuttal:

Decision: Accept