Acceleration in Distributed Sparse Regression
Authors: Marie Maros
Gesualdo Scutari
Venue: NeurIPS 2022 Accept (2022)
Keywords: distributed optimization
acceleration
high-dimensional statistics
linear convergence

Abstract: We study acceleration for distributed sparse regression in   {\it  high-dimensions},  which allows the parameter size  to exceed and grow faster than the sample size. When applicable, existing  distributed algorithms employing acceleration perform poorly  in this setting, theoretically and numerically.  We  propose a new accelerated distributed algorithm suitable for high-dimensions. The method couples  a suitable instance of accelerated Nesterov's proximal gradient  with consensus and gradient-tracking mechanisms, aiming at estimating locally the gradient of the empirical loss while enforcing agreement on the local estimates.  Under standard assumptions on the statistical model and tuning parameters, the proposed method is proved to  globally converge   at {\it linear} rate  to an estimate that is within the {\it statistical precision} of the model. The iteration  complexity scales as $\mathcal{O}(\sqrt{\kappa})$, while the communications per iteration are at most $\widetilde{\mathcal{O}}(\log m/(1-\rho))$, 
 where $\kappa$ is the restricted condition number of the empirical loss, $m$ is the number of agents, and $\rho\in (0,1)$ measures the network connectivity. As by-product of our design, we also report    an accelerated method for high-dimensional estimations over  master-worker architectures, which is of independent interest and  compares favorably with existing works.

Acceleration in Distributed Sparse Regression
Maric Maros
Gesualdo Scutari
School Industrial Engincering
School Industrial Engincering
Purdue University mmaros@purdue edu
Purduc University gscutari@purduee edu
Abstract
We study acceleration for distributed sparse regression in high-dimensions, which allows the parameter size to exceed and grow faster than the sample size. When applicable, existing distributed algorithms employing acceleration perform poorly in this setting, theoretically and numerically. We propose accelerated distributed algorithm suitable for high-dimension The method couples suitable instance of accelerated Nesterov's proximal gradient with consensus and gradient-tracking mechanisms, aiming at estimating locally the gradient of the empirical loss while enforcing agreement the local estimates. Under standard assumptions statistical model and tuning parameters, the proposed method is proved to globally converge at linear rate to estimate that is within the statistical precision of the model. The iteration (i.e., gradient oracle) complexity scales as OVKK), while the communications per iteration are at most (log m/(1 p)), where x. is the restricted condition number of the empirical loss, m the number of agents, and P E [0, measures the network connectivity. As by-product of our design, we also report an accelerated method for nigh-dimensiooal estimation over master- worker architectures, which is of independent interest and compares favorably with cxisting works.
the
1 Introduction
Consider a multiagent system composed of m machines, connected throughout a fixed, undirected graph-we will refer such networks as mesh networks, in contrast centralized topologies such as master-worker architectures, where there exists a node connected to all the others. The ultimate goal solve the stochastic (quadratic) optimization (learning) problem
8* argmin DER
f(0) ( -_E(x)))>(2
y)²1
(1)
Each of the agents has access to i.i.d observations, drawn from the unknown, common distribution F on Z C R2, and collected in the set S;. The associated local empirical estimate of reads
(0)
Σ (1) - JES.
2n
where x, E IR is the vector of predictors and y E R the associated response. The overall Empirical Risk Minimization (ERM) over the network is then
Ø E argmin
(())
1
Σ
f(00)
(E0:R10)
where a (convex) regularizer (with 0) and Ω is some (convex) subset of IRd
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

