Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this work a distributed (strongly)-convex-(strongly)-concave saddle point problem (SPP) is studied, over two different types of networks, i.e., master/worker, and meshed networks. In both cases lower bounds are derived for the number of communication rounds required  to reach an $\epsilon$ optimal solution. Differently than previous works on distributed SPP, the new analysis takes into account the similarity between the local functions. The lower communication complexity for reaching an $\epsilon$-optimal solution is shown to be in the order of $\Omega \left( \frac{\Delta \delta}{\mu} \log \left( \frac{1}{\epsilon}\right) \right)$ for a master/worker network and  $\Omega \left( \frac{ \delta}{\mu \sqrt{\rho}} \log \left( \frac{1}{\epsilon}\right) \right)$ for a meshed one; the parameter $\delta$ captures the function similarity while $\Delta, \rho$ depend on the properties of the network. Then, two algorithms are developed, one for each network type, that match these bounds, up to logarithmic factors. Finally, the proposed algorithms are evaluated on a robust linear regression problem over synthetic and real data.
main_review: Some of the positive aspects of this work are the following:

1. The authors derive novel communication complexity bounds for a setting (where the similarity between the local functions is leveraged) that has not been studied before in distributed SPPs. These new results generalize known lower bounds in the sense that the known ones offer more pessimistic estimates in the setting where function similarity is considered.
 
2. The algorithm class under which the lower bounds are derived is wide enough to capture many interesting distributed algorithms (e.g. using gradient or Newton updates)
    
3. Both types of networks, that is master/worker and meshed, are common and their study is motivated by applications. For instance, master/worker networks appear in federated learning applications.

The weak points of this work, as well as some other minor comments, are given below.

1. The utility of the derived lower bound is limited, since it is useful/interesting under the condition that $\frac{\delta}{\mu} << \frac{L}{\mu}$, where $\delta$ captures function similarity, $\mu$ is the strong convexity modulus, and $L$ is the smoothness parameter. 

2. A central assumption in this work is the $\delta$-similarity of the local functions. However, the specific similarity concept defined in assumption 2 is not sufficiently motivated.  For instance, why not consider similarity in terms of gradients (rather than Hessian)?  Overall, why it is important to study the problem under the assumption of function similarity?

3. The last two motivating examples in Section 2.1 do not seem to motivate the distributed SPP problem, but rather a general SPP problem. Since this is a work about distributed SPPs I think it would be fitting to discuss why these problems are interesting in the distributed setting. 

4. Comments about the experiments

    a. In the experiments Algorithm 1 is compared with the extragradient method, which is ‘‘applied directly on problem (10)’’. I presume this means that the extragradient method solves problem (10) as a non-distributed problem. Then, it is not clear how the communication rounds are defined for the extragradient algorithm, in figures 1 and 2. Also,  the authors need to explain why the comparison with a non-distributed algorithm is meaningful.

    b. There is no comparison with a distributed SPP algorithm. Thus, we cannot see if the proposed algorithm is indeed better in practice in terms of communication complexity compared with algorithms developed for the same setting. Why not perform a comparison with one of the distributed SPP methods mentioned in the ‘Introduction’ section?

    c. It is mentioned in the text that the experiments over meshed networks are located in the supplementary material. However, I cannot find these results. Are they missing?

   d. What is ‘sliding’ in the legend of figure 1? Also, the legends in figures 1 and 2 are different, although according to the description both experiments compare the same algorithms.

  e. It is mentioned that ‘We solve the problem over a master/workers topology; we consider networks with 10 and 15 workers’. However, in the figures 1 and 2 the numbers are 10 and 20, respectively.

5. In the four theorems of the main text the solution $z^{\ast}$ is not defined.
limitations_and_societal_impact: See the Main Review Section for some of this works limitations/weak points that remain to be addressed.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies distributed (both centralized and decentralized) saddle point problems. The focus is to relate the complexity to the similarity between objective function (determined by data) on different machines, thus the complexity will be reduced when the local objectives are similar to each other.
main_review: Merits: Developed distributed algorithms that take advantage of local function similarity, reducing communication complexity compared to existing works when \delta/mu << L/mu.

Concerns:

1. My first concern is the correctness of the lower bound. In the centralized case (master/workers network),  the lower bound of O(\delta/mu \log(1/\epsilon)) in this submission is different from the one in reference [2], i.e. O(\sqrt(\delta/mu)\log(1/\epsilon)), which means the lower bound in this submission is higher (tighter) than that one when \delta/\mu > 1. What causes this difference? Is the lower bound in [2] not tight? Since reference [2] already proposed an algorithm that can hit the lower bound for a special class of problems (quadratic problem) which can satisfy the assumptions in this submission, I doubt the correctness of the lower bound in this submission. The authors may want to highlight the setting difference and proof technique difference if the lower bound in this submission is indeed correct and tighter than reference [2].  

2. Theorem 1, 2 in the paper and theorem 5, 6 in the supplement material use extra assumptions f and f_m is 1-smooth and 1-Lipschitz continuous. These coefficients are critical (or even the whole point given the problems considered in this paper), thus I would highly suggest to keep them as parameters explicitly (e.g., L-smooth and G-Lipschitz), only then we can make sure the theorems are telling the right story. Also, please double check other theorems in case these assumptions are used implicitly.  

3. At each iteration, full gradients are required and a subproblem has be solved accurately enough. This makes the algorithm impractical, especially considering the fact that problem scales are usually quite big in distributed scenarios.

4. In Algorithm 1, F_1 and f_1 are used, are they typos? Otherwise, what is the insight to utilize F_1 and f_1 in that way?

5. Please relate the theorems in the supplement materials more clearly to the theorems in the paper, i.e., which is which.


limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors have studied solution methods for strongly-convex-strongly-concave saddle-point problems over two types of networks, namely, master/workers networks and meshed networks. For each type of network, the authors have established lower and upper complexity bounds that depend on the problem parameters, such as the degree of similarity of the local functions and the strongly convex/concave parameter. 


main_review: The paper is well written and also improves the state of the art in the field. The main weakness of the paper is that the experimental results are limited and Algorithm 3 requires global information of the network.  The detailed comments are as follows:

1. The parameter $\eta$ in Algorithm 3 depends on the second largest eigenvalue of the communication matrix $W$, i.e. $\lambda_{2}(W)$, which requires the global information of the network. Can you discuss this point and provide some distributed methods that can provide a good estimate of $\lambda_{2}(W)$?

2. In experimental results, it is preferred to study the effects of the graphs (ring, random, $k$-regular expander, etc.) on the convergence of the proposed algorithm.

3. The comparison with related work in experiments seems lacking. It is preferred to compare with the algorithms in [4] and [34]. It is also of interest to see the performance comparisons when the problem is ill-conditioned. 
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the problem of solving smooth strongly convex strongly concave saddle point problems over both centralized and decentralized networks. The main novelty is the consideration of the similarity between local functions in terms of second-order information. It provides better complexity lower bounds for both centralized and decentralized cases when the similarity of local functions is better than the smoothness of the objectives, as well as a near-optimal algorithm for the centralized case.
main_review: This work provides novel and solid complexity results for distributed SPPs under the local function similarity framework. Empirical studies are also discussed.

Major questions and concerns are: 
1. The paper only discusses the empirical loss (i.e., the robust regression) example that is related to the key Assumption 2 throughout the paper, which might limit its potential scope. It is beneficial to include more examples to discuss how strong it is in practice.
2. Sometimes x and y play unsymmetric roles in SPPs, while Assumption 2 treats them equally. Can the authors comment on the potential generalization of Assumption 2 to handle x, y differently to give an even tighter analysis?
3. At Line 176, is limiting $\alpha + \beta >0$ and $\theta + \psi >0$ necessary for obtaining the lower complexity bounds? Why?
4. Algorithm 1 does not explicitly use any similarly related quantities, it is just a tighter analysis under Assumption 2 to make it optimal? Authors should provide more insights about the analysis to explain how the algorithm takes advantage of similarity assumptions. Authors should also explain what example you construct to prove complexity lower bounds in the main text. 
5. The results for the decentralized case do not seem ideal as the complexity depends on $O(\log^2 \frac{1}{\epsilon})$. There are also no empirical results for this case.

Minor comments are: 
1. Title in pdf file mismatches with the submission
2. Line 97, n should be d
3. Line 111, L-smooth gradient should be either L-Lipschitz gradient or L-smooth
4. Line 143 and 144, notation n is reused and can cause confusion
5. Line 183 and 185, $\phi$ should be $\psi$
6. Line 3 in Alg 3, $t+1$ should be $t$
limitations_and_societal_impact: The authors addressed them.
review_title: null

Meta-review: In this work a distributed (strongly)-convex-(strongly)-concave saddle point problem (SPP) is studied. The authors provide communication lower bounds to reach an  $\epsilon$-optimal solution. Differently than previous works on distributed SPP, the result in this work takes into account the similarity between the local functions. Further, algorithms are developed which  match the proposed lower bounds. Finally, the proposed algorithms are evaluated on a robust linear regression problem over synthetic and real data.

Pros:

1) The authors derive communication complexity bounds for the SSP setting, which appears to generalize known lower bounds for the same class of saddle point problems, but without taking the similarity into consideration. 

2) The authors developed two algorithms, one for the case with central controller, and one for the case without central controller, for the considered problems. Further, the authors developed analysis for the proposed algorithms, and show that the lower bound derived can be in fact met. 

Cons:

1) The intuition behind algorithm design is not clear; nor is it clear whether a few design choices is necessary for not. For example, in Algorithm 1, why instead of performing a single gradient descent step, one needs to do step (iii) combined with step (i). Consider the simple case where there is no constraint, and f_1 = 0, then it seems that step (iii) does not provide any benefit in addition to step (i). As some reviewers have pointed out, it is difficult to understand a few design choices of the proposed algorithm. 

2) There is a lingering issue about how the lower bounds depends on how the fact that the authors' assumption about f and f_m being 1-smooth and 1-Lipschitz continuous (instead of having constants explicitly written down) will affect the proof.  This is an important question. The authors provided answers to it, but this requires the current proof to be changed. 

3) A question related to 2)  is that when constructing lower bound, it has assumed that the function is 1-Lipschitz continuous, while everywhere in the paper, such condition is not considered. Typically this will not pose any issue since the upper bound (for a wider class of problem without assuming Lipschitz-continuous function) matches the lower bound (constructed using a smaller class). However, since the dependency on the Lipschitz constant is not clear, and the key here is to understand whether the upper bound is tight in \delta, there could be an issue. Assume that the constructed problem is L-Lipschitz. It could be that the lower bound depends on \delta and L through $\frac{\delta}{L}$. In this case, the larger the L, the weaker the dependency on \delta. However, the upper bound does not quantify such a dependency, since there is no assumption on the Lipschitzness of the function. My point is that, it is important to explicitly write down the dependency on the Lipschitz constant, and the gradient Lipschitz constant, especially when the constructed problem requires additional assumption. 

3) As a minor comment, the algorithm itself is not particularly designed for problems with similarity. The similarity constant appears when providing the analysis, and in particular, when setting the accuracy for solving local problems. 

Overall, I think the paper is interesting and contains good results. However, there are still a few places,  that require some substantial revision.  I believe that this paper will be made much better if these issues are addressed. 


Decision: Accept (Poster)