Momentum and Error Feedback for Clipping with Fast Rates and Differential Privacy

This paper basically proposes the heavy-ball momentum version of clipped SGD with error feedback (Richtárik et al., 2021); the authors name this algorithm Clip21-SGDM. A version for DP training is also provided (by suitably adding noise to the updates). The paper also shows that standard clipped SGD + error feedback without momentum can fail to converge in some cases. Convergence results of $\mathcal{O}(1/T)$ and $\widetilde{\mathcal{O}}(1/\sqrt{n T})$ are derived for smooth non-convex functions in the deterministic and stochastic cases for Clip21-SGDM -- the good thing about these results is that they don't require any kind of bounded gradient assumption (unlike prior papers). Empirical results verify the theory showing that Clip21-SGDM converges better over a wide range of clipping radii in the non-DP case.

The paper provides a momentum and error feedback based clipping SGD mechanism which can satisfy DP by adding appropriate noise. The authors provide formal proof of convergence of the algorithm in three cases: (i) deterministic case (using exact gradient at each step), (ii) stochastic case (each worker has access to σ-sub-Gaussian unbiased estimator), and (iii) the case where DP noise is added to the clipped term in the stochastic case. The theoretical analysis provides three main results: $O(1/T)$ convergence rate in the deterministic case $O(1/\sqrt{nT})$ high-probability convergence rate in the stochastic case with sub-Gaussian noise Optimal local DP-error bounds when privacy noise is added. The proof of the algorithm doesn't rely on any assumptions regarding the boundedness of gradients or data heterogeneity and only requires Assumption 1 (L-smoothness and lower boundedness) and Assumption 2 (sub-Gaussian property of the stochastic gradients). They provide experiments on nonconvex logistic regression, CIFAR10 with ResNet20 and VGG16, and MNIST dataset with MLP and CNN.

The paper considers the problem of using (DP) federated learning to minimize a non-convex smooth loss using heterogenous clients. Using the standard Clip-SGD algorithm is not guaranteed to converge to a local minimum when one exists, even when clients' gradients are non-stochastic. The Clip21-SGD algorithm instead clips the difference between a current estimate of the client's gradient and its true gradient, and adds this difference to its current estimate to get a new estimate. When clients have non-stochastic gradients Clip21-SGD converges, but the authors give an example which shows that with stochastic gradients Clip21-SGD is not guaranteed to converge. The authors propose a modification of Clip21-SGD called Clip21-SGDM, where each client reports an exponentially weighted average of its gradients so far (i.e., the update it would use if using SGDM), and Clip21-SGDM clips the difference between this average and its current estimate of the average. The authors show that unlike Clip21-SGD, Clip21-SGDM converges (in terms of the squared gradient norm) at the optimal rate of 1/T when gradients are non-stochastic, and at rate $1/T + s/\sqrt{T n}$ when client gradients are s-subGaussian. Finally, the authors show that the algorithm achieves the optimal bound of $\sqrt{d} / \sqrt{n} \epsilon$ under $(\epsilon, \delta)$ local-DP when Gaussian noise is added to the clipped values. Empirically, the authors compare Clip-SGD, Clip21-SGD, and Clip21-SGDM. On logistic regression with a non-convex regularizer, Clip21-SGDM achieves smaller final gradient norm with and without DP. On image recognition tasks of MNIST and CIFAR without DP, it achieves better performance than Clip-SGD and comparable or slightly better performance than Clip21-SGD. With DP, it outperforms Clip21-SGD but is incomparable to Clip-SGD on MNIST tasks.

This paper addresses the challenge of achieving both strong DP and optimization guarantees in Federated Learning. The authors introduce Clip21-SGDM, a new method that combines clipping, heavy-ball momentum, and error feedback to provide optimal convergence rates. Experiments on non-convex logistic regression and neural network training demonstrate that Clip21-SGDM outperforms baseline methods in optimization performance for a given DP budget.

a) Summary

Prior work identified that clipping stochastic gradients introduces bias, which hampers convergence. The authors demonstrate that error feedback, a commonly used approach to address this bias, fails to resolve convergence issues in certain cases. They propose a novel combination of error feedback (EF21) and momentum averaging, showing that this approach effectively overcomes convergence challenges while achieving optimal convergence rates.

b) Strengths

• A new algorithm, Clip21-SGDM, which combines heavy-ball momentum, error feedback (EF21), and gradient clipping to overcome demonstrated convergence limitations. I especially liked that the approach is well motivated, with clear demonstration that previous approaches fail.
• The paper provides rigorous optimal convergence guarantees for the proposed method in non-convex optimization settings, addressing deterministic, stochastic, and DP noise scenarios.

c) Weaknesses

• The privacy analysis in this paper is missing. While the authors define central item-level DP, their approach seems to be motivated by local / user-level DP. The v_^t term uses heavy ball momentum and so has terms involving multiple datapoints. This is unlike SGD. So standard subsampling and sensitivity analysis does not hold. The authors need to carefully perform privacy accounting for their proposed algorithm.
• Lack of intuition: I share Reviewer LwoD's concern. I'm surprised by the fact that convergence can be guaranteed for arbitarily small clipping radii $\tau$. (Theorems 2 and 3). What is preventing us from setting $\tau = 0$?

d) Reason for rejection

While the paper is very intruiging and has promising results, the authors need to address the privacy concerns. Also improved intuitions for their theory would be helpful.

Reject

We would like to emphasize that the updated version of the paper is available on arXiv: https://arxiv.org/abs/2502.11682

The key takeaways are:

• the convergence rate in the deterministic and stochastic cases remains unchanged; we added the explicit dependency on the clipping parameter $\tau$ in these cases.
• we added the second momentum which allows to average DP-noise which is needed to reduce its impact.
• we provide the convergence rate in the stochastic with and without DP noise together; the rate in the stochastic case can be obtained by setting the DP-noise variance $\sigma_{\omega}=0$.
• consequently, we provided corrected DP guarantees. The modified algorithm achieves near-optimal privacy-utility tradeoff