We study estimators under high-dimensional scaling, meaning that the ambient dimension d exceeds (and grows faster than) the total sample size N = m n. The desired parameter 6* is assumed to lie in smaller subset of S2 or is well approximated by member of it-such structural constraints are enforced by the regularizer R in (3). Examples include sparse linear models with & regularizers, low-rank matrix recovery via nuclear norm, and matrix regression with soft-rank constraints [1].
The goal is to compute an estimate of #* by solving the ERM (3) that is within the statistical error of the model |0 - 0*11. We target first-order methods. Despite the vast literature of distributed oplimization (see Sec. 1.1), only very recently such guarantees have been established on mesh networks for the LASSO problem in the projected form [26] [as (3)] and in the Lagrangian form [11]. The benchmark is the scheme in [26]. termed NetLASSO: under restricted notions of strong convexity and smoothness of f (see Sec. 2) which hold with high probability for a variety of data generation models as well log d/N = o(1) a condition necessary for statistical consistency in s-spare linear regression-the iterates generated by NetLASSO reach an s-neighborhood of a statistically optimal solution in
Ö ( ("II log 1/E) number of communications,
log
where 6 2 is the condition number of f in (3) restricted to sparse directions, and E [0, 1) measures the connectivity of the network-the smaller the more connected the graph (Ó hides log-factors on optimization parameters). This shows linear rate up to statistical precision, whose dependence on K matches that of the centralized Projected Gradient Algorithm (PGA) [1].
Since the bottleneck in distributed systems is often represented by the cost of communications (in comparison with local computations) [6. 15], a key question is whether the communication complexity (4) is improvable while still preserving the same statistical guarantees and local computational complexity (first-order methods). This is particularly sensible when dealing with ill-conditioned population losses, resulting in very large values of k. To improve the dependency on K, a natural approach is to employ some form of acceleration. Despite the vast literature of accelerated methods in distributed optimization, this remains an open problem in high-dimensions, as elaborated next.
1.1 Distributed acceleration in high-dimensions: Challenges and open problems
Accelerating first-order methods over mesh networks (undirected graphs) has received attention in the last few years; distributed schemes in the primal domain include [22, 32, 33, 14, 12, 24] while [25, 28, 13] are accelerated dual or genalty-based methods. They are suitable to solve distributed, unconstrained, smooth optimization problems, with the exception of [33], which decentralizes the accelerated proximal-gradies method, and thus is applicable also to the constrained ERM (3).
Albeit different, when applicd to the minimization of a -s-moohh and Ht-strongly convex loss f == 1/m E fa with cach f. being Lmoohh and p,.-trongly convex, they all provably achieve linear convergence to the minimizer of f. some [25, 13, 14, 12, 28] with communication complexity scaling with /ke (Ng max; L,/ min; μ4 is the local condition number) while others [32, 33. 24] with Vky (Ky- L/ f/p is the condition number of f). Note that in general Ky < Kg; hence, the latter group is preferable to the former. For weakly convex losses fi s, convergence is certified at sublinear rate, the optimality gap on the objective value vanishes as ((1(t²), where / is the iteration index.
When applied to the constrained ERM (3) in high-dimensions. these convergence results are unsatisfac- tory. First, they are of pure optimization type. and do not provide any statistical guarantce- computing below the statistical noise would result in a waste of resources. Second, for fixed d and N, with d > N thigh-dimensions), they would certify sublinear convergence rates, as the empirical loss f is convex but not strongly convex globally the d x d Hessian matrix 2 f has rank at most N. This provides pessimistic, non-informetive predictions, which contrast with (4), proving instead that linear rates up to the statistical precision are achievable by nonaccelerated distributed methods. Third, under the scal- ing d/N -> oc (d growing faster than N) typical regime in high-dimensions [29, c/-convereence analyses in the aforementioned papers break down; they all require global smoothness of the local fi's and global f losses, property that does not hold when d/N + oo. If fact, for commonly used designs of predictors x, 's, the Lipschitz constant of V grows indefinitely with d/N [29]. Fourth, if never- theless simulated, the only distributed accelerated scheme applicable to the constrained ERM (3), that is DPAG [33], performs poorly in high nigh-dimensions, as Fig. shows. In the figure we plot the average
2

---

estimation error, defined as (1/m)
- |00 Σi
0* 11, versus the iterations indexed by f. where of is the
estimate of f* from agent i at iteration generated by DPAG solving projected LASSO over a mesh
network (a special instance of (3) with (0) | and 0 is the population s-sparse minimizer in (1). We contrast DPAG with the new distributed accelerated method proposed in this paper. As benchmark, we also plot the estimation error generated by NetLASSO (non-accelerated method) [26].
Despite the good performance of DPAG in low- dimensions (i.c., N > d) [33], the figure shows that acceleration as in DPAG is no longer effective in high- dimensions (d N); DPAG achieves estimates of 6* that are worse than those achievable by non accelerated schemes, yielding estimation errors that much larger than centralized statistical ones. Further, in our exper- iment we observed that this gap grows with d/N. In
DRAG
Ned.as50 TM
Cervellre Seieeee
Estimation Ervor
contrast, the proposed distributed acceleration exhibits linear convergence up to centralized statistical precision, at rate faster than the nonaccelcrated NetLASSO.
20
140
Derntton
Wc conjecture that the unsatisfactory performance of DPAG [33] is due to the following facts: (i) the empir- ical loss of LASSO is strongly convex only over sparse vectors (see Sec. 2). Hence, fast convergence is expected only when traveling such curved region of the land- scape; (ii) the scheme [33] can be interpreted as a decentralization of the accelerated proximal gradient based on the Nesterov's first method [21]; as such, it does not implement any mechanism enforcing the trajectory at which gradients are evaluated to be (approximately) sparse. This suggests that acceleration in the distributed high-dimensional setting needs to be rethought-new designs and convergence analyses are needed. This is what this paper is about.
Figure 1: Projected LASSO: Average estimation error vs. iterations. Existing distributed accelerations (DPAG) may not work high- dimenninn!iinn The proposed acceler- ated method outperforms nonaccelerated distributed schemes (NeLLASSO) while achieving centralized stafistical accuracy. See Section A.2 for details
1.2 Main contributions
Algorithm design: We propose distributed algorithm for high- figh-dimensional estimation achieving acceleration provably. The method decentralizes Nesterov's 's accelerated proximal gradient (form III) [20] via consensus dynamics and a gradient tracking mechanism [7, 30, 19], the former enforcing an agreement on the agents' estimates and the latter aiming at tracking locally the gradient of f.
The rationale to hinge on Nesterov's 's third scheme rather than form I, as used instead so far in all accelerated distributed algorithms, is to enforce feasibility (with respect to the norm ball constraint R(0) < R) of the momentum-scqueeee evaluated. For instance, when solving a constrained LASSO (i.e., R(0)= = [[@][1), this yields sequences that are approximately sparse, thus traveling the landscape of an "almost" strongly convex and smooth loss. In fact, our analysis shows that this is the key enabler to retain fast, linear convergence to statistically optimal solutions in high-dimension, where f is no longer strongly convex globally.
generated by the algorithm. the one over which gradients are
guarantees: Under standard notions of restricted strong convexity and smoothness of the empirical loss, which hold with high probability for variety of statistical models, and proper algorithm tuning, the iterates generated by the proposed scheme converge at linear rate to limit point that is within fixed tolerance from the unknown 0* When customized to specific statistical models-
cnntisical-computttiei
sparse linear models with & regularization, low-rank matrix recovery with nuclear norm, and matrix completion-the tolerance becomes of the order of the statistical error ||@ 1*1 Specifically, for such models and arbitrary network connectivity p. the iterates generated by the algorithm enter an e-neighborhood of a statistically optimal estimate of 8* after
log 1-p log 1/E
o (Vk 1/E) and δ
(5)
numbers of iterations (gradient evaluations) and communications, respectively, where Ô hides log- factors on optimization parameters (recall k is the restricted condition number). This improves on the communication complexity (4) of NetLASSO [26] applied to L fj-constrained LASSO, showing the more favorable square-root scaling on K, typical of accelcrated methods in low-dimension. Furthermore, the rates in (5) are showed to be invariant under figgh-iimnssioall scaling d/N + oc.
as long as the statistical error ||@ 6*| remains constant.
3

---

A special case: A by-product of the proposed method is its customization to master-worker architec- tures, which is of independent interest and compares favorable with existing accelerated centralized designs [16, 311, proposed for fi-least squares (in Lagrangian form); they are double-loop methods, combining the accelerated proximal gradient method [27, 5, 20J with homotopy continuation.
2 Setup and Background
This section states the main assumptions on the ERM (3) and the network underlying our derivations.
We anticipated that, in high-dimension, ff in (3) is not strongly convex uniformly (as d N). However, strong convexity and smoothness hold along restricted set of directions, for a variety of statistical estimations [29]. which is enough to employ fast convergence and favorable statistical guarantees of the PGA [1]. Here we postulate the same properties for the landscape of
RSC & RSM:
Assumption (Global RSC & RSM [1]). The loss function in (3) satisfies
(i) Restricted Strong Convexity (RSC) with respect to R with (positivee parameters (1/2, Tu) over Z:
f(x) - f(y) - (Vf(y), x - y) 2 4 || v112 - R - -y), Yx, E 92
(6)
2
(ii) Restricted Smoothness (RSM) with respect to R with (positive) parameters (2L, TL.) over Ω:
f(x) f(v) - (V)),, < L|| - + TL R²
v), Vr,y E
The restricted condition number is defined as K A L/P and it is assumed k 2 1.
In the distributed setting, the RSM property required to hold also locally. Assumption 2 (local RSM). Each loss function fa satisfies local RSM with respect to RR with (positive) parameters (2 Tt) over Ωt
[(x) fi(1) (VI(V), x- v) < ve [ y112 + Te R² v), Vx, E 9
(8)
This notion plays key role for statistical consistency of in high- dimension [1]. Decomposability is defined with respect two subspaces of 52, namely: M, known as the parameter subspace, capturing constraints from the model (e.g., vectors with particular support or a subspace of low-rank matrices); and M referred as perturbation subspace, representing the deviations from the model subspace M. We also require Lipschitz continuity of RR over M.
Decomposable regularizer R:
Assumption 3. (i) The regularizer R. : Ω + R is norm, with Ω C Id convex and 0 E Ω without loss of generality. Furthermore, given a subspace pair M+) such that MCM:
(ii) R is (M, ----)-dccopossale that is, R(x + y) = R(x) + R(y), for all x E E and y E MM=;
(ii) When M + {0). R is (ipssiissttttz over M with respect to some norm su R(0)/10011. If M {0), we set ({0)) O.
||: ((M) A
Regularizers sharing the above properties over certain pairs M+) are ubiquitous in M-cstimation problems [29]; examples include the & norm, the (overlap) group norm, and the nuclear norm.
Statistical models: RSC and RSM properties 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 E regularization, low-rank matrix recovery with nuclear norm, and matrix regression with soft-rank constraints [17, 29].
Assumption 4. The random predictors I; Rd are i..dd. and fulfill one of the following conditions:
(i) va ~ N(O, E) and are i.i.d., for some Σ > 0;
(ii) v, are (72 E) subb-uusanss and ii.dd, with Σ, > 0; (iii) x, = ej where j ~ uniform(L, d) and i..dd

---

Lemma 1. Under Assumption 4(i), there exist universal constants Co. C1, C2 > O such that, with co expeep(-ee -c N + log m). N 2 10, Assumptions hold with parameters
probubility at least
I Amin
Tu - o2 /N and L = Xmax
TL - c2 (x:))
and so does Assumption 2 with parameters "t (2m + 1)d (E) and Ti C2 (E where R$ is the dual norm of R. When R(-)) = 111. (E(R (2,))) & ( log(d).
The proof of Lemma follows from that of [1. Prop. 1J. Similar results under Assumptions 4(ii)-(iii) can be found in the supplementary material, sce Appendix A.7.
On the network: Agents are connected throughout a communication network, modelled as an undirected graph G = (V, E) where the vertices V = [m] {l,.... m) correspond to the agents and & is the sct of edges of the graph; (i,,) if and only if there communication link between agents and j. The set of neighbors of each agent is denoted by Nr & (j E V: (t,5) E E) U {i). In the proposed algorithms, agents will average neighbouring information using weights as below.
Assumption 5 (Gossip matrices). Define W = [wa m the following hold: (i) W is G-congruent, that is, Wij > 0, if (i E ε; otherwise Wij 0; furthermore, wa > 0, for all i E [m]; (ii) W = W and W1 = (stochastic); and (üi) there holds _ |[ Jlla < 1, where J 2 11 /mm
Assumption 5 is quite standard in the literature of distributed algorithms and is satisfied by several weight matrices; see, c.g., [18]. Note that & < 1 by construction, as long as G is connected. Roughly speaking, P measures how fast the network mixes information; the smaller p. the faster the mixing,
3 Algorithm Design
At the core of our distributed accelerated algorithm there is an instance of Nesterov's acceleration proximal gradient method, which we identified be suitable for nigh-dimensional estimation. We begin presenting this method in the centralized setting, along with its statistical guarantees (Sec. 3.1); we then proceed design and analyze suitable decentralization mesh networks (Sec. 3.2).
3.1 Warm-up: A Nesterov's acceleration (form III) for high-dimensional estimation
Consider (3) in the centralized setting (e.g., moster-worker systems). Assumption shows that f is strongly convex and smooth only along a restricted set of directions. To enable fast convergence, the algorithm design should produce trajectories (approximately) traveling such portions of the landscape of f. To handle this situation while achieving acceleration we propose to use Nesterov's 's method written in form III [9, Algorithm 11] equipped with the projected operator to enforce feasibility of all the sequences generated by the algorithm. This ensures that gradients are always evaluated at feasible points of (3), which we prove unlock lincar convergence (up to a tolcrance) at accelcrated rate.
Given feasible 80 and t the main iterate {0r, vt, 2²) of the algorithm reads: for any 0, 0.1.....
B
+
ve,
B+1
3+1
H11 HAN
(1-/)e² + --²²
a -
3 -V(()))
0+ = =B + (1-
where E (0, 1) and B (0, are parameters tune, and R denotes the Euclidean projection (of its argument) onto the convex set {0 E Ω R(v) < R); for specific estimators such as l constrarrdee or Lagrangian LASSO, this projection has a closed form expression [8, 11]. Notice that, under feasibility of 8 and e0, the sequences (6'), {v²} and {Ø*} feasible, for all t.
wide variety of accelerated methods exists in the centralized setting (see, e.g., [9] for a recent overview), and most variants settle the infeasibility of the z' sequence using two projection (proximal) operations per iteration (see, e.g., [3)). The algorithm in (9) performs instead one projection per iteration. Variations of the theme can be found in a number of references, including [2, 9. 27, 10]. Existing analyses however are not adequate to capture the behaviour of these methods high- dimensions, including (9); as discussed in Sec. 1.1 for distributed implementations, they would
5

---

provide pessimistic predictions and break down under the scaling d/N - cc. As by-product of our novel convergence analysis in the distributed setting, Theorem below establishes, under RSC and RSM properties (Assumption 1). global convergence of the algorithm in (9) at linear (accelerated) rate to a fixed tolerance. This result is of independent interest, and complements existing accelerated schemes for & lleast squares estimations (LASSO in Lagrangian form) [16. 31J. These are doublc-loop methods, combining accelerated proximal gradient with a homotopy continuation mechanism.
Leveraging Assumptions 3, let us introduce the tolerance A and the initial optimality gap VO: A A 22 M (0*)) + 2 (A*) + (MM)I1471) ? v A s(0)) ((0)
_4 1 0|? (10)
where A - 0r i is the satistical error, M- denotes the Euclidean projection onto the orthogonal complement of the subspace M, and T (M) defined in Assumption 3. Convergence is stated next.
Theorem 1. Given the ERM (3), suppose (i) satisfies the RSC/RSM conditions (Assumption I); (ti) R. is a decomposable regularizer with respect to chosen pair of subspaces (M,M) (Assumption 3); and (iti) MM and RSC/RSM parameters (H,TT) Tu) and (L,TL) are such that (²(M) max (TL, S Co. for some constant Co > 0. Let {0t Je21 be the sequence generated using Algorithm (9), with tuning 2L and B 11((8n). Then, for any solution 1 of for which R(Ø)- R, have
(1
|10' 0| v
8 J
V + O
Tu + TL A2
(11)
16k
1
This proves linear convergence at the accelerated rate 1- 1/616K), up to fixed tolerance. As it will be showed directly in the distributed setting (see Sec. 4), when considering specific statistical models under 2 (M) max {TL, = o(1)-a condition necessary for statistical consistency [1, 29]-the residual error in (11) becomes smaller than the statistical precision, proving thus convergence to statistically optimal solutions. This improves the convergence rate of the PGA [1], with Algorithm (9) gaining acceleration while retaining the same statistical precision and computational complexity.
Finally, we remark that, while Theorem 1 has been stated for quadratic ERM, the same conclusions hold for nonquadratic losses, satisfying RSC/RSM conditions as in Assumption 1.
3.2 Distributed accelerated proximal gradient method for high-dimensional estimation
Equipped with Algorithm (9), we are ready to introduce our accelerated method for distributed high-dimensional estimations in the form (3), as given in Algorithm 1 below, and discussed next.
What prevents (9) from being implemented on mesh networks is the lack of knowledge of V the agents' sides. Agents' losses fi's ss are decoupled by introducing local estimates 0, controlled (updated) by the intended agent, along with the associated sequences z; and Us which play the same role of z and v as in (9): first, they are locally updated as the related ones in (9), followed by the consensus step (16), enforcing agreement among the momentum sequences and local estimates. The update of the e-variables, as per (9) would require the knowledge of V f from each agent, an information that is not available, Hence, f replaced by local estimate y [see (13)]; the tracking of V f via each y/s is employed by the dynamic consensus mechanism (a.k.a. gradient-tracking! [7, 30, 19] in (14). In fact, not difficult to check that the average of the yf 's tracks the average of the local gradients fi(z)) i.e.,
m
m
(12)
m
M
Assuming that consensus on the 2 's and the y, 's variables is asymptotically achieved, i.e., || 2i|l + O and ||æ| - ازل + 0 as f + oo, for all i,j = 1,... m (a fact that will be proved), (12) would yield the desired gradient tracking property (x() - xfll + as t + co, for all = 1,...,m. m.
4 Statistial-CComptationn Guarantees
This section studies convergence of Algorithm 1. Our first result (Theorem 2) is of deterministic type: We establish conditions for the estimation error (I/m) Em ||0| 0|2 to shrink linearly

---

Algorithm
Data: Set 0g = vi - =- and y (0) for all i E [m]]; a 2 2L and (0, 1);
Iterate = 0, 1,
[S.1]: Consensus and gradient-tracking Each agent performs
2
Σ
Wi
+ 03 + 1+ 03)
(13)
JEN,
b =
Σ
(v}
+ [z)()) - v5(g 1)
(14)
JCN
[S.2]: Local Optimization and updates: Each agent performs
p r-1 ()N)(()) (1- B)ut + B21 got
a
(15)
0 Befth + - 8)0
(16)
up to a tolerance. These conditions hold with high probabbobybility for a variety of statistical models (Assumption 4), proving linear convergence (at accelerated rate) within minimax statistical rates.
Theorem 2. Consider the ERM (3) over mesh networks, under the same assumptions (i)-(iii) as in Theorem I; furtherrore, (iv) suppose fi satisfies the local RSM condition (Assumption 2), for all i E [m]. Let (0)))mm))) be the sequence generated by Algorithm 1, with tuning a 2I, and B /1/(8)), and weight matrix W satisfying Assumption 5, with such that
L R
Ss C1 min
VR-L
(17)
ma/2 (7 + (M +T))
where C₁ > a universal constant (see Theorem in Appendix A.4).
Then, for any solution á of for which R(9) R. we have: for some C2 > 0,
100 212 < 1
L 0
Tu TL
+
Ti TLV mp
(18)
32k
centridized precision
network
where L E 0o) captures the initial optimality gap and dependence on optimization and RSC/RSM parameters (its expression can be found in Theorem 3, Appendix A.4).
This shows linear convergence at rate 1 - 1/((3k) to tolerance. The first term of this tolerance matches that achieved in the centralized setting (see (11)) while the second term is extra error due to the decentralization of the estimation process-it vanishes when p = 0 (fully connected network). In the next section, we will show that for the statistical models captured by Assumption (i), the overall tolerance can be made of a higher-order of the centralized statistical error. The condition on p (17) calls for a sufficiently connected network. When it is not satisfied by the given network and gossip matrix W, it can be enforced running multiple rounds of communications, affecting the total communication complexity by log-factor terms. More specifically, given W/ with associated ||W Jl22 larger than what required in (17), one can build another matrix W W and choose the positive integer number K that A ||
J n satisfies (17); it is sufficient to set
log km 2.5 (15 C2/L)
K
1-p p
The use of W instead of W in Algorithm 1 corresponds to employing K rounds of communications (consensus and tracking updates) per iteration t, each one using the weights W.
4.1 Statistical Guarantees
We apply now Theorem to specific statistical models, establishing convergence and statistical guarantees with overwhelming probability. Corollary studies the case of sparse linear regression,
7

---

under both strong and weak sparsity. Corollary addresses the low-rank matrix recovery problem. Sub-Gaussian linear regression (Corollary 3) and matrix completion (Corollary 4) are discussed in the supporting material (Appendix A.3).
Suppose O* in (1) is sparse, i.e., ||0 S Rg. with & E [0, (q corresponds to hard-sparsity, while > 0 models weak sparsity). The regression model at agent is: y =j lr + w J S,, where SS n, wy *N(0,, o²), and xy satisfies Assumption 4(i). Define
Sparse regression:
max, ((2)a)) Amin () R₂ (log d
1- q [0,1] and Ro
XN
Corollary 1. Consider the ERM solving the linear regression problem above, with R(:) = || 111. |1011 S R |10]1, and Ω = R4; let N (( (R)))),))/// 2/11//12//2)) [ log d). Let ((0))=)))) be the sequence generated by Algorithm with tuning as in Theorem 2, where (17) becomes
}. for some C₁, C2 > O.
K 22 (1 (2/1)
PS C1 min
VK-
(19)
Then, with probability at least
co exepp (-c log(m)) for some co: c1 0, it holds
m Σ
10: -
8
(1-V3))
111
1
1
L O XN Rg
log d
1-2 + [(AT1P)) (20)
Amin (Σ)
32x
N
where L > 0 depends on the the initial optimality gap and statistical parameters (see Appendix A.6)
A few comments are in order. (i) Linear convergence at rate 1 - ((x-1/2) is certified, up to tolerance that, under the sample-size N = ((
log d), is of a higher order than the
centralized statistical error || 2 In fact, the additional term R&( ) 1-90/2 due to the statistical nonidentifiability linear regression over the ball and thus not improvable, is no larger than || with sigh-robbbiiltt.. (ii) The aforementioned scaling on N is unavoidable, as it matches that necessary for any (centralized) method to be statistically consistent over lg -ball [23]. This proves that statistically optimal estimates are achievable over mesh networks even when the local sample size violates information theoretical lower bounds (as long as N satisfies so). This is possible thanks to the network mixing local information sufficiently fast rate, as required by (43). (iii) As anticipated, condition (43), when not implicitly satisfied, can be met running multiple rounds of communications/ieraatiii it can be shown that Olog m/ p)) are enough, resulting in overall communication complexity as in (5) to reach an e-neighborhood a statistically optimal estimate.
We consider the compressed sensing version of the matrix regression over meshed networks, as formulated next. Let O* in (1) satisfy ||@*|l, S Rg, with E [0, 1] and R2 > 0. In that the case g O corresponds to matrices with rank at most
Low-rank matrix recovery:
will have Ro The case q > 0 results approximately low-rank of @*, Consider observations yj (X,, θ*) + wj j E S, [S|] n, where X, E R p is such that vce(X,) satisfies Assumption 4.(i), wy NO are i...d. and independent of Xj. Define
max, (12)at R.
P 2-2-8 N
XN
q E [0.1) and Ro =
Amin
Corollary 2. Consider the ERM (3) solving the ronk matrix regression problem above with ||0]|, and Ω = Rexp; let N Ω (p(mp:R,,) (p((n=:R,)1/Uu44(2))
Let (0 be the sequence generated by Algorithm with tuning as Theorem including (17) for some C1, C2 > O. Then, with probability at least 1 exp ( ( + log(m)), for some
R(()) = ||0|,, ||0*|] S
Co, C1 > 0, holds:
m
10 0012
(1-V3)
L +0
XN
Rg
P N
1-3 +
IIA))))
m
Amin (E)
32k
where L > depends on the the initial optimality gap and statistical parameters (see Appendix A.6).
8

