An improved analysis of per-sample and per-update clipping in federated learning
Authors: Bo Li
Xiaowen Jiang
Mikkel N. Schmidt
Tommy Sonne Alstrøm
Sebastian U Stich
Venue: ICLR 2024 poster (2024)
Keywords: optimization
clipping
federated learning
decentralized learning
distributed optimization
Primary area: optimization
TL;DR: We rigorously and precisely analyze the impact of per-sample and per-update clipping on the convergence of FedAvg

Abstract: Gradient clipping is key mechanism that is essential to differentially private training techniques in Federated learning. Two popular strategies are per-sample clipping, which clips the mini-batch gradient, and per-update clipping, which clips each user's model update. However, there has not been a thorough theoretical analysis of these two clipping methods.

In this work, we rigorously analyze the impact of these two clipping techniques on the convergence of a popular federated learning algorithm FedAvg under standard stochastic noise and gradient dissimilarity assumptions. We provide a convergence guarantee given any arbitrary clipping threshold. Specifically, we show that per-sample clipping is guaranteed to converge to the neighborhood of the stationary point, with the size dependent on the stochastic noise, gradient dissimilarity, and clipping threshold. In contrast, the convergence to the stationary point can be guaranteed with a sufficiently small stepsize in per-update clipping at the cost of more communication rounds. We further provide insights into understanding the impact of the improved convergence analysis in the differentially private setting.

Published conference paper at ICLR 2024
AN IMPROVED ANALYSIS OF PER-SAMPLE AND PER- UPDATE CLIPPING IN FEDERATED LEARNING
Bo Li
Xiaowen Jiang" CISPA
Mikkel N. Schmidt
Tommy Alstrom DTUF
DTUF
DTU
bliaedtu.dk
xiaowen. hiannnniaageees.......
mnscedtu.ck
tsa (ddtu.dk
Sebastian U. Stich CISPA
stich@cispa.de
ABSTRACT
Gradient clipping is key mechanism that is essential to differentially private training techniques in Federated learning. Two popular strategies per-sample clipping, which clips the mini-batch gradient, and per-update clipping, which clips each user's model update. However, there has not been a thorough theoretical analysis of these two clipping methods. In this work, we rigorously analyze the impact of these two clipping techniques on the convergence of popular federated learn- ing algorithm FedAvg under standard stochastic noise and gradient dissimilarity assumptions. We provide convergence guarantee given any arbitrary clipping threshold. Specifically, we show that per-sample clipping is guaranteed con- verge to the neighborhood of the stationary point, with the size dependent on the stochastic noise, gradient dissimilarity, and clipping threshold. In contrast, the convergence to the stationary point can be guaranteed with sufficiently small stepsize in per-update clipping at the cost more communication rounds. We further provide insights into understanding the impact of the improved convergence analysis in the differentially private setting.
INTRODUCTION
Federated learning (FL) is an essential distributed learning scheme where workers collaboratively train a model without sharing their data (Acar et al. 2022] Kairouz et al. 2019 Karimireddy et al. 2019 McMahan et al. 2016). One of the popular federated optimization methods is FedAvg (McMahan central server in a series of rounds. However, existing works have shown that vanilla FedAvg is vulnerable to inference attacks as sensitive information can he extracted from the learned model parameters (Carlini et al. 2018) Fredrikson ct al. 2015 Nasr et al. 22018; Melis et al. (2088) Therefore, ensuring the model parameters not reveal input data distribution has attracted considerable interest (Andrew et al. 2021 McMahan et al.
al. 2016),, where locally trained models are averaged
2018 Choudhury al. 2019 Wei et al. 2019 Geyer et al. 2017).
way mitigate the risk information leakage is to bound the gradients (Andrew et al. 202 McMahan
Since each training example leave footprint the gradients (Nasr et al.
2018
et al. 2018) via gradient clipping (Zhang et al.] (2022) Koloskova el 20033. Two popular clipping strategies in FL are per- sampl clipping (Liu al. (022) and per-update clipping (McMahan al.) 2018 Andrew et al. 2021 Geyer et al., 2017] Wei et al. 2019). each local iteration, per-sample clipping limits the norm of the mini- batch gradient. In contrast, per-update clipping limits the overall local update in each round, which is the product of the stepsize and the sum of the mini batch gradients. Per-sample (when batch size I) and per-update clipping are commonly used
"Equal contribution
Work done while at CISPA TTechnical University of Demmark CCISAA Helmholtz Center for Information Security

---

