Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities

Summary

This paper investigates distributed variational inequalities (VI) problems in the context of a server-workers architecture. It proposes a method that combines three major communication-saving techniques: i) compression, ii) local steps, and iii) data similarity across workers. For strongly monotone VI and strongly-convex strongly-concave saddle point problems (SPP), the proposed method outperforms competing methods in terms of communication complexity. Furthermore, it improves on previous results for non-monotone operators. It also extends the technique to a partial participation setting, in which one random device is selected at each iteration to send an uncompressed parameter while all other devices remain idle.

Strengths

This paper employs three communication-saving techniques (local methods, compression, and similarity) to achieve the best theoretical communication complexity for distributed methods solving strongly-monotone VI problems.

Weaknesses

- I believe that the writing and organization could be much improved. The paper is not well explained. There several typos and unclear statements. (line 172, the inner product in assumption 4.2 a semicolon is used instead of comma) (Missing comma in line 174 after i.e.) (initial value of $m^k$ is not specified in Alg 1) (line 10 in alg 1 $z^{k+1}$ instead of $z^k$) (definition of communication complexity is unclear and uncommon) (line 203 ‘we’ is missing an e) (having the main computation on server is not a contribution since there are methods with the same feature) The description of the algorithm is too long and not organized well. In page 6, lines 228—229 the author describe a reformulation that I find unclear where it came from. Moreover, in this part, variables $m^k,v^k$ are introduced where $m^k$ is a reference sequence that is only explained after several paragraphs. Similarly for the momentum term. The contribution is incremental in my opinion and builds on prior works [12] and [16]. The result is also a minor improvement over [51]. Under strong monotonicity the analysis is not that challenging and follows by using basic techniques from the literature. Moreover, assumption 4.3 is a strong assumption since data heterogeneity is common in practice. This is not worth a NeuRIPS paper on its own. The algorithm does not use full compression since it occasionally sends uncompressed vector in uplink (with small probability). Also it does not use compression in the downlink and it is unclear how to do that (even though the authors mention that their method can be generalized to two-sided compression).

Questions

The lower bound mentioned in Table 1 does not consider compression and, in my opinion, appears irrelevant. Could you please provide a lower bound that takes compression into account? This would be valuable in assessing the optimality of the proposed method. I understand that this aspect is currently designated for future research, but I strongly believe that it would be a significant contribution that enhances the paper Could it be said that permutation compressors are more accurately characterized as a sparsification technique rather than a compression method? In the context of this study, communication complexity is defined as the aggregate information transmitted. Specifically, in line 283, it is indicated that an average of $O(p+1/n)$ information is communicated. I would greatly appreciate a precise explanation of the concept of "information" within this context. Furthermore, I would appreciate more clarification regarding the division of communication rounds by $n$. Is this division influenced by compression techniques, such as sparsification, where $p$ corresponds to $1/n$? I would like to inquire about the validity of setting $H$ to 1 in line 296. In such a scenario, $\gamma$ would be equal to 0, resulting in an undefined bound. Could you please provide clarification regarding this aspect? Is the probability $p$ required to be: $0 < p < 1$? I would appreciate clarification regarding Theorem 5.7, as I find it confusing. How is it possible for $H$ to be of the order $O(K^2)$? Multiplying the communication rounds rate by $H$ seems to result in a computational bound that increases with $K$. Could you please provide further explanation on this matter?

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

1 poor

Contribution

2 fair

Limitations

No. For example, the studied assumptions are strict and not practical.

Summary

The paper presents a study of distributed algorithms for solving variational inequalities in a centralized distributed optimization setting. The authors propose three improvements: compression, data similarity, and local steps. Compression reduces the communication complexity by transmitting compressed versions of the data, data similarity reduces the variance among workers by sending batches of data that are similar across workers, and local steps reduce the communication rounds by allowing each worker to perform multiple iterations locally before communicating with the central server. The paper's main contribution is achieving the best known theoretical convergence compared to other deterministic algorithms for solving variational inequalities bot for monotone and strongly monotone VI.

Strengths

