Stabilized Proximal-Point Methods for Federated Optimization

We thank the reviewer for the great evaluation of our paper. Your every comment is important to us. We did our best to understand and reply to your constructive feedback as follows:

W1

Thanks for the great question. Here are some justifications.

1. Interestingly, we do not use any smoothness-related assumptions to prove the communication complexity. Therefore, the function classes also include Lipschitz and non-smooth functions. In this case, we believe using Definition 4 is reasonable.

2. If we further assume that the function $f$ is $L$-smooth, then we agree that Definition 4 can be relaxed. For instance, one can consider $\frac{1}{n}\sum_{i=1}^n ||\nabla f_i (x) - \nabla f(x)||^2 \le \zeta^2 + \beta ||\nabla f(x)||^2 \le \zeta^2 + 2\beta L (f(x) - f^\star)$ with $\beta > 0$, which captures the growth behaviour of the dissimilarity. The only change in the proof will appear in line 589 where we have an additional error term which can be canceled by choosing small $\gamma$ and large $\lambda$ that depend also on $\beta$ and $L$.

3. The interesting regime of considering partial client participation is when the number of clients $n$ is potentially very large. Then Definition 4 allows almost unbounded distribution of the gradient dissimilarity (similar to the notion of 'stochastic gradient noise' for centralized SGD). Therefore, we believe using this assumption is still reasonable in practice. More detailed discussions can be found in Section 2 from [22] where the same assumption is used.

W2 & Q1

Thanks for this nice question! We refer to the attached pdf for the clarification of your concerns. Please let us know if there is anything unclear. We will add the discussions to our main manuscript.

W3

Yes! However, note that our analysis works for standard convex functions ($\mu = 0$) as well. In the strongly convex case, when the function is of the form $f(x) = \frac{1}{n} \sum_{i = 1}^n \phi_i(x) + \frac{\mu}{2} || x ||^2$, we can rewrite it as $f(x) = \frac{1}{n} \sum_{i=1}^n f_i(x)$ with $\mu$-strongly convex $f_i(x) = \phi_i(x) + \frac{\mu}{2} || x ||^2$.

In practice, the strong convexity often comes from adding explicit regularization of the local convex loss function (e.g. regularized logistic regression). Then each function typically is strongly-convex and $\mu$ is often known.

We can actually propose the version of our method for composite functions $F(x) = f(x) + \psi(x)$ for which such an artificial split would be unnecessary but we do not do it for simplicity.

W4: typos

Thanks for finding the typos!

Q2

Thanks for asking this important question. We refer to the section of 'adaptive S-DANE with line-search' in the attached pdf for answering this question.

We thank you again for your great review! If you agree that we managed to address all issues, please consider raising your score–this would totally boost our chance. If you believe this is not the case, please let us know and we will try our best to answer your every question!

We thank the reviewer for the great evaluation of our paper. Your every comment is important to us. We did our best to understand and reply to your constructive feedback as follows:

W1

Thanks for the nice question.

1. This statement only (appears and) refers to the accuracy condition written in line 124. To satisfy this condition, if using GD, then the number of steps should depend on $k$, which is correct.

2. This condition is only stated for the original proximal point method (eq 2). It is well-known that the local computation has an unnecessary logarithmic dependency on either k or the final accuracy for this method, which can be improved by using more advanced variants [1,2,3].

3. 5GCS is different from the original proximal point method when $n=1$. In Table 1, many previous works (with proximal-point steps) also do not require increasing the number of GD steps, such as AccSVRS. These facts do not contradict this statement because these are different methods.

4. Acc-S-DANE is strictly better than 5GCS at least in the full-client participation settings. 1) the communication complexity depends on $\delta_A$ instead of $L$ for 5GCS 2) Even if $\delta_A = L$, the number of local steps is 1 instead of $\tilde{O}( \sqrt{L/\mu} )$ for 5GCS. 3) we prove convergence for the function value which is stronger than the squared distance for 5GCS. 4) it works well when $\mu \to 0$ while 5GCS seems not well-defined when $\mu = 0$.

Nevertheless, 5GCS is an excellent method in some settings and we will add more discussion on it.

[1] Svaiter B.F. and Solodov, M.V. A hybrid projection-proximal point algorithm. Journal of Convex Analysis. 1999.

[2] Carmon, Yair, et al. Recapp: Crafting a more efficient catalyst for convex optimization. ICML 2022.

[3] Ivanova, Anastasiya, et al. Adaptive Catalyst for Smooth Convex Optimization. International Conference on Optimization and Applications. 2021.

W2

Thanks for the suggestion! However, it might be difficult to compare these two methods directly with our methods and others, as different settings are considered: for instance, 1) we consider cross-device setting where $n$ might be very large and each client is stateless (no control variates are stored), and hence SAGA-type methods are not applicable 2) certain first-order dissimilarity condition has to be assumed in this setting 3) as a result, our rates do not have a dependency on $\frac{n}{s}$ but instead on $\zeta^2$.

We will add the rates and discussions of these two excellent methods in our manuscript.

W3

