# Clip21: Error Feedback for Gradient Clipping

Sarit Khirirat
Department of Machine Learning
MBZUAI† &Eduard Gorbunov
Department of Machine Learning
MBZUAI &Samuel Horváth
Department of Machine Learning
MBZUAI &Rustem Islamov
Department of Applied Mathematics
Institut Polytechnique de Paris &Fakhri Karray
Department of Machine Learning
MBZUAI &Peter Richtárik
Artificial Intelligence Initiative
KAUST‡

###### Abstract

Motivated by the increasing popularity and importance of large-scale training
under differential privacy (DP) constraints, we study distributed gradient
methods with gradient clipping, i.e., clipping applied to the gradients
computed from local information at the nodes. While gradient clipping is an
essential tool for injecting formal DP guarantees into gradient-based methods
[1], it also induces bias which causes serious convergence issues specific to
the distributed setting. Inspired by recent progress in the error-feedback
literature which is focused on taming the bias/error introduced by
communication compression operators such as Top-$k$ [2], and mathematical
similarities between the clipping operator and contractive compression
operators, we design  Clip21 – the first provably effective and practically
useful error feedback mechanism for distributed methods with gradient
clipping. We prove that our method converges at the same ${\cal
O}(\nicefrac{{1}}{{K}})$ rate as distributed gradient descent in the smooth
nonconvex regime, which improves the previous best ${\cal
O}(\nicefrac{{1}}{{\sqrt{K}}})$ rate which was obtained under significantly
stronger assumptions. Our method converges significantly faster in practice
than competing methods.

###  1 Introduction

Gradient clipping is a popular and versatile tool used in several areas of
machine learning. For example, it is employed to i) enforce bounded $\ell_{2}$
sensitivity in order to obtain formal differentially privacy guarantees in
gradient-based optimization methods [1, 3], ii) tame the exploding gradient
problem in deep learning [4, 5], iii) stabilize convergence of  SGD in the
heavy-tailed noise regime [nazin2019algorithms, gorbunov2020stochastic], and
iv) design provably Byzantine-robust gradient aggregators
[karimireddy2021learning].

####  1.1 The problem

Our work is motivated by the increasing popularity and importance of large-
scale training under differential privacy (DP) constraints [DP-ImageNet-2022,
FL-DP-google-blog-2022]. In particular, we wish to solve the optimization
problem

$\textstyle\min\limits_{x\in\mathbb{R}^{d}}\left[f(x)\coloneqq\frac{1}{n}\sum\limits_{i=1}^{n}f_{i}(x)\right],$
(1)

where $n$ is the number of clients and $f_{i}$ is the loss of a model
parameterized by vector $x\in\mathbb{R}^{d}$ over all private data ${\cal
D}_{i}$ owned by client $i\in[n]\coloneqq\\{1,\dots,n\\}$. We assume each
$f_{i}$ has $L_{i}$-Lipschitz gradient, i.e.,

$\textstyle\left\|\nabla f_{i}(x)-\nabla f_{i}(y)\right\|\leq
L_{i}\left\|x-y\right\|$ (2)

for all $x,y\in\mathbb{R}^{d}$, where $\left\|x\right\|\coloneqq\langle
x,x\rangle^{1/2}$ and $\langle x,y\rangle\coloneqq\sum_{i=1}^{d}x_{i}y_{i}$ is
the standard Euclidean inner product. This implies that $f$ has $L$-Lipschitz
gradient, i.e.,

$\textstyle\left\|\nabla f(x)-\nabla f(y)\right\|\leq L\left\|x-y\right\|$ (3)

for all $x,y\in\mathbb{R}^{d}$, where $L$ satisfies
$L\leq\frac{1}{n}\sum_{i=1}^{n}L_{i}$. Let $L_{\max}\coloneqq\max_{i}L_{i}$.
Moreover, we assume $f$ to be lower bounded by some $f_{\inf}\in\mathbb{R}$.
Note that we do not require any convexity assumptions. Further, we do not
assume $f_{i}$ nor $f$ to be Lipchitz, which is a typical assumption used to
enforce bounded $\ell_{2}$ sensitivity – a crucial property when proving
formal DP guarantees.

####  1.2 Optimization with gradient clipping

Perhaps the simplest DP algorithm for solving (1) in this regime is  DP-Clip-
GD [abadi2016deep, chen2020understanding], performing the iterations

$\textstyle
x_{k+1}=x_{k}-\gamma_{k}\left(\frac{1}{n}\sum\limits_{i=1}^{n}{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{k}))+\zeta_{k}\right),$ (4)

where $\gamma_{k}>0$ is a stepsize, $\zeta_{k}\sim{\cal N}(0,\sigma^{2}I_{d})$
is zero-mean Gaussian noise with variance $\sigma^{2}\geq 0$, and
${\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}:\mathbb{R}^{d}\to\mathbb{R}^{d}$
is the clipping operator with threshold $\tau>0$, defined via

$\textstyle{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(x)\coloneqq\begin{cases}x&\text{if}\quad\left\|x\right\|\leq\tau\\\
\frac{\tau}{\left\|x\right\|}x&\text{if}\quad\left\|x\right\|>\tau\end{cases}.$
(5)

Formal privacy guarantees for algorithm (4) can be found in [abadi2016deep,
Theorem 1]111[abadi2016deep] consider the more general setting with subsampled
gradients $\\{\nabla f_{i}:i\in S_{k}\\}$ for random $S_{k}\subseteq[n]$. .
When $\sigma^{2}=0$, we will refer to this method as  Clip-GD, dropping the DP
designation.

Table 1: Known and our new results for first order methods with clipping. (a) It is not clear if the analysis is correct: https://openreview.net/forum?id=hq7vLjZTJPk. (b) Relies on bounded gradient and gradient similarity assumptions: there exists $G\geq 0$ and $\sigma_{g}\geq 0$ such that $\left\|\nabla f_{i}(x)\right\|^{2}\leq G^{2}$ and $\left\|\nabla f_{i}(x)-\nabla f(x)\right\|^{2}\leq\sigma_{g}^{2}$ for all $x\in\mathbb{R}^{d}$ and all $i\in[n]$. (c) considers local steps for communication efficiency, but these lead to a worse communication efficiency guarantee. (d) $\sigma^{2}$ is the variance of the Gaussian noise. Algorithm |  | Covers
---
$n>1$ Case?
| Nonconvex
---
Rate
| DP
---
Guarantees
| Communication
---
Compression
Comment
| Clip-GD
---
[Zhang2020Why]
✗ | ${\cal O}(\nicefrac{{1}}{{K}})$ | ✗ | — |  |  $(L_{0}^{\prime},L_{1}^{\prime})$-smoothness
---
applies to $n=1$ case only
| CE-FedAvg
---
[zhang2022understanding]
✓ | ${\cal O}(\nicefrac{{1}}{{\sqrt{K}}})$ | ✗ |  ✗ (c) |  | strong assumptions (b)
---
slow rate
| CELGC
---
[liu2022communication]
✓ |  ${\cal O}(\nicefrac{{1}}{{\sqrt{K}}})$ (a) | ✗ | ✗ |  | strong assumptions (b)
---
slow rate
| Clip21-Avg
---
NEW (Alg 1)
✓ |  | ${\cal O}(\max\\{0,1-K\\})$
---
(Thm 4.3)
✗ | ✗ |  | Exact solution in $O(1)$ steps
---
Solves average estimation
| Clip21-GD
---
NEW (Alg 2)
✓ |  | ${\cal O}(\nicefrac{{1}}{{K}})$
---
(Thm 5.6)
✗ | ✗ |  | Fast  GD-like rate
---
under $L$-smoothness
| DP-Clip21-GD
---
NEW (Alg 3)
✓ |  |  ${\cal O}(e^{-K}+\frac{\ln(1/\delta)}{\epsilon})$ (d)
---
(Thm M.1)
✓ | ✗ |  | Linear rate up to ${\cal O}(\sigma^{2})$ distance
---
of optimum under PŁ assumption
| Press-Clip21-GD
---
NEW (Alg 4)
✓ |  | ${\cal O}(\nicefrac{{1}}{{K}})$
---
(Thm Q.1)
✗ | ✓ |  | Fast  GD-like rate
---
under $L$-smoothness

####  1.3 Convergence of  Clip-GD in the $n=1$ case

In the $n=1$ case,  Clip-GD was studied by [Zhang2020Why], where it was shown
that, under our assumptions222[Zhang2020Why] need to additionally assume $f$
to be twice continuously differentiable., and for suitable stepsizes,

$\textstyle\left\|\nabla
f(x_{K})\right\|^{2}\leq\frac{20L(f(x_{0})-f_{\inf})}{K}.$

This is the same rate as that of vanilla  GD, i.e., the clipping bias does not
cause any convergence issues in the $n=1$ regime. [Zhang2020Why] did not
consider the distributed ($n>1$) regime since their work was motivated by
orthogonal considerations to ours: instead of tackling the issue of clipping
bias inherent to the distributed regime, as we do, they set out to explain the
efficacy of clipping as a tool for convergence stabilization of  GD for
functions with rapidly growing gradients (this issue exists even in the single
node regime). To model functions with rapidly growing gradients, they consider
the $(L^{\prime}_{0},L^{\prime}_{1})$-smoothness assumption, which requires
the bound $\left\|\nabla^{2}f(x)\right\|\leq
L^{\prime}_{0}+L^{\prime}_{1}\left\|\nabla f(x)\right\|$ to hold for all
$x\in\mathbb{R}^{d}$. For twice continuously differentiable functions, this
assumption specializes to ours by setting $L^{\prime}_{0}=L=L_{1}$ and
$L^{\prime}_{1}=0$.

####  1.4 Divergence of  Clip-GD in the $n>1$ case

Surprisingly little is known about the convergence properties of  Clip-GD in
the $n>1$ case. The key reason behind this is the poor quality of

$\textstyle
g(x)\coloneqq\frac{1}{n}\sum\limits_{i=1}^{n}{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x))$ (6)

as an estimator of $\nabla f(x)$. This issue does not arise in the $n=1$ case
since clipped gradient retains the directional information of the original
gradient and all that is lost is just some of the scaling information, which
is in the light of the results of [Zhang2020Why] described above is not
problematic. However, the situation is more complicated in the $n>1$ case as
illustrated in the following example.

######  Example 1.1.

Let $d=1$, $n=2$ with $f_{1}(x)=\frac{\beta}{2}x^{2}$ and
$f_{2}(x)=-\frac{\alpha}{2}x^{2}$, where $\beta>\alpha\geq\tau>0$ and $x>0$.
Both of these functions have Lipschitz gradients, and $f$ has
$(\beta-\alpha)$-Lipschitz gradient. Moreover,
$f(x)=\frac{\beta-\alpha}{2}x^{2}$ is lower bounded below by $f_{\inf}=0$. So,
this setup satisfies our assumptions. Notice that while the gradient is equal
to $\nabla f(x)=\frac{1}{2}\nabla f_{1}(x)+\frac{1}{2}\nabla f_{1}(x)=\beta
x-\alpha x=(\beta-\alpha)x$, the gradient estimator (6) gives
$g(x)=\frac{1}{2}{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{1}(x))+\frac{1}{2}{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{2}(x))=\min\\{1,\frac{\tau}{|\beta x|}\\}\beta
x+\min\\{1,\frac{\tau}{|-\alpha x|}\\}(-\alpha x)=\tau-\tau=0$ whenever
$x\geq\frac{\tau}{\alpha}$. This means that  Clip-GD will not progress at all
if initialized with $x_{0}\geq\frac{\tau}{\alpha}$. For example, if we choose
$x_{0}=\frac{\tau}{\alpha}$, then both the function value
$f(x_{0})=\frac{\beta-\alpha}{2}\frac{\tau^{2}}{\alpha^{2}}$ and the gradient
$\nabla f(x_{0})=(\beta-\alpha)\frac{\tau}{\alpha}$ can be arbitrarily large
(by fixing $\tau$ and $\alpha$, and increasing $\beta$), while the optimal
value and gradient of $f$ are both zero.

As the above example illustrates,  Clip-GD is a fundamentally flawed method in
the $n>1$ case, unable to converge from many starting points to any finite
degree of accuracy, however weak accuracy requirements we may have! This is
true for any class of functions which includes the above example, and hence it
is true for the class of functions we consider in this paper: lower bounded,
with Lipschitz gradient.

###  2 Summary of Contributions

In the light of the above discussion, there are at least three ways forward:
i) consider a different algorithm, ii) consider a different function class, or
iii) change both the algorithm and the function class. In our work we explore
the first of these three possible approaches: we design a new way of combining
clipping and gradient descent – one that does not suffer from any convergence
issues.

####  2.1  Clip21-Avg: Error feedback for average estimation with clipping

As a first step in our process of discovery of a fix for the bias caused by
the clipping estimator (6) in the estimation of the gradient, we first study a
simplified setting void of any optimization aspect, thus removing one source
of dynamics, which greatly simplifies the situation. In particular, we study
the problem of the estimation of the average of a number of fixed vectors
$a^{1},\dots,a^{n}\in\mathbb{R}^{d}$ via repeated use of clipping. We then
propose an error feedback mechanism for this task, leading to method
Clip21-Avg (see Algorithm 1), and prove that our method finds the exact
average in

$K={\cal O}(\nicefrac{{1}}{{\tau}})$

iterations (see Theorem 4.3). As a corollary, if $\tau$ is sufficiently large,
then  Clip21-Avg finds the exact average in a single iteration, which is to be
expected from any reasonable mechanism. In particular,  Clip21-Avg maintains a
collection of auxiliary iterates $v_{k}^{1},\dots,v_{k}^{n}$ used to estimate
the vectors $a^{1},\dots,a^{n}$ which we evolve via the rule

$\textstyle
v_{k}^{i}=v_{k-1}^{i}+{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(a^{i}-v_{k-1}^{i}),\quad
i\in[n].$ (7)

The average of the vectors is then estimated by
$v_{k}\coloneqq\frac{1}{n}\sum_{i=1}^{n}v_{k}^{i}\approx\frac{1}{n}\sum_{i=1}^{n}a^{i}$.

####  2.2  Clip21-GD: Error feedback for  GD with clipping

Having solved the simpler task of average estimation, we now use similar ideas
to design an error feedback mechanism for fixing the bias caused by clipping
in an optimization setting for solving problem (1). In particular, we propose
to estimate the average of the gradients $\nabla f_{i}(x^{k}),\dots,\nabla
f_{n}(x^{k})$ by the output of a single iteration of  Clip21-Avg, i.e., by
$v_{k}=\frac{1}{n}\sum_{i=1}^{n}v_{k}^{i}$, where

$\textstyle
v_{k}^{i}=v_{k-1}^{i}+{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{k})-v_{k-1}^{i}),\quad i\in[n],$ (8)

and use this estimator in lieu of the true gradient to progress in our
optimization task: $x_{k+1}=x_{k}-\gamma v_{k}.$ This approach leads to the
main method of this paper:  Clip21-GD (see Algorithm 2). The re-introduction
of gradient dynamics into the picture causes considerable issues in that our
analysis can not rely on the arguments used to analyze  Clip21-Avg. Indeed,
while the vectors $a^{1},\dots,a^{n}$ whose average we are trying to estimate
in  Clip21-Avg remain static throughout the iterations of  Clip21-Avg, in
Clip21-GD they change after every step. Analyzing the combined dynamics of two
these methods turned out challenging, but ultimately possible, and the result
is satisfying. In particular, in Theorem 5.6 we prove that  Clip21-GD enjoys
the same rate as vanilla  GD; that is, our method outputs a (random) point
$\hat{x}_{K}$ such that

$\mathbf{E}\left[\left\|\nabla f(\hat{x}_{K})\right\|^{2}\right]\leq{\cal
O}(\nicefrac{{1}}{{K}}).$

Our main result can be found in Section 5; see also Table 1. Next, the closest
competing method to ours is that of [zhang2022understanding], which studies
the convergence of a clip-enabled variant of the  FedAvg algorithm, called
CE-FedAvg, under the additional assumptions that there exists $G\geq 0$ and
$\sigma_{g}\geq 0$ such that $\left\|\nabla f_{i}(x)\right\|^{2}\leq G^{2}$
and $\left\|\nabla f_{i}(x)-\nabla f(x)\right\|^{2}\leq\sigma_{g}^{2}$ for all
$x\in\mathbb{R}^{d}$ and all $i\in[n]$. Given the discussion from the
beginning of Section 2, their work can thus be seen as embarking on approach
ii) towards taming the divergence issues associated with applying gradient
clipping in the $n>1$ case. We wish to note that these additional assumptions
are rather strong. First, it is unclear why gradient clipping is required in
the regime when the gradients are already bounded. Second, the function
similarity assumption typically does not hold in practice [localSGD-
AISTATS2020, richtarik2021ef21]. Finally, none of these assumptions hold even
for convex quadratics. Even with these additional and arguably strong
assumptions, [zhang2022understanding] in their Theorem 3.1 establish a result
of the form

$\textstyle\left\|\nabla f(\hat{x}_{K})\right\|^{2}\leq{\cal
O}(\nicefrac{{1}}{{\sqrt{K}}}),$

which is weaker than the ${\cal O}(\nicefrac{{1}}{{K}})$ rate we achieve.

####  2.3 Extension 1: Adding noise for DP guarantees

We add bounded Gaussian noise to  Clip21-GD, which leads to the new method
DP-Clip21-GD (see Algorithm 3), and prove convergence with privacy guarantees
for solving nonconvex problems under the PŁ condition. The results can be
found in Appendix L.

####  2.4 Extension 2: Adding communication compression for increased
communication efficiency

We extend  Clip21-GD to communication-efficient learning applications. We call
this method  Press-Clip21-GD where each node compresses the clipped vector
before it communicates. The description and convergence theorem of  Press-
Clip21-GD are provided in Appendix Q.

####  2.5 Experiments

Our experiments on regression and deep learning problems suggest that
Clip21-GD and  DP-Clip21-GD substantially outperform  Clip-GD and its DP
variants. See Section 6.

###  3 Related Work

As we shall outline next, our work is complementary to the existing literature
on methods utilizing the clipping operator for solving various problems.

####  3.1 Relation to literature on exploding gradients

Gradient clipping and normalization were studied in early subgradient
optimization literature by [Shor1985] and [Ermoliev1988], among others, as
techniques for enforcing convergence when minimizing rapidly growing (i.e.,
non-Lipschitz) functions. In contrast to this and also more recent literature
on this topic [pascanu2013difficulty, goodfellow2016deep, Zhang2020Why,
mai2021stability], we assume $L$-Lipschitzness of the gradient. This is
because the issue we are trying to overcome in our work exists even in this
more restrictive regime. In other words, we are not employing clipping as a
tool for taming the exploding gradients problem, and our work is fully
complementary to this literature. Citing [abadi2016deep], “gradient clipping
of this form is a popular ingredient of  SGD for deep networks for non-privacy
reasons, though in that setting it usually suffices to clip after averaging.”
Clipping after averaging does not cause the severe bias and divergence issues
we are addressing in our work.

####  3.2 Relation to literature on heavy-tailed noise

In contrast to the literature on using clipping to tame stochastic gradient
estimators with a heavy-tailed behavior [nazin2019algorithms,
zhang2020adaptive, gorbunov2020stochastic, gorbunov2021near,
cutkosky2021high], we do not consider the heavy-tailed setup in our work. In
fact, our key methods and results are fully meaningful in the deterministic
gradient regime, which is why we focus on it in much of the paper.

####  3.3 Relation to literature on Byzantine robustness

In our work we do not consider the Byzantine setup and instead focus on
standard distributed optimization with nodes whose outputs can be trusted.
However, there is a certain similarity between our  Clip21-Avg method and the
centered clipping mechanism employed by [karimireddy2021learning] to obtain a
Byzantine-robust estimator of the gradient. We shall comment on this in
Appendix A.

####  3.4 Relation to literature on error feedback

