A Computation and Communication Efficient Method for Distributed Nonconvex Problems in the Partial Participation Setting

Summary

This research focuses on distributed learning problems and introduces a novel approach that incorporates three key elements: variance reduction, compression, and partial participation. It extends the DASHA method to address the partial participation scenario in both finite-sum and stochastic scenarios. In the context of partial participation, the proposed method achieves state-of-the-art communication complexity. Furthermore, in the scenario involving variance reduction and partial participation (without compression), it achieves optimal oracle complexity without relying on strict bounded gradient assumptions.

Strengths

The extension of DASHA to accommodate the partial participation setting is nontrivial addition. The analysis involving partial participation introduces additional complexity, but this work successfully establishes state-of-the-art bounds (although not that surprising).

Weaknesses

The presentation can be further improved in several ways to enhance clarity and readability. Firstly, instead of listing the assumptions and results for all three settings (full gradient, finite sum, stochastic) consecutively, it would be beneficial to present each setting individually with a particular focus on the stochastic setting, which is the main focus of this work. This approach would make it easier for the reader to understand and follow the discussion. Additionally, by adopting this approach, it would be possible to cover the results for both the nonconvex and PL condition cases in the main text. Furthermore, there are a few minor typos that need to be addressed. The set $\mathbb{R}^d$ is written as $\mathbb{R}$ in various places, specifically lines 35, 44, 51, and 59. Additionally, in line 164, "what" should be replaced with "which." Finally, in line 405, "dependeces" should be corrected to "dependencies." Another aspect that requires attention is the presentation of the algorithm. Currently, it lacks motivation and clarity. For instance, it is unclear how step (9) is derived to address the issue in steps (7) to (8), where it is mentioned that these updates are adapted to ensure the validity of the proof. Providing a clearer explanation or justification for step (9) would greatly improve the understanding of the algorithm and its purpose. Although the specific setup presented in this study has not been previously explored, and its analysis poses challenges, it can be viewed as a minor blend of previous setups, and the results can be considered as a slight extension of the work done in DASHA. Finally, the scope of the experiments conducted in this research is somewhat limited, as they do not encompass the more intriguing nonconvex neural network scenarios. Furthermore, there is a notable absence of numerical comparisons with other methods, such as FRECON or any other method within the full gradient setup. While I understand that space constraints may be a factor, with careful organization, it may be possible to allocate some room for such comparisons. One possible approach could involve dedicating the main body solely to the stochastic setting, while relegating the finite-sum case to the appendix. This would create additional space for the inclusion of numerical comparisons and provide a more comprehensive evaluation of the proposed approach.

Questions

After examining equations (7)-(8), it is mentioned that step (7) requires further updating if the same idea as in the full gradient step is utilized. The question arises as to why this is necessary. Would the method still function if only the participating nodes updated $h$ while the others retained the previous values? Essentially, is this a limitation of the analysis or would the method diverge under such circumstances? Another query pertains to practical applications that satisfy Assumption 6. Is there a specific real-world scenario that meets this criterion? Additionally, it is worth exploring whether achieving state-of-the-art bounds in the stochastic setting is possible without relying on Assumption 6.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Yes.

Summary

This paper introduces a novel method for distributed optimization and federated learning that integrates three critical components: variance reduction of stochastic gradients, partial participation, and compressed communication. The proposed method is shown to have optimal oracle complexity and leading-edge communication complexity in a setting of partial participation. A significant advantage of this method is that it effectively blends variance reduction and partial participation, thus providing optimal oracle complexity without the necessity of all nodes' participation or the bounded gradients assumption.

Strengths

One of the primary strengths of this paper is the integration of three crucial elements in distributed optimization and federated learning. By encompassing variance reduction of stochastic gradients, partial participation, and compressed communication into a single method, the authors have created a holistic approach that takes into account the multifaceted nature of distributed optimization. The authors demonstrate that their method achieves optimal oracle complexity, which is an important measure of the efficiency of an algorithm. This is a significant contribution, suggesting that the method has a high degree of efficiency in processing the data.

Weaknesses

