Clip21: Error Feedback for Gradient Clipping

While gradient clipping is originally known to solve the exploding gradient problem, it seems not reflected in theoretical analysis of this paper. This paper still considers the standard $L$-smooth setting rather than $(L_0,L_1)$-smoothness, so the benefit of using clipped gradients is unclear from the theory.

We agree that Clip-GD enjoys stronger convergence guarantees than GD for problems under the $(L_0, L_1)$ smoothness assumption, which implies the exploding gradient condition in deep neural network training [1]. However, existing results of gradient clipping algorithms are limited for the centralized case (one master and one client).

Even under the $L$-smoothness assumption, we show that distributed clipping algorithms do not even converge towards the optimal solution (see Example 1). This motivates our investigation to modify standard clipping methods to attain strong convergence for distributed settings. We also prove theoretically and empirically that Clip21-GD outperforms these standard gradient clipping algorithms.

Furthermore, we believe that our analysis is sufficient to prove the convergence under the $(L_0, L_1)$ smoothness. We prove this by finding the upper-bound for $\Vert \nabla^2 f(x_k) \Vert$ and our results apply as follows:

1. By the $(L_0, L_1)$ smoothness and Assumption 3 of [A1],

2. We then have $\Vert \nabla^2 f(x_k) \Vert \leq L_0 + L_1 \sqrt{2L\phi_0}$ for all $k \geq 0$ by proving that $f(x_k) \leq f_{\inf}+\phi_0$ by the induction and by setting the step-size $\gamma$ sufficiently small.

We also refer the reviewer to our general response, where we explain why the current analysis from our paper holds under $(L_0, L_1)$-smoothness.

[A1]: Khaled, Ahmed, and Peter Richtárik. "Better theory for SGD in the nonconvex world." arXiv preprint arXiv:2002.03329 (2020).

This paper only considers the case for deterministic gradients. Although it is expected that similar results hold for stochastic gradients, in the gradient clipping literature more restrictive assumptions are made on noise (bounded noise tather than the more standard bounded variance, see e.g. [1]). It is unclear whether gradient noise is an issue in the distributed setting.

Stochastic optimization algorithms suffer from instability for neural network training, which is in the presence of heavy-tailed stochastic gradient noises. This has been observed empirically for training neural network models by centralized stochastic gradient descent in Zhang et al. (2020b), and distributed methods in [M1]. Furthermore, deriving the result for Clip21-GD with stochastic gradients is non-trivial, because of (1) the dependency of the clipping threshold $\tau$ on the noise variance parameters, and (2) the required condition on the bounded norm of the input vector before clipping. This may be proved by the strong bounded noise condition, e.g. $\Vert g - \nabla f(x) \Vert^\alpha \leq \sigma^\alpha$ with probability 1.

[M1] Yang, Haibo, Peiwen Qiu, and Jia Liu. "Taming Fat-Tailed (“Heavier-Tailed” with Potentially Infinite Variance) Noise in Federated Learning." Advances in Neural Information Processing Systems 35 (2022): 17017-17029.

In your Example 1.1, what if one chooses different clipping thresholds for different clients, or use a 'soft clipping' $\nabla f(x)/(\vert \nabla f(x) \vert + a)$? In these cases the clipped gradient does not seem to cancel out.

By using different clipping thresholds for different clients or soft clipping, the clipped gradient may not cancel out in Example 1.1. However, the solution using the clipped gradient from both cases will be further away from the initial solution for simple toy examples. First, we prove the case for different clipping thresholds by letting in Example 1.1 $\beta = 10$, $\alpha=-1$, $x_0=1$, and the clipping thresholds at $0.1$ for $f_1(x)$ and $1$ for $f_2(x)$. Then,

$x_1$ is thus further away from the optimum $x^\star=0$, as the step-size $\gamma>0$. Second, we prove the case for soft clipping by considering the problem of minimizing $f(x)=f_1(x)+f_2(x)+f_3(x)$ for $x\in\mathbb{R}$ and $f_i(x)=(\alpha_i/2) x^2$ for $\alpha_i>0$ and $i=1,2,3$. If we choose $\alpha_1 = 10$, $\alpha_2=-4$, $\alpha_3=-4$, $x_0=1$ and $a=1$, then $f$ has Lipschitz continuous gradient with $L=2$, and also

$x_1$ is therefore more distant from the optimum $x^\star=0$ as $\gamma>0$.

(Related to weaknesses 1) What is the motivation of considering gradient clipping at the client level? Because in a distributed setting, one only wants to optimize the averaged objective function, can we just clipp the averaged gradient at the server to accelerate training? If you clip the server's gradient instead of the clients, then the problem demonstrated by Example 1.1 does not exist, and there may be a more straightforward approach.