Error feedback ( EF), originally proposed by [seide20141], is a popular
mechanism for stabilizing optimization methods that use compressed gradients
to reduce communication costs. Variants of  EF methods were originally
analyzed by [alistarh2018convergence, stich2018sparsified, wu2018error] and
later refined by [tang2019doublesqueeze, karimireddy2019error, stich2020error,
qian2021error, khirirat2020compressed]. The current best results can be found
in [gorbunov2020linearly, qian2021error]. However, these methods were analyzed
either in the single-node setting, or homogeneous data setting, or otherwise
suffer from restrictive assumptions (e.g., bounded gradient-norm and bounded
data dissimilarity conditions) and not fully satisfying rates (e.g., ${\cal
O}(\nicefrac{{1}}{{K^{2/3}}})$ in the nonconvex regime). To address these
problems, a new error-feedback mechnism called  EF21 was proposed by
[richtarik2021ef21], and shown to provide fast ${\cal O}(\nicefrac{{1}}{{K}})$
convergence for distributed optimization over smooth, heterogeneous objective
functions [richtarik2021ef21, EF21BW, richtarik20223pc], under weak
assumptions. Our algorithmic approach behind  Clip21-GD is inspired by the
error feedback mechanism  EF21 of [richtarik2021ef21] proposed in the context
of distributed optimization with contractive communication compression, but
needs a different theoretical approach due to a difference between the
properties of the clipping and compression operators which necessitates a
substantially more refined and involved analysis. We shall comment on this in
more detail in Section 5.

###  4 Error Feedback for Average Estimation with Clipping

Algorithm 1 Clip21-Avg (Error Feedback for Average Estimation with Clipping)

1: Input: initial shifts $v^{1}_{-1},\dots,v^{n}_{-1}\in\mathbb{R}^{d}$;
clipping threshold $\tau>0$

2: for $k=0,1,2,\dots,K-1$ do

3: for each worker $i=1,\ldots,n$ in parallel do

