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

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.

We appreciate your appreciation of our work.

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

Our work builds upon related studies, including EF14 and EF21-P (Gruntkowska et al., 2023). Unlike Gruntkowska et al. (2023), which analyzed EF21-P under constant step sizes in strongly convex and smooth convex regimes, Lemmas 1 and 2 enable the analysis of EF21-P with any general step size rules, seamlessly covering both smooth and nonsmooth convex regimes. We also concur with Reviewer 6CKe that Lemmas 1 and 2 for EF21-P can be applied to EF14. This is because EF21-P is equivalent to EF14 in the single-node case, as demonstrated by Gruntkowska et al. (2023). However, while EF14 for nonsmooth convex regimes, as studied by Karimireddy et al. (2019), is limited to constant step sizes, Lemmas 1 and 2 extend this analysis to accommodate any general step size rules.

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. We apologize for these typos. In the revised manuscript, we will replace $\alpha$ with $\eta$ in the convergence theorems.

If $f$ is not differentiable the subgradient can have many elements. What does Assumption 3 mean in this case? 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.

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 = \mathcal{O}(k^{-1/3})$). Considering one specific decreasing scheme makes the theoretical contributions very limited.

We consider this comment to be minor. We agree that exploring other adaptive step size strategies, such as Adagrad, gradient diversity-based step sizes, and Nonnegative Gauss-Newton step sizes, to establish the convergence of EF21-P would further enhance our contribution. However, we may have misunderstood your suggestion regarding the choice of a specific decreasing step size. Using $\gamma_k = \mathcal{O}(k^{-1/3})$ ensures a convergence rate of $\mathcal{O}(K^{-2/3})$, which remains slower than the rate achieved with a properly tuned constant step size. This holds true for any stochastic gradient descent and variants. We would be happy to discuss this further.

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]$.

**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$. ** Hölder continuity: 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. SVM: We kindly refer you to the SVM problem discussed in Section 5 of Shamir & Zhang (2013), which provides details on computing subgradients for the regularized SVM problem. Additionally, we note a typo in the reviewer's comment: the subgradient is $-a_i b_i$ if $b_i \langle x, a_i \rangle \leq 1$, and $0$ otherwise.

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.

To the best of our knowledge, practical problems where the interpolation condition holds include deep neural network training problems. These problems inherently involve training over-parameterized models, as discussed in Lines 462–464.

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.

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.

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.

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, one of our key contributions 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.

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.

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.

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?

We show the results for Sections 5.1.-5.3 to illustrate how our descent lemmas can be used to obtain the convergence of EF21-P in both smooth and nonsmooth regimes in a unified manner. Furthermore, we derive the optimal convergence bound from Section 5.1 with constant stepsizes, which can be shown later that this bound can be achieved by the Polyak stepsize in Section 5.3.

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^{*}$.

The problem of [1] and [2] is that the analysis for EF14 is applied for constant and decreasing stepsizes. This is in contrast to our work, where the Polyak stepsize can be applied. We agree that $f^{\star}$ must be known, but it can be estimated for some classes of optimization problems, as discussed by Loizou et al. (2021).

However, we agree that Lemma 14 of [1] can be utilized to derive the convergence rate from our descent lemmas in Lemmas 1 and 2.

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

Unlike earlier studies on error feedback algorithms, such as EF21-P (Gruntkowska et al., 2023) and EF14, which primarily rely on constant step sizes to ensure convergence, our Lemmas 1 and 2 enable us to establish the convergence of EF21-P under any general step size rules in both smooth and nonsmooth settings in a unified framework. Additionally, we provide the first theoretical demonstration of integrating Polyak step sizes with error feedback algorithms, representing a key innovation in this paper, as highlighted by Reviewers aGTD and gPkf. Moreover, EF21-P can be seamlessly combined with distributed algorithms that employ compression for client-to-server communication, such as DIANA and DCGD, paving the way for bi-directional compression algorithms. While we acknowledge the suggestion to present convergence results for these bi-directional compression algorithms using EF21-P, we note that this aspect is outside the scope of the present work.

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$.

We acknowledge that the interpolation condition can be restrictive. However, it is a widely used assumption in the analysis of gradient-based algorithms with Polyak step sizes, as demonstrated by Loizou et al. (2021) and Wang et al. (2023). This condition is crucial for proving that gradient-based algorithms with Polyak step sizes can achieve the optimal convergence bound, unlike those employing constant or decreasing step sizes. In contrast, for other step size strategies, such as constant or decreasing step sizes, Lemmas 1 and 2 establish the convergence of EF21-P without requiring the interpolation condition. Exploring other adaptive step size strategies for EF21-P without relying on interpolation is an intriguing direction, which we discuss in more detail in the future works section.

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

We apologize for these typos. In the revised manuscript, we will replace $\alpha$ with $\eta$ in Line 270, and in the convergence theorems.

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 nonsmooth $\eta=0$.

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.