Exploiting Similarity for Computation and Communication-Efficient Decentralized Optimization

We thank the reviewer for the positive feedback.

The paper would benefit from providing a proof sketch for key theoretical results, particularly for the convergence analysis.

Thank you for the suggestion. We promise to add the proof sketch in the camera-ready version.

The Accelerated-SPDO algorithm seems to be a straightforward extension of SPDO by incorporating the Monteiro and Svaiter acceleration method. However, are there any unique challenges or modifications required to apply this acceleration in the decentralized optimization setting?

The primary challenge of proposing our methods is that a straightforward combination of Hybrid Projection Proximal-point Method, multiple gossip averaging, and gradient tracking does not work (See the update rule in lines 262-274 and discussion in lines 275-295). To overcome this, we proposed a carefully designed modification in Algorithm 3 (see the update rule highlighted in blue). The same modification is also necessary for Accelerated SPDO, which is one of the primary novelties of our paper.

[...] the contribution bullets list the accelerated method first. To improve clarity and consistency, it would be better to align the sequence of the contribution bullets with the flow of the paper.

Thank you for the suggestion. We will fix the paper to clarify the contribution.

Can the proposed SPDO and Accelerated-SPDO algorithms be applicable to nonconvex optimization problems?

PDO, SPDO, and Accelerated-SPDO are designed specifically for convex optimization problems, and their applicability to non-convex optimization is not guaranteed. However, developing algorithms in the convex case is an important first step for studying algorithms in the more challenging non-convex case. We believe that our work provides valuable insights that could contribute to the development of future algorithms for non-convex optimization problems.

[...] Can the authors provide more intuition or insight into why SPDO achieves this improvement?

The main drawback of existing methods, including Decentralized SGD and Gradient Tracking, is that they cannot utilize the multiple local steps. In their local update, each node performs gradient descent, but fully minimizing the objective function is not desirable. For Decentralized SGD, [1] showed that we need to decrease the stepsize when we increase the number of local updates to not fully minimize the objective function. Compared with them, PDO, SPDO, and Accelerated PDO can solve the subproblem in their local update, which leads to lower communication complexities.

Reference

[1] Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., and Stich, S. A unified theory of decentralized SGD with changing topology and local updates. In ICML, 2020.

We thank the reviewer for examining our paper.

The methods are closely related to two existing works (Scutari & Sun, Li 2020) as discussed in the paper. However, the connection is not clear enough: [...]

Our paper and existing papers [1,2] use a slightly different notation, which might confuse the reviewer. We clarify it in the following.

Let define $y_i^{(r)} := h_i^{(r)} + \nabla f_i (x_i^{(r)})$. If we replace $h_i$ with $y_i$ in PDO, we obtain almost the same algorithm as Algorithm 1 shown in [1] as SONATA. The difference is that PDO solves the subproblem approximately, while SONATA needs to solve it exactly. Note that the original SONATA [2] has an additional hyperparameter $\alpha$ (See Algorithm 1 in [2]), but as shown in [1], $\alpha$ is not essential, and we can set $\alpha=1$. Thus, more precisely speaking, PDO contains the original SONATA with $\alpha=1$ as a special instance.

If the reviewer still has concerns, we would appreciate being informed. We will be happy to resolve them.

It is difficult for me to understand the difference between PDO and Stablized PDO. [...] If this is true, then the novelty and contribution of SPDO will be questionable.

We respectfully disagree with this reviewer's comment. Thanks to the update rule of $v$, Stabilized PDO can solve the subproblem more coarsely than PDO (see Eqs. (8) and (9)) and is computationally less expensive.

Specifically, the update rule of $v$ is not a simple gradient descent step. When $\mu=0$, the update rule of $v$ is $v_i^{(r)} - \frac{1}{\lambda} (\nabla f_i (x_i^{(r+1)}) + h_i^{(r)})$. The gradient is computed at $x$ instead of $v$, and it is not a simple gradient descent. It plays a crucial role in reducing computational complexity.

In Algorithm 1, the last term in the update of $h_i$ should be $\nabla f_i(x_i^{(r+1)})$ or $\nabla f_i(x_i^{(r)})$? [...]

Thank you for carefully checking our algorithm. This is not a typo, and Algorithm 1 is correct. We wonder if the reviewer might be confused since we use slightly different notations from [1] and [2]. See our response to your first comment. If the reviewer still has concerns, we would be glad to resolve them.

Typo: In Line 4 of Algorithm 2, it should be $a_j^{(m)}$ rather than $a_j^{(r)}$.

Thank you for pointing this out. We will fix it in the revised manuscript.

Regarding the theorem itself, the assumption seems to be very strong, and except for affine functions, it is difficult for me to find any other functions that satisfy Assumption 3.

We would respectfully disagree with this reviewer's comment. All of our theorems, Theorems 1-6, use only Assumptions 1, 2, and 4 and do not use Assumption 3.

As we explained in lines 120-126, the existing methods, SONATA and Accelerated SONATA, used Assumption 3, while our proposed methods and theorems successfully omit Assumption 3. Instead of using Assumption 3, we use Definition 1. As we mentioned in Remark 1, Definition 1 is not an assumption since all $L$-smooth functions satisfy Eq. (3) with $\delta \leq 2 L$. We can check this by the following inequalities:

$

\frac{1}{n} \sum_{i=1}^n | \nabla h_i(x) - \nabla h_i (y)|^2 \leq 2 | \nabla f (x) - \nabla f(y)|^2 + \frac{2}{n} \sum_{i=1}^n | \nabla f_i(x) - \nabla f_i (y)|^2 \leq 4 L^2 | x - y|^2

$

[...] I suggest them to also include primal-dual type methods for comparison.

Thank you for your suggestion. The papers the reviewer mentioned [A,B,C,D] do not utilize the similarity $\delta$. Thus, our proposed methods, PDO, Stabilized PDO, and Accelerated-PDO, can achieve better communication complexity by utilizing the similarity of local functions, especially when $\delta \ll L$. We will cite the papers the reviewer mentioned and add the discussion in the revised manuscript.

We believe these additions clarify the relationship between existing and our proposed methods, strengthening our paper. Therefore, we kindly ask the reviewer to reassess their score. If further concerns remain, we are happy to address them.

Reference

[1] Tian, Y., Scutari, G., Cao, T., and Gasnikov, A. Acceleration in distributed optimization under similarity. In AISTATS, 2022.

[2] Sun, Y., Scutari, G., and Daneshmand, A. Distributed optimization based on gradient tracking revisited: Enhancing convergence rate via surrogation. In SIAM Journal on Optimization, 2022.

We thank the reviewer for your constructive comments. We have addressed the concerns about missing ablation studies and included the results in our rebuttal below. We agree that these additional experiments significantly strengthen our paper. We kindly ask the reviewer to reconsider the evaluation and, if possible, adjust the score to reflect these changes.

The authors do not measure or estimate $\delta$ (the second-order similarity measure) directly on these data splits [...]

Thank you for your suggestion. We randomly sampled $100$ points from $\mathcal{N}(0, I / \sqrt{2d})$ and reported the approximation of $\delta$. The following table indicates that $\delta$ decreases as $\alpha$ increases. Thus, examining the performance of methods with various $\alpha$ is a proper way to evaluate the effect of $\delta$. We promise to add this table in the camera-ready version.

The authors do not show error bars or repeated runs to reveal the variance.

We promise to run our experiments several times and report their variance in the camera-ready version.

Real distributed environments might have node-level heterogeneity in CPU/GPU power.

We agree with the importance of considering the settings where each node has different computational resources. However, developing algorithms in this simple setting is an important first step for studying algorithms in the more challenging setting, as the reviewer mentioned. We believe that our work provides helpful insights that could contribute to the development of future algorithms for more realistic settings.

It would strengthen the experimental section if the authors demonstrated at least one experiment systematically varying M—for instance, letting $M$ take on $\{1, 5, 10, 20\}$ [...]

Thank you for the suggestion. In the following table, we fixed the number of multiple gossip averaging $M$ of SPDO and listed the gradient norm reached after $2000$ communication.

The hyperparameters, except for $M$, were tuned as in Figure 1(a) with $0.01$ L2 regularization. The table indicates that setting $M$ to $5$ is optimal. Comparing the results with $M=1, 2, 3, 5$, increasing the number of gossip averaging decreased the gradient norm. This implies that performing gossip averaging multiple times is important. Furthermore, increasing the number of gossip averaging too much increases the gradient norm since the total number of communication is fixed (See lines 422-425). These observations are consistent with Theorem 3.

We promise to add this table to the revised manuscript.

It would be more persuasive to include plots (or at least a table) that show how the final performance depends on each hyperparameter. [...]

According to the reviewer's suggestion, we examined the sensitivity of $\lambda$. The following table shows the gradient norm reached after running algorithms for $2000$ communication.

If we use a very large $\lambda$, the number of iterations of a local solver can decrease (see Lemma 31), while it requires more communication since the parameters are almost the same even after solving the subproblem, which ultimately requires a large number of communications. We can see consistent observations in the above table.

We will numerically analyze the sensitivity of other hyperparameters and promise to report the results in the revised manuscript.

When $\delta\approx L$, do the improvements over classical decentralized methods persist or vanish?

In the worst case, such as $\delta \approx L$, Stabilized PDO and Gradient Tracking require the same communication complexities. However, in many practical scenarios, $\delta$ is smaller than $L$ [2,3]. For instance, many existing papers, e.g., [1], considered that Dirichlet distribution with $\alpha=0.1$ was heterogeneous. Even in this setting, Figure 1 indicates that our proposed methods can achieve lower communication complexities than Gradient Tracking. We will clarify it in the revised manuscript.

Reference

[1] Lin et. al., Quasi-global momentum: Accelerating decentralized deep learning on heterogeneous data. In ICML 2021

[2] Chayti et. al., Optimization with Access to Auxiliary Information, In TMLR 2024

[3] Kovalev et. al., Optimal gradient sliding and its application to optimal distributed optimization under similarity. In NeurIPS 2022.

We thank the reviewer for the positive feedback and careful review.

The main idea seems be to directly combine the inexact gradient sliding (Kovalev et al., 2022) with Multiple Gossip and gradient tracking. Can you highlight the main technical novelty in the algorithm and analysis?

We would like to emphasize that a straightforward combination of gradient sliding, multiple gossip averaging, and gradient tracking does not work. To overcome this, we proposed a carefully designed modification in Algorithm 3 (see the update rule highlighted in blue).

Specifically, straightforwardly combining them yields the update rules shown in lines 263-274. However, as we described in lines 275-289, this simple combination does not work. Our paper is the first to analyze this challenge and develop a principled modification that ensures low communication and computational complexities.

The domains of $x$ and $v$ in lines 4-5 of Algorithm 3 and lines 12-13 in Algorithm 4 should be presented.

The domains of $x$ and $v$ are $\mathbb{R}^d$. We will clarify them in the camera-ready version.

The experimental results only includes the comparison on the communication cost. I think the comparison on the computational cost is also required.

The comparison of the computational costs is shown in the second and fourth figures in Figure 1. The first and third figures from the left show the communication complexities. We will clarify it in the revised manuscript.

Can we avoid the term $1/\sqrt{1-\rho}$ in the computational cost?

We deeply appreciate the reviewer for checking it carefully. There are typos in Table 1; the computational costs for methods other than Gradient Tracking do not depend on $\rho$ since $\tfrac{1}{\sqrt{1 - \rho}}$ in communication complexity comes from the multiple gossip averaging, which does not affect the total computational complexity. The statements of our theorems in the paper are correct, and this correction does not affect the discussion in the entire paper. We apologize for your confusion. We promise to replace Table 1 with the following version in the revised manuscript.

Can we provide the lower bound the verify the optimality of proposed algorithms?

Thank you for the comments. We will add the following discussion in the camera-ready version.

Communication Complexity: [1] showed that lower bound requires at least

$

\Omega \left( \sqrt{\frac{\delta}{\mu (1 - \rho)}} \log \left( \frac{\mu \| x^\star \|^2}{\epsilon} \right) \right)

$

communication to achieve $f (x) - f (x^\star) \leq \epsilon$. Our Accelerated SPDO can achieve the following communication complexity:

$

\tilde{\mathcal{O}} \left( \sqrt{\frac{1 + \frac{\delta}{\mu}}{1 - \rho}} \log \left( 1 + \sqrt{\frac{\min \\{ \mu, \delta\\} \|x^{(0)} - x^\star \|^2}{\epsilon}} \right) \right)

$

Thus, when $\delta \geq \mu$, Accelerated SPDO is optimal up to the logarithmic factor.

Computational Complexity: For non-distributed cases, any first-order algorithms requires at least

$

\Omega \left( \sqrt{\frac{L}{\mu}} \log \left(\frac{\mu \| x^{(0)} - x^\star \|^2}{\epsilon} \right) \right)

$

gradient-oracles to satisfy $f(x) - f^\star \leq \epsilon$ (See Theorem 2.1.13 in [2]). Accelerated SPDO can achieve the following computational complexity:

$

\tilde{\mathcal{O}} \left( \sqrt{\frac{L}{\mu}} \log \left( 1 + \sqrt{\frac{\min \\{ \mu, \delta\\} \|x^{(0)} - x^\star \|^2}{\epsilon}} \right) \right)

$

Thus, the computational complexity of Accelerated SPDO is optimal up to logarithmic factors.

Reference

[1] Tian, Y., Scutari, G., Cao, T., and Gasnikov, A. Acceleration in distributed optimization under similarity. In AISTATS, 2022.

[2] Nesterov, Y. Lectures on convex optimization. In Springer, 2018.