Error Feedback for Smooth and Nonsmooth Convex Optimization with Constant, Decreasing and Polyak Stepsizes

Authors: Sarit Khirirat, Peter Richtárik
Primary area: optimization
Keywords: Error feedback; Polyak stepsize; Communication-efficient optimization

Abstract:
Error feedback, originally proposed a decade ago by Seide et al (2014), is an immensely popular strategy for stabilizing the convergence behavior of distributed algorithms employing communication compression via the application of contractive compression operators, such as greedy and random sparsification, quantization, and low-rank approximation. While our algorithmic and theoretical understanding of error feedback has grown immensely over the years, several important considerations remained elusive. For example, the theory of error feedback is fully focused on the smooth convex and nonconvex regimes, and results in the nonsmooth convex setting are limited. This is not a coincidence: Error feedback works when the gradients converge, and this is not necessarily the case in the nonsmooth setting. Further, existing stepsize rules for error feedback are limited to constant schedules; a by-product of the current theoretical approach to analyzing error feedback. By modifying the algorithmic design of error feedback, we are able to resolve these issues. In particular, we provide a comprehensive analysis covering both the smooth and nonsmooth convex regimes, and give support for constant, decreasing and adaptive (Polyak-type) stepsizes. This is  the first time such results are obtained. In particular, this is the first time adaptive stepsizes have successfully been combined with compression mechanisms. Our theoretical results are corroborated with suitable numerical experiments.

Decision: reject
Reviewer scores: 5, 3, 8, 3

Reviews and discussion:
<thread>
creation date:
1730161225160

thread_type:
official_review

<thread_object>
creator: reviewer_gpkf

<content>
summary:
In this work, the authors analyzed the convergence rate of the error feedback algorithm EF21-P. The authors focused on the convex setting when the objective function can be a smooth or non-smooth convex function. Three different stepsize schema, constant, decreasing and Polyak, are considered and their convergence rates are proved. In addition, the authors provided the convergence rate when the stochastic EF21-P algorithm is applied and the objective function is a finite-sum loss function with the interpolation condition. Numerical examples are provided to support the theoretical findings.

strengths:
The paper has is well-structured and easy to follow. The intuition behind the design and the theory of the new stepsize schema is clear and easy to understand. The results under the setting of distributed convex optimization should be novel (although a similar problem may have been studied under a different setting) and the proofs should be correct.

weaknesses:
The major weakness of the paper is that the theory in this paper seems very preliminary. For example, in Theorem 2, the decreasing stepsize has a worse convergence rate than the constant stepsize. It would be curious if this is also the case for other schema of decreasing stepsize (e.g., $\gamma_k = O(k^{-1/3})$). Considering one specific decreasing scheme makes the theoretical contributions very limited. In addition, the authors defined Assumption 3 with a general $\eta$ but focused on two special choices, $\eta=0$ and $\eta=1$. This also seems too limited to me and may be generalized to other values of $\eta$. It would be helpful if the authors could generalize the results to other choices of decreasing stepsizes and other values of $\eta\in[0,1]$.

The authors claimed that the advantage of the Polyak stepsize is that it does not require estimating the Lipschitz constant and the optimal objective function value is easier to estimate. However, I feel that the authors did not provide convincing evidence that the optimal objective function value is easier to estimate than the Lipschitz constant, although I agree that in certain problems the optimal objective function value is exactly zero. I would suggest the authors provide more supporting evidences for this claim. For example, the authors may provide references or practical examples where the optimal value can be estimated a priori. This would help substantiate the claim about the advantages of the Polyak stepsize.

Finally, I feel that similar problem may have been studied by splitting-operator algorithms, where the compression operator $C$ can be the operator induced by the splitting operator (e.g., the Douglas–Rachford splitting or the Peaceman-Rachford splitting). It would be helpful if the authors could discuss the similarities and differences between the compression operator $C$ and a split operator. This could provide valuable context on the novelty and positioning of this work.