Despite the significant theoretical contributions, this paper falls short in one crucial aspect, which restricts its overall impact and practical applicability. Lack of Empirical Validation: The major limitation of this paper is the absence of empirical experiments to substantiate the theoretical findings. While the theoretical results are compelling, they need to be complemented with practical validation to establish the practicality and effectiveness of the proposed method. The lack of experimental results makes it difficult to ascertain the method's performance in real-world scenarios, to gauge its scalability with varying data sizes and distributions, and to compare it with existing methods.

Questions

See weakness

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

None

Summary

This manuscript considers distributed non-convex optimization in the federated learning setting. It proposes an algorithm DASHA-PP that brings three important features of federated learning together: i) variance reduction, ii) compressed communication, and iii) partial participation. The authors derive the oracle and communication complexities of finding an $\epsilon$-stationary point of the smooth non-convex objective. It is the first method that includes those three important features. The algorithm presented in the paper is built upon DASHA, presented in [1]. In particular, in its form in [1], DASHA could work in the partial participation case only when the exact gradient oracle was available. In this manuscript, the authors extended the partial participation property of DASHA to the stochastic and finite-sum settings. [1] Tyurin, Alexander and Peter Richt'arik. “DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization.” ArXiv abs/2202.01268 (2022): n. pag.

Strengths

* I think the paper is very well-written. * The problem the manuscript considers is an important problem for the large-scale federated learning setting, where including all three features, i.e., partial participation/compressed communication/stochastic gradient, is inevitable.

Weaknesses

* The main technical contribution of the manuscript over [1] is the update rule given in Eq. (9). Similar update rule adjustments are frequently used in bandit optimization literature, cf [Section 2, 2] and [Section 6, 2]. * Besides the new update rule, it seems to me that the mathematical derivations in the manuscript are very similar to those in [1]. In that sense, I find the contribution of the manuscript is rather incremental. [1] Tyurin, Alexander and Peter Richt'arik. “DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization.” ArXiv abs/2202.01268 (2022): n. pag. [2] Cesa-Bianchi, Nicolò and Gábor Lugosi. “Prediction, learning, and games.” (2006).

Questions

NA

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

2 fair

Limitations

NA

Summary

The paper injects existing algorithm for distributed optimisation in the compressed and variance reduced setting with a mechanism for partial participation of nodes. Theoretical guarantees are given in the general non-convex setting, but also under PL-condition. The theoretical results are verified empirically in a classification problem.

Strengths

The paper considers the setting of partial participation, which is of importance in distributed optimisation. The setting of partial participation considered, is general enough to include at least two specific partial participation strategies. The theoretical results match the state of the art guarantees for variance reduced algorithms with limited communication up to scaling of $1/p_a$, where $p_a$ governs the probability of some node to participate in the gradient estimation during some iteration of the algorithm. I find this result elegant and I like that this scaling is pretty much observed in the experiments. The authors give some intuition on why passing from the full to the partial participation setting is non-trivial.

Weaknesses

The paper is very technical (if one wishes to follow proofs of the claims) and builds to an extensive amount of previous work, thus it is difficult to be appreciated by readers that do not belong to this specific research community. The appendix is about 90 (!) pages and a significant portion of them is essential to the proper understanding of this work, thus it's quite hard to review it in the context of neurips (the results are believable though). Since the topic is distributed computing with limited communication, I would expect a wider experimental analysis of the proposed algorithms in various tasks (also would be good some of the experiments to be in the main text).

Questions

I struggle a bit to understand the intuition behind Algorithms 3 and 4. For algorithm 3, I don't see immediately the connection with the PAGE algorithm and, for Algorithm 4, I don't see which algorithm tries to generalise. Could you elaborate? Is it possible to show that the chosen batch sizes of $B=O((L_{max}/\hat L)^2)$ and $O((L_{\sigma}/\hat L)^2)$ are at most $n$? Otherwise, there is a chance that such a batch size is not available. Minor: there are some issues with the writing, e.g.: "it is not trivial in each order one should apply the expectations" "We are not fighting for the full generality" " The main goal of our paper is to develop a method for the nonconvex distributed optimization" "From the beginning of federated learning era, the partial participation..." I would recommend to the authors to go through the text once more and improve the quality of writing.

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.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

2 fair

Limitations

The authors do not discuss limitations of their work, but I cannot see any profound ones. Perhaps the issue of batch sizes specified in my questions deserves a bit more attention.