Implementing the client-side gradient algorithm is necessary for designing federated averaging algorithms that stabilize neural network training while saving communication costs, e.g. CELGC by Liu et al. (2022). Clip21-GD can be modified for these federated learning applications to accelerate the convergence of CELGC by Liu et al. (2022). This is because distributed gradient clipping algorithms can be viewed as a special case of CELGC by Liu et al. (2022) with the number of local steps $I=1$. Also note that the implementation of clipping the average gradient of clients can be viewed as Clip21-GD with the $n=1$ case supported by our theory.

The article's motivation may need further clarity. While it claims to address the importance of deep neural network (DNN) training, the use of gradient descent (GD) in Clip-GD may appear unsuitable for DNNs. While Clip-SGD is briefly mentioned in the appendix for VGG 11 training, its theoretical convergence rate is not thoroughly explored in the main text, leaving room for ambiguity.

We believe that Clip21-GD can be modified to obtain similar convergence guarantees when it uses stochastic gradients. This is because EF21 that inspires Clip21-GD attains the $\mathcal{O}(K^{-1})$ convergence rate when it uses stochastic gradients for nonconvex problems (see Theorem 3 in Appendix D.1 of [L1]). From this theorem, the residual error term of running EF21-SGD decreases when we increase the mini-batch size of stochastic gradients.

However, deriving the result for Clip21-GD with stochastic gradients is non-trivial because of the required condition on the bounded norm of the input vector before clipping. This condition can be proved by the strong bounded noise condition, e.g. $\Vert g - \nabla f(x) \Vert\leq \sigma$ with probability 1 [L2].

[L1] Fatkhullin, Ilyas, Igor Sokolov, Eduard Gorbunov, Zhize Li, and Peter Richtárik. "EF21 with bells & whistles: Practical algorithmic extensions of modern error feedback." arXiv preprint arXiv:2110.03294 (2021).

[L2] Zhang, Bohang, Jikai Jin, Cong Fang, and Liwei Wang. "Improved analysis of clipping algorithms for non-convex optimization." Advances in Neural Information Processing Systems 33 (2020): 15511-15521.

The necessity of a client-side gradient clipping algorithm is not sufficiently explained. The implementation of clipping the average gradient of clients on the server side may seem more straightforward and effective in managing explosive gradients to prevent convergence issues.

We believe that implementing the client-side gradient algorithm is necessary for designing federated algorithms that stabilize neural network training while saving communication costs, e.g. CELGC by Liu et al. (2022). Clip21-GD can be extended for these federated set-ups to further accelerate the convergence of CELGC by Liu et al. (2022). This is because distributed gradient clipping algorithms can be viewed as a special case of CELGC by Liu et al. (2022) with the number of local steps $I=1$. Also note that the implementation of clipping the average gradient of clients can be viewed as Clip21-GD with the $n=1$ case supported by our theory.

The article's disclosure that gradient clipping in Clip21-GD will not work after a specific number of steps ( $K=\mathcal{O}(1/\tau)$) raises questions about the algorithm's practicality and long-term effectiveness. The purpose and usability of Clip21-GD beyond this threshold remain unclear.

Clip21-GD and Clip-GD become classical gradient descent when the clipping threshold $\tau$ is extremely large. In this situation, we cannot expect both gradient clipping methods to outperform classical gradient descent. Furthermore, from Figure 1 and 2, Clip21-GD empirically outperforms Clip-GD, especially when the clipping threshold $\tau$ becomes small. This is because Clip21-GD allows for the clipping to be inactive sooner than Clip-GD. This verifies Proposition 5.2 and 5.5, stating that the step before clipping becomes inactive $K=(1/\tau)(\| \nabla f(x_0) \| - \tau)$ is large as the clipping threshold $\tau$ is small and the initial solution $x_0$ satisfies $\| \nabla f(x_0)\| \gg \tau$.

I appreciate the responses from the author, yet my concerns persist.

1. The extension from Clip21-GD to Clip21-SGD is non-trivial, challenging the claim that Clip21-GD effectively addresses issues in DNN training. This motivation seems overstated.

2. The rationale behind implementing client-side gradient clipping remains unclear. Employing simpler server-side gradient clipping could also potentially achieve training stability, and the benefits of client-side clipping in reducing communication overhead are not clearly demonstrated.

Relevance to Differential Privacy. Element-wise gradient clipping is typically used DP-SGD (Abadi et al, 2016). DP-SGD uses clipping to control the sensitivity of gradient steps. Then DP-SGD adds a Gaussian noise to the clipped gradient to create a Gaussian mechanism. In Alg 1, the clipped vectors are aggregated, but the influence of a noise $\xi_i$ on the mean estimate $\frac{1}{n}\sum_i v_i$ is not studied, therefore it is not clear if this algorithm would work in the context of differential privacy.