Published a conference paper at ICLR 2024
achieve example-level (Abadi al., 2016; Choudhury et 2019) and user-level (MeMahan al. 2018 |eeer et al. 2017) differential privacy.
While tremendous efforts have been made to understand the influence of clipping on the convergence of optimization algorithms (Zhang et al. 22020b Koloskova et al. 2023] Zhang et al. 2020al Mai & Johansson 202 Zhang et al,, 2022; Liu et al.
2022). existing methods often imply a specific choice of c to guarantee convergence (Zhang ct al. (020b). To address this issue, Koloskova et al. (202)) studied the convergence behavior for clipped mini-batch SGD under any arbitrary clipping threshold on stochastic non-convex functions and established a tight convergence guarantee. However, the impact on federated learning is not yet known. Besides, prior theoretical results usually rely on uniformly bounded stochastic noise (Zhang et al. 2020b Crawshaw et al. 2023 Liu al.
2022) and bounded gradients (Zhang et al.] 2022) assumptions, which do not necessarily hold practice, especially in the training of deep neural networks (Gorbunov ct al. 22200; Siisskli et al.)
2019 Krizhevsky et al., (2012). Moreover, a formal theoretical analysis comparing the convergence
behavior of these two commonly used clipping operations in federated learning remains unexplored.
In this work, we precisely characterize the impact of the two commonly used clipping techniques: per-sample and per-update clipping, on the convergence of a popular federated optimization algorithm FedAvg (McMahan al. 2016)), under the standard bounded variance o² (Koloskova al., 2023
and gradient dissimilarity <² (Woodworth et al. 2020, Reddi et al. 2020 assumptions to inc lude heavy-tailed noise (Simsekli et 2019) and data heterogeneity scenarios (Kairouz et al., 2019).
We prove that per-sample clipping is guaranteed to converge neighborhood with the size dependent on the stochastic noise o, gradient dissimilarity & and the clipping threshold c. Specifically, the assurance of attaining any desired level of accuracy can only be achieved by selecting a sufficiently large value for the clipping threshold. This result is consistent and is extension of the work from Koloskova al. (023). which studied the convergence behavior clipped mini-batch SGD a single worker. Conversely, given any arhitrary clipping threshold, per-update clipping can converge to any accuracy level by choosing the appropriate stepsizes. We show that the main reason for the different behaviors the incorporation of an inner stepsize in per-update clipping. Consequently, one can develop a better per-sampling clipping algorithm based on this insight.
Contributions: we summarize our main contributions as below:
We rigorously analyze the impact of two popular clipping strategies: per-sample and per-update clipping. the convergence of FedAvg, under standard bounded variance and gradient dissimilar- ity assumptions.
We precisely characterize the impact of stochastic noise o² and data heterogeneity Ç² on the clipped FedAvg. Specifically, we show that per-sample clipping is guaranteed to converge a neighborhood of the stationary point, with the size being O(min(o + Ç. =²+()). We provide examples to show the tightness of the neighborhood size. On the other hand, given arbitrary clipping threshold c, per-update clipping can converge to any accuracy by picking the inner stepsize to be smaller than O (To+tT() where is the number of local steps.
We extend our theoretical results into the differentially private setting where a stochastic noise is injected into each step. We provide insights into understanding the impact of the and Ç for determining the appropriate stepsize and clipping thresholds to achieve better privacy-utility tra
We experimentally validate our theoretical statements under different levels of data heterogeneity.
1.1 RELATED WORK
Clipping in centralized learning: Clipping is popular technique that can enhance the stability of the optimization process (Dosovitskiy al. 2020 Mai & Johansson 202T You al. 2017 Pascanu et al.) 2012bba a (teeiner et al.) (021). Recently, numerous efforts have been made to understand clipping theoretically. Inspired by the practical observations from DNN training. Zhang et al. (2020b) proposed a new (Ln, Ly >-soothhnsss assumption and justified that gradient clipping can accelerate the convergence of SGD. Ziaagg et (2020a) and Mai & Johansson (202T) then extended the analysis to incorporate momentum methods for non moo-shooth functions. However, the above theoretical results rely strong assumption, namely every stochastic gradient falls into ball

---

Published conference paper at ICLR 2024
Table I: Convergence rate of for non-convex function f 1K + R, with I. deserihed the smoothness, given e. the clipping threshold, as the stepsize in per- per-sample clipping, 7/I and fl as the inner and outer stepsize in per-update clipping, Fú == fxx) f(x ), 7 as the numher of local steps, as the number of workers, R as the number of communication rounds, and T ;= R 7 the total number of iterations.
Algorithan
Comeeggnnes
Assuuptioz
Per ser-sa millugh [R/
SGD Kallaaanooo et al.
2023
(V* +
(vingle worker)
Clupped SGD Koloskova al.
2023
(/ 1+- vho - chi in minls 4))
Assumption
(single wocker)
TacalSCin Kolokknor al.
M020
1 +V To 70
Assumptio
workers)
Clipped LocalSGi
V/ Valea (
Assumptions 14.5 5
Domagernooss
FAT dlippinePP
V 1.r + GP En 1 +y ote-) Be (1.9)
Assumptio
momeen Yang etal.
2022
Fu
Ri. ne?
Lolla chillo" +C7
Oues
of
Asampion L
(posompppe)
(4, ohe mia (Tv/2 (2.)) min (o fo+ =2))
Per Per-upddate: mitn [0
P Karimireday al. vi
Ped//gg workers)
2019
Assumption
my I +25
+V R
ar
D (lo of1 + -g
Cligpo--Fedrra Fed Zhang al. (po-opdatt))
Zhang
2022
Avampiion L
(lot lot 07l of -00
FAT dlippine
Tivit (000--)) de [L.2
Assuuption
momen Yang al.
2022
+0+ O0trni 25 ())
Ours (pe-apdate)
Assungtion L
Bounded gradient assumes [F(x)] < G for all [n] and E Rd.
Uniformly bounded noise assumes V FF(()) [x(x]] S o² for a E [n] and x R".
Bounded dissimilarity assumes [xx) V S ç² for all [n] and x E R
8-moment assumes *[][V
I G for all i E [n] and x (8 and implies [V
of max((cm E Dlll o. max EE VIll
and a" := D E..
with a radius of a to the true (expected) gradients, which can hardly hold in many practical DNN- based applications (Simsekli et al.] 2019 Zhang et al., 2020c Krizhevsky al. 2012 Vaswani (et al. 2017). Therefore, [Gorbunov et al. 2020) relaxed this by introducing bounded variance expectation to include heavy-tailed noise. Nevertheless, the convergence guarantee above usually implies and requires specific value of the clipping threshold c, meaning must be tuned carefully to achieve the suggested convergence. Tuning clipping threshold, however, may raise other privacy Therefore,Kooloskvva
concerns (Andrew et al., (02T). Therefore, Koloskova et (2023) provided a convergence guarantee of using clipped SGD given any arbitrary clipping threshold to address this issue. In a stochastic setting. they demonstrated that the clipping bias can hamper the convergence to the true optimum.
Clipping for privacy protection in FL: Recent works have shown that vanilla FL algorithms are vulnerable to adversary attacks as it is possible to extract information from the participating users by looking at the parameters of trained model (Fredrikson al. [2015] Carlini al.] [2018] Melis al. 2018). Therefore, providing a certain level of privacy guarantee is crucial |ei et al. (2019); Abadi et al. (2016): McMahan et al. (2018). To make such promises, each data point (user) 's maximum contribution needs to be bounded (Bassily et al., 2019 Wang et al. 2018, Das al. 2022 Amin al. 2019). which is usually achieved by projecting larger updates back to ball of norm e using clipping. Two popular clipping operations are per-sample clipping and per-update clipping. Per-sample clipping clips the gradient of each data point to limit its influence on the model parameters, (Liu et all, (022). which can protect example-Iee leeell privacy (Abadi et al., (2016). Per-update clipping restricts the local model update (Geyer et al. (017). which is the product between the sum of mini-bat muni-batch gradient and the stepsize (McMahan et al. 2016 Karimireddy et al. 2019 Acar al. 202T). Per-update clipping

---

Published conference paper at ICLR 2024
essential tool for preserving user-level privacy (Geyer et al., 2017 Zhang et al. 2022 McMahan eet al. 2018), which provides stronger privacy guarantee than example-level privacy.
To theoretically understand the effect of clipping in the federated optimization, Zhang et al. (2022) and Liu et al. (2022) presented the convergence guarantee of per-update and per-sample clipping, requiring the bounded gradient assumption. Despite the success these algorithms, the convergence behavior of clipping in federated learning, especially the differences between different clipping methods, has yet be well explored. We aim fill this gap in this paper.
2 PROBLEM FORMULATION
We formalize the prohlem minimizing of stochastic functions with only access to stochastic samples:
min
f(x)
5x(x) fi(x) == BE-DD Fi E),
where fi FR - R are distributed among workers and D, is the distribution of data & on worker i. For theoretical results, we make the following assumptions.
We first assume bounded variance in expectation following Koloskova et al. (2023) to incorporate heavy-tailed stochastic noise (Gorbunov et al. 2020) in Assumption [] As data heterogeneity in unavoidable in FL, assume gradient dissimilarit larity following Woodworth et al. (2020); Reddi al. (2020): Yuan et al. (2016) in Assumption 2 all the objective functions are identical (homogeneous workers), J = Jj. Vi. J. then the gradient dissimilarity is O.
Assumption (bounded variance). We assume that there exists a o² such that Vx E IR,, we have:
Egg [x][V/((xEE) - (Vx(x)) S o².
Assumption 2 (gradient dissimilarity). We assume there exist a <², such that, Vx Rd, we have:
E. (V) < <²
We propose an adaptation of the (Lo. Lmm-oohthsssss assumption from Zhang et al. (2020b);
Koloskova al. (2023); Zhang al. (2020a) that is tailored distributed setup smoothness assumplion can account for data heterogeneity and facilitate proof:
Assumption 3 (distributed (Lo, Ln smmotthtnsss We assume there exists Lo and Ln such that (f+}
(Lo, (1) -msooohh yx,y IR4 with ||x - yll S +.
fx)) - ff((v)l S (Lo + L V yyl-
(1)
This assumption introduces coupling of heterogeneity and smoothness of the function. Under standard individual (Lo, l.))-smothhnsss (Zhang al. 2020b a) and gradient dissimilarity, this assumption is always satisfied. Similar to the non-distributed setting, Assumption 3 recovers the standard L-smoothness from Nesterov (2018) when L1 O. When L1 > 0, Assumption 3 weaker it can include group of simple and important
than the standard L-smoothness assumption functions that do not necessarily satisfy global L-smoothness under any L, e,g. polynomial function f f(x = x². See Appendix A.1.1 1 for discussion on the implication of Assumption
3 ALGORITHMS AND CONVERGENCE RESULTS
In this section, we first describe the FedAvg algorithm (MeMahan et al., 2016). FedAvg mainly has steps: local model updating each worker and model aggregation on the server. FedAvg initializes the server with a server model x. Then each participating worker receives copy of the server model x and performs 7 steps of (stochastic) gradient descent (SGD). The updated local models are then communicated to the server for aggregation, finishing one communication round. This process is repeated for R rounds or until we have reached the target accuracy. However, it has been observed that adversarial servers can extract sensitive information from the learned model
parameters (Carlini al. 2018 Zhang al. 2022 Fredrikson al. 2015 Melis al. 2018)

---

Published conference paper at ICLR 2024
Algorithm 1 Per-sample clipping
Algorithm 2 Per-update clipping
1: procedure PER-SAMPLE CLIPPING Initialize stepsize
1: procedure PER-UPDATE CLIPPING
Initialize local and global stepsize 'Ps 7oo
for 1,..., R do
3: for 1,..., R do
Send server model all clients for elient ....., in parallel do
Send server model all clients for elient 1, ..... in parallel do
initialize local model y; f- for k: 1.....TT do
initialize local model y;
for k 1,....- 7 do
g: min 1. I (R())
y: y: m V Fi(y:)
end for
y pryy yc ng
10:
A, - y A t min 1, Ta:il A.
10:
end for Communicate y; the server
11:
11:
12:
end for x 2
12:
Communicate A the end for
13:
13:
14:
end for
14:
x 17 Σ;
15:
end procedure
15:
end for
16:
end procedure
Therefore, we next describe two popular clipping methods, which are critical to regularize each user's contribution and thus facilitate the analysis differential privacy.
3.1 PER-SAMPLE CLIPPING
Following Liu al. (202), we clip mini-batch gradient at every local iteration (see Algo- rithm[]). Throughout this section, we denote M == m f [x, and adopt the virtual sequence
definition 1 -i=1 Yi. with X, X, when mod (r + 1)
from Stich 2019). See
Appendix A.I.I for discussion of the M parameter and Appendix D for the proot.
Theorem (per-sample clipping). Suppose functions {Ja] satisfy Assumption to 3 If we run Algorithm 7 for T' = R. steps with R communication rounds, 7 local steps, clipping threshold e,
and stepsize 7 S I4LF with L == Lg + min(c, M) M) In and M max, max f fxx))
l}, then it holds
that:
No neT
Pb T/T
nlia² +(2)
min (( +E[1
n
+ min (a+c.
o² &xt0))))))))
nL min
where Fy = f(xo) f
The convergence criterion on the left-hand side, the minimum gradient norm, could also be replaced with the average of the expected gradient norm of the virtual iterates. When there is no stochastic noise and heterogeneity (a² = 0, 52 = 0), the first two terms control the convergence and can decrease with the increasing number iterations number workers (take square for both sides). The last bias term can decrease with a larger clipping threshold assuming the o² and 22 are fixed and are larger than zero. We provide concrete examples similarly to Koloskova al. (2023) considering
The third term indicates linear speedup in the
to illustrate that the neighborhood size is tight,
i.e., f(x)]l = Ω min a + xf+(
2 together with the proof in Appendix
Comparison to the unclipped FedAvg: Under Assumptions + and standard I L-smoothness assumption, the unclipped FedAvg has the following convergence rate min f
( nLaz LnV/To++*??* Comparably, the most notable difference the bias term O (min (. (3)))))) which decrease with increasing When oc, the radius O as no gradients get clipped. (See Theorem Appendix [ for recovering FedAvg when is large).
Corollary Suppose functions {ff} satisfy Assumption if we add random Gaussian noise Z such that Ziςt N (0,
gi in Algorithmm] 1
and it for T steps with stepsize

---

n Published conference paper at ICLR 2024
7) I 141. and == Lg + ML,, and define Fo f(x0) fr" then we have:
min B|IV S
Fo neT
+
V n/l
Fo
nL(o3 +3))
Lnmin (TV02+
tE|1,T]
(3)
o + S, o² + +))++
yLobe n. n
+ min
Extension privacy-preserving FedAvg: We extend our algorithm to make suitable for pre- serving privacy for each individual data point in some scenarios. Specifically, we update the local model following Y; <- Y; - 7/(; + 2,) where 2; ~ (00 h and dl is the dimensionality of the parameters. When batch size
this updating rule protects example-Ievel privacy for each client (Abadi et al. (2016)) and achieves local differential privacy. The updated convergence result is shown in Corollary !| Compared to the convergence result from Theorem we have extra terms that are dependent the variance of the added Gaussian noise and are decreasing with larger number of clients n. See the privacy discussion in section 3.3 for the connection to centralized DP-SGD,
Privacy discussion We consider the scenario where the server might be malicious. Following Abadi
al. 2016). the variance of the added noise oi needs to be ! @dlog([/5)] to achieve example-
N
level (EDP, 8) oloco differential privacy, where := min, [[D.]] is the minimum number data points among all the clients and mini-bat bati-bbtch size is one each client. We require the definition of N
the record that differs between the neighhoring dataset is example in the training data for each
T (og((T/)
client (Abadi et al. 2016). When @(o² + <²) is small, the optimal utility after T = θ
iteration is O
4/og(1/8) =N
by choosing
e dlog(1/5) a and ())((=))) We obtain
optimal iteration complexity T when r = 1, which shows no benefits in doing multiple local steps from the analysis. When ( +(2) dominates the convergence, we need to pick larger c and smaller y to reach the optimal utility, See Appendix D.5 for more detailed discussion and the proof.
3.2 PER-UPDATE CLIPPING
Per-update clipping aims to bound the influence of any user in FedAvg by clipping the model update A, The complete theorem with client sampling and its proof can be found in Appendix C33 Through- out this section, we assume L,1 = O and let I. == Lo (using the standard smoothness assumption) for clarity of presentation. A complete version can be found in Theorem Mij Appendix C.I
Theorem II (per-update clipping). Under Assumptions 1o consider Algorithm with stepsizes
R S 32FL and 41llTTL L. S to Ifc OGRVTO + T)T(), then after I rounds, holds that:
(xxx)) so -E[L.M
Fo ongR +
min
(4)
Ifc 2 O(IVTO + MTT(), let ng 2 2/nn n and then it holds that:
min FE
E|ll (x.))l| < 00
Fo
L T
+
+5)
Fo
TeT
00" (
R
VF
ong
Foddigg tem
clipping trrm
(5)
where F. = (x0)
When the clipping threshold is larger than O(n + M)T{) (Eq.5)) 5p). the exact convergence to any accuracy can be achieved by choosing sufficiently small yi to reduce the clipping bias, which is in contrast to Algorithm|] [ where the convergence is only guaranteed with a sufficiently large clipping threshold. However, when > O( ((vro+T<) (E). Algorithm 2 is only guaranteed to converge to a neighborhood of stationary point, with size 9 o + <). We illustrate that this neighborhood size is tight with an example following Koloskova al. (203) given F in Appendix B
Comparison to the unclipped FedAvg. Apart from the additional clipping terms, Eq. 5 contains the
standard FedAvg terms Karimireddy et al. 2019 Theorem V), except for / n. Ç. We prove that

---

Published conference paper at ICLR 2024
it disappears as long as is large enough such that e ( TTTT/(C) (see Appendix C.3 for more details). Therefore, the convergence rates of unclipped FedAvg can be recovered as c od.
Extension to differentially private FedAvg, We here extend the convergence result to differentially- private FedAvg LDP-FedAAve that protects user-level local privacy(McMahan et al. 2018 Geyer et
al. 2017 Zhhng et al. 2022). Before sending A; to the server, we add additional noise such that A + Zi where ~ (0, /r/dIL We summarize the convergence rate of DD-FedAvg in Compared with Theorem [ DP- DP-FedAvg has additional terms that depend the privacy noise oh and are decreasing with larger number of clients.
A
Corollary[I [I
Privacy discussion: Corollary [ protects user-level privacy, where the record that differs between neighhoring dataset is the combination of all the training examples from single client (Ponomareva) al, 2023). Following AAbadi al. (2 to achieve (EDP, d)-differential privacy, the variance of the added noise oh needs to be 2 dlg'dlog(1/ R/ (full client participation). Compared with Corollary [ oi does not depend on as clipping is performed every T local steps. When
@ ((o2/++<" (2)
is small with relatively low privacy-budger we obtain the optimal privacy-utilie
bound O dlog(11/8) after running Rt R=
nEor
rounds by choosing c
dlog(1/a) TeE
(178)
= (
V and fl = ( Due to the more practical bounded variance assumption, our
optimal utility bound is the square of the standard local DP utility OVV dlog(1/8)) which assumes
nefe
bounded gradient. Increasing n can linearly reduce the reached optimal error. Differently from increasing local steps 7 does not impact the number of rounds R to reach the optimal utility trade-off. When 0(02/T (?) is large, the utility error increases as and increases. See Appendix [o detailed discussions and proofs. While Algorithm 2 can converge to any accuracy, it has to pay the price for larger DP noise as ODp is proportional to R. Consequently, the overall privacy-utility trade-off is no better than Algorithm | (N2 does not appear in the denominator due to a stronger privacy notion).
Corollary[] [
Corollary II. Under Assumptions 1 to consider DP-FedAvg with stepsizes S 32 TigT S TO
1. Let Fo = f(xo) - fr. Ifc < O To + MIT(), then after R rounds, it holds that:
(xx)] s So c0( FE[1.R
Lmg obr a en
- +s)
min
(6)
Suppose c 2 O(II/TT MTT() Let fly 2 2/n.
Then holds that:
min rE[l.R]
[x|[V/(x)]]]
Fo
+
LLnS
I a
tc)
FislAng torm
Ligg nepe
Lag a Dp
ofr
chipping torm
DP coise IOREA
3.3 COMPARISON BETWEEN PER-SAMPLE AND
CLIPPING
While per-update and per-sample clipping are designed to protect different levels of privacy, they share some similarities from the pure algorithmic point of view as discussed below.
Special case I: Accuracy: when 1, 17 "//lg- and Oper_sample sample = -pper wwt.uppatee// 11 given Cper_sample and Gper_update as the clipping thresholds, the two algorithms are the same and the clipping bias for both algorithm be simplified O (min (7 ( 2((++() Cpe spdar
(see Appendix E for the proof and
the simplification of the convergence rate). Therefore. in this special case, we can adjust Oper ser_ssampi in per-sample clipping to reach any accuracy, which is essentially equivalent to the strategy of adjusting inner stepsize yp (adjusting the magnitude of the local updates before clipping) to reach any accuracy in per-update clipping (Appendix [E). Per-sample clipping recovers clipped mini-batch SGD:
When = 1,5 O and the mini-batch size is one on each client, Theorem recovers Theorem 3.3 from Koloskova et al. (2023) by discussing the relation between e and See Appendix P for

---

Published conference paper at ICLR 2024
the proof. Privacy-utilics trade-off: When the mini-batch size one on each client Algorithm and 2 with DP-noise are equívalent to the centralized DP-SGD Koloskova et al. (2023) algorithmically (except that one algorithm uses two stepsizes). Note that the DP notion is slightly
0.
different from before. See Appendix C.6 and D.5 for more details. this case, we prove that
both algorithms achieve the same privacy-utility bound O <lag(1/5)
with T = 0
Nu Lad log
N Nuuffe
iterations, where Neat being the total number of data points. Due to the use of the bounded variance assumption [I, our utility bound is slightly worse (higher order) than existing works (Kiter al.) 2012, Wang et al. 2018) which assume bounded gradient and prove the optimal utility bound as [log(1/6)
Nor
Arbitrary choices of We can always adjust the inner stepsize in per-update clipping to change the norm of the model update A; := -1) Σ (y,s)) such that it might not get clipped and can reach any accuracy. However, we cannot adjust the norm of the mini-batch gradient in per-sample clipping and thus have chance of converging the neighborhood (see Appendix and E for examples).
When 41 > O, we can use larger stepsize 1) (1/((LLo cl1)r) when < A in Theorem I Theorem[ll] all Theorem requires the maximum norm of the gradient due to the use of Assumption 3 More detailed discussions can be found in Appendix A.I.I
Stepsize:
More local steps 7: Compared to Algorithm larger local step can reduce the influence of the stochastic noise x² by factor of _L in Algorithm
3.4 PRACTICAL IMPLICATIONS
In practice, Algorithm and 2 are parallel from privacy perspective. Algorithm [ |limits the contri- bution of (individual) training example on the client model update, whereas A Algorithm 2 controls the contribution of all the training examples from client on the server model update. Therefore, depending the specific definition of neighboring dataset [Ponomareva et al. (2023),
should select different algorithm. We next discuss the practical implications based on our results. We
refer|MeMaie McMahan et al.) (2018); (Zhang ct al. (2022), ;; Liu et al. (2022) | Yang et al. (2022) for an extensive experimental study of the similar algorithms as we study in this paper.
Accuracy perspective: Suppose there no DP noise. Theorem I suggests that a higher accuracy can be achieved by picking a sufficiently small inner stepsize vp.
O (TotTe). As this can slow
down the training, one can pick f2 to be as large ((1/(mITL) L)) to accelerate the training process. For per-sample clipping, we need to set e 2 θ (2+s²)
to guarantee the convergence to s-accuracy. We refer to Appendix C.5 and D.4 where more explicit formulas of the stepsizes can be found.
Privacy perspective: We provide insights in understanding the impact of the stochastic noise o² and ( the choices of stepsize and clipping threshold for obtaining optimal privacy-utility bound in Appendix [D.3] and C.6) While per-update clipping can converge to any accuracy by adjusting the inner stepsize, it is no better than per-sample clipping in terms of the optimal privacy-utie trade-off seeing that the added noise needs proportional the number of communication rounds.
The observations Theorem suggest that one can improve per-sample clipping by incorporating both inner and outer stepsizes into Algorithm[[sso that the clipping bias can be reduced by decreasing the inner stepsize Addtionally, both algorithms with DP noise require the maximum norm of the gradient for determining the stepsize, which can be less practical.
I. Limitation
4 EXPERIMENTAL RESULTS
As the effect of stochastic noise has been thoroughly evaluated experimentallyKKoookovaaa Koloskova et al. (2023).
we here mainly focus on demonstrating the impact of the data heterogeneity (² on the convergence. Our main findings are: 1) when the data heterogeneity is low, per-sample and per-update clipping have similar convergence behaviour2) when the data heterogeneity is high, per-sample clipping can converge to neighborhood of the target accuracy. However, this neighbourhood size is reducing clipping threshold increases 3) Per-update clipping can reach the target accuracy at the cost of

---

Published conference paper at ICLR 2024
(6) No.classes=1
(b) No.classe==5
(c) |[9W]][[No.chs==11rrr
Clipping Ihresholds
500
1.50
12
c:1.50, 1r:0.1 c:2.12, 1r:0.4 c lr:0.2
2.12
407
447
468
481
492
498
28
30
19
13
7
8
100
3.00
61
61
61
63
63
63
65
38
28
17
12
10
7
10a
4.24
47
49
50
15
7
6.00
40
40
41
43
44
45
46
31
24
14
10
9
10-1
30
30
31
32
33
34
34
30
23
14
9
8
6
2
3
5
6
2
3
5
6
400 Communication rounds
200
Number of local steps
Figure 1: The number of communication rounds to reach target accuracy [| fxx)]] = 0.18 (dotted line in (c)) using per-sample clipping. No. classes represents the number of classes in each worker. When the data heterogencity is high (a), we can hardly reach when e = 1.5. However, the neighborhood size O (c2/c) gets smaller as we increase the clipping threshold and we can reach with larger clipping threshold. (c) shows that the gap between when c + oc and = 1.5 does not decrease with larger R.
(a) 1
(b) No classes=5
(c) [|9/0x]|| (No.cless= 1, T=7)
Clipping thresholds
0.15
163218
240224224
70
344
802
79
29
21
22
18
500
c:0.15, 1r:0.0125 c:0.21, lr:0.0125 C Ir:0.20
0.21
140146
2242377
13
0.30
63
92
116142
188251
354
39
25
18
12
12
10
9
100
100
0.42
70
75
86
100
18
068816211
181
28
24
15
11
10
8
8
10
0.60
42
45
46
14
7
10-1
29
30
31
32
30
34
34
30
14
6
3
6
250
500
750
Number of local steps
Communication rounds
Figure 2: The number of communication rounds reach target accuracy f(x](l 0.18 (dotted line in (c)) using per-update clipping. Given fixed clipping thresholds and high data heterogeneity (a), we require more rounds to reach the target accuracy as the number local steps increase. (c) shows that when the clipping threshold is large, we can slowly arrive at the target accuracy eventually.
communication rounds. See Appendix for experimental setup and Appendix for complicated NN experiment on CIFAR dataset.
Experimental results: We tune the stepsize for all the experiments to reach the desired target accuracy V fx(x))l with the fewest rounds. We show the required number of communication rounds to reach the target accuracy
0.18 using per-sample clipping in Fig. [ and per-update clipping in Fig. / We observe that when the data heterogeneity is low (Fig. (b) and Fig. (b)). both clipping operations can easily reach the accuracy. However, when the data heterogeneity is high such that each worker only has images from single class, comparably, we hardly reach with per-sample clipping when the clipping threshold is 1.50. (Fig.
[ (a)). The gap between when c = 1.5 and - oo is clearly non-decreasing as shown in Fig. | (C). However, we can reach the target accuracy with larger clipping threshold. When we use per-update clipping. even when the clipping threshold is small, we can slowly but eventually converge to the required accuracy (Fig. 2(a))
5 CONCLUSTON
In this paper, we have rigorously analyzed the impact of two popular clipping strategies: per-sample and per-update clipping, on the convergence of FedAvg under any clipping threshold. Comparably, per-update clipping interacts with the stepsize, adjusting stepsize accordingly can lead to convergence eventually, but at the cost of more communication rounds. We note that the conclusions drawn in this paper are tied to the specific specifications of the procedures. It is possible that by introducing additional stepsize in per-sample clipping, a different trade-off between accuracy and convergence rate can be achieved. Our work provide better theoretical understanding of two clipping strategies in federated learning. We have established precise impact of data heterogeneity on the convergence of clipping-base based FedAvg. As preserving user privacy becomes more important, our work can facilitate the analysis of differential privacy in federated learning and open up future directions for tackling the unfavourable influence of data heterogeneity in the field of privacy-friendl federated learning.

---

Published conference paper at ICLR 2024
ACKNOWLEDGEMENT
Bo Li, Mikkel N. Schmidt, and Tommy S. Alstrom thank for financial support from the European Union's Horizon 2020 research and innovation programme under grant agreement no. 883390 B2R020-UU-SECU-200 SERSing Project) and Pioneer Centre for AI, DNRF grant number Pl. Sehastian Stich thanks for partial financial support from Meta Privacy Enhancing Technologies Research Award 2022. The authors thank Anastasia Koloskova for the discussion.
REPRODUCIBILITY STATEMENT
We refer to Appendix G for the implementation of the two clipping methods as well as the hyperpa- rameter choices and software, We refer to Appendix C and [ for the detailed proof.
REFERENCES
Martán Abadi, Andy Chu, Goodfellow, McMahan, llya Mironov, Kunal Talwar, and Zhang. Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, 2016.
Durmus Alp Emre Acar, Yue Zhao, Ramon Matas, Matthew Mattina, Paul Whatmough, and Venkatesh Saligrama. Federated learning based on dynamic regularization. In International Conference on Learning Representations 2021. URL btRtttts::: / opw.revl ew.net/ Forum? ? d- 4CM44CCC88 67 9%
Kareem Amin, Alex Kulesza, Andres Munoz, and Sergei Vassilvtiskii. Bounding user contributions: A bias- variance trade-off differential privacy. Kamalika Chaudhuri and Ruslan Sulakhutdinov (eds.), Proceedings the 36th International Conference on Mackine Learning, volume 97 of Proceedings of Machine Learning Research. pp. 263-271. PMLR, 09-15 Jun 2019. URL hhtps: http:/ps///ppcceeed..ooom wttp://eeeeinn...m.........mmm.. www.....r.e///ee am 9a.ntm]]
Galen Andrew, Om Thakkar, Hugh Brendan McMahan, and Swaroop Ramas wamy. Differentially private learning with adaptive clipping. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL httpp::/ pttt:ss://operzevee.eeeee feru/oorummm
RUQI ZWZR8
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta. Private stochastic convex optimization with optimal rates. CoRR, abs/1908.099) 09970, 2019. (RLL:hhtp://axxi..ooo abs abs/1908.09970
Nicholas Carlini, Chang Liu, Jemej Kos, Úlfar Erlingsson, and Dawn Song. The secret sharer: Mcasuring unintended neural network memorization & extracting secrets. CoRR, ahs/1882.082233 8018. URL http:
7/arxiv warxiv.org/a abs/ /wtp///00222 802.08232
Olivia Choudhury, Aris Gkoulalas- Theodoros Salonidis, Issa Sylla, Yoonyoung Park, Grace Hsu, and Amar Das. Differential privacy-emabled federated learning for sensitive health data. CoRR, abs/1910 10.02578. 2019. http:///t//axx
abs/ 0.02578
Michael Crawshaw, Yajie Bao, and Mingrui Liu. EPISODE: Episodic gradient elipping with periodic resampled conrections for federated learning with heterogeneoous data. In The Eleventh International Conference on Learning Representations, 2023. URL http:ppss//ppene..ee....tttt
Eorumm 11-yt 22 Ymzt ET
Rudrajit Das. Satyen Kale. Zheng Xu, Tong Zhang, and Sujay Sanghavi. Beyond uniform lipschitz condition in differentially private oprimization, 2022.
Alexey Dosovitskiy, Lucas Beyer. Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby, An image is worth 16x16 words: Transformers for image recognition scale. CoRR, abs/2010.11929, 2020.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart, Model inversion attacks that exploit confidence information and basic countermeasures. In Proceedings of the 22nd ACM SIGSAC Confenence on
Computer and Comminications Security, CCS '15, pp. 1322 1333, New York, NY, USA, 2015. As- sociation for Computing Machinery. ISBN 9781450338325. doi: 10.1145/2810133.28166 http:p//aablootr//11133332300000
URL
Robin C. Geyer, Tassilo Klein, and Moin Nabi. Differentially private federated learning: A client level perspoctive. CoRR, abx/1712.07557, 2017. URL WtRl.httt::/aatee wttp:/wwwwwwgg//////////ooo/
10

---

Published conference paper at ICLR 2024
Eduard A. Gorbunov, Marina Danilova, and Alexander V. Gasnikov. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. ArXiv, aws/200S..105335 2020.
William H. Greene. Econometric Analysis, Pearson Education, fifth edition, 2003. ISBN 0-13-06618999, URL
hett:://aagss.teer..yyy..es wtw.://u.uedduugreeeeeeee httpi/eeeeettttteeeeeeeeeee http::/:/wcc..e..cona.aaaaaaaaaa
Tzu-Ming Harry Hsu, Hang Qi. and Matthew Brown. Measuring the effects of non-identical data distribution
for federated visual classification. CoRR, ahs/1909.063355, 2019. URL.
1909.06335
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Ronawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. D'Oliveira, Salim EI Rouayheb, David Evans, Josh Gardner, Zachary Garrett Adrià Gascón, Badih Ghazi, Phillip B. Gibhons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi. Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo. Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür. Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song. Weikang Song. Sebastian Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang. Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems federated learning. CoRR, abs/1912.04977. 2019. Uttphtt::/ http//axxvvv..g.g../ www..//.ggg//ooo/aoooooooooe wttp:///bs/111111/11/02 1912.04977
Sai Praneeth Karimireddy, Saryen Kale, Mehryar Mohri, Sashank J. Reddi, Sehastian U. Stich, and Ananda Theertha Suresh. SCAFFOLDD: stochastic controlled averaging for on-device federated learning. CoRR, abs/1910.06378, 2019. URL httt:://tattwww.te////
abs wwtp://9991011331
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high- dimensional regression. In Shie Mannor. Nathan Srebro, and Robert C. Williamson (eds.), Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pp. 25.1-20.40, Edinburgh. Scotland, 25-27 Jun 2012. PMLR. httpat/pss//ppcceednggssss
f2rlxiferl2.htm
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sehastian Stich. A unified the- ory decentralized SGD with changing topology and local updates. Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 5381-5393. PMLR, 13-18 Jul 2020. URL https 7/proceedingss www.m..ppresst. r.press/v 1 19 os oskova20a.htm
Anastasia Koloskova, Hadrien Hendrikx, and Sebastian U. Stich. Revisiting gradient clipping: Stochastic hias and tight convergence guarantees, 2023.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep volutional neural networks. In F. Pereira, C.J. Burges. L. Botton, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012. URL httpps: http://wwwcceiiinnnnesep....po http:/ppppraaepppppeeeeeeeeeeeee /ltp///pe////pee/////l.eeee c399862d3b9d5b3 4ct.ae/6666644444244444442---bb-
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL URU/tts::/yacm.eecu.
excb/mn mn ist/]
Mingrui Liu, Zhenxun Zhuang, Yunwei Lei, and Chunyang Liao. A communication-effici distributed gradient clipping algorithm for training deep neural networks, 2022.
Vien V. Mai and Mikael Johansson. Stability and convergence of stochastic gradient clipping: Beyond lip- schitz continuity and smoothness. CORR, abs/2102.06488, 2021. URL. https:://arxlwworr/:
2102.06489
B. McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agūeea y Arcas. Communication- efficient learning of deep networks from decentralized data. International Conference on Artificial Intelligence and Statistics, 2016.
H. Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In International Conference on Learning Representations, 2018. URL https:/
spenzeview.cet/Eooo Horum. htt.:///oouunn.dddd.... -2C
Luca Melis, Congzheng Song. Emiliano De Cristofaro, and Vitaly Shmatikow. Inference attacks against collaborative learning. CoRR, Abs/1885.04000 2018. URL http:ppp/aaww...oo////bbb.ee
04349
Milad Nast, R. Shokri, and Amir Houmansadr. Comprehensive privacy analysis of deep learning: Stand-alone and federated leamning under passive and active white-hox inference attacks. ArXiv, abs/1812.00910 2018.

---

Published conference paper at ICLR 2024
Yurii Nesterov, Lectures on Convex Optimization. Springer Publishing Company, Incorporated. 2nd edition. 2018. ISBN 3319915770.
Razvan Pascanu, Tomás Mikolov, and Yoshua Bengio. Understanding the exploding gradient problem. CoRR. abs/1211.5063 2a.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks, International Conference on Machine Learning, 2012b.
Natalia Ponomareva, Hussein Hazimeh, Alexey Kurakin, Zheng Xu, Carson E. Denison, H. B. McMahan, Sergei Vassilvitskii, Steve Chien, and Ablurdeepp Thakurta. How dp-fy ml: A practical guide to machine learning with differential privacy. J. Artif. Intell Res, 77:1113 113 1201, 2023. URL https
7/api. see.ssemtnticcchee lar www.ooog///oo... Corpus 1::572254552
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Brendan McMahan. Adaptive federated optimization. CoRR, abs/2003.00299 2020. URL
Umut Simsekli, Levent Sagun, and Mert Gürbüzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. CoRR, 0ts//1901.60533 2019.
Andreas Steiner, Alexander Kolesnikov, Xiaohua Zhai, Ross Wightman, Jakob Uszkoreit, and Lueas Beyer. How train your vit? data, augmentation, and regularization in vision transformers. CoRR, abs/2106. Nts/2106.10270,, 2021. /tl.lapppee//a/x...rr//aa/a//
Sebastian U. Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations, 2019, URL
forum? wds1dd2111eeeeee
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. CoRR, abs/1706.03762, 2017. URL /tttp://axxiv.orr
abs/1706.0376)
Di Wang. Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. CoRR, abs/1802.00251, 2018. URL
abs 111120088202211
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard Yang, Farhad Farokhi, Shi Jin, Tony Q Quek, and H. Vincent Poor. Federated lcarning with differential privacy: Algorithms and performance analysis. CoRR, abs/1911 100222, 2019. URL www.w:wwwwoo......oooo....... httpa/////.1111110
Blake F. Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch vs local SGD for heterogeneous distributed learning. CoRR, abs/2006.04/ 04735, 2020. URL
abs/ 2006.04735
Haibo Yang, Peiwen Qiu, and Jia Liu. Taming fat-tailed (heavier-tuiled with potentially infinite variance) noise federated learning- In Alice Oh, Alckh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances Neural Information Processing Systems, 2022. /RRLLtttps///ppeeeiiicco forum? d=851 [GGXXmmk]
Yang You, Igor Gitman, and Boris Ginshurg. Scaling SGD batch size to 32k for imagenct training. CoRR, abs/ 0bb//1708.55 778.03888. 2017.
Kun Yuan, Qing Ling. and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3):1835-188 2016. doi: 10.11337/1109931170 httll//tttt:///ooooo.. wtt.oo/g///....... 11.17777
1309431
Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of algorins for non-convex optimization. CoRR, abs/2010.02519, 2020a. URL
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaic. Why gradient clipping accelerates training: A thcoretical justificution for adaptivity. International Conference on Learning Representations, 2020h. URI.
Jingzhao Zhang, Sai Pranceth Karimireddy, Andreas Veir, Seungycon Kim, Sashank J Reddi, Sanjiv Kumar, and Suvrit Sra. Why [adam] beats [sgd) for attention models, 2020c. URI. BRRl/httts:///peeree/ www.te//
Forum? 2 d=S TTE
Xinwei Zhang, Xiangyi Chen, Mingyi Hong. Steven Wu, and Jinfeng Yi. Understanding clipping federated learning: Convergence and client-level differential privacy, 2022. URIl/Kttpp.//opeeeeeev...
Forum? 1 [XX3666884
12

---

Published conference paper at ICLR 2024
Appendix
Table of Contents
Technicalities
14
A.1 Assumptions
14
Some technical lemmas
14
Examples for illustrating the neighborhood size light
15
B.I Per-sumple clipping neighborhood
15
B. Ped-update clipping neighborhood size
17
Per-update clipping
18
C.1 Full statement of the convergence resull
18
Proof Sketch
................................
Proof of convergence
19
Usetul Lemmas
22
Accuracy perspective
................................
29
C66
Privacy-utility discussion
29
Per-sample clipping
33
D.1
Convergence result
33
D.2
Proof of convergence
................................
34
Extension differentially private SGD
................................
45
D.4
Accuracy perspective
46
D.5
Privacy-urility discussion
46
Connection between Algorithm and Algorithm
49
Comparison against existing works
49
F.1
Per-lample clipping
49
Per-update clipping
49
Experimental setup and details
50
MNIST experiment
50
CIFARIO experlment using per-update clipping
51

---

Published conference paper at ICLR 2024
A TECHNICALITIES
A.1 ASSUMPTIONS
Assumption A-1 (individual gradient dissimilarity). Assumption 2 holds, assume there exist C? such that vx R":
[Vx((x) f(()) c. <max = max & $ nn²
the maximum of gradient dissimilarity on single worker ng² when we consider the gradient dissimilarity on the rest n workers as Therefore, Smax S nn²
Proof. According to Assumption 2
Note that we use Assumption CnrumptionSttrouuuee throoghhuut the proof. We only use Assumption A- when we demonstrate that we can recover the convergence rate of the unclipped FedAvg when the clipping threshold is large.
Proposition (Relation to standard (Lo, Li )-smoothness Zhang al. (2020b ab). ). If A'ssupption 2 and the
standard Lo., Ia)-smoothness assumption holds, such that fi() Nylll (Lo+AallVii())] x-yll for x E R and ||x yll T.T then we have:
[V) Vv(()) (Lo + (I yll s (Lo Lima L.I[Vf())|]]]x yll (A.1)
standard( (.) -mmoothnes
Proof. According to Assumption
2 we have:
(f(() (V vx(x) +[[l( S Smax [(x](l
The first inequality triangle inequality. The second inequality Assumption A-I Considering the standard smoothness assumption from Koloskova et (2023) Zhang at (20206) for every worker i:
[V V/fxx) < (Lo + L1 [[(x yll $ (la + Imxmax + [xx])(x yll
Proposition 2 (Implication of the distributed (Lo, -mmoohhes)s) If Assumption 3 holds, then for any x.y Rd with ||x yll i (V < (La -////\)) vll
If above assumption holds, then:
[[(x((
fily f((x) (Vf(x))))
2 |x -11.
A.I.I DISCUSSION ON THE IMPLICATIONS OF THE DISTRIBUTED (Lo, SMMOOTTTNESS
Note that the standard (La, 4 -moothh assumption (Zhang 2020b requires ||x yl1 ł any
run the standard gradient descent without clipping: X++1 X. (x+), x, y Rd Consequently, [|x--] -xell then must hold that v stepsize has to satisfy
S 1,1I//O for any 0. Therefore, guarantee convergence, the
Lo LA1 max, [xx))]]]]
Therefore, setting the stepsize that depends the maximum gradient is. in fact, necessary in scenarios. See also the discussion regarding (Zhang al. 2020b Assumption
A.2 SOME TECHNICAL LEMMAS
Lemma 1. any > and u Rd, the following holds:
Vf(x) - 2a
|ull
I a (xx)]]]
(A.2)
2x

---

Published conference paper at ICLR 2024
Lemma (triangle inequality), For arbitrary set of vectors [u,)22 with es E R", the following holds:
N
Σ
alll S N
(A.3)
a|u + w/ll² $ (1 10:11
+
||lll Va 0.
(A.4)
Lemma (projection lemma Koloskova et al. 2023 Given e cas constant and cxip, min (1, |||ا|| we have:
clipa(x) - clip, 1|x-~xXv yll.
(A.5)
Proof clipping projection onto convex set (ball of radius of c), and thus is Lipschitz operation with Lipschitz constant with
Lemma 4 (Implication Assumption D. If each function fa (Lo, Li)-shoth,, then function also
(Na, Ia) -mmoohh such that, vx.y Rd with ||x yll S T. we have:
fly) - f(x) (V)(). x) Lo L [.IV)(())
x y11"
(A.6)
2
Proof. If each function fo is Li -smoohhhh we have:
Lo [
Jıly) f((x) (Vf(xx..
-1ll
2
Take the expectation w.r.t i, we have:
Lo L1 [
B[A(y)] < (BIAA
xx=
2
S +V x) Lo + [(())((x)] y11
B EXAMPLES FOR ILLUSTRATING THE NEIGHBORHOOD SIZE TIGHT
We present examples with considering the gradient dissimilarity given illustrate the neighhorhood is tight similarly as Koloskova et 2023) in following sections.
B. PER-SAMPLE CLIPPING NEIGHBORHOOD SIZE
We here first provide an example that illustrates the neighhorhond size tight for per-sample clipping, i.c.,
((.)] Q (min (a + 2²+c2) Vt 1 and show the proof.
Example (similar to Koloskova al. (023)). Scenario (C > 0, O, 1): Case 1: For any
<> 0. e < 3c. there exists function (x) with heterogeneity Ç² such that there exists fixed point br
Algorithm with [|V/(""]|| c. For example, considering f(x) = ". f((x,, where (x)
x
fa(x)
xx fa(x) = 1 + 3a)² and > 0. We note that x* - is a fixed point of Algorithm but
Vf(x')
a 2.
2: For any
0. 35. there exists function f(x) with heterogeneity
2² such that there exists fixed point x" of Algorithm with [[V((x II > ac² For example, considering 1 and (x)
[x + na)² with > 0 and We note that x' --T tixed point of Algorithm hut fx((x') 50c Scenario 2 (C 0.0 > 0, 1): We can derive the corresponding neighborhood size following Theorem 3.1 and 3.2
f(x) : > fz(x), where [+(x) = 1x² for
1= 10 7
2-
from Koloskova et al. 2023).
Example Scenario (( > 0,0 0, 1), Case 1::
By fixed point, mean the algorithm does move away from if initialized

---

Published conference paper at ICLR 2024
Proof. According to the definition (Assumption 2a². Since we assume < [., we get 2v Letx' = = We obtain
we have ç² = 1 Eim V Vf(x)]*
II |I| = VV |I| = ||x" || = _ <c
and
[V = = ||x* + 3a = ||
2 + 30/l
c>c
3 V22
Therefore, (x" and (x*x)) ) are clipped while V fx(x') gets clipped. This implics that
E. [clp
2 +c=0.
Hence, any stepsize v > O, we have y B. [elip, (Vf((V((())))))))) ))] = and thus x fixed point Algorithm |
(when Algorithm iss initialized at x'. will not move). However. the error as large as the following:
12
1
[V III x + all =
all
2
10
20
Example Scenario (C > 0, O 1). Case 21:
Proof. According to the definition of ç² (Assumption 2 we have <² = E; [IV - *
(n- (n- and thus vn - Ta. Since assume that 2 96 and that 10 1. we get
n> > 10, = I We obtain that
IV -||====||x=-->=-----
n- --1ll
c <..,
that
[V n
c + nall
Using assumption that n 12 {z. it holds that
vn-l - (n 1)02
20
+ na 2
11
Equivalently,
|V 2
Therefore, for any i n fx(xx) not elipped while V.n (x*) gets clipped. This implies that
(V/((")) (n 1)= +c=
Honce, x" is fixed point of Algorithm
But note that the error can be as large as
+a a
C
Vn-I
(
10 =
2
5²
103c
2c
50c
Example Scenario (( 0, > 0,
Proof. Let assume for simplicity f. f= F(x,, E) for any E [n]. By picking the functions indicated in
Theorem 3.1 and 3.2 from Koloskova (0123). We end up with the same order of the neighborhood
16

---

Published conference paper at ICLR 2024
B.2 PER-UPDATE CLIPPING NEIGHBORHOOD SIZE
We here provide example highlight the bias from Corollary (Eq. 4 tight for when m
Example (similar to Koloskova al. (2023), Scenario Let and a O. any Ç 0.
P.C. there exists function f(x] with heterogeneity <² such there exists fixed point
Algorithm
2 with [V/((") 2. For example, considering f(x) ". fi(x) where fi(x) 1xx²
fx(x) xx fa(x) = [(x 3a)² and a > We note that x" = 2n is fixed point of Algorithm
but vf(x') Toa > S. Scenario When r and = 0, similar argument can be made with (x) = fa(x) = f(x where f(x) defined as above.
Example 2
Scenario (C > 0, = =
Proof. According to the definition of < (Assumption
we have = 2i [V
a 2n². Since we assume < si we get bv/2 amj. l.et = 201"
We obtain
Im f2(xx I|| = |1 Vxxx"")) "|| ||xx'1 = <c.
and
3
11 (=V(((x)))) ||xx"" + 3am
|| 3aml
1
ccc.
Therefore, (x'") and fx(")) are not clipped while m fx(x") gets clipped. This implies that
E. Inclip, (Vf((")))
2 cc=
Hence, any outer stepsize 7a.
we have My E, [.(ncclip, (V )) and thus fixed point
Algorithm [ (when Algorithm is initialized at x",, it will not move). However, the error is as large as the following:
1
[Vx(x*)| ||x" all
+all
2rp.
2
10
20
Example Scenario ( 0, 0
Proof. Let 2 fi(x) and fi f. Further let f be the same function defined in Example 1. The same argument can be made with replaced with a.
Scenario

---

Published conference paper at ICLR 2024
C PER-UPDATE CLIPPING
In this section, consider DP- De-FedAvg algorithm with the following update rule.
No x== yik yla -VV...y
(C.1)
x" xx=x-11 ng Eiesr- (yip, +
where xi_ ~ (O, 1) for all í [n] E
In round we sample S" C [n] clients with | = S and then perform local steps starting from the shared model x"-1. Then we clip each local model update and add DP noise. After that, aggregate the updates from each client and compute the global parameter x".
C.I FULL STATEMENT THE CONVERGENCE RESULT
main theorem De-FedAvg (C.I (per-update elipping). Compared with the theorem provided the main puper. Theorem ||| includes client sampling well the discussion on the the large clipping threshold with e ( VTO + (max))
this section,
Theorem III (Per-update clipping). Under Assumption mlyT S To
and consider DP-FedAvg with update
rule (C.I) and step sizes m
+ La max, M.l. II.. f(" IIB 1fc < O Ta + TTT)), then after R rounds, it holds that:
By max., [Ix where
min "'Jo,
EXIVIX(')II s o [(x))- -
Lm
obr
σ VF
(C.2)
(R+
c$
aafl @(niTT )). then it holds that:
f(x")
La cg
f(x")
Liyy or
min E[IIVf(X'III = =E[O.R]
oze
[ +
Cn +
(C.3)
mmgTl.
(5+ VBS) + +Lmm ( (5=+5)
715 6-"
( (=+t))
S
ife O(n.To + (TTaa) otherwise
where
Corollary III. Under the setting of Theorem
ifc OlivFo + MTT() and (mx.-lll 2 2v5, then
with global step size 2 2v5, it holds that:
min B(Ils[(>)II < o f(x²) - relu.qq
Lmg cS
f(x)) - + (R++
Lmg ofr Shp
+
obr +
(C.4)
+ VEC) + +ImmI + Th1 00²
c (-+t5) +c))
Corollary if we let oo and ofe 0, then f 1- and thus C.4 recovers the standard convergence result of FedAvg Karimireddy et al. (2019).
Discussion on L. parameter: When L1 & 0. L depends on the largest gradient norm. This seems cannot avoided since Algorithm requires multiple local steps before getting clipped. ensure a sufficient decrease. the stepsize has to he dependent on the largest gradient norm. See section A.1.I detailed explanations.
C.2 PROOF SKETCH
section C following Karimireddy et al. (2019). we first provide a lemma (Lemma 55 that quantitics the progress of DD-Avv (C.I) for each round where the discussion on different cases for the clipping threshold is also included. Based on this decrease lemma, we give the proof for Theorem and Corollary [II In section C.4 we provide useful lemmas that we frequently use for the proof of Lemma The main challenge appears the case when c is large. Note that the local update Ei= VF((y...) always has a chance to be clipped since we only assume V Fx, E) fxx)) a² But n Di= f.((.. be smaller than large almost surely due the finite sum structure. Hence. one needs carefully disentangle the effect caused by and C when estimating variance The key lemma for recovering unelipped FodAvg is provided in Lemma 10

---

Published conference paper at ICLR 2024
C.3 PROOF OF CONVERGENCE
From here on, we use E, to denote the expectation conditioned on all the randomness generated before the round
Lemma 5 round progress). Under Assumption
2
and
the updates of Algoritlum [.. where
with step Tn S BETI MM S and Vig m
Lo
In max, E IlI II
| satisfy:
casel: c V I1 | I| 64m To 64
20(1If(xx" Blf(xO))
10 or cS
-[|l ||||
(C.5)
case2: : |[ م and /T 64
Blll / )) [[B[f(x"-)]] -[f(x")
2 obr
(C.6)
case3: |1uTV/(x~1]11 < : and c 2 6T 64
(x B[f(x"))) I1)
2L of
|||l//(x'
(1927 LLa 111 1/2) +
STIT
(C.7)
16 LL 0² + ((22)
2720n
72 5*)
6²
where f 1- if' 2 64m + 6mxx otherwise
Proof. Let u² = clip, (n Ei=1 VF ()). Using the upper bound of m and fp. we have
I Eie(s] -1 S Ei |p ΣT=n VD
I and 1| Eiels 2 = S E2T 3227
4_..
follows that: Woll 1 EEEs (u) + 2 88-111 ||| 4/- Plugging the update rule (C.T) into the definition (La, smooothness and let -
l flllf((x
have:
f(x)) f(x (V
s
Σ
nn
+
19
2
5
Σ 5E
(n)
+2
(C.8)
[E(S]
Using the fact that x is Gaussian noise with mean zero and variance obe. we can take expectation on both sides conditioned filtration and use the fact that 1. 11-1 ohtain:
E. E. { S(x
To E.
}}+
(E(S)
(C.9)
Ug E.-lll Σ
L
u
00
28
[E[S]
Case 1: ||1 and InrVf 2 64p /TO 64n.CC We start hy using Lemma
7 to
obtain:
E, B.
Σ [E[S]
u 1 (n )," ") S 10 ol cllm V
I1I
(C.10)
Since 5 |///// {xx ||. it follows that:
E,-
Σ sE|9]
Σ
E, E II1 < é < dIxxVf(("")
(C.1I)
sE[s]
We conclude by plugging
C.10
and
C..I
into
rearranging and taking expectation.

---

Published conference paper at ICLR 2024
Case 2
|/ |||
and c 2 6 64g.TC. We use Lemma c
with
on
E, (1 f(x
3
Σ
Eess
{)] and this leads to:
- 1(x
5 te|
-1 1|1
Br-1
11
E. 1l Σ u '1"1
[E[S]
1E/81
S $-21lxTV/(xx"111
)1(
B
11 E 10-11=///(('"" -u '171
(C.12)
We now Lemma 8 to bound the last term:
Er Ill -
$ 167" 2 L3
N | V /xx"'\11 ( + 27 1/)) + -87 L'ml Tull )o?
$
1
| fx 1|1 + -2 (16gf 1.2 2)
17 + 1 10²
64
7
|
- 11 n| 7 8r oz)
64
(C.13)
INTV 1111 1/² 2 7f
64
Anf 72
[ ||
|
22
64
7/
where we recursively use the assumption that 7i L S 37.
21 and 2 64m /a + 6
Plug
13133
(2.12 into C.9)
we have:
E,
f(x"
1)13+
+ (
L
E
|1|
Σ
n 11
o
4
2m
25
< 5((x
V
25 10
1
(C.14)
where we use assumption that no I 1. Take expectation on both sides and rearrange gives result.
Case [|x+V
and 6im + 64mITς. We Lemma
| with 1
-(nrV ) By 1 E [c(s) u
[1 and this leads to:
- - 1 > s E1|
u "
->1lmrV 2|1 B |
Σ u '11 + 1 /-V[(x"'))-- "
-E
Σ
'1P
1E
-111mmV/(( ||
-
ju
V E. [u] 1||.
(C.15)
Besides, we separate the mean and variance of the last term:
E.
[m] "]] + E.
Σ n
1 I1
B.
(C.16)
xE|9|
sc|s)
Apply Lemma 10 and 9 and plug and (C.66) into (.9 and use the assumption that mp
1
min( 10 1), we get:
(ff((((x") }] f(x
- N1
5Lmg
| -
-11 + (
3o )ll E, E1 _/] [up-111 '11 + noise
2mer
25
2m17
(C.17)
Vo
"TTV[((²"11)) noise
4ny7
20

---

Published conference paper at ICLR 2024
where noise-
A + BC² CHH. Do and
A 7M T (48mf 7 1,2 + mnng
B 11 (48rff ~
C n² . + 8 8% 11 Lmnng"
S T
(C.18)
D) fg 7 (19M
H = 340n
e ( + (*)-
We use the assumption m15l I 1 in ahove inequalities. Rearranging and taking expectation gives the result. 32
Proof of Theorem [ We first prove the case where e < O + MIT)). If gj..) f y I
64m Fo 64n,TC, then the inequality (C.2 trivially holds. Otherwise, use C3. Lemma Average over S S R gives:
20( - 8*) cna 1)
10L of cS
R E
BIIV 000 S
(C.19)
We next prove the case where Olva Fo + n) Since the upper bound
C.6 in the second case is always
better than the third case (C.7), we consider only two situations henceforth.
Defin Tn to be the set of indices
with [[ |Il and Ja to be the of indices with || V Vx(x") S c.
Σ
cBIIIV
II +
Σ
M E V/(x {)(
R+
(r- 1)
(r-1)E3
20(s(x") - 17)
12L ofp + mIT(
16 L
(E< 2
+ 0²
(C.20)
no(R +
7
+ 2 133n21(5²+ 0² m
2720m
0² 72
+(")
This implies that:
R+1 Σ E I|I
(r-1)E3
2x( 1*)
12L
2
1/T
16
+ à²
(C.21)
+
on (R +
cs
S
(192+21?21))) 1.212)(2
+ _
mr
2720m 2
0
+
and that:
R+1 Σ
f[IlV 11
1)
2x( f()
121.gg
16mM oi
(1(2
0²
(C.22)
TW R + 1)
SHIT
S
of
2720n 2 t54
1927 "5
Denote right hand side of
to C We simplify (c22) as following:
[Ja
<
Σ
R
Jel
(r-
1)632
(r- D)E
Σ
V |||
Σ
V
JTz
(r- J)
(r- 12
Σ
|| - ||| v QR + D) < <0
(m-1)67g
(C.23)
21

---

Published conference paper at ICLR 2024
Combine C.23
and C.21
we arrive at:
R+1
R B1 f
III
20(f(x²) f*)
12Lmg -
20(f(x²) - {()
12Lmg ofr SHITT
(R + 1)
c5
11ll 1)
+ ThT 16
16
TT 2720m
+ ((7) +
+ ve()=
+ (()
(C.24)
+ TIT 1927" 13111 11/
+ + L0p
VF +(+ + 60ml
+ +
)x( -1²)
12Lmg cs
20( - f*) T (R+1)
12Lng or SHIT
opp
ong R 1)
32mNNgF + 5
a + + 100m o² +()
Ve()
where we use the assumption that 2 6lm 64 and m S 7.... which implies 1E 57 (S $)) 2720nf
+ $ 1
(
( ( (2)-
Proof of Corollary | It can be shown that 24r Lop < V /aangrk in equation C.24
C.4 USEFUL LEMMAS
In this section, provide useful lemmas that we frequently for the proof of Theorem
Lemma (bounded drift (Karimireddy et al. (2019)). )) Under Assumption
2 and
f for any 2 and r 2 1,
the updates (C.I) with step size 5 wE where L == Lo + Li max., (Il Ayl. Oll V }] satisfy:
[V >11 87 n +4 2002
(C.25)
Proof. If then the lemma trivially holds since vioo =====x =x for all E [n]. Assume 2 2. Recall that
ViA vin-1 - V Fy (x) ). we obtain:
B, ||ly(T - x 11
E. [1ly x- m
VF W
- [1ly x W.f. [ o/
18 1 by V - x |8] +1+71! .rी H.... VI of
1
(1
Ey
x
27 12 11 -
+ 2Tm E,
|||
|
|) 1100²
(1+
1
E
- -x- 11 + 27T (Lo (Lo + 1.11V/(<~ ", 1, -x x-=1 |19]
--1
T
1
2Tv
E,
V
fx
2
Iyy
- - -x-
11 27 (1V + n/
-
(C.26)
where in the second inequality we separate the mean and the variance, in the third incquality, used Lemma the fifth incquality, we used Assumption F and the last inequality, we used the upper hound of np and
2
22

---

Published conference paper at ICLR 2024
Assumption 2
Unrolling the recursion gives:
11 =
( (2
+ + - ohf (1 --
(C.27)
8T X
8 + 1T
(1t - *1
where in the last inequality, the fact that: Summing over & gives:
E1=0
2/6r-11 47 for S
119 87
V
87 mt 1r2no 2]1
(C.28)
Lemma 7. Under Assumption
2 and and suppose that c S 11x and that
| fx]" 2 Fo + b.g the updates of (C.I) with step size 32-L where L. ==
La max, VIVY II, Vs(x IMl satisfies:
( Σ
VEGTTAMM
1 V
(C.29)
10
k=1
Proof Let Leta?=-=miu(( min(1, Im Eisn vROIT1,0 ). We can write the above inner product as:
( Σ (AAY
= "Io"""n==//(''"" Vn mm
- (C.30)
-a; +o V 1|m Σ -
We further upper bound || El=
V VTV by:
11m
-
-
1mm
(VRY
V 11 Σ E(vily1--) Vf(x-
(C.31)
1|
V/
DII m |NTT-11 - x1
Next, show the probability that C.31 is larger than / 8m f [ is small.
Pr(lin
V/
- x Fo
(C.32)
8T1TS + 1 -
< Pr((2|m
+2)
11 - - 112 >
60n 64m 25 1 2 Vf(x vf(x"~1111
Anf + + L2 -. E, 1
21
64 - 64 + /
4n T(" +
+
23

---

Published conference paper at ICLR 2024
Tnf + + 1 + 8rf
16n'T'L² VV((x' ||? a V )
64 + 64n
16
2018
64
25
In the first inequality. square both sides and use triangular inequality. The second incquality is due Markov's inequality and Assumption
The third inequality is due to Lemma [ and the fifth is due the assumption that ni S + Therefore, with high probability, ||m Ek=1 V
fxx""(""") is upper bounded by 8myy Ta + -.pTC + 3 In this case, we can plug the upper bound into C.30%
cllip clipp(n
VFely
(C.33)
1 (|( STATS 2 V/x""//
"00''llV//(x>>>> a.
(C.34)
5 a. "In"""ll/V/V""""
(C.35)
3 ||
$ 8
(C.36)
where the second inequality is due to the assumption that || 2 64 + 64g We can further lower bound a." by:
min(1,
11 Ei= VFlly
min(1,
||m Σi_ VR MjT
(C.37)
NUT VX
The last inequality is because of the assumption that |/ Combine (C.6 and have:
CC37 we
3c
) clip,, (n VF <
V/(x
(C.38)
13
In the other case where [| Eisr VII m7
V5
Sn 8MT
V/
we have:
V (n
(C.39)
We conclude by using the law of total expectation:
Er-1(- B--11-(n-V/xx"""))p)p)) clip
Villy S
2
23
3
25
25 13
10
(C.40)
O
Lemma Under Assumption 7 and 3 and suppose that llae V (x(x c and that yj 2rL where
L = Lo + Li max,, (IIV Il.. f(x
I1]), the updates of C..I satisfies:
niann 1) 5 167 ml Vf(xx "11x""")] 1. ml 27 n + (8r 1 13m + +ni )o²
(C.4)
where 11 = cli Ei V vA(y(,1.))
Proof. Since f I a we have that 7p nrV clip. (Vxx// By the fact that clipping is Lipschitz operator with constant it follows that:
B I1| u 7 V (V(x">>>>)
(C.42)
(B-111 1 Σ
-
(C.43)
24

---

Published conference paper at ICLR 2024
1/1
E
(C.44)
$ B |1|
(C.45)
1/1
2B, EVVA - +22 -//(x'>11
TO²
(C.46)
0+0 '/i 2TL2² B 101-1lly1 1x1
(C.47)
$ n 2r
8 4 0²) + 2 + TO² +
(C.48)
$ 16 (1 + + 87 mp 2 2pEc + rnioa
(C.49)
where in the second inequality, we separate the mean and the variance, in the last third inequality, we use Aasumptionnaande and and in the last second inequality, we apply Lemma[6]
Lemma 9. Under Assumption and 3 and suppose that I fxxx"= 1)l 10C, 11
32. where
L Lo + L1 max, (Il satisfiex:
Ill and that e 2 645 6AnITT, the updates of (C.I)
- f/x
I|I
3 n |11
+ 96m' * +
(C.50)
where clip. Σi-1
Vy and higher order tern 340ml (32 +tt)
Proof.
E, [u] TJT Vfxx
|| [u]
vp Er-
V +n E.-
S 2||
Vf 1]I + 2/ 1y-
-
2|| E,
[u] R,
V 2
E VV -
2|| 2,1 [u] Tp B,
V 2-L2m
E 1|9
2| <
[u]
Th
R, V D0 +
I| 8 o²)
(C.51)
where in the second equality, use the fact that - [ V in the last second incquality use Assumption aadd Jand apply Jensen's inequality on the squared nom function, and in the last inequality, we
apply Lemma We next bound the first term in (C.5T) by showing the probability that vp Eim Fy gets clipped is low because (xx is sufficienlly smaller than Note that:
1| E VAGYTD
I m
- +mll Σ (V VX b)1l M / I)ll
m (VE
(C.52)
25

---

Published a conference paper at ICLR 2024
By the assumption that |/r f(x" I|| S 22c, it follows that:
V gct -
Σ 1 11) (C.53)
Define 6- (11T Ei=l V > c). We can compute an upper bound of 1.-"16""11 by:
E--1 4
Prillu
V
455
Pr
(VF -- VIVVE V + Σ
Ily - c
21p1
0²
Pr 2 Σ
VH - - 21.37 Σ Ilxfa-1 112
(C.54)
1nf
$ And
(2 VR(YTT)) V 21.7
Br- |lly - -x (9))
k=1
B 4nf
o² (47(0" + (2) + 21 - /IVV |||
+7 4
4T (m 02)
16 + 32 mL 0² 16 T 64L 2 32 1.2 1/
6²
The first inequality is due to C.53). The last second inequality is due Markov's inequality and apply
Lemma 6 to the last inequality. Recall that assume 2 64m /To + 64bJTT and therefore we have
64 1/1 Ta 6i1nnn 7² C². Using n/lllV f(x" ")ll jc and n SUFI. follows that:
17 r" 2 + (
1 10"
and 1 $
1..
(C.55)
64
4
32
64
We are now ready to upper bound obtain:
EE,I
[u]
Tp
B.
E
V MII Plug in the definition of u, we
(n - 171 1r.-1
(C.56)
m
E,
f .)]
(E.-iclip, (1
VF 11 1210-11
+1-1 8 11)
(C.57)
m
B
Vf (B
k=
+ 8" mm Σ
||
111 Ex
k-
(C.58)
B--1((1
1m Ehin V 1 7 I11
(C.59)
11-11(11
VP 1-- =1 11p018 =1)1
(C.00)
11 Eim -
VF 1 000 1 1 1)a
(C.61)
|m Ein VA(Y---))
SE..
VF 1)=0111-1111000- 1018
P|
1)²
(C.62)
VF VF
,01,= 10-000-0 1) Pr(6' = 1)
(C.63)
E. VE Pr( =1)
(C.64)
In the fourth equality, we apply the law of total expectation. In the last third inequality, we apply Jensen's inequality to the squared norm function and in the last second inequality, we use the fact that
26

---

Published conference paper at ICLR 2024
c E 1| Ei-1 VF ||ll given that 8--1 1. The last inequality due the fact that 6-11 _ 1.
We next unroll E, [1/m Di= VFLly .)1 and it holds that:
B-- (1 1 Σ
V
$4E,
Σ
VR -
4E, +48,
11ve
Anj B [1 Vf(x " Anf || ||
S To² + 5-) + 4nji
E- 11lyy - 111 40p r V "| })? ?
< (4ni + +2n1 + v [(x || (4 + 16 >
"² 0² (4 r + 32n r 12)C²
(C.65)
Plug
C.55
and C.05
into C.64 and use S 32-T. gives:
18--1 [u Th
8 i
IVX(x 11p 170m +()
+40m 4 { +53)
(
(C.66)
We conclude by plugging C.66
C.5I
and using n
Lemma 10. Under Assumption
and and suppose that
< 2 < 32FL where
Lo + Ii max,, satisfies:
< (I
11. I11 and that e 2 6F 64m.TC. the updates of (C.I
B--
11
Σ
uf
E. 1u
5 aon 7 V5(x
'11
8ni 7 202
S
(C.67)
7 222 + 680ml
72 + +
where u, - :- :=cip El= VDly and {1
f1-1
& if 2 64m 6drp
otherwise
Proof. Casel: c 2 64m vTo + 7 We use Rs, to denote taking the expectation conditioned on the randomness and all the randomness generated before the round r. Consider the following split:
B--10 |||
1
Σ
u 1-
[u
5
1E[8]
= -E--101
Σ
u
Σ KE|S|
E., [u] 1
Σ (E|S)
Er [u;-']
E-- E--1 ']1"
VE|S
(C.68)
22E,-Ill
Σ
u
Σ
E.g
[u "11
Σ Eur(uf 1(,
5
8
[5]
[E[S]
sE[S]
S n. 3 Er- ||| Err,, Er, E--1 [u] 11119
8 Er- |||u
E.,[Iv
"1
2(1
where in the last inequality, used the fact that:
E, (iu Eu,[u" [u= uz - [u, =
(C.69)
and the property of sampling without replacement. We next bound the terms from (C.68 separately.
E, |||u| E,, [u] "119
-E,-1l1m m
v Vilyinn [n "11
(C.70)
< 22 [1|1 m
V E.,, [u] (1/).
27

---

Published conference paper at ICLR 2024
c for all x E R" since [[) 1 By our assumption that e 2 T holds that [xx]]l I nur [VV - [[(x]]++[[/[ S Smax + 2ny S 3e
anp Therefore, have: I| Ei=1 V(((y(n-1)) - We next follow the same proof technique used in Lemma [8 and
The first term can be bounded by:
f-11lluu
m
v
(C.71)
Er- ||
VAI(yTLL) m V
$ 10 ro
To bound the second term in (C.70) we first show that |b Ei V Illl S with high probabilityy
Note that || Di= Vrlly.ti all
& m Eis VF Σx V 4. Define 8
1 1p Ei-1 VF - all cj. can compute an upper bound of Es, 16-'
Ks, 16
Pr[lm
VRly 11l >d
(C.72)
Pr [Imm
VFlly
Vhly
èt 16
=Pr[Ilm] VF
16 2
follows that:
11 Vilyi=11 [u,
mm Vily Bo, [clip (T Σ
VPILY ()0 -1---- +1-8-1111
k=1
||m ViyTi 1) - E., 1 Σi= Vicly
18 +1
1|m Σi= VF
[1,
1I Ei VRGGTL)) )m
VF r-1 18"
VF )00= Bo, 18- 1]1
||m Eie VR
< Ho, [llm
VAily Ks, 11
(C.73)
We can now bound the second term in (C770) by plugging in (3773) and C.72
E 111mm
E., [u] I]I E, [R., ll|m
Es, 18 '11
VP 16m TO²
1l E.., E,
62
k=1
16 x²
E,
16
[5m
[
I|
+
5र T2
+ <3)
à
(C.74)
where the last inequality due to C.65
It remains to bound the second term in C.68
E. 1|| E., [
1-1 E,
[u
< SEE, ||| E., /x (xxx="""))===- 2B
E. [n !
(C.75)
2E (005-=llu-----rV// " + In - -
28

---

Published conference paper at ICLR 2024
where the last line we used Jensen's 's inequality since the squared norm is a convex function, Applying Lemma S and and wrapping up yields:
B--
Σ EES
E,- 16, [u]"
V 111 + 41/ 2 + 320
+
(72 + [()
(C.76)
+ (1
// 2m " 1|1" + Am 7
+ + +
310ml
r
7 + (2)
680n
0²
$5 15n
| | f(x |1| ~ + 8nn 5²
4,2 +()]
Case2: 64/j
6é & c 64m Fo + G4rpTTSaa..
B--1
Σ u B. (4]""1
i8|8)
E
!||n|
1 !|1
(C.77)
8
E,
|||u
| E.-illlur///e E, [u] (11".
s
Applying Lemma
8
and
I and merging cases concludes the proof.
C.5 ACCURACY PERSPECTIVE
this section, we discuss how choose the stepsizes reach e-accuracy for Algorithm P (min-ell) m [xxlV/(x))II) e). According Theorem I we obtain following convergence result when
Ii S O1 (Fotre) ) (by taking the square on both sides):
min BlJ f(x))I S O rE|1,R
Fo MR
70 ( +==
+*)
(
+
K
Since the second, the third and the last do depend R. have to pick vn and My such that each individual less than e². From the second and the last terms, deduce:
n S min 0
& 1LC
T(= + (3))
00 VTo + A.
(C.78)
remains to deal the third term. Recall that fl 2 ((V)) and v s O(1).
casel:
θ Ay
()) > ((s): we need to set
VTE
111 S o
T3 O(Vn)
(C.79)
TL( +
case2:
0 A(AviL
(?) < @(s): we can choose T/y to be large possible:
fJ ((A). 7/5 min ArL(
nE
(C.80)
AvL
Finally, we can compute the required communication rounds R by plugging in the respective choices of m and No and letting the first and the fourth terms be less than s².
C.6 PRIVACY-UTILITY DISCUSSION
C.6.1 LOCAL DP GUARANTEE
Assume that the server might be malicious, De-FedA with update rule C.I (per-update clipping with DP noise) aims at protecting each user's data by providing the formal DP guarantee for the clipped model updates between every two rounds. Note that, for each client, the neighboring dataset in DP-FedAvg defined by any alterations made to the data points within that specific dataset. In other words, can treat the whole dataset of each client data point. To achieve the formal DP guarantee, the variance ofe should satisfy the following condition. (Note the DP noise in update nule C.1 is set z \o 2 1) for all E [p] and N.)
29

---

Published conference paper at ICLR 2024
Theorem 11 Abadi 2016)). For any Eve S O((%
wz RR. 0 and DP-FedAvg with update
rdee C.J achieves (Enr, oo-local differential privacy for any client i E [m] if we choose
c$ cS 1og(1///
Opr ?
(C.81)
where UDP ==
Tap vd
Proof. Let q == x- According to the analysis from Abadi al. (2016), suppose A; at round satisfies
(e',8")DP for any O,... R - 1 and i E [r)) then the total privacy guarantee after R rounds is (Oig/Ree) O()"). follows from the Gaussian mechanism (and coe qvRR', Re', d 8') that, each opr should satisfy
Aoylog(1/0)n 3pp f
(C.82)
EDP
where A is fz-sensitivity of the algorithm output for which the server receives each communication round. and can be bounded by 2c since (x) clip, (y)ll x 2c for x, R
C.6.2 OPTIMAL PRIVACY- UTILITY TRADE AND CHOICES FOR HYPER PARAMETERS
Based on the privacy budget Epe and 6, the ideal approach involves an initial selection of clipping threshold with the aim of achieving good privacy and utility trade-off. Subsequently, the noise scale obe can be set based on Theorem [1] The final step entails choosing appropriate step sizes to attain the optimal iteration complexity. We next provide the theoretical good choices of hyper-parameten, including e, n and fg to obtain the optimal privacy-utility trade-off and the communication rounds R.
Throughout this section, we assume @( + 5²))= e _ + (). similar argument can also be made the other way around. Let A = VFoLE vi
B = + 5 and N, = minre(),n) (x.)/((x.)I
Let e 2 @(mvTT + WT().. We recall the constraints on the stepsizes иµг & O(+). m0 & O(1) and
No 2 @(vT).
Taking the square of 7 on both sides and plugging obe @ R) into the convergence rate, where v (log(1/8) (suppose full client participation, i.c. = n), we obtain
N₂ S so
Pb
LMg vc R)) + ( 2 npe
L' 2 e + 1
1ogTh + (²)
+ n
B
d
(C.83)
We minimize the first four dominating terms w.r.t R by picking R
0
V.n ono vT
and C.83 thus reduces to:
N, s O
CA+A TRT
12 22
(2)
(C.84)
Case 1: ((4) 2 O(H)
It is clear that A² dominates the error terms. Therefore, to reduce the number of rounds R, we should pick the largest Cgly in the denominator of R. Note S O (0(=)z) by picking = O ((=zz) it remains to find the largest number for TTT.. It clear that we can pick WiFT as large as & from the first term in (C.33. For that, we can pick yp @ VaLL and c 0 0(4) so that 72 2 @(yn)) to finally achieve the guarantee. By these choices parameerram,trrss, the optimal privacy-utility trade-off's then:
Kolw
v Fin
No s ((47) o
with
R= θ
(C.85)
AV
Lv
Case 2: 0(4) < ((B)
To balance A and 3 B, we lot = g1/s 777
mा 775 It follows that en2 173 TT Therefore, to reduce the number communication rounds need maximize ryn, under the constraints
g4/a
30

---

Published conference paper at ICLR 2024
vi L² & B1/8 and T B 1118
(C.86)
With additional constraints on the stepsizes: & O m and neT S ((()). The largest 7 we can ohtain is
Di min (1.
12/8n n)
To obtain this bound, fl = ((n)) and let m @ min 21 Dz)
B8
where 1) min
guee .1.. By these choices of hyper-parameters, the privacy-utility trade-off is then:
VonL 2 AUS.
N, S S (OBBI////))
with R O
(C.87)
H1/6 min
A A13 vo
C.6.3 IMPLICATION
Let us begin by examining Case 1 characterized by relatively low privacy budget, with a and ( being relatively small. Plugging dlog(1/6) (suppose full client participation, i.e. re) into C.85 we obtain the optimal
für
privacy-utility trade-off as well as best communication rounds as follows:
[(+ 5o (f
FoLd nefr
nEP Ld loggg(1
min rE(Lm
R θ
(C.88)
by choosing
V Filld Fooldoog(1//)
@(v).
(C.89)
Vieepe
Due to the relaxed assumption on bounded variance, the optimal utility is of order O (dlvet) nage
(16)
which is the
square of the standard utility O [dgg for local DP under the bounded stochastic gradient assumption.
viicpe
Since the ratio between the number of client n and (Ewr. 8) is unchanged, increasing n can still lincarly decrease the utility error. Further, the effective stepsize 1/11 = +(=z) decrease as increases and R does not depend on т. This implies that performing 7 local steps equivalent to using one local step effective stepsize ) Hence, under the current analysis, we cannot prove effectiveness for doing multiple local steps when the privacy budget e and are relatively small.
Let consider Case 2 where have large stochastic noise and heterogencity. Assume and large enough such that 1//6 2 A2/3n. Plugging v <loo((1/)) (suppose full client participation, i.c. $ = n) into C.87 we obtain the optimal privacy-utility trade-off as well as the best communication rounds as follows:
min |[X))( so (Fooddlog(1/0)) rEll,N)
( 73
Eppl (FoL)
R R= n (d (doog(1/)))
nten
(C.90)
The utility increases and become larger. While local steps reduce the stochasticity coming from the noise a², the caused by heterogeneity related DP training but is also known for the common local SGD methods for solving heterogeneous systems.
be reduced. However, this phenomenon only
C.6.4 CONNECTION CENTRALIZED DP-SGD
While DP-FedAvg with update rule C.I is federated learning algorithm that aims at protecting user-level privacy, it is still comparable with centralized DP-SGD from pure algorithmic point of view when r = 1.
Let us now forget about the federated learning setting and think about DP-FedAvg in a centralized manner. Let Ç = 0 and r = It is clear that conceptually, DP-FedAvg is equivalent to DP-SGD with both inner and outer stopsizes, and n becomes the size of the minibatch:
X X, 77
clip. (m (T..))())) -
(C.91)

---

Published conference paper at ICLR 2024
Suppose the size the whole dataset Nou. Then target optimization problem becomes:
f(x) =
Fx
(C.92)
Noua
with
B
(C.93)
recovers this special case. However, the notion of DP is no longer the same as hefore. In the centralized setting, DP-SGD considers the glohal DP guarantce. In other words, what we should protect the uveraged clipped gradients 1 > clip, (..... rather than each individual update. Therefore, if running At steps, in order to achieve (E, OJDDP guarantee, the noise dur should satisfy (by treating E as single noise):
Essentially, the analysis in section C.6.2
Tue Var 1 Σz.)
de (og(1/
2.)
(C.94)
N2
Neaa fo
From the formula of oi.. obtain is relatively small, then obtain the following optimal privacy-utility trade-off and required number of iterations:
on 1og(1/5) Following the same discussion as in Section C.6.3 suppose N Na
f(x,) of log(11) KELL
N Sup (1)og(1/8)
R= e=
min
(C.95)
N
The obtained tra is the same as DP-SGD with single stepsize. Introducing an inner stepsize to the clipping operator could potentially drive convergence towards any desired accuracy level. However, it is crucial to note that this may come at the cost of an inereased total number of iterations, consequently amplifying the associated noise levels.
32

---

Published conference paper at ICLR 2024
D PER-SAMPLE CLIPPING
We first present our more refined convergence result formally, then prove the results for the convergence.
D.I CONVERGENCE RESULT
Theorem IV (Per-sample clipping). Suppose function Ja sotisfies Assuupttion 3 then if we run Algorithmp V
for T = R.7 steps with R communication rounds, T local steps, clipping threshold and step size S 14LT
with L = La + min(e, L and M := max. [V (xx)). then it holds that:
((xx) -5 net
f(x))
min E [( S 1.3]
q/
YLo
ngL²
+
1 Icco(o+Came)
(D.I)
min Lov/to2 + +2(2.0) min (o+c, (+cc.(5)))))))))))))){))))
where if o Olo + Smax) e
Theorem IV is more refined convergence rate compared to Theorem ! in the manuscript. In Theorem !| we observe that even if when c + oc, we cannot recover the unclipped convergence rate as demonstrated in Koloskova et al. (2020) due to the terms O (vnlL(3/m) and o (1ov7790)) However, we can cancel show influence the noise O(vro²)) such that we can recover the convergence rate provided in Koloskova et al. (2020) when e - oc based on a more refined analysis by discussing the rate when >> O( + (max).
the influence of O (VV5"/m /n))
Note practice, can set the stepsize to y I O ((1cca to avoid knowing maximum the norm of the gradient M. Since this stepsize can be smaller than the theoretical 1 defined in Theorem [V] the convergence rate is also guaranteed.
We next give an updated Corollary which takes into account the differential private noise. After that, we give the proof for Thenrem IVii the following sections.
Corollary Suppose function satisfies Assumption 7 3 then if we run Algorithm with updating rule
Y. + y. 78 + 2.) for 'I := R steps with R communication rounds, local steps, clipping threshold c, stepsize S 141. with I. == Lo + - I.1 and == max, (Xx)]], and ahe as the variance of added
Gaussian noise such that 2, N (o. fa) then it holds:
min ExV])(x) 00 [(x0) -
(xx) nT
neT
y1o2 +
1cc
(D.2)
02 +
min (LnVFOR + min o +
nLoBe
n1. opp
where f: := > Olo + (max) else
Note the stepsize defined in the above Corollary has to depend on M instead of min(c, M). It cannot avoided due to the conditions in Assumption (sec discussion in Appendix A.I.I). I). as the algorithm does not clip the update after adding the noise.
Local SGD To facilitate the proof, we describe the Local SGD algorithm following Stich 2019. There are n
nodes in total. At iteration in parallel on all the nodes E [n). we have:
Bite = clip.
(VF. (x,,))) = min (1. "'IVFICANNI
1
VA((x.)).
(D.3a)
If 1 is multiple of
XX
X1.
nB..
global averaging.
(D.3b)
33

---

Published conference paper at ICLR 2024
Otherwise:
rigi local step.
(D.3c)
Additional definitions Following Stich 2019). we first define virtual sequence {&t 120 as:
X1
(D.4)
We then define the consensus distance between and X
Nr xx,,|??
(D.5)
As we are discussing the convergence rate on norm the gradient, to distinguish between different cases, given as clipping threshold, we define:
Jet {t; [xx)))) e), J++ ft; 2 ((V)())) < Jc,J5-- (1:IVV/(x))) < )) (D.6)
Specifically, we also define the following two sets to distinguish between the norm of the gradient within two communication rounds given 1 - ly as the index of the last communication round (kt S r 1);
Je-. = {;: (xx,)l 2 C,j
Re, 1}}
(D.7a)
Jz+. = ef:c/2 [IV.(]] [ <.j
ke, 1}} k., 1]}, Je-a: T=+. Ugg
(D.7b)
Jz-. ([]1I
(D.7c)
D.2 PROOF OF CONVERGENCE
When < O(a + Smax))
We give the proof for the convergence of per-sample clipping in Local SGD. We first bound the difference between the model update in Lemma [2 To give the convergence rate, we consider when the clipping threshold is large c 2 O(a + () and when the clipping threshold is small e S O + (). When the clipping threshold
is large, we present the convergence by discussing when the norm of the grudient is large in Lemma 13 is intermediate large in Lemma 14] and is small in Lemma 15
Lemma (Difference). For vj S Tomm
I4LT with
Lo min(e, M) it holds:
ER, min
1961.2
(D.8)
588n'r Σ (02 (3)
Σ ?
Σ
1V
1
95L2T
jeJe+it
jeJe-,t
Proof. Following Koloskova et al. 2020). we assume that there exists a kt S T such that:
R.
Σ
Σ (g.,
BT)ll" 1²2 Σ
Σ
giy
(D.9)
-
Duc the clipping operation, know || c. Therefore, given 1) Tul. we hound Ra by:
1-
&.all 5 6²
Σ
(D.10)
196
j-1-k,
We then give more general bound for R; given the definition of the set of indices Jet, and Jo- from Eq
D.7
Rs
llgu
(S(x))
v/(3))1
71
n
jEJ.
jEJe .
< TT)
2711
2
Σ
(D.11)
383.+,1
JEJ
JEC
S TT
Σ
2712
-
- +27m²
Σ
||V[(x))1
J6Je+.t
n
t= J6Jee
JEJe-.t

---

Published conference paper at ICLR 2024
The first inequality uses the ussumption that k; S r and Cauchy-Schwartz inequality. The second inequality uses the condition that if | [(x))l e for j E Tet... then lighter upper bound we can give for l|g:; ll is to simply to use the fact that ||s || S c. However, when [x;))l c, we can give a more precise bound using
triangle inequality. The third inequality uses Lemma 5
We next give the bound for A. :- El| (x)))) V (x( 311 using the (Lu, La) assumption:
A
S 3E
V Fl (x
V f 3B| V)(x,)))
VI(xx)]ll + +()))(((x))))))))))))))))))))))) - V
(D.12)
30 3(Lo
L | ||x, x + 3 ( {/()))||*
Plug Eq. D.12 back to Eq.
D.II
we have:
2
ER S Tm
Σ o²
Σ
(3o" 33L0 [+l) xI1l +3IV//(x)) vf(x;)1'*
JEJe+i
JEJem.t
+ 2T12
Σ
||V[(x))1
JEJo-.t
S Tm
Σ
à + Gro Σ (2+ Σ
(Lu + [VV[(2))) + 27m2 Σ |[V
JEJe+.
JEJe-.t
JEJe-.
JEJe-.t
s tm
Σ JEJet.
2 6rr
Σ (0"
+ 67 6r' L Ra 2n1 Σ JEJe-.t
||
JEJe-.
(D.13)
In the last inequality, we use the definition that L = Lo + min(e, M)L, and Ejer_ Lo + +[V[[28,))11 S
Ejer.
L. We also uses the fact that EN, S ER, Vj E [t - ki, - 11. With rj S TH.. we have:
ER S 1901.7
Σ
Σ
588T1
Σ
(o" (5)
(D.14)
951.7
JEJe..t
JeJe-.
JEJem.
When O(a +
Lemma 13 (descent lemma for [xx|()))|| 2 c).
Under Assumption 1
2 and and
||]](x))| 2 with
stepsize vj S M4 we have;
53c V f(x))l
f(x.) f(x++1)
(D.15)
128
"
Proof. We start by using the smoothness of function f (Lemma and taking the conditional expectation:
[[f(x(+1) < fxx,) + (e)(((x), Lo L.IlV ((l)V [|A
(D.16)
2
We first look at the second term. Using Lemma and letting a [[ we have:
(V (x.)..
= 2 n )
= 2 Σ
+
1 2x
B 1l
1
1 Elg (V/(.(V
n
"
< 110 | (xx)
2an Σ El
7
7.
(30² +3/0 [V.)(
+ ()())))1
2x
11
|V/((x)
1
El 3y)(2++()
3ry(Lo L R.
2
2an
2a
2a
ndl v((x))
3d"
36"
3r + [())))
+
Σ
B g..
2
c²
2a
2cm
35

---

Published a conference paper at ICLR 2024
/(x)]
3nyLa L1
"
Σ
"
E El
16
2a
2an
Lo L1
7
16
2a
196(Lu + M ML))²
2am
[xx)]V/(xx)]
V
11
E Elggdl
16
392
2am
337
no (x)))
2cm Σ Bl
"
784
The first equality uses the update rule E[Ax] == -rEgg... The second equality uses Lemma D with
a [[]]( The first inequality uses the projection Lemma and follows the same procedure
in bounding Eq. [.12] given Assumption [ and 3] The second mequality uses Assumption g and
the definition of the consensus distance R. == 1 2i=i ||xi,
&. The third inequality uses the
assumption that 30 302 S 8. The fourth inequality uses Lemma 12 (Lu + L [xx[V((>))l)) R.
min( 1507 Ejer.t.. + Der Eyer.,, [|[ +
D5r Eser.., (a² + +²)) The smallest value in o² 3 c². For this term to be smaller than 196 we would E - [V 56.24
3
the second tern will be 567
require |/ fxx))l S De [t - 4, t.,-11, 1]. However, the gradient norm for the current time step is larger than e, [x+]( > e, which makes the requirement [Xx))l s 25 2g Vj (t --- k.,
difficult. Therefore, we here bound (Lo + L ((x)))) S
Take the above equation back to Eq. D.16 and with S 14(40 we have:
f(x(411 $ f(x)) 53 V (xx))l
(Lo + [(IlV(()))))
Σ
B|
128
2en
2m
f(x)) 53
[xx)]l
f
|r.ll (1x-o|//(x))1144) - 17 Lu
|g.
128
2en
2n
$ fx.)
53nc|
[xx))]l
17
Σ
Bl
-nnn-nll/iii /lIVf( no0 S f(x,)
53nell
V fxx))
128
2n
128
(D.17)
The third inequality uses the assumption that [[v)(())] > n S 4e given 7 2 1.
The last inequality uses the condition that
Lemma 14. (descent lemma for & [[
Under Assumption and condition g.
[Vx))]] < c with stepsize v I I4LF given L == Lo + min(e, M) we have:
7c [(xx))
f(x,) f(x=11)
3L
2 Re.
(D.18)
32
Proof. The proof is very similar to the previous case, we again first look at the term (V.().)
2 (V]()) = n > [VJ
= "IVS(E))
2n >
Elgll
1
Elgg - (S()). 2
2m
1=1
"1 Σ 1l
< 2
2n
1 (300 + 3(10 + || - - -
2n
" Σ 11
$ 2
2n
370 + 3rx²
3
[V
Σ
||x xx11
2
2n
36

---

Published conference paper at ICLR 2024
< --V//((R)I
"
Σ
Ellg
31j0² + 3ry5²
3(Lo
[V/(xi)]|
2n
2
2
[[V]((
3
[](x.)]
3nc || (((x:)]
3 [V [2xx))]11
R.
22 2mc
Σ
K] gg,
4
2
nel [xx))]
30 + 35²
3(Lo +
[V
L1)² 2'1
R.
11
Σ
B
Blga
x²
2
2m
[(x))V
3(Lu + [IV [11)"1
BllB..
32
2n
The second equality uses Lemma 1 with a 1. In the first inequality, we consider if
V f (3.)
(V)(()) = (x,,), so then |g:. - ( (Xx.)) can be hounded using I Lemma
and Eq.
D.12
The fourth incquality uses the condition that if 5 S II (x.)) IIl I c, -[V S i and
(())))
2 1.
The fifth inequality uses the assumption that 2xc2 the condition 17 I Tuz.'
= 1 Take the above equation back in Eq. D.16 and given
obtain:
T f(x))
)|
3(Lo + [V(x.) L1)
7 + L.IIV.(xx)II)
f(x++1) S f(x.
Rs
E Bl
B l|
32
2n
2
7sye | (xxx)
3(Lo [V((x)) L1)²
f(xx)
Re
Bllg.elf nLo
32
2
2n.
V (xx) )|
3(Lo + [ )1 L1)²
S {((x))
R
32
((x,))
31.2
$ fxx))
Re-
32
2
(D.19)
Lemma 15 (descent lemma for [|V](( < {), Under Assumption with stepsize 1) S val. given L = Lo + min(c, MI we have:
1
22
3 and the condition
[ <
|+((2)|| < [(x.) 1 Es(((1) 7 12 + 16 (o² + 72(a² 53)
+
(D.20)
Proof. In this case, cannot prove like in the previous cases. We start by defining an indicator function 6, = F (x.)ll > c). which indicates that the stochastic gradient VF((xa) at time step clipped. O.
We first show the bound for [B[6,.] Pr(8,, 1) as de, equals
Bl8..) Pr(
Pr[1 V (.(x))) || d) S Pr(lVE.(xx)) ff. > -
(D.21)
We uses condition that [Vx((
& and triangle inequality. We then square both sides and obtain:
( > 6 E < (x.)).))
4B V. 2x
1(3BI P. (
V fi 3/ V + V (xx))))
12o - [2 V/ 12(Lo [V (1) | x,|12
The second line uses Markov inequality. The third line uses Jensen inequality. The fourth line uses Assumption [] and As we have n workers, we next bound the term 1. Ei= E.
12 +
12 + (
B18..1 5
(D.22)
2
37

---

Published a conference paper at ICLR 2024
We next bound the differences between [ - Eg...l? To approach the bound of [|V fxx) - Eg...ll..
we first find the expression for Eg...
Eg,, Ed [VF(())))) (F((K,,)) + B(I (.))))
-1) V Vf(x)))
Therefore:
Σ V [(x))
Egal 2 [Vxx) + + Σ Edia
(1-1I7R(x..)) VF((x..)) - Σ v [xx,)]]
Σ
1=1
1=1
1=1
2 ||Eós, (VVi(())))))
VB((K))) +211 Σ V(((x..)) - [((()))
7
2
(Pr(b.. = 1)) (1- (1-1IT((Z.)))
Vbb = 111
2
-
Σ Pr(óe. 1 2(L + (()) [1x))) Σ xx xx.Il
Pr(de 1) 2( 11 12,)2
<
2
Σ Pr(d.. = 1) + 6(L + 1V/ x1
(,(2)) [[(R,)] 2 2 (V n.
12 Pr(ó... = 1)(0² + + + (Lo + [/(x,)]
+ 4P = DIV ((x)) 1 + IV Re
The first incquality uses triangle inequality. The second incquality uses the rule that E 6x]| Pr(6 1) = 11, [|]]] = (Pr(6- = 1))² | 5 = IIIl?. The third inequality uses the condition that (x. > when d5, = 1, and Jensen incquality for conditional expectation. The fourth inequality uses the fact that de is either or 0. We next approach each tern individually.
Pr(o., 1)(22 +5-) +4600++59
144L' 144L'R((0' + +2
62
e²
141(a² + 52)
R
6²
12 n
1441. Ri
Pr(O,, = 1)(1 + 2 Re S (
y1 Re
3
144
$
Re.
196
For both terms, we use the definition == Lo - min(c, M)L, and the condition Lo [|V](())] S L.
We also assume that 12(=²1<²)
1. For the second equation, we know that Re is bounded by the minimum
18.
between Eq. DD and Eq. D.14
We here choose to use the slightly larger bound from Eq. D. for Rs to
continue the proof. Now combining the results, we have:
144(o² + 232
144 196
12 19
fxx:)
2
L.
+
G
(D.23)
(Rt), Elgad)
-
|
111
Σ
Ega.
1I
+ 111 1
Σ
v/(x)) Eg..ll
2
2 n
s- 1 +
72
72
+ 22)²
Σ
Eg...1
196
d
2 1=1
38

---

Published conference paper at ICLR 2024
We next approach the term B| Σi= B..ll2
1
gi
1
Ell
gi. Eg.i1 1
++211
Σ
Eg.ll 2
1
Σ
Bllgi, Egu
1
+ 2 Σ
1
Eg..t1
7
2
12
i=1
2n1 1=1
i=1
BllB v)(x,)11
+ 70
Vf((x))
Kgg.el 1 + =
Σ &gg.ell
12
i=1
1
Bllg.. V/(x))1 1
Eg..all
7
144(0² + 63)
+ 2
+ 196
144
L +
48(0² + + R.
1 (x:))1)
6²
1
1
(30"
+ 3C + +3L B.)
Eg Eg
72
3(0² + (2)
7
141
L
R.
+ 12 +(9)+ + 1212
4
196
16( + +(4)
(
37
144
1.2
R4
Eg
2
196
2
(D.24)
The first equality uses the fact that R -1 Bi.r Ega,:
0 and the variance of the sum of independent variahles equal to the sum of the variance of the variables. The first inequality uses Jensen incquality. The
second incquality uses the result from Eq. D.22 and Eq. D.23 The third inequality uses Jensen incquality and
the assumption |/V fxx,)l 3.
Therefore, using the smoothness assumption and taking the conditional expectation, we have:
Bf((+11) < [(x.) /(I0/(
415g 196
L2
72n(o=+
72n(l=
2 1111
Σ
Eg
2²
M(0" + +(2)
3370mm" 1.3
q I.
Egg.:/
196
(D.25)
1m1
$ f(x.) - 2 (xx)))l
115
3770
)n1.² R.
196
14
+ 12n 2 + )² 16,/ L(o
(
n
Rearrange the above equation and divide by n, have:
+ || f(x,) - f(xx+1)
7 1.2 + 16n4
(0² + (3) 72(a² + c
+
(D.26)
7 2
Wrapping up
When Re S 190r Eser,,, d abr Eisr... [V + 688
(0² 2 (2)
Now,
we
wrap
up the above three
cases
together.
Given
As
ErErer cIIV + c[([f((x)]l Exedg- [IV.((
128T
fxx0) -f" Σ
31.2
71.2
Aa <
R4 +
Σ
R
281/T
56
64
163
n1.
(0² + (2) + 9(0 22)
2
4e2
(xx)
1
(d" + (3) + 9(0² + 3)2
28n'T'
2
46a
39

---

Published conference paper at ICLR 2024
Σ
3
Σ
<[[[[()))]
+
Σ
Σ
|V
56
190r
95t
95T
g+
JEJotic
SEJ
Σ
7
Σ
E
|[V
Σ
|V
T
64
190T
tE. 2-
JEJ++.
JE f++
JEJ
Σ
3
588TT) 1,2
+++
Σ
7 588mn 1,2
Σ
(6 +
56
95
64
95
g+
JEJ
1639-
(x00 f-
nL
(0 + 9(0 +2)
281/
2
4
Σ
d|V/(x)]l + T
7
cl
VS(x)]l+
7 61 95 [X))( T
Σ
T
61 190
61 95
1eJe+
1EJg
16
10 + 19
13
the last equality, each term at time step in the parentheses can maximum appear k; times and 4 S 7 1. As for the coefficient for each term, we can simply bound with the largest coefficient from when / E Jg+ + and t E Jg-. We can also verify this in example later. Note the same terms appear hoth in the left-hand side and the right-hand side of the equation, and the convergence behaviour between when Je+ and é Jg+ similar, so we can rearrange it:
Σ 1EJel
Σ [IV((8))1) 155g
f(xo) -f"
nK
(a²
+ +²2)
1527
281/T'
2n
H(0² + 2
13
2
L' (o" + 52)
T
19
(D.27)
We know that x² 2 2er 5² for any O. Following Koloskova al
2023
can get
E.Eo, (/(x.) - =²) < A. letting A f(xa)-f" - abie +c"
+ L' 70
without considering the coefficient, and VA, we have:
f(xo) f(x²) +²
Σ |V VA 1EJ9
T
11
mpllo++57 + V (()
Summing up the two cases together. we have:
[[v)())) f(xo) f(x²)
f(xo) f(x))
T
offT
1/
(D.28)
nL(02 -2) + Laps v [a02 (3))
When L- S
instead 1,2 R. hounded by Vt [?'), then we would have similar convergence rate Eq. instead of the term Lay Vlo2 + (2), would have term that is
D.28 but
fx(x))l f(xo) f(x') + f(xu) f(x)) 0² +
nl(02 +(?)
tc. (D.29)
T
enT
40

---

Published conference paper at ICLR 2024
Therefore, combining above two cases from Eq. D.28 and Eq. [b.29 together. we have:
[Vv)( f(xo) f(x')
f(xo) f(x*)
+c
orf
1/
6
(D.30)
n1.00 (3)
min o
When < O(a +
this part, we assume clipping threshold is c < 12 12Ç and 20 20Ç S [X())) Note, the numerical value chosen high here to make the proof simple and clean.
Lemma 16. (descent lemma for c² < O [o + (²)) Under Assumption and the condition that c S 12 12,, and 20 + 20ç I [xx)( we have:
VS())l S [(xo)
(D.31)
11
Proof. We again start by using (Lo, L1) smoothness:
(La L1 L
Ef(x++1] f(x.)
(x.)(()...B.)))
D e|
2
(P 1, (xx))
fxx)) (x.
(D.32)
2
f(x.) Σ f(V)( gn.) 3 + L, V [[V
10
The second inequality uses the fact that after clipping, the norm of the stochastic gradients is smaller than the last inequality uses the assumption that || [x)))]
We then define indicator function de- If (x.,))) ((())]l > 12x 12)lV (x(x)))
(lug el1) lxx, x. We will derive the convergence rate based on d next.
When 6,_
0
If - = 0, then
This means that strong variance holds for some of the stochastic noises. Assuming a, = min (1
we have:
- n
(i(()))
1 Σ v/(x) -
avIlV/(x011=
[ [[(x))]
(12
44- xx(l)
Σ 12x 12 V/(301|
+Lo + -
au v
12 (1. [[](

---

Published conference paper at ICLR 2024
+ 1 n
Σ [dllV/(<))]
(3 10 [
V
T
40m
We triangle inequality in the third line. and 12( + S ( seventh inequality.
s1Zotmitc..12217 in the
As a = min (1, (195)(x we can bound 1 " Ei= ax
1
D [Vx((x)))
12a + 12 - 7ooo + [V/\x))
(D.33)
f( |1 [x())]
fxx
The second inequality [[[[((=)]]| < 12 |[/|()))| [x,,)) (Lo + (()
[V..))) and [VF((x))) 12r |/ (xxx))l The third line uses the condition 1 bound the inner product:
3U04+mn क [V+ Therefore,
13 07 [VA(
(V((()))..))
(D.34)
When &
If de- = 1, then some stochastic noises can be larger than the assumed variance. Therefore, we cannot bound the inner product as before. Instead, we can use Cauchy-Sehie Schwarts inequality to bound:
VFF < Σ (.
<(V/((x)))
(D.35)
We next derive the probability ((( - vs(x))| > 12r + 12 (x()))
[[(() 12(Lo +
V L))lx) xc|l
(x (x(())
12x (x)
xx
[
12o + 12 71
12
(D.36)
Therefore, combining the two cases, we have:
< Pr(fa- 0) Σ ((V. V
Pr(6._
1) Σ
(V. +V (D.37)
<
11 13
Jd| (xx))
-
1267
12
Bf(x++1) S f(x.)-
7 (((x))
3rp la vf(x))l)) f[v/(x))]
10
(D.38)
< f(x.)
DC
[(xx)]]
TT
42

---

Published conference paper at ICLR 2024
Rearrange the above equation, we have:
[V)()lI f(x,) - f(x(=1)
(D.39)
Wrap up there is at least one iteration such the gradient norm small [V](x))] O( + (). then it simply holds that:
min / < O( + c).
[E|1.T]
Otherwise, can use Eq. D.38 bound the gradient norm, combining the above two cases and averaging over T iterations, we have:
[(xa) f(x') neT + to+s).
min (()
(D.40)
When O(a Smax)
When we look Theorem [ let -> compared to the convergence rate from Koloskova et al. (2020 the
only terms that are different from the unclipped federated optimization convergence are: O(r"a") and O(v + )
These two terms appear the case discussion of when || [x,)] < 3. Therefore, we mainly show the proof the case | f(x)(
to illustrate that recover FedAvg.
For the remaining of the proof, is important note that when /[*](x))| and 32 12(a + Gmax). we have:
| s ((.)) Vf(..))
[V(() S Smax 2
We first give an updated difference lemma that recovers ra²: Lemma 17. For & T4(Lo (TLLe. and O(a Emax), ) holds:
E.R. 5
1097n²
Σ
o+
7in
Σ
|V1()))|1
288n + <2)
136r
218n"r² <²
20
6²
JEJ g+
JEJg-1 g-11
Proef.
Σ
Billl*
1
Σ)
Σ
giy Eg:ll 1
1 Σ1
|1
Σ
Egall
JEJy-.
1=1
JEJg-1t
1=1
JEJ
(D44)
<
Σ
Bis
Eg.ll
71
71
j63g
$EJ
The first equality uses mean variance separation. The second incquality uses the fact that the variance of the sum of the independent variables equal to the sum of the variance. We next bound Ag and As separately.
Au
go (((x)) + V)(()) Ego 1
2
Σ
VS(R)) 2
2 Σ [[(s) Eg,,11
2
Σ VF((x))))))) v/(x))1 )11²
Σ Vf((x;) Eg
n
$ 2 - 1(Lo + 1|V.
Σ Pr(d.; -]), ) 2 1(Lo (V7((8))114))
< 40² 288(0² + 2
2 +
72
L
+ 196 |
19
(D.42)
The first inequality uses the triangle inequality. The second inequality uses the projection Lemma 3 The third inequality following the same procedure as in D.12] The last inequality uses the result from Eq D.22 the definition of = La + min(e, M) and the condition Lo + // (X;))[ S L.
Aa
Σn
Egal
Σ1 Σ
Eg, VA(K,) + V)(x))1?
JEJ
JEJ
43

---

Published a conference paper at ICLR 2024
Bgg;
VA(x,)I|
2 Σ1
I|
Σ
V1((x)) - V v/<s))
J6
(.) Vf(())) VX(()))|| 27 + 2
Σ |
g
16
Pr(O 1ill Σ
VF(X)) 4F
Σ
(Lo 1V/ n, + 22
+ JEJ
Σ
SCJg-it
47
12 + (
12(Lo + \
Σ
Σ
IVT(x,))|+47(( + \V
Σ R2
x²
JEJg-
JEJ
2 + 2T
Σ
|V
JEJ g-1
g-
48 + (2)
48 LL + [V
1 E E
|V((x))) 4: + -VV L1)²
Σ B
n
JE.
JEJ
+ 27 2 + 2T
||V
--
288(0 + (
2911.2
Σ
R2
+
145 196
+ 2r)
Σ
|[
98
jEJg
JEJg
+ 1. 2 Σ
Rg
+22 22
JEJy
28 _
291
1,2
Σ
145
2T)
[V 4TL.
Σ JEJ
R2 + 2r
98
196
JEJg
JEJS
2
The first inequality uses triangle inequality. The second inequality uses Cauchy-Schwartz Schwartz inequality. The third inequality uses triangle inequality. The fourth inequality uses the result from Eq. D.22 The fifth inequality uses the fact that a & when a < 1. The sixth inequality uses the definition L. == Lo + min(c, MI and La [[&)(( L since E Jg-.s. Combining the above two equations, we have:
galll s An"ro"
1075 L?
Σ
R +
145m
Σ
[[
7
JEJ -.
6
98
JE3
196
JEJ
7 + 53)2
20
f
+
R2
Σ
||
6²
98
196
JEJy
JE3
+ TL2 Σ
Rg 27j
25²
570m + c3)
17.
Σ R2
682
Σ
|/xx))
6²
98
196
JEJ 4 8
JEJ
+ T0" + +2n1²²²²²
(D.43)
2 506 +992
1758127L2
ER S TT2
Σ
Σ R₁
98
JEJc+.culg+.. g+
1EJg-.
(D.44)
682n)²
Σ
|V/(()]|| + +4 222
196
JEJ
44

---

Published conference paper at ICLR 2024
Therefore, given vj S 14br we have:
E.R - 109rn²
Σ
Tin
Σ
|V(()))]
2
136r T 0
218n"r² <²
20
6²
JEJ 5-1
(D.45)
We next bound the term E
Ei-1 g..ll
given Lo Mi)(,,
1
8
=
=
1
Σ gis 18g.111
1 111
Egg.e
BllBs, 18ga p+ 211 Σ
Egael
7
12
1
| (((.)) Ega.:1 + 1 - 2 Eg..!l
Blg.. [
7
n2a
(l - VS((N111
BI - .gg.dll + 2 gg..
722
21.2
Σ Pr(f., 1)8 2 + 1/111 Σ 1g..
112
1-1
20
21
211
1
Eg..l
144
2
22
144
LL +
48(0² + 48L22
|| f(x))))
62
2
196
2
20
611E²
Ra
144(o² + c²)²
31
21 Bg.d..
6
125
(D.46)
Therefore, replacing the result Ellg..11 from Eq. D.25 with the above updated result and replacing the
difference lemma with the updated difference lemma in Eq. D.27 with carefully tuned stepsize, we obtain:
min ((x)) s o (.
((x)
f
(xx)
neT
4/
+2(2 ( min a o²
min
When --> Jo, the above result recover the convergence rate provided in Koloskova et al. (2000)
D.3 EXTENSION TO DIFFERENTIALLY PRIVATE LOCAL SGD
section, add random noise ,,, (00 I where is the dimension the parameter on the clipped gradients. Therefore, the conditional expectation becomes:
f(8(11) & f(x:)
B(V (xx)) 8..))
Σ B(V((x)), 2..))
n
n
+ (1o L1 (x.))) 11)
Σ B (1o L1
7
2n
(Lo [=||V](x((I1)
rf + L.IlV/((x)))) E|
fxx)
B(V (xV)(x))....)
E1
gadl
2
2n
(XVf(x)) (..)(x)....)) g..) ( /
f(x))(
1/2 + 1.ll f
< fx())
b||
Σ 8.1l
2
2n
(D.47)
The second incquality the fact that B/z..] O. The third incquality the fact that Var(z,,.] oip. The of the proof the same hefore.
45

---

Published conference paper at ICLR 2024
D.4 ACCURACY PERSPECTIVE
this section, discuss how choose and reach s-aceuracy for Algorithm (minggn..y E.I III] S E). According Theorem obtain the following convergence result:
Fo
Pb nI
nlia² +
min E V te
TjT
n
+ min (a+ of + =x=))
+ n min
Since the last three terms do not depend on T, we have to pick and such that each individual term is less than It is clear from the last term that can pick to be:
(D.48)
Let A == miimmy//aaaaiii of - 6², -ut2) Together with the constraint S O(+)), we obtain the choice for yj as follows:
S min e
ns?
0
(
L(o + C2)
(D.49)
Finally, compute the required iteration T by plugging in the respective choices of and c and letting the first and the second terms be less than s².
D.5 PRIVACY-UTILITY DISCUSSION
D.5.1 LOCAL DP GUARANTEE
When the mini-hatch size is one on cach client, per-sample clipping with the DP-noise can limit the contribution of cach individual data point on the client model update, and achieve certain level of differential privacy. Here, the neighborhood dataset is defined such that two datasets only differ by one data point.
To proceed with the analysis, we assume the mini-batch size on each client is one and denote the minimum size among all clients by N, i.c., vi E [N], we have:
1 N: (x)(
f(x)
N min(N:),
(D.50)
N 1=1
(x), V
1
(FF Vi((i) <o?
(D.51)
N.
To achieve the formal local DP guarantee, the variance air should sutisfy the following condition. (Note the DP
noise is set to 2, NO00, 2 for all i [n].)
Theorem (Theorem Abadi al. (2016). For any sor S 0
REN
Algorithun / with updating rule y: +- ngg + 2.) with NO, 2 for all [n] for R. steps with R communication rounds, local steps, achieves (Eur, 60-local differential privacy for any client i E [r]] choose
Opr = Q ee/log(1/8)T
(D.52)
NenP
where opr
Zue v/d
Proof. Let q x- According the analysis from KoomAbadi et 2016), suppose yi, satisfies (e', for any 1 O..,, R - and any E [m]) then the total privacy guarantee after R rounds is (O(gvTRe'), O(8)). It follows from the Gaussian mechanism (and let EDP = gV/RR' 8 8') that, each ope should satisly
Agy (ogllo/
TDe 2
(D.53)
EUP
where is dy-eeniityvity of the algorithm output at cach iteration, which can be bounded by 2c since |/clip.(x) (y)) < 2c for any x,y e Rd. (Note for each elient, the minihatch size assumed 1.)
46

---

Published conference paper at ICLR 2024
D.5.2 OPTIMAL PRIVACY-UTILITY TRADE-OFF AND CHOICES FOR HYPER-PARE PARAMETERS
In this section, we provide the choices of syper-parameiers including v and achieve the optimal privacy utility trade-off and the optimal iteration complexity.
Let K. = o² + + and take the square for hoth sides in Eq. we have:
Fe
Fo 1T
nLK
L' min(r' min (1o () =iin((++
K2
L n²
n1 2
min [/()) O
62
obp
According Theorem Vi order to achieve (sne, 6)-local DP for each client. the noise scale should satisfy d11)(1
or 2 TV) where y
Plugging the bound for dpr into the previous display, and minimize
the first and the last terms w.t and 7, have 7 e
O where = VFon Let Aooe
/Fon
vir
= Fg we can then rewrite the above rate as:
min E[VVS( S (Act
(Ac
K2 BLK L'r? min(>" min (a +)
x2 + AP)
(D.54)
Case 1: When A² larger than such that O(Ac + A²) dominates error. we can set as large as A pick the stepsize as large as v7 = θ (+t to reduce the number of iterations T. We then obtain the privacy-utility trade-off as:
min f(x)|( s o Fol.
TV Pont. cVD
T=
(D.55)
Case 2: Suppose X is much larger than A such that min ((r + 2)?:
dominates the error. As O ((o + <)²)
is fixed, we can instead reduce the term O be reduced to:
x²
by letting = 0
K2/3
such that the rate from Eq. D.54 can
22
A3/5
min E V S
n.K
+ 1211² min(mmm K.
K/4
A2/3 - k.2 g2/3
n
We can then pick as large 17 e
LTKl//3 to reduce the number of iterations T so that: O ("Lx)
At/3
O (1/2g2/5) O A2/8) and O 7) S (A3/9C13)) s O(K2/3 We then obtain the urivacy-utility trade-off as:
Fola 2/9
min V s o 2218 (V
T= 0
(D.56)
coll/3
D.5.3 IMPLICATION
Case I: Let begin by examining Case characterized relatively low privacy budget, with and being relatively small. Plugging N-
(l/()15) into D.55 we obtain the optimal privacy-utility trade-off as well as the
best iteration complexity as follows:
dlog(1/5) nN
T sip
min B((V s
e
(D.57)
dlog(1/8)
choosing
/dlog(1/8) VnNNepe
θ (
(D.58)
Due to the weaker notion of neighboring dataset compared with per-update clipping, the optimal utility is N² times better than O dlog((1//)) obtained in Scction C.6.3 Further, the hest iteration complexity is achieved by letting 7 which the as per-update clipping. Again, under the current analysis, we cannot prove effectiveness for doing multiple local steps when the privacy budget and relatively small.
nefr

---

Published conference paper at ICLR 2024
Case Let now consider Case where we have large stochastic noise heterogeneity. Plugging the value dlog(1/5) we then have:
min B| V/(x)| s0 10' (0²+
(
2 dllog(1/8)
T +
NNVe
(0² (2) V/
by choosing:
c c= (0+
nN dlog(1/5)
1/0 )rr) 17 n= 6
dlog(1/6) N
F( ç2)a/a
In this the higher stochastic noise o² and data heterogeneity <² need pick slightly large clipping threshold and small stepsize seeing that @ @(10² (2yars) and
the optimal utility. We
(( Again, larger number of local steps r can increase the number of iterations T to reach such utility. The optimal clipping threshold and stepsize in this case complicated interplay between of, 5 problem dimension d, number of data point N, and the privacy cost (Eve, 6).
D.5.4 CONNECTION TO CENTRALIZED DP-SGD
Following same discussion as presented in C.6.4 per-sample clipping (Algorithm with DP noise) can treated as centralized algorithm when r from a pure algoritumic point view.
Again, let ç and mini-batch size each client be is clear that, Algorithm with DP noise exactly equivalent DP-SGD (where
interpreted as the mini-batch used Koloskova 2023)):
1 E clip, (VF((x)) +
X
(D.59)
Suppose the size the whole dataset is Noouz Then the target optimization problem becomes:
Nisa
f(x)
Fx(x.
Nectal
Essentially, the analysis in section D.5.2 can use the noise bound derived in C9.4
recovers this special case. To guarantee the global DP guarantee, we
dnc? 1og(1/8)T
or
(D.60)
N2 F
From the formula of añe. obtain is relatively small, then obtain the following optimal privacy-utility trade-off and required number of iterations:
de (18)
Nise Following the discussion Section D.5.3 suppose
[xx] so s (lo((11)) rE[L.R]
N N
min
T 0
(D.61)
N Nu
dlog(1/6))
by choosing
v (log(1//)
+
n n= 0
(D.62)
NiuaEee
Many researches Wang et al. (2018) Kifer al. (2012) have shown that the optimal utility bound DP-SGD
(olog()/5)
under bounded stochastic gradient assumption is O
We here obtain slightly worse (higher
Na
order) utility bound due to the of the practical bounded variance assumption, but still keeps the same ratio between the privacy cost (eve, 8). the problem dimension and the dataset size. The underlying reason is due to higher order term 5² y21 24
that appears when gradient norm (x,)] large.
48

---

Published conference paper at ICLR 2024
E CONNECTION BETWEEN ALGORITHM 1 AND ALGORITHM 2
Similarity in the special case: When T Sperapeee
the two algorithms are exactly the same given This because, by definition. Mgllip poorpter (yn V...))))))) Spaoart
"
Wol and sample
"
No min(1, 2u [2IVv
Thy min(1, [VF.CN:) VF:())) syclip ape
(VP(y.)). Theo-
rem Cand Ia be simplified and give the same convergence guarantee in this case, that
Theorem
Fi
Fy
min( V o 02 +3,e) min(a + C. =
NOT
Theorem
V
nL ( mLL min(a C.
m(fo* Ope spter
nit
Except for the fourth term that is caused by different distance Jemma, obtain the same convergence guarantee. Therefore, in this special case, can adjust Oper sumple to allow per-sample clipping converges any accuracy, which is essentially equivalent to the strategy of adjusting the inner stepsize in per-update elipping reach any accuracy.
Dissimilarity under arbitrary clipping threshold We here provide an example where per-sample only con- verges to the neighborhuod of the stationary point given arbitrary clipping threshold assuming 1.
p = 1/3
Let
p 1/3, here assume is random vector the gradient is stochastic:
2, p = 1/3
For per-update clipping, for any Cperupiaee we can always pick m S Eln,elip speune (m=) = O.
Sper update
such that
For per-sample clipping, suppose Gper
1. Then for any 1) > holds that (nclip Spor (1)
5 >>
Per-sample clipping recovers the result from Koloskova al. 2023) when r and ( 0
and f. f for any i [n]. Each client performs elipped stochastic gradient descent with minibatch size of 1. Then resulting algorithm equivalent to the centralized mini-batch SGD with mini-batch size Note this case, Theorem I can be simplified as;
Let consider the special case where
Pa
pl La min(a, min = where 1::= Lo cla.
Since 1) S 14-1. the last two terms hecome min(a, c) + min(a, e²)
By simply discussing the relation between
a and c, it holds that @(min(ar, c) min(a, "²)) O (mmin IT ). Therefore, the resulting rate covers the
clipped muiii-btchl SGD rate as presented in Koloskova et al. (2033)
COMPARISON AGAINST EXISTING WORKS
F. PER-SAMPLE CLIPPING
Our result covers the convergence rate of the centralized clipped mini-batch SGD (single worker, rI
from Koloskova et al. (2023) when we assume Ç ç= 0 and communicates every iteration (r = 1). except for the fourth term in Thhorrmm I which only mildly influences the convergence (Koloskova et al. (2220) Compared
CELGC (Liu et al. 2022). present the convergence rate given arbitrary clipping threshold with
heterogeneous workers (C 0). Compared to Yang et al. (2022). we provide more explicit influence of stochastic noise and data heterogeneity on the convergence rate.
F.2 PER-UPDATE CLIPPING
Zhang et al. (2022) studied the same ulgorithm under uniformly bounded gradient dissimilarity (sce Table
D.. Note that Corollary 3.2. from Zhang ct al. (2022) exactly recovers the standard FodAvg result under the assumption that e > MITG. However, assuming the norm of the update |m Σim V [x((x)] S m is always smaller than is strong and can hardly hold in practice. Yang et al, (2022) relaxed the assumptions by introducing
the bounded 3 moment Zhang et al. 2020cp. While [>V]] is allowed to follow heavy-tailed distribution.
this assumption implics [ for any Rd which excludes interesting functions. Morcover,
49

---

Published conference paper at ICLR 2024
the effect caused by stochastic noise heterogeneity are hidden the parameter. Comparably, we use lighter Assumptions D and our result light and interpretable.
G EXPERIMENTAL SETUP AND DETAILS
We illustrate the performance using multinomial Ingistic regression (Greene 2003 MNIST dataset (LeCun Cortes 2010). use ten workers full participation. We randomly subsample 1024 images into each worker use full-batch gradients (o 0). vary the number classes in each worker to simulate different levels data heterogeneity following Hsu et al. 2019). The heterogeneity highest when each worker only has images from a single class. We tune stepsize all the experiments to reach the desired target accuracy = ||V [xx)]] with fewest rounds. See Appendix for more complicated NN experiment on CIFARIO dataset.
models with PyTorch 1.7.1 and Python 3.7.9, prepare MNIST training dataset by simply randomly subsampling 1024 images per digit. For per-update elipping, experiment with using stepsize from (0.00625, 0.0125, 0.025, 0.05, 0.1, 0.2). For per-sample clipping, we experiment
We implement
using stepsize from [0.1, 0.2,0.4, 0.8). choose the stepsize such that we can reach a specified norm the gradient [Vxx with communication rounds, For implementing the clipped FedAvg, the main components are two functions where we apply per-sample and per-update clipping.
def
(local_model, model,
threstold):
*""Args:
loca Local_mocoll the local modol & Ny cl1 11iping_threshcll constant,
if Sdipping_threstie
>
grad_group = terch. (Ip. data detach () clone () vview for _ in Socal_modes naned daammd_pprramttee ()
if p.requires grad and p.grad is not None],
10
dim=0)
grad norm torch.norm(grad group)
coet min clippping_hhreshcle grad_norm. (t)
if coef 1:
for name, F in local_model mama_/mmeeo..mmopaarrettettt ():: if p. requirees__grar p.grad. data coef
15
17
slse:
18
coef 1.0
19
local model, coef
def per per__pe___lee c_r__uddtt___e popdate_clippnng (prev 8, current_li 1, clipping (hreshold)) ***Args:
(prev
prev_s: the server model from the previous round current_l: the current updated local model
clipping_threstolld: coastant,
diff =
for k in current_ keeys
diff(k] = current_ [k] data - data [k]]_s[k]. data
detach() c)loe()) .vieww((1)) for k in diff reshape = corch.cat (Idiff [ddiff(k]]] (k..fffch)dddchc diff.keys ()), dim-0)
11
diff norm torch.normice (diff reerh..o
12
coef min threshoo / [tff_norm.item/ee for in aurrent_l.keys(u
diff(k] coef
return diff, coef
H MNIST EXPERIMENT
We here show the accuracy evaluated the MNIST dataset (10,000 images) for per-sample and per-update clipping. Note, the test accuracy improved further with higger and/or deeper neural network.
50

---

Published conference paper at ICLR 2024
(a) Persample clipping
(b) Per-uddate clipping
0.85
c:1.50
1c:0100 62.12.
In:0.4
0.85
C:0.15 1c:001255 E:0.21, 1r:0220
lr:0.0125
1r:0.20
0.80
0.80
100
200 300
400
500
200
400
600
800
Communication rounds
Communication rounds
Figure H.1: Server test accuracy (local step the numher of class per client is 1) using (a) per-sample clipping and (b) per-update clipping.
I CIFARIO IO EXPERIMENT USING PER-UPDATE CLIPPING
We conduct an experiment considering stochastic noise, local steps, data heterogeneity, non-convex neural networks, different clipping threshold, and more complicated datasets. We use simple deep neural network with two convolution layers (32 and 64 channels) and two fully connected layers (hidden dimension 512) on CIFAR for classification. We split the CIFARIO training data into 10 clients following Dirichlet distribution Kairouz et al. (2019) with concentration parameter 0.1 (0.1 usually means that the client heterogeneity is high). We use 10 local steps, batch size of 1024, tune the stepsize from (0.05, 0.1. 0.2). We here mainly performed per-update clipping experiment as would like to highlight the non-clipping- bias behaviour. We clearly show that when the clipping threshold is small, we can still converge to similar level as without clipping but the cost of more communication rounds.
Loss
Accuracy
c 0.10
2.2
0.50
2.0
c 1.00
0.6
1.8
2.00
0.5
C
1.6
0.4
= 0.10
1.4
0.3
0.50
1.2
= 1.00
0.2
1.0
2.00
0.1
+ + 00
0.8
200
400
600
800
1000
0
200
400
600
800
1000
Communication rounds
Communication rounds
Figure I.1: Test classification loss and accuracy on the CIFARIO dataset with per-update clipping. When the clipping threshold is small, e.g.. c=0.1, can still obtain similar performance vanilla FedAvg (e - oc) the cost of more communication rounds. We can improve the classification accuracy by c.g., using more advanced deep neural networks.


Reviews:
[{"review_id": "sTvLXtdkow", "reviewer": "Reviewer_6LCG", "summary": "This paper studies two different clipping methods, per-sample clipping and per-update clipping, in distributed DP-SGD. Per-sample clipping captures a case where the user clips the update in each local iteration; per-update clipping is more similar to a local SGD scenario where users do local updates for multiple rounds before clipping the update and communicate with the central server. This paper demonstrates that when the clipping threshold is large enough or learning rate small enough, for second-moment bounded gradient, the bias due to clipping can go to zero.", "questions": "1. What is the optimal utility-privacy tradeoff/ utility bound under the optimal parameter selection of Algorithm 1 and 2 (in particular, Algorithm 1 with both inner and outer leaning rate)? In particular, what is the tradeoff considering the bias caused. \n\n2. Which clipping method we should use in practice?\n\n3. Can the different clipping methods produce better performance compared to existing works?", "limitations": "", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper generalizes the convergence analysis in SCAFFOLD to study the clipped DP-SGD. The proof seems solid and the claims on the clipping bias make sense to me.", "weaknesses": "1. My main concern is that the authors do not make the implication of the theoretical results presented clear. I am puzzled by the motivation of studying Algorithm 1 with a fixed learning rate. It seems that Algorithm 1 can also apply both an inner and an outer learning rate and they should produce the similar bias control as what is claimed in Algorithm 2. So, this make the comparison between Algorithm 1 and 2 in Section 3.3 very confusing, given that after incorporated with the inner learning rate, both of them can achieve arbitrary accuracy. So, what do the analysis want to tell? Which clipping method should we apply in practice? Overall, this makes the practical impact of the theoretical results weak. \n\n2. The privacy-utility tradeoff is not well studied in this paper. In Appendix D.4, the authors briefly discuss the iteration number T required to achieve the balanced point between convergence progress and utility loss resulting from noise. I would suggest plugging the expression of v with $\\epsilon$ and $\\delta$ into the bound, and compare with existing works, such as \"Differentially private empirical risk minimization revisited: Faster and more general\". It is not clear to me whether the proposed analysis brings any improvement either in terms of the optimal utility-privacy tradeoff or the efficiency, i.e., the convergence time. The clipping bias needs to be carefully controlled such that the three terms: convergence advancement, utility loss by noise, and the bias should be all in the same degree. From the complicated expression, I find it hard to figure out in practice, do we want a large bias but slow convergence with large DP noise or the converse way.  \n\n3. For an ICLR paper, I feel the experiments need to be strengthened. The experiments on both MNIST and CIFAR10 do not report the test accuracy but only the loss. Still, we do not know **under the corresponding  optimal parameter selection** of the two clipping methods, which one performs better in practice. There is no comparison presented with existing empirical works on DP-SGD, such as \"Unlocking High-Accuracy Differentially Private Image Classification through Scale\". \n\n4. The code is not released.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HGfKoroeq9", "reviewer": "Reviewer_6Kwh", "summary": "This paper studies the problem of clipping in federated learning. More specifically, the authors consider the per-sample and per-update clippings in FedAvg, and derive the corresponding convergence guarantees of FedAvg with these two clipping techniques. The authors also discuss how these two results can be utilized in the differentially private federated learning.", "questions": "The problem studied in this paper is very interesting and can be very useful in other related problems, such as differentially private federated learning. However, I have several questions about the current paper:\n1. It seems that when we choose $c$ as infinity, the results (e.g., Theorem I) cannot reduce to the unclipped results (e.g., LocalSGD  Koloskova et al. 2020), and I'm wondering what steps cause this discrepancy?\n2. I'm not sure how the results can be applied to the differentially private setting. The authors consider the stochastic setting, and thus the authors need to specify what is the dataset you want to protect when you apply Corollary I and Corollary II. From my understanding, it would be more meaningful if the authors can provide the finite sum results with bounded stochastic gradient assumption instead of the stochastic setting with bounded variance assumption for the application of differentially private setting.\n3. On page 5, comparison to the previous works, why you can claim that the established results can recover the rate of the centralized clipped mini-batch SGD?\n4. I'm wondering when you consider the finite sum with bounded stochastic gradient assumption, how the lower bound result will look like in terms of the clipping parameter $c$ and the bounded gradient norm?\n5. According to Corollary I and Corollary II, it seems to me that there is no need to use any local update. If this is the case, why don't you just use the private variant of the Minibatch SGD?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The strengths of the paper are as follows:\n1. The authors provide the convergence rate of FedAvg with two different clipping techniques.\n2. The authors show that how their results can be applied in the privacy protection setting.", "weaknesses": "The weaknesses of the current paper are as follows:\n1. It is unclear how the results are appropriate for privacy setting.\n2. The results cannot recover the unclipped results when the clipping parameters goes to infinity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OlzNnyNP9V", "reviewer": "Reviewer_CsYx", "summary": "The paper theoretically analyzes the convergence of the FedAvg algorithm with per-sample or per-update gradient clipping on heterogeneous data. They prove the upper bound for the expectation of gradient norm during training for a general class of learning objectives that satisfies bounded gradient variance, bounded gradient dissimilarity, and distributed $(L_0, L_1)$-smoothness. The main theoretical insights are as follows.\n- Under per-sample clipping, the expected gradient norm converges to a neighborhood with a size that depends on the gradient dissimilarity, the stochastic variance in gradient, and the clipping threshold (even when we set the step-size to be infinitesimal).\n- By contrast, under per-update clipping, the expected gradient norm can converge to an arbitrarily small level when the clipping threshold is reasonably large and the step-size is small, at the cost of more communication rounds.\n\nThe authors also perform logistic regression on MNIST to numerically support their insights on the effect of data heterogeneity on convergence under clipping.", "questions": "- Could the author explain why this local update step-size $\\eta_l$ would contribute to significantly different convergence behaviors between per-sample and per-update clipping? See weakness 1 for details.\n- Could the authors comment on this discrepancy between recommended large clipping threshold in this paper and the small clipping threshold used for practical DP learning?\n\n\nOther minor comments:\n- Is there a reason why, in the experiments of Figures 1 and 2, the clipping threshold for per-sample clipping is chosen to be much larger than the clipping threshold for per-update clipping?\n- In Table 1, $L$ is not defined. In Theorem 1, $M$ is not defined. In Corollary 1, $g_{i, t}$ cannot be found in Algorithm 1.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The analysis in this paper holds for arbitrary choice of clipping threshold, while prior works generally either assume a large enough clipping threshold or assume homogeneous data.\n- The authors drew interesting comparisons between two clipping methods, per-sample clipping, and per-update clipping, highlighting that the quality of converged solution under per-sample clipping is highly limited by data heterogeneity. In contrast, per-update clipping enjoys convergence to arbitrary accuracy under data heterogeneity.", "weaknesses": "1. The authors proved drastically different convergence results under per-sample clipping and per-update clipping, even though the two clipping methods are equivalent when $\\tau = 1$ (despite a local step-size $\\eta_l$). This seems counterintuitive and needs more clarification. \n2. Although the analysis holds for arbitrary clipping threshold, satisfying convergence to an accurate solution still relies on setting a large enough clipping threshold. This insight makes sense theoretically (as a larger clipping threshold enables the training process to be closer to unclipped training), yet it is quite different from practice. (For DP learning, generally, a small clipping threshold such as 0.1 enables good performance [a, b].) \n3. Another less critical weakness is that the main theorems (Theorem 1 and Theorem 2) seem to be direct extensions of the prior work [Koloskova 2023]. Consequently, it needs to be clarified how non-trivial are the additional efforts made in this work.\n\nReferences:\n- [a] Tramer, Florian, and Dan Boneh. \"Differentially Private Learning Needs Better Features (or Much More Data).\" In International Conference on Learning Representations. 2020.\n- [b] De, Soham, Leonard Berrada, Jamie Hayes, Samuel L. Smith, and Borja Balle. \"Unlocking high-accuracy differentially private image classification through scale.\" arXiv preprint arXiv:2204.13650 (2022).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7PnADseym2", "reviewer": "Reviewer_VZxT", "summary": "In summary, this work focuses on analyzing the effect of per-sample clipping and per-update clipping in private federated learning theoretically, and improves the theoretical results from previous works. Specifically, the major improvement lies in two aspects: 1. Fewer assumptions than previous works. Previous works like Zhang et al. (2022) and Yang et al. (2022) rely on extra assumptions like the uniformly bounded stochastic gradient or bounded $\\beta$-moment of the stochastic gradient; 2. Convergence rate under the arbitrary clipping threshold, while previous works only provide rate under specific choices of the clipping threshold.", "questions": "So far I have no other questions", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "As far as I can see, when compared to existing works, the theoretical bounds in this work are certainly more appealing from three aspects.\n\n1. Relying on minimal assumptions for federated learning.\n\n2. Convergence guarantee under arbitrarily clipping threshold. In my view, this is the most important improvement compared to existing work, because, in practice, the clipping threshold is usually a hyperparameter. A continuous bound on the clipping threshold is certainly more helpful for understanding the effect of this hyperparameter.\n\n3. A more interpretable bounds that uncover the relationship among convergence, data heterogeneity, and clipping threshold.", "weaknesses": "So far I didn't see a major weakness in this work, and the theoretical results appear to be correct, although I didn't carefully check the math details. \n\nWhile I acknowledge that this is certainly a solid work, I would not consider the contribution significant. Because, firstly, the contribution is mainly on the theoretical exploration, and does not lead to practical guidance for hyperparameter tuning. On the other, there has been some theoretical exploration on this topic, and it seems that many proof techniques of this work come from Koloskova et al. (2023). Therefore, I give a \"fair\" score for the contribution and only recommend it for borderline acceptance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MKyBzvCGAy", "reviewer": "Reviewer_EwA6", "summary": "The paper provides a tight convergence analysis of federated averaging with clipping under two scenarios: per-sample clipping, where sample gradients are clipped during local optimization, and per-update clipping, where sample gradients are not clipped but the entire user update for each round is clipped. It demonstrates that per-sample clipping converges to a neighborhood of a stationary point, while per-update can converge to any accuracy if the inner step size is small enough. An extended analysis that includes added noise for differential privacy is provided.", "questions": "What is the meaning of the dotted line in Figs 1/2c?\n\nIt is unusual as far as I know to obtain a DP guarantee with per-sample clipping. Does that come from bounding the sensitivity by taking the worst case ||y_i|| given the fixed number of local steps \\tau? That seems like it would be really weak. So I'm surprised that \"per-update is no better than per-sample in terms of the optimal privacy/utility trade-off\". Can you provide any intuition there?\n\nCould there be any utility in doing *both* per-sample and per-update clipping? How hard would it be to extend the analysis to that case, and if you can, what does it say?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The writing is very clear and the analysis is insightful. Clipping in FL is an important problem to study, as some means of bounding sensitivity is needed to achieve differential privacy.", "weaknesses": "The experiments would be stronger if continued for more communication rounds.\n\nMinor things:\nThe \"assumptions\" column of Table 1 needs formatting (sometimes assumptions are referred to as An, sometimes just as n)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)