---

(a) Rate bifariance + 00
0.2
Rate invariance IN - 00 (mrr)
(e) Real data: train
109
Entimation liror T.TIT
109
5000
NetLASSO
20000
Th
625
Algorithm
Estimation Errar
10
1250
10-1
10-2
10-1
3
10 3
10-3
10
10
100
150
200
20
60
80
100
120
5
Iterations (f)
Iterations (1)
Iterations (t)
(b) Degradation with
(d) Rate degradation
p 0.
Real data:
109
100
211
50
Achieved PGD
625
NeiLASSO
Estimation Eroor
Ediimation Ernor
2n 1250
Algorithm
10-1
10-7
Prodiction
10-1
10-2
10-2
10-3
10
0
200
400
600
800
1,000
1,200
20
40
60
80
100
0
5
10
15
20
Deeaatins (f)
leratiins (1)
Iterations
Figure 2: Algorithm (dotted-lines) vs. NeILASSO (solid-lines). (a) Linear convergence vs iterations up to statistical precision (dashed) A for s, d, N growing, such that A z 0.2. (b) Estimation error vs iterations for different values of k. (e) Estimation error iterations for growing such that p = O( 2.5). (d) Same (c) but with P = 0.2. (e)-(f): eyedata data set, (e) training error vs. iterations. (f) testing error vs. iterations.
Although quantitative aspects of the sample rates are different, Corollary 2 is analogous to Corollary 1,
which refer for specific comments. As therein, also here the final tolerance is of higher-order of the statistical error of the model.
Overall the above statistical guarantees (along with those discussed in the supporting material for other estimation problems, see Appendix A.3) complement [1], matching those therein but over meshed networks while improving convergences rate of the PGA gaining acceleration.
Numerical Results
Numerical results are presented in this section validating our theoretical findings on synthetic and real data. Simulations are performed computer with an Intel i7-8650U CPU @ 1.9 GHz using 16 GB RAM.
Synthetic data: We simulate the sparse linear regression model as in Corollary 1, with q = 0. We set Rg s, 0² 0.25 and R ||0+1|2. The covariates x; E Ed are generated as in [1] Lijj = Zij + WTi with 11,1 = 24,1, where each 2ij NN0 1) and i.i.d. This implies that > n (1 w) and L L' 2((1+ (1 w)) We will denote A & (slog d)/N, which is of the order of the statistical precision of the model. The network is generated using an Erdōs- Rényi graph, with m agents and link activation probability p. The specific values of each of the parameters is given in each specific experiment. All curves are averaged over 10 independent Montecarlo simulations. We now proceed to verify the different aspects of Corollary 1.
Fig (.(a) plots the normalized estimation error E, 110 01 I versus iterations, generated by Algorithm (dashed-lines) and NetLASSO [26] (solid lines), solving the regression problem, with w = 0.5 (yielding μ = 0.44 and = 5.33); different curves refer to different values of 5, d, N. with d growing faster than N, such that A x 0.2, and m = 5. In both algorithms we set the stepsize a = 2L': the momentum parameter 3 is set to 3= (8p' (L)) 1/2, Condition (43) enforced via = rounds of communicationn/iteaatiioo for both algorithms. In Fig. 2.(b) we plot the same quantities now for different condition numbers obtained choosing w E (0.1, 0.2, 0.5). The following comments are in order: (i) As predicted by (20), Algorithm 1 convergences at linear rate to statistically optimal estimates; although it has the same computational cost per iteration of the nonaccelerated NetLASSO, it is much faster, especially when Σ is ill-conditioned (large r), which proves the advantages of acceleration also in high high-dimensions.
1) Linear convergence to optimal estimates:

---

(ii) As d and N increase, as long as A is constant, the rate and reached statistical accuracy remain roughly invariant. (Fig. 2.())), which a resirable property.
2) On the scaling of with m as in (43): Fig. 2.(c)-(d) plots the same quantities as in Fig. 2(a), now with fixed d = 5000, s = [vd] .V.
m 2500, and varying m E {50, 625, 1250]. The 2.5) (this is achieved setting p = 0.8) while
random graph is generated so that in plot (c) p z (mm)) in plot (d) x 0.2 for all m (achieved setting p E {0.7, 0.4, 0.22} for the associated values of m). The number of communications/teraine
set to for both algorithms. The two plots show that p should decrease with m if one wants to achieve centralized statistical consistency; O(m 2.5), as predicted by (43), seems to he sufficient. On the other hand, a p constant with m breaks down the performance of both distributed algorithms.
(B) Real data: We test here NeILASSO and Algorithm 1 on the data set eyedata in the package [4]; d = 200 and N 120. We generated W for m = 10 and p 0.9. To achieve the required connectivity we set W W7, The data set is split between test- and training-data, corresponding to Nest = 40 and Nerain = 80, respectively. Both data sets are cqually distributed across m 10 agents. In Fig. 2.(c) we display quantitites relevant to the training phase. Specifically, we plot the objective function value along the iterates generated by NetLASSO and Algorithm We observe that both schemes achieve similar final objective function value and converge linearly, with Algorithm 1 at much faster rate. Fig. 2.(f) shows the performance on the test data. We implemented the following procedure. Denote by y the output the test-set and by X the test covariates. We build predictors y X E [m]] where ff is the estimate of 6* from agent at time t, generated by the two algorithms when running on the training set. The figure plots Ti (Ness: 2i-1 Ilv - 2 versus iterations, for NetLASSO and Algorithm 1. The dashed line corresponds ()) -ll +ly 011?, where ý = X and 0 denotes the estimator obtained via the PGA. The performance on test-data are consistent with what observed already on training-data.
Conclusions
We proposed a decentralized accelerated algorithm to solve quadratic high dimensional estimation problems over mesh networks whose empirical losses are neither strongly convex nor Lipschitz smooth globally. To employ acceleration in this setting, the design hinges on careful considerations regarding the directions traversed by the schemes, enforcing sparsity of the iterate and momentum sequences. Global convergence to statistically optimal solutions is proved liner rate, proportional
to VR, with a communication cost per iteration at most Ô (logm/(3 m/(1 p)) is unclear whether this communication cost is improvable, for instance, whether the log-dependence on the number of agents and the transmission of d gradient/iterate components can relaxed. This left to future investigations.
Acknowledgments and Disclosure of Funding
Funding in direct support of this work: ONR Grant N. N00014-21-1-2673.
References
[1] Alekh Agarwal, Sahand Negahban, and Martin Wainwright. Fast global convergence of gradient methods for high- high-dimenssonal statistical recovery. The Annals of Statistics, 40(5):2452-2444 2482, 2012.
[2] Alfred Auslender and Mark Teboulle. Interior gradient and proximal methods in convex and conic optimization. SIAM J. Optimization, 16:697-725, 2006.
[3] Michel Baes. Estimate sequence methods: extensions and approximations. Institute for Operations Research, ETH, Zütrch, Switzerland, 2009.
[4] Ray Bai and Malay Ghosh. On the beta prime prior for scale parameters in high -igh--iinnsional bayesian regression models. arXiv preprint
2018.
[5] Amir Beck and Mark Teboulle. A fast iterative shrinkage-threshold algorithm for linear inverse problems. SIAM J. Imaging Sci., 211):183-202, 2009.
10

