Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis

Summary

**Summary** The paper studies finite-sum minimization ($\min_{x} f(x):= \frac{1}{n} \sum_{i= 1}^n f_i(x)$) in the distributed setting with a central node and $n-1$ non-central (client) nodes. The setup and the paper's assumptions are as follows. 1. Each function $f_i$ is held in the $i$-th client node, and the first node is designated the central node. The machines on the non-central nodes can communicate function values and gradients with each other as well as with the central node. 2. The different $f_i$'s are assumed to be related to each other via the notion of "second-order similarity", which essentially means that the Hessians of $f_i$ and $f$ evaluated at the same point do not differ from each other by too much in the operator norm. A benefit of this assumption is that different clients do not need to all send their Hessian information. 3. The $f_i$'s are all convex, $f$ is $\mu$-strongly convex, and the $f_i$'s all satisfy $\delta$-average-second-order-similarity as described in 2. The paper's results are three-fold: 1. A non-accelerated algorithm called SVRS, which attains a communication cost of $\widetilde{O}(n + \sqrt{n} \delta/\mu)$. This result improves upon the previous best result of Khaled and Jin when $\delta \geq \sqrt{n} \mu$. 2. An accelerated algorithm called AccSVRS, which attains a communication cost of $O((n+ n^{3/4} \sqrt{\delta/\mu})\log|\epsilon|)$, which improves upon the previous best accelerated rate by Khaled and Jin by a factor of $\log(L/\mu)$. Therefore, this new rate is "smoothness-free". 3. Lower bounds for 2. The paper's technique is based, broadly, on the use of Bregman-SVRG: instead of calculating exactly in each iteration, we calculate the approximate entities every time and periodically offset the error by exact calculations; additionally, through the use of a Bregman divergence term, the update rule ensures that the next iterate is not too far from the current one in some chosen distance metric.

Strengths

**Strengths** I think the paper scores highly on the story-telling aspect: it reads quite well! I also think the paper studies an important problem (faster communication complexity for distributed optimization).

Weaknesses

In results: 1. Line 64: The paper's result from SVRS beats that of SVRP by Khaled and Jin when $\delta \geq \sqrt{n} \mu$. As of now it's not clear to me what the scope of this assumption is: are there many cases where this inequality holds? It appears to me that Lines 124 and 198 allude to this but it's not entirely clear to me. Can the authors please elaborate? 2. Line 68 - 70: The paper's result with acceleration shaves a log factor from the previous best result as well as removes a component-wise strong convexity assumption from the previous best result. It would be nice to see some intuition for why the removal of log factor here is important and why the component-wise strong convexity is that much stronger than total strong convexity. In the writing: 1. In lines 14 - 17, there are no references for these stated applications. It would be much more convincing to have citations for each of the stated applications. 2. The problem parameter $\mu$ should be introduced separately, rather than as part of the related work in lines 40 - 48, since it's an important parameter that comes up repeatedly. 3. The inclusion of Lemma $3.1$ in the main body does not serve (in my opinion) much purpose because it's mathematically quite dense to parse Equation $(10)$. Theorem $3.2$ is ok since it clearly gives the claimed rate. Instead of Lemma $3.1$, I'd have preferred to have a proof sketch for Theorem $3.2$.

Questions

**Questions** 1. In Algorithm 1, should line 4 be $g_t = \nabla f_{i_t} (w_t) - \nabla f(w_t)$ and should there be an update rule for $w_t$ somewhere? (That's what Line 176 seems to suggest.) If not, it would be great to have intuition for why the same $w_0$ is used through the entire algorithm. 2. Please see the Weaknesses section above for more questions.

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.

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

N/A

Summary

The authors consider distributed minimization problems under data similarity (hessian similarity). The authors consider stochastic methods that reduce communication complexity via device sampling. In particular, from the stochastic point of view, the variance reduction techniques: SVRG and Katyusha, are taken. The sliding (stochastic preconditioning/mirror descent with unusual Bregman divergence) technique is used for dealing with similarity. The authors obtain record results in communication complexity (the previous ones were beaten by the logarithmic factor). To complete the picture, the authors provide lower bounds that give the optimality of their upper bounds. Synthetic experiments are also given.

Strengths

1) Direct acceleration (without envelops) is an interesting and important result. In theory it removes the extra logarithmic factor, and in practice it works better. 2) The lower bounds complete the picture.

Weaknesses

1) I think the literature review is not complete. In particular I find two papers also about the hessian similarity, which also use the variance reduction technique and obtain such non-accelerated results as the authors have. A detailed comparison in approaches and results is needed. Beznosikov, A., & Gasnikov, A. (2023). Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities. arXiv preprint arXiv:2302.07615. Beznosikov, A., & Gasnikov, A. (2022, September). Compression and data similarity: Combination of two techniques for communication-efficient solving of distributed variational inequalities. In International Conference on Optimization and Applications (pp. 151-162). Cham: Springer Nature Switzerland. 2) The lower bounds are a good supplement to the upper bounds, but they are to be expected. The idea of getting them is also known. Unfortunately, here the authors don not also give a complete summary of the literature: the problem with a matrix A is classical (the authors note it), but the partition of the problem into columns is also classical - see the papers: Zhang, M., Shu, Y., & He, K. (2020). Tight Lower Complexity Bounds for Strongly Convex Finite-Sum Optimization. arXiv preprint arXiv:2010.08766. Han, Y., Xie, G., & Zhang, Z. (2021). Lower complexity bounds of finite-sum optimization problems: The results and construction. arXiv preprint arXiv:2103.08280. Kovalev, D., Beznosikov, A., Sadiev, A., Persiianov, M., Richtárik, P., & Gasnikov, A. (2022). Optimal algorithms for decentralized stochastic variational inequalities. Advances in Neural Information Processing Systems, 35, 31073-31088. 3) Experiments for me are not the most important thing in this paper, which is primarily theoretical. But I would still like to see real datasets (3 for symmetry with synthetic data). I would also advise authors to change not \mu, but to change \delta in synthetic experiments, this way the effect of similarity will be noticeable. Summary: For me, this is a borderline paper. For now I put a (weak) rejection, but I hope the authors will take part in discussion and make the changes I asked for.

