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 author studied a convex optimization problem, where the objective function can be decomposed into a smooth convex function and a possible nonconvex function. There are three major contributions: 1. the author proposed gradient sliding algorithm which achieves optimal complexity of gradient calls of each component functions; 2. the author proved the algorithm achieves optimal communication complexity under $\delta$-similarity; 3. the author applied the proposed method to a class of distributed saddle-point optimization problem. 
strengths_and_weaknesses: The paper is a good one with strong theoretical results and clear presentation.
questions: I am wondering what is the author's thoughts on the comparison between the proposed methods and the so-called local SGD studied in [1],
and any thoughts on the proposed methods for deep learning.

[1] Stich, Sebastian U. "Local SGD converges fast and communicates little." arXiv preprint arXiv:1805.09767 (2018). 
limitations: the authors have adequately addressed the limitations
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: Paper considers convex minimization of sum of smooth functions r(x) = p(x) + q(x) with Lipschtiz-smoothness constants Lp and Lq (Lp < Lq). Here they assume that p can be non-convex and q is convex. This paper provides a gradient sliding algorithm which only uses O(\sqrt{Lp}) gradients of p and O(\sqrt{Lq}) gradients of q. This kind of separation is useful when first order oracle of p is much more costlier than that of q. Paper provides these results when r is convex, or strongly convex.

This algorithm is then used to obtain optimal communication and gradient complexities for distribution finite sum optimization under similarity Hessian assumption. Paper also extends the sliding scheme to the setting of solving a monotonic variation inequality of sum of two Lipschitz continuous operators.
strengths_and_weaknesses: Strengths
- Gradient sliding results seems novel
- Results seem to pass quick checking of logic
- Paper provides results for two different settings and applies them to distributed optimization to obtain optimal guarantees
- Experiments section

Weakness
- Paper does not explain the intuition behind the algorithm. The exposition should also make it clear how they are related to known ideas. These help the community assimilate the results and build on top of them to produce future scientific output.
- No proper examples are provided for the settings studied in the paper.
- Not enough experiment details are provided and there seems to be missing baselines
- It is not clear whether the missing entries in the “Local gradient complexity” column of the table actually means these oracles are hard to solve. The best complexity for solving the oracle sub-problems should be mentioned here.

After rebuttal
- Authors addressed almost all of my concerns. Assuming authors will take action on my suggestions, including the new ones about the intuition and rewording the claim, I am increasing my score.
questions: 1. Why does the algorithm work? Why is this called “accelerated extragradient”
2. What are examples where r is mu-strongly convex, p is nonconvex and q is convex?  It looks like the one in simulations doesn’t satisfy this. If there are no such examples, can step 5 of algorithm be solved using accelerated smooth strongly convex optimization?
3. Function similarity assumption and the assumption 6 different (notice j in former). What is the relation between the two and why does the paper use a different assumption?
4. Acc SONATA [44], what is the complexity to solve proximal steps? Is it O(\sqrt{L_i/\mu} \log(1/eps)) because of strong convexity? If yes, this should be noted in the table as well.

5. In experiments, what are the r, p and q, and Lp, Lq and \mu?
6. In experimental section what does lambda=0,1 mean? What was used for the experiments and why were these choices made?
7. Please provide comparison to AccSONATA which has the SOTA communication complexity. The sub problems should be easy to compute if they are convex or strongly-convex.	
8. In Synthetic minimization dataset how much noise was added?

Minor comments

9. Lq >= Lp >= mu assumption should be more prominant
10. “Weakly convex” function also has another meaning of mu < 0. May be use “convex”?

limitations: No limitations are provided. Authors may discuss the challenges of extending results to to nonconvex settings
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper combines extra gradient, gradient sliding, and acceleration to propose an accelerated extragradient sliding methods for convex composite optimization that achieves improved gradient complexity. When applied to distributed optimization problem under agents' function similarity, the method achieves lower bounds on communication and gradient complexities. The method is further extended to variational inequality setting.
strengths_and_weaknesses: ## Strength

1. The paper combines extra gradient, gradient sliding, and acceleration that achieves $O(\sqrt{L_p/\mu})$ and $O(\sqrt{L_q/\mu})$ gradient call for $\nabla p$ and $\nabla q$ respectively, improving over the condition number for minimization problem. It well suits the unbalanced problem.
2. The method is further extends to obtain optimal gradient sliding for VIs.
3. When applied to distribution optimization and distributed minimax optimization under similarity assumption, the proposed methods achieve the lower bounds on both communication and gradient complexities.


## Weakness

1. Presentation needs serious improvements. See questions below.