Thanks for the great question. The complexity is correct. In Table 1, we report the number of communication rounds for all the methods including SVRP (for which the number of rounds is in the same order as the total number of vectors transmitted). We refer to the attached PDF where the settings and how SVRP works are explained in detail. The main metric of SVRP/SVRS is different and we separated these two algorithms in Table 1 and added Remark 6.

W4

Thanks for the reference. This is a strong work. However, 1) The main target is the same as SVRP/SVRS, i.e. minimizing the total number of bits transmitted across rounds, which is different from this work. 2) It does not consider acceleration (while AccSVRS does) but uses compression to reduce the bits (while AccSVRS does not) and 3) in the end, it requires $\tilde{O}( n + \delta \sqrt{n} / \mu )$ communication rounds scaling with $n$.

W5

Thanks for the interesting suggestion. The paper is based on the existing theoretical results. Studying if certain previous algorithms can exploit similarity is a bit irrelevant to the focus of this paper, which could instead be an interesting future work. Also in many cases, by tuning hyperparameters, some methods can outperform their theoretical upper bounds. For instance, Scaffnew and Scaffold have a similar performance by tuning stepsize while Scaffold has not been proven to achieve acceleration. But as you suggested, we will try to see if some of your mentioned methods can benefit from the similarity in our toy example.

W6

1. Interestingly, we do not use any smoothness-related assumptions to prove the communication complexity. Definition 4 says the difference function is Lipschitz, and the original functions can be non-smooth.

2. Lipschitz functions are not just linear functions. The log-sum-exp is not linear but Lipschitz.

3. If we further assume that the function $f$ is $L$-smooth, then we agree that Definition 4 can be relaxed. For instance, one can consider $\frac{1}{n}\sum_{i=1}^n ||\nabla f_i (x) - \nabla f(x)||^2 \le \zeta^2 + \beta ||\nabla f(x)||^2 \le \zeta^2 + 2\beta L (f(x) - f^\star)$ with $\beta > 0$, which captures the growth behaviour of the dissimilarity. The only change in the proof will appear in line 589 where we have an additional error term which can be canceled by choosing small $\gamma$ and large $\lambda$ that depend also on $\beta$ and $L$.

4. The interesting regime of considering partial client participation is when the number of clients $n$ is potentially very large. Then Definition 4 allows an almost unbounded distribution of the gradient dissimilarity (similar to the notion of 'stochastic gradient noise' for centralized SGD). Therefore, we believe using this assumption is still reasonable in practice. More detailed discussions can be found in Section 2 from [22] where the same assumption is used.

Typos and reference

Thanks for finding the typos and we will update this reference.

Q1

Many thanks. Yes, in Table 1, we reported the interesting regime $\mu \le \Theta(\delta)$ and we will add it to the text.

We thank you for your great review and appreciate your help in improving the paper! If you agree that we managed to address your concerns, please consider raising your score–this would totally boost our chance. If you believe this is not the case, please let us know and we will try our best to answer your every question!

We thank the reviewer for the great evaluation and the support of our paper!

Q1

Thanks for the interesting question. The geometric meaning of equation (3) can be found in [1]. Previously, we derived this equation directly from the proof. Since we want to have the one-step recurrence of the form: $a\bigl( f(x^{r+1}) - f(x^\star) \bigr) + \frac{1+\mu a}{2} ||v^{r+1} - x^\star||^2 \le \frac{1}{2} ||v^r - x^\star||^2 ,$ then we can first use convexity at the beginning of the proof: $a f(x^\star) + \frac{1}{2} ||v^r - x^\star||^2 \ge a \bigl( f(x^{r+1}) + \langle \nabla f(x^{r+1}), x^\star - x^{r+1}\rangle + \frac{\mu}{2} ||x^{r+1} - x^\star||^2 \bigr) + \frac{1}{2} ||v^r - x^\star||^2 .$ Then it is natural to set $v^{r+1}$ to be the minimizer of the right expression in $x^\star$, which is $(a\mu + 1)$- strongly convex. After that, we can approximately get the main recurrence.

[1] Svaiter B.F. and Solodov, M.V. A hybrid projection-proximal point algorithm. Journal of Convex Analysis. 1999.

Q2

Yes, this statement is wrong for accelerated proximal-point methods. Indeed, apart from your references, we also found several adaptive catalyst frameworks [2,3] that successfully remove the logarithmic dependency on $k$. Many thanks for pointing this out and providing the important reference.

[2] Carmon, Yair, et al. Recapp: Crafting a more efficient catalyst for convex optimization. ICML 2022.

[3] Ivanova, Anastasiya, et al. Adaptive Catalyst for Smooth Convex Optimization. International Conference on Optimization and Applications. 2021.

Q3

We appreciate the reviewer for providing these nice references and we will add them to our manuscript!

We thank the reviewer again for your great review and appreciate your help in improving the paper!

We thank the reviewer for the great evaluation of our paper! Your every comment is important to us. We did our best to understand and reply to your constructive feedback as follows:

W1

Yes, this sentence is confusing! We will rewrite it.