Overall, I feel that this paper presented some novel and interesting results, but the theory of the paper may have focused on a few very specific settings and this will limit the applicability of the results in this work.

questions:
I have a few other minor comments for the authors to consider:

- The theory in Theorem 3 cannot capture the better empirical performance of Polyak stepsize than the constant stepsize. Maybe the authors could consider improving the constant before $1/\sqrt{K}$ or $1/K$.

- Lines 122 and 256: If EF21-P is equivalent to EF14, maybe the authors can choose to replace EF14 with EF21-P throughout the paper to avoid confusions.

- Line 270: $\alpha=1$ should be $\eta=1$. Also, in Theorem 1, $\alpha=0$ should be $\eta=0$.

- Assumption 3: I wonder if the assumption applies to the case when the subgradient is not unique at some points. In the case when the subgradient may not be unique, how do we choose the function $g(x)$ to guarantee the Holder continuity and the convergence? For example, in the SVM example, why did the authors choose the subgradient at line 499 when $b_{i}\langle a_{i}, x\rangle = 1$.

- Line 312: the current choice of $\lambda$ and $\theta$ only considers constant B in the inequality. This choice ignores their appearance in the Lyapunov function. I wonder if it is possible to derive the convergence rate with general $\lambda$ and $\theta$ and then choose the optimal value based on the convergence rate?

- Line 368, it should be for any initial iterates $x_0,w_0$. There are many other typos in the paper. I would suggest the authors check the paper carefully and fix the typos.

- Lines 373 and 377: $\hat{x}_{K}$ is not defined.

- Line 452: I cannot see why the interpolation condition implies that $f(x_*)=0$.

- In Figure 1, it would be better if the authors could show the performance of the constant/decreasing stepsize when they converge. It is hard to check if the current stepsize schema lead to global convergence, since it is possible that the current stepsize is too large or too small.

- In the main paper, the authors focused on the SVM example. However, the results of SVM are not presented in the main paper.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730217457177

thread_type:
official_review

<thread_object>
creator: reviewer_agtd

<content>
summary:
The paper presents new analysis for compressed (sub-) gradient descent with error feedback. The contributions include analysis for full batch GD for convex functions in the non-smooth case and analysis with decreasing and Polyak step-sizes. SGD with compression in the interpolation regime is also analyzed using a similar Lyapunov function as in the full batch case.

strengths:
The paper is very well-written and easy to read. The authors invest substantial effort to explain their contribution compared to related work. This contribution, while not too original, is fair in the sense that presents analysis of a popular algorithm (error feedback) with popular choice of step-sizes apart from the constant one for which analysis already exists. In addition, there is analysis for non-smooth optimization problems (like support vector machines), which is not really surprising, but still a good to know result.

weaknesses:
As discussed previously, my only issue with the paper is that it is blend of very-well known ideas, like error-feedback, adaptive step-sizes for GD, SGD in the interpolation regime etc.

questions:
1. Is the Lyapunov function presented in Lemma 1 completely original, or there is some version of it in previous work?

2. It is repeatedly written over the results about Assumption 3 holding with $\alpha=0$ or $\alpha=1$, but $\alpha$ measures the quality of the compressor and Assumption 3 is about Holder continuity.

3. Why some to use diminishing step-sizes? The rate is worse and if I'm not mistaken one needs again to compute the generally unknown hyperparameters $L_0,L_1$.

4. If $f$ is not differentiable the subgradient can have many elements. What does Assumption 3 mean in this case?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730467171479

thread_type:
official_review

<thread_object>
creator: reviewer_6cke

<content>
summary:
The paper studies the error feedback mechanism under non-constant step sizes. In particular, with decreasing step sizes and Polyak step sizes. The author corroborated their theory with some numerical experiments.

strengths:
The majority of the existing works on the Error Feedback mechanism focused on well-tuned constant-step sizes. This paper instead studies the case where the step sizes are changing. It also investigates the combination of EF with adaptive step sizes which seems to be the first in the field.

weaknesses:
1. Seide's formulation of the Error Feedback mechanism (as is adopted in most existing works, e.g. [1]) is well-established in the literature. The authors refers to this formulation as EF14. I wonder why does the author, instead of just using this well-established formulation, use what they called "EF21-P" formulation? It seems to me that this EF21-P formulation is just writing the "virtual iteration" (used in the analysis of Seide's EF, see e.g. [1]) explicitly into the algorithm, which is a reasonable reformulation of Seide's EF but does not seem to bring any new benefit in the context of this paper. I would suggest the authors to just stick to the well-established formulation instead of rebranding it.

2. I do not understand the necessity of introducing the Hölder's smoothness condition. The paper focuses on two cases: 1) Lipschitz gradient and 2) Lipschitz continuity. Both cases are standard and extensively studied in the optimization literature. My understanding is that, when you bring up the Hölder's smoothness condition, you typically deal with "Universal methods" that automatically adapt to the best $\eta$, which is clearly not the case here. Since the theorems are stated separately for 1) and 2) anyway, I would suggest the authors to remove Assumption 3 completely to avoid confusions.

3. Regarding Lemma 1 and Lemma 2: The typical workflow of the analysis of variants of Seide's EF is the following: First you derive a descent lemma for the virtual iteration (which is the $x_t$ in this paper), and then you derive a descent lemma for the error term (which is the $w_t-x_t$ term in this paper), and then you combine the two into a Lyapunov function and proceed with the complexity analysis. Different regularity assumptions (e.g. convexity, smoothness, Lipschitzness) might affect the specific details of the derivations of these descent lemmas, but typically the overall template is not affected. The Lemma 1 and Lemma 2, though have been given strong emphasis in the main text (spanning 2 sections), seem to be a simple summary of the workflow I just described above. If these two lemmas somehow carries more insights, the authors should highlight it more clearly.

4. Regarding Section 5.1: These results seem to be well-known in the literature (see e.g. [1][2]). Is there any reason why they have to be there?

5. Regarding the changing step sizes: Typically the problem with changing stepsizes is extracted out and dealt with separately. In the case of decreasing step sizes, it seems to me that the backbone of the analysis is completely intact and one only has to do a different "summation lemma" for a complexity estimation (see, e.g. section 3.5 of [1]). Is it also the case in this paper? The case of Polyak stepsizes seems more interesting, but I would like to point out that, even though the authors claim in Table 2 that  for the Polyak step sizes the only required parameter is B, it is a bit disingenuous because you would also have to know $f^\star$.

[1] Stich, Sebastian U., and Sai Praneeth Karimireddy. "The error-feedback framework: SGD with delayed gradients." Journal of Machine Learning Research 21.237 (2020): 1-36.
[2] Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes SGD and other gradient compression schemes. In International Conference on Machine Learning, pp. 3252–3261. PMLR, 2019.

questions:
see weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730571185140

thread_type:
official_review

<thread_object>
creator: reviewer_dikj

<content>
summary:
This paper studies the convergence behaviors of EF21-P when using different kind of stepsizes (fixed, decreasing, polyak) under different cases (deterministic and stochastic, convex and non-convex).

strengths:
This paper presents a comprehensive study on the stepsize scheduler of EF21-P. The work contains the convergence rates of EF21-P under deterministic convex case when using constant, decreasing, and Polyak stepsize, as well as convex stochastic under an interpolation condition.

weaknesses:
I find the following weaknesses in the paper and hope the author can address them:

1. The paper only focuses on the stepsize scheduler and the related convergence rates on EF-21P, however, they do not compare their convergence rates with other distributed convex optimization methods. Hence, it is quite difficult to check their theoretical contributions.

2. For the stochastic cases, the authors consider an interpolation condition which is too strong in distributed optimization, which means the optimal point of $f$ is also the optimal point of every $f_i$.


Some typos:

line 270 $\alpha=1$ should be $\eta=1$ and all left theorems use $\alpha$, which should be replaced by $\eta$.

questions:
Please check the weakness parts. Also with the following questions:

1. What is challenge of dealing with the non-smoothness in analysis? It seems that doing analysis on Assumption 3, one can directly obtain a general result that cover the case of smooth $\eta=1$ and non-smooth ($\eta=0$).

I am not an expert in this field and I shall read the comments from other reviewers and the rebuttal from authors and may change my score accordingly.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732528936690

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We appreciate all the reviewers for their appreciation of the novelty of adaptive stepsizes on error feedback algorithms under nonsmooth and smooth regimes. 

We would like to start with addressing common concerns, and will address each reviewer’s comments individually. 

**Concern 1: Why EF21-P, not EF14?:**   EF21-P, while equivalent to EF14, serves as a useful error feedback algorithm designed for server-to-client communication. Notably, EF21-P can integrate with distributed algorithms that compress client-to-server communication, such as DIANA and DCGD, enabling the creation of bi-directional compression algorithms. In contrast, EF14 focuses on saving client-to-server communication and does not support this bidirectional capability.

**Concern 2: Regarding Lemmas 1 and 2:**  Lemmas 1 and 2 enable us to establish convergence for error feedback algorithms using any step size strategy $\gamma_k > 0$, unlike prior works on error feedback algorithms—such as EF21-P (Gruntkowska et al., 2023) and EF14—which predominantly rely on constant step sizes to guarantee convergence. These lemmas allow us to derive the convergence of EF21-P in both smooth and nonsmooth regimes in a unified manner. 

We agree with Reviewer 6CKe that Lemmas 1 and 2 for EF21-P can be applied for EF14. This holds true because EF21-P is equivalent to EF14 for the single-node case, as shown by (Gruntkowska et al., 2023). However, EF21-P is an error feedback algorithm addressing a different issue from EF14, as explained in Concern 1. 

Moreover, another key contribution in our work is presenting the first result demonstrating the successful integration of Polyak step sizes with error feedback algorithms. To the best of our knowledge, this is the first instance of adaptive step size strategies being applied to error feedback algorithms, setting it apart from prior works that only consider constant step sizes. Our framework also supports other adaptive step size methods, such as Adagrad, gradient diversity-based step sizes, and Nonnegative Gauss-Newton step sizes, for establishing convergence results.

**Concern 3: Hölder's continuity of subgradient:**  We leverage the Hölder continuity of the subgradient, parameterized by $\eta$, to establish our convergence theorems while accommodating both nonsmooth and smooth regimes. This approach minimizes the need for restrictive assumptions about the Lipschitz continuity and smoothness of the function $f$. We concur with Reviewer 6cKe's observation that convergence theorems for gradient-based algorithms under this condition typically hold for any $\eta \in [0,1]$. This represents a compelling extension that necessitates revisiting the Lyapunov function to derive the convergence of EF21-P under general step size rules.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This work addresses limitations in the theory of error feedback, a popular method for stabilizing distributed algorithms with communication compression. It extends error feedback analysis to nonsmooth convex settings, supports constant, decreasing, and adaptive (Polyak-type) stepsizes, and introduces a combination of adaptive stepsizes with compression mechanisms. Theoretical advancements are validated with numerical experiments.

While the paper's theoretical approach is interesting, the reviewers raised several concerns regarding its novelty and assumptions. The key points are summarized below:

1. One reviewer noted the lack of comparison with other distributed convex optimization methods, making it difficult to evaluate the paper’s theoretical contributions.
2. The same reviewer criticized the use of an interpolation condition in the stochastic setting, describing it as too strong for distributed optimization.
3 Another reviewer questioned the necessity of the Hölder smoothness condition.
4. This reviewer also expressed doubts about the technical novelty of the proof techniques, pointing out that some results are already well-established in the literature.