Although DP-Clip-SGD for distributed settings (Abadi et al, 2016) has been studied empirically, there is no theoretical convergence for this method. Even without DP noise, distributed Clip-GD does not converge towards the optimum for quadratic problems in Example 1.1. This motivates us to redesign distributed Clip-GD that leverages the error-feedback framework to ensure convergence. Deriving DP guarantees for a version of Clip21-GD is a prominent research direction for future work.

Relevance for exploding gradients. As written in the paper: ``we are not employing clipping as a tool for taming the exploding gradients problem, and our work is fully complementary to this literature. [...] Clipping after averaging does not cause the severe bias and divergence issues we are addressing in our work.”

We agree that clipping helps stabilize neural network training which has exploding gradient problems, which can be modeled by the $(L_0,L_1)$ smoothness condition. We believe that our analysis is sufficient to prove the convergence under the $(L_0, L_1)$ smoothness. We prove this by finding the upper-bound for $\Vert \nabla^2 f(x_k) \Vert$ and our results apply as follows:

1. By the $(L_0, L_1)$ smoothness and Assumption 3 of [A1],

2. We then have $\Vert \nabla^2 f(x_k) \Vert \leq L_0 + L_1 \sqrt{2L\phi_0}$ for all $k \geq 0$ by proving that $f(x_k) \leq f_{\inf}+\phi_0$ by the induction and by setting the step-size $\gamma$ sufficiently small. We also refer the reviewer to our general response, where we explain why the current analysis from our paper holds under $(L_0, L_1)$-smoothness.

[A1]: Khaled, Ahmed, and Peter Richtárik. "Better theory for SGD in the nonconvex world." arXiv preprint arXiv:2002.03329 (2020).

The idea of Algorithm 1 is to estimate the average $\frac{1}{n}\sum_{i=1}a_i$ exactly. Clipping may help to circumvent instabilities when some individual gradients $a_i$ are too high (whetever the reason, exploding gradient being an example, numerical inaccuracies another). In this case, biasing the average direction with clipping is the wanted behavior, since we don't want the descent step to be driven by a single example with exceedingly large gradient norm. The average operator $\bar a := a \mapsto \frac{1}{n}\sum_{i=1}a_i$ is not robust by definition against outliers.

By building an estimator of this average operator $\bar a$, aren't we falling back to the issues the average operator $\frac{1}{n}\sum_{i=1}a_i$ was suffering in the first place?

We agree that this naive averaging operator does not ensure the convergence of distributed clipped gradient methods as in Example 1.1. To this end, we show that this naive averaging can be circumvented by leveraging the error-feedback framework to recover the average of full gradients from the average of memory vectors. In particular, from Lemma 4.2 and 4.3, the Clip21 algorithm ensures the following: (1) each memory vector $v_k^i$ approaches $a^i$ at node $i$, and hence (2) we can obtain $v_k := \frac{1}{n}\sum_{i} v_i^k$ which approaches $a:= \frac{1}{n}\sum_{i} a_i$.

The paper positions itself against the Clip-GD algorithm (among others... ), in all experiments. But experiments with comparison against vanilla GD are lacking.

Can you clarify what are the use-cases in which Clip21-GD overcomes vanilla GD (and not only Clip-GD) ? What makes your algorithm different from vanilla GD in practice? Experiments are lacking to compare against it.

Our theory and experiments suggest that Clip21-GD outperforms the Clip-GD for both deterministic and stochastic gradients since it can handle data heterogeneity and ensures strong convergence guarantees. We believe that Clip21-GD would outperform the naive clipping algorithm, which is faster than vanilla SGD for neural network trainin, e.g., in (Zhang et al.,2020a).

For citations, for example a top of page 5, I recommand to use \citep{} instead of \cite{}, for example in, Richt ´arik et al. (2021); Fatkhullin et al. (2021); Richt ´arik et al. (2022),

it will become “inactive” in at most k⋆ steps (i.e., ∇fi(xk) − vik−1 ≤ τ. Missing $)$.

We thank the reviewer for this recommendation and for spotting this typo. We will correct this in our finalized manuscript.

[L1] Fatkhullin, Ilyas, Igor Sokolov, Eduard Gorbunov, Zhize Li, and Peter Richtárik. "EF21 with bells & whistles: Practical algorithmic extensions of modern error feedback." arXiv preprint arXiv:2110.03294 (2021).

[L2] Zhang, Bohang, Jikai Jin, Cong Fang, and Liwei Wang. "Improved analysis of clipping algorithms for non-convex optimization." Advances in Neural Information Processing Systems 33 (2020): 15511-15521.