Decentralized Finite-Sum Optimization over Time-Varying Networks

Dear Reviewer,

Thank you for your time and effort while reviewing our paper. Below we answer the questions you have raised.

Incremental contribution and niche setting.

Please see the common answer to Reviewers.

Algorithms use multi-consensus and may perform badly in asynchronous setting.

Our algorithms are not designed for the asynchronous setting, but still GT-PAGE is optimal in its setup. Multi-step communication is a typical trick in decentralized optimization [1, 2]. In our understanding, this trick is mainly needed to eliminate the additional factor $\chi$ in the number of gradient calls, i.e. the trick is mostly theoretical. Anyway, using this technique leads to optimal complexities, which is effective, as you mentioned. Moreover, Acc-GT [5], which is an optimal method for time-varying networks, has a network dependence $\chi^{3/2}$ without multi-consensus. Finally, you mentioned that our methods are unlikely to extend well to asynchronous setup, but this fact cannot be quickly checked in our discussion.

DADAO

Thank you for pointing out the DADAO paper. We understand your comment that in the asynchronous setup DADAO is likely to lead to better solutions and may close the complexity gap. But please see that our paper already provides methods and closes the gap in the nonconvex setting. Therefore, we acknowledge that other approaches are possible but do not see it as a weakness of our work.

Questions

• Multi-consensus matrix.

Thank you for raising a question on multi-consensus. It was meant that each $W(k)$ is replaced by a product of $T$ consequent matrices $\tilde W(kT, T) = W(kT + (T - 1)) W(kT + (T - 2))\ldots W(kT)$ that corresponds to $T$ consequent communication rounds.

References

[1] Scaman, Kevin, et al. "Optimal algorithms for smooth and strongly convex distributed optimization in networks." international conference on machine learning. PMLR, 2017.

[2] Kovalev, Dmitry, et al. "Lower bounds and optimal algorithms for smooth and strongly convex decentralized optimization over time-varying networks." Advances in Neural Information Processing Systems 34 (2021): 22325-22335.

[3] URL: https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.LogisticRegression.html

[4] URL: https://github.com/scikit-learn/scikit-learn/blob/main/sklearn/linear_model/_sag.py#L87

[5] Li, Huan, and Zhouchen Lin. "Accelerated gradient tracking over time-varying graphs for decentralized optimization." Journal of Machine Learning Research 25.274 (2024): 1-52.

Dear Reviewer, thank you for your thorough review.

Weaknesses.

Paper organization.

The aim of the paper is to propose optimal algorithms for decentralized finite-sum optimization. In modern optimization theory [3], a problem class and an algorithm class are determined by introducing corresponding assumptions. In our paper, the problem class is decentralized finite-sum problems as defined in Section 2 and the method class is determined as first-order decentralized algorithms in Section 4.1. After that, the iteration complexity of the algorithm is compared to lower complexity bounds for the given problem class. If these two complexities coincide up to a constant term, the corresponding method is called optimal. Optimal methods for strongly convex and nonconvex scenarios use different techniques and have different theoretical analysis. In particular, Nesterov momentum allows to reach optimality in the strongly convex case but is useless in the nonconvex case. Therefore, a method optimal for one scenario cannot be used for the different scenario out-of-the-box even for usual (i.e. not decentralized) optimization.

In our work we used previously existing techniques to build new methods for each of the cases (strongly convex and nonconvex). That is why in the strongly convex case we used ADOM+ and in the nonconvex case we applied PAGE. As mentioned above, a method designed for the strongly convex scenario cannot be directly applied to the nonconvex one and vice versa. We managed to obtain an optimal algorithm for the nonconvex case, closing the previously existing gap in the literature. We also obtained an algorithm approaching optimality for the strongly convex case.

Assumption 2.5 on $\chi$.

It is possible to construct a matrix sequence $W(k)$ satisfying Assumption 2.5 under realistic assumptions on the time-varying network. The only restriction on the network is that the graph $\mathcal{G}^k$ is connected at each iteration. After that, we choose $W(k) = L(\mathcal{G}^k) / \lambda_{\max}(L(\mathcal{G}^k)$, where $L(\mathcal{G}^k) = D(\mathcal{G}^k) - A(\mathcal{G}^k)$ denotes the graph Laplacian matrix (see lines 196-198 of our paper; here D(\mathcal{G}^k) denoted the diagonal matrix containing the node degrees and A(\mathcal{G}^k) is the adjacency matrix). For each of the graphs $\mathcal{G}^k$, denote its Laplacian condition number $\chi_k = \frac{\lambda_{\max}(L(\mathcal{G}^k))}{\lambda_{\min}^+(L(\mathcal{G}^k))}$. Since the graph is connected, $\chi < +\infty$, and since $\lambda_{\max}(\mathcal{G}^k)\geq \lambda_{\min}^+(\mathcal{G}^k)$ we have $\chi_k\geq 1$. Moreover, since the set of vertices is fixed, there is a finite number of different graphs on these vertices. It is straightforward to check that $\chi = \max_k \chi_k$ satisfies Assumption 2.5 and $1\leq\chi < +\infty$.

Also note that for a fully-connected graph we have $\chi = 1$. One gossip iteration on a fully connected network corresponds to full averaging, which corresponds to Assumption 2.5. This explains why we do not impose that $\chi > 1$.

Our work does not stick to taking graph Laplacians: Assumption 2.5 allows to use any other matrices that satisfy the gossip requirements.

Dear Reviewer,

Thank you for your thorough review and comments. We are grateful that you pointed out the strengths of our paper.

Qualitative discussions.

Thank you for your suggestion. In the revised version of the paper, we will add a discussion to stress the paper contributions.

Smoothness parameters in Tables 1 and 2.

We will add clarifications and links to Assumptions in Section 2 in the annotations to Tables 1 and 2.

Motivating examples.

Typically in optimization literature one writes out the problem formulation right away. The examples are usually given in the numerical experiments section, like in our paper.

Error bars in numerical experiments.

Thank you for pointing this out. The error bars could be added to the plots, but this is not very typical in optimization papers.

Dear Reviewer,

Thank you for your thorough review and comments. We are grateful that you acknowledged the strengths of our work.

Contribution of the work.

The contributions of our paper are algorithms for decentralized finite-sum optimization over time-varying networks, optimal in the nonconvex case, as well as lower bounds. Previously methods were known for:

• decentralized non-stochastic optimization over time-varying networks (Kovalev et al., 2021a, Li and Lin, 2021);

• decentralized stochastic optimization without finite-sum structure over time-varying networks (Huang and Yuan, 2022);

• finite-sum optimization over static networks (Luo and Ye, 2022).

As you can see, the combination of time-varying graphs and finite-sum structure has not been previously studied. Our work closes the gap in this direction (in the nonconvex case).

Proofs identical to previous works. The main technical challenge lies in the proof of GT-PAGE. Please see the common answer to Reviewers for details. Time-varying topology is not challenging.

We respectfully disagree that time-varying topology does not seem substantially more challenging than that of fixed topology. Static and time-varying networks are two different classes of problems. A typical approach to decentralized problems is describing the constraint set $x_1 = \ldots = x_m$ by an affine constraint involving gossip matrix $W$, i.e. $Wx = 0$. The main obstacle of time-varying networks, even if they stay connected at each iteration, is that matrix $W_k$ changes between iterations, thus changing the description of the constraint set. This obstacle requires new approaches for decentralized problems. Working with time-varying graphs requires additional techniques such as gradient tracking [3,4] and error feedback [2,5]. In fact, after optimal methods for static graphs were obtained in [1] it took four years for the community to obtain optimal methods for time-varying graphs [2].

Assumptions on Smoothness.

Assumption 2.1 holds, for example, for logistic regression. Consider one summand of form $f_{ij}(x) = \log(1 + \exp(b_{ij}\langle a_{ij}, x\rangle))$, where $x$ is the problem weight vector, $a_{ij}$ denotes the feature vector and $b_{ij}\in\{-1, 1\}$ is the feature label. It can be checked (i.e. by computing the hessian) that $L_{ij} = \|\|a_{ij}\|\|^2 / 4$.

For the relation of smoothness constants, see line 177: $L\leq \overline{L}\leq nL$, where $n$ is the dimension. This can be seen by triangle inequality and by the fact that for convex smooth functions $g$ and $h$ we have $L(g)\leq L(g + h)$. Analogically it can be shown that $L\leq \hat L\leq \sqrt{n} L$. We will add the corresponding discussion to the revised version of the work.

Paper readability.

In the results section, we do describe previously known results. However, we believe that our explanations show the way of obtaining new results and think that this increases the readability of the paper. If we do not provide clarifications, our results might seem more challenging and unique, but this will be done at the cost of keeping the reader uninformed of the basics underlying the proposed algorithms. Summing up, we do not see a problem in explaining the existing results.

Thank you for pointing out the undefined symbols. We will correct this issue in the revised version of the paper.

Questions

• Why the two proposed algorithms require different function smoothness assumptions (c.f. Assumption 2.1, 2.2 and 2.3)?**

The methods are based on their corresponding counterparts in decentralized optimization. In the nonconvex case, we use algorithm PAGE [6] that requires the average smoothness assumption similar to Assumption 2.3. In the strongly convex case, we adopt Katyusha [7] that uses worst-case constants as in Assumptions 2.1 and 2.2. In other words, such choice of assumptions is caused by backward compatibility.

• The LibSVM dataset used for the experiments in this work seems not adequate; the reviewer would like to know if the algorithm could be applied to more complex datasets such as cifar-10/100 to further validate the effect of the algorithm.

Thank you for your suggestion. The choice of simple datasets and models enables to tune the step-sizes and other algorithm parameters according to theory.

• How is the time-varying topology being implemented in the experiments?

It is implemented using random geometric graphs [7].

• Why the reference Metelev et al. (2024) is not discussed in the main text? In fact, the time-varying topological sequences used in this work for obtaining lower bound adopt their strategy.

Thank you for noticing it. Indeed, this reference is used for the lower bounds and we mention it in line 1677 in the appendix. We will mention this paper in the main part of our work.