---

[6] Ron Bekkerman, Mikhail Bilenko, and John Langford. Scaling up Machine Learning: Parallel and Distributed Approaches. Cambridge University Press, 201
[7] Paolo Di Lorenzo and Gesualdo Scutari. NEXT: In-network nonconvex optimization. IEEE Transactions on Signal and Information Processing over Networks, 2(2):120-133 136. 2016.
[8] John Duchi, Shai Shalev-Shwartz, Yoram Singer, and Tushar Chandra. Efficient projections onto the bblll for learning in high dimensions. Proceedings of the 25th International Conference on Machine Learning, pages 272-279, July 2008.
[9] Alexandre d' Aspremont, Damien Scieur, and Adrien Taylor. Acceleration methods. Foundations and Trendsw in Optimization, 1(1-2): 2021.
[10] Alexander Gasnikov and Yuri Nesterov. Universal method for stochastic composite optimization problems, Computational Mathematics and Mathematical Physics, 58:48 64, 2018.
[11] Yao Ji, Gesualdo Scutari, Ying Sun, and Harsha Honnappa. Distributed sparse regression via penalization. arXiv preprint, (0Xi::2//100652: Nov. 2021.
[12] Dmitry Kovalev, Adil Salim, and Peter Richtárik. Optimal and practical algorithms for smooth and strongly convex decentralized optimization. Advances in Neural Information Processing Systems, volume 33, 2020.
[13] Huan Li, Cong Fang, Wotao Yin, and Zhouchen Lin. A sharp convergence rate analysis for distributed accelerated gradient methods. arXiv preprint, arXiv:1810.01053 2018.
[14] Huan Li and Zhouchen Lin. Revisiting extra for smooth distributed optimization. SIAM J. on Optimization, (0(3):195--883 2020.
[15] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems, pages 5330-5340, 2017.
[16] Qihang Lin and Lin Xiao. An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization. Comput. Optim. Appl., 60:633 674,, 2015.
[17] Po-Ling Loh and Martin Wainwright. High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity. The Annals of Statistics, 4033):1637-164,, 2012.
[18] Angelia Nedić, Alex Olshevsky, and Mike Rabbat. Network topology and communication- computation tradeoffs in decentralized optimization. Proceedings of the IEEE, 106:953 2018.
[19] Angelia Nedié, Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27:2597-2633. July 2016.
[20] Yuri Nesterov. Gradient methods for minimizing composite objective function. Math. Program. (Ser.B), 140:114-11111 125-161, 2013.
[21] Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
[22] Guannan Qu and Na Li. Accelerated distributed nesterov gradient descent. JEEE Transactions on Automatic Control, 65(6):2566-2581, 2019.
[23] Garvesh Raskutti, Martin Wainwright, and Bin Yu. Restricted eigenvalue properties for corre- lated gaussian designs. The Journal of Machine Learning Research, 11:2241-2255 2010.
[24] Alexander Rogozin, Vladislav Lukoshkin, Alexander Gasnikov, Dmitry Kovalev, and Egor Shulgin. Towards accelerated rates for distributed optimization over time-varying networks. In International Conference on Optimization and Applications (OPTIMA 2021), pages 258-272, 2.21.
11

---

[25] Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 3027-3036, 2017.
[26] Ying Sun, Marie Maros, Gesualdo Scutari, and Guang Cheng. High-dimensional inference over networks: Linear convergence and statistical guarantees. ArXiv preprint, arXiv:2201.08507 Jan 2022.
[27] Paul Tseng. On accelerated proximal gradient methods for convex concave optimization. manuscript, 2008.
[28] César A Uribe, Soomin Lec, Alexander Gasnikov, and Angelia Nedić. A dual approach for optimal algorithms in distributed optimization over networks. In 2020 Information Theory and Applications Workshop (ITA), pages 1-37, 2020.
[29] Martin Wainwright. High-dimensiona statistics: non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[30] Jinming Xu, Shanying Zhu, Yeng Chai Soh, and Lihua Xie. Convergence of asynchronous distributed gradient methods over stochastic networks. IEEE Trans. Automat. Contr., 63(2):434- 448, 2017.
[31] Tianbao Yang, Lijun Zhang, Rong Jin, Shenghuo Zhu, and Zhi-Hua Zhou. A simple homotopy proximal mapping algorithm for compressive sensing, Machine Learning, 108:1019-1056, 2019.
[32] Haishan Ye, Luo Luo, Ziang Zhou, and Tong Zhang. Multi-consensus decentralized accelerated gradient descent. arXiv preprint, urXiv:2005.00797, 2020.
[33] Haishan Ye, Ziang Zhou, Luo Luo, and Tong Zhang. Decentralized accelerated proximal gradient descent. In Proc. of the Thirty-fourth Conference on Neural Information Processing Systems (NeurIPS 2020), 2020.
Checklist
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? [Yes]
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 thcoretical results? [Yes] See Supplementary Material
3. 1f you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (cither in the supplemental material or URL)? [No]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(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, cloud provider)? [Yes]
4. If you using existing assets (c.g., code, data, models) or curating/releasing assets...
12

---

(a) If 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 as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshols, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "lc3dXuzpHeE", "reviewer": "Reviewer_2ihf", "summary": "The paper proposes an accelerated algorithm for distributed sparse regression in high dimensions. \nThey combine accelerated Nesterov’s proximal gradient with consensus and gradient tracking mechanisms.\nThey show it converges globally at a linear rate, achieving both optimal iteration complexity and communication complexity under the first-order oracle.", "questions": "Questions:\n\n1. The communication complexity is nearly optimal up to log factors. Is it possible to save the $\\log m$ dependence in (5)?  \n\n2. Can you upper bound the $\\Delta^2$ defined in (10) in terms of interest parameters like $m, N, d$？\n\n3. Theorem 2 requires $\\rho$ to be sufficiently small (see (16)). Though the author says we can run multiple rounds of communications to ensure (16) holds, some previous work doesn’t require it (e.g., [11]). Could I say this is because of the used accelerated technique, the resulting analysis needs to carefully bound residual errors?\n\n4. In the proof, the author makes use of a Lyapunov-like function to derive convergence. See (23). My question is why you use $\\hat{\\theta}$ in the definition of $(23)$ not $\\theta^*$?\n\n5. An extension question: the paper studies the case where all samples are generated according to $\\mathbb{P}$, while in some applications like Federated Learning (FL), the data points on different devices will conform to different distributions. Do you think your proposed method will still work in the data-heterogeneous setting? If not, how to overcome it?\n\n=============Post Rebuttal=============\n\nI have read the author's responses. All of my questions have been addressed. I keep my score.", "limitations": "See the questions.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: The problem setting is quite different from many previous results. The paper considers the high-dimension setting where the ambient dimension $d$ could be much larger than the number of samples $N$, failing many previous algorithms. Though the proposed solution is a combination of two popular techniques, the analysis is new. The analysis setting follows from [1] but has been modified to adapt to the distributed setting.\n\nQuality: The paper is technically sound with all theoretical claims supported. The experiment setting is clearly described.\n\nClarity: The paper is overall well-written and easy to follow. \n\nSignificance: The paper answers an important question in distributed learning and fills the blank of methods and theories in sparse distributed learning in high dimensions. It might be important.\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": "gOd0AqsWjfY", "reviewer": "Reviewer_ie1L", "summary": "This paper investigates distributed sparse regression in high-dimensions to speed up its computation, which combines Nesterov’s proximal gradient with consensus and gradient-tracking mechanisms. This method can estimate locally the gradient of the empirical loss while enforcing agreement on the local estimates. Based on the basic assumptions, the proposed algorithm globally converges at linear rate. The iteration complexity scales as \\sqrt{k} while the communications per iteration are at most \\logm/(1-\\rho). The experiments on real-world datasets and simulation studies verify the effectiveness of the proposed algorithms.", "questions": "This paper investigates acceleration for distributed sparse regression in high-dimensions. The paper can be improved from multiple points of view.\n1)Presentation. The logic of this paper is quite hard to follow. The presentation could be improved.\n2)Experiments. The experiment on more than one real-world data sets (only one in this paper). It would be better to do experiments with more real data.\n3)Complexity of algorithm. It would have been nice to see the complexity (time and space) analysis of the proposed algorithm in theoretical analysis and experimental results. ", "limitations": "This paper describes the scope of application of the proposed methods in detail, and does not involve negative social impact.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper has the following contributions: This paper proposes distributed algorithm for high-dimensional estimation to reduce the computational requirements, which decentralizes Nesterov’s accelerated proximal gradient via consensus dynamics and a gradient tracking mechanism to track locally the gradient of f. In theoretical analysis, under standard notion of restricted strong convexity and smoothness of the empirical loss, the iterates generated by the proposed scheme converge at linear rate to a limit point. The numerical experiments on simulated and real data show the effectiveness of the proposed algorithm. The computational complexity is also an important part in algorithms. In this paper, it will be better to analyze the complexity (time, space, communications) of the algorithm from theoretical analysis and experiments.\nThe research field of this paper is significant. The organization and presentation of this paper can be further improved. This paper is quite hard to follow. There is no conclusion section and organization section.", "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": "R0zQH6ERSME", "reviewer": "Reviewer_GRMi", "summary": "This manuscript studies the problem of sparse regression in a decentralized setting. Specifically, an accelerated algorithm is proposed, and its convergence and statistical properties are proven. Building upon recent advances in high-dimensional statistics, the authors take advance of the restricted strong convexity and restricted smoothness properties to develop their convergence analysis. Decomposable regularizers are also assumed. The authors show the performance of the proposed algorithm for the studied problems ", "questions": "For what graph classes does the bound on \\rho holds? More importantly, how does this bound scale with the number of agents? There is some dependency on m^2.5 which might imply that as the number of nodes increases, the graph needs to be more and more connected, which makes the proposed method impractical for relatively small graphs. \n\nCan this method go beyond linear regression? Let's say strongly convex and smooth graphs?\n", "limitations": "No societal impact limitations. ", "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- The manuscript clearly states the proposed problem and compares it with existing literature. It is clear that the proposed method extends the existing literature on the topic\n- The manuscript is well written and easy to follow. The authors make an effort to explain the details in sufficient detail. \n\nWeaknesses\n- While there is sufficient contribution, many of the core technical ideas build upon [1] and classical approaches to decentralized optimization.\n- \"almost\" strongly convex or smooth is strange. The way the authors handle inexactness and approximation terms like that causes confusion. For example, the authors mention trajectories (approximately) traveling in the \"good\" portion of the landscape. However, if the geometric properties of the function only hold in the appropriate subspaces, there is no reason to believe that they will hold in the approximate trajectories also. \n- The authors mention and work with l0 in the sparse regression setting and numerics but it looks like l1 is used instead. \n- The selected simulations do not clearly show the asymptotic behavior studied. ", "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": "IcDujwYnWOn", "reviewer": "Reviewer_UFEg", "summary": "The paper proposes a method for accelerating distributed high-dimensional regression under sparsity constraints. To do so the authors adapt Nesterov's proximal gradient method to the setting by combining it with a consensus step based on the connectivity of the graph. Experiments on synthetic data and a couple of public datasets demonstrates superiority validate the analytical claims.", "questions": "Please address the points under Weaknesses above (provide intuition for (13); explain what multiple rounds of communication/iteration means, how it would help, and what effect it would have on guarantees; provide a conclusion section)", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper clearly improves over prior work in theory and in practice.\n\n2. The application of Nesterov's method to this setting is clear and intuitive and overall the authors demonstrate its impact on multiple problem settings.\n\nWeaknesses:\n\n1. The explanation of the method is a bit dense and may not make complete sense to readers unfamiliar with all the technical prerequisites. Specifically, the logic behind equation (13) was not clear to me. It appears to rely on prior work ([7],[30],[19]) but as it is the key step in the algorithm, I would strongly recommend explaining it in a self-contained manner to make the picture clearer. \n\n2. The authors acknowledge that when the graph is not connected enough (for e.g. when condition (18) is not satisfied) then multiple rounds of communication/iteration may be needed to facilitate convergence. It is not clear what that exactly means. I am assuming it means multiple rounds of S.1 (consensus and gradient tracking). However I do not see clearly how that will overcome the lack of connectivity. This is another place where some intuition would be helpful. Also won't it affect the statistical and computational guarantees in (5) since now each iteration will have higher cost due to multiple rounds of communication?\n\n3. The paper ends abruptly with no conclusion section or a discussion of limitations/future work. ", "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