The paper's major strength lies in its successful implementation of three known techniques to improve communication complexity in distributed learning, combined in a way that maximizes their effectiveness. The authors pushed these techniques to their limits and studied the best theoretical combination, which is a significant contribution to the field. While the techniques themselves are not novel, the authors' implementation and optimization sets their work apart. Additionally, the paper provides a thorough analysis of the convergence and complexity of the proposed algorithm, which adds to its strength.

Weaknesses

However, a potential weakness of the paper is the centralized distributed optimization setting considered by the authors. The paper assumes the presence of a central server that synchronizes the work among the different workers, which may not always be feasible in real-life applications. Moreover, the author should address synchronization issues, such as a worker taking too long to send their result to the server. The paper could benefit from more discussion on the limitations and applicability of the proposed algorithm in different distributed settings.

Questions

The paper is clear and well-written, and the proposed algorithm's convergence and complexity are thoroughly analyzed. While I don't have any specific questions, I believe it would be helpful to know how the proposed algorithm performs in other distributed settings and to what extent the synchronization assumptions affect its performance, especially in the case of communication delays or worker failures. Providing insights on these aspects would enhance the applicability of the proposed algorithm and help readers understand its potential limitations.

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

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

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

In addition to the synchronization issue, I believe that a stochastic version of the algorithm would be more appropriate for handling large-scale distributed optimization problems, as mentioned by the authors. Moreover, the limitations are not sufficiently discussed by the authors.

Summary

This paper studies distributed variational inequalities. It combines three techniques – similarity, compression, and local updates – to reduce the total number of communication rounds. It establishes theoretical guarantees of communication complexity.

Strengths

1 It combines three techniques – similarity, compression, and local updates to reduce the total number of communication rounds for distributed variational inequalities. 2 It establishes tight communication complexity.

Weaknesses

The tight bound on communication complexity relies on the assumption of data similarity. However, this assumption is not always valid, such as in the case of highly heterogeneous data.

Questions

1 Which step of Algorithm 1 is the initialized $z_i^0$ used? 2 In line 186, it mentions "using only local information about operator $F_i$, changes the local value of variable $z$." In Algorithm 1, it seems that only the server updates $z$, and the device updates occur only in line 8 and line 13. There is no local $z_i$? 3 Line 676, it should be `` Proof of Theorem 5.7’’.

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

3 good

Contribution

3 good

Limitations

Yes.

Summary

The paper proposes two novel distributed algorithms, for solving variational inequalities and saddle point problems. These algorithms combine three techniques - local updates, compression, and similarity - to address the communication bottleneck in distributed optimization for these problems. Algorithm 1 uses Tseng's method as the outer iteration and Extra Gradient for the local updates. It incorporates a compression technique based on variance reduction and permutation compressors that take advantage of data similarity. Algorithm 2 is an extension that uses partial participation to reduce local complexity.

Strengths

The paper provides a thorough convergence analysis of the proposed algorithms under standard assumptions. The analysis derives competitive convergence rates and communication complexities that improve upon state-of-the-art methods. The analysis is also extended to the non-monotone case, demonstrating advantages over competitors. The theoretical work is a significant contribution. Comprehensive experiments on synthetic and real datasets confirm the benefits of the proposed algorithms over other baselines. The experiments show efficacy, especially as the degree of similarity between local functions increases. The results demonstrate both theoretical and practical significance.

Weaknesses

Some concerns arise for this paper: - The main concern I have for this paper is that, at each communication round only one client is calculating the gradients and updating the model. Hence, what is the number of communication required for convergence compared to other baselines? This has not been studied in the empirical section either. - Also, there are other baselines in saddlepoint problems in federated learning, which this paper is missing to compare with, such as [A,B] with communication efficiency approaches. - The algorithms and analysis are for the deterministic case. While the deterministic case is standard in the literature, the stochastic case may be more representative of machine learning applications. Analysis of the stochastic case would strengthen the work. [A]Mohri, Mehryar, Gary Sivek, and Ananda Theertha Suresh. "Agnostic federated learning." International Conference on Machine Learning. PMLR, 2019. [B]Deng, Yuyang, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. "Distributionally robust federated averaging." Advances in neural information processing systems 33 (2020): 15111-15122.

Questions

See above for questions.

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

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

They have discussed some of the limitations of their work in the paper, but it is more useful if we can have a detail explanation of them at the end.