SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compression
Authors: Zhize Li
Haoyu Zhao
Boyue Li
Yuejie Chi
Venue: NeurIPS 2022 Accept (2022)
Keywords: differential privacy
communication compression
nonconvex optimization
federated learning

Abstract: To enable large-scale machine learning in bandwidth-hungry environments such as wireless networks, significant progress has been made recently in designing communication-efficient federated learning algorithms with the aid of communication compression. On the other end, privacy preserving, especially at the client level, is another important desideratum that has not been addressed simultaneously in the presence of advanced communication compression techniques yet. In this paper, we propose a unified framework that enhances the communication efficiency of private federated learning with communication compression. Exploiting both general compression operators and local differential privacy, we first examine a simple algorithm that applies compression directly to differentially-private stochastic gradient descent, and identify its limitations. We then propose a unified framework SoteriaFL for private federated learning, which accommodates a general family of local gradient estimators including popular stochastic variance-reduced gradient methods and the state-of-the-art shifted compression scheme. We provide a comprehensive characterization of its performance trade-offs in terms of privacy, utility, and communication complexity, where SoteriaFL is shown to achieve better communication complexity without sacrificing privacy nor utility than other private federated learning algorithms without communication compression.

SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compression
Zhize Li Carnegie Mellon University
Haoyu Zhao Princeton University haoyu@princeton.co
Boyue Li
Carnegie Mellon University
chizelGandren cmu. edu
boyuel Gandrew cmu, edu
Yuejie Chi Carnegie Mellon University yuejiecGandrew. cmu, edu
Abstract
To enable large-scale machine learning in bandwidth-hungry environments such as wireless networks, significant progress has been made recently in designing communication-efficeen federated learning algorithms with the aid of communi- cation compression. On the other end, privacy-preserving level, is another important desideratum that has not been addressed simultaneously in the presence of advanced communication compression techniques yet. In this paper, propose unified framework that enhances the communication efficiency private federated learning with communication compression. Exploiting both general compression operators and local differential privacy, we first examine sim- ple algorithm that applies compression directly to differentially tireeenntially-pivaatee stochastic gradient descent, and identify its limitations. We then propose unified framework SoteriaFL for private federated learning, which accommodates general family of local gradient estimators including popular stochastic variance-reduced gradi- ent methods and the state-of-the-art shifted compression scheme. We provide a comprehensive characterization of its performance trade-offs in terms of privacy, utility, and communication complexity, where SoteriaFL is shown to achieve better communication complexity without sacrificing privacy nor utility than other private federated learning algorithms without communication compression.
especially at the client
Introduction
With the proliferation of mobile and edge devices, federated learning (FL) 42 55
has recently emerged a disruptive paradigm for training large-scale machine learning models vast amount of geographically distributed and heterogeneous devices. For instance, Google uses FL in the Gboard FL is often modeled distributed optimization 2
mobile keyboard for next word predictions aiming to solve
problem 55 35 72
where f(x; D.) = 1 m
[(x; min meRd
f(x; [(a;
(1): D.)
Σ I (a;; di.g)-
m. j=1
Here, D denotes the entire dataset distributed across all n clients, where each client has a local dataset D, {dl,j , 1 of equal size ml' x E Rd denotes the model parameters, f(æ; D), f fæ; D.). and fx; di,)) denote the nonconvex loss function of the current model æ the entire dataset D, the local dataset D,, and a single data sample di.j. respectively. For simplicity, we use f(x), f((x) and faz((z)) to denote fx: D). f=; D.) and f(; d. respectively.
TTii is without loss of generality, since otherwise
simply adjust the weights of the loss function.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

1.1 Motivation:
trade-offs
To unleash the full potential of FL, it is extremely important that the algorithm designed to solve needs to meet several competing desiderata.
Communication efficiency. Communication between the server and clients is well recognized as the main bottleneck for optimizing the latency of FL systems, especially when the clients-suce as mobile devices-hare limited bandwidth, the number of clients is large, and/or the machine learning model has lot of parameters- for example, the language model GPT-3 has billions of parameters and therefore cumbersome to share directly.
Therefore, it is very important to design FL algorithms to reduce the overall communication cost, which takes into account both the number of communication rounds and the cost per communication round for reaching desired accuracy. With these two quantities in mind, there are two principal approaches for communication cefftuiccationefffiiiettt FL: 1) local methods, where in each communication round, clients multiple local update steps before communicating with the server, in the hope of reducing 38,
the number of communication rounds, e.g.. [55] 48 39
27
71
60, 9 47
78 58,
57]; 2)
compression methods, where clients send compressed communication message to the server, in the 56
hope of reducing the cost per communication round, e.g..
4 40
B1
BV
61
52
28
51
62 21
45
While both categories have garnered significant attention in recent years, we focus on the second approach based on communication compression to enhance communication efficiency.
Privacy preserving. While FL holds great promise of harnessing the inferential power of private data stored on a large number of distributed clients, these local data at clients often contain sensitive or proprietary information without consent to share. Although FL may appear to protect the data privacy via storing data locally and only sharing the model updates (c.g., gradient information), the training process nonetheless reveal sensitive information demonstrated by. e.g., Zhu et al. [81] is thus desirable for FL to preserve privacy in a guaranteed manner 224
To ensure the training process does not accidentally leak private information, advanced privacy- preserving tools such as differential privacy (DP) 200 have been widely integrated into training algorithms [18 12
19 I
69
52
15
23 A notable example is Abadi et al.
[1.. which developed
a differentially-priiee privatt stochastic gradient descent (SGD) algorithm DP-SGD in the centralized (sidgle-node) setting. More recently, several infferentiallypprvvaa algorithms
[
[
35 54 are
proposed for the more general distributed (n-node) setting suitable for FL. In this paper, we also follow the DP approach to preserve privacy. In particular, we adopt local differential privacy (LDP) to respect the privacy of each client, which is critical in FL.
Goal. Encouraged by recent advances in communication compression techniques, and the widespread success of serrenttilll-privvatt methods, a natural question is
Can we develop a unified framework for private federated learning with communication compression, and understand the trade-off' between privacy, utility, and communication?
Note that there have been a handful of works that simultaneously address compression and privacy in FL. Unfortunately, they only provide partial answers to the above question. Most of the existing works only consider specific, elementary, tailored compression schemes that are applied directly to the gradient messages in DP-SGD R
/
82
76 17. A number of works [66] [3 [4]
36 2p [77
extended and considered different compression schemes, but did not provide concrete trade-offs in terms of privacy, utility and communication. Furthermore, existing theoretical analyses can be limited only to convex problems (26). lacking in some aspects such utility [2) or delivering pessimistic guarantees on utility and/or communication due to strong assumptions 76. I7]. Finally, existing work only studied the DP framework for direct compression, while it is known that the recently developed shifted compression scheme [56, 30 50) achieves much better convergence guarantees. Due to noise injection for setwwcc-ppreeevvnng it is priori unclear if the shifted compression scheme is also compatible with privacy.
1.2 Our contributions
In this paper, we answer the above question by providing general approach that enhances the communication efficiency private federated learning in the nonconver setting, through a unified framework called SoteriaFL (see Algorithm 2b. Specifically, we have the following contributions.

---

Table 1: Comparisons among (local) settrentiilly-priialt algorithms for the nonconvex problem in both central (single-node) and distributed (n-node) settings. Here, m denotes the number of data stored on single client, n is the number of clients, d is the dimension, and wi is the parameter for the compression operator (ef. Definition D. The communication complexity is computed by ndT (1++), where T'ss is the total number of communication rounds, and nd/(1 + w) is the communication cost per round. The utility/ accuracy measures the average squared gradient norm of the objective function complexity are small under the same privacy guarantee.
after T rounds. Note that the algorithm is better when the utility/accuracy and the communication
Algorithu
Privacy
Utiltt/Accerrayy
Communication Complexity
Remark
RRPSGD RR
(e.6)-DP
y Ing( 1ogg2/31411
single node
DP-GD/SGD
6e,6)
(oggt/00
single node
DP-SRM 0
(e.6)-DP
single mode
Distributed
(
6c.6))PP
2 muva Vlog(1/8)
modes,
DP-SRM [i
comp.
SVRG
(c, 6)-LP
3/ ma v Viogi1755
nndes,
LDP SPIDER
no comp. nodes, direct comp. nodes,
Q-DPSGD-1
IN
(e. 5)-LDP
(a2 /n+1//mm
2//,//3
(1+n ((ma
d.og(a/8)
SDM.DSGD
K6
(c, 5)-LPP
y /1/og(1/8) Vime
m
(ng (1+22)
mm22,2 2,2
direct comp.
CDP-SGD
LDP
(14w)) dd (18))
3/2 mev?
2,2
nodes.
(Theorem
(10g(1/8))
(1
direct comp.
SoteriaFL-SGR
SoterisFL-GD
(9
(c, LDD
( (oR(1
(1+
3/2mev
(1 vF)
nodes,
(Corollary
Vome
Vlox(1/2)
shifled comp.
SoteriaFL-SVRG
SoteriaFL-SAGA (0)
(c. 5)-LDP
mava 277 (1ox(11))
(1
modes, shifted comp.
(Corollary 2
Vame
Wang et al. considered the "global" (c, 6)D (which only protects privacy for entire dataset i.e. the local dataset D; on node i may leak to other nodes j # i) without communication compression. However, we consider the "local" (e, 5)-LDP which can protect the local datasets D, at the client level.
Ding et al. adopted a slightly different compression assumption E]][C(x)
a: a=|]3] S 6", with o² playing similar role (1 + w) in ours. However, it obtains a worse accuracy (G /n=/nt1/mm/ (dd
m7272275
V(62// ho)///)d ( ((==/n+/mmmm²²) 1/66 ((64/041/m)ddo) me
T/// a factor of T worse than
me
dlog(1/8)
/n+1/mmm² the optimal choice to achieve the utility of the other algorithms including ours, where (a the best accuracy for Q-DPSGD-1.
dog(118]
(3) Zhang et al. (76) only considered random-& sparsification, which is special case of our general compression operator. Morcover, it requires 1 ++ < log T, i.c., at least &o >> log out of d coordinates need to be
d
communicated, and its utility hides logarithmic factors larger than 1 The communication complexity n 7/2 is due to their convergence condition T' > nt".
(4) Here, 7 = -i72 If n 2 (1 w1) (which is typical in FL), then J < 1, and we can drop the terms involving 7 from Fot
3/22
3/2
1. We first present simple algorithm CDP-SGD (Algorithm Db that directly combines com- munication compression and DP- We provide thcoretical analysis for CDP-SGD in Theorem I and show its limitations in communication efficiency.
2. We then propose general framework SoteriaFL for private FL. which accommodates general family of local gradient estimators including popular stochastic variance-reduced gradient methods and the state-of-the-an shifted compression scheme. We provide a unified characterization of its performance trade-offs in terms of privacy, utility (convergence accuracy), and communication complexity.
3. We apply our unified analysis for SoteriaFL and obtain theoretical guarantees for several new private FL algorithms, including SoteriaFL-GD, SoteriaFL-SGD. SoteriaFL-SVRG. and FoteriaFL-SAGA. All of these algorithms are shown to perform better than the plain CDP-SGD (Algorithm)
I and have lower communication complexity compared with other
3

---

private FL algorithms without compression. The numerical experiments also corroborate the theory and confirm the practical superiority of SoteriaFL.
We provide detailed comparisons between the proposed approach and prior arts in Table To the best of our knowledge, SoteriaFL is the first unified framework that simultancously enables local differential privacy and shifted compression, and allows flexible local computation protocols the client level.
2 Preliminaries
Let [ni] denote the set 21 ,,, and ||.|| denote the Euclidean norm a vector. Let (u, v) denote
the standard Euclidean inner product of two vectors and Let == min f(x) > -00 denote the optimal value of the objective function in ① In addition, we use the standard order notation (-))
hide absolute constants. We now introduce the definitions of the compression operator and local differential privacy, as well as some standard assumptions for the objective functions.
Compression operator. Let us introduce the notion of randomized compression operator, which used to compress the gradients to save communication. The following definition of unbiased compressors is standard and has been used in many distributeed/feddrraee learning algorithms 4 40
56 30
50
52 28 ST].
Definition (Compression operator). A randomized map C IRd - Rd is w-compression operator for all a E Rd,, il satisfies
E(C(a))] x. E [[(((=)) zz|1 S ww ||a/||
In particular, no compression (C(x)= = x) implies w O.
Note that the conditions random sparsification and random quantization 52 511
satisfied by many practically useful compression operators, e.g., A useful rule of thumb is that the communication cost is often reduced by factor of T- due compression
4 Next, we briefly
discuss example called random sparsification to provide more intuition.
Example (Random sparsification). Given æ E RRd, the random-k sparsification operator is defined by C(æ) 1 (Ex @)), where O denotes the Hadamard (element-wise) product and &a {0, 1)d 1ddn is a uniformly random binary vector with k nonzero entries (léx llo = k). This random-k sparsification operator C satisfies with w
E - 1, and the communication cost reduced by a factor 1+ since transmit As It (due
coordinates rather than coordinates of the message.
Local differential privacy. We not only want to train the machine learning model using fewer communication bits, but also want maintain each client's local privacy, which key component for FL applications. Following the framework of (local) differential privacy [5] I 80], say that two datasets D and D' are neighbors they differ by only one entry. We have the following definition for local differential privacy (LDP).
Definition (Local differential privacy (LDP)). A randomized mechanism : - R with domain 'D and range R is (c, (c.8)-locally differentially private for client if for all neighboring datasets D,, D2 E D on client and for all events S E R in the oulput space of M, we have Pr(M(D.) E S) S Pr(M(D() E S) +
The definition of LDP (Definition 2 is very similar to the original definition of (e, dD 20 except that now in the FL setting, each client protects its own privacy by encoding and processing its sensitive data locally, and then transmitting the encoded information to the server without coordination and information sharing between the clients.
Assumptions about the functions. Recalling I we consider the nonconvex FL setting, where the functions { are arbitrary functions satisfying the following standard smoothness assumption [ and bounded gradient assumption (Assumption)
(Assumption
Assumption (Smoothness). There exists some L 2 O, such that for all E [m], E [m]] the function fag is L-smooth, i.e.,
[f)((()) - (az((12)l < | x2l1,
Var, 22 E RRd

---

Assumption 2 (Bounded gradient). There exists some G 2 0, such that for all i E [m], E [m]] and a E IRo, we have [, & G.
The smoothness assumption is very standard for the convergence analysis 59 25 and the
bounded gradient assumption is also standard for the differential privacy analysis 69 32 23
Warm-up: Plain Compressed
siitreenttally-Prvaaate SGD
There are two methods to combine privacy and compression: (1) first perturb and then compress, and (2) first compress and then perturb. The advantage of the first method that it is very simple and general, since compression will preserve the differential privacy and work seamlessly with any existing privacy mechanisms. However, the second method requires carefully designed perturbation mechanisms (otherwise the perturbation might diminish the communication saving of compression), e.g. binomial perturbation [3] or discrete Gaussian perturbation [36]. addition, observed that
the first method achieves better utility compared with the second one in some settings [17] Thus, we
also apply the first method this paper: first perturb then compress.
Baseline algorithm: CDP-SGD. As a warm-up, we first introduce a simple algorithm CDP-SGD
(described Algorithm M which subsumes some existing algorithms as special cases (e.g.. 76
for private FL with better theoretical guarantees. The procedure for CDP-SGD is very simple: at round f, each client i first computes a local stochastic gradient gf using its local dataset D; (Line in Algorithm D] Then, it uses Gaussian mechanism [1] to achieve LDP (Line 5 in Algorithm and communicates the compressed perturbed private gradient information the server (Line 0 Algorithm D. Finally, the server aggregates the compressed information and update the model parameters (Line 9 in Algorithm
Algorithm Compressed Differentially--riiall Stochastic Gradient Descent (CDP-SGD)
Input: initial point 2², stepsize 7/1, variance oz minibatch size b
1: for = 0, 1, 2........ do
2:
for each node i [n] do in parallel
3:
Sample a random minibatch I. from local dataset Dj Compute local stochastic gradient 인 = EEED Viil(a'
4:
all nodes use SGD method
5:
Privacy: of = प + c where g N((,0
6: Compression: let o! = (g()) and send to the server
I/ direct compression
7: end each node
8: Server aggregates compressed information v' = E 1a
9: x= = x² n
end for
Now we present the theoretical guarantees for CDP-SGD in the following theorem.
Theorem (Privacy, utility and communication for CDP-SGD). Suppose that Assumptions 7 and
2 hold, and the compression operators C₁ (cf. Line 6 of Algorithm 7 are drawn independently satisfying Definition ! By choosing the algorithm parameters properly and letting the total number of
communication rounds T O (V(L+a)dlog(1/))
VnIme
?n²
CDP-SGD (Algorithm I satisfies
dlog(1188)
G (/(tt))ddoog(//
(e, 6)-DPP and the utility T Ei= (2)
Vnme
The proposed CDP-SGD (Algorithm) is simple but effective. When the compression parameter a constant (i.e., constant compression ratio), CDP-SGD achieves the same utility O( /dlog(1/8) as SP-SGD in the single-node case with n In comparison, our utility is better than by factor of 1/6 and our communication complexity is much better than 76
me
(see Table Db.
However, the communication complexity of CDP-SGD still has room for improvements due to direct compression (Line 5 in Algorithm []. In particular, if the size of the local dataset stored on clients dominating, then CDP-SGD (even we compute local full gradients as CDP-GD) requires Omm²) communication rounds (see Theorem I.. while previous distributed tifferentially-priveee
5

---

algorithms without communication compression (e.g.. Distributed DP-SRM 73 LDP SVRG and LDP SPIDER [54] only need (m) communication rounds (see Table D
4 SoteriaFL: A Unified Private FL Framework with Shifted Compression
Due to the limitations of plain CDP-SGD, we now present an advanced and unified private FL framework called SoteriaFLi in this section, which allows large family of local gradient estimators (Line in Algorithm 2 and Line i Algorithm B Via adopting the advanced shifted compression
(Line in Algorithm 2. SoteriaFL reduces the total number of communication rounds ((m²) of CDP-SGD to Om), which matches previous uncompressed DP algorithms (see Table and further reduces the total communication complexity due to less communication cost per round.
4.1 A unified SoteriaFL framework
Our SoteriaFL framework is described in Algorithm 2 At round t, each client will compute local (stochastic) gradient estimator gf using its local dataset D, (Line in Algorithm One can choose several optimization methods for computing this local gradient estimator such as standard gradient descent (GD), stochastic GD (SGD), stochastic variance reduced gradient (SVRG) 64 and SAGA [16] (see e.g., Line 3 11 in Algorithm 3p. Then, each client adds Gaussian perturbation
c on its gradient estimate g to ensure LDP (Line Algorithm P). However, different from CDP-SGD (Algorithm]) D where we directly compress the perturbed stochastic gradients, now each client maintains a reference sf and compresses the shifted message ğ 8f (Line 5 in Algorithm 2 This extra shift operation achieves much better convergence behavior (fewer communication rounds) than CDP-SGD, and thus allowing much lower communication complexity.
Algorithm 2 SoteriaFL (a unified framework for compressed private FL)
Input: initial point x", stepsize Th, shift stepsize "t, variance of initial reference sf
7' I: for t = 0, 1, ,, do
2: for each node [n] do parallel
3:
Compute local gradient estimator of // allows many methods, e.g., SGD, SVRG, and SAGA Privacy: of = o + c where & NM(0, IT
4:
5:
Compression: let nf = Cg sg) and send the server
I/ shifted compression
6:
Update shift 8 ++1 = of + NCC )
7: end each node
8: Server aggregates compressed information v'
+ + + of
9:
r+1 = x² T
10: s ++1 st 24 Ei
11: end for
4.2 Generic assumption and unified theory
We provide generic Assumption g which is very flexible capture the behavior of several existing (and potentially new) gradient estimators, while simultancously maintaining the tractability to enable a unified and sharp theoretical analysis.
Assumption (Generic assumption of local gradient estimator for SoteriaFL). The gradient es- timator g (Line 3 of Algorithm Z) is unbiased |g = (z( [('))]forrr for E [n]] where E, takes the expectation conditioned on all history before round Moreover, can be decomposed into two terms g := A + Bi and there exist constants GA. GB. C1, C2, Cg, Ca, O and a random sequence {A²} such that
A
Σ
B
Wig
(3a)
m j=1
JEI,
E,
g
< CA + C22
(3b)
1=1
E,
A ++1
< (1-0044
+ C.E, x
(3c)

---

where Pig and Vi j are bounded by GA and GB respectively, and Is usualty denotes random minibatch with size b. Here, vl. and vi, should be viewed as functions related to the j-th sample ds stored on client
A few comments are in order. Concretely, the decomposition Bay is used for our unified privacy analysis (i.e., Theorem 2 We can let one of them be if the gradient estimator only contains one term is not decomposable. The parameters C1 and C2 in 3by capture the variance of the gradient estimators, e.g.. C1 = C2 = O if the client computes local full gradient O Vi (a=",, and C1 * (note that A will shrink in (3c)) and C2 0 if the client uses variance- reduuce gradient estimators such as SVRG/SAGA, Finally, the parameters 0, C3 and C4 in (3c) capture the shrinking behavior of the variance (incurred by the gradient estimators), where different variance-reduced gradient methods usually have different shrinking behaviors. More concrete examples to follow in Lemma ! in Section 5
Unified theory for
com.uiiityyommmmmiatiiiioonoo trade-offs. Given our generic Assumption 3
we can obtain a unified analysis for SoteriaFL framework. The following Theorem privacy analysis and Theorem unifies the utility and communication complexity analysis.
2 unifies the
Theorem 2 (Privacy for SoteriaFL). Suppose that Assumption 3 holds. There exist constants e and d' for any e < cbPT) /m² and E (0, 1). SoteriaFL (Algorithm is (c,6)-LDP if we choose
of / Gogg/oo((//)) (1/()
m².2
Theorem (Utility and communication for SoteriaFL), Suppose that Assumptions Z and hold, and the compression operators C; (cf. Line of Algorithm 2 are drawn independently satisfying Definition 7
Set the stepsize as
1
VBn
The = n min
(1 + 2aC4 + 4,(1 + w) 20C3/18)L
V1+ 2aCa + 43(1 + w w)
where o 21 311--0012
38C,
vB > 0, the shift stepsize as % =
2(1+w)> and the privacy variance oz satisfies (e, (..D)- and the following
1+2
according to Theorem
Then, SoteriaFL (Algorithml
20h nTT
38
clG3//4 GB (d log(1 m²2
Σ T
C2
LI
f a LL + where D0 - number of communication rounds as
In E Vf((x)) =6112. By further choosing the total
3
me /2E/2(L +
C2m2
T T=max max
(5)
V 3/dd / C log(1/5) cd G log(1/))
SoteriaFL has the following utility (accuracy) guarantee:
T Σ B|V 50
/BdGG//4+ G log(1/8)
BC₂ + w)
(6)
11me / (1+
Theorem is unified theorem for our SoteriaFL framework, which covers large family of local stochastic gradient methods under the generic Assumption El many popular local gradient estimators (GD, SGD, SVRG, and SAGA) satisfy Assumption F and thus can be captured by our unified analysis.
In the next Section 5 we will show that
5 Some Algorithms within SoteriaFL Framework
In this section, we propose several new private FL algorithms (SoteriaFL-GD, SoteriaFL-SGD, SoteriaFL-SVRG and SoteriaFL-SAGAI captured by our SoteriaFL framework. We give a detailed Algorithm 3 which describes all these four SoteriaFL-type algorithms in a nutshell.
To analyze Algorithm 3 using our unified SoteriaFL framework, we begin by showing that these local gradient estimators (GD, SGD, SVRG, and SAGA) satisfy Assumption 3 in the following main lemma, detailing the corresponding parameter values (i.c., GA. GB, C1, C2 Ca. C4, and 0).
7

---

Algorithm 3 SoteriaFL-SGD. SoteriaFL-SVRG, and SoteriaFL-SAGA
Input: initial point x", stepsize NR, shift stepsize "/. variance op minibatch size initial reference
8. = 0. initial wD = x for SVRG or wh = x" for SAGA, probability p for for each node i [ra] do in parallel
..... I'' do
2:
3:
Option I: SGD
4:
Compute local SGD estimator / - 1 EjEI, fia((x)) // GD if choose b
5:
Option II: SVRG
6:
Compute local SVRG estimator g = 8 EEEE,, (V).,())) - + V.((w))
Update SVRG snapshot point w' ar'
with probability P
7:
w',
with probability 1 p
8:
Option III: SAGA Compute local SAGA estimator:
9:
g = Σ jez, (V)i((x')
(w) m ΣØ ((eg(())))
x for Io for j $ Is
10:
Update SAGA variables w
wh
11:
End Options
12:
Privacy: gi = g + c. where g NN(0, o1
13:
Compression: let of = (g (f) and send to the server
14:
Update shift 8 = of + ( =
end each node
16:
Server aggregates compressed information v' = s¹ + # Ei= of
17:
x +++ = x² nuu
s*+1 st + inn E of
19:
end for
Lemma (SGD/SVRG//AGA estimators satisfy Assumption Suppose that Assumptions and hold. The local SGD) estimator g! (Option Algorithm
satisfies Assumption with
(m G) = A A
G = G, Ci=
0, C2
mb
The local SVRG estimator g (Option in Algorithm
3) satisfies Assumption with
GA = 2G, GB = G, Ci = b C2 = 0, C3 = 2(1 - p)n?
L
C4 =
A =
||
w0² 112
2
The local SAGA estimator z (Option III Algorithm
satisfies Assumption with
L
2(m 6)m²
G = 2G, GB = G, C
C2 =0, 0, C3
C4 =
b
0 b
x
2m
nm
With Lemma in hand,
plug their corresponding parameters into the unified Theo- rem 3 to obtain detailed utility and communication bounds for the resulting methods (SoteriaFL- SGD/SoteriaFL-GD. SoteriaFL-SVRG. and SoteriaFL-SAGA), Formally, we have the following three corollaries.
Suppose that Assumptions combine Theorem and Lemma 7 i.e., choosing stepsize 1i 17 (1+2 (1tw)) where
Corollary (SoteriaL--SaD/Sotriiarrs
7 and hold and we
we set 3 2(1w)) and =
8/2 8/2
1+22 and privacy variance shift stepsize = = 2(+=)3
n1/2
of 0 G (og(1)16)) If we further the minibatch size b min (I+ Log(1/88 m
mcG/B
and the total number of communication rounds T o( (1to)ddoog)))))
VnLue
(1 + vT)), then

---

Table 2: Gradient complexity for proposed SoteriaFL-style algorithms, which is computed the product the total number communication rounds I and the minibatch size Here, for notation simplicity, K
VnLme
and (1+w) n=/2
G GV
SoteriaFL-GD (Option Algorithm with = m)
SoteriaFL-SVRG SoteriaFL-SAGA
SoteriaFL-SGD
Algorithms
(Option I in Algorithm
(Option II, III in Algorithm
Gradient Complexity
K(1 + vm
( + /r)b
K(1 + r)m
SoteriaFL-SGD satisfies 83,D) and the following utility guarantee + E /
0
G (ogg//) (1 + VT)). If we choose minibatch size (local full gradient) in Vnme
SoteriaFL-SGD, the result of SoteriaFL-SGD leads to that of SoteriaFL-GG.
Corollary 2 (SoteriaFL-SVRG) Suppose that Assumptions 7 andd 2 holl and we combine Theorem
3
22/3/2/5 min(1. /wlll///////l/ [[(()=)))) where set B 1+2 2(1+w and
and Lemma 2//3///0 mln(1.n/(2+w0)) 12/36113 < 1/4 and p S 1/4, shift stepsize 7tt /
ie., choosing stepsize т)t
"
privacy variance o = - ( If we farther let the minibatch size b 2/3 the probubility
= bfm, and the total number of communication rounds =0 Ga (
VnLme max (1,T)),
(1+w)a//2 where = n- then SoteriaFL-SVRG satisfies (1,6)-L.P and the following utility guarantee
Ld Log((1)))) Ldd Vime
T
The utility and communication complexity for SoteriaFL-SAGA are the same as SoteriaFL-SVRG. and we defer its detailed corollary to the appendix.
Interestingly, SoteriaFL-style algorithms more communication--fficee than CDP-SGD when the local dataset size m is large, with a communication complexity of (mm) in contrast to ((m²) for CDP-SGD. In terms of utility. SoteriaFL-SVRG and SoteriaFL-SAGA
achieve the same
utility as CDP-SGD, while SoteriaFL-GD and SoteriaFL-SGD achieve a slightly worse guarantee
(1+
is small when the number of than that of CDP-SGD by a factor of vT, where = mi72 clients is large.
Gradient complexity of SoteriaFL-style algorithms. Although the utility and the communication complexity are the most important considerations in private FL., another worth-noting criterion is the gradient complexity, which is defined the total number of stochastic gradients computed by each client. Although SoteriaFL-GD, SoteriaFL-SGD, SoteriaFL-SVRG and SoteriaFL-SAGA have similar communication complexity (see Table D.. they actually have very different gradient in Table -isice the minibatch sizes and gradient update rules for these algorithms vary lot. The gradient complexity of BeaerraaLLSVV///ttriaaaaaLss usually smaller than SoteriaFL-SGU and all of them are smaller than SoteriaFL-GD. In sum, we recommend SideriaaL-SVrr/SStttraaLL--- while maintaining almost the same communication complexity as Scterafl-SSDDSSotrrrFL-oo
complexities-suumaatie
is
due to its superior utility and gradient complexity
Numerical Experiments
We conduct experiments on standard real-world datasets 10 to numerically verify privacy-utility communication trade-offss among different algorithms. The code be accessed at:
http:://gsthuu..cc///oppppzaaz2p h
Concretely, we compare the direct compression algorithm CDP-SGD (Algorithm 1h. shifted compres- sion algorithms SoteriaFL-SGD (Algorithm with Option I) and SoteriaFL-SVRG (Algorithm)

---

LDP
0.8
0
LDP-SVRG
LDP-SVRG:
CBP
0.6
SSD
SateriaFL
SoteriaFL.SVRG
0.6
Utiilt
Utility
0.4
0.4
0.2
0.2
Communicatio rounds
Communicatioo hits
-10*
Figure 1: Logistic regression with nonconvex regularization on the a9a dataset under (e, 8)-LDP with c 1 and 8 = 10-3
LDP-SGD
LDP-SGD
LDU-SVRG
LDP-SVRG
CDP-SGD
1.5
CDP-SGD
SoteriaFI--SOi
SoDD SoteriaFL-SVRC
SoteriaFL-SVRG
Tiileyy
0.5
0.5
100
150
1.5
2.5
zounds
Communicstion
-10"
Figure 2: Shallow neural network training on the MNIST dataset under (e, 0)-LDP with e = 1 and 6
10-3
with Option II), and algorithms without compression LDP-SGD || 544 and LDP-SVRG Y on two nonconvex problems (logistic regression with nonconvex regularization, and shallow neural network training). The detailed problem definition, experiment setup, and more experiments can be found in Appendix A
The experimental results show that compressed algorithms converges faster than the uncompressed algorithm in terms of communication bits (right columns), and also confirm that shifted compression based SoteriaFL can perform better than direct compression based CDP-SGD.
7 Conclusion
We propose SoteriaFL, a unified framework for private FI., which accommodates a general family of local gradient estimators including popular stochastic variance-reduced gradient methods and the state-of-the-aat shifted compression scheme. A unified characterization of its performance trade-offs in terms of privacy, utility (convergence accuracy), and communication complexity is presented, which is then instantiated to arrive at several new private FL algorithms. All of these algorithms are shown perform better than the plain CDP-SGD algorithm especially when the local dataset size is large, and have lower communication complexity compared with other private FL algorithms without compression.
Acknowledgments
The work of Z. Li, B. Li and Y. Chi is supported in part by ONR N00014-19-1-2404 by AFRL under PA8750-20-2-0504 and by NSF under CCF-19011 199, CCF-2007911, DMS-215 2134800 and CNS-2148212. The work of H. Zhao is supported in part by NSF, ONR, Simons Foundation, DARPA and SRC through awards to S. Arora. B. Li is also gratefully supported by Wei Shen and Xuehong Zhang Presidential Fellowship Carnegie Mellon University.
10

---

References
[1] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[2] D. A. E. Acar, Y. Zhao, R. M. Navarro, M. Mattina, P. N. Whatmough, and V. Saligrama. Federated learning based on dynamic regularization. arXiv preprint arXiv:2111.02663 2021.
[3] N. Agarwal, A. T. Suresh, F. X. X. Yu, S. Kumar, and B. McMahan. epSGD: Communication- efficient and setenntillll-privaaat distributed SGD. Advances in Neural Information Processing Systems, 31, 2018.
[4] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic. QSGD: Communication-efiicee SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems, pages 1709-1720, 2017.
[5] M. E. Andrés, N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi. Geo- indistinguishability: Differential privacy for secation-based systems. In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, pages 901-914, 2013.
[6] R. Bassily, A. Smith, and A. Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 464-473, IEEE, 2014.
[7] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, Shyam, G. Sastry, A. Askell, et al. Language models are few-shot learners. arXiv preprint arXiv:2005. 14165, 2020.
[8] M. Bun and T. Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryplography Conference, pages 635-658. Springer, 2016.
[9] S. Cen, H. Zhang, Y. Chi, W. Chen, and T.-Y. Liu. Convergence of distributed stochastic variance reduced methods without sampling extra data, IEEE Transactions on Signal Processing, 68: 3976-3989, 2020.
[10] C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3): 2011.
[11] K. Chatzikokolakiss M. E. Andrés, N. F. Bordenabe, and C. Palamidessi. Broadening the scope of differential privacy using metrics. In International Symposium on Privacy Enhancing Technologies Symposium, pages 82-102. Springer, 2013.
[12] K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. Differentially private empirical risk mini- mization. Journal of Machine Learning Research, 12(3), 2011.
[13] W.-N. Chen, P. Kairouz, and A. Ozgur. Breaking the communication- wwwaoonaaaavvvacvaaaeeee trilemma. Advances in Neural Information Processing Systems, 33:3312-3322 2020.
[14] W.-N. Chen, C. A. Choquette- -hhoo, and P. Kairouz. Communication efficient federated learning with secure aggregation and differential privacy. In NeurlPS 202/ Workshop Privacy in Machine Learning, 2021.
[15] A. Cheu, A. Smith, J. Ullman, D. Zeber, and M. Zhilyaev. Distributed differential privacy via shuffling. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 375-403. Springer, 2019.
[16] A. Defazio, F. Bach, and S. Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances neural information processing systems, 27, 2014.
[17] J. Ding, G. Liang, J. Bi, and M. Pan. Differentially private and communication efficient collaborative learning. In Proceedings of the AAAI Conference on Artificial Intelligence, Virtual Conference, 2021.
11

---

[18] C. Dwork. Differential privacy: A survey of results. In International conference on theory and applications of models of computation, pages 1-19. Springer, 2008.
[19] C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, (0:44)2111407, 2014.
[20] C. Dwork, F, McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265- 265. Springer, 2006.
[21] Fatkhullin, Sokolov, E. Gorbunov, Z. Li, and P. Richtárik. EF21 with bells & whistles: Practical algorithmic extensions of modern error feedback. arXiv preprint arXiv:2110.03294, 2021.
[22] V. Feldman and K. Talwar. Lossless compression of efficient private local randomizers. In International Conference on Machine Learning, pages 3208-3219, PMLR, 2021.
[23] V. Feldman, T. Koren, and K. Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 339,449, 2020.
[24] R. C. Geyer, T. Klein, and M. Nabi. Differentially private federated learning: A client level perspective. arXiv preprint drXiv:1712.07577, 2017.
[25] S. Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-23 2013.
[26] A. Girgis, D. Data, S. Diggavi, P. Kairouz, and A. T. Suresh. Shuffled model of differential privacy in federated learning. In International Conference on Artificial Intelligence and Statistics, pages 2521-2529. PMLR, 2021.
[27] E. Gorbunov, F. Hanzely, and P. Richtárik. Local SGD: Unified theory and new efficient methods. arXiv preprint arXiv:2011.0282 2020.
(28) E. Gorbunov, K. P. Burlachenko, 7. Li, and P. Richtárik. MARINA: Faster non-convex dis- tributed learning with compression. In International Conference on Machine Learning, pages 3788-378 3798. PMLR, 2021.
[29] A. Hard, K. Rao, R. Mathews, S. Ramaswamy, F. Beaufays, S. Augenstein. H. Eichner, C. Kid- don, and D. Ramage. Federated learning for mobile keyboard prediction. arXiv preprint arXiv:1811.03604 2018.
[30] S. Horváth, D. Kovalev, K. Mishchenko, S. Stich, and Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. arXiv preprint arXiv: /904005 15, 2019.
[31] N. Ivkin, D. Rothchild, E. Ullah, V. Braverman, I. Stoica, and R. Arora. Communication- efficient distributed SGD with sketching. Advances in Neural Information Processing Systems, 32, 2019.
[32] R. Iyengar, J. Near, D. Song, O. Thakkar, A. Thakurta, and L. Wang. Towards practical differentially private convex optimization. In 2019 IEFE Symposium Security and Privacy, pages 299-316. IEEE, 2019.
[33] B. Jayaraman, I.. Wang, D. Evans, and Q. Gu. Distributed learning without distress: Privacy- preserving empirical risk minimization. Advances in Neural Information Processing Systems, 31, 2018.
[34] R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26, 2013.
[35] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, et al. Advances and open problems federated learning. arXiv preprint 1rXin:1912.04997,, 2019.
12

---

[36] P. Kairouz, Z. Liu, and T. Steinke. The distributed discrete Gaussian mechanism for federated learning with secure aggregation. In International Conference on Machine Learning, pages 5201-5212. PMLR, 2021.
[37] S. P. Karimireddy, Q. Rebjock, S. Stich, and M. Jaggi. Error feedback fixes signSGD and other gradient compression schemes. In International Conference on Machine Learning, pages 3252-3261. PMLR, 2019.
[38] S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and A. T. Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pages 5132-5143. PMLR, 2020.
[39] A. Khaled, Mishchenko, and P. Richtárik. Tighter theory for local sgd on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pages 4519 4529. PMLR, 2020.
[40] S. Khirirat, H. R. Feyzmahdavian, and M. Johansson. Distributed learning with compressed gradients. arXiv preprint arXiv:180..0633 2018.
[41] Konečný, H. B. McMahan, D. Ramage, and P. Richtárik. Federated optimization: Distributed machine learning for on-device intelligence. arXiv preprint arXiv: 2016.
[42] J. Konečný, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint 411.04.61. 2016.
[43] D. Kovalev, S. Horváth, and P. Richtárik. Don't jump through hoops and remove those loops: Svrg and katyusha are better without the outer loop. In Algorithmic Learning Theory, pages 451-467. PMLR, 2020.
[44] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient- brasee learning applied document recognition. Proceedings of the IEEE, 86(11):2277 22:22223222, 1998.
[45] C.-S. Lee, N. Michelusi, and G. Scutari. bin quantization for distributed algorithms with linear convergence. arXiv preprint arXiv:2107.11304 2021.
[46] B. Li, S. Cen, Y. Chen, and Y. Chi. Communication-effiieeee distributed optimization in networks with gradient tracking and variance reduction. Journal of Machine Learning Research, 21:1-51, 2020.
[47] B. Li, Z. Li, and Y. Chi. DESTRESS: Computation-optina and ceatuniicatto-ffffiiettte decentralized nonconvex finite-uum optimization. SIAM Journal on Mathematics of Data Science, 1(3)10031- 2022.
[48] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2:429-450, 2020.
[49] Z. Li and J. Li. Simple and optimal stochastic gradient methods for nonsmooth nonconvex optimization. Journal of Machine Learning Research, 23(239): 2022.
[50] Z. Li and P. Richtárik. A unified analysis of stochastic gradient methods for nonconvex federated optimization. arXiv preprint X100:2000000001111, 2020.
[51] Z. Li and P. Richtárik. CANITA: Faster rates for distributed convex optimization with com- munication compression. In Advances in Neural Information Processing Systems, pages 13770-13781, 2021.
[52] Z. Li, D. Kovalev, X. Qian, and P. Richtárik. Accelcration for compressed gradient descent in distributed and federated optimization. In International Conference on Machine Learning. pages 5895-5904 PMLR, 2020.
[53] 7. Li, H. Bao, X. Zhang, and P. Richtárik. PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In International Conference on Machine Learning, pages 6286-6295 PMLR, 2021.
13

---

[54] A. Lowy, A. Ghafelebashi, and M. Razaviyayn. Private non-convex federated learning without a trusted server. arXiv preprint arXiv:2203.067:15 2022.
[55] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. Arcas. Communication-efficennt learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1 1273-1282. PMLR, 2017.
[56] K. Mishchenko, E. Gorbunov, M. Takáč, and P. Richtárik, Distributed learning with compressed gradient differences. arXiv preprint
2019.
[57] K. Mishchenko, G. Malinovsky, S. Stich, and P. Richtárik. ProxSkip: Yes! local gradient steps provably lead to communication accelcration! finally! arXiv preprint arXiv:2202.000 09357, 2022.
[58] A. Mitra, R. Jaafar, G. J. Pappas, and H. Hassani. Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. Advances in Neural Information Processing 3ystems,34:146000 34:14606-14611 14619, 2021.
[59] Y. Nesterov. Introductory Lectures Convex Optimization: A Basic Course. Kluwer, 2004.
[60] R. Pathak and M. J. Wainwright. Fedsplit: An algorithmic framework for fast federated optimization. Advances in Neural Information Processing Systems, 33:7057-7066, 2020.
[61] A. Reisizadeh, A. Mokhtari, H. Hassani, A. Jadbabaie, and R. Pedarsani. FedPAQ: A communication-efficii federated learning method with periodic averaging and quantization. In International Conference on Artificial Intelligence and Statistics, pages 2021-2031. PMLR, 2020.
[62] P. Richtárik, I. Sokolov, and I. Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster error feedback. Advances Neural Information Processing Systems, 34, 2021.
[63] P. Richtárik, I. Sokolov, E. Gasanov, I. Fatkhullin, Z. Li, and E. Gorbunov. 3PC: Three point compressors for communication-effiiee distributed training and a better theory for lazy aggregation. In International Conference Machine Learning, pages 18596-18648. PMLR, 2022.
[64] C. Sabater, A. Bellet, and J. Ramon. Distributed differentially private averaging with improved utility and robustness to malicious parties. arXiv preprint urXiv:2006.07216 2020.
[65] F. Shang. T. Xu, Y. Liu, H. Liu, L. Shen, and M. Gong. Differentially private ADMM algorithms for machine learning. IEEE Transactions on Information Forensics and Security, 2021.
[66] A. T. Suresh, F. X. Yu, S. Kumar, and H. B. McMahan. Distributed mean estimation with limited communication. In International Conference Machine Learning, pages PMLR, 2017.
[67] A. Triastcyn, M. Reisser, and C. Louizos. DP-REC: Private & communication-efficcenn federated learning. arXiv preprint arX05:2111.05454, 2021.
[68] T. Van Erven and P. Harremos. Rényi divergence and kullback-leibler divergence. IEEE Transactions on Information Theory. 60(7):3797-3800, 2014.
[69] D. Wang, M. Ye, and J. Xu. Differentially private empirical risk minimization revisited: Faster and more general. Advances in Neural Information Processing Systems. 30, 2017.
[70] H. Wang, S. Sievert. S. Liu, Z. Charles, Papailiopoulos, and S. Wright. ATOMO: Communication effiiceent learning via atomic sparsification. Advances in Neural Information Processing Systems, 31, 2018.
[71] J. Wang, Q. Liu, H. Liang, G. Joshi, and H. V. Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances neural information processing systems, 33:761 1-76111-66,,,,0 2020.
14

---

[72] J. Wang, Z. Charles, Z. Xu, G. Joshi, H. B. McMahan, M. Al-Shedivat, G. Andrew, S. Aves- timehr, K. Daly, D. Data, et al. A field guide federated optimization. arXiv preprint arXiv:1107.00917,200 2021.
[73] L. Wang, B. Jayaraman, D. Evans, and Q Gu. Efficient privacy-preserving stochastic nonconvex optimization. arXiv preprint arXiv:1910.13.. 2019.
[74] L. Wang, R. Jia, and D. Song. D2P-Fed: Differentially private federated learning with efficient communication. arXiv preprint crXiv:2006.13039 2020.
[75] Zhang, K. Zheng, W. Mou, and L. Wang. Efficient private ERM for smooth objectives. arXiv preprint arXiv: 1 799409947, 2017.
[76] X. Zhang, M. Fang, J. Liu, and Z. Zhu. Private and communication-efficcent edge learning: sparse differential Gaussian -aassinn-masking First International Symposium Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, pages 261-270, 2020.
masking distributed SGD approach. In Proceedings of the Twenty-
[77] H. Zhao, K. Burlachenko, Z. Li, and P. Richtárik. Faster rates for compressed federated learning with client- veeni-varinnce reduction. arXiv preprint arXiv:2112.13000 2021.
[78] H. Zhao, Z. Li, and P. Richtárik. FedPAGE: A fast local stochastic gradient method for communication-effiieenn federated learning. arXiv preprint arXiv:2108.04755 2021.
[79] H. Zhao, B. Li, Z. Li, P. Richtárik, and Y. Chi. BEER: Fast OL//T) rate for decentralized nonconvex optimization with communication compression. arXiv preprint arXiv:2201.13322 2022.
[80] Y. Zhao, J. Zhao, M. Yang, T. Wang, N. Wang. L. Lyu, D. Niyato, and K.-Y. Lam. Local differential privacy-based federated learning for internet of things. IEEE Internet of Things Journal, 8(1 8(11):836-8853, 2020.
[81] L. Zhu, Z. Liu, and S. Han. Deep leakage from gradients. Advances in Neural Information Processing Systems, 32, 2019.
[82] H. Zong, Q. Wang, X. Liu, Y. Li, and Y. Shao. Communication reducing quantization for federated learning with local differential privacy mechanism. In 202/ IEFF/CIC International Conference on Communications in China, pages 75-80. IEEE, 2021.
15

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All assumptions are stated in Section
(b) Did you include complete proofs of all theoretical results? [Yes] All detailed proofs for our theorems, lemmas and corollaries are provided in appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
16


Reviews:
[{"review_id": "ea59johwYsf", "reviewer": "Reviewer_qXn9", "summary": "The paper presents methods for differentially-private stochastic gradient descent, bounding the communication complexity for several gradient descent methods in their framework.  ", "questions": "See issue above on definitions.\n\nIt really seems for your analysis you don't care about what type of compression is being used (since you're adding noise, then compressing) and just need the compressor to satisfy (2)?  If so it feels like you could streamline things -- it wasn't clear to me where \"compression\" was important to the results, and my impression after going over it a few times is that it really isn't, you just happen to be compressing the end vector.  (To me it's a bit strange to refer to this as a unified treatment -- it seems that compression is just a black box to you.)\n\nSee issue above on \"practice\".  Could you do an experiment?  Or, can you better justify why the theoretical results should be of sufficient interest?  \n\n", "limitations": "n/a\n", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nAppears to improve on current state-of-the-art communication complexity results.\nMathematical analysis.\nAttempt to make the analysis as general as possible.  \n\nWeaknesses:  \n\nEssentially all theoretical for what is, at its heart, a problem for practice.  Some type of experiment showing its utility, comparing to other existing schemes, etc. seems called for.  \nAnalysis appears to use straightforward methods;  could be clearer about the novelty.  \n\nOriginality:  Original analysis.\nQuality:  Proofs seem correct, haven't checked them in detail.\nClarity:  Adequate, some issues, examples below.\nSignificance:  Hard to tell  without experiments of some form.  Is this just a theoretical result?  Should people doing FL in practice care?  \n\nIssues:  It's unclear in reading the main paper what the \"databases\" are and what it means for them to be \"neighbors\" in this context.  What exactly are the \"entries\" in the database, what does the \"mechanism\" correspond to here -- what exactly is it that is being kept \"private\".  (If I'm doing learning on a set of images, is an entry one of the images?  What is the mechanism acting on the image?  What are possible effects of changing out an image?)  \n\nI have strong hesitations on this type of \"theoretical\" result for DP on a practical problem without any sort of experiment to see if the end-to-end product is actually worthwhile.  Asymptotics can cover up a lot.  What is the actual effect/cost of adding DP into a system on any sort of real problem?  (I have no sense from reading the paper.)  ", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SuoC2aEzFCT", "reviewer": "Reviewer_XdPn", "summary": "This paper studies FL framework that both take into account compression to reduce the communication cost, and Local Differential-Privacy. The paper first introduces a baseline method CDP-SGD, which is basically DP-SGD combined with a compression of the model updates, and compute its utility for a number of communication rounds and a (epsilon, delta) DP bound.\n\nThe paper then introduced another class of framework (SoteriaFL). The main idea of SoteriaFL is to introduce a local shift s_i at each clients, that is track across the rounds. The gradient update $g_i$ of each client is shifted by $s_i$ before being compressed and sent to the central server. The server also keep track of a global shift, and add this global shift back to the sum of the model updates received during the aggregation part of the FL algorithm. SoteriaFL can be used with various local gradient estimators. The paper consider three such gradient estimators: SGD, SVRG and SAGA. For each of them,  the paper computes the utility and the communication complexity of SoteriaFL under (epsilon,delta)-Local Differential Privacy constraints.", "questions": "- Could you elaborate more on the assumptions 1 and 2, and explain in which FL cases you think there are satisfied?\n", "limitations": "I see to main limitations of this work:\n\n- There are no numerical experiment, even on mock data to support and illustrates the claim made by the authors. The theoretical results are $O( \\cdot. )$ meaning that all the constant have disappear. Therefore it would be nice to see these results in a numerical examples in order to better understand the order of magnitudes involved.\n\n- The authors do not put enough in context the necessity of such a framework. It would be better to have an example of a real-world FL use-case, in order to put order of magnitude in the different parameters (number of clients, dataset etc.) and show explicitly that SoteriaFL could improved real-world FL project.\n\nI don't think that these two limitations prevent from publication, as this work is a theoretical work and the focus of the paper is on convergence/compression rate.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Originality\nThe method presented in the paper seems new, and the authors made a specific effort to cite related work and explain how their work differ from existing work. In particular they point out that their CDP-SGD algorithm can subsume other previously published works when specific hyperparameter are chosen.\n\n\n# Quality\n\nThe submission seems technically sound, and the mathematical proof of the claims made are provided. I did not check all the proofs of the papers (and the appendices). But the quality of the writing and the clarity of the presentation indicate a meticulous work from the authors.\n\n\n# Clarity\nThe paper is extremely clear and well-written. I just have the following two remarks:\n\n- Algorithm 1, line 3: $I_b$ is not defined. It is defined later at line 204, but it would be important to define it here properly. In particular, it is important for the reader to understand that this step is only a gradient estimation, and there is no local model updates made as in FedAvg.\n\n- Algorithm2: Tjhe initialization of $s_i^{(t=0)}$ and $s^{(t=0)}$ is not specified. Could you specify it?\n\n\n\n# Significance\nComputing theoretical convergence rates and complexity bounds of newly designed FL framework is important in order to provide more theoretical foundations to the FL research fields. Therefore the line of research followed by this paper is worthy of publication. However it's significance is slightly reduced by the fact that:\n\n- The authors do not justify when/whether the assumptions 1 and 2 are true\n- There is not simulations, even on mock data, to illustrate and support there findings.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FVyqQ-FqegG", "reviewer": "Reviewer_YLXD", "summary": "The paper introduces a private and communication-efficient framework for federated learning. For communication efficiency, the authors use compression, and for privacy, the authors use local differential privacy. The authors first start with a simple algorithm that applies compression directly to DP-SGD, and expand it to the SoteriaFL framrwork, which supports a number of of local gradient estimators and the state-of-the-art shifted compression scheme. The authors back up their claims with theoretical and mathematical rigor. ", "questions": "The only question I have from authors, is that, are the current theoretical analyses enough to back the arguments? How about some field experiments with actual devices and real measurements? Will something like that increase the confidence of the claims of the paper?\n\n", "limitations": "It would be nice if the authors upfront and honest discuss the limitations of the paper. I believe it adds value and increases the trust from the readers \n\n(disclaimer: I should mention that I did not check the correctness of the theorems and proofs)", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is well-written and it's very easy to follow\n- The paper has a smooth transition from a simple algorithm that applies compression directly to DP-SGD, to a more advanced private and communication-efficient algorithm. I personally found this transition smooth and nice.\n- The paper is backed by a lot of theory and it is technically sound\n\nWeakness:\n- I am not a true expert in DP papers, while I read a lot of them, but I think this paper could benefit from some numerical analysis and experiments.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept