Stabilized Proximal-Point Methods for Federated Optimization

Summary

The authors of the paper extend the DANE algorithm to the stabilized-DANE (S-DANE) algorithm based on intuition from stabilized proximal point method. They also enhance the proposed S-DANE method with Monterio-Svaiter acceleration. The algorithms proposed by the authors allow for partial participation and various local solvers to some extent. Convergence analysis and experiments are provided.

Strengths

1. The presentation of the paper is clear, logical and easy to follow. 2. The paper proposes two novel algorithms S-DANE and its accelerated version and provides convergence analysis of them, experiments are also provided to validate the claim of the paper. 3. The proposed algorithms allow for partial participation and various local solvers in some sense.

Weaknesses

1. The partial client participation case of S-DANE and accelerated S-DANE both relies on the bounded gradient dissimilarity assumption, which is violated in many cases, and is not accurate enough when describing the effect of data heterogeneity. This raises concerns of the reviewer whether or not the algorithm is practical in the case of partial client participation. 2. The paper wants to address the communication bottleneck in FL setting by reducing the total number of communication rounds the algorithm needed to reach a certain accuracy level. However, it is also important to take into account the number of bits transferred from the client to the server as they are often constrained by the bandwidth. In fact, the terms communication complexity/efficiency appeared in the paper are quite misleading. 3. As the authors have suggested, the analysis is carried out in the case where each local objective $f_i$ is $\mu$-strongly convex, which is a little restrictive. 4. There are some typos (e.g., Line 265).

Questions

1. In Table 1, why do the authors compare the number of communication rounds rather than the total amount of communication for each algorithm? Does all of those algorithms have the same communication overhead in each communication round? If the reviewer is not mistaken, some algorithms (such as SVRP) in the table work in the single client setting, is it fair to compare them directly to S-DANE in the full client participation setting? 2. For S-DANE (and its accelerated version), how to determine the proper stepsize? In the convergence guarantee, $\gamma$ depends on the unknown average Hessian dissimilarity constant $\bar{\delta}_s$ and the bounded gradient diversity constant $\zeta$. Could the author illustrate on how the two constants are estimated?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

No.

Summary

An algorithm for distributed convex optimization with partial participation is proposed, under a similarity assumption.

Strengths

The proposed algorithm has complexity Acc-S-DANE has claimed communication complexity O(sqrt(delta/mu)log(1/epsilon), for the first time. (I did not check the details of the proof but the main lines look correct to me).

Weaknesses

* I want you to discuss your statement "Suppose we use the standard gradient descent as a local solver, then the number of gradient steps required to solve the subproblem increases across the iterations k". I don't think this is correct. In fact, you should discuss the 5GCS algorithm in Grudzien et al. "Can 5th Generation Local Training Methods Support Client Sampling? Yes!" AISTATS 2023. 5GCS is essentially a Point-SAGA algorithm with inexact computation of the proximity operators, and different strategies to solve these subproblems are discussed. The number of GD steps does not increase, you just pay a log(L/mu) factor for that in the complexity. * You need to provide 2 tables: Table 1 in the full participation case, and a second table on existing algorithms for partial participation of $s$ clients. In particular, 5GCS and TAMUNA in "TAMUNA: Doubly Accelerated Federated Learning with Local Training, Compression, and Partial Participation" arXiv:2302.09832, 2023 have communication complexity $O\left(\sqrt{\frac{nL}{s\mu}}+\frac{n}{s}\right)\log(1/\epsilon)$. * The complexity of Catalyzed SVRP reported in Table 1 is not correct. This value is for a different communication model, which counts "exchanging a vector between the server and one of the clients as a single communication step". So, if $s$ clients communicate, the complexity is multiplied by $s$, and $s=1$ gives the best complexity in this sense, since asynchronicity is encouraged. This is clearly different from measuring the number of communication rounds, in which $s<n$ *worsens* the complexity. * You should discuss the paper Beznosikov et al. "Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities", arXiv:2302.07615 * You should compare in your experiments to some of the methods mentioned above, in the two heterogeneous (delta = L) and homogeneous (delta<<L) regimes: does your method improve on them by exploiting the similarity, whereas other methods do not? (it might be that an algorithm also benefits from similarity, but has just not been studied under the similarity assumption in the literature). * Definition 4 is very restricting, this means that the $f_i$ are all the same up to a linear difference. This is an auxiliary result but it is not very useful in practice. typo in several places : mu-convex -> mu-strongly convex The paper [4] has been published in ICLR.

Questions

Do you assume that $\delta\geq \mu$? Because a complexity of $\sqrt{\delta/\mu}$ is a strong statement, it means that the algorithm converges in 1 round if $\delta \rightarrow 0$. FedRed, for instance, has $(\delta+\mu)/\mu$. Please check.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Summary

The paper introduces a stabilized version of DANE (S-DANE). It replaces the proximal point step with an extragradient-type step. With the well-designed subproblem criterion, the number of local gradient oracle queries improves over DANE in logarithmic terms. It further combines Monteiro-Svaiter acceleration with S-DANE, which leads to the best communication complexity. The paper also considers partial client participation.

Strengths

a) S-DANE eliminates the logarithmic term present in DANE. b) Accelerated S-DANE achieves a communication complexity of \(O(\sqrt{\delta_A/\mu \log(1/\epsilon)})\), which surpasses the complexities in the existing literature. c) The clarity of the manuscript's writing is good.

Weaknesses

See "Questions".

Questions

1. Apart from its resemblance to the extragradient method when \(\mu = 0\), what is the underlying motivation for considering equation (3)? 2. Regarding line 129 on page 4, the statement "such computation overhead cannot be avoided" seems imprecise. In the strongly convex case presented in [35] and both the convex and strongly convex cases described by Lan et al., 2023, the number of gradient steps required to solve the subproblem does not necessarily increase with \(k\). Lan, G., & Li, Y. (2023). A Novel Catalyst Scheme for Stochastic Minimax Optimization. arXiv preprint arXiv:2311.02814. 3. Some suggested references for extragradient: Korpelevich, G. M. (1976). The extragradient method for finding saddle points and other problems. Matecon, 12, 747-756. Nemirovski, A. (2004). Prox-method with rate of convergence O (1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1), 229-251.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Summary

This paper considers the problem of distributed optimization under second-order similarity under (strong) convexity and smoothness. The paper proposes a new algorithm, Stabilized DANE, which (a) matches the best-known communication complexity under Hessian similarity while (b) requiring that local computation problems are solved only up to an approximately constant accuracy (i.e. not an accuracy that depends polynomially on $1/\epsilon$ where $\epsilon$ is the desired solution accuracy). The authors also consider partial participation, where only a subset of the clients is available at any given time, and also provide an accelerated version of Stabilized DANE.

Strengths

- The paper is written clearly and the new algorithms are well-motivated. The proofs are easy to follow. - The stabilization technique is elegant and clearly obtains both theoretical improvements (mostly in local computation complexity, as far as I can tell) and in practice (as shown in Section 5). - The algorithms developed build on DANE, which is well-known and already a strong algorithm.

Weaknesses

1. "It is necessary to assume a certain level of dissimilarity" (lines 208-212), I'm not actually sure that's _necessary_. There are certainly upper bounds without this assumption. Why is it necessary? Relaxed assumptions like expected smoothness are often enough even in this setting. 2. The complexities given for Acc-SVRS/Catalyzed SVRP in Table 1 are not consistent with how the other rates are presented in this work-- the $n$ factors should not be there, since in Table 1 for every other work full participation is assumed anyway (i.e. they should all have an $n$ factor multiplied). Which brings me to another point: What is the advantage of S-DANE over SVRS/SVRP? Is it only the higher efficiency of local computation? 3. The paper right now has a few different settings (full participation, partial participation) that contrast to other settings in prior work. Remark 6 attempts to explain the difference but I think this should be explained more clearly and placed in the main body of the paper.

Questions

- Please address my concerns in the weaknesses section. - Is the hessian similarity actually smaller than the smoothness over the training trajectory in the CIFAR10 optimization task? - Can you derive theory for the variant of your method with no control variates that you use in the deep learning experiment? Does it just reduce to stabilized prox then?

Rating

7

Confidence

5

Soundness

4

Presentation

4

Contribution

3

Limitations

N/A.

Summary

The paper introduces a new variant of the existing DANE algorithm for federated learning. The paper integrates the stabilized proximal point method into DANE to form S-DANE. Convergence analyses are provided showing that S-DANE has the same rate as DANE but with better dependency on the communication round. The accelerated variant of S-DANE is also proposed which achieves better rates than S-DANE. Numerical experiments are able to show the advantage of S-DANE and Accelerated S-DANE compared to existing works.

Strengths

- The related work discussion of the paper is good. I am able to see how the paper is positioned among existing works. - I have not seen stabilized proximal update applied to federated learning (FL) so the idea in the paper appears to be new for FL. - S-DANE and accelerated S-DANE are able to achieve the best-known rate for their corresponding setting. - The claims are supported by theoretical analyses. - The convergence results are done under both full and partial client participations. - Extensive experiments showing the advantage of S-DANE/Accelerated S-DANE.

Weaknesses

- The design of the algorithm is a little bit unclear, see questions below. - Somehow I only see the full 8 algorithm in the left-most plot in Figure 2, while in the remaining 3 there are only about 4 algorithms displayed in the plots, i.e. I cannot see Snaffnew, AccGradSliding, DANE-GD, GD.

Questions

1. In both algorithm 1 and algorithm 2, aseach device $i \in S_r$ performs the update in parallel, I do not see how $\nabla f_{S_{r}} (v^r)$ or $\nabla f_{S_{r}} (y^r)$ is computed since it requires the evaluation of the gradient of $f_j$ for $j \in S_r, j\neq i$? 2. In Figure 4, Scaffnew actually performs worse than Scaffold, this is somewhat surprising given the experiments in Mishchenko et al. (2022). What is your explanation on this?

Rating

7

Confidence

4

Soundness

2

Presentation

3

Contribution

3

Limitations

The paper adequately discusses the limitation.

Responses to authors

I thank the authors for the responses. I believe my concerns have been fully addressed. I have adjusted the score. If the paper gets accepted, I would like these responses to appear in the revised version as well.