4:
$v^{i}_{k}=v^{i}_{k-1}+{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(a^{i}-v^{i}_{k-1})$

5: end for

6: $v_{k}=\frac{1}{n}\sum_{i=1}^{n}v^{i}_{k}$ $\diamond$ estimate of
$a\coloneqq\frac{1}{n}\sum_{i}a^{i}$

7: end for

We shall now describe the properties of our  Clip21-Avg method (Algorithm 1)
for finding the average of $n$ vectors, $a^{1},\dots,a^{n}\in\mathbb{R}^{d}$.

####  4.1 Basic properties of the clipping operator

It is easy to verify that
${\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color<EMAIL_ADDRESS>is the projection operator onto the ball ${\cal
B}(0,\tau)\coloneqq\\{x:\left\|x\right\|\leq\tau\\}$, and that is satisfies
the properties in the next lemma.

######  Lemma 4.1.

The clipping operator
${\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}:\mathbb{R}^{d}\to\mathbb{R}^{d}$
has the following properties for all $\tau>0$:

  * (i)

${\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\gamma\tau}(x)=\gamma{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}\left(\nicefrac{{x}}{{\gamma}}\right)$
for all $x\in\mathbb{R}^{d}$ and $\gamma>0$,

  * (ii)

$\left\|{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(x)-x\right\|=0$
if $\left\|x\right\|\leq\tau$,

  * (iii)

$\left\|{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(x)-x\right\|=\left\|x\right\|-\tau$
if $\left\|x\right\|\geq\tau$,

  * (iv)

$\left\|{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(x)-x\right\|^{2}=\left(1-\nicefrac{{\tau}}{{\left\|x\right\|}}\right)^{2}\left\|x\right\|^{2}$
if $\left\|x\right\|\geq\tau$.

We will use parts (ii)-(iii) of this lemma in the rest of this section. Part
(iv) will be useful in Section 5.

####  4.2 Estimating $a^{i}$

We now analyze Step 3 of Algorithm 1 (i.e., (7)). As we shall see, $v^{i}_{k}$
converges to $a^{i}$ exactly in a finite # of steps.

######  Lemma 4.2.

For all iterates $k\geq 0$ of Algorithm 1,

$\textstyle\left\|v^{i}_{k}-a^{i}\right\|\leq\max\left\\{0,\left\|v^{i}_{-1}-a^{i}\right\|-(k+1)\tau\right\\},\forall
i.$ (9)

In particular, if $\left\|v^{i}_{-1}-a^{i}\right\|\leq\tau$, then
$v^{i}_{0}=a^{i}$. Otherwise, if
$k\geq\left\lceil\frac{1}{\tau}\left\|v^{i}_{-1}-a^{i}\right\|-1\right\rceil$,
then $v^{i}_{k}=a^{i}$.

####  4.3 Estimating $a\coloneqq\frac{1}{n}\sum_{i=1}^{n}a^{i}$

A convergence result for $v_{k}\to a$ follows by applying Lemma 4.2 for all
$i\in[n]$ and using convexity of the norm.

######  Theorem 4.3.

For all iterates $k\geq 0$ of Algorithm 1,

$\textstyle\left\|v_{k}-a\right\|\leq\frac{1}{n}\sum\limits_{i=1}^{n}\max\left\\{0,\left\|v^{i}_{-1}-a^{i}\right\|-(k+1)\tau\right\\}.$

In particular, if $\left\|v^{i}_{-1}-a^{i}\right\|\leq\tau$ for all $i$, then
$v_{0}=a$. Otherwise, if
$k\geq\max_{i}\left\lceil\frac{1}{\tau}\left\|v^{i}_{-1}-a^{i}\right\|-1\right\rceil$,
then $v_{k}=a$.

###  5 Error Feedback for Distributed Optimization with Clipping

Algorithm 2 Clip21-GD (Error Feedback for Distributed Optimization with
Clipping)

1: Input: initial iterate $x_{0}\in\mathbb{R}^{d}$; learning rate $\gamma>0$;
initial gradient shifts $v^{1}_{-1},\dots,v^{n}_{-1}\in\mathbb{R}^{d}$;
clipping threshold $\tau>0$

2: for $k=0,1,2,\dots,K-1$ do

3: Broadcast $x_{k}$ to all workers

4: for each worker $i=1,\ldots,n$ in parallel do

5: Compute
$g_{k}^{i}={\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{k})-v^{i}_{k-1})$

6: Update $v^{i}_{k}=v^{i}_{k-1}+g_{k}^{i}$

7: end for

8: $v_{k}=v_{k-1}+\frac{1}{n}\sum_{i=1}^{n}g_{k}^{i}$

9: $x_{k+1}=x_{k}-\gamma\frac{1}{n}\sum_{i=1}^{n}v^{i}_{k}$

10: end for

The design of our new method  Clip21-GD (Algorithm 2) is inspired by the
current state-of-the-art error feedback mechanism called  EF21 developed by
[richtarik2021ef21] (see [EF21BW, richtarik20223pc] for extensions) the goal
of which is to progressively remove the error introduced by a contractive
compression operator applied to the gradients333This is why use the number 21
in the name  Clip21.. A contractive operator is a possibly randomized mapping
${\cal C}:\mathbb{R}^{d}\to\mathbb{R}^{d}$ satisfying

$\textstyle\mathbf{E}\left[\left\|{\cal
C}(x)-x\right\|^{2}\right]\leq(1-\alpha)\left\|x\right\|^{2},\quad\forall
x\in\mathbb{R}^{d}$ (10)

for some $0<\alpha\leq 1$. However, the results of [richtarik2021ef21] do not
apply to our setup since the clipping operator is not contractive in the sense
of (10). Our idea is to instead rely on the related identity

$\textstyle\left\|{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(x)-x\right\|^{2}=\begin{cases}0&\text{if
}\left\|x\right\|\leq\tau\\\
\left(1-\frac{\tau}{\left\|x\right\|}\right)^{2}\left\|x\right\|^{2}&\text{if
}\left\|x\right\|\geq\tau\end{cases}$

established in Lemma 4.1. Using this identity in lieu of (10) is more
complicated since the contraction factor can be arbitrarily if
$\left\|x\right\|$ is large. We needed to develop a new analysis technique to
handle this situation.

In the rest of this section we describe the strong theoretical properties of
Clip21-GD (Algorithm 2).

####  5.1 Single-node regime ($n=1$)

We begin by studying  Clip21-GD in the single-node case. For simplicity, in
the subsequent text and statements, we drop the superscript $i$ from all
iterates.

In the light of the discussion from Section 1.3, in this case our error
feedback mechanism for clipping is not needed; that is,  Clip-GD suffices, and
there is no need for  Clip21-GD. However, one would hope that our approach
offers comparable guarantees in this case to those obtained by [Zhang2020Why]
in the $L$-smooth regime; i.e., we expect to obtain a ${\cal
O}(\nicefrac{{1}}{{K}})$ rate. The key purpose of this section is to see that
this is indeed the case. However, we believe that  Clip21-GD is needed even in
the $n=1$ case if one wants to obtain results in the more general constrained
or proximal regime444We believe such results can be obtained by using the
techniques developed by [EF21BW]., and hence the results of this section can
serve as a basis for further exploration and extensions.

Our first result establishes a descent lemma for a certain Lyapunov function.
This is a substantial departure from existing analyses of clipping methods
which do not make use of the control variate sequence $\\{v_{k}\\}$.

######  Lemma 5.1 (Descent lemma).

Consider the problem of minimizing $f:\mathbb{R}^{d}\to\mathbb{R}$, assuming
it has $L$-Lipschitz gradient and lower bounded by $f_{\rm inf}\in\mathbb{R}$.
Let $v_{-1}=0\in\mathbb{R}^{d}$,
$\eta\coloneqq\min\left\\{1,\frac{\tau}{\|\nabla f(x_{0})\|}\right\\}$,
$F_{0}\coloneqq f(x_{0})-f_{\rm inf}$, and $G_{0}\coloneqq|\left\|\nabla
f(x_{0})\right\|-\tau|$. Then, single-node  Clip21-GD (described in Algorithm
2 with $n=1$) with stepsize

$\displaystyle\textstyle\gamma\leq\frac{1}{L}\min\left\\{\frac{1-1/\sqrt{2}}{1+\sqrt{1+2\beta_{1}}},\frac{\tau^{2}}{4L\left[\sqrt{F_{0}}+\sqrt{\beta_{2}}\right]^{2}}\right\\},$
(11)

where $\beta_{1}\coloneqq\frac{(1-\eta)^{2}(1+2/\eta)}{1-(1-\eta)(1-\eta/2)}$
and $\beta_{2}\coloneqq F_{0}+\frac{\tau G_{0}}{\sqrt{2\eta}L}$, satisfies

$\displaystyle\textstyle\phi_{k+1}\leq\phi_{k}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2},$ (12)

where $\phi_{k}\coloneqq f(x_{k})-f_{\rm inf}+A\left\|\nabla
f(x_{k})-v_{k}\right\|^{2}$ and
$A\coloneqq\frac{\gamma}{2[1-(1-\eta)(1-\eta/2)]}$.

Inequality (12) states that the Lyapunov function $\phi_{k}$ decreases in each
iteration by an amount proportional to the squared norm of the gradient,
regardless of whether the clipping operator is active or not. We next prove
the state of the clipping operator when the algorithm is run. Our next result
states that if the clipping operator is “active” at the start (i.e., $\|\nabla
f(x_{0})\|>\tau$), it will become “inactive” (i.e., it will act as the
identity mapping) after at most ${\cal O}(\nicefrac{{\left\|\nabla
f(x_{0})\right\|}}{{\tau}})$ iterations, and then stay inactive from then on.

######  Proposition 5.2 (Finite-time to no clipping).

Let the conditions of Lemma 5.1 hold.

  * (i)

On the one hand, if $x_{0}$ satisfies $\|\nabla f(x_{0})\|\leq\tau$, then
$\|\nabla f(x_{k})-v_{k-1}\|\leq\tau$ for all $k\geq 0$. That is, the clipping
operator is inactive for all iterations.

  * (ii)

On the other hand, if $x_{0}$ satisfies $\|\nabla f(x_{0})\|>\tau$, then
$\|\nabla f(x_{k})-v_{k-1}\|\leq\tau$ for $k\geq
k^{\star}\coloneqq\frac{2}{\tau}\left(\|\nabla f(x_{0})\|-\tau\right)+1$. That
is, the clipping operator becomes inactive after at most $k^{\star}={\cal
O}(\nicefrac{{1}}{{\tau}})$ iterations.

Note that when clipping becomes inactive, then
$v_{k}=v_{k-1}+{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f(x_{k})-v_{k-1})=\nabla f(x_{k})$, which means that  Clip21-GD turns into  GD
after at most $k^{\star}$ iterations. Finally, Lemma 5.1 and Proposition 5.2
lead to our main convergence result.

######  Theorem 5.3 (Convergence result).

Consider single-node  Clip21-GD (described in Algorithm 2 with $n=1$). Let the
conditions of Lemma 5.1 hold and let $\hat{x}_{K}$ be a point selected from
the set $\\{x_{0},x_{1},\ldots,x_{K-1}\\}$ for $K\geq 1$ uniformly at random.
Then

$\displaystyle\textstyle\mathbf{E}\left[\|\nabla
f(\hat{x}_{K})\|^{2}\right]\leq\frac{2}{\gamma}\frac{\phi_{0}}{K}.$

If $\gamma$ is chosen to be the right-hand side of (11), then for
$C\coloneqq\max\left\\{LF_{0},\left\|\nabla f(x_{0})\right\|^{2}\right\\}$,

$\displaystyle\textstyle\mathbf{E}\left[\|\nabla
f(\hat{x}_{K})\|^{2}\right]={\cal O}\left(\left[\frac{C(\left\|\nabla
f(x_{0})\right\|+\tau)}{\tau}+\frac{L^{2}(F_{0})^{2}}{\tau^{2}}\right]\frac{1}{K}\right).$

Theorem 5.3 states that in the $L$-smooth non-convex regime, single-node
Clip21-GD enjoys the $\mathcal{O}(\nicefrac{{1}}{{K}})$ rate. Up to constant
factors, this is the same rate as that of  GD.

####  5.2 Multi-node regime ($n>1$)

Next, we turn our attention to multi-node  Clip21-GD as described in Algorithm
2. Note that this method becomes  EF21 when we replace
${\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\cdot)$
with a contractive compressor, and becomes  GD when we let $\tau\to+\infty$.
Our results for multi-node  Clip21-GD have the same meaning as those for the
single-node case, and hence a commentary comparing these results to the $n=1$
case should suffice.

######  Lemma 5.4 (Descent lemma).

Consider multi-node  Clip21-GD (described in Algorithm 2 for general $n$) for
solving (1). Suppose that each $f_{i}(x)$ has $L_{i}$-Lipschitz gradient and
that $f$ has $L$-Lipschitz gradient and lower bounded by $f_{\rm
inf}\in\mathbb{R}$. Let $v_{-1}^{i}=0$ for all $i$,
$\eta\coloneqq\min\left\\{1,\frac{\tau}{\max_{i}\left\|\nabla
f_{i}(x_{0})\right\|}\right\\}$, $F_{0}\coloneqq f(x_{0})-f_{\rm inf}$, and
$G_{0}^{2}\coloneqq\frac{1}{n}\sum_{i=1}^{n}(\left\|\nabla
f_{i}(x_{0})\right\|-\tau)^{2}$, with stepsize

$\displaystyle\textstyle\gamma\leq\min\left\\{\frac{\phi_{0}}{(B-\tau)^{2}},\frac{\nicefrac{{(1-1/\sqrt{2})}}{{L}}}{1+\sqrt{1+2\beta_{1}}},\frac{\nicefrac{{\tau^{2}}}{{L_{\max}^{2}}}}{16\left[\sqrt{F_{0}}+\sqrt{\beta_{2}}\right]^{2}}\right\\},$
(13)

where $\beta_{1}\coloneqq
2\frac{(1-\eta)^{2}(1+2/\eta)}{1-(1-\eta)(1-\eta/2)}\left(\nicefrac{{L_{\max}}}{{L}}\right)^{2}$
and $\beta_{2}\coloneqq F_{0}+\frac{G_{0}\tau}{2\sqrt{2\eta}L_{\max}}$. Then,

$\displaystyle\textstyle\phi_{k+1}\leq\phi_{k}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2},$ (14)

where $\textstyle\phi_{k}\coloneqq f(x_{k})-f_{\rm
inf}+\frac{A}{n}\sum\limits_{i=1}^{n}\left\|\nabla
f_{i}(x_{k})-v_{k}^{i}\right\|^{2}$ and
$A\coloneqq\frac{\gamma}{2[1-(1-\eta)(1-\eta/2)]}$.

######  Proposition 5.5 (Finite-time to no clipping).

Let the conditions of Lemma 5.4 hold. On the one hand, if $x_{0}$ satisfies
$\|\nabla f_{i}(x_{0})\|\leq\tau$, then $\|\nabla
f_{i}(x_{k})-v^{i}_{k-1}\|\leq\tau$ for all $k\geq 0$. On the other hand, if
$x_{0}$ satisfies $\|\nabla f_{i}(x_{0})\|>\tau$, then $\|\nabla
f_{i}(x_{k})-v^{i}_{k-1}\|\leq\tau$ for $k\geq
k^{\star}\coloneqq\frac{2}{\tau}\left(\|\nabla f_{i}(x_{0})\|-\tau\right)+1$.

######  Theorem 5.6 (Convergence result).

Let the conditions of Lemma 5.4 hold, and $\hat{x}_{K}$ be a point selected
from the set $\\{x_{0},x_{1},\ldots,x_{K}\\}$ uniformly at random for $K\geq
1$. Then, multi-node  Clip21-GD (described in Algorithm 2) satisfies

$\displaystyle\textstyle\mathbf{E}\left[\left\|\nabla
f(\hat{x}_{K})\right\|^{2}\right]\leq\frac{2}{\gamma}\frac{\phi_{0}}{K}.$

If $\gamma$ is chosen to be the right-hand side of (13), then

$\displaystyle\textstyle\mathbf{E}\left[\left\|\nabla
f(\hat{x}_{K})\right\|^{2}\right]={\cal
O}\left(\left[\left(1+\frac{C_{1}}{\tau}\right)C_{2}+\frac{L_{\max}^{2}(F_{0})^{2}}{\tau^{2}}\right]\frac{1}{K}\right),$

where $C_{1}\coloneqq\max_{i}\left\|\nabla f_{i}(x_{0})\right\|$,
$C_{2}\coloneqq\max\\{F_{0}\max(L,L_{\max}),C_{1}^{2}\\}$.

Theorem 5.6 says that  Clip21-GD enjoys an ${\cal O}(\nicefrac{{1}}{{K}})$
rate, which is faster than the previous state-of-the-art rate ${\cal
O}(\nicefrac{{1}}{{\sqrt{K}}})$ rate obtained by [zhang2022understanding,
liu2022communication] on nonconvex problems. Also, we do not require bounded
gradient and function similarity assumptions as they do (see Table 1).
Furthermore, Proposition 5.5 says that if the clipping operator at each node
is “active” at the start (i.e., $\left\|\nabla f_{i}(x_{0})\right\|>\tau$), it
will become “inactive” in at most $k^{\star}$ steps (i.e., $\left\|\nabla
f_{i}(x_{k})-v^{i}_{k-1}\right\|\leq\tau$, and  Clip21-GD will effectively
become  GD. Moreover, when specializing our multi-node theory for  Clip21-GD
to the $n=1$ case, and compare this to the theory from Section 5.1, we pay the
price of a smaller maximum stepsize by a factor of $\approx 10$. We comment
more on this in Appendix C.

####  5.3 Adding DP noise

To train the model under the privacy budget, we further add bounded Gaussian
noise $z^{i}_{k-1}$ to clipped gradients
${\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{k})-v_{k-1}^{i})$ before it is transmitted. This modified  Clip21-GD
method, called  DP-Clip21-GD, achieves the linear rate with residual error due
to the DP-noise for nonconvex problems under the PŁ condition. The results can
be found in Appendix L.

####  5.4 Adding communication compression

In order to reduce the communication cost, we further modify  Clip21-GD by
replacing
${\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{k})-v_{k-1}^{i})$ with ${\cal
C}({\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{k})-v_{k-1}^{i}))$, where ${\cal C}:\mathbb{R}^{d}\to\mathbb{R}^{d}$
is a contractive compressor. This method, which we call  Press-Clip21-GD, is
shown to enjoy the $\mathcal{O}(\nicefrac{{1}}{{K}})$ rate as well. The method
and theory are relegated to Appendix Q.

###  6 Experiments

---
|  |
(a) madelon | (b) w7a | (c) w8a
Figure 1: Comparison of  Clip21-GD vs  Clip-GD with clipping threshold
$\tau\in\\{0.01,0.1,1\\}$ on logistic regression with $\ell_{2}$-regularizer
(first line) and a nonconvex regularizer (second line).

To demonstrate strong performance of  Clip21-GD and  DP-Clip21-GD over
traditional clipped gradient methods, we evaluate all the methods on the
logistic regression problem, i.e. the problem of minimizing

$f(x)\coloneqq\frac{1}{n}\sum\limits_{i=1}^{n}f_{i}(x)+\lambda r(x),$

where

$f_{i}(x)\coloneqq\frac{1}{m}\sum\limits_{j=1}^{m}\log(1+e^{-b_{ij}a_{ij}^{\top}x}),$

$a_{ij}\in\mathbb{R}^{d}$ is the $j^{\text{th}}$ training sample associated
with class label $b_{ij}\in\\{-1,1\\}$, which is privately known by node $i$.
Additional experiments on nonconvex linear regression and deep neural network
training are deferred to Section B. We use datasets from the LibSVM library
[chang2011libsvm], and two types of regularization:

  * (1)

$r(x)=\frac{1}{2}\|x\|^{2}$, which is the $\ell_{2}$-regularizer, and

  * (2)

$r(x)=\sum_{j=1}^{d}{x_{j}^{2}}/{(1+x_{j}^{2})}$, which is a nonconvex
regularizer.

Before running the algorithms, we preprocess each dataset as follows: we $(i)$
sort the training samples according to the labels; $(ii)$ split the dataset
into $n$ equal parts among the nodes; and $(iii)$ normalize each sample of
each part by using StandardScaler from the scikit-learn library [scikit-
learn]. By this preprocessing, the problem becomes more heterogeneous while
the Lipschitz constants of functions $\nabla f_{i}$ are closer to each other.
We reported the best convergence performance of the baseline  Clip-GD and
Clip21-GD by choosing stepsizes
$\gamma\in\\{\nicefrac{{1}}{{4L}},\nicefrac{{1}}{{2L}},\dots,\nicefrac{{8}}{{L}}\\}$.
We also set $n=10$; $\lambda=10^{-1}$ and $\lambda=10^{-4}$ for nonconvex and
$\ell_{2}$ regularizers respectively.

####  6.1 Performance of  Clip21-GD and  Clip-GD

Figure 1 shows that  Clip21-GD outperforms  Clip-GD in both the convergence
speed and solution accuracy. This happens because when the clipping operator
is turned on at the beginning, it will be turned off in  Clip-GD with required
iteration counts $k$ much larger than in  Clip21-GD for small values of
$\tau$. For $\tau\in\\{0.01,0.1\\}$,  Clip-GD converges towards the
neighborhood while  Clip21-GD always converges towards the stationary point.
At iteration $k=10^{4}$ and for $\tau=0.01$,  Clip21-GD achieves roughly $6$
times more accurate solution than  Clip-GD for the madelon and w7a datasets.

####  6.2 Performance of  DP-Clip21-GD and  DP-Clip-GD

We next showcase that  DP-Clip21-GD also outperforms  DP-Clip-GD for training
over the privacy budget. In these experiments, we set $\tau=0.1$ and noise
$\sigma\in\\{0.01,0.05,0.1\\}$. Looking at Figure 2, we see that  DP-Clip21-GD
outperforms  DP-Clip-GD in solution accuracy:  DP-Clip21-GD converges towards
the higher accurate solution as the noise variance $\sigma$ decreases while
DP-Clip-GD converges towards the neighbourhood regardless of any values of
$\sigma$. At $k>10^{4}$ and $\sigma=0.01$, solution accuracy from  DP-
Clip21-GD is higher than  DP-Clip-GD by an order of magnitude for every
benchmarked dataset. This happens because  DP-Clip21-GD can handle problem
heterogeneity, as suggested by our theory.

---
|  |
(a) madelon | (b) phishing | (c) w8a
Figure 2: Comparison of  DP-Clip21-GD and  DP-Clip-GD with $\tau=0.1$ and
$\sigma\in\\{0.01,0.05,0.1\\}$ on logistic regression with
$\ell_{2}$-regularizer (first line) and a nonconvex regularizer (second line).

###  7 Conclusions, Limitations and Extensions

We proposed  Clip21-GD – an error feedback mechanism for dealing with the bias
by gradient clipping. We proved that  Clip21-GD enjoys the
$\mathcal{O}(\nicefrac{{1}}{{K}})$ convergence for nonconvex problems in
single-node and multi-node settings. We also prove that its DP variant called
DP-Clip21-GD attains privacy and utility guarantee for nonconvex functions
that satisfy the PŁ condition. Our numerical experiments indicate that
Clip21-GD and  DP-Clip21-GD attains faster convergence speed and higher
solution accuracy than  Clip-GD and  DP-Clip-GD, respectively. We plan to
extend our theory for  Clip21-GD to stochastic optimization as it works well
in our experiments on training deep neural network models.

### References

  * [1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308–318, 2016.
  * [2] Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin.  EF21: a new, simpler, theoretically better, and practically faster error feedback.  Advances in Neural Information Processing Systems, 34:4384–4396, 2021.
  * [3] Xiangyi Chen, Steven Z Wu, and Mingyi Hong.  Understanding gradient clipping in private SGD: A geometric perspective.  Advances in Neural Information Processing Systems, 33:13773–13782, 2020.
  * [4] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio.  On the difficulty of training recurrent neural networks.  In International conference on machine learning, pages 1310–1318. PMLR, 2013.
  * [5] Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie.  Why gradient clipping accelerates training: A theoretical justification for adaptivity.  In International Conference on Learning Representations, 2020.
  * [6] Aleksandr Viktorovich Nazin, AS Nemirovsky, Aleksandr Borisovich Tsybakov, and AB Juditsky.  Algorithms of robust stochastic optimization based on mirror descent method.  Automation and Remote Control, 80(9):1607–1627, 2019.
  * [7] Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov.  Stochastic optimization with heavy-tailed noise via accelerated gradient clipping.  Advances in Neural Information Processing Systems, 33:15042–15053, 2020.
  * [8] Sai Praneeth Karimireddy, Lie He, and Martin Jaggi.  Learning from history for Byzantine robust optimization.  In International Conference on Machine Learning, pages 5311–5319. PMLR, 2021.
  * [9] Alexey Kurakin, Shuang Song, Steve Chien, Roxana Geambasu, Andreas Terzis, and Abhradeep Thakurta.  Toward training at imagenet scale with differential privacy.  arXiv preprint arXiv:2201.12328v2, 2022.
  * [10] Brendan McMahan and Abhradeep Thakurta.  Federated learning with formal differential privacy guarantees.  Google Research Blog, February 2022.
  * [11] Xinwei Zhang, Xiangyi Chen, Mingyi Hong, Steven Wu, and Jinfeng Yi.  Understanding clipping for federated learning: Convergence and client-level differential privacy.  In International Conference on Machine Learning, pages 26048–26067. PMLR, 2022.
  * [12] Mingrui Liu, Zhenxun Zhuang, Yunwei Lei, and Chunyang Liao.  A communication-efficient distributed gradient clipping algorithm for training deep neural networks.  arXiv preprint arXiv:2205.05040, 2022.
  * [13] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik.  Tighter theory for local SGD on identical and heterogeneous data.  In The 23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020), 2020.
  * [14] Naum Zuselevich Shor.  Minimization methods for non-differentiable functions, volume 3.  Springer Science & Business Media, 1985.
  * [15] Yuri Ermoliev.  Numerical techniques for stochastic optimization, chapter Stochastic quasigradient methods, pages 141–185.  Springer, 1988.
  * [16] Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  Deep learning.  MIT press, 2016.
  * [17] Vien V Mai and Mikael Johansson.  Stability and convergence of stochastic gradient clipping: Beyond lipschitz continuity and smoothness.  In International Conference on Machine Learning, pages 7325–7335. PMLR, 2021.
  * [18] Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra.  Why are adaptive methods good for attention models?  Advances in Neural Information Processing Systems, 33:15383–15393, 2020.
  * [19] Eduard Gorbunov, Marina Danilova, Innokentiy Shibaev, Pavel Dvurechensky, and Alexander Gasnikov.  Near-optimal high probability complexity bounds for non-smooth stochastic optimization with heavy-tailed noise.  arXiv preprint arXiv:2106.05958, 2021.
  * [20] Ashok Cutkosky and Harsh Mehta.  High-probability bounds for non-convex stochastic optimization with heavy tails.  Advances in Neural Information Processing Systems, 34, 2021.
  * [21] Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu.  1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns.  In Fifteenth annual conference of the international speech communication association, 2014.
  * [22] Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli.  The convergence of sparsified gradient methods.  Advances in Neural Information Processing Systems, 31, 2018.
  * [23] Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi.  Sparsified SGD with memory.  Advances in Neural Information Processing Systems, 31, 2018.
  * [24] Jiaxiang Wu, Weidong Huang, Junzhou Huang, and Tong Zhang.  Error compensated quantized SGD and its applications to large-scale distributed optimization.  In International Conference on Machine Learning, pages 5325–5333. PMLR, 2018.
  * [25] Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Ji Liu.  Doublesqueeze: Parallel stochastic gradient descent with double-pass error-compensated compression.  In International Conference on Machine Learning, pages 6155–6165. PMLR, 2019.
  * [26] Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi.  Error feedback fixes signsgd and other gradient compression schemes.  In International Conference on Machine Learning, pages 3252–3261. PMLR, 2019.
  * [27] Sebastian U Stich and Sai Praneeth Karimireddy.  The error-feedback framework: Better rates for SGD with delayed gradients and compressed updates.  Journal of Machine Learning Research, 21:1–36, 2020.
  * [28] Xun Qian, Peter Richtárik, and Tong Zhang.  Error compensated distributed SGD can be accelerated.  Advances in Neural Information Processing Systems, 34:30401–30413, 2021.
  * [29] Sarit Khirirat, Sindri Magnússon, and Mikael Johansson.  Compressed gradient methods with hessian-aided error compensation.  IEEE Transactions on Signal Processing, 69:998–1011, 2020.
  * [30] Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik.  Linearly converging error compensated SGD.  Advances in Neural Information Processing Systems, 33:20889–20900, 2020.
  * [31] Ilyas Fatkhullin, 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.
  * [32] Peter Richtárik, Igor Sokolov, Elnur Gasanov, Ilyas Fatkhullin, Zhize Li, and Eduard Gorbunov.  3PC: three point compressors for communication-efficient distributed training and a better theory for lazy aggregation.  In International Conference on Machine Learning, pages 18596–18648. PMLR, 2022.
  * [33] Chih-Chung Chang and Chih-Jen Lin.  LibSVM: a library for support vector machines.  ACM Transactions on Intelligent Systems and Technology (TIST), 2(3):1–27, 2011.
  * [34] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine learning in Python.  Journal of Machine Learning Research, 12:2825–2830, 2011.
  * [35] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  3rd International Conference on Learning Representations (ICLR), 2014.
  * [36] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton.  Cifar-10 (canadian institute for advanced research).  2009\.
  * [37] Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik.  PAGE: a simple and optimal probabilistic gradient estimator for nonconvex optimization.  In International Conference on Machine Learning, pages 6286–6295. PMLR, 2021.
  * [38] Bo Chen and Matthew Hale.  The bounded gaussian mechanism for differential privacy.  arXiv preprint arXiv:2211.17230, 2022.
  * [39] Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014.

## Appendix

###  Appendix A Relation to literature on Byzantine robustness

Algorithm 1 is similar to the centered clipping subroutine used by
[karimireddy2021learning] to obtain a Byzantine-robust estimator of the
gradient. In their setting, the clients are partitioned into two groups,
regular (majority) and Byzantine (minority), and the goal is to minimize the
average of the functions owned by the regular clients without a-priori knowing
which clients are regular. The Byzantine clients are allowed to report any
vectors in an adversarial fashion in an attempt to induce bias into gradient
estimation. In this application, it is assumed that the regular workers share
the same function as this ensures that there is enough “signal” for the
optimization method to iteratively find out which clients are regular. In
contrast, we allow all functions $f_{i}$ to be arbitrarily heterogeneous.
While [karimireddy2021learning] use a single shared center/shift for all
clients $i\in[n]$ the purpose of which is to “learn” who the regular (i.e.,
non-Byzantine) clients are via tracking the (homogeneous) gradient of these
regular clients, we use $n$ different centers/shifts
($v_{k}^{1},\dots,v_{k}^{n}$) designed to track and ultimately find all the
original vectors $a^{1},\dots,a^{n}$, respectively, which can be arbitrarily
different. Due to the different goal they have, their analysis is completely
different to ours.

###  Appendix B Additional Experiments

We now include several additional experimental results.

####  B.1 Nonconvex linear regression

We run all clipped methods and their DP versions to solve the linear
regression problem with the nonconvex regularization on the form:

$\min_{x\in\mathbb{R}^{d}}\left[f(x)=\frac{1}{n}\sum\limits_{i=1}^{n}f_{i}(x)\right],$

where each local loss function is

$f_{i}(x)=\frac{1}{m}\sum\limits_{j=1}^{m}(a_{ij}^{\top}x-b_{ij})^{2}+\lambda\sum\limits_{j=1}^{d}\frac{x^{2}_{j}}{1+x_{j}^{2}}.$

Here, $\lambda>0$ is the nonconvex regularization parameter, and
$(a_{i1},b_{i1}),\ldots,(a_{im},b_{im})$ where $a_{ij}\in\mathbb{R}^{d}$ and
$b_{ij}\in\\{-1,1\\}$ are $m$ training data samples available for node $i$. We
use datasets from LibSVM library [chang2011libsvm], and perform the
preprocessing steps described in Section 6. These preprocessing steps allow
some workers to have data samples with only one class label, which make the
problem more heterogeneous. Also, by the normalization step of this
preprocessing Lipschitz constants of local loss functions $f_{i}(x)$ become
close to each other. We also used the same set of parameters (i.e.
$n,\lambda,\tau,\sigma$) for the linear regression problem as the logistic
regression problem.

From Figure 3 (a)-(b), the convergence speed of  Clip21-GD is faster than or
the same as  Clip-GD. For instance,  Clip21-GD converges faster than  Clip-GD
when $\tau=0.1$ while both methods have the same convergence performance when
$\tau=1$. This happens because when the clipping operator is turned on at the
beginning, it will be turned off in  Clip-GD with required iteration counts
$k$ much larger than in  Clip21-GD for small values of $\tau$ (e.g. for
$\tau=0.1$,  Clip-GD does not converge at all).

We also reported the training performance of  DP-Clip21-GD and  DP-Clip-GD
under the DP budget in Figure 3 (c)-(d). In particular,  DP-Clip21-GD
converges towards the higher accurate solution as the noise level decreases,
while  DP-Clip-GD converges towards the neighbourhood regardless of the noise
level. This is because  DP-Clip21-GD, unlike  DP-Clip-GD, can handle the
problem heterogeneity, as suggested by our theory.

|
---|---
|  |  |
(a) a1a | (b) w8a | (c) phishing | (d) mushrooms
Figure 3: (a), (b) The comparison of  Clip-EF21 and  Clip-GD varying clipping
parameter $\tau$ on Linear Regression with nonconvex regularization. (c), (d)
The comparison of  DP-Clip21-GD and  DP-Clip-GD varying noise level on Linear
Regression with nonconvex regularization

####  B.2 Deep learning experiments

We now showcase that  Clip21 also outperforms  Clip for training the VGG11
model [vgg11] for multiclass classification problem on the CIFAR10 train
dataset with $50000$ samples and $10$ classes ($5000$ samples for each class)
[cifar10]. We modify  Clip21-GD and  Clip-GD by replacing the full local
gradient $\nabla f_{i}(x_{k})$ with its mini-batch stochastic estimator. We
refer these methods as  Clip21-SGD and  Clip-SGD.

This data set is split into $10$ classes among $10$ workers according to the
following rules:

  1. 1.

$2500$ samples of the $i^{\text{th}}$ class are given to the $i^{\text{th}}$
client (which is in total $25000$ samples), and

  2. 2.

the rest of dataset is shuffled and partitioned randomly between workers.

These preprocessing rules allow the $i^{\text{th}}$ worker to have most
samples with the $i^{\text{th}}$ class, which makes the problem more
heterogeneous. For each worker, its local datasets are shuffled only once at
the beginning, and its stochastic gradient is computed for each iteration from
randomly selected samples with the batch size $32$.

We reported the best performance of  Clip21-SGD and  Clip-SGD in train loss
and test accuracy from fine-tuning stepsizes (see Figure 4). We observe that
Clip21-SGD outperforms  Clip-SGD in both metrics for any values of $\tau$; see
Figure 4. In particular, one can notice that for small value of clipping
parameter ($\tau=10^{-4}$) the difference in train loss and test accuracy
given by  Clip21-SGD and  Clip-SGD is significant, while for relatively large
values ($\tau=10^{-2}$) the performance of algorithms becomes similar.
Besides,  Clip21-SGD attains more than $3$ (in log scale) times lower train
loss than  Clip-SGD at epoch $50$ for $\tau\in\\{10^{-4},10^{-3},10^{-2}\\}$.
These encouraging experiments motivate us to investigate theoretical
convergence guarantees for  Clip21-SGD as our future directions.

Next, we consider DP-versions of algorithms applied on the same problem. Now
workers compute mini-batches of size $512$. We add normally distributed noise
to the updates varying its variance. The results of this set of experiments
are presented in Figure 5. We observe that  DP-Clip21-SGD slightly outperforms
DP-Clip-SGD in both metrics.

|  |
---|---|---
|  |
Figure 4: The performance of  Clip21-SGD and  Clip-SGD with fine-tuned stepsizes to train the VGG11 model on the CIFAR10 dataset. |  |  |
---|---|---|---
Figure 5: The performance of  DP-Clip21-SGD and  DP-Clip-SGD with fine-tuned
stepsizes to train the VGG11 model on the CIFAR10 dataset.

###  Appendix C Loss of a Constant Factor when Generalizing to Arbitrary $n$

When specializing our multi-node theory for  Clip21-GD to the $n=1$ case, and
compare this to the theory from Section 5.1, we pay the price of a smaller
maximum stepsize, which affects constants in the convergence rate.

We illustrate this by letting $\phi_{0}$ to be large, $L=L_{\max}$ and $n=1$
in Lemma 5.4, Proposition 5.5 and Theorem 5.6. Suppose that
$\frac{\left\|\nabla f(x_{0})\right\|}{\tau}$ is close to $1$. Then, Lemma
5.4, Proposition 5.5 and Theorem 5.6 with $n=1$ recover the results from
Section 5.1 under the stepsize

$\gamma\leq\frac{1}{L}\cdot\min\left(\frac{1-1/\sqrt{2}}{1+\sqrt{1+2\beta_{1}}},\frac{\tau^{2}}{16L\left[\sqrt{F_{0}}+\sqrt{\beta_{2}}\right]^{2}}\right),$

where $\eta,\beta_{1},\beta_{2},F_{0},G_{0}$ are defined in Theorem 5.3.

This step-size is $4$ times smaller than that allowed by Theorem 5.3 dedicated
to the single-node setting. The technical difficulty preventing us from
generalizing the single-node theory to the multi-node version in a tighter
manner is related to upper bounding the quantity $\left\|v_{k}\right\|$ in the
analysis. In the multi-node setting, we have

$\left\|v_{k}\right\|=\left\|\nabla
f(x_{k})+\frac{1}{n}\sum_{i=1}^{n}e_{k}^{i}\right\|\leq\left\|\nabla
f(x_{k})\right\|+\frac{1}{n}\sum_{i=1}^{n}{\left\|e_{k}^{i}\right\|},$

where

$e_{k}^{i}={\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{k})-v_{k-1}^{i})-(\nabla f_{i}(x_{k})-v_{k-1}^{i}).$

This upper bound on $\left\|v_{k}\right\|$ is looser than that we could use in
the single-node setting, which instead reads:

$\left\|v_{k}\right\|\leq(1-\eta_{k})\left\|v_{k-1}\right\|+\eta_{k}\left\|\nabla
f(x_{k})\right\|,$

where

$\eta_{k}=\min\left\\{1,\frac{1}{\left\|\nabla
f(x_{k})-v_{k-1}\right\|}\right\\}.$

###  Appendix D Basic Inequalities and Useful Lemmas

####  D.1 Basic Inequalities

Triangle inequality:

$\left\|x+y\right\|\leq\left\|x\right\|+\left\|y\right\|,\quad\forall
x,y\in\mathbb{R}^{d}.$ (15)

Subadditivity of the square root:

$\sqrt{a+b}\leq\sqrt{a}+\sqrt{b},\quad\forall a,b\geq 0.$ (16)

Young’s inequality:

$\left\|x+y\right\|^{2}\leq(1+\theta)\left\|x\right\|^{2}+(1+\theta^{-1})\left\|y\right\|^{2},\quad\forall
x,y\in\mathbb{R}^{d},\;\theta>0.$ (17)

####  D.2 Lemmas

In this section, we introduce several lemmas that are instrumental to our
analysis.

######  Lemma D.1.

Let $f:\mathbb{R}^{d}\to\mathbb{R}$ be a function with $L$-Lipschitz gradient,
with $f_{\inf}\in\mathbb{R}$ being a lower bound on $f$. Then

$\frac{1}{2L}\left\|\nabla f(x)\right\|^{2}\leq f(x)-f_{\inf},\quad\forall
x\in\mathbb{R}^{d}.$ (18)

######  Lemma D.2.

Let $f:\mathbb{R}^{d}\to\mathbb{R}$ be a function with $L$-Lipschitz gradient.
Then

$f(x)\leq f(y)+\langle\nabla
f(y),y-x\rangle+\frac{L}{2}\left\|x-y\right\|^{2},\quad\forall
x\in\mathbb{R}^{d}.$ (19)

Lemma D.3 gives the bound on the function value after one step of a method of
the type: $x_{k+1}\coloneqq x_{k}-\gamma v_{k}$. We use this lemma to derive
the descent inequality for  Clip21-GD and its variants.

######  Lemma D.3 (Lemma 2 from [li2021page]).

Let $f:\mathbb{R}^{d}\to\mathbb{R}$ be a function with $L$-Lipschitz gradient
and let $x_{k+1}\coloneqq x_{k}-\gamma v_{k}$, where $\gamma>0$ and
$v_{k}\in\mathbb{R}^{d}$ is any vector. Then

$\displaystyle f(x_{k+1})\leq f(x_{k})-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}-\left(\frac{1}{2\gamma}-\frac{L}{2}\right)\left\|x_{k+1}-x_{k}\right\|^{2}+\frac{\gamma}{2}\left\|\nabla
f(x_{k})-v_{k}\right\|^{2}.$ (20)

Finally, we present Lemma D.4 and D.5 that are useful for deriving the easy-
to-write condition on the step-size that ensures the convergence of  Clip21-GD
and its variants.

######  Lemma D.4.

If the stepsize is chosen to satisfy

$0<\gamma\leq\frac{2}{L(\beta_{1}+\sqrt{\beta_{1}^{2}+4\beta_{2}})}$

for some $\beta_{1},\beta_{2}>0$, then

$\frac{1}{\gamma}-\beta_{1}L-\gamma\beta_{2}L^{2}\geq 0.$

###### Proof.

Let $\gamma=\nicefrac{{1}}{{(\theta L)}}$ where $\theta>0$. Then, $\gamma>0$.
Also, $\nicefrac{{1}}{{\gamma}}-\beta_{1}L-\gamma\beta_{2}L^{2}\geq 0$ can be
expressed equivalently as $\theta^{2}-\beta_{1}\theta-\beta_{2}\geq 0.$ This
condition holds if
$\theta\geq\nicefrac{{(\beta_{1}+\sqrt{\beta_{1}^{2}+4\beta_{2}})}}{{2}}$ or
equivalently
$0<\gamma\leq\nicefrac{{2}}{{[L(\beta_{1}+\sqrt{\beta_{1}^{2}+4\beta_{2}})]}}$.
∎

######  Lemma D.5.

If
$0<\gamma\leq\frac{4c_{3}^{2}\tau^{2}}{c_{1}^{2}L^{2}\left[\sqrt{F_{0}}+\sqrt{F_{0}+CG_{0}}\right]^{2}}$
for $C=\frac{4c_{2}c_{3}\tau}{c_{1}^{2}L}$ and for some
$c_{1},c_{2},c_{3},F_{0},G_{0},\tau>0$, then $c_{1}L\sqrt{\gamma
F_{0}}+c_{2}LG_{0}\gamma\leq c_{3}\tau$.

###### Proof.

Using Lemma D.4 with $\beta_{1}=c_{1}\sqrt{F_{0}}/(c_{3}\tau)$ and
$\beta_{2}=c_{2}G_{0}/(c_{3}\tau L)$, we prove the result. ∎

###  Appendix E Proof of Lemmas in Section 4

####  E.1 Proof of Lemma 4.2

Subtracting $a^{i}$ from both sides of Step 3 of Algorithm 1, and applying
norms, we get

$\displaystyle\left\|a^{i}-v_{k}^{i}\right\|$ $\displaystyle=$
$\displaystyle\left\|v_{k-1}^{i}+{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(a^{i}-v_{k-1}^{i})-a^{i}\right\|$
$\displaystyle=$
$\displaystyle\left\|{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(a^{i}-v_{k-1}^{i})-(a^{i}-v_{k-1}^{i})\right\|.$

In view of Lemma 4.1, parts (ii) and (iii), the last expression is 0 if
$\left\|a^{i}-v_{k-1}^{i}\right\|\leq\tau$, and is equal to
$\left\|a^{i}-v_{k-1}^{i}\right\|-\tau$ otherwise. The rest follows.

####  E.2 Proof of Theorem 4.3

By convexity of the norm, the quantity
$\left\|v_{k}-a\right\|=\left\|\frac{1}{n}\sum_{i=1}^{n}v^{i}_{k}-\frac{1}{n}\sum_{i=1}^{n}a^{i}\right\|$
can be upper bounded by
$\frac{1}{n}\sum_{i=1}^{n}\left\|v^{i}_{k}-a^{i}\right\|$. It remains to apply
Lemma 4.2.

###  Appendix F Clip21-GD in the $n=1$ Regime

We will now analyze the single-node version of  Clip21-GD (Algorithm 2 for
$n=1$), i.e.,

$x_{k+1}=x_{k}-\gamma v_{k},$ (21)

where

$v_{k}=v_{k-1}+{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f(x_{k})-v_{k-1}).$ (22)

Note that this can be rewritten into the simpler form

$\displaystyle v_{k}=(1-\eta_{k})v_{k-1}+\eta_{k}\nabla f(x_{k}),$ (23)

where

$\eta_{k}\coloneqq\min\left\\{1,\frac{\tau}{\left\|\nabla
f(x_{k})-v_{k-1}\right\|}\right\\},$ (24)

and the ratio $\frac{\tau}{\left\|\nabla f(x_{k})-v_{k-1}\right\|}$ is
interpreted as $+\infty$ if $\nabla f(x_{k})=v_{k-1}$, which means that
$\eta_{k}=1$ in that case. Note that this means that

$\left\|\nabla
f(x_{k})-v_{k}\right\|^{2}\overset{\eqref{eqn:ineq_v_k}}{=}(1-\eta_{k})^{2}\left\|\nabla
f(x_{k})-v_{k-1}\right\|^{2}.$ (25)

Recall that the Lyapunov function was defined as

$\phi_{k}\coloneqq f(x_{k})-f_{\inf}+\frac{\gamma A_{\eta}}{2}\left\|\nabla
f(x_{k})-v_{k}\right\|^{2},$ (26)

where $A_{\eta}\coloneqq\frac{1}{1-(1-\eta)\left(1-\frac{\eta}{2}\right)}$ and
$\eta\coloneqq\min\left\\{1,\frac{\tau}{\left\|\nabla
f(x_{0})\right\|}\right\\}$. Also let $F_{0}\coloneqq f(x_{0})-f_{\inf}$ and
$G_{0}\coloneqq\max\left\\{0,\left\|\nabla f(x_{0})\right\|-\tau\right\\}$.

####  F.1 Claims

We first establish several simple but helpful results.

######  Claim F.1.

Assume that $v_{-1}=0$. Then

$v_{0}={\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f(x_{0})),$ (27) $\left\|v_{0}\right\|=\min\left\\{\tau,\left\|\nabla
f(x_{0})\right\|\right\\},$ (28)

and

$\left\|\nabla f(x_{0})-v_{0}\right\|=\max\left\\{0,\left\|\nabla
f(x_{0})\right\|-\tau\right\\}.$ (29)

If we additionally assume that $\gamma\leq\frac{2}{L}$, then

$\left\|v_{0}\right\|\leq\sqrt{\frac{4}{\gamma}\phi_{0}}.$ (30)

###### Proof.

Equation (27) follows from

$\displaystyle v_{0}$ $\displaystyle\overset{\eqref{eq:yf89gfdfd}}{=}$
$\displaystyle
v_{-1}+{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f(x_{0})-v_{-1})\quad=\quad{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f(x_{0})).$

Equation (28) follows from (27). Equation (29) follows from (27) and Lemma
4.1:

$\left\|\nabla
f(x_{0})-v_{0}\right\|\overset{\eqref{eq:98ifd_8hfd9-1}}{=}\left\|\nabla
f(x_{0})-{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f(x_{0}))\right\|\overset{(\text{Lemma~{}\ref{lem:clip}(ii)-(iii)})}{=}\max\left\\{0,\left\|\nabla
f(x_{0})\right\|-\tau\right\\}.$

Finally, (30) follows from

$\displaystyle\left\|v_{0}\right\|$
$\displaystyle\overset{\eqref{eq:98ifd_8hfd9-2}}{=}$
$\displaystyle\min\left\\{\tau,\left\|\nabla f(x_{0})\right\|\right\\}$
$\displaystyle\leq$ $\displaystyle\left\|\nabla f(x_{0})\right\|$
$\displaystyle\overset{\eqref{eq:ssss}}{\leq}$
$\displaystyle\sqrt{2L\left(f(x_{0})-f_{\rm inf}\right)}$
$\displaystyle\overset{\eqref{eq:Lyapunov-89d}}{\leq}$
$\displaystyle\sqrt{2L\phi_{0}}$ $\displaystyle\leq$
$\displaystyle\sqrt{\frac{4}{\gamma}\phi_{0}},$

where the last inequality follows from the assumption $\gamma\leq\frac{2}{L}$.
∎

######  Claim F.2.

Fix $k\geq 0$. Then

$\left\|\nabla f(x_{k+1})-v_{k}\right\|\leq\max\left\\{0,\left\|\nabla
f(x_{k})-v_{k-1}\right\|-\tau\right\\}+L\gamma\left\|v_{k}\right\|.$ (31)

###### Proof.

Indeed,

$\displaystyle\left\|\nabla f(x_{k+1})-v_{k}\right\|$ $\displaystyle=$
$\displaystyle\left\|\nabla f(x_{k})-v_{k}+\nabla f(x_{k+1})-\nabla
f(x_{k})\right\|$ $\displaystyle\overset{\eqref{eq:triangle}}{\leq}$
$\displaystyle\left\|\nabla f(x_{k})-v_{k}\right\|+\left\|\nabla
f(x_{k+1})-\nabla f(x_{k})\right\|$
$\displaystyle\overset{\eqref{eq:yf89gfdfd}}{=}$ $\displaystyle\left\|(\nabla
f(x_{k})-v_{k-1})-{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f(x_{k})-v_{k-1})\right\|$ $\displaystyle+\left\|\nabla f(x_{k+1})-\nabla
f(x_{k})\right\|$
$\displaystyle\overset{(\text{Lemma~{}\ref{lem:clip}(ii)-(iii)})}{=}$
$\displaystyle\max\left\\{0,\left\|\nabla
f(x_{k})-v_{k-1}\right\|-\tau\right\\}+\left\|\nabla f(x_{k+1})-\nabla
f(x_{k})\right\|$ $\displaystyle\overset{\eqref{eq:L-smooth}}{\leq}$
$\displaystyle\max\left\\{0,\left\|\nabla
f(x_{k})-v_{k-1}\right\|-\tau\right\\}+L\left\|x_{k+1}-x_{k}\right\|$
$\displaystyle\overset{\eqref{eq:8y98fd_08yfd}}{=}$
$\displaystyle\max\left\\{0,\left\|\nabla
f(x_{k})-v_{k-1}\right\|-\tau\right\\}+L\gamma\left\|v_{k}\right\|.$

∎

######  Claim F.3.

Fix $k\geq 1$. If $\frac{\gamma}{2}\left\|\nabla
f(x_{k-1})\right\|^{2}\leq\phi_{0}$,
$\frac{\gamma}{4}\|v_{k-1}\|^{2}\leq\phi_{0}$ and
$\gamma\leq\frac{1-\frac{1}{\sqrt{2}}}{L}$, then

$\left\|v_{k}\right\|\leq\sqrt{\frac{4}{\gamma}\phi_{0}}.$ (32)

###### Proof.

$\displaystyle\left\|v_{k}\right\|$
$\displaystyle\overset{\eqref{eqn:ineq_v_k}+\eqref{eq:triangle}}{\leq}$
$\displaystyle(1-\eta_{k})\|v_{k-1}\|+\eta_{k}\|\nabla f(x_{k})\|$ (33)
$\displaystyle\overset{\eqref{eq:triangle}}{\leq}$
$\displaystyle(1-\eta_{k})\|v_{k-1}\|+\eta_{k}\|\nabla f(x_{k})-\nabla
f(x_{k-1})\|+\eta_{k}\|\nabla f(x_{k-1})\|$
$\displaystyle\overset{\eqref{eq:L-smooth}}{\leq}$
$\displaystyle(1-\eta_{k})\|v_{k-1}\|+\eta_{k}L\left\|x_{k}-x_{k-1}\right\|+\eta_{k}\left\|\nabla
f(x_{k-1})\right\|$ $\displaystyle\overset{\eqref{eq:8y98fd_08yfd}}{=}$
$\displaystyle(1-\eta_{k})\|v_{k-1}\|+\eta_{k}L\gamma\left\|v_{k-1}\right\|+\eta_{k}\|\nabla
f(x_{k-1})\|$ $\displaystyle=$
$\displaystyle(1-\eta_{k}+\eta_{k}L\gamma)\left\|v_{k-1}\right\|+\eta_{k}\left\|\nabla
f(x_{k-1})\right\|$ $\displaystyle\overset{(*)}{\leq}$
$\displaystyle(1-\eta_{k}+\eta_{k}L\gamma)\sqrt{\frac{4}{\gamma}\phi_{0}}+\eta_{k}\sqrt{\frac{2}{\gamma}\phi_{0}}$
$\displaystyle=$
$\displaystyle\left(1-\eta_{k}+\eta_{k}L\gamma+\frac{\eta_{k}}{\sqrt{2}}\right)\sqrt{\frac{4}{\gamma}\phi_{0}}$
$\displaystyle\overset{(**)}{\leq}$
$\displaystyle\sqrt{\frac{4}{\gamma}\phi_{0}},$

where in (*) we have used the first two assumptions, and in (**) we have used
the bound on $\gamma$. ∎

######  Claim F.4.

Assume that $v_{-1}=0$. If

$\displaystyle
0\leq\gamma\leq\frac{\tau^{2}}{4L^{2}\left[\sqrt{F_{0}}+\sqrt{F_{0}+\frac{\tau
G_{0}}{\sqrt{2\eta}L}}\right]^{2}},$ (34)

where $\eta\coloneqq\min\left\\{1,\frac{\tau}{\left\|\nabla
f(x_{0})\right\|}\right\\}$, $F_{0}\coloneqq f(x_{0})-f_{\rm inf}$ and
$G_{0}\coloneqq\max\left\\{0,\left\|\nabla f(x_{0})\right\|-\tau\right\\}$,
then

$2L\sqrt{\gamma\phi_{0}}\leq\frac{\tau}{2}.$

###### Proof.

This takes a bit of effort since $\phi_{0}$ depends on $\gamma$ as well. In
particular,

$\displaystyle 2L\sqrt{\gamma\phi_{0}}$
$\displaystyle\overset{\eqref{eq:Lyapunov-89d}}{=}$ $\displaystyle
2L\sqrt{\gamma\left(f(x_{0})-f_{\inf}\right)+\frac{\gamma^{2}A_{\eta}}{2}\left\|\nabla
f(x_{0})-v_{0}\right\|^{2}}$
$\displaystyle\overset{\eqref{eq:98ifd_8hfd9-3}}{=}$ $\displaystyle
2L\sqrt{\gamma F_{0}+\frac{\gamma^{2}A_{\eta}}{2}G_{0}^{2}}$
$\displaystyle\leq$ $\displaystyle 2L\sqrt{\gamma
F_{0}+\frac{\gamma^{2}}{2\eta}G_{0}^{2}},$

where we reach the last inequality by the fact that
$A_{\eta}=\frac{1}{1-(1-\eta)\left(1-\frac{\eta}{2}\right)}\leq\frac{1}{1-(1-\eta)}=\frac{1}{\eta}$.
By subadditivity of $t\mapsto\sqrt{t}$, we therefore get

$\displaystyle 2L\sqrt{\gamma\phi_{0}}$
$\displaystyle\overset{\eqref{eq:sqrt}}{\leq}$ $\displaystyle
2L\sqrt{F_{0}}\sqrt{\gamma}+\sqrt{\frac{2}{\eta}}LG_{0}\gamma.$

Hence, any $\gamma>0$ satisfying

$\displaystyle
2L\sqrt{F_{0}}\sqrt{\gamma}+\sqrt{\frac{2}{\eta}}LG_{0}\gamma\leq\frac{\tau}{2}$
(35)

also satisfies $2L\sqrt{\gamma\phi_{0}}\leq\frac{\tau}{2}$. The condition (35)
can be re-written as

$\displaystyle\frac{1}{\sqrt{\gamma}}-\frac{4}{\tau}\sqrt{F_{0}}\cdot
L-\sqrt{\gamma}\cdot\frac{2\sqrt{2}}{\tau\sqrt{\eta}}\frac{G_{0}}{L}\cdot
L^{2}\geq 0.$

It remains to apply Lemma D.5 with $c_{1}=2$, $c_{2}=\sqrt{\frac{2}{\eta}}$
and $c_{3}=\frac{1}{2}$.

∎

######  Claim F.5.

Pick any $k\geq 0$ and assume that $\left\|\nabla
f(x_{k+1})-v_{k}\right\|\leq\left\|\nabla f(x_{0})\right\|$. Also let
$\eta=\min\left\\{1,\frac{\tau}{\left\|\nabla f(x_{0})\right\|}\right\\}$.
Then

$\left\|\nabla
f(x_{k+1})-v_{k+1}\right\|^{2}\leq(1-\eta)\left(1-\frac{\eta}{2}\right)\left\|\nabla
f(x_{k})-v_{k}\right\|^{2}+\left(1+\frac{2}{\eta}\right)(1-\eta)^{2}L^{2}\left\|x_{k+1}-x_{k}\right\|^{2},$
(36)

and

$\phi_{k+1}\leq\phi_{k}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}-\frac{1}{2\gamma}\left(1-\gamma
L-\gamma^{2}A_{\eta}\left(1+\frac{2}{\eta}\right)(1-\eta)^{2}L^{2}\right)\left\|x_{k+1}-x_{k}\right\|^{2}.$
(37)

If moreover the step-size satisfies

$0<\gamma\leq\frac{1}{L\left(1+\sqrt{1+2A_{\eta}(1-\eta)^{2}\left(1+\frac{2}{\eta}\right)}\right)},$
(38)

then

$\displaystyle\phi_{k+1}\leq\phi_{k}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}-\frac{\gamma}{4}\left\|v_{k}\right\|^{2}.$ (39)

###### Proof.

Since $\left\|\nabla f(x_{k+1})-v_{k}\right\|\leq\left\|\nabla
f(x_{0})\right\|$,

$\eta_{k+1}\overset{\eqref{eq:98y98dg087fd+09ufd}}{=}\min\left\\{1,\frac{\tau}{\left\|\nabla
f(x_{k+1})-v_{k}\right\|}\right\\}\geq\min\left\\{1,\frac{\tau}{\left\|\nabla
f(x_{0})\right\|}\right\\}=\eta.$ (40)

Therefore,

$\displaystyle\left\|\nabla f(x_{k+1})-v_{k+1}\right\|^{2}$
$\displaystyle\overset{\eqref{eq:89hfd8f_98yfd9}}{=}$
$\displaystyle(1-\eta_{k+1})^{2}\left\|\nabla f(x_{k+1})-v_{k}\right\|^{2}$
$\displaystyle\overset{\eqref{eq:hp87yfd0}}{\leq}$
$\displaystyle(1-\eta)^{2}\left\|\nabla f(x_{k+1})-v_{k}\right\|^{2}$
$\displaystyle=$ $\displaystyle(1-\eta)^{2}\left\|\nabla f(x_{k})-v_{k}+\nabla
f(x_{k+1})-\nabla f(x_{k})\right\|^{2}$
$\displaystyle\overset{\eqref{eq:Young}}{\leq}$
$\displaystyle(1+\theta)(1-\eta)^{2}\left\|\nabla f(x_{k})-v_{k}\right\|^{2}$
$\displaystyle+\left(1+\theta^{-1}\right)(1-\eta)^{2}\left\|\nabla
f(x_{k+1})-\nabla f(x_{k})\right\|^{2}$ $\displaystyle\leq$
$\displaystyle(1+\theta)(1-\eta)^{2}\left\|\nabla
f(x_{k})-v_{k}\right\|^{2}+\left(1+\theta^{-1}\right)(1-\eta)^{2}L^{2}\left\|x_{k+1}-x_{k}\right\|^{2},$

