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: 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.
strengths_and_weaknesses: Strengths:

1. The paper clearly improves over prior work in theory and in practice.

2. The application of Nesterov's method to this setting is clear and intuitive and overall the authors demonstrate its impact on multiple problem settings.

Weaknesses:

1. 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. 

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

3. The paper ends abruptly with no conclusion section or a discussion of limitations/future work. 
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
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 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 
strengths_and_weaknesses: Strengths
- 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
- The manuscript is well written and easy to follow. The authors make an effort to explain the details in sufficient detail. 

Weaknesses
- While there is sufficient contribution, many of the core technical ideas build upon [1] and classical approaches to decentralized optimization.
- "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. 
- The authors mention and work with l0 in the sparse regression setting and numerics but it looks like l1 is used instead. 
- The selected simulations do not clearly show the asymptotic behavior studied. 
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. 

Can this method go beyond linear regression? Let's say strongly convex and smooth graphs?

limitations: No societal impact limitations.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
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.
The 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.
questions: This paper investigates acceleration for distributed sparse regression in high-dimensions. The paper can be improved from multiple points of view.
1)Presentation. The logic of this paper is quite hard to follow. The presentation could be improved.
2)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.
3)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.
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: The paper proposes an accelerated algorithm for distributed sparse regression in high dimensions. 
They combine accelerated Nesterov’s proximal gradient with consensus and gradient tracking mechanisms.
They show it converges globally at a linear rate, achieving both optimal iteration complexity and communication complexity under the first-order oracle.
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.

Quality: The paper is technically sound with all theoretical claims supported. The experiment setting is clearly described.

Clarity: The paper is overall well-written and easy to follow. 

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

questions: Questions:

1. The communication complexity is nearly optimal up to log factors. Is it possible to save the $\log m$ dependence in (5)?  

2. Can you upper bound the $\Delta^2$ defined in (10) in terms of interest parameters like $m, N, d$？

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

4. 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^*$?

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

=============Post Rebuttal=============

I have read the author's responses. All of my questions have been addressed. I keep my score.
limitations: See the questions.
review_title: null

Meta-review: metareview: The paper provides novel guarantees for the well-studied distributed sparse regression problem. Their theoretical results improve upon the state of the art and extend to settings that many previous results could not handle. From a technical perspective, their result builds upon previous frameworks, but also requires a number new, novel ideas. The paper does have some downsides; as mentioned previously, some of their ideas do build quite strongly off of previous work, and the presentation of the paper is quite dense, as several reviewers noted. However, the consensus of the reviewers overall is that the technical contribution of the paper is above the bar for acceptance, and would be of interest to the distributed optimization community.
confidence: Less certain
Decision: Accept