• This sentence (that was first written in [22]) particularly refers to the setting where $n$ might go to infinity and each client does not store any vectors on its device (what people call 'stateless'). Then this sentence says to prove convergence, we need to assume a certain level of dissimilarity, which is correct. This sentence does not necessarily refer to using Definition 4.
• When $n$ is sufficiently small, then we can use SAGA-type methods (considered in Scaffold) that ask each device to store certain control variates. Then yes, no dissimilarity assumption is required. Meanwhile, we need to assume the $L$-smoothness of the function and the final complexity depends on $L$.
• In this paper, we consider the same setting as in paper [22] (with potentially very large $n$). Then as you mentioned, the question is if using Definition 4 is too strong. Interestingly, we do not use any smoothness-related assumptions to prove the communication complexity. Therefore, the function classes also include Lipschitz and non-smooth functions. In this case, we believe using Definition 4 is necessary.
• However, as you mentioned, if we further assume that the function $f$ is $L$-smooth, then Definition 4 can exactly be relaxed. For instance, one can consider $\frac{1}{n}\sum_{i=1}^n ||\nabla f_i (x) - \nabla f(x)||^2 \le \zeta^2 + \beta ||\nabla f(x)||^2 \le \zeta^2 + 2\beta L (f(x) - f^\star)$ with $\beta > 0$, which captures the growth behaviour of the dissimilarity. The only change in the proof will appear in line 589 where we have an additional error term which can be canceled by choosing small $\gamma$ and large $\lambda$ that depend also on $\beta$ and $L$.

We will make this sentence clear and add more discussions to the manuscript according to your suggestion!

W2 & W3

Thanks for raising these points! We refer to the attached PDF for clarification of your concerns. (In Table 1, we report the number of communication rounds for all the methods including SVRP for which the number of rounds is in the same order as the total number of vectors transmitted.) Please let us know if there is anything unclear. We will move these discussions to the main paper as you suggested!

Q2

This is a very interesting question. From our experiments, we saw that the estimated dissimilarity quantity defined as in Figure 3 ranges from $10^{-4}$ to $10^{-3}$ in the CIFAR10 task (and we choose $\lambda = 10^{-3}$ and the local learning rate $10^{-1}$ for S-DANE). Unfortunately, we did not record the local estimated smoothness quantity for our experiments. Empirically studying the relation between Hessian similarity and smoothness in different deep-learning tasks with various NN structures is indeed a very interesting future direction.

Q3

Yes! The proof is similar to the one for S-DANE with $1$ client participation. Let us compare Algorithm 3 with $s= n$ and Algorithm 1 with $s = 1$. The main difference is that the former considers deterministic averaging and the latter considers sampling (in the proof, we need to take expectation for the latter which is similar to the deterministic averaging for the former). Therefore, if we study Algorithm 3, we have to similarly assume a certain first-order dissimilarity condition. We are not fully sure what you mean by stabilized prox. But yes, it can be seen as stabilized FedProx.

We thank you again for your great review and we appreciate your support! If you agree that we managed to address all issues, please consider slightly raising your score–this would totally boost our chance. If you believe this is not the case, please let us know and we will try our best to answer your every question!

We thank the reviewer for the great evaluation of our paper. Your every comment is important to us. We did our best to understand and reply to your constructive feedback as follows:

W1 & Q1

Thanks for the question. The description can be found from line 158 to 163. Specifically, during each communication round $r$, the server first sends $v^r$ to the sampled clients. Then each client $i \in S_r$ computes $\nabla f_i(v^r)$ and sends this vector back to the server. Afterwards, the server computes $\nabla f_{S_r}(v^r) = \frac{1}{s}\sum_{i \in S_r} \nabla f_i(v^r)$ and sends $\nabla f_{S_r} (v^r)$ back to these clients. The same procedure was written in Section 4 in the Scaffold paper [1].

W2

Thanks for the great observation. The remaining 3 plots are about partial-client participation. Indeed, we do not plot these four algorithms as partial-client participation is not considered in their original papers. We will make it clear in the manuscript.

Q2

Thanks for the great observation. Note that Scaffold has two choices of control variates (cv). The cvs between Scaffnew and Scaffold are different in our experiments. For Scaffold, we use the same cv as DANE (option I in [1]) while for Scaffnew the cv is similar to option II in [1].

1. In the Scaffnew paper, they use the same cv for both Scaffnew and Scaffold. This is why they perform similarly (with tuned parameters).

2. So far, no results have shown that the cv for Scaffnew can achieve communication reduction under second-order similarity. However, the other cv (option I) can exploit similarity [2]. This is perhaps why we can observe a better performance of Scaffold in certain experiments.

3. Figure 4 is about deep learning. We expect that the cv for Scaffnew {option II} can be slightly less stable than another cv (option I).

[1] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. ICML 2020.

[2] Xiaowen Jiang, Anton Rodomanov, and Sebastian U Stich. Federated optimization with doubly regularized drift correction. ICML 2024.

We thank you again for your great review! If you agree that we managed to address all issues, please consider raising your score–this would totally boost our chance. If you believe this is not the case, please let us know and we will try our best to answer your every question!