where we have the freedom to choose $\theta>0$. To obtain (36), it remains to
choose $\theta=\frac{\eta}{2}$ and apply the inequality
$(1-\eta)(1+\frac{\eta}{2})\leq 1-\frac{\eta}{2}$ (which holds for any
$\eta\in\mathbb{R}$).

Furthermore, by combining (36) with Lemma D.3, we get

$\displaystyle\phi_{k+1}$ $\displaystyle\overset{\eqref{eq:Lyapunov-89d}}{=}$
$\displaystyle f(x_{k+1})-f_{\rm inf}+\frac{\gamma A_{\eta}}{2}\left\|\nabla
f(x_{k+1})-v_{k+1}\right\|^{2}$ (41)
$\displaystyle\overset{\eqref{eq:descent_ineq}}{\leq}$ $\displaystyle
f(x_{k})-f_{\inf}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}-\left(\frac{1}{2\gamma}-\frac{L}{2}\right)\left\|x_{k+1}-x_{k}\right\|^{2}+\frac{\gamma}{2}\left\|\nabla
f(x_{k})-v_{k}\right\|^{2}$ $\displaystyle+\frac{\gamma
A_{\eta}}{2}\left\|\nabla f(x_{k+1})-v_{k+1}\right\|^{2}$
$\displaystyle\overset{\eqref{eq:Lyapunov-89d}}{=}$
$\displaystyle\phi_{k}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}-\left(\frac{1}{2\gamma}-\frac{L}{2}\right)\left\|x_{k+1}-x_{k}\right\|^{2}+\left(\frac{\gamma}{2}-\frac{\gamma
A_{\eta}}{2}\right)\left\|\nabla f(x_{k})-v_{k}\right\|^{2}$
$\displaystyle+\frac{\gamma A_{\eta}}{2}\left\|\nabla
f(x_{k+1})-v_{k+1}\right\|^{2}$
$\displaystyle\overset{\eqref{eqn:0980d9_09ufd}}{\leq}$
$\displaystyle\phi_{k}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}-\left(\frac{1}{2\gamma}-\frac{L}{2}-\frac{\gamma
A_{\eta}}{2}\left(1+\frac{2}{\eta}\right)(1-\eta)^{2}L^{2}\right)\left\|x_{k+1}-x_{k}\right\|^{2}$
$\displaystyle\hskip 14.22636pt+\left(\frac{\gamma}{2}+\frac{\gamma
A_{\eta}}{2}(1-\eta)\left(1-\frac{\eta}{2}\right)-\frac{\gamma
A_{\eta}}{2}\right)\left\|\nabla f(x_{k})-v_{k}\right\|^{2}$ $\displaystyle=$
$\displaystyle\phi_{k}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}-\frac{1}{2\gamma}\left(1-\gamma
L-\gamma^{2}A_{\eta}\left(1+\frac{2}{\eta}\right)(1-\eta)^{2}L^{2}\right)\left\|x_{k+1}-x_{k}\right\|^{2},$

where in the last step the term corresponding to $\left\|\nabla
f(x_{k})-v_{k}\right\|^{2}$ vanished because
$A_{\eta}\coloneqq\frac{1}{1-(1-\eta)\left(1-\frac{\eta}{2}\right)}$. Recall
that $\eta\coloneqq\min\left\\{1,\frac{\tau}{\left\|\nabla
f(x_{0})\right\|}\right\\}$.

Finally, if the step-size $\gamma$ satisfies (38), then from Lemma D.4 with
$\beta_{1}=2$ and
$\beta_{2}=2A_{\eta}(1-\eta)^{2}\left(1+\frac{2}{\eta}\right)$, this condition
implies $1-\gamma
L-\gamma^{2}A_{\eta}(1-\eta)^{2}\left(1+\frac{2}{\eta}\right)L^{2}\geq\frac{1}{2}$
and thus

$\displaystyle\phi_{k+1}$
$\displaystyle\overset{\eqref{eq:988y=-oidf9u}}{\leq}$
$\displaystyle\phi_{k}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}-\frac{1}{4\gamma}\left\|x_{k+1}-x_{k}\right\|^{2}$
$\displaystyle\overset{\eqref{eq:8y98fd_08yfd}}{=}$
$\displaystyle\phi_{k}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}-\frac{\gamma}{4}\left\|v_{k}\right\|^{2}.$

∎

####  F.2 Proof of Lemma 5.1

We will derive the descent inequality

$\displaystyle\phi_{k+1}$
$\displaystyle\leq\phi_{k}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}.$

We consider two cases: (1) when $\tau<\|\nabla f(x_{k})-v_{k-1}\|$ and (2)
when $\|\nabla f(x_{k})-v_{k-1}\|\leq\tau$.

For notational convenience, we assume that $\nabla f(x_{-1})=v_{-1}=0$ and
$\phi_{-1}=\phi_{0}$.

####  F.3 Case (1): $\tau<\|\nabla f(x_{k})-v_{k-1}\|$

Assume that

$\tau\leq\left\|\nabla f(x_{k})-v_{k-1}\right\|.$ (42)

To derive the descent inequality we will show by induction the stronger
result: $\|\nabla f(x_{k})-v_{k-1}\|\leq B-\frac{k\tau}{2}$, where
$B\coloneqq\left\|\nabla f(x_{0})\right\|$ and

$\phi_{k}\leq\phi_{k-1}-\frac{\gamma}{2}\left\|\nabla
f(x_{k-1})\right\|^{2}-\frac{\gamma}{4}\|v_{k-1}\|^{2}$ (43)

for any $k\geq 0$. The base of the induction is trivial: when $k=0$ we have
$\|\nabla f(x_{k})-v_{k-1}\|=\|\nabla f(x_{0})-v_{-1}\|=\|\nabla
f(x_{0})\|:=B$ and (43) holds by definition since $\phi_{0}=\phi_{-1}$. Next,
we assume that for some $k\geq 0$ inequalities $\left\|\nabla
f(x_{t})-v_{t-1}\right\|\leq B$ and (43) hold for $t=0,1,\ldots,k$.

Let $0\leq\phi_{k}\leq\phi_{0}$ for all $k\geq 0$. If $\gamma\leq 1/L$, then

$\displaystyle\left\|\nabla f(x_{k-1})\right\|^{2}$
$\displaystyle\mathop{\leq}\limits^{\eqref{eq:ssss}}$ $\displaystyle
2L[f(x_{k-1})-f_{\inf}]$
$\displaystyle\mathop{\leq}\limits^{\eqref{eq:Lyapunov-89d}}$ $\displaystyle
2L\phi_{k-1}$ $\displaystyle\leq$ $\displaystyle 2L\phi_{0}$
$\displaystyle\leq$ $\displaystyle\frac{2}{\gamma}\phi_{0}.$

If $\gamma\leq\frac{1-\frac{1}{\sqrt{2}}}{L}$ and $v_{-1}=0$, then we have
from Claim F.1 and F.3 that for $k\geq 0$

$\displaystyle\left\|v_{k}\right\|\leq\sqrt{\frac{4}{\gamma}\phi_{0}}.$

Next, from Claim F.2 with (42),

$\displaystyle\left\|\nabla f(x_{k+1})-v_{k}\right\|$ $\displaystyle\leq$
$\displaystyle\left\|\nabla
f(x_{k})-v_{k-1}\right\|-\tau+L\gamma\left\|v_{k}\right\|$ $\displaystyle\leq$
$\displaystyle\left\|\nabla
f(x_{k})-v_{k-1}\right\|-\tau+2L\sqrt{\gamma\phi_{0}}.$

STEP: Small stepsize.

If $\gamma>0$ satisfies (34), then from Claim F.4 we have
$2L\sqrt{\gamma\phi_{0}}\leq\frac{\tau}{2}$. Hence, the above inequality and
the inductive assumption imply

$\displaystyle\left\|\nabla f(x_{k+1})-v_{k}\right\|$
$\displaystyle\leq\left\|\nabla
f(x_{k})-v_{k-1}\right\|-\frac{\tau}{2}\leq\cdots\leq\left\|\nabla
f(x_{0})\right\|-\frac{(k+1)\tau}{2}.$ (44)

In conclusion, Eq. (44) implies that $\left\|\nabla
f(x_{k})-v_{k-1}\right\|\leq\left\|\nabla f(x_{0})\right\|:=B$ for any $k\geq
0$.

STEP: Descent inequality.

If the step-size $\gamma>0$ satisfies (38), then by the assumption that
$\left\|\nabla f(x_{k})-v_{k-1}\right\|\leq B$ for any $k\geq 0$ and from
Claim F.5 we obtain

$\displaystyle\phi_{k+1}\leq\phi_{k}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}-\frac{\gamma}{4}\left\|v_{k}\right\|^{2}.$

This concludes the proof in case (1).

####  F.4 Case (2): $\|\nabla f(x_{k})-v_{k-1}\|\leq\tau$

Suppose that $\|\nabla f(x_{k})-v_{k-1}\|\leq\tau$. Then, by using (23) and by
the fact that $\eta_{k}=\eta=1$, we have

$\displaystyle v_{k}=\nabla f(x_{k}).$ (45)

Therefore, single-node  Clip21-GD described in Algorithm 2 with $n=1$ reduces
to classical gradient descent at step $k$. From the definition of $\phi_{k}$
and Lemma D.3,

$\displaystyle\phi_{k+1}$ $\displaystyle=$ $\displaystyle f(x_{k+1})-f_{\rm
inf}$ $\displaystyle\overset{\eqref{eq:descent_ineq}}{\leq}$ $\displaystyle
f(x_{k})-f_{\rm inf}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}-\left(\frac{1}{2\gamma}-\frac{L}{2}\right)\|x_{k+1}-x_{k}\|^{2}+\frac{\gamma}{2}\left\|\nabla
f(x_{k})-v_{k}\right\|^{2}$ $\displaystyle{\leq}$
$\displaystyle\phi_{k}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}-\left(\frac{1}{2\gamma}-\frac{L}{2}\right)\|x_{k+1}-x_{k}\|^{2}.$

If $\gamma\leq 1/L$, then

$\displaystyle\phi_{k+1}$
$\displaystyle\leq\phi_{k}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}.$ (46)

From (46), we get $0\leq\phi_{k}\leq\phi_{0}$ and

$\displaystyle\left\|\nabla f(x_{k})\right\|$
$\displaystyle\leq\sqrt{\left\|\nabla
f(x_{k})\right\|^{2}}\leq\sqrt{\frac{2}{\gamma}[\phi_{k}-\phi_{k+1}]}\leq\sqrt{\frac{2}{\gamma}\phi_{k}}\leq\sqrt{\frac{2}{\gamma}\phi_{0}}.$

Finally, we will show that $\|\nabla f(x_{k})-v_{k-1}\|\leq\tau$ implies
$\|\nabla f(x_{k+1})-v_{k}\|\leq\tau$. In this case,

$\displaystyle\|\nabla f(x_{k+1})-v_{k}\|$ $\displaystyle\leq$ $\displaystyle
L\left\|x_{k+1}-x_{k}\right\|$
$\displaystyle\mathop{=}\limits^{\eqref{eqn:v_k_off_centralized}}$
$\displaystyle L\gamma\left\|\nabla f(x_{k})\right\|$
$\displaystyle\mathop{\leq}\limits^{\eqref{eq:triangle}}$ $\displaystyle
L\gamma\left\|\nabla f(x_{k})-v_{k-1}\right\|+L\gamma\left\|v_{k-1}\right\|$
$\displaystyle\leq$ $\displaystyle L\gamma\tau+L\gamma\left\|v_{k-1}\right\|.$

If $\gamma\leq\frac{1-1/\sqrt{2}}{L\left(1+\sqrt{1+2\beta_{1}}\right)}$ where
$\beta_{1}=\frac{(1-\eta)^{2}(1+2/\eta)}{[1-(1-\eta)(1-\eta/2)]}$, then from
Claim F.3 (clipping active at $k-1$) and from (46) (clipping inactive at
$k-1$)

$\displaystyle\|v_{k-1}\|\leq\max\left(\sqrt{\frac{4}{\gamma}\phi_{0}},\sqrt{\frac{2}{\gamma}\phi_{0}}\right)\leq\sqrt{\frac{4}{\gamma}\phi_{0}}.$

Note that for $k=0$, we have $\left\|v_{0}\right\|\leq\sqrt{4\phi_{0}/\gamma}$
due to $v_{-1}=0$. Therefore,

$\displaystyle\|\nabla f(x_{k+1})-v_{k}\|$ $\displaystyle\leq
L\gamma\tau+2L\sqrt{\gamma\phi_{0}}.$ (47)

In conclusion, $\|\nabla f(x_{k})-v_{k-1}\|\leq\tau$ implies $\|\nabla
f(x_{k+1})-v_{k}\|\leq\tau$ if $\gamma$ satisfies

$\displaystyle L\gamma\tau\leq\frac{\tau}{2}\quad\text{and}\quad
2L\sqrt{\gamma\phi_{0}}\leq\frac{\tau}{2}.$ (48)

From Claim F.4, we can express step-size conditions (48) equivalently as:

$\displaystyle\gamma\leq\frac{1}{2L}\quad\text{and}\quad\gamma\leq\frac{\tau^{2}}{4L^{2}\left[\sqrt{F_{0}}+\sqrt{F_{0}+\frac{\tau
G_{0}}{\sqrt{2\eta}L}}\right]^{2}},$

where $\eta=\frac{\tau}{\|\nabla f(x_{0})\|}$, $F_{0}=f(x_{0})-f_{\rm inf}$
and $G_{0}=|\|\nabla f(x_{0})\|-\tau|$. Putting all the conditions on $\gamma$
together, we obtain the results.

###  Appendix G Proof of Proposition 5.2

If $\|\nabla f(x_{0})\|\leq\tau$, then from (47) and step-size condition from
Theorem 5.3, we prove that the clipping operator is always turned off for all
$k\geq 0$, i.e., $\|\nabla f(x_{k})-v_{k-1}\|\leq\tau$ implying that
$v_{k}=\nabla f(x_{k})$ for all $k\geq 0$.

If $\|\nabla f(x_{0})\|>\tau$, then the clipping operator is turned on at the
beginning. Moreover, for all $k\geq 0$ such that $\|\nabla
f(x_{k})-v_{k-1}\|>\tau$ (clipping is turned on), we have from the derivation
of (44) and the step-size condition of Theorem 5.3

$\displaystyle\|\nabla f(x_{k})-v_{k-1}\|$ $\displaystyle\leq\|\nabla
f(x_{k-1})-v_{k-2}\|-\frac{\tau}{2}\leq\ldots\leq\|\nabla
f(x_{0})\|-k\frac{\tau}{2}.$

Therefore, the situation when $\tau<\|\nabla f(x_{k})-v_{k-1}\|$ is possible
only for $0\leq k<k^{\star}$ with $k^{\star}=\frac{2}{\tau}(\|\nabla
f(x_{0})\|-\tau)+1$. After that, the clipping operator always turns off, i.e.,
$\|\nabla f(x_{k})-v_{k-1}\|\leq\tau$ for $k\geq k^{\star}$.

###  Appendix H Proof of Theorem 5.3

Let $\hat{x}_{K}$ be selected uniformly at random from
$\\{x_{0},x_{1},\ldots,x_{K-1}\\}$. Then,

$\displaystyle\mathbf{E}\left[\|\nabla f(\hat{x}_{K})\|^{2}\right]$
$\displaystyle=\frac{1}{K}\sum_{k=0}^{K-1}\left\|\nabla f(x_{k})\right\|^{2}.$

From Theorem 5.3,

$\displaystyle\mathbf{E}\left[\|\nabla f(\hat{x}_{K})\|^{2}\right]$
$\displaystyle\leq\frac{2}{\gamma}\frac{1}{K}\sum_{k=0}^{K-1}(\phi_{k}-\phi_{k+1})=\frac{2(\phi_{0}-\phi_{K})}{\gamma
K}\leq\frac{2\phi_{0}}{\gamma K}.$

Next, we consider the case when

$\gamma=\min\left(\frac{1}{L(1+\sqrt{1+2\beta_{1}})},\frac{\tau^{2}}{4L^{2}\left[\sqrt{F_{0}}+\sqrt{\beta_{2}}\right]^{2}}\right).$

First, we have

$\displaystyle\beta_{1}$
$\displaystyle=\frac{(1-\eta)^{2}(1+\nicefrac{{2}}{{\eta}})}{1-(1-\eta)(1-\nicefrac{{2}}{{\eta}})}\leq\frac{1+\nicefrac{{2}}{{\eta}}}{1-(1-\eta)}=\frac{2}{\eta^{2}}+\frac{1}{\eta}={\cal
O}\left(\frac{1}{\eta^{2}}\right)={\cal O}\left(1+\frac{\|\nabla
f(x_{0})\|^{2}}{\tau^{2}}\right),$ $\displaystyle\beta_{2}$
$\displaystyle=F_{0}+\frac{\tau G_{0}}{\sqrt{2\eta}L}\leq
F_{0}+\frac{\tau\max(\|\nabla
f(x_{0})\|,\tau)}{\sqrt{2\max\left(1,\frac{\tau}{\|\nabla
f(x_{0})\|}\right)}L}=F_{0}+\frac{\tau\|\nabla
f(x_{0})\|\sqrt{\max\left(1,\frac{\tau}{\|\nabla
f(x_{0})\|}\right)}}{\sqrt{2}L}$ $\displaystyle={\cal
O}\left(F_{0}+\frac{\tau\|\nabla
f(x_{0})\|}{L}+\frac{\tau^{\nicefrac{{3}}{{2}}}\sqrt{\|\nabla
f(x_{0})\|}}{L}\right).$

Using this, we estimate $\nicefrac{{1}}{{\gamma}}$ as

$\displaystyle\frac{1}{\gamma}$
$\displaystyle=\max\left(L(1+\sqrt{1+2\beta_{1}}),\frac{4L^{2}\left[\sqrt{F_{0}}+\sqrt{\beta_{2}}\right]^{2}}{\tau^{2}}\right)$
$\displaystyle={\cal O}\left(L\left(1+\frac{\|\nabla
f(x_{0})\|}{\tau}\right)+\frac{L^{2}F_{0}}{\tau^{2}}+\frac{L\|\nabla
f(x_{0})\|}{\tau}+\frac{L\sqrt{\|\nabla f(x_{0})\|}}{\sqrt{\tau}}\right)$
$\displaystyle={\cal O}\left(L\left(1+\frac{\|\nabla
f(x_{0})\|}{\tau}\right)+\frac{L^{2}F_{0}}{\tau^{2}}\right).$

Therefore, since

$\displaystyle\frac{A}{\gamma}=\frac{1}{2[1-(1-\eta)(1-\eta/2)]}={\cal
O}\left(\frac{1}{\eta}\right)={\cal O}\left(1+\frac{\|\nabla
f(x_{0})\|}{\tau}\right)$

and

$\displaystyle\|\nabla f(x_{0})-v_{-1}\|^{2}=\|\nabla f(x_{0})\|^{2},$

we have

$\displaystyle\mathbf{E}\left[\|\nabla f(\hat{x}_{K})\|^{2}\right]$
$\displaystyle\leq\frac{2\phi_{0}}{\gamma K}=\frac{2\left(f(x_{0})-f_{\rm
inf}+A\|\nabla f(x_{0})-v_{-1}\|^{2}\right)}{\gamma K}$ $\displaystyle={\cal
O}\left(\frac{\left(1+\frac{\|\nabla
f(x_{0})\|}{\tau}\right)\max(LF_{0},\|\nabla
f(x_{0})\|^{2})+\frac{L^{2}(F_{0})^{2}}{\tau^{2}}}{K}\right),$

which concludes the proof.

###  Appendix I Multi-node  Clip21-GD

In this section we analyze the convergence for multi-node  Clip21-GD described
in Algorithm 2. Its update can be expressed as (21), where
$v_{k}=\frac{1}{n}\sum_{i=1}^{n}v_{k}^{i}$ and

$\displaystyle v_{k}^{i}=(1-\eta_{k}^{i})v_{k-1}^{i}+\eta_{k}^{i}\nabla
f_{i}(x_{k}).$ (49)