Questions

-

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

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

The paper is theoretical, therefore there is no need to discuss the social negative impact.

Summary

The paper presents a novel algorithm for distributed optimization, named Accelerated Stochastic Variance-Reduced Sliding (ASVRS). The authors focus on the problem of minimizing the average of a large number of smooth and strongly convex functions, a common scenario in machine learning and data analysis. The proposed ASVRS algorithm combines the techniques of gradient-sliding and variance reduction, aiming to improve the convergence rate and reduce the communication cost in distributed settings.

Strengths

The ASVRS algorithm is a novel contribution that combines gradient-sliding and variance reduction techniques in a unique way. This combination appears to be original and innovative. The authors provide detailed proofs for the convergence rate and communication complexity of the ASVRS algorithm, demonstrating its theoretical advantages over existing methods. I didn't check the details but the result seems reasonable.

Weaknesses

The theoretical analysis relies on several assumptions, such as the strong convexity of the functions. This makes the application of the work rather limited. It would be helpful to discuss the implications of these assumptions and how the algorithm's performance might be affected if they are not met.

Questions

How sensitive is the ASVRS algorithm to its parameters? Could you provide some guidance on how to set the parameters in practice.

Rating

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

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The limitation has been adequately addressed.

Summary

The paper considers distributed strongly convex optimization problems in the setting where the communication between nodes is bottleneck. The authors propose new methods, SVRS and AccSVRS, that guarantee new communication complexities. Also, they proved the lower bound that ensures the optimality of the AccSVRS method.

Strengths

I think that the paper is strong. The authors provide new theoretical guarantees in the considered setting. They improve the previous methods. I haven't checked the proofs in detail and I can miss some essential parts, but the theory sounds to me.

Weaknesses

It is well known that the (Loopless-)Katyusha method converges after $n + \sqrt{n \frac{L}{\mu}}$ iterations. By applying Katyusha to the authors' problem, we can get the communication complexity $n + \sqrt{n \frac{L}{\mu}},$ since Katyusha requires only one gradient in each iteration. In the regime when $\delta = L$ the Katyusha method has better communication complexity than $n + n^{3/4} \sqrt{\frac{L}{\mu}}.$ Why doesn't it contradict the lower bound (Theorem G.7 and Theorem 4.4)? Does it mean that your method is only better in the regimes when $\delta \ll L$? Minor comments: The paper's setup can be slightly confusing. Many other papers (e.g., \[1,2\]) assume that the nodes can do calculations and send vectors *in parallel,* meaning that they count each round as *one* communication, *one round = one communication*. In comparison, this paper assumes that *one round = $n$ communications* in the full participation regime. Can the authors write a small text *in the paper* explaining the difference between the setups? It seems that we have at least two different setups that both have the right to life. Typos: Eq. (18): $\nabla$ is missed. \[1\]: https://arxiv.org/abs/2202.09357 \[2\]: https://arxiv.org/abs/2304.04169

Questions

-

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and 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

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

-

Summary

This work considers finite-sum (distributed) optimization problems in the strongly convex and second-order similar regime. The authors proposed SVRS and its acceleration, AccSVRS, to solve the problem and provided the corresponding communication and computation complexities, which outperform existing works in several perspectives. The authors further characterized the lower bound for solving such problems, which validates the near optimality of the proposed AccSVRS algorithm.

Strengths

1. The study is comprehensive in general, covering both upper and lower bounds 2. Proposed algorithm achieves near-optimal communication/computation complexity. 3. The design of the algorithm, which incorporates PPA, VR, gradient sliding and Katyusha, is interesting. 4. The paper is well-written, and the flow is clear.

Weaknesses

1. The design of the AccSVRS, as the core algorithm achieving near optimality, can be further elaborated. For now, I do not have a clear understanding on Steps 5 and 6 in AccSVRS. Some discussions similar to Section 3.1 connecting Katyusha X paper will be appreciated. 2. Some more questions below.

Questions

1. Line 232, you mentioned you recovered the optimal complexity of the average smooth setting. While with the additional AveSS setting, I may expect the complexity possibly can be (strictly) better than the classical $L$-smooth $\mu$-strongly convex case (assuming all components are $L$-smooth here for convenience). In your proof of Appendix E, you mentioned the obtained complexity is only smaller than that of the average smooth setting (Line 590), but should it be equivalence (rather than smaller only) here to be verified? 2. With the current result in Section 3.3, can we argue that possibly second-order similarity does not help in the gradient complexity of the classical case? 3. Line 591 in Appendix E (or Line 234), why do you drop the $O(n^{3/4}(L/\mu)^{1/4})$ term? Compared to the last $O(\sqrt{nL/\mu})$ term, is there a possibility that the $n^{3/4}$ term will dominate? Do I miss anything here?

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

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

N/A

Final decision

Thank you! I quickly went through the comment. It seems that my questions have been addressed. Thank you for the explanation. I will slightly increase the score. Good luck with other rebuttals.