Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this paper, the authors propose a distributed algorithm that converges linearly to the statistical precision for high-dimensional linear regression problems.
strengths_and_weaknesses: Strengths:

1. Overall this is a good paper. The investigated problem is important. The favorable dependency on d/N is novel.
2. I did not check the proofs, but the analysis seems sound.
3. The presentation is smooth, although this paper is mathematically extensive.

Weaknesses:

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?
2. Related to the previous comment, can the authors give some insights about why (a) helps us improve the dependency on d/N?
3. In the numerical experiments, the ratios d/N are not large. This contradicts with the motivation.

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?
2. Related to the previous comment, can the authors give some insights about why (a) helps us improve the dependency on d/N?
3. In the numerical experiments, the ratios d/N are not large. This contradicts with the motivation.

limitations: N/A.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.
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.  

Strengths:
- 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.
- The techniques used for proving the main result seems novel and the reviewer have checked most of the proofs which seems correct. 
- The paper developed statistical guarantees for several popular examples in M-estimation, which may be beneficial to the machine learning community

Weaknesses:
- 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.


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?

- 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?

- 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?

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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
1. This paper analyzes DGD for high-dimensional statistical estimation problems, which is a novel setting.
2. The analysis takes into account both the eigen gap of the weight matrix and the condition number.
3. This paper shows how the general analysis can be applied to sparse vector regression and matrix completion problems.
questions: 1. Line 22, should "undetermined" be "underdetermined"?
limitations: 1. Is it possible to extend the analysis to stochastic updates?
review_title: null

Meta-review: metareview: This paper studies the problem of high-dimensional linear regression in a decentralized setting. A distributed algorithm, incorporating so-called "double mixing" with decentralized gradient descent, is proposed that converges linearly to statistical precision in the regime where the problem dimension is much larger than the number of samples. The paper is well-written, clearly positions the contributions with respect to previous work, and provides significant results. The reviewers are also unanimous in recommending that the work be accepted, and recognizing the contribution as significant.

The reviewers found the post-rebuttal discussion to be very informative, and we recommend that the authors expand on the following points when preparing the camera ready manuscript:
* Adding some discussion of communication overhead associated with double mixing
* The tradeoff between double mixing (parameters and gradients) vs. additional rounds of communication to cope with poor conditioning
* Discussion of potential challenges extending the results to the stochastic gradient setting

confidence: Certain
Decision: Accept