Here, $\eta_{k}^{i}=\min\left(1,\frac{\tau}{\left\|\nabla
f_{i}(x_{k})-v_{k-1}^{i}\right\|}\right)$. To facilitate our analysis, denote
$\mathcal{I}_{k}$ as the subset from $\\{1,2,\ldots,n\\}$ such that
$\left\|\nabla f_{i}(x_{k})-v_{k-1}^{i}\right\|>\tau$. Recall that the
Lyapunov function is

$\displaystyle\phi_{k}=f(x_{k})-f^{\text{inf}}+A\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla
f_{i}(x_{k})-v_{k}^{i}\right\|^{2},$ (50)

where $A=\frac{\gamma}{2[1-(1-\eta)(1-\eta/2)]}$.

####  I.1 Claims

We first establish several simple but helpful results.

######  Claim I.1.

Let each $f_{i}$ have $L_{i}$-Lipschitz gradient. Then, for $k\geq 0$,

$\displaystyle\left\|\nabla
f_{i}(x_{k+1})-v^{i}_{k}\right\|\leq\max\left\\{0,\left\|\nabla
f_{i}(x_{k})-v^{i}_{k-1}\right\|-\tau\right\\}+L_{\max}\gamma\left\|v_{k}\right\|.$
(51)

###### Proof.

From the definition of the Euclidean norm,

$\displaystyle\left\|\nabla f_{i}(x_{k+1})-v_{k}^{i}\right\|$
$\displaystyle\mathop{\leq}\limits^{\eqref{eq:triangle}}$
$\displaystyle\left\|\nabla f_{i}(x_{k})-v_{k}^{i}\right\|+\left\|\nabla
f_{i}(x_{k+1})-\nabla f_{i}(x_{k})\right\|$
$\displaystyle\mathop{=}\limits^{\eqref{eqn:v_k_distributed_equi}}$
$\displaystyle\left\|\nabla
f_{i}(x_{k})-v_{k-1}^{i}-{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{k})-v_{k-1}^{i})\right\|$ $\displaystyle+\left\|\nabla
f_{i}(x_{k+1})-\nabla f_{i}(x_{k})\right\|$
$\displaystyle\overset{(\text{Lemma~{}\ref{lem:clip}(ii)-(iii)})}{\leq}$
$\displaystyle\max\\{0,\left\|\nabla
f_{i}(x_{k})-v_{k-1}^{i}\right\|-\tau\\}+\left\|\nabla f_{i}(x_{k+1})-\nabla
f_{i}(x_{k})\right\|$ $\displaystyle\overset{\eqref{eq:L-smooth}}{\leq}$
$\displaystyle\max\\{0,\left\|\nabla
f_{i}(x_{k})-v_{k-1}^{i}\right\|-\tau\\}+L_{\max}\left\|x_{k+1}-x_{k}\right\|$
$\displaystyle\overset{\eqref{eq:8y98fd_08yfd}}{=}$
$\displaystyle\max\\{0,\left\|\nabla
f_{i}(x_{k})-v_{k-1}^{i}\right\|-\tau\\}+L_{\max}\gamma\left\|v_{k}\right\|.$

∎

######  Claim I.2.

Let $v_{-1}^{i}=0$ for all $i$, $\max_{i}\left\|\nabla
f_{i}(x_{0})\right\|:=B>\tau$ and $\gamma\leq 2/L$. Then,

$\displaystyle\left\|v_{0}\right\|\leq\sqrt{\frac{4}{\gamma}\phi_{0}}+2(B-\tau).$
(52)

###### Proof.

By the fact that
$v_{0}=\frac{1}{n}\sum_{i=1}^{n}v^{i}_{0}=\frac{1}{n}\sum_{i=1}^{n}{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{0}))$,

$\displaystyle\left\|v_{0}\right\|$
$\displaystyle\overset{\eqref{eq:triangle}}{\leq}$ $\displaystyle\left\|\nabla
f(x_{0})\right\|+\left\|\frac{1}{n}\sum_{i=1}^{n}{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{0}))-\nabla f(x_{0})\right\|$
$\displaystyle\overset{\eqref{eq:triangle}}{\leq}$ $\displaystyle\left\|\nabla
f(x_{0})\right\|+\frac{1}{n}\sum_{i=1}^{n}\left\|{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{0}))-\nabla f_{i}(x_{0})\right\|$
$\displaystyle\overset{(\text{Lemma~{}\ref{lem:clip}(ii)-(iii)})}{\leq}$
$\displaystyle\left\|\nabla
f(x_{0})\right\|+\frac{1}{n}\sum_{i=1}^{n}\max\\{0,\left\|\nabla
f_{i}(x_{0})\right\|-\tau\\}.$

If $\max_{i}\left\|\nabla f_{i}(x_{0})\right\|>\tau$ and $\gamma\leq 2/L$,
then

$\displaystyle\left\|v_{0}\right\|$ $\displaystyle\leq$
$\displaystyle\left\|\nabla f(x_{0})\right\|+B-\tau$ $\displaystyle\leq$
$\displaystyle\left\|\nabla f(x_{0})\right\|+2(B-\tau)$
$\displaystyle\overset{\eqref{eq:ssss}}{\leq}$
$\displaystyle\sqrt{2L[f(x_{0})-f^{\inf}]}+2(B-\tau)$
$\displaystyle\overset{\eqref{eqn:phi_multinode_noDPnoComp}}{\leq}$
$\displaystyle\sqrt{2L\phi_{0}}+2(B-\tau)$ $\displaystyle\leq$
$\displaystyle\sqrt{\frac{4}{\gamma}\phi_{0}}+2(B-\tau).$

∎

######  Claim I.3.

Fix $k\geq 1$. Let $f$ have $L$-Lipschitz gradient. Also suppose that
$\left\|\nabla f_{i}(x_{k})-v_{k-1}^{i}\right\|\leq{\max}_{i}\left\|\nabla
f_{i}(x_{0})\right\|:=B>\tau$ for $i\in\mathcal{I}_{k}$,
$\left\|v_{k-1}\right\|\leq\sqrt{\frac{4}{\gamma}\phi_{0}}+2(B-\tau)$,
$\left\|\nabla f(x_{k-1})\right\|\leq\sqrt{\frac{2}{\gamma}\phi_{0}}$, and
$\gamma\leq\frac{1-\frac{1}{\sqrt{2}}}{L}$. Then,

$\displaystyle\left\|v_{k}\right\|$ $\displaystyle\leq$
$\displaystyle\sqrt{\frac{4}{\gamma}\phi_{0}}+2(B-\tau).$ (53)

###### Proof.

From the definition of the Euclidean norm and by the fact that
$v_{k}=\frac{1}{n}\sum_{i=1}^{n}v^{i}_{k}$,

$\displaystyle\left\|v_{k}\right\|$
$\displaystyle\overset{\eqref{eqn:v_k_distributed_equi}}{=}$
$\displaystyle\left\|\frac{1}{n}\sum_{i=1}^{n}v_{k-1}^{i}+{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{k})-v_{k-1}^{i})\right\|$ $\displaystyle=$
$\displaystyle\left\|\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(x_{k})+[{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{k})-v_{k-1}^{i})-(\nabla f_{i}(x_{k})-v_{k-1}^{i})]\right\|$
$\displaystyle\overset{\eqref{eq:triangle}}{\leq}$ $\displaystyle\left\|\nabla
f(x_{k})\right\|+\frac{1}{n}\sum_{i=1}^{n}\left\|{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{k})-v_{k-1}^{i})-(\nabla f_{i}(x_{k})-v_{k-1}^{i})\right\|$
$\displaystyle\leq$ $\displaystyle\left\|\nabla
f(x_{k})\right\|+\frac{1}{n}\sum_{i=1}^{n}\max\\{0,\left\|\nabla
f_{i}(x_{k})-v_{k-1}^{i}\right\|-\tau\\}.$

If $\left\|\nabla f_{i}(x_{k})-v_{k-1}^{i}\right\|\leq{\max}_{i}\left\|\nabla
f_{i}(x_{0})\right\|:=B>\tau$ for $i\in\mathcal{I}_{k}$, then

$\displaystyle\left\|v_{k}\right\|$ $\displaystyle\leq$
$\displaystyle\left\|\nabla f(x_{k})\right\|+B-\tau$
$\displaystyle\overset{\eqref{eq:triangle}}{\leq}$ $\displaystyle\left\|\nabla
f(x_{k-1})\right\|+\left\|\nabla f(x_{k})-\nabla f(x_{k-1})\right\|+B-\tau$
$\displaystyle\overset{\eqref{eq:L-smooth}}{\leq}$ $\displaystyle\left\|\nabla
f(x_{k-1})\right\|+L\left\|x_{k}-x_{k-1}\right\|+B-\tau$
$\displaystyle\overset{\eqref{eq:8y98fd_08yfd}}{=}$
$\displaystyle\left\|\nabla
f(x_{k-1}))\right\|+L\gamma\left\|v_{k-1}\right\|+B-\tau.$

If $\left\|v_{k-1}\right\|\leq\sqrt{\frac{4}{\gamma}\phi_{0}}+2(B-\tau)$ and
$\left\|\nabla f(x_{k-1})\right\|\leq\sqrt{\frac{2}{\gamma}\phi_{0}}$, then

$\displaystyle\left\|v_{k}\right\|$ $\displaystyle\leq$
$\displaystyle(L\gamma+1/\sqrt{2})\sqrt{\frac{4}{\gamma}\phi_{0}}+(2L\gamma+1)(B-\tau).$

If $\gamma\leq\frac{1-\frac{1}{\sqrt{2}}}{L}$, then $\gamma\leq 1/(2L)$ and

$\displaystyle\left\|v_{k}\right\|$ $\displaystyle\leq$
$\displaystyle\sqrt{\frac{4}{\gamma}\phi_{0}}+2(B-\tau).$

∎

######  Claim I.4.

If

$\displaystyle
0<\gamma\leq\frac{\tau^{2}}{16L_{\max}^{2}(\sqrt{F_{0}}+\sqrt{F_{0}+\frac{G_{0}\tau}{2\sqrt{2\eta}L_{\max}}})^{2}},$
(54)

where $\eta\coloneqq\min\left\\{1,\frac{\tau}{\max_{i}\left\|\nabla
f_{i}(x_{0})\right\|}\right\\}$, $F_{0}:=f(x_{0})-f_{\inf}$ and
$G_{0}:=\sqrt{\frac{1}{n}\sum_{i=1}^{n}(\left\|\nabla
f_{i}(x_{0})\right\|-\tau)^{2}}$, then

$\displaystyle 4L_{\max}\sqrt{\gamma\phi_{0}}\leq\tau/2.$ (55)

###### Proof.

By the definition of $\phi_{0}$,

$\displaystyle 2L_{\max}\sqrt{\gamma\phi_{0}}$ $\displaystyle=$ $\displaystyle
2L_{\max}\sqrt{\gamma[f(x_{0})-f_{\inf}]+\gamma
A\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla f_{i}(x_{0})-v^{i}_{0}\right\|^{2}}$
$\displaystyle\leq$ $\displaystyle
2L_{\max}\sqrt{\gamma[f(x_{0})-f_{\inf}]+\frac{\gamma^{2}}{2\eta}\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla
f_{i}(x_{0})-v^{i}_{0}\right\|^{2}}.$

Since $v_{-1}^{i}=0$ for all $i$, we have
$v^{i}_{0}={\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{0}))$ and

$\displaystyle 2L_{\max}\sqrt{\gamma\phi_{0}}$
$\displaystyle\overset{(\text{Lemma~{}\ref{lem:clip}(ii)-(iii)})}{\leq}$
$\displaystyle
2L_{\max}\sqrt{\gamma[f(x_{0})-f_{\inf}]+\frac{\gamma^{2}}{2\eta}\frac{1}{n}\sum_{i=1}^{n}\max\\{0,\left\|\nabla
f_{i}(x_{0})\right\|-\tau\\}^{2}}$
$\displaystyle\overset{\eqref{eq:sqrt}}{\leq}$ $\displaystyle
2L_{\max}\sqrt{\gamma}\sqrt{F_{0}}+\gamma L_{\max}\sqrt{\frac{2}{\eta}}G_{0},$

where $F_{0}:=f(x_{0})-f_{\inf}$ and
$G_{0}:=\sqrt{\frac{1}{n}\sum_{i=1}^{n}(\left\|\nabla
f_{i}(x_{0})\right\|-\tau)^{2}}$.

Hence, any $\gamma>0$ satisfying

$\displaystyle 4L_{\max}\sqrt{\gamma}\sqrt{F_{0}}+\gamma
2L_{\max}\sqrt{\frac{2}{\eta}}G_{0}\leq\tau/2$ (56)

also satisfies $4L_{\max}\sqrt{\gamma\phi_{0}}\leq B/2$. Condition (56) can be
rewritten as:

$\displaystyle\frac{1}{\sqrt{\gamma}}-\frac{8\sqrt{F_{0}}}{\tau}L_{\max}-\sqrt{\gamma}\frac{4\sqrt{2}}{\sqrt{\eta}}\frac{G_{0}}{L_{\max}\tau}L_{\max}^{2}\geq
0.$

Finally, by Lemma D.4 with $L=L_{\max}$,
$\beta_{1}=\frac{8\sqrt{F_{0}}}{\tau}$ and
$\beta_{2}=\frac{4\sqrt{2}}{\sqrt{\eta}}\frac{G_{0}}{L_{\max}\tau}$, we have

$\displaystyle
0<\sqrt{\gamma}\leq\frac{\tau}{4L_{\max}(\sqrt{F_{0}}+\sqrt{F_{0}+\frac{G_{0}\tau}{2\sqrt{2\eta}L_{\max}}})}.$

By taking the square, we complete our proof. ∎

####  I.2 Proof of Theorem 5.6

We then derive the descent inequality

$\displaystyle\phi_{k+1}\leq\phi_{k}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2},$

for two possible cases: (1) when $|\mathcal{I}_{k}|>0$ and (2) when
$|\mathcal{I}_{k}|=0$.

###### Case (1): $|\mathcal{I}_{k}|>0$.

To derive the descent inequality we will show by induction the stronger
result: $\left\|\nabla f_{i}(x_{k})-v^{i}_{k-1}\right\|\leq B-\frac{k\tau}{2}$
for $i\in\mathcal{I}_{k}$, where $B\coloneqq\max_{i}\left\|\nabla
f_{i}(x_{0})\right\|$ and

$\phi_{k}\leq\phi_{k-1}-\frac{\gamma}{2}\left\|\nabla
f(x_{k-1})\right\|^{2}-\frac{\gamma}{4}\left\|v_{k-1}\right\|^{2}$ (57)

for any $k\geq 0$, where for notational convenience we assume that $\nabla
f_{i}(x_{-1})=v^{i}_{-1}=0$ and $\phi_{-1}=\phi_{0}$. The base of the
induction is trivial: when $k=0$ we have $\left\|\nabla
f_{i}(x_{k})-v^{i}_{k-1}\right\|=\left\|\nabla
f_{i}(x_{0})-v^{i}_{-1}\right\|=\left\|\nabla
f_{i}(x_{0})\right\|\leq\max_{i}\left\|\nabla f_{i}(x_{0})\right\|=B$ where
$B>\tau$ for $i\in\mathcal{I}_{-1}$ and (57) holds by definition. Next, we
assume that for some $k\geq 0$ inequalities $\left\|\nabla
f_{i}(x_{t})-v^{i}_{t-1}\right\|\leq B$ for $i\in\mathcal{I}_{t-1}$ and (57)
hold for $t=0,1,\ldots,k$.

Let $0\leq\phi_{k}\leq\phi_{0}$ for all $k\geq 0$. If $\gamma\leq 1/L$, then

$\displaystyle\left\|\nabla f(x_{k-1})\right\|^{2}$
$\displaystyle\mathop{\leq}\limits^{\eqref{eq:ssss}}$ $\displaystyle
2L[f(x_{k-1})-f_{\inf}]$
$\displaystyle\mathop{\leq}\limits^{\eqref{eq:Lyapunov-89d}}$ $\displaystyle
2L\phi_{k-1}$ $\displaystyle\leq$ $\displaystyle 2L\phi_{0}$
$\displaystyle\leq$ $\displaystyle\frac{2}{\gamma}\phi_{0}.$

If $\gamma\leq(1-1/\sqrt{2})/L$, then by using the above inequality, and also
Claim I.2 and I.3, for $k\geq 0$

$\displaystyle\left\|v_{k}\right\|\leq\sqrt{\frac{4}{\gamma}\phi_{0}}+2(B-\tau).$

Next, from the above inequality and from Claim I.1, for $i\in\mathcal{I}_{k}$

$\displaystyle\left\|\nabla f_{i}(x_{k+1})-v_{k}^{i}\right\|$
$\displaystyle\leq$ $\displaystyle\left\|\nabla
f_{i}(x_{k})-v_{k-1}^{i}\right\|-\tau+L_{\max}\gamma\left\|v_{k}\right\|$
$\displaystyle\leq$ $\displaystyle\left\|\nabla
f_{i}(x_{k})-v_{k-1}^{i}\right\|-\tau+L_{\max}\gamma\sqrt{\frac{4}{\gamma}\phi_{0}}+2L_{\max}\gamma(B-\tau)$
$\displaystyle=$ $\displaystyle\left\|\nabla
f_{i}(x_{k})-v_{k-1}^{i}\right\|-\tau+2L_{\max}\sqrt{\gamma\phi_{0}}+2L_{\max}\gamma(B-\tau).$

STEP: Small step-size

The above inequality and the inductive assumption imply for
$i\in\mathcal{I}_{k}$

$\displaystyle\left\|\nabla f_{i}(x_{k+1})-v^{i}_{k}\right\|\leq\left\|\nabla
f_{i}(x_{k})-v^{i}_{k-1}\right\|-\frac{\tau}{2}\leq B-\frac{(k+1)\tau}{2}$
(58)

if the step-size $\gamma>0$ satisfies

$\displaystyle 2L_{\max}\gamma(B-\tau)\leq
2L_{\max}\sqrt{\gamma\phi_{0}}\quad\text{and}\quad
4L_{\max}\sqrt{\gamma\phi_{0}}\leq\tau/2.$

By Claim I.4, this condition can be expressed equivalently as:

$\displaystyle\gamma\leq\frac{\phi_{0}}{(B-\tau)^{2}}\quad\text{and}\quad\gamma\leq\frac{\tau^{2}}{16L_{\max}^{2}(\sqrt{F_{0}}+\sqrt{F_{0}+\frac{G_{0}\tau}{2\sqrt{2\eta}L_{\max}}})^{2}}.$

In conclusion, under this step-size condition, $\left\|\nabla
f_{i}(x_{k})-v^{i}_{k-1}\right\|\leq B$ for $i\in\mathcal{I}_{k-1}$ and $k\geq
0$. In addition, $\mathcal{I}_{k+1}\subseteq\mathcal{I}_{k}$.

STEP: Descent inequality

It remains to prove the descent inequality. By the inductive assumption proved
above, we then have for $i\in\mathcal{I}_{k+1}$,

$\displaystyle\eta^{i}_{k+1}=\frac{\tau}{\left\|\nabla
f_{i}(x_{k+1})-v^{i}_{k}\right\|}\geq\frac{\tau}{B}=\eta.$ (59)

Therefore,

$\displaystyle\left\|\nabla f_{i}(x_{k+1})-v^{i}_{k+1}\right\|^{2}$
$\displaystyle\overset{\eqref{eqn:v_k_distributed_equi}}{=}$ $\displaystyle
0\cdot\mathbbm{1}(i\in\mathcal{I}_{k+1}^{\prime})+(1-\eta^{i}_{k+1})^{2}\left\|\nabla
f_{i}(x_{k+1})-v^{i}_{k}\right\|^{2}\cdot\mathbbm{1}(i\in\mathcal{I}_{k+1})$
$\displaystyle\overset{\eqref{eqn:eta_multinode_case_on}}{\leq}$
$\displaystyle
0\cdot\mathbbm{1}(i\in\mathcal{I}_{k+1}^{\prime})+(1-\eta)^{2}\left\|\nabla
f_{i}(x_{k+1})-v^{i}_{k}\right\|^{2}\cdot\mathbbm{1}(i\in\mathcal{I}_{k+1})$
$\displaystyle\leq$ $\displaystyle(1-\eta)^{2}\left\|\nabla
f_{i}(x_{k+1})-v^{i}_{k}\right\|^{2}$
$\displaystyle\overset{\eqref{eq:Young}}{\leq}$
$\displaystyle(1+\theta)(1-\eta)^{2}\left\|\nabla
f_{i}(x_{k})-v^{i}_{k}\right\|^{2}$
$\displaystyle+(1+\nicefrac{{1}}{{\theta}})(1-\eta)^{2}\left\|\nabla
f_{i}(x_{k+1})-\nabla f_{i}(x_{k})\right\|^{2}$
$\displaystyle\overset{\eqref{eq:L_i-smooth}}{\leq}$
$\displaystyle(1+\theta)(1-\eta)^{2}\left\|\nabla
f_{i}(x_{k})-v^{i}_{k}\right\|^{2}$
$\displaystyle+(1+\nicefrac{{1}}{{\theta}})(1-\eta)^{2}L_{\max}^{2}\left\|x_{k+1}-x_{k}\right\|^{2}$

where $\theta>0$. Taking $\theta=\nicefrac{{\eta}}{{2}}$ and applying
inequality $(1-\eta)(1+\nicefrac{{\eta}}{{2}})\leq 1-\nicefrac{{\eta}}{{2}}$,
we get

$\displaystyle\left\|\nabla f_{i}(x_{k+1})-v^{i}_{k+1}\right\|^{2}$
$\displaystyle\leq$
$\displaystyle(1-\eta)(1-\nicefrac{{\eta}}{{2}})\left\|\nabla
f_{i}(x_{k})-v^{i}_{k}\right\|^{2}$ (60)
$\displaystyle+(1+\nicefrac{{2}}{{\eta}})(1-\eta)^{2}L_{\max}^{2}\left\|x_{k+1}-x_{k}\right\|^{2}.$

Next, we combine the above inequality with Lemma D.3:

$\displaystyle\phi_{k+1}$ $\displaystyle=$ $\displaystyle
f(x_{k+1})-f_{\inf}+A\frac{1}{n}\sum_{i=1}^{n}\|\nabla
f_{i}(x_{k+1})-v^{i}_{k+1}\|^{2}$
$\displaystyle\mathop{\leq}\limits^{\eqref{eq:descent_ineq}}$ $\displaystyle
f(x_{k})-f_{\inf}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}-\left(\frac{1}{2\gamma}-\frac{L}{2}\right)\left\|x_{k+1}-x_{k}\right\|^{2}$
$\displaystyle+\frac{\gamma}{2}\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla
f_{i}(x_{k})-v^{i}_{k}\right\|^{2}+A\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla
f_{i}(x_{k+1})-v^{i}_{k+1}\right\|^{2}$ $\displaystyle=$
$\displaystyle\phi_{k}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}-\left(\frac{1}{2\gamma}-\frac{L}{2}\right)\left\|x_{k+1}-x_{k}\right\|^{2}$
$\displaystyle+\left(\frac{\gamma}{2}-A\right)\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla
f_{i}(x_{k})-v^{i}_{k}\right\|^{2}+A\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla
f_{i}(x_{k+1})-v^{i}_{k+1}\right\|^{2}$
$\displaystyle\mathop{\leq}\limits^{\eqref{eqn:TrickFromEF21_multinode}}$
$\displaystyle\phi_{k}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}-\left(\frac{1}{2\gamma}-\frac{L}{2}-A\left(1+\frac{2}{\eta}\right)(1-\eta)^{2}(L_{\max})^{2}\right)\left\|x_{k+1}-x_{k}\right\|^{2}$
$\displaystyle+\left(\frac{\gamma}{2}+A(1-\eta)(1-\eta/2)-A\right)\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla
f_{i}(x_{k})-v^{i}_{k}\right\|^{2}.$

Since $A=\frac{\gamma}{2[1-(1-\eta)(1-\eta/2)]}$, we get

$\displaystyle\phi_{k+1}\leq\phi_{k}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}-\frac{1}{2\gamma}\left(1-\gamma
L-\gamma^{2}\cdot\frac{(1+2/\eta)(1-\eta)^{2}}{[1-(1-\eta)(1-\eta/2)]}(L_{\max})^{2}\right)\left\|x_{k+1}-x_{k}\right\|^{2}.$

If the step-size $\gamma$ satisfies

$\displaystyle
0<\gamma\leq\frac{1}{L\left(1+\sqrt{1+2\frac{(1-\eta)^{2}(1+2/\eta)}{[1-(1-\eta)(1-\eta/2)]}\left(\frac{L_{\max}}{L}\right)^{2}}\right)},$

then from Lemma D.4 with $L=1$, $\beta_{1}=2L$ and
$\beta_{2}=2\frac{(1-\eta)^{2}(1+2/\eta)}{[1-(1-\eta)(1-\eta/2)]}(L_{\max})^{2}$,
this condition implies $1-\gamma
L-\gamma^{2}\cdot\frac{(1-\eta)^{2}(1+2/\eta)}{[1-(1-\eta)(1-\eta/2)]}(L_{\max})^{2}\geq\frac{1}{2}$
and thus

$\displaystyle\phi_{k+1}\leq\phi_{k}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}-\frac{1}{4\gamma}\left\|x_{k+1}-x_{k}\right\|^{2}.$

Since $x_{k+1}-x_{k}=-\gamma v_{k}$,

$\displaystyle\phi_{k+1}$
$\displaystyle\leq\phi_{k}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}-\frac{\gamma}{4}\left\|v_{k}\right\|^{2}.$ (61)

This concludes the proof in the case (1).

###### Case (2): $|\mathcal{I}_{k}|=0$.

Suppose $|\mathcal{I}_{k}|=0$. Then, $\left\|\nabla
f_{i}(x_{k})-v^{i}_{k-1}\right\|\leq\tau$ for all $i$. Then, by using (49) and
by the fact that $\eta_{k}^{i}=\eta=1$, we have $v_{k}^{i}=\nabla
f_{i}(x_{k})$. Therefore,  Clip21-GD described in Algorithm 2 reduces to
classical gradient descent at step $k$. From the definition of $\phi_{k}$ and
Lemma D.3,

$\displaystyle\phi_{k+1}$ $\displaystyle=f(x_{k+1})-f_{\inf}$
$\displaystyle\mathop{\leq}\limits^{\eqref{eq:descent_ineq}}f(x_{k})-f_{\inf}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}-\left(\frac{1}{2\gamma}-\frac{L}{2}\right)\left\|x_{k+1}-x_{k}\right\|^{2}+\frac{\gamma}{2}\left\|\nabla
f(x_{k})-v_{k}\right\|^{2}$
$\displaystyle\leq\phi_{k}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}-\left(\frac{1}{2\gamma}-\frac{L}{2}\right)\left\|x_{k+1}-x_{k}\right\|^{2}.$

If $\gamma\leq 1/L$, then

$\displaystyle\phi_{k+1}$
$\displaystyle\leq\phi_{k}-\frac{\gamma}{2}\left\|\nabla
f(x_{k})\right\|^{2}.$ (62)

Therefore, $0\leq\phi_{k}\leq\phi_{0}$ and

$\displaystyle\left\|\nabla f(x_{k})\right\|$
$\displaystyle\leq\sqrt{\left\|\nabla
f(x_{k})\right\|^{2}}\leq\sqrt{\frac{2}{\gamma}[\phi_{k}-\phi_{k+1}]}\leq\sqrt{\frac{2}{\gamma}\phi_{k}}\leq\sqrt{\frac{2}{\gamma}\phi_{0}}.$

Finally, we will show that $\left\|\nabla
f_{i}(x_{k})-v^{i}_{k-1}\right\|\leq\tau$ for all $i$ implies $\|\nabla
f_{i}(x_{k+1})-v^{i}_{k}\|\leq\tau$ for all $i$. Indeed, in this case, we have
$v^{i}_{k}=\nabla f_{i}(x_{k})$ and

$\displaystyle\left\|\nabla f_{i}(x_{k+1})-v^{i}_{k}\right\|$
$\displaystyle\overset{\eqref{eq:L_i-smooth}}{\leq}$ $\displaystyle
L_{\max}\left\|x_{k+1}-x_{k}\right\|$ $\displaystyle=$ $\displaystyle
L_{\max}\gamma\left\|\nabla f(x_{k})\right\|$
$\displaystyle\overset{\eqref{eq:triangle}}{\leq}$ $\displaystyle
L_{\max}\gamma\left\|\nabla
f(x_{k})-v_{k-1}\right\|+L_{\max}\gamma\left\|v_{k-1}\right\|$
$\displaystyle\overset{\eqref{eq:triangle}}{\leq}$ $\displaystyle
L_{\max}\gamma\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla
f_{i}(x_{k})-v^{i}_{k-1}\right\|+L_{\max}\gamma\|v_{k-1}\|$
$\displaystyle\leq$ $\displaystyle
L_{\max}\gamma\tau+L_{\max}\gamma\left\|v_{k-1}\right\|.$

If $\gamma\leq\frac{1}{L(1+\sqrt{1+2\beta_{1})}}$ where
$\beta_{1}=\frac{(1-\eta)^{2}(1+2/\eta)}{[1-(1-\eta)(1-\eta/2)]}\left(\frac{L_{\max}}{L}\right)^{2}$,
then from Claim I.3 and (62),

$\displaystyle\left\|v_{k-1}\right\|\leq\sqrt{\frac{4}{\gamma}\phi_{0}}+2(B-\tau).$

Note that for $k=0$ the above inequality also holds due to $v_{-1}=0$ (see
Claim I.2). Hence, for all $i$

$\displaystyle\left\|\nabla f_{i}(x_{k+1})-v^{i}_{k}\right\|$
$\displaystyle\leq$ $\displaystyle
L_{\max}\gamma\tau+2L_{\max}\sqrt{\gamma\phi_{0}}+2L_{\max}\gamma(B-\tau)$
(63) $\displaystyle\leq$ $\displaystyle
2L_{\max}\sqrt{\gamma\phi_{0}}+2L_{\max}\gamma B$

In conclusion, $\left\|\nabla f_{i}(x_{k+1})-v^{i}_{k}\right\|\leq\tau$ is
true for all $i$ if $\gamma$ satisfies

$\displaystyle 2L_{\max}\gamma B\leq\frac{\tau}{2}\quad\text{and}\quad
2L_{\max}\sqrt{\gamma\phi_{0}}\leq\frac{\tau}{2}.$ (64)

From Claim I.4, the condition (64) is hence satisfied when

$\displaystyle\gamma\leq\frac{\tau}{4BL_{\max}}\quad\text{and}\quad\gamma\leq\frac{\tau^{2}}{16L_{\max}^{2}(\sqrt{F_{0}}+\sqrt{F_{0}+\frac{G_{0}\tau}{2\sqrt{2\eta}L_{\max}}})^{2}},$

where $\eta\coloneqq\min\left\\{1,\frac{\tau}{\max_{i}\left\|\nabla
f_{i}(x_{0})\right\|}\right\\}$, $F_{0}:=f(x_{0})-f_{\inf}$ and
$G_{0}:=\sqrt{\frac{1}{n}\sum_{i=1}^{n}(\left\|\nabla
f_{i}(x_{0})\right\|-\tau)^{2}}$. Putting all the conditions on $\gamma$
together, we obtain the results.

###  Appendix J Proof of Proposition 5.5

If $\|\nabla f_{i}(x_{0})\|\leq\tau$, then from (63) and step-size condition
from Lemma 5.4, we prove that the clipping operator is always turned off for
all $k\geq 0$, i.e., $\|\nabla f_{i}(x_{k})-v^{i}_{k-1}\|\leq\tau$ implying
that $v^{i}_{k}=\nabla f_{i}(x_{k})$ for all $k\geq 0$.

If $\|\nabla f_{i}(x_{0})\|>\tau$, then the clipping operator is turned on at
the beginning. Moreover, for all $k\geq 0$ such that $\|\nabla
f_{i}(x_{k})-v^{i}_{k-1}\|>\tau$ (clipping is turned on), we have from the
derivation of (58) and the step-size condition of Lemma 5.4

$\displaystyle\|\nabla f_{i}(x_{k})-v^{i}_{k-1}\|$ $\displaystyle\leq\|\nabla
f_{i}(x_{k-1})-v^{i}_{k-2}\|-\tau/2\leq\ldots\leq\|\nabla
f_{i}(x_{0})\|-k\tau/2.$

Therefore, the situation when $\tau<\|\nabla f_{i}(x_{k})-v^{i}_{k-1}\|$ is
possible only for $0\leq k<k^{\star}$ with $k^{\star}=\frac{2}{\tau}(\|\nabla
f_{i}(x_{0})\|-\tau)+1$. After that, the clipping operator always turns off,
i.e., $\|\nabla f_{i}(x_{k})-v^{i}_{k-1}\|\leq\tau$ for $k\geq k^{\star}$.

###  Appendix K Proof of Theorem 5.6

Let $\hat{x}_{K}$ be selected uniformly at random from
$\\{x_{0},x_{1},\ldots,x_{K-1}\\}$. Then,

$\displaystyle\mathbf{E}\left[\|\nabla f(\hat{x}_{K})\|^{2}\right]$
$\displaystyle=\frac{1}{K}\sum_{k=0}^{K-1}\left\|\nabla f(x_{k})\right\|^{2}.$

From Lemma 5.4,

$\displaystyle\mathbf{E}\left[\|\nabla f(\hat{x}_{K})\|^{2}\right]$
$\displaystyle\leq\frac{2}{\gamma}\frac{1}{K}\sum_{k=0}^{K-1}(\phi_{k}-\phi_{k+1})=\frac{2(\phi_{0}-\phi_{K})}{\gamma
K}\leq\frac{2\phi_{0}}{\gamma K}.$

Next, we consider the case when $\phi_{0}$ is very large. Then,

$\gamma\leq\min\left(\frac{1}{L}\frac{1}{1+\sqrt{1+2\beta_{1}}},\frac{\tau^{2}}{16L_{\max}^{2}\left[\sqrt{F_{0}}+\sqrt{\beta_{2}}\right]^{2}}\right).$

First, we have $\frac{1}{\eta}=\mathcal{O}(1+\frac{\max_{i}\|\nabla
f_{i}(x_{0})\|}{\tau})$ and

$\displaystyle\beta_{1}$
$\displaystyle\leq\frac{(1-\eta)^{2}(1+\nicefrac{{2}}{{\eta}})}{1-(1-\eta)(1-\nicefrac{{2}}{{\eta}})}\leq\frac{1+\nicefrac{{2}}{{\eta}}}{1-(1-\eta)}=\frac{2}{\eta^{2}}+\frac{1}{\eta}={\cal
O}\left(\frac{1}{\eta^{2}}\right)={\cal O}\left(1+\frac{(\max_{i}\|\nabla
f_{i}(x_{0})\|)^{2}}{\tau^{2}}\right),$ $\displaystyle\beta_{2}$
$\displaystyle=F_{0}+\frac{\tau G_{0}}{\sqrt{2\eta}L_{\max}}\leq
F_{0}+\frac{1}{\sqrt{2}}\frac{\tau\max(\tau,\max_{i}\|\nabla
f_{i}(x_{0})\|)}{\sqrt{\max\left(1,\frac{\tau}{\max_{i}\|\nabla
f_{i}(x_{0})\|}\right)}L_{\max}}$
$\displaystyle=F_{0}+\frac{1}{\sqrt{2}}\frac{\tau\max_{i}\|\nabla
f_{i}(x_{0})\|\sqrt{\max\left(1,\frac{\tau}{\max_{i}\|\nabla
f_{i}(x_{0})\|}\right)}}{L_{\max}}$ $\displaystyle={\cal
O}\left(F_{0}+\frac{\tau\max_{i}\|\nabla
f_{i}(x_{0})\|}{L_{\max}}+\frac{\tau^{3/2}{\max_{i}\|\nabla
f_{i}(x_{0})\|}^{1/2}}{L_{\max}}\right).$

Using this, we estimate $\nicefrac{{1}}{{\gamma}}$ as

$\displaystyle\frac{1}{\gamma}=\max\left(L(1+\sqrt{1+2\beta_{1}}),\frac{16(L_{\max})^{2}\left[\sqrt{F_{0}}+\sqrt{\beta_{2}}\right]^{2}}{\tau^{2}}\right)$
$\displaystyle={\cal O}\left(L\left(1+\frac{\max_{i}\|\nabla
f_{i}(x_{0})\|}{\tau}\right)+\frac{(L_{\max})^{2}F_{0}}{\tau^{2}}+T\right)$
$\displaystyle={\cal
O}\left(\max(L,L_{\max})\left(1+\sqrt{\tau\max_{i}\left\|\nabla
f_{i}(x_{0})\right\|}\right)+\frac{(L_{\max})^{2}F_{0}}{\tau^{2}}\right),$

where $T=\frac{L_{\max}\max_{i}\|\nabla
f_{i}(x_{0})\|}{\tau}+L_{\max}\sqrt{\tau\max_{i}\left\|\nabla
f_{i}(x_{0})\right\|}$. Therefore, since

$\displaystyle\frac{A}{\gamma}=\frac{1}{2[1-(1-\eta)(1-\eta/2)]}={\cal
O}\left(\frac{1}{\eta}\right)={\cal O}\left(1+\frac{\max_{i}\|\nabla
f_{i}(x_{0})\|}{\tau}\right)$

and

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\|\nabla
f_{i}(x_{0})-v^{i}_{-1}\|^{2}=\frac{1}{n}\sum_{i=1}^{n}\|\nabla
f_{i}(x_{0})\|^{2}={\cal O}(\max_{i}\|\nabla f_{i}(x_{0})\|^{2}),$

we have

$\displaystyle\mathbf{E}\left[\|\nabla f(\hat{x}_{K})\|^{2}\right]$
$\displaystyle\leq\frac{2\phi_{0}}{\gamma K}=\frac{2\left(f(x_{0})-f_{\rm
inf}+A\frac{1}{n}\sum_{i=1}^{n}\|\nabla
f_{i}(x_{0})-v^{i}_{-1}\|^{2}\right)}{\gamma K}$ $\displaystyle={\cal
O}\left(\frac{\left(1+\frac{\max_{i}\|\nabla
f_{i}(x_{0})\|}{\tau}\right)\max(F_{0}\max(L_{\max},L),\max_{i}\|\nabla
f_{i}(x_{0})\|^{2})+\frac{(L_{\max})^{2}(F_{0})^{2}}{\tau^{2}}}{K}\right).$

###  Appendix L Adding Gaussian Noise for DP Guarantees

Algorithm 3 DP-Clip21-GD (Error Feedback for DP Optimization with Clipping)

1: Input: initial iterate $x_{0}\in\mathbb{R}^{d}$; learning rate $\gamma>0$;
initial gradient shifts $v^{1}_{-1},\dots,v^{n}_{-1}\in\mathbb{R}^{d}$;
clipping threshold $\tau>0$; variance $\sigma^{2}>0$; variance bound $\nu>0$

2: for $k=0,1,2,\dots,K-1$ do

3: Broadcast $x_{k}$ to all workers

4: for each worker $i=1,\ldots,n$ in parallel do

5: Sample $\zeta_{k-1}^{i}\sim\mathcal{N}(0,\sigma^{2})$

6: Set
$z_{k-1}^{i}={\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\nu}(\zeta_{k-1}^{i})$

7: Compute
$g_{k}^{i}={\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{k})-v^{i}_{k-1})+z_{k-1}^{i}$

8: Update $v^{i}_{k}=v^{i}_{k-1}+g_{k}^{i}$

9: end for

10: $v_{k}=v_{k-1}+\frac{1}{n}\sum_{i=1}^{n}g_{k}^{i}$

11: $x_{k+1}=x_{k}-\gamma\frac{1}{n}\sum_{i=1}^{n}v^{i}_{k}$

12: end for

In this section, we extend  Clip21-GD to solve the problem under target
privacy budget. We call this new method  DP-Clip21-GD – it is described in
detail as Algorithm 3. Notice that  DP-Clip21-GD with $\sigma^{2}=0$ reduces
to  Clip21-GD.

Given a certain condition on the Gaussian noise, we first derive a privacy
guarantee by Theorem 3.4 of [chen2022bounded], which gives an $\epsilon$-DP
guarantee for the bounded Gaussian mechanism, and by the advanced composition
theorem in Corollary 3.21 of [dwork2014algorithmic].

######  Theorem L.1 (Privacy guarantee).

Let $0<\epsilon<1$, $\delta>0$, $0<\alpha<1$, and $\tau\geq 6\nu\geq 6\sigma$
satisfy

$\textstyle\delta\geq\exp\left(-\frac{1}{2K}\left[\frac{\epsilon}{\max(P_{1},P_{2})}\right]^{2}\right),$