2. The numerical results are relatively less informative. On real datasets, the proposed method only achieves comparable performance with the state-of-the-art method. 


questions: 1. Line 23, "a network of $m$ agents." For Equation (2), is it $1/m$ or $1/n$? See also Line 47, line 45 line 56.

2. Line 44, why one would use the second order information for similarity notation? What would happen if one uses first/zeroth-order information for similarity notation. How to verify that function similarity holds.

3. If there is similarity, does it reduce back to the stochastic setting? For example, if using first-order similarity notation, one may rewrite the problem as a stochastic optimization with a discrete distribution and bounded variance of the first-order information. 

4. For second-order similarity, how to evaluate it numerically?

5. The proposed method combines acceleration, extragradient, and gradient sliding. It is unclear which component improves the complexity bound, comparing to the existing literature. Please specify with a more detailed comparison with existing literature on the methodology. 

## Minor Comments:
1. Line 6, 7, missing bracket. 
2. Line 23, is it $m$ or $n$?
3. Line 29, there are $m$ agents or $m$ samples? 
4. Line 30, what does it mean by mismatch between parameter and sample?
5. Assumption 1 with $\mu=0$ is normally treated as convexity while $\mu<0$ is weakly convex in the literature. It would be nice to stay consistent. 
6. Example 2 Line 201, is it $\min_z$ or $\max_z$ as it is a saddle point problem. 
7. Line 114,  120, missing bracket
limitations: N.A.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper considers a gradient sliding approach for distributed optimization. The idea is that by interleaving the computations between past and future iterates, the distributed optimization system is more robust to noise and convergence can be accelerated.
strengths_and_weaknesses: Strengths
 - The paper does a pretty thorough related works review, and seems to be integrating sophisticated methods.

Weaknesses
 - It is a bit unwieldy to have 2 theorem boxes, which are referred to in the paper, in the appendix. In general I have a hard time understanding why each one is contributing something different, and something like this should be discussed more clearly in the main text.

 - The second set of numerical results are extremely inconclusive, and does not show consistent advantage at all. 
questions: It is possible that all the rest of the issues are misunderstandings, and if we can clarify them (and discuss how they can be clarified in the paper), I can increase my score.

Broad strokes questions

 - Why is it called extragradient method? Extragradient usually implies taking two gradient calls and then using the second one, in order to get a "midpoint discretization" scheme and improve performance, but at a 2x overhead. None of the algorithms seem to be doing this.

 - It seems like the method mainly focuses on an outer loop / inner loop approach, where the outer loop achieves linear convergence and the inner loop borrows from other SOTA methods to get good guarantees. This seems appropriate for optimal rates, but I don't see the clear benefit to *distributed* optimization. Is this a noise variance controlling technique, or straggler mitigation technique? I guess what I'm asking is, if A = gradient sliding and B = optimal method, is this paper just A + B (arbitrary mix and match), or are there deeper ramifications for using this combination?

 - There is the big question also of what is hidden in the constants. For example, the scale of delta may be big in practice. More to the point, if delta is small in practice, to the point where the rates are tight, wouldn't the competitor methods work pretty well? A more extensive numerical experiments comparison would show if this is really a practical method.

 - What's the big idea behind using the prox operations in step 5 of alg 1? Is it just to achieve optimal rates? I ask because it seems prox operations are used, but aren't really discussed in terms of key benefits and numerical insights here, and the standard is usually just gradient descent. 

Technical questions
 - In (8), I see a dependency of error on 1/T^2. However, in (9), T is a constant. This doesn't seem logical, since later inner iterations should require higher precision (and thus larger T) than initial ones. This of course affects the main final results (Thm 5)

 - Theorems 4 and 10 seem to better match the inner / outer loop issues, but they are kind of terrible rates then. How do they compare against competitors?

limitations: n/a
review_title: null

Meta-review: metareview: The paper extends gradient sliding to the situation where both functions are smooth and the sum is strongly convex. The resulting algorithm is then applied to distributed optimization settings and similarity assumptions, where it jointly achieves optimal gradient evaluations and communication complexities, improving on prior complexity bounds by logarithmic factors.

Initially, the reviewers were unclear about the motivation and construction of the algorithm, as well as the significance of the theoretical results. However, through extensive discussion, most of the issues were clarified to the satisfaction of the reviewers. Consequently, I recommend acceptance of the paper and urge the reviewers to carefully incorporate all the clarifications in their rebuttal into the camera ready paper.

In addition, please provide an accurate answer (either yes or no) to question 3a in the reproducibility checklist.
confidence: Less certain
Decision: Accept