where $P_{1}\coloneqq\frac{2\ln(\Delta C(\tau/6,c^{\star}))}{\alpha}$,
$P_{2}\coloneqq\frac{72\tau^{2}}{(1-\alpha)\tau}$, $K$ is the number of steps
and $c^{\star}$ is the solution to the following problem:

$\displaystyle\textstyle\max_{c}$ $\displaystyle\textstyle\quad\Delta
C(\sqrt{\min(\sigma^{2},\nu^{2})},c)\coloneqq\frac{C(a,\sqrt{\min(\sigma^{2},\nu^{2})})}{C(a+c,\sqrt{\min(\sigma^{2},\nu^{2})})}$
subject to $\displaystyle\textstyle\quad 0\leq c\leq
b-a\quad\text{and}\quad\|c\|\leq 2\tau.$

Here, each element of $a\in\mathbb{R}^{d}$ is
$-\nicefrac{{\tau}}{{\sqrt{d}}}$, each element of $b\in\mathbb{R}^{d}$ is
$\nicefrac{{\tau}}{{\sqrt{d}}}$, and

$\textstyle
C(y,\sigma)\coloneqq\left(\int_{a}^{b}\exp\left(-\frac{\left\|x-y\right\|^{2}}{\sigma^{2}}\right)\;dx\right)^{-1}.$

Then,  DP-Clip21-GD is $(\epsilon,\delta)$-differentially private for

$\textstyle\min(\nu^{2},\sigma^{2})\geq\frac{12\tau^{2}\sqrt{2K\ln(1/\delta)}}{(1-\alpha)\epsilon}\coloneqq\sigma^{2}_{\min}(K).$
(65)

The utility guarantee, presented next, can thus be obtained by substituting
$\sigma^{2}$ from Theorem L.1 into our convergence theorem, which we present
in Theorem M.1.

######  Theorem L.2 (Utility guarantee).

Consider the problem of solving (1). Suppose that each $f_{i}$ is
$L_{i}$-Lipschitz gradient, and that $f$ is $L$-Lipschitz gradient and
satisfies the PŁ condition, i.e., there exists $\mu>0$ such that

$\textstyle f(x)-f_{\star}\leq\frac{1}{2\mu}\left\|\nabla
f(x)\right\|^{2},\;\forall x\in\mathbb{R}^{d},$

where $f_{\star}\coloneqq\min_{x}f(x)$. Choose
$\nu\leq\frac{\tau}{2(\sqrt{2LC}+2)}$ and let $v_{-1}^{i}=0$ for all
$i\in[n]$, $\eta\coloneqq\min\left\\{1,\frac{\tau}{\max_{i}\|\nabla
f_{i}(x_{0})\|}\right\\}$, $F_{0}\coloneqq f(x_{0})-f_{\star}$ and
$G_{0}\coloneqq\sqrt{\frac{1}{n}\sum_{i=1}^{n}(|\nabla
f_{i}(x_{0})-\tau|+\nu)^{2}}$. Choose the privacy variance $\sigma^{2}$
according to Theorem L.1,

$\displaystyle\textstyle\gamma\leq\min\left(\frac{\eta}{4\mu},\frac{2\mu}{L_{\max}^{2}},\frac{\phi_{0}}{(B-\tau/2)^{2}},\frac{1-1/\sqrt{2}}{L(1+\sqrt{1+8\beta_{1}})},\frac{\tau^{2}}{64L_{\max}^{2}\left[\sqrt{F_{0}}+\sqrt{\beta_{2}}\right]^{2}}\right)$
(66)

where
$\beta_{1}\coloneqq\frac{(1+2/\eta)(1-\eta)(1-\eta/2)}{\eta}\left(\frac{L_{\max}}{L}\right)^{2}$,
and $\beta_{2}\coloneqq F_{0}+\frac{\tau G_{0}}{2\sqrt{2\eta}L_{\max}}$. Then,
DP-Clip21-GD (described in Algorithm 3) satisfies

$\displaystyle\textstyle\mathbf{E}\left[\phi_{K}\right]\leq(1-\gamma\mu)^{K}\phi_{0}+A_{3}\sigma^{2}_{\min}(K),$
(67)

where $\sigma^{2}_{\min}(K)$ is as in (65),
$A_{3}\coloneqq\frac{1}{\eta\mu}{2(1+\frac{2}{\eta})}$ and

$\textstyle\phi_{k}\coloneqq
f(x_{k})-f_{\star}+\frac{2\gamma}{\eta}\frac{1}{n}\sum\limits_{i=1}^{n}\left\|\nabla
f_{i}(x_{k})-v_{k}^{i}\right\|^{2}.$

Here, $0\leq\phi_{k}\leq\phi_{0}+C\nu^{2}$ for some $C>0$.

###  Appendix M Convergence theorem for  DP-Clip21-GD

We derive the convergence theorem for  DP-Clip21-GD in Section L.

######  Theorem M.1.

Consider the problem of minimizing $f(x)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(x)$.
Suppose that each $f_{i}(x)$ is $L_{i}$-Lipschitz gradient, and that the whole
objective $f(x)$ is $L$-Lipschitz gradient and satisfies the PŁ condition,
i.e. there exists $\mu>0$ such that $f(x)-f_{\star}\leq\left\|\nabla
f(x)\right\|^{2}/(2\mu)$ where $f_{\star}=\min_{x}f(x)$. Let $v_{-1}^{i}=0$
for all $i$, $\eta\coloneqq\min\left(1,\frac{\tau}{\max_{i}\|\nabla
f_{i}(x_{0})\|}\right)$, $F_{0}\coloneqq f(x_{0})-f_{\star}$ and
$G_{0}\coloneqq\sqrt{\frac{1}{n}\sum_{i=1}^{n}(|\nabla
f_{i}(x_{0})-\tau|+\nu)^{2}}$. Then,  DP-Clip21-GD with
$\nu\leq\frac{\tau}{2(\sqrt{2LC}+2)}$ and

$\displaystyle\gamma\leq\min\left(\frac{\eta}{4\mu},\frac{2\mu}{L_{\max}^{2}},\frac{\phi_{0}}{(B-\tau/2)^{2}},\frac{1-1/\sqrt{2}}{L(1+\sqrt{1+8\beta_{1}})},\frac{\tau^{2}}{64L_{\max}^{2}\left[\sqrt{F_{0}}+\sqrt{\beta_{2}}\right]^{2}}\right)$
(68)

where
$\beta_{1}\coloneqq\frac{(1+2/\eta)(1-\eta)(1-\eta/2)}{\eta}\left(\frac{L_{\max}}{L}\right)^{2}$,
and $\beta_{2}\coloneqq F_{0}+\frac{\tau G_{0}}{2\sqrt{2\eta}L_{\max}}$
satisfies

$\displaystyle\mathbf{E}\left[\phi_{k+1}\right]\leq(1-\gamma\mu)\mathbf{E}\left[\phi_{k}\right]+\frac{2(1+2/\eta)}{\eta}\gamma\min(\nu^{2},\sigma^{2}),$
(69)

where $\phi_{k}\coloneqq
f(x_{k})-f^{\star}+\frac{2\gamma}{\eta}\frac{1}{n}\sum_{i=1}^{n}\|\nabla
f_{i}(x_{k})-v_{k}^{i}\|^{2}$ and $0\leq\phi_{k}\leq\phi_{0}+C\nu^{2}$ for
some $C>0$.

###  Appendix N Proof of Theorem M.1

The update of $v_{k}^{i}$ in  DP-Clip21-GD can be equivalently expressed as
(21), where $v_{k}=\frac{1}{n}\sum_{i=1}^{n}v_{k}^{i}$ and

$\displaystyle v_{k}^{i}=(1-\eta_{k}^{i})v_{k-1}^{i}+\eta_{k}^{i}\nabla
f_{i}(x_{k})+{z}_{k-1}^{i},$ (70)

where $\eta_{k}^{i}=\min\left(1,\frac{\tau}{\|\nabla
f_{i}(x_{k})-v_{k-1}^{i}\|}\right)$ and $\left\|z_{k-1}^{i}\right\|\leq\nu$.
Recall that the Lyapunov function for analyzing the result is

$\displaystyle\phi_{k}=f(x_{k})-f^{\star}+A\frac{1}{n}\sum_{i=1}^{n}\|\nabla
f_{i}(x_{k})-v_{k}^{i}\|^{2},$ (71)

where $A=\frac{2\gamma}{\eta}$.

####  N.1 Basic Claims

######  Claim N.1.

Let each $f_{i}$ have $L_{i}$-Lipschitz gradient. Then, for $k\geq 0$,

$\displaystyle\left\|\nabla
f_{i}(x_{k+1})-v_{k}^{i}\right\|\leq\max\\{0,\left\|\nabla
f_{i}(x_{k})-v_{k-1}^{i}\right\|-\tau\\}+\nu+L_{\max}\gamma\left\|v_{k}\right\|.$
(72)

###### Proof.

From the definition of $v_{k}^{i}$,

$\displaystyle\left\|\nabla f_{i}(x_{k+1})-v_{k}^{i}\right\|$
$\displaystyle\overset{\eqref{eq:triangle}}{\leq}$ $\displaystyle\left\|\nabla
f_{i}(x_{k})-v_{k}^{i}\right\|+\left\|\nabla f_{i}(x_{k+1})-\nabla
f_{i}(x_{k})\right\|$ $\displaystyle=$ $\displaystyle\left\|\nabla
f_{i}(x_{k})-v_{k-1}^{i}-{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{k})-v_{k-1}^{i})+z_{k-1}^{i}\right\|$ $\displaystyle+\left\|\nabla
f_{i}(x_{k+1})-\nabla f_{i}(x_{k})\right\|$
$\displaystyle\overset{\eqref{eq:triangle}}{\leq}$ $\displaystyle\left\|\nabla
f_{i}(x_{k})-v_{k-1}^{i}-{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{k})-v_{k-1}^{i})\right\|$
$\displaystyle+\left\|z_{k-1}^{i}\right\|+\left\|\nabla f_{i}(x_{k+1})-\nabla
f_{i}(x_{k})\right\|$
$\displaystyle\overset{(\text{Lemma~{}\ref{lem:clip}(ii)-(iii)})}{\leq}$
$\displaystyle\max\\{0,\left\|\nabla f_{i}(x_{k})-v_{k-1}^{i}\right\|-\tau\\}$
$\displaystyle+\left\|z_{k-1}^{i}\right\|+\left\|\nabla f_{i}(x_{k+1})-\nabla
f_{i}(x_{k})\right\|$ $\displaystyle\overset{\eqref{eq:L_i-
smooth}+\eqref{eq:8y98fd_08yfd}}{\leq}$ $\displaystyle\max\\{0,\left\|\nabla
f_{i}(x_{k})-v_{k-1}^{i}\right\|-\tau\\}+\nu+L_{\max}\gamma\left\|v_{k}\right\|.$

∎

######  Claim N.2.

Let $v_{-1}^{i}=0$ for all $i$, $\max_{i}\left\|\nabla
f_{i}(x_{0})\right\|:=B>\tau$, and $\gamma\leq 2/L$. Then,

$\displaystyle\left\|v_{0}\right\|\leq\sqrt{\frac{4}{\gamma}\phi_{0}}+2(B+\nu-\tau).$
(73)

###### Proof.

By the fact that
$v_{0}=\frac{1}{n}\sum_{i=1}^{n}v_{0}^{i}=\frac{1}{n}\sum_{i=1}^{n}[{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{0}))+z_{-1}^{i}]$,

$\displaystyle\left\|v_{0}\right\|$
$\displaystyle\overset{\eqref{eq:triangle}}{\leq}$ $\displaystyle\left\|\nabla
f(x_{0})\right\|+\frac{1}{n}\sum_{i=1}^{n}\left\|{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{0}))-\nabla
f_{i}(x_{0})\right\|+\frac{1}{n}\sum_{i=1}^{n}\left\|z_{-1}^{i}\right\|$
$\displaystyle\overset{\text{(Lemma~{}\ref{lem:clip}(ii)-(iii))}}{\leq}$
$\displaystyle\left\|\nabla
f(x_{0})\right\|+\frac{1}{n}\sum_{i=1}^{n}\max\\{0,\left\|\nabla
f_{i}(x_{0})\right\|-\tau\\}+\frac{1}{n}\sum_{i=1}^{n}\left\|z_{-1}^{i}\right\|$
$\displaystyle\leq$ $\displaystyle\left\|\nabla
f(x_{0})\right\|+\frac{1}{n}\sum_{i=1}^{n}\max\\{0,\left\|\nabla
f_{i}(x_{0})\right\|-\tau\\}+\nu.$

If $\left\|\nabla f_{i}(x_{k})-v_{k-1}^{i}\right\|\leq\max_{i}\left\|\nabla
f_{i}(x_{0})\right\|\coloneqq B>\tau$ and $\gamma\leq 2/L$, then

$\displaystyle\left\|v_{0}\right\|$ $\displaystyle\leq$
$\displaystyle\left\|\nabla f(x_{0})\right\|+B+\nu-\tau$
$\displaystyle\overset{\eqref{eq:ssss}}{\leq}$
$\displaystyle\sqrt{2L(f(x_{0})-f_{\inf})}+B+\nu-\tau$ $\displaystyle\leq$
$\displaystyle\sqrt{2L\phi_{0}}+B+\nu-\tau$ $\displaystyle\leq$
$\displaystyle\sqrt{\frac{4}{\gamma}\phi_{0}}+2(B+\nu-\tau).$

∎

######  Claim N.3.

Fix $k\geq 1$. Let $f$ have $L$-Lipschitz gradient. Also suppose that
$\left\|\nabla f_{i}(x_{k})-v_{k-1}^{i}\right\|\leq\max_{i}\left\|\nabla
f_{i}(x_{0})\right\|\coloneqq B>\tau$,
$\left\|v_{k-1}\right\|\leq\sqrt{\frac{4}{\gamma}\phi_{0}}+2(B+\nu-\tau)$,
$\left\|\nabla
f(x_{k-1})\right\|\leq\sqrt{\frac{2}{\gamma}\phi_{0}}+\sqrt{2LC}\nu$ for some
$C>0$, $\gamma\leq(1-1/\sqrt{2})/L$ and $\nu\leq\frac{\tau}{2(\sqrt{2LC}+2)}$.
Then,

$\displaystyle\left\|v_{k}\right\|\leq\sqrt{\frac{4}{\gamma}\phi_{0}}+2(B-\tau/2).$
(74)

###### Proof.

From the definition of $v_{k}$,

$\displaystyle v_{k}$ $\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}[v_{k-1}^{i}+{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{k})-v_{k-1}^{i})+z_{k-1}^{i}]$ $\displaystyle=$ $\displaystyle\nabla
f(x_{k})+\frac{1}{n}\sum_{i=1}^{n}[{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{k})-v_{k-1}^{i})-(\nabla f_{i}(x_{k})-v_{k-1}^{i})+z_{k-1}^{i}].$

Therefore,

$\displaystyle\left\|v_{k}\right\|$
$\displaystyle\overset{\eqref{eq:triangle}}{\leq}$ $\displaystyle\left\|\nabla
f(x_{k})\right\|+\frac{1}{n}\sum_{i=1}^{n}\left\|{\rm\sf\color[rgb]{0.76,0.01,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.76,0.01,0}\pgfsys@color@cmyk@stroke{0}{0.75}{1}{0.24}\pgfsys@color@cmyk@fill{0}{0.75}{1}{0.24}clip}_{\tau}(\nabla
f_{i}(x_{k})-v_{k-1}^{i})-(\nabla
f_{i}(x_{k})-v_{k-1}^{i})\right\|+\frac{1}{n}\sum_{i=1}^{n}\left\|z_{k-1}^{i}\right\|.$

By the fact that $\left\|z_{k-1}^{i}\right\|\leq\nu$ and by Lemma
4.1(ii)-(iii),

$\displaystyle\left\|v_{k}\right\|$ $\displaystyle\leq$
$\displaystyle\left\|\nabla
f(x_{k})\right\|+\nu+\frac{1}{n}\sum_{i=1}^{n}\max\\{0,\left\|\nabla
f_{i}(x_{k})-v_{k-1}^{i})\right\|-\tau\\}$
$\displaystyle\overset{\eqref{eq:triangle}}{\leq}$ $\displaystyle\left\|\nabla
f(x_{k-1})\right\|+\left\|\nabla f(x_{k})-\nabla
f(x_{k-1})\right\|+\nu+\frac{1}{n}\sum_{i=1}^{n}\max\\{0,\left\|\nabla
f_{i}(x_{k})-v_{k-1}^{i})\right\|-\tau\\}$
$\displaystyle\overset{\eqref{eq:8y98fd_08yfd}+\eqref{eq:L-smooth}}{\leq}$
$\displaystyle\left\|\nabla
f(x_{k-1})\right\|+L\gamma\left\|v_{k-1}\right\|+\nu+\frac{1}{n}\sum_{i=1}^{n}\max\\{0,\left\|\nabla
f_{i}(x_{k})-v_{k-1}^{i})\right\|-\tau\\}.$

If $\left\|\nabla f_{i}(x_{k})-v_{k-1}^{i}\right\|\leq\max_{i}\left\|\nabla
f_{i}(x_{0})\right\|\coloneqq B>\tau$, then

$\displaystyle\left\|v_{k}\right\|\leq\left\|\nabla
f(x_{k-1})\right\|+L\gamma\left\|v_{k-1}\right\|+\nu+B-\tau.$

If $\left\|v_{k-1}\right\|\leq\sqrt{\frac{4}{\gamma}\phi_{0}}+2(B+\nu-\tau)$,
$\left\|\nabla
f(x_{k-1})\right\|\leq\sqrt{\frac{2}{\gamma}\phi_{0}}+\sqrt{2LC}\nu$ for some
$C>0$, and $\gamma\leq(1-1/\sqrt{2})/L$, then we have $\gamma\leq 1/(2L)$ and

$\displaystyle\left\|v_{k}\right\|$ $\displaystyle\leq$
$\displaystyle(L\gamma+1/\sqrt{2})\sqrt{\frac{4}{\gamma}\phi_{0}}+(2L\gamma+1)(B-\tau)+(2L\gamma+\sqrt{2LC}+1)\nu$
$\displaystyle\leq$
$\displaystyle\sqrt{\frac{4}{\gamma}\phi_{0}}+2(B-\tau)+(\sqrt{2LC}+2)\nu.$

If $\nu\leq\frac{\tau}{2(\sqrt{2LC}+2)}$, then
$\left\|v_{k-1}\right\|\leq\sqrt{\frac{4}{\gamma}\phi_{0}}+2(B+\nu-\tau)\leq\sqrt{\frac{4}{\gamma}\phi_{0}}+2(B-\tau/2)$
and

$\displaystyle\left\|v_{k}\right\|$ $\displaystyle\leq$
$\displaystyle\sqrt{\frac{4}{\gamma}\phi_{0}}+2(B-\tau/2).$

∎

######  Claim N.4.

If

$\displaystyle
0\leq\gamma\leq\frac{\tau^{2}}{64L_{\max}^{2}\left(\sqrt{F_{0}}+\sqrt{F_{0}+\frac{G_{0}\tau}{2\sqrt{2\eta}L_{\max}}}\right)^{2}},$
(75)

where $\eta\coloneqq\min\left\\{1,\frac{\tau}{\max_{i}\left\|\nabla
f_{i}(x_{0})\right\|}\right\\}$, $F_{0}:=f(x_{0})-f(x^{\star})$ and
$G_{0}:=\sqrt{\frac{1}{n}\sum_{i=1}^{n}(|\nabla f_{i}(x_{0})-\tau|+\nu)^{2}}$,
then

$\displaystyle 4L_{\max}\sqrt{\gamma\phi_{0}}\leq\frac{\tau}{4}.$ (76)

###### Proof.

From the definition of $\phi_{0}$ and by the fact that $v_{-1}^{i}=0$ and that
$\left\|z^{i}_{k}\right\|\leq\nu$,

$\displaystyle 4L_{\max}\sqrt{\gamma\phi_{0}}$ $\displaystyle=$ $\displaystyle
4L_{\max}\sqrt{\gamma
F_{0}+\frac{2\gamma^{2}}{\eta}\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla
f_{i}(x_{0})-v^{i}_{0}\right\|^{2}}$ $\displaystyle=$ $\displaystyle
4L_{\max}\sqrt{\gamma
F_{0}+\frac{2\gamma^{2}}{\eta}\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla