Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Losses
Authors: Andrew Lowy
Meisam Razaviyayn
Venue: ICLR 2023 poster (2023)
Keywords: differential privacy
federated learning
distributed optimization
private optimization
stochastic convex optimization
cross-silo federated learning

Abstract: This paper studies federated learning (FL)—especially cross-silo FL—with data from people who do not trust the server or other silos. In this setting, each silo (e.g. hospital) has data from different people (e.g. patients) and must maintain the privacy of each person’s data (e.g. medical record), even if the server or other silos act as adversarial eavesdroppers. This requirement motivates the study of Inter-Silo Record-Level Differential Privacy (ISRL-DP), which requires silo $i$’s communications to satisfy record/item-level differential privacy (DP). ISRL-DP ensures that the data of each person (e.g. patient) in silo $i$ (e.g. hospital $i$) cannot be leaked. ISRL-DP is different from well-studied privacy notions. Central and user-level DP assume that people trust the server/other silos. On the other end of the spectrum, local DP assumes that people do not trust anyone at all (even their own silo). Sitting between central and local DP, ISRL-DP makes the realistic assumption (in cross-silo FL) that people trust their own silo, but not the server or other silos. In this work, we provide tight (up to logarithms) upper and lower bounds for ISRL-DP FL with convex/strongly convex loss functions and homogeneous (i.i.d.) silo data. Remarkably, we show that similar bounds are attainable for smooth losses with arbitrary heterogeneous silo data distributions, via an accelerated ISRL-DP algorithm. We also provide tight upper and lower bounds for ISRL-DP federated empirical risk minimization, and use acceleration to attain the optimal bounds in fewer rounds of communication than the state-of-the-art. Finally, with a secure “shuffler” to anonymize silo messages (but without a trusted server), our algorithm attains the optimal central DP rates under more practical trust assumptions. Numerical experiments show favorable privacy-accuracy tradeoffs for our algorithm in classification and regression tasks.

Published as a conference paper at ICLR 2023
PRIVATE FEDERATED LEARNING WITHOUT A TRUSTED
SERVER: OPTIMAL ALGORITHMS FOR CONVEX
LOSSES
Andrew Lowy
Meisam Razaviyayn
Department of Mathematics University of Southern Californi Los Angeles, CA 90089, USA lowya@usc.edu
Department of Industrial & Systems Engineering University of Southern California
Los Angeles, CA 90089, USA ra razavis yalusc.eduu
ABSTRACT
This paper studies federated learning (FL)- especially cross-silo FL-with data from people who do not trust the server or other silos. In this setting, each silo (e.g. hospital) has data from different people (e.g. patients) and must maintain the privacy each person's 's data (c.g. medical record), even the server or other silos act as adversarial eavesdroppers. This requirement motivates the study of Inter-Silo Record-Level Differential Privacy (ISRL-DP), which requires silo i's communications satisfy record/item-level differential privacy (DP). ISRL-DP ensures that the data of each person (e.g. patient) in silo i (e.g. hospital i) cannot be leaked. ISRL-DP is different from well-studied privacy notions. Central and user-level DP assume that people trust the server/other silos. On the other end of the spectrum, local DP assumes that people do not trust anyone at all (even their own silo). Sitting between central and local DP, ISRL-DP makes the realistic assumption (in cross-silo FL.) that people trust their own silo, but not the server or other silos. In this work, we provide tight (up to logarithms) upper and lower bounds for ISRL-DP FL with convex/strongly convex loss functions and homogeneous (i.i.d.) silo data. Remarkably, losses with arbitrary heterogeneous silo data distributions, via an accelerated ISRL-DP algorithm. We also provide tight upper and lower bounds for ISRL-DP federated empirical risk minimization, and use acceleration to attain the optimal bounds in fewer rounds of communication than the state-of-the-att Finally, with a secure "shuffler" to anonymize silo messages (but without a trusted server), our algorithm attains the optimal central DP rates under more practical trust assumptions. Numerical experiments show favorable privacy-accurage tradeoffs for our algorithm in classification and regression tasks.
show that similar bounds attainable for smooth
INTRODUCTION
Machine learning tasks often involve data from different "silos" (e... cell cell-phone users or organizations such as hospitals) containing sensitive information (e.g. location or health records). In federated learning (FI.), each silo (a.k.a. "client") stores its data locally and central server coordinates updates among different silos to achieve global learning objective (Kairouz et al., 2019). One of the primary reasons for the introduction of FL was to offer greater privacy (McMahan et al., 2017). However, storing data locally is not sufficient to prevent data leakage. Model parameters or updates can still reveal sensitive information (e.g. via model inversion attacks membership inference attacks) (Fredrikson et al., 2015; He et al., 2019; Song et al., 2020; Zhu & Han, 2020).
Differential privacy (DP) (Dwork et al., 2006) protects against privacy attacks. Different notions of DP have been proposed for FL. The works of Jayaraman & Wang (2018); Truex et al. (2019); Noble al. (2022) considered central DP (CDP) FL. which protects the privacy of silos' aggregated data against an external adversary who observes the final trained model. There are two major issues with
We abbreviate central differential privacy by CDP. This is different than the concentrated differential privacy notion in Bun & Steinke (2016), for which the same abbreviation sometimes used in other works.

---

Published as a conference paper at ICLR 2023
1) it does not guarantee privacy for each specific silo; and 2) it does not guarantee data privacy when an adversarial eavesdropper has access to other silos or the server. To address the first issue, McMahan et al. (2018); Geyer et al. (2017); Jayaraman & Wang (2018); Gade & Vaidya (2018); Wei et al. (2020a); Zhou & Tang (2020); Levy et al. (2021); Ghazi et al. (2021) considered user-level DP (a.k.a. client-level DP). User-level DP guarantees privacy of each silo's s full local data set. This is a practical notion for cross-device FL, where each silo/client corresponds to single person (c.g. cell-phone user) with many records (e.g. text messages). However, user-level DP still suffers from the second critical shortcoming of CDP: it allows silo data to be leaked to an untrusted server or to other silos. Furthermore, user-level DP is less suitable for cross-silo FL, where silos are typically organizations (e.g. hospitals, banks, or schools) that contain data from many different people (e.g. patients, customers, or students). In cross-silo FI., each person has record (a. "item") that may contain sensitive data. Thus, an appropriate notion of DP for cross-silo FL. should protect the privacy of each individual record ('item-level DP") in silo i, rather than silo i's full aggregate data.
CDP FL:
Aceeaey
Another notion of DP is local DP (LDP) (Kasiviswanathan et al., 2011; Duchi et al., 2013). While central and user- level DP assume that people trust all of the silos and the server, LDP assumes that individuals (e.g. patients) do not trust anyone else with their sensitive data, not even their own silo (e.g. hospital). Thus, LDP would require each person (e.g. patient) to randomize her report (e.g. medical test results) before releasing it (e.g. to their own doctor/hospital).. Since patients/custoomrr//suddde ally trust their own hospital/bank//chool LDP may be unnecessarily stringent, hindering performancelaccuracy,
Server
Adverury
Advenury
usu-
DV
Figure I: ISRL-DP protects the privacy of each patient's record regardless of whether the server/other silos trustworthy, long as the patient's own hospital is trusted. By contrast, user-level DP protects aggregate data of patients in hospital i and does not protect against adversarial serverfother silos. et al. (2020); Huang et al. (2020); Huang & Gong (2020); Wu et al. (2019); Wei et al. (2020b); Dobbe al. (2020); Zhao et al. (2020); Arachchige al. (2019); Seif al. (2020); Liu al. (2022). We provide a rigorous definition of ISRL-DP in Definition 2 and Appendix B.
In this work. we consider privacy notion called inter- silo record-level differential privacy (ISRI-DP), which requires that all of the communications of each silo satisfy (item-level) DP; see Fig. 1. By the post-procsssing prop- erty of DP, this also ensures that the the broadcasts by the server and the global model are DP. Privacy notions simi- lar or identical to ISRL-DP have been considered in Truex
Why ISRL-DP? ISRL-DP is the natural notion of DP for cross-silo FI., where each silo contains data from many individuals who trust their own silo but may not trust the server or other silos (e.g.. hospitals in Fig. 1). The item-level privacy guarantee that ISRL-DP provides for each silo (e.g. hospital) ensures that no person's 's record can be leaked. In contrast to central DP and user-level DP, the protection of ISRL-DP is guaranteed even against an adversary with access to the server and/or other silos (e.g. hospitals). This is because each silo's communications are DP with respect to their own data records and cannot leak information to any adversarial eavesdropper. On the other hand, since individuals (e.g. patients) trust their own silo (e.g. hospital), ISRL-DP does not require individuals to randomize their own data reports (c.g. health records). Thus, ISRL-DP leads to better performancc/accurrayy than local DP by relaxing the strict local DP requirement. Another benefit of ISRL-DP is that each silo i can set its own (G, 5,) item-level DP budget depending on its privacy needs; see Appendix H and also Liu et al. (2022); Aldaghri al. (2021).
In addition, ISRL-DP can be useful in cross-device FL without a trusted server: If the ISRL privacy parameters are chosen sufficiently small, then ISRL-DP implies user-level DP (see Appendix C). Unlike user- DP, ISRL-DP does not allow data to be leaked to the untrusted server/other users.
Another intermediate trust model between the low-trust local model and the high-trust central/user- level models is the shuffle model of DP (Bittau et al., 2017; Cheu et al., 2019). In this model, a secure shuffler receives noisy reports from the silos and randomly permutes them before the reports are sent to the untrusted server. An algorithm is Shuffle Differentially Private (SDP) if silos' shuffled
2 Assume that the reports can he decrypted by the server, but not by the shuffler Frlingsson et al. (2020n); Feldman al. (2020b).
2

---

Published as a conference paper at ICLR 2023
messages CDP; see Definition 3. Fig. 2 summarizes which parties are assumed to be trustworthy (from the perspective of person contributing data to a silo) in each of the described privacy notions.
Problem setup: Consider a FL setting with N silos, each containing local data set with n samples;" X; (Ii. ;(,,,, for E [N] := {1.... ....... J.. each round of communication r, silos download the global model Wi and use their local data to improve the model. Then, silos send local updates
to the server (or other silos, in peer-to-pect peer FL.), who updates the global model to wr+1- For each
silo i, let Dj be an unknown probability distribution on data universe X, (i.e. X, 2²"). Let
X U X, Given loss function f /:W W
X R. define silo i's local objective as F((w) == Re [f(w, x:]..
(I)
where W = Rd is a parameter domain. Our goal is find model parameter that performs well for all silos, by solving the FL problem
Low
High trust
min wWW
F(w)
r(w)) N
N Σ
(2)
Local DP
Inter-Silo Record- Leval DP
DP
Contral
User-lovel
DP
while maintaining the privacy of each silo's local data, At times, we will focus empirical risk minimization (ERM), where Fi(w))
Trust one's
silo (e.g. hospital)?
Σこ ((w,)i.) is silo i's local objective. Thus, in the ERM case, our goal is to solve min Fx (w) = Σn" (w)) while main- taining privacy. When F; takes the form (1) (not neces- sarily ERM), we may refer to the problem as stochastic convex optimization (SCO) for emphasis. For ERM, we make no assumptions on the data; for SCO, we assume the samples { he (iee) are drawn independently. For SCO, we say problem (2) is "i.i.."" or "homoge- neous" if X; X and D, D. Vi. The excess risk of an algorithm A for solving (2) is EF(A(X) - F*, where F wnw F(w) and the expectation is taken over both the random draw of X (X),..., .x) and the randomness of A. For ERM, the excess empirical risk of A is (A(x))()) solely over the randomness of A. Thus, fundamental
"Trust" shuffler?
X
Trust server?
X
X
Trust other silos g. hospilalss?
Figure 2: Trust assumptions of DP FL tions: We put "trust" in quotes because the shuffler assumed to secure and silo messages must already satisfy (at least a weak level of) ISRL-DP in order to realize SDP: anonymization alone cannot "create" DP (Dwork & Roth, 2014).
fxx where the expectation is taken
question in FL is about the minimum achievable excess risk while maintaining privacy. In this work. we specifically study the following questions for FL with convex and strongly convex loss functions:"
What is the minimum achievable excess risk for solving (2) with inter-silo record-level DP?
Question 1.
Question 2. With a trusted shuffler (but no trusted server), can the optimal central DP rates be attained?
Our first contribution is a complete answer to Question 1 when silo data is i.i.d.: we give tight upper and lower bounds in Section 2. The ISRL-DP rates sit between the local DP and central DP rates: higher trust allows for higher accuracy. Further, we show that the ISRL-DP rates nearly match the optimal non-private rates if d & neg. where ég is the ISRL-DP parameter ("privacy for free"). As a corollary of our analysis, we also derive tight upper and lower bounds for FL algorithms that satisfy both ISRL-DP and user-level DP simultaneously. which could be useful in cross-device settings where (e.g. cell phone) users don't 't trust the server or other users with their sensitive data (e.g. text messages): see Appendix D.3.5.
Contributions:
Second, we give a complete answer to Question! 1 when F = Fx is an empirical loss in Section 4.5 While (Girgis et al., 2021) provided tight upper bound for the (non-strongly) convex case, use
In Appendix H, we consider the more general setting where data set sizes n, and ISRL-DP parameters (ei, 6.) may vary across silos, and the weights pa on each silo's loss F, in (2) may differ (i.e. p. * 1/N). 'Function g W - IR is p-strroggly convex (j. > 0) if g(w) > g(w') + (ōg(w'), (iq(w"),ver w w/) + #
w/|l II wt, w' W and all sub-gradients 0g(w"). If µ 0, y is convex.
'ERM a special case of the Fl. problem (2): if Dj is the empirical distribution X then F == Px.
3

---

Published as a conference paper at ICLR 2023
novel accelerated algorithm to achieve this upper bound in fewer communication rounds. Further, we obtain matching lower bounds. We also cover the strongly convex case.
Third, we give partial answer to Question 1 when silo data is heterogeneous (non-i.i.d.) providing algorithms for smooth f(.,z) that nearly achieve the optimal i..d. rates in Section 3. For example, if f(),)) is j-strongly convex and B-smooth, then the excess risk of our algorithm nearly matches the i.i.d. lower bound up to multiplicative factor of ((3/p). Our algorithm is significantly more effective (in terms of excess risk) than existing ISRI.-DP FL. algorithms (e.g. Arachchige et al. (2019); Dobbe et al. (2020); Zhao et al. (2020)): see Appendix for a thorough discussion of related work.
Fourth, we address Question 2 in Section 5: We give a positive answer to Question 2 when silo data is i.i.d. Further, with heterogeneous silo data, the optimal central DP rates are nearly achieved without trusted server, if the loss function is smooth. We summarize our results in Fig. 3.
1.1 PRELIMINARIES
Loss Func.
Excess Risk Upper Bound
Excess Risk Lower Bound
Differential Privacy: Let X = XAT ... and p X² - [0, x)) be a distance between databases. Two databases X,X' X are p- adjaceni if p(X, X') & 1. DP ensures that (with high probability) an adversary cannot dis- tinguish between the outputs of algorithm A when it is run on adjacent databases:
problem
vi
va
ISRL-DP i...
Convex
2.1)
v.N
W d
2.2
SCO
Strongly Convex
(Tm.. 2.11
2.2
Smooth Convex
v
v
ISRL-DP non-il.d.
(Tm.
3.11
Vnn
/u 221
Definition 1 (Differential Privacy). Let > O, E [o, 1). randomized algorithm :
SCO
Smooth
(Thm.
Thm
strongly
aN
3.1)
229
y/a
(irgs
ya
X - W is (e, (e,8)-differee differentially private (DP) (with respect to p) if for all p-adjacent data
Convex
20211
Thmm 4.2)
ISRL-DP ERM
(Thm.
4.1)
Strongly
(Thm.
(Thm. 4.2)
sets X,X X'X e X and all measurable subsets
Convex
4.11
S S W, we have
vd
(Thm.
V
(Bassly
SDP i.d.
Convex
v/n
6.11
P(A(X) S) & <EP(((X) E 5. (3)
sCo
Strongly
(Tm.
(Bassly ct
Definition 2 (Inter-Silo Record-Levv Differ-
Convex
A.V
6.91
AN
al, 2019)
ential Privacy). Let Pi X?
(() Σ5=1 I (p1,+ i [N]. A
[0. co),
SDP non-ii.d.
Smooth
Convex
v/N
cnN
(Thm.
5.21
Vun onn
v/
(Basaly
2018
at at...
randomized algorithm A is (Eo, 80) 80)-ISRL-DP DP for all E [N] and all pi-adjacent silo data sets X,, X², the full transcript of silo i sent messages satisfies (3) for any fixed settings of other silos' messages and data.
SCO
strongly
Smooth
R.V
c'e'N"
Via
(Thm. 5.2)
d
Basshy
2015)
al.
Figure 3: We fix M N, omit logs, and Ca := Lonv/N/Vajar Round complexity in Theorem 4.1 improves (Girgis al., 2021). *For non-i.idd al- gorithm, Theorem 2.2 only applies if co (1/nn) or N = =()) see Appendix D.3.
Definition 3 (Shuffle Differential Privacy (Bit- tau et al., 2017; Cheu al., 2019)). A random-
ized algorithm A is (c, 8)-shuffle DP (SDP) if for all p-adjacent databases X, E X and all measurable subsets S, the collection of all uniformly randomly permuted messages that are sent by
the shuffler satisfies (3), with p(X, (X) = D. - (11.+
Notation and Assumptions: Let| || be the E2 norm and (2w(2): argmin |w 2|2 denote
the projection operator. Function h: : W - Rm is L-Lipschitz if [[h(w) h ((w)) < Ll[w - w'll. Yw, w/ E W. A differentiable function h(-) is 3-smooth if its derivative Vh is 8-Lipschitz. If h is B-smooth and p-strongly convex, denote its condition number by k := 3/p.. For differentiable (w.r.t. w) f(w,, we denote its gradient w.r.t. by V (w) Write a S b if 3C 0 such that Cb. Write a = Ö(b) if a & log" (0)b for some parameters 0. Assume the following throughout:
Assumption 1.
W TRd is closed, convex, and ||w w'| & D, Yw, u' e W.
2. f(,,z) is L-Lipschitz and convex for all x E X. In some parts of the paper, we assume f(,,z) x) is p-strongly convex.
3. sup wew Er.-D. E...D.IVV[,,.. x,) VF((W) & o for all i [N].
4. In each round r, uniformly random subset S, of M, [N] silos is available to communi- cate with the server, where (My)rau are independent random variables with 1
M := E( M.
4

---

Published as a conference paper at ICLR 2023
In Assumption part 4, the network determines M,: it is not design parameter. This assumption is more general (and realistic for cross-devics FL (Kairouz et al., 2019)) than most (DP) FL works, which usually assume M N M, M is deterministic. On the other hand. in cross-silo FL, typically all silos can reliably communicate in each round, i.e. M = N (Kairouz et al., 2019).
2 INTER-SILL RECORD-LEVEL, DP FL WITH HOMOGENEOUS SI1. DATA
In this section, we provide tight (up to logarithms) upper and lower bounds on the excess risk of ISRL-DP algorithms for FL with i.i.d silo data. For consistency of presentation, we assume that there is an untrusted server. However, our algorithms readily extend to peer-to-peer FL (no server), by having silos send private messages directly to each other and perform model updates themselves.
2.1 UPPER BOUNDS VIA NOISY DISTRIBUTED MINIBATCH SGD
We begin with our upper bounds, obtained via Noisy Distributed Minibatch SGD (MB-SGD): In each round r, all M, available silos receive Wp from the server and send noisy stochastic gradients to the server: Tf == K Σソー V.(W,, =ig)) + us, where ~ (O, La and of are drawn uniformly from X, (and then replaced). The server averages these M, reports and updates wr+1 == Iwl[wr Jr.
M. Eies, Fr1. After R. rounds, weighted average of the iterates is returned: 6R PR E 70
with I Rt-1 Tr. With proper choices of (Te, 7r
RR-1 o², K, and R, we have:
Theorem 2.1 (Informal). Let eo 221n(2/0)) 6o E (0, 1). Then Noisy MB-SGD is (eo, -1S-LDDD
Moreover:
If f(,,z) is convex, then
EF(@R) F*
3
LD
1
(d
(4)
VM
Vni
ea72
2. If f()2)) is p-strooggyy convex, then
L2
1
d dln((160))
BF(#R) - F
(5)
J.M
72
The first terms in each of (4) and (5) (LD/vMM for convex and L2/ for strongly convex) are bounds on the uniform stability (Bousquet & Elisseeff, 2002) of Noisy MB-SGD. We use these uniform stability bounds to bound the generalization error of our algorithm. Our stability bound for O in Lemma D.2 is novel even for N = 1. The second terms in (4) and (5) are bounds the empirical risk of the algorithm. We use Nesterov smoothing (Nesterov, 2005) to extend our bounds to non-smooth losses. This requires us choose different stepsize and R from Bassily et al. (2019) (for N ==1 1, = O), which eliminates the restriction on the smoothness parameter that appears in (Bassily al., 2019, Theorem 3.2). Privacy of Noisy MB-SGD follows from the Gaussian mechanism (Dwork & Roth, 2014, Theorem A.2). privacy amplification by subsampling (Ullman, 2017), and advanced composition (Dwork Roth, 2014 4, Theorem 3.20) or moments accountant (Abadi et al., 2016, Theorem 1). See Appendix D.2 for the detailed proof.
2.2 LOWER BOUNDS
We provide excess risk lower bounds for the case M N, establishing the optimality of Noisy MB- SGD for two function classes: FL.D == (f f(, x) is convex, L-Lipschitz, Va E X and w w/| & D Vw, w'= E W): and Gp,L.D := (f E FL.D f(-,z) is u-strongly convex, Vz X).. We restrict attention to distributions 'D. satisfying Assumption 1, part 3. The (co, (o)- algorithm class (e), contains all sequentially interactive algorithms and all fully interactive, C-compositional (defined in Appendix D.3) algorithms." If A is sequentially interactive or ((1) compossiiiiii write A Ar(r The vast majority of DP algorithms in the literature are C-compositional. For example, any algorithm that uses the strong composition theorems of (Dwork & Roth, 2014; Kairouz et al., 2015; Abadi et al., 2016) for its privacy analysis is 1-compositional: see Appendix D.3.2. In particular, Noisy MB-SGD is 1-compositional, hence it is in (ca.bo)-
*In (Bassily et al., 2019), the number iterations is denoted by T. rather than R. "Sqquentially interactive algorithms can query silos adaptively in sequence, but cannot query any one silo more than once. Fully interactive algorithms can query each silo any number of times. See (Joseph et al., 2019) for further discussion.
5

---

Published as a conference paper at ICLR 2023
Theorem 2.2 (Informal). Let eo (0, (0.YM, 60 o(1/nN), M = N, and A 8oco Then:
1. There exists f E FL.D and a distribution such that for X Dun we have:
EF(A(X)) - -t = ΦD
LDmin min
<OIVNC=))
vd
Nn
2. There exists p-smooth f E EGH,LDD and distribution D such that for X ~ D'N,, we have d + LL min @ 1)
BF(A(X)) - b - (0 1²²
Further, A &. then the above lower bounds hold with C 1
The lower bounds for (ca.5)) are nearly tight by Theorem 2.1. The first term in each of the lower bounds is the optimal non-private rate; the second terms are proved in Appendix D.3.4. In particular, if E <fn, then the non-private term in each bound is dominant, so the ISRL-DP rates match the respective non-private rates, resulting in "privacy for free" (Nemirovskii & Yudin, 1983). The ISRL-DP rates sit between the rates for LDP and CDP: higher trust allows for higher accuracy. For example, for Fr.,D. the LDP rate OLD min{1, vd/eo (d//ov/N)) (Duchi et al., 2013), and the CDP rate is / + LD min(1, vd/ (Bassily et al., 2019).
Theorem 2.2 is more generally applicable than existing LDP and CDP lower bounds. When ISRL-DP is equivalent to LDP and Theorem 2.2 recovers the LDP lower bounds (Duchi et al., 2013; Smith al., 2017). However, Theorem 2.2 holds for a wider class of algorithms than the lower bounds of (Duchi et al., 2013; Smith et al., 2017), which were limited to sequentially interactive LDP algorithms. When N 1, ISRL-DP is equivalent to CDP and Theorem 2.2 recovers the CDP lower bounds (Bassily et al., 2019).
Obtaining our more general lower bounds under the more complex notion of ISRL-DP challenging. The lower bound approaches of (Duchi et al., 2013; Smith et al., 2017; Duchi & Rogers, 2019) are heavily tailored to LDP and sequentially interactive algorithms. Further, the applicability of the standard CDP lower bound framework (e.g. (Bassily et al., 2014; 2019)) to ISRL-DP FL is unclear.
In light of these challenges, we take different approach to proving Theorem 2.2: We first analyze the central DP guarantees of A when silo data sets X1, , are shuffled in each round, showing that CDP amplifies
Ō /N ). We could not have concluded this from existing amplification results (Erlingsson et al., 2020b; Feldman et al., 2020b; Balle al., 2019; Cheu al., 2019; Balle et al., 2020) since these results are all limited to sequentially interactive LDP algorithms and n 1. Thus, we prove the first privacy amplification by shuffling bound for fully interactive ISRL-DP FL algorithms. Then, version of A. This implies that the shuffled algorithm A, has excess population loss that is lower bounded as in Theorem 2.2. Finally, have the same expected population loss. Note that our proof techniques can also be used to obtain ISRL-DP lower bounds for other problems in which a CDP lower bound is known.
apply the CDP lower bounds of Bassily et al. (2019) to A., the "shuffled"
observe that the i.idd assumption implies that A, and A
INTER-SILE RECORD-LEVER DP FL WITH HETEROGENEOUS SILO DATA
Consider the non-i.idd FL problem, where (w) takes the form (1) for some unknown distributions D; on X, Vi. The uniform stability approach that we used to obtain our i.i.d. upper bounds does not work in this setting. 9 Instead, we directly minimize by modifying Noisy MB-SGD as follows:
1. We draw disjoint batches of K local samples without replacement from each silo and set R [ Thus, stochastic gradients are independent across iterations, so our bounds apply to F.
2. We use acceleration (Ghadimi & Lan, 2012) increase the convergence rate.
3. To provide ISRL-DP, we re-calibrate x² and apply parallel composition (McSherry, 2009). After these modifications, we call the resulting algorithm One-Pass Accelerated Noisy MB-SGD. It is described in A Algorithm 1. In the strongly convex case, we use a multi-stage implementation of One- Accelerated Noisy MB-SGI (inspired by (Ghadimi & Lan, 2013)) to further expedite convergence: see Appendix E. for details. Carefully tuning step sizes, 0². and K yields:
*Up to logarithms, a factor of &/ T., and for strongly convex case-a factor of jD/T. T.. If egn² N, then the ISRL-DP algorithm that outputs any w0 E W attains the matching upper bound O "Specifically, Lemma D.1 in Appendix D does not apply without the i.i.d. assumption.

---

Published as a conference paper at ICLR 2023
Theorem 3.1 (M = N case). Let (() be B-smooth for all x X. Assume co W 8 881n(1660) du (0,1). Then One-Pass Accelerated Noisy MB-SGD (Ea, 60) -ISRLDP. Moreover, if M N, then: For convex f(;, 3), we have
ΦD VNn
B3/ (ddn(1/66)
4/5
EF(wR)
F
(6)
2. For p-strongly convex 2() with
8
have
VK La dlIn(1/60) 2..2N
BF(wR) - F = JUN
(7)
Remarkably, the bound (7) nearly matches the optimal i.i.d. bound (5) up to the factor RR). In particular, for well conditioned loss functions, our algorithm achieves the optimal i.i.d. rates even when silo data is arbitrarily heterogeneous. The gap between the bound (6) and the i.i.d. bound (4) is (((Vd/oo//N))
Closing the gaps between the non-i.i.d upper bounds in Theorem 3.1 and the i..d. lower bounds in Theorem 2.2 is left as an open problem. Compared to previous upper bounds, Theorem 3.1 is major improvement: see Appendix A for details.
Algorithm Accelerated Noisy MB-SGD
1: Input: Data X; XP; e [N]. strong convexity modulus y4 > O, noise parameter o², iteration number R N, batch size K E [n]] step size parameters (π>]rejæ), (ar)rejn))
2: Initialize w/0 wo E W and = 1.
3: for [R]] do
4: Server updates and broadcasts wnnd (1-aa))utte))
7/- (1- (1-a))p w + ar a-((1ar)) Wy-1 ne +1-
5: for E S, in parallel do
6: Silo i draws {<t V from X, (replace samples for ERM) and noise ~ NO0,
7: Silo i computes of := K Σ V[( xx ))= Ug.
8: end for
9: Server aggregates gr
Mr is. Dr
and
updates
Wr
argmin=ew far Kūr, w) + w wol? + [1 a
[Wy-1-
- w/
2
Server updates and broadcasts u a, (1 a,, 7
11: end for
12:
Output: w
In Appendix E.2, we provide a general version (and proof) of Theorem 3.1 for M & N. If < N M is sufficiently large or silo heterogeneity sufficiently small, then the same bounds in Theorem 3.1 hold with replaced by M. Intuitively, the N case is harder when data is highly heterogeneous, since stochastic estimates of F will have larger variance. In Lemma E.3 (Appendix E.2), we use combinatorial argument to bound the variance of stochastic gradients.
INTER-SILO RECORD-LEVEL DP FEDERATED ERM
In this section, we provide ISRL-DP Fl. algorithm, Accelerated Noisy MB-SGD, with optimal excess empirical risk. The difference between our proposed algorithm and One-Pass Accelerated Noisy MB-SGD is that silo now samples from X; with replacement in each round: see line 6 in Algorithm 1. This allows us to a) amplify privacy via local subsampling and advanced composi- tion/moments accountant, allowing for smaller o²; and b) run more iterations of our algorithm to better optimize Fx. These modifications are necessary for obtaining the optimal rates for federated ERM. We again employ Nesterov smoothing (Nesterov, 2005) to extend our results to non-smooth f.
Theorem 4.1 (Informal). Let en & 2 (n(/0o)) do (0, 1). Then, there exist algorithmic parameters such that Algorithm is (Co, 66)-1SRL-DP and:
1. If f(, x) is convex, then
(xx Frx = δ LD V (lm(1/)))
(8)
cnnyM
2. If f(;x)) is u-strongly convex then
BFx(w P = ((1 1.2 d1n(1166))
(9)
4 e
7

---

Published as a conference paper at ICLR 2023
See Appendix F.1 for the formal statement and proof. With non-random M, M, Girgis al. (2021) provides an upper bound for (non-strongly) convex ISRL-DP ERM that nearly matches the we provide in (8). However, Algorithm 1 achieves the upper bounds for convex and strongly convex loss in fewer rounds of communication than (Girgis et al., 20 see Appendix F.1 for details. In Appendix F.2, get matching lower bounds, establishing the optimality of Algorithm for ERM.
5 SHUFFLE DP FEDERATED LEARNING
Assume access to a secure shuffler and fix M, = M. In each round r, the shuffler receives reports ( 2!!²) from active silos (we assume S, [M] here for concreteness), draws uniformly Z, z(*(MO) to the server for aggregation. When this shuffling procedure is combined with ISRL-DP Noisy Distributed MB-SGD. obtain:
random permutation of [M] x, and then sends (z,-(1))
Theorem 5.1 (i.id.), Let 6 & ln(2/6), 8 E (0, 1). Then there are choices of algorithmic parameters such that Shuffled Noisy MB-SGD is (c, 6)-D....P Moreover:
1. If [(, () is convex, then
V vdln(1/5)
EF(ØR) F*
δ LD
VnM
enN
If [(,2)) 3)) is p-strongly convex, then
1,2 1
d'm(1/88 en?
EF(ØR) 1x ===
nM
See Appendix G.1 for details and proof. When M N, the rates in Theorem 5.1 match the optimal central DP rates (Bassily et al., 2019), and are attained without a trusted server. Thus, with shuffling, Noisy MB-SGD is simulianeously optimal for i.i.d. Fl. in the inter-silo and central DP models.
If silo data is heterogeneous, then we use shuffle DP variation of One-Pass Accelerated Noisy MB-SGD, described in Appendix G.2, to get:
Theorem 5.2 (N..-i.i.d.). Assume f(-, 2) is 3-smooth Vx X. Let & 15,5E E (0, (0,2). Then, there is an (e, SDP variation of One-Pass Accelerated Noisy MB-SGD such that for M = N, we have: 1. If f(, 2) is convex, then
&D
QVAALD* /alm(d/0)
RF(( p* s
+
(10)
NNn
enN
2. If f(.2)) is p-strongly convex with k u then
0²
La d(m(1188) PoLNT
(F F*
(11)
J
The bound (11) matches the optimal i.i.d., central DP bound (Bassily et al., 2019) up to (VVR). Hence, if f is not ill-conditioned, then (11) shows that is not necessary to have either i..d. data or a trusted server to attain the optimal CDP rates. See Appendix G.2 for proof and the M < N case.
6 NUMERICAL EXPERIMENTS
We validate our theoretical findings with three sets of experiments. Our results indicate that ISRL-DP MB-SGD yields accurate, private models in practice. Our method performs well even relative to non-private Local SGD, a.k.a. FedAvg (McMahan et al., 2017), and outperforms ISRL-DP Local SGD for most privacy levels. Appendix I contains details of experiments, and additional results. 10
Following (Woodworth et al., 2020b), we consider binary logistic regression MNIST (LeCun & Cortes, 2010). The task is to classify digits as odd or Each of 25 odd/even digit pairings is assigned to a silo (N 25). Fig. 4 shows that ISRL-DP MB-SGD outperforms (non-privale) Local SGD for e 12 and outperforms ISRL-DP Local SGD.
Binary Logistic Regression with MNIST:
Linear Regression with Health Insurance Data:
We divide the data set (Choi, 2018) (d = 7, x
N 1338) into N silos based the level of the target: patient medical costs. Fig. 5 shows that ISRL-DP MB-SGD outperforms ISRL-DP Local SGD, especially in the high privacy regime < 2. For 3 2, ISRL-DP MB-SGD is in line with (non-private) Local SGD.
We also describe the ISRL-DP Local SGD baseline in Appendix I.
8

---

Published as a conference paper at ICLR 2023
Multiclass Logistic Regression with Obesity Data: We train softmax regression model for 7- way classification task with an obesity data set (Palechor & de la Hoz Manotas, 2019). We divide the data into N 7 heterogeneous silos based on the value of the target variable, obesity level, which takes 7 values: Insufficient Weight, Normal Weight, Overweight Level I, Overweight Level II, Obesity Type I, Obesity Type II and Ohesity Type III. As shown in Fig. 6, our algorithm significantly outperforms DPRL-DP Local SGD by 10 - 30% across all privacy levels.
N 25, M 25
N 25, M
0.2
ISRL DP MB-900
rounds
ISRL
0.0
SGD
0.24
after 25 rounds
Test Enoo Thal)
0.19
MB 6GO after 36 rounds
Local SGD after 25 rounds
Test Erro Thaio)
0.22
Local BOD after 35 rounds
SCD rounds
0.38
0.20
0.17
0.1
0.18
0.16
0.14
0.14
013
0.0
2.5
5.0
7.5
10.0
12.5
15.0
17.5
0.0
25
5.0
7.5
10.0
12.5
15.0
17.5
Figure 4: Binary logistic regression on MNIST. 5 1/n².. 90% error bars are shown.
2
No5. M 5
ISRL.OP MB-SGD
ISAL MB 800
ISRL.DP
rounds
30-
MB Local sco after 35 rounds Local SGD ofee rounds
stvv Test RMSE Tratt
ND-600 after 35 rounds
Local 5GD efter rounds
0.9-
071
06
Figure 5: Linear regression on health insurance data, 5 = 1/n2, 90% error bars are shown.
N M
N
0.80
ISRL-OP MB-SGD after rounds ISRL-OP Local
ISRL-DP MB MB-SGD after 35 rounds
rounds
ISRL-DP Local SGD after 35 rounds.
MB-SGD after 35 rounds
MB-SGD after rounds
0.70
Local SGD after 35 rounds
0.7
SGD after rounds
0.6
0.60
0.55
0.50
0.-
0.45
2
Figure 6: Softmax regression obesity data. 8 1/1e"
CONCLUDING REMARKS AND OPEN QUESTIONS
This paper considered FL without a trusted server and advocated for inter-silo record-level DP (ISRL-DP) as a practical privacy notion in this setting, particularly in cross-silo applications. We provided optimal ISRL-DP algorithms for convex/strongly convex FL in both the i.i.d. and ERM settings when all M = N clients are able to communicate. The i.i.d. rates sit between the rates for the stringent "no trust" local DP and relaxed "high trust" central DP notions, and allow for "privacy for free" when d & <.n. As side result, in Appendix D.3.5, we established the optimal rates for cross-device FL with user-level DP in the absence of a trusted server. Additionally, we devised an accelerated ISRL-DP algorithm to obtain state-of-the-art upper bounds for heterogeneous FL. We also gave a shuffle DP algorithm that (nearly) attains the optimal central DP rates for (non-ii.d.) i.i.d. FL. An open problem is to close the gap between our i.i.d. lower bounds and non-i.i.d upper bounds: e.g. can /k in (7) be removed? Also, when M < N, are our upper bounds tight? Finally, what performance is possible for non-convex ISRL-DP FL.?
9

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This work was partly supported by gift from the USC-Meta Center for Research and Education in Al and Learning.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Oct 2016. doi: 10.11452997674..9988811 URL http:http////t. //xp doi lorg/100 1144.11997174444 11117777777927881111 2.78318 8.
Alekh Agarwal, Peter L. Bartlett, Pradeep Ravikumar, and Martin J. Wainwright, Information- theoretic lower bounds on the oracle complexity of stochastic convex optimization. IEEE Transac- tions Information Theory, (8(5):3335-32499 2012. doi: 10. 1019/TTT.2011.21821111
Nasser Aldaghri, Hessam Mahdavifar, and Ahmad Beirami. Feo2: Federated learning with opt-out differential privacy. arXiv preprini arXiv:21 10. 15252, 2021.
Pathum Chamikara Mahawaga Arachchige, Peter Bertok, Ibrahim Khalil, Dongxi Liu, Seyit Camtepe, and Mohammed Atiquzzaman. Local differential privacy for deep learning. IEEE Internet of Things Journal, 7(7):5827-588) 2019.
Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates 11 geometry. In International Conference on Machine Learning, pp. 393-403.
PMLR, 2021.
Borja Balle, James Bell, Adria Gascón, and Kobbi Nissim. The privacy blanket of the shuffle model. In Anmual International Cryptology Conference, pp. 638-667. Springer, 2019.
Borja Balle, Peter Kairouz, Brendan McMahan, Om Dipakbhai Thakkar, and Abhradeep Thakurta. Privacy amplification via random check-ins. 33, 2020.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 464-473. IEEE, 2014.
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta. Private stochastic convex optimization with optimal rates. In Advances in Neural Information Processing Systems, 2019.
Andrea Bittau, Ulfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld. Prochlo: Strong privacy for analyties in the crowd. In Proceedings of the Symposium on Operating Systems Principles (SOSP), pp. 1411,49,,,, 2017.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Proceedings, Part of the 14th International Conference Theory of Cryptography Volume 9985, pp. 635-658, Berlin, Heidelberg, 2016. Springer- Verlag. ISBN 9783662536407. doi: 10. 1111000977-36622--555 3-17888-662---66111 24. URL ht /oo. ort.0/..0000000 978 1118---20 3--33-6622 662 0002-33441-2 53641-4_24
Yi-Ruei Chen, Amir Rezapour, and Wen-Guey Tzeng. Privacy-preserving ridge regression on distributed data. Information Sciences, 451:34 49, 2018.
Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. Distributed differ- ential privacy via shuffling. In Annual International Conference the Theory and Applications of Cryptographic Techniques, pp. 375-403. Springer, 2019.
Albert Cheu, Matthew Joseph, Jieming Mao, and Binghui Peng. Shuffle private stochastic convex optimization. arXiv preprint arXiv:2 106.09805 2021.
10

---

Published as a conference paper at ICLR 2023
Miri Choi. Medical insurance charges data. 2018. URL https://www.kagett
mirichoi0218/ itw.uuran/.nnnnnn.e....m
Frank Den Hollander. Probability theory: The coupling method. 2012.
Roel Dobbe, Ye Pu, Jingge Zhu, Kannan Ramchandran, and Claire Tomlin. Customized local
differential privacy for multi-agent distributed optimization, 2020.
John Duchi and Ryan Rogers. Lower bounds for locally private estimation via communication complexity. In Conference on Learning Theory, pp. 1161-1191. PMLR, 2019.
John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 429-438, 2013. doi: 10.1 (L09//CCS.2033..5
Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. 2014.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006.
Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Shuang Song, Kunal Talwar, and Abhradeep Thakurta. Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation. arXiv preprint arXiv:200..036/4 2020a.
Ulfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity, 2020b.
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Alina Beygelzimer and Daniel Hsu (eds.), Proceedings of the Thirty-Second Conference on Learning Theory. volume 99 of Proceedings of Machine Learning Research, pp. 1270-1279, Phoenix, USA, 25-28 Jun 2019. PMLR. URL http:// proceedings mlr press / v999 fel.manl1ll html.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 439-449, 2020a.
Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling, 2020b.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confidence information and basic countermeasures. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communccations Security, pp. 1322-1333, 2015.
Shripad Gade and Nitin H Vaidya. Privacy-preserving distributed learning via obfuscated stochastic gradients. In 2018 IEEE Conference on Decision and Control (CDC), pp. 184-191. IEEE, 2018.
Robin C. Geyer, Tassilo Klein, and Moin Nabi. Differentially private federated learning: A client level perspective. CoRR, abs/1772.00557, 2017. URL http: / arxiv. org/ abs 1 1722..112 07557.
Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on Optimization, 22(4): 1469 1469-149992 1492, 2012. doi: 10. 10848864. URL https: peettps://do.oooo orgg
10. 100. 4888864.
Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, ii: Shrinking procedures and optimal algorithms. SIAM Journal on Optimization, 23(4):2061-2085 2013. doi: 1 10848876. URL https: //doi. , 110 11 1111 1111/11118887
Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. User-level private learning via correlated sampling. arXiv preprint arXiv:2110.1 /208, 2021.
11

---

Published as a conference paper at ICLR 2023
Antonious Girgis, Deepesh Data, Suhas Diggavi, Peter Kairouz, and Ananda Theertha Suresh. Shuffled model of differential privacy in federated learning. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 2521-2529. PMLR, 13-15 Apr 2021. https:::: http///ooocedgegee ngs .ll. www...p...s......m...mmmmmmmmm.e v wttpppeess/l1////gg/gg//e/
html.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning. volume 48 of Proceedings of Machine Learning Research, pp. 1225-1234, New York, New York, USA, 20-22 Jun 2016. PMLR. URL http:/ / ngs ml ..r.pree press / v/8///////// /ha rdt 6 html.
Zecheng He, Tianwei Zhang, and Ruby B Lee. Model inversion attacks against collaborative inference. In Proceedings of the 35th Annual Computer Security Applications Conference, pp. 148-162, 2019.
Zonghao Huang and Yanmin Gong, Differentially private ADMM for convex distributed learning: Improved accuracy via multi-step approximation. arXiv preprint:2005.07553 07890, 2020.
Zonghao Huang, Rui Hu, Yuanxiong Guo, Eric Chan-Tin, and Yanmin Gong. DP-ADMM: ADMM- based distributed learning with differential privacy. IEFE Transactions on Information Forensics and Security, 001-1002,, 2020.
Bargav Jayaraman and Lingxiao Wang. Distributed learning without distress: Privacy-preeerving empirical risk minimization. Advances in Neural Information Processing Systems, 2018.
Matthew Joseph. Jieming Mao. Seth Neel, and Aaron Roth. The role of interactivity in local differential privacy. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pp. 94-105. IEEE, 2019.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy, 2015.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, 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 U. 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 in federated learning. arXiv 191print:1912.04490
2019.
Gautam Kamath. Cs 860: Algorithms for private data analysis, 2020. URL http:/ /www. gautamkamath..c com/ wtc.cc/cc///cc 60eonennnnsseeeeeee letes//eeec.......
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In 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. 5132-5143. PMLR, 13-18 Jul 2020.
Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793-826, 2011.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Better communication complexity for local SGD. arXiv preprint, 2019.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized SGD with changing topology and local updates. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning. volume 1 119 of Proceedings of Machine Learning Research, pp. 5381-5393. PMLR, 13-18 Jul 2020.
12

---

Published as a conference paper at ICLR 2023
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL http: /yann. lecun. com/ eeeeee/mmmmme /w/is//ii//////////////mmei.isss
Lihua Lei, Cheng Ju, Jianbo Chen, and Michael I Jordan. Non-convex finite-sum optimization via sesg methods. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 2345-2355 2017.
Daniel Levy, Ziteng Sun, Kareem Amin, Satyen Kale, Alex Kulesza, Mehryar Mohri, and Ananda Theertha Suresh. Learning with user-level privacy. arXiv preprint arXiv:2102.11845, 2021.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of FedAvg on non-iid data. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020. URL https: httpp:://peerreviee. sernnrevveeweeeeee net Forum?id=Hin F.Rum??dddDxNAAAVtDD.
Jingcheng Liu and Kunal Talwar. Private selection from private candidates. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 298-309, 2019.
Ziyu Liu, Shengyuan Hu, Zhiwei Steven Wu, and Virginia Smith. On privacy and personalization in cross-silo federated learning. arXiv preprint arXiv:2206.0783 2022.
Ilan Lobel and Asuman Ozdaglar. Distributed subgradient methods for convex optimization over random networks. IEEE Transactions on Automatic Control, 1696)112 2010.
Andrew Lowy and Meisam Razaviyayn. Output perturbation for differentially private convex optimization with improved population loss bounds, runtimes and applications to private adversarial training. arXiv preprint:210..02 022004744 2021.
Xu Ma, Fangguo Zhang, Xiaofeng Chen, and Jian Shen. Privacy preserving multi-party computation delegation for deep learning in cloud computing. Information Sciences, 459:103-116, 2018.
Brendan McMahan, Eider Moore, Daniel Ramage. Seth Hampson, and Blaise Aguera y Arcas. Communicationn-lficcienn learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273 1282. PMLR, 2017.
Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In International Conference on Learning Representations (ICLR), 2018. URL https: /ttp:::////peeeeeere/ee net wwte/pfffiideeee idddfidd-JOOF11200
Frank D McSherry. Privacy integrated queries: extensible platform for privacy-preserve data analysis. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, pp. 19-30, 2009.
Jack Murtagh and Salil Vadhan. The complexity of computing the optimal composition differential privacy. In Theory of Cryptography Conference, pp. 157-175. Springer, 2016.
Angelia Nedie, Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27(4):2597-2633, 2017.
Arkadii Semenovich Nemirovski and David Borisovich Yudin. Problem Complexity and Method Efficiency in Optimization. 1983.
Yurii Nesterov. Smooth minimization of non-smooth functions. Mathematical programmingg 103(1): 127-152, 2005.
Maxence Noble, Aurélien Bellet, and Aymeric Dieuleveut. Differentially private federated learning heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pp. 10110-10145. PML.I..............MMM PMLR, 2022.
Fabio Mendoza Palechor and Alexis de la Hoz Manotas. Dataset for estimation of obesity levels based on eating habits and physical condition individuals from colombia, peru and mexico. Data in brief, 25: 104344, 2019.
13

---

Published as a conference paper at ICLR 2023
Nicolas Paperno and Thomas Steinke. Hyperparameter tuning with renyi differential privacy, 2021.
Mohamed Seif, Ravi Tandon, and Ming Li. Wireless federated learning with local differential privacy. In 2020 IEEE International Symposium on Information Theory (ISIT), pp. 2604-2609, 2020, doi: 10.1 00000STT4444..22000111
Adam Smith, Abhradeep Thakurta, and Jalaj Upadhyay. Is interaction necessary for distributed private learning? In 2017 IEEE Symposium Security and Privacy (SP), pp. 58-77, 2017. doi: 10. 10.1109/SP.211.335.
Mengkai Song, Zhibo Wang, Zhifei Zhang, Yang Song, Qian Wang. Ju Ren, and Hairong Qi. Analyzing user-level privacy attack against federated learning. IEEE Journal on Selected Areas in Communications, 38(10)2430-2444 2020. doi: 10.1 10.1099/...22220000003333
Sebastian U. Stich. Unified optimal analysis of the (stochastic) gradient method. arXiv
preprint: 044222, 2019.
Behrouz Touri and Bahman Gharesifard. Continuous-time distributed convex optimization on time- varying directed networks. In 2015 54th IEEE Conference on Decision and Control (CDC), pp. 724-729, 2015. doi: 10.1109/CDDC.2015..42200
Stacey Truex, Nathalic Baracaldo, Ali Anwar, Thomas Steinke, Heiko Ludwig, Rui Zhang, and Yi Zhou. A hybrid approach to preseevii federated learning. In Proceedings of the 12th
ACM Workshop on Artificial Intelligence and Security, pp. 1-11, 2019.
Stacey Truex, Ling Liu, Ka-Ho Chow. Mehmet Emre Gursoy, and Wenqi Wei. LDP-Fed: federated learning with local differential privacy. In Proceedings of the Third ACM International Workshop on Edge Systems, Analytics and Networking, pp. 61-66. Association for Computing Machinery, 2020. ISBN 9781450371322.
Jonathan Ullman. CS7880: rigorous approaches data privacy, 2017. URL http::/pp//ee ccs. meu.edus home / fulllllllllll malllman//// cs 78880s 7/WW sol. .ddf.
D Wang, M Ye, and J Xu. Differentially private empirical risk minimization revisited: Faster and more general. In Proc. 3 Annual Conference on Advances Neural Information Processing Systems (NIPS 2017), 2017.
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Hang Su, Bo Zhang, and H Vincent Poor. User-level preserving federated learning: Analysis and performance optimization. arXiv preprint:2003300022, 2020a.
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE Trunsactions on Information Forensics and Security, 15:3454-3469, 2020b.
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Memahan, Ohad Shamir, and Nathan Srebro. Is local SGD better than minibatch SGD? In International Conference on Machine Learning, pp. 10334-10343. PMLR, 2020a.
Blake E Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch vs local sgd for heterogeneous distributed learning. H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. ciates, Inc., 2020b. URL https: //ppccpeppp//pooceeeiiiggggge/ inwp:eceeeeeiinneeeneeeeeeeeeeee wwtpppppp////////c////c/ 2020/file/ (597116622011331caee222228888888
Curran Asso-
pdf.
Nan Wu, Farhad Farokhi, David Smith, and Mohamed Ali Kaafar. The value of collaboration in convex machine learning with differential privacy, 2019.
Honglin Yuan and Tengyu Ma. Federated accelerated stochastic gradient descent. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 5332-5344. Curran Asso- ciates, Inc., 2020. URL 3 39d0a8 908 fbe 8039ea 201216090002222777700032--220 .df.
/iiee/
14

---

Published as a conference paper at ICLR 2023
Yang Zhao, Jun Zhao, Mengmeng Yang, Teng Wang, Ning Wang, Lingjuan Lyu, Dusit Niyato, and Kwok- Yan Lam. Local differential privacy based federated learning for internet of things. IEEE Internet of Things Journal, 2020.
Yaqin Zhou and Shaojie Tang. Differentially private distributed learning. INFORMS Journal on Computing, 32(3):779-789, 2020.
Ligeng Zhu and Song Han. Deep leakage from gradients. In Federated learning, pp. 17-31. Springer, 2020.
15

---

Published as a conference paper at ICLR 2023
APPENDIX
To ease navigation, we provide a high-level table contents for this Appendix:
Contents
Appendix A: Thorough Discussion of Related Work
Appendix B: Rigorous Definition of Inter-Silo Record-Level DP
Appendix C: Relationships Between Notions of DP
Appendix D: Proofs and Supplementary Material for Section
Appendix E: Proofs and Supplemental Material for Section 3
Appendix F: Prools and Supplementary Material for Section 4
Appendix G: Proofs and Supplementary Materials for Section 5
Appendix H: ISRL-DP Upper Bounds with Unbalanced Data and Differing Silo Privacy Needs
Appendix Numerical Experiments: Details and Additional Results Appendix J: Limitations and Societal Impacts
16

---

Published as a conference paper at ICLR 2023
A THOROUGH DISCUSSION OF RELATED WORK
Federated Learning: In the absence of differential privacy constraints, federated learning (FL) has received lot of attention from researchers in recent years. Among these, the most relevant works to us are (Koloskova et al., 2020; Li et al., 2020; Karimireddy et al., 2020; Woodworth et al., 2020a;b; Yuan & Ma, 2020), which have proved bounds the convergence rate of FI. algorithms. From an algorithmic standpoint, all of these works propose and analyze either Minibatch SGD (MB-SGD), FedAvg/Local SGD (MeMahan et al., 2017), or an extension or accelerated/varaanc--rddeee variation of one of these (e.g. SCAFFOLD (Karimireddy et al., 2020)). Notably, Woodworth et al. (2020b) proves tight upper and lower bounds that establish the near optimality of accelerated MB-SGD for the heterogeneous SCO problem with non-random M, = M = N in fairly wide parameter regime. Lobel & Ozdaglar (2010); Touri & Gharesifard (2015); Nedic et al. (2017) provide convergence results with random connectivity graphs. Our upper bounds describe the effect of the mean of 1/M, on DP FL.
DP Optimization: In the centralized setting, DP ERM and SCO is well-understood for convex and strongly convex loss functions (Bassily et al., 2014; Wang et al., 2017; Bassily et al., 2019; Feldman et al., 2020a; Lowy & Razaviyayn, 2021; Asi et al., 2021).
Tight excess risk bounds for local DP SCO were provided in Duchi et al. (2013); Smith et al. (2017).
A few works have also considered Shuffle DP ERM and SCO. Girgis et al. (2021); Erlingsson et al. (2020a) showed that the optimal CDP convex ERM rate can be attained in the lower trust (relative to the central model) shufile model of DP. The main difference between our treatment of shuffle DP and Cheu et al. (2021) is that our results are much more general than Cheu et al. (2021). For example, Cheu al. (2021) does not consider FL: instead they consider the simpler problem of stochastic convex optimization (SCO). SCO is a simple special case of FL in which each silo has only n = 1 sample. Additionally, Cheu et al. (2021) only considers the i.i.d. case, but the more challenging non-i.i.d, case. Further, Cheu et al. (2021) assumes perfect communication (M- = .N), while we also analyze the case when MM N and some silos are unavailable in certain rounds (e.g. due internet issues). Note that our bounds in Theorem 5.1 recover the results in Cheu et al. (2021) in the special case considered in their work.
DP Federated Learning: More recently, there have been many proposed attempts to ensure the privacy of individuals' data during and after the FL process. Some of these have used secure multi-party computation (MPC) (Chen et al., 2018; Ma et al., 201 8), but this approach leaves users vulnerable to inference attacks on the trained model and does not provide the rigorous guarantee of DP. Others (McMahan et al., 2018: Geyer et al., 2017: Jayaraman & Wang, 2018; Gade & Vaidya, 2018; Wei et al., 2020a; Zhou & Tang, 2020; Levy et al., 2021; Ghazi et al., 2021; Noble et al., 2022) have used user-level DP or central DP (CDP), which rely trusted third party, hybrid DP/MPC approaches (Jayaraman & Wang, 2018; Truex et al., 2019). The work of (Jayaraman & Wang, 2018) proves CDP empirical risk bounds and high probability guarantees on the population loss when the data is i.i.d. across silos. However, ISRL-DP and SDP are not considered, nor is heterogeneous (non-i.i.d.) FL. It is also worth mentioning that (Geyer et al., 2017) considers random M, but does not prove any bounds.
Despite this progress, prior to our present work, very little was known about the excess risk potential of ISRL-DP FL algorithms, except in the two extreme corner cases of N = 1 and n = 1. When N = 1, ISRL-DP and CDP are essentially equivalent; tight ERM (Bassily et al., 2014) and i.i.d. SCO (Bassily et al., 2019; Feldman et al., 2020a) bounds are known for this case. In addition, for LDP i..d. SCO when n = and M, = N. (Duchi et al., 2013) establishes the minimax optimal rate for the class of sequentially interactive algorithms and non-strongly convex loss functions. To the best of our knowledge, all previous works examining the general ISRL-DP FL problem with arbitrary n, N >> either focus ERM and/or do not provide excess risk bounds that scale with both M and n, making the upper bounds provided in the present work significantly tighter. Furthermore, none of the existing works on ISRL-DP FL provide lower bounds upper bounds for the case of random M,. We discuss each of these works in turn below:
(Truex et al., 2020) gives a ISRL-DP FL algorithm, but no risk bounds are provided in their work.
The works of (Huang et al., 2020) and (Huang & Gong, 2020) use ISRL-DP ADMM algorithms for smooth convex Federated ERM. However, the utility bounds in their works stated in terms of an
17

---

Published as a conference paper at ICLR 2023
average of the silo functions evaluated at different points, so it is not clear how to relate their result to the standard performance measure for learning (which we consider in this paper); expected excess risk at the point e output by the algorithm. Also, no lower bounds are provided for their performance measure. Therefore, the sub-optimality gap of their result is not clear.
(Wu et al., 2019, Theorem 2) provides an (c, O)-SRLLDD ERM bound for fixed M, = -M N of O
(KL2 d nNZ + +c) for p-strongly convex, f-smooth f with condition number K. f/Jr, and 1/(²
is an average of 1/e.. The additive term is clearly problematic: e.g. if (1), then the bound becomes trivial. Ignoring this term, the first term in their bound is still looser than the bound that we provide in Theorem 4.1. Namely, for co. our bound in part 2 of Theorem 4.1 is tighter by factor of O
(n(1/66)) and does not require 6-smoothness of the loss. Additionally, the bounds in (Wu et al.,
2019) require "large enough" and do not come with communication complexity guarantees. In the convex case, the ISRL-DP ERM bound reported in (Wu et al., 2019, Theorem 3) is difficult to interpret because the unspecified "constants" in the upper bound on E (wx) allowed to depend on R.
Fxx are said to be
(Wei et al., 2020b, Theorems 2-3) provide convergence rates for smooth convex generalization of strong convexity) ISRL-DP ERM, which are complicated non-monotonic functions of R. Since they do not prescribe choice of R, it is unclear what excess loss and communication complexity bounds are attainable with their algorithm.
(a
(Dobbe al., 2020) proposes a ISRL-DP Inexact Alternating Minimization Algorithm (IAMA) with Laplace noise; their result (Dobbe et al., 2020, Theorem 3.11) gives a convergence rate for
e [ar) of ignoring smoothness and strong
smooth, strongly convex ISRL-DP FL of order
convexity factors, where θ is parameter that is only upper bounded in special cases (e.g. quadratic objective). Thus, the bounds given in (Dobbe et al., 2020) are not complete for general strongly convex loss functions. Even in the special cases where bound for θ is provided, our bounds are tighter. Assuming that θ = and (for simplicity of exposition) that parameters are the same across silos, (Dobbe et al., 2020, Theorem 3.11) implies taking o² 1/c2 to ensure (c, O)-ISRL-DP. The resulting convergence rate is then O(M/e², which does not scale with n. and is increasing with M. Also, the dependence of their rate on the dimension is unclear, it does not appear explicitly in their theorem." 11 Ignoring this issue, the dependence on M and n in the bound of (Dobbe et al., 2020) still looser than all of the excess loss bounds that we provide in the present work.
(Zhao et al., 2020) and (Arachchige et al., 2019) apply the ISRL-DP FL framework to Internet of Things, and (Seif et al., 2020) uses noisy (full-batch) GD for ISRL-DP wireless channels in the FL (smooth strongly convex) ERM setting. The bounds in these works do not scale with the number of data points n, however (only with the number of silos N). Therefore, the bounds that we provide in the present work are tighter, and apply to general convex FL problems besides wireless channels and Internet of Things.
B RIGOROUS DEFINITION OF INTER-SILL SILO RECORD-LEVEL DP
Recall:
Definition 4. (Differential Privacy) Let e 2/ 0, de [0, 1). A randomized algorithm A X - W is
8), for all p-adjacent data sets X, X' e X. and all measurable subsets S = W, we have
P(A(X) E S) & e (AA(') e S) +
(12)
If (12) holds for all measurable subsets S. then we denote this property by A(X) ~ A(X'). An
(c.5)
R-round fully interactive randomized algorithm for FL is characterized in every round r e [R] by
N local silo functions called randomizers R! g(x11)xN x XT - 2 (i [N] and an aggregation mechanism. (See below for an example that further clarifies the terminology used in this paragraph.)
The randomizers send messages z(() R. (1 X2), ), to the server or other silos. The messages
ll Note that in order for their result to he correct, by (Bassily et al., 2014) when N M 1, their bound must scale least d² /e2n" 2 unless their bound trivial (3 T.D).
18

---

Published as a conference paper at ICLR 2023
2 may depend on silo data X; and the outputs Z1:-1 (2,0) ] [ of silos' randomizers in prior rounds. Then, the server (or silos, for peer-to-peer FL) updates the global model. We consider the output of A : X - RRxN to be the transcript of all silos' communications: i.e. the
collection of all N R messages { Algorithm A is (Eo, 6o)-ISRL-DP if for all silos i, the full transcript {2, (re[rz) ) is (cu. 6 -D, for any fixed settings of the other silos' messages and data. More precisely:
Definition 5. (Inter-Silo Record-Leved Differential Privacy) Let pi(Xi, := Σÿ- 1 (ei (.s) i [N]. A randomized algorithm A is (eo, 60)-ISRL-DP for all silos and all p--adjacent Xi, X/. (X.),
(R) (X.), R46 (z,, Xi), R (Z.
(X)) R (Z X)), .M R (ZiRR11 X()),
(co.bo)
where Z, == (R, X.) and Z == (R,
X
Example clarifying the terminology used in the definition of ISRL-DP given above: Assume all M, N silos are available in every round and consider A to be the minibatch SGD) algorithm, wr+1- == w 19r.. where 9. NK Di=1 Ei= Vf(w,, x5,5) for {aī drawn randomly from X, Then the randomizers R.d) 2(r-D)NN X - 2 of silo are its stochastic gradients: KK - (Z X,) R 2 vf(w,,,), for {x] )= drawn randomly from X,, Note that the output of these randomizers depends on Wr. which is function of previous stochastic gradients of all silos Zir-- = (2 J- The aggregation mechanism outputs 9, by simply averaging the outputs of silos' randomizers: 9r N E z We view the output of A X 2 Rxx to be the transcript of all silos' communications, which in this case the collection of all x R stochastic minibatch gradients ( )e
[e[))]reeR)) Note that in practice, the algorithm A does not truly output a list of gradients, but rather outputs w E W that is some convex combination
of the iterates {w, (wr]re[R]- which themselves are functions of (7,") [N]])) However, by the post-processing property of DP (Dwork & Roth, 2014, Proposition 2.1), the privacy of Φ will be guaranteed if the silo transcripts are DP. Thus, here we simply consider the output of A to be the silo transcripts. Clearly, minibatch SGD is not ISRL-DP. To make it ISRL-DP, it would be necessary to introduce additional randomness to make sure that each silo's collection of stochastic gradients is DP, conditional on the messages and data of all other silos. For example, Noisy MB- BBD is a ISRL-DP variation of (projected) minibatch SGD.
C RELATIONSHIPS BETWEEN NOTIONS OF DP
C.1 ISRL-DP IS STRONGER THAN CDP
Assume A is (co. 60)-ISRL-DP. Let X, X' be adjacent databases in the CDP sense; i.e. there exists unique [N], j E [nI] such that æij # x'. Then for all r E [R], ( * i, X1 = Xi, so the conditional (('
distributions of (² (ZIr-1,.)) X1) and R, (0 R (Z X1) given z((²+( 2|:r-1 are identical for all (1)+1)
-1e-1 E (( Integrating both sides of this equality with respect to the joint density of Ir-- shows that (Z X1) = R (Zi.-1 X/) (unconditional equality of distributions).
Hence the full transcript of silo 7 is (unconditionally) (0. O)-CPP for all * i. A similar argument (using the inequality (3) instead of equality) shows that silo i's full transcript is unconditionally (eo, CDD- Therefore, by the basic composition theorem for DP (Dwork & Roth, 2014), the full combined transcript of all N silos is (eo, CCDP which implies that A is (eo, 6c)-CDP
Conversely, ( does not imply (e', 8')-ILDDD for any é' 0, 8 (0, 1). This is because a CDP algorithm may send non- non-private updates to the server and rely on the server to randomize, completely violating the requirement of LDP.
(Zi--1, 1e assume that R! (Z,. X,) is dependent on X, Gj i) given Z and X,; that is, the distribution of R.( is completely characterized by Zi.-- and X.. Therefore, the randomizers of i cannot "cavesdrop" on another silo's data, which aligns with the local data principle of FL. We allow for z to be empty/zero if silo i does not output anything to the server in round t.
19

---

Published as a conference paper at ICLR 2023
C.2 ISRL-DP IMPLIES USER- DP FOR SMALL (Cu, 06)
Precisely, claim that if A is (co, do) -ISRILPD then A is (ne, ()=))))=8)) user-level DP; but conversely (c, -usee--lll DP does not imply (e'.''-ISRL--D for any e' > 0, 8' (0, 1). The first part of the claim is due group privacy (see (Kamath, 2020, Theorem 10) and the argument used above in Appendix C.I to get rid of the "conditional". The second part of the claim is true because a user-level DP algorithm may send non-private updates the server and rely the server to randomize, completely violating the requirement of ISRL-DP.
Therefore, if cD (L//n) and 69 1/n, then any (co. -IR-ISR algorithm also provides strong user-level privacy guarantee.
D PROOFS AND SUPPLEMENTARY MATERIAL FOR SECTION 2
D.1 PSEUDOCODE OF NOISY MB-SGD
We present pseudocode for Noisy MB-SGD in Algorithm 2:
Algorithm 2 Noisy ISRL-DP MB-SGD
1: Input: N,d, d, N, o² > 0, X; e X for e [N], loss function f(w,, x), K [n]. (Me]re(R)
and (=r)1
2: Initialize Wy W.
13 do 4: for S, in parallel do
3: for E {0, 10.
5: Server sends global model wi to silo
6: Silo i draws K samples ri uniformly from X, (for j E [K] and noise u, NO0, ol.)
7: Silo i computes J. = K Σーー ((, + us and sends to server.
8:
end for
9: Server aggregates ğr == M. Lies Tr.
Server updates wr+1 II [w, Tr
11:
end for
Output: On
I' IR-1 Wy, where I'n = RR-1 R-1 75-
D.2 PROOF OF THEOREM 2.1
We begin by proving Theorem 2.1 for 3-smooth f(-,x) and then extend our result to the non-smooth case via Nesterov smoothing (Nesterov, 2005). We will require some preliminaries. We begin with the following definition from (Bousquet & Elisseeff, 2002):
Definition (Uniform Stability) randomized algorithm A W x N is said be a-uniformly stable (W.rt. loss function f W x X) if for any pair of adjacent data sets X, X' N XAXX < 2,
we have
sup E [f - zeA
f(A((())))))
a.
In context, N N x The following lemma, which is well known, allows easily pass from empirical risk to population loss when the algorithm in Question Is uniformly stable:
Lemma D.I. Let A: x W be a-uniformly stable w.r.t. convex loss function f : W x X R.
Let be any distribution over X and let D Then the excess population loss is upper bounded by the excess expected empirical loss plus
B(F(A(X), - FF] < a E[fx(A(X))
< min (x(w),
wEW
where the expectations are over both the randomness in A and the sampling of X ~ DN Here we denote the empirical loss by Fx(w) and the population loss by F(w, D) for additional clarity, and F win F(u F(w, D) minlew F(w).
20

---

Published as a conference paper at ICLR 2023
Proof. By Theorem 2.2 in (Hardt al., 2016),
[[F(A(X), D) - Fx(A(X)] E
Hence
B[F(A(X), D) - F*] B[F(A(X), D) (x(A(X)) + (x(x))
min Fx( min Fx(w) F+1 weW
weW
< < < wEW
min 7x (w)l:
since E Win (w) & min IE [Ex(w, min F(w, D) F*a
The next step is to bound the uniform stability of Algorithm 2.
Lemma D.2. Let f(.,z) be convex, L-Lipschitz. and B-smooth loss for all x E X. Let n == min(n) I.N 1==1 Then under Assumption 3, Noisy MB-SGD with constant stepsize 1) 3 and averaging
weights "ir nt is a-uniformly stable with respect to f for a j-stroogly convex, for all x E X, then Noisy MB-SGD with constant step size Thr = 1] & $ and
21.2 Rn If. addition f(r.x) is
nM
R is a-uniformly stable with respect to f for a I]Mn-1] (assuming any averaging weights (7rr)m
412
min(M,n) n) > 1).
Proof of Lemma D.2. The proof of the convex case extends techniques and arguments used in the proof's of (Hardt et al., 2016, Theorem 3.8), (Feldman & Vondrak, 2019, Lemma 4.3), and (Bassily et al., 2019, Lemma 3.4) to the ISRL-DP FL setting; the strongly convex bound requires additional work get tight bound. For now, fix the randomness of {Mr) Let X, X' X,X'
x be two data sets. denoted X = (X1,... .Nx) for X; E X" for all i e [M] and similarly for X', and assume XAXX| = 2. Then there is a unique a E [N] and b e [n] such that Wa, * 2 For t e {0, 1, R), denote the f-th iterates of Algorithm 2 on these two data sets by Wt = (X() and w/ = we (X') respectively. We claim that
R [1lec - wfll w
M, Josret] &
2
Σ M,
(13)
for all 6. We prove the claim by induction. It is trivially true when L = 0. Suppose (13) holds for all t & r. Denote the samples in each local mani-batch at iteration r by (e (dropping the r for brevity). Assume WLOG that S, = [M,]]. First condition on the randomness due to minibatch sampling and due the Gaussian noise, which we denote by = Nt. Eies, Ug Also, denote
1 (for L > 0) Tr == MrKK Eies, JE[K] V [f(w,, + TI and T. = M,K EVES. VV(w(, + ū. Then by the same argument used in Lemma 3.4 of (Bassily et al., 2019), we can effectively ignore the noise in our analysis of step 7 + of the algorithm since the same (conditionally non-random) update is performed on X and X", implying that the noises cancel out. More precisely, by eeeeeaaaaivveess of projection and gradient descent step for 17 B
(see Lemma 3.7 in (Hardt et al., 2016)), we have
W++1 - wh+1l
1lw (w, - -Trrrr - 11w (w's - n))
(WT --0rr) - (w'- - nHH.)l
WT 1/7 (( M,K (11)+(a))
Vs(W,, Ris) )+
Σ
+
((M
w4 nr
Σ Vf(w(, + uu
M,K
(k.))
+ M,K
Tr
VJ(Wr, (((W',
W w/[ + 4r
Vf(Wy, - Vs(w 2 2bb1)
M,K
21

---

Published as a conference paper at ICLR 2023
where 9r 10. K} is realization of the random variable Q, that counts the number of times index b occurs in worker a local minibatch at iteration т. (Recall that we sample uniformly with replacement.) Now Q. is sum of K independent Bernoulli( + random variables, hence EQ, K Then using the inductive hypothesis and taking expected value over the randomness of the Gaussian noise and the minibatch sampling proves the claim. Next, taking expectation with respect the randomness of (M)) implies
2Lt
E W0 will
nM
since the M, are i.i.d. with E mt.)) = M. Then Jensen's inequality and Lipschitz continuity of f(..)) imply that for any x E X,
[) f( fl x')] < WB WRl
L R-1
E U14 w'll
R
21 R(R 1)
L2 1)
RM
Mn
completing the proof of the convex case.
Next suppose f is p-strongly convex. The proof begins identically to the convex case. We condition on My, u, and S, as before and (keeping the same notation used there) get for any r
Wr+1 w/+1l
((17AA
1
Σ v((w) + +
Wr
1/r
(M,KK (1,))((a)))
w1 - -mr ((
Σ
V[(Wh, mis))
+ 11
M,K
(1,))((,))
Tr
(f(W,,
v((W',
M,K
We will need the following tighter estimate of the non-expansiveness of the gradient updates to bound the first term the right-han hand side of the inequality above:
Lemma D.3. (Hardt et al.. 2016) Let G : W - Rd be u-strongly convex and 9-smooth. Assume
2_ 7 & D4u Then for any w. v W, we have
[( - (wwnDGG(w) - (u (MV
1
B 11 ) 10- fo-wl w/ < (1 7 |/u w||.
n1
Note that Gr Gr(w)) = M.K E(..) 9r
f(wr, 25,) is (1 M.K 8 -mooth and (1 M, K )-sttonnyy convex and hence so is (w,,, + u. Therefore, invoking Lemma D.3 and the
assumption = 17 & 3: as well as Lipschitzness of ((=x))Ve X, yields
|w,+1 - w/+1// <
1- nu(
M.K
4r |we, - w/'l +
2g.nL
M,K
Next, taking expectations over the M, (with mean EE E(H+)) # the minibatch sampling (recall K ) and the Gaussian noise implies
Eq.- no
17/(1
2
Wr+1 W,r1--w - w/+al <
naa
ElIl,, w/ll +
2
M
One can then prove the following claim by an inductive argument very similar to the one used the proof of the convex part of Lemma D.2: for all t 2 O,
2 n.M Σ (1 b)",
E W2 - will &
r-0
22

---

Published as a conference paper at ICLR 2023
where b == en 2
2g 1o.M-1 ng Ad
1. The above claim implics that
2
(1 (1-
b) b)(-1
Ellu, - w//1 $
na
b
4L
u( M - 1)
4L
MMnMM 11
Finally, using the above bound together with Lipschitz continuity of f and Jensen's 's inequality, we obtain that for any z X,
E E[f(ūR.2) - f(w// z)]
LE T'yll
WR
R-1
1
LI
Yr [w+ w/x)
I'R 0
R-1
1
LE
7r. 7-11u, - w'll
-w'll
R -=
L
1 R-1
Σ 7r
(m(nM (M
4L
T P=0
4L2
u(nM 1)
This completes the proof of Lemma D.2.
Next, we will bound the empirical loss of Noisy MB-SGD (Algorithm 2). We will need the following two lemmas for the proof of Lemma D.6 (and hence Theorem 2.1):
Lemma D.4. (Projection lemma) Let W < Rdd be a closed convex set. Then (T) -bl & ||a (la-by bl2
for any a Rdd b. Rd.be W.
Lemma D.5. (Stich, 2019) Let b > O, let a, i= O, and (ne)rso be non-negative step-sizes such
that < 1 for all t 3 0 for some parameter g Bo a. Let (rihes and {sttas be two non-negative sequences of real numbers which satisfy
T+41 & (1 anjrr lm:tt + enf
for all t > 0. Then there exist particular choices of step-sizes The g such that
& and averaging weights V 0
b
Σ sh arr+1 = (oro exp (-ar)+ oT
FT t=
where Tr = Σt= Yt- In fact, we can choose vi and Tt as follows:
1)2 = min { In (max {2, (2.a2roT2/c)) /c})
jo = (1- (1- ((++1)
aT
We give the excess empirical risk guarantee of ISRL-DP MB-SGD below: Lemma D.6. Let f W x X - R be p-strongly convex (with μ 0 foror convex case), L-Lipschitz, and 3-smooth in w for all x E X, where W is a closed convex set in Rd s.t. || - w'll & D for
all w, w' E W. Let X X. Then Noisy MB-SGD (Algorithm 2) with o² 2561. R In( 2:23 (n(2/8))
n=eg
attains the following empirical loss bounds as a function of step size and the number of rounds: 1. (Convex) For any 1/3 and R E N. = 1/R, we have
(@x / <
D2
?L?
256dR In
In (2/80) 2.5R
80
+ +1)
+1)
2n
2
Mn
23

---

Published as a conference paper at ICLR 2023
2. (Strongly Convex) There exists constant stepsize "r n o 1/B such that if R. > ( then Ltd
2x In
Px Ö (
L2 ddIn(1/00) /
1 R
EP (wR)
(14)
Megn²
Proof. First, condition on the random M, and consider M, as fixed. Let w* E argmin ix (x(w) be any minimizer of F'x. and denote the average of the i.id. Gaussian noises across all silos one round by n. = Mr
1 Liss, U4. Note that ūt N 0, Nr. Ia) by independence of the [us]ee and
hence E 12,11 do² M.
Then for any r 2 0, conditional on M,, we have that
E
Wr++1 w "0' Mr
V f( Wy,, xT.j)) u.)
E
IIw
Wr 177
-u
~
M,
Mr
iES,
1
<B
7/r
M
K
[W,, xو, -ui
-w*
Mr
iESt
E
Mr
V Fx) + Try u/ --=--)
Mr
2
+ E
Ur + 1
Σ
1
V Vf(Wr: 2T,
Mr
M,
K
iES,
j-1
W,y - w* w02
Mr
21,, LEI Fx (w)) - PXIMA
K
ʃ (Wey o.t 12
+ E
Üh + M, S
Mr
K
j=1
ddo2 M, + 12
< - 1.
|w,, - w* 1
M,
2n, [[
(x((((,) (w,) - PRIMJ + Th
(15)
where we used Lemma D.4 in the first inequality, ju-strong convexity of F (for μ > 0) and the fact that ū, is independent of the gradient estimate and mean zero in the next inequality, and the fact that [(, .)) is L-Lipschitz all æ in the last inequality (together with independence of the noise and data again). Now we consider the convex (μ 0) and strongly convex (μ >> 0) cases separately.
Convex (μ 0) case: Re-arranging (15), get
do
E (w, - P - < 2nr
[E]] W. w 2
|| =0112) +
+ I²
2 Mr
and hence
[R[[ uc wº 21 || ==+ + 7r do²
(wx,) - - & 2n,
M + 1??
2
24

---

Published as a conference paper at ICLR 2023
by taking total expectation and using B|1/M,] 1/M. Then for nr 17, the average iterate wa satisfies:
(R) - F*1
Px (w,))= - [*1
R
R-1
Σ
[E[ [[[l,, -0112-1100++1 - w= 11)
R
2n
1=
+
7/
do
+ I??
2
M
WWb
w* 12
!/r
( do²
L2²
+
nR
2
M
Plugging in o² finishes the proof of the convex case.
Strongly convex (μr > 0) case: Recall from (15) that
B| W - u u=*1]]] & (1 - 10) wi - == - P (x:))) PX1
do
+ v/
M + 1
(16)
for all (upon taking expectation over M,). Now, (16) satisfies the conditions for Lemma D.5, with sequences
E We
"0I 11 St ==[Fx(())) F*1
and parameters
do
a = μ4, = 2, c
+ L2 g = -223, T R.
M
Then Lemma D.5 and Jensen's inequality imply
( F Ō BBD
R
I
d
exp
2k
R
Megn²
Finally, plugging R and d² completes the proof.
We prepared to prove Theorem 2.1 in the B-smooth case: Theorem D.1. Let f(w, x) be 8-smooth in for all x E X. Assume co & 2 22l62/))), choose o² 2561 Rln 2.30 (n(2/5)) and K (2/21102/660) Then Algorithm (co, 50) -IRII-PP. Moreover,
there are choices of RR, such that Algorithm 2 achieves the following excess loss bounds: n,, c.
1. If f(-x2) is convex, then setting H BDVM min
|
n,
Fam Vd
+ min
yields
LD
dln(1166))
EF( F F* δ
+
(17)
VM
vn
cun
2. If z()x)) is p-stroongy convex, then setting R = max yields
28
In
BD uMeRa? dT.
min Mn, Mcãn
EF(@R)-F*= - === I?2
dlIn(1/5)) enn
(18)
HM
Proof. Privacy: By independence of the Gaussian noise across silos, it suffices to show that transcript of silo i's interactions with the server is DP for all [N] (conditional on the tran- scripts of all other silos). WLOG consider orem 3.20 in (Dwork & Roth, 2014)), it suffices to show that each of the R rounds of the algo- rithm is (ē, -I-SLL-D where غ 2v2211(2/85) (we used the assumption < In(2/6)) here)
1. By the advanced composition theorem (The-
and 5
2R First, condition the randomness due to local sampling of the local data point
25

---

Published as a conference paper at ICLR 2023
'f.1 (line 4 of Algorithm 2). Now, the L2 sensitivity of each local step of SGD is bounded by := Ax] wew ll l ト ff(,,,I1.) (f((,111,)) < 2 K, by L-Lipschitzness of f. Thus, the standard privacy guarantee of the Gaussian mechanism (see (Dwork & Roth, 2014, The- orem A.1)) implies that (conditional on the randomness due to sampling) taking of SL 12/1,222 (5,/ 2²K²
suffices ensure that round (in isolation) (c, -I-RLDDD Now invoke the randomness due to sampling: (Ullman, 2017) implies that round r (in isolation) 2EK 8)-ISRL-DP. The assump- tion on K ensures that c' 2K 2 (2266))
1, so that the privacy guarantees of the Gaussian
mechanism and amplification by subsampling stated above indeed hold. Therefore, with sampling, 2561.' ft (2.5//66))) in(2/6n) ensure that round (in isolation) nºeg
suffices to take o² 321. (m(1,25/8)
is (E, ISSLLDD for all and hence that the full algorithm (R rounds) is (tu, 6o)--SLLDPP.
Excess loss: 1. First suppose f is merely convex (u 0). By Lemma D.2, Lemma D.I, and Lemma D.6, we have:
EF(wR) F & a + ((R) Fx
2L
D²
256dR In( 2.5Rt
ln(2/60)
+
+
nM
2n
2M
n=
for any 1 & 1/3. Choosing 7) min
D
min {I,
M Rddd
aM
implies
33
LVR
π
3Da
LD
/dR R/60)
R
EF(@n) F*
VR
EGTV
M
n.M
Finally, verifies that the prescribed choice of R yields (17).
Now suppose f is j--stroglyy convex. Then for the & 1/3 used in the proof Lemma D.6 and In
R >
29
3D 2
we have
dL
(RR) ( P = Ō
E
L2 6
1
d(l((1/p))
Megne
+
R
1
Mn
by Lemma D.6, Lemma D.2, and Lemma D.I. Hence (18) follows by our choice of R >>
min MMn Meina
We use Theorem D.I to prove Theorem 2.1 via Nesterov smoothing (Nesterov, 2005). similar to how (Bassily et al., 2019) proceeded for CDP SCO with non-strongly convex loss and N 1. That is, for non-smooth f. we run ISRL-DP Noisy MB-SGD on the smoothed objective (a.k.a. 3-Moreau envelope) fa(w) := mingew (f(v) + [ --|w== =l?). where 3 > 0 is a design parameter that we will optimize for. The following key lemma allows to easily extend Theorem D.I to non-smooth Lemma D.7 (Nesterov (2005)). Let f W - TRd be convex and T.-Lipschitz and let B3 > 0. Then the 3-Moreau envelope fø(w) == min.ew (f(u) fll o1p) satisfies:
1. fa is convex, 2L-Lipschitz, and 8-smooth.
Vw, fo(w) & f(w & fø(w) + 23
Now let us re-state the precise version of Theorem 2.1 before providing its proof:
Theorem D.2 (Precise version of Theorem 2.1). Let en & 2l and choose o²
2 2,28) lu(2/60)
K 4 222R1112)660 Then Algorithm 2 is (co. 50)-LPD Fur- > such that running Algorithm on fo(w,x)
n²cg ther, there exist choices of
mingew (f(,,)) u12)
yields:
1. If f(,,2) is convex. then setting R
BD M L
min (Vn, Eall + min { n,M d
?
yields
LD
d dln(11/0))
EF(ØR) F+=
+
(19)
VM
eg7
26

---

Published as a conference paper at ICLR 2023
If f()))) a)) is p-strongly convex, then setting R max yields
28
BDD2 pM
minn { Mdn Mrgn"
})
aL?
L J.M
dll(11/o))
BF(wR) - F* =Ō ===
(20)
Enn
Proof. Privacy: ISRL-DP is immediate from post- post-processing (Dwork & Roth, 2014, Proposition
2.1), since we already showed that Algorithm (applied to f3) is ISRL-DP.
Excess risk: We have (F)(w) F* & (F F3 + 2
L2
by part 2 of Lemma D.7. Moreover,
by part 1 of Lemma D.7 and Theorem D.I, have:
1. (F)(@R) - F3 Ô
LD
1
+
M
n2
En7
for convex f, and
L
dlm(1/58))
2. (FF((R) F3 Ö
J.M
enn²
for j-sttrnglyy convex f. Thus, choosing 31 such that L2/32
LD
vn +
and
B2
VM
con
such that 12/322 & and (1 +
1.2
dll(1/60) =in"
completes the proof.
D.3 LOWER BOUNDS FOR ISRL-DP FL: SUPPLEMENTAL MATERIAL AND PROOFS
This section requires familiarity with the notation introduced in the rigorous definition of ISRL-DP in Appendix B.
D.3.1 C-COMPOSITIONALITY
The (4o. 4o)-ISLL-DP algorithm class A((orbu).C contains all sequentially interactive and fully inter- active, C-compositional algorithms.
Definition 7 (Compositionality). Let be an R-round (co, 8o)-ISRL-DP algorithm with data domain X. Let {(Eg, 6,) denote the minimal (non-negative) parameters of the local randomizers R( selected at round r such that R! (Z(r--1)s')) is (c6, - for all [N] and all Z
For C O, we say that A is C-compositional if / Eree(R (c))2 & Ceo. If such is an absolute constant, we simply say A is compositional.
Definition 7 is an extension of the definition in Joseph et al. (2019) to 8 > O.
D.3.2 ALGORITHMS WHOSE PRIVACY FOLLOWS FROM ADVANCED COMPOSITION THEOREM ARE I-COMPOSITIONAL
Suppose is (Eo, 6o)-ISLLDPP by the advanced composition theorem (Dwork & Roth, 2014, Theo- rem 3.20). Then
R (6)) (1/8))
c0
2
Σ (6 1),
and 80 Σ 8% + 8' for any 8' e 1). Assume 8' (0, 1/3) without loss of generality: otherwise the privacy guarantee A essentially meaningless (see Remark D. Then 6o > 2222"" (= In(1/8") e v2 // > (E)), so that A is 1-compositional. Note that even if 8' > 1/3, A would still be compositional, but the constant may be larger than
27

---

Published as a conference paper at ICLR 2023
D.3.3 EXAMPLE OF LDP ALGORITHM THAT NOT COMPOSITIONAL
This example is simple modification of Example 2.2 in (Joseph al., 2019) (adapted to our definition of compositionality for dg 0). Given any C > O, set d := 2Ct and let X [er,... ea) = 1) be the standard basis for R Let n = and X = (21, (- ,NN) E X For all i E [N] let ...
Q+); : X - X' be the randomized response mechanism that outputs (x.) = H with probability e'u
eoo+d-1 and otherwise outputs a uniformly random element of X [ Note that Q is cn hence (Eo, -DP for any do 0. Consider the d-round algorithm A X zax in Algorithm 3, where
Algorithm 3 LDP Algorithm that is not C-compositional
1:
for r [d] do
2: for N do
3: if dy e, then
4:
(x,))) = (x:).
R2 (z:)
5:
else
6:
R2
(x:) (x:) == 0 Rd.
7: end if
8:
end for
9:
end for
10: Output: (R re[])
Since each silo's data is only referenced once and @(+) co-DP, we have o = cn and A is (co, 6o)-DP.
However, V (E))² de /2C Ceo. that A is not C-coopositionall.
Also, note that our One-Pass Accelerated Noisy MB-SGD is only C-compositional for C' v R. since 6g c for this algorithm. Thus, substituting the R that is used to prove the upper bounds in Theorem 3.1 (see Appendix E.2) and plugging C /R into Theorem 2.2 explains where the non-i.i.d. lower bounds in Fig. 3 come from.
D.3.4 PROOF OF THEOREM 2.2
First, let us state the complete, formal version of Theorem 2.2, which uses notation from Appendix B:
Theorem D.3 (Complete Version of Theorem 2.2). Let co e (0, VN), 80 o(1 ((/nNN), and A Co)... Suppose that in each round r, the local randomizers are all (c6 DD) for 6 $ 3, & = o(1/nNN), R), ,, N > 16 (n(2//))) Then:
There exists f E FL,D and a distribution such that for X ~ DDNN we have:
EF(A(X)) - F =²=
ΦD VNn
+ LDmin
2. There exists p-smooth f E &G,LIDD and distribution D such that for X ~ D'N we have
EF(A(X)) - F* = (
JnN + -DDmin { d
<2n=NC4 1)
Further, A E &, then the above lower bounds hold with C = 1.
Before we proceed to the proof of Theorem 2.2, we recall the simpler characterization of ISRL-DP for sequentially interactive algorithms. A sequentially interactive algorithm A with randomizers N Ji-1 is (Eo, -oR-ISR if and only if for all [N]. (.) (., (1=-1)) X7 Z is
(co, DDP for all (1=-11) zi-1, In what follows, we will fix X, X' for all i. We now turn to the proof.
Step 1: Privacy amplification by shuffling. We begin by stating and proving the amplification by shuffling result that we will leverage obtain Theorem 2.2:
28

---

Published as a conference paper at ICLR 2023
Theorem D.4. Let A E Bo), such that cu E (0, vN] and do (0, Assume that in each round, the local randomizers RT (Z (Z(::-11):)) x - 2 are (cg- (6)-DP for all i E [M] [R): (1r-11 2"-1xN with Cp & Assume N 161n(2/8 If is C-compositional, then assume % & I4nNR and denote ò == 14Nn Er-1 % if instead A is sequentially interactive, then assume 6g- % & TNn and denote == 7Nn Let A, X W be the same algorithm as A
1
except that in each round T, A, draws random permutation Tr [f] and applies R(") to (x)
In( 6 C and 60tn == [[]] 6-
instead of X, Then, A, is (c, (),PP where O
VN
co (n1n/(/nN6 VN
In particular, if A A, then O 8gsin -oo-
Note that for sequentially interactive A.
To the best of our knowledge, the restriction on cj needed to obtain c= Ö(eo/V / in all works that have analyzed privacy amplification by shuffling (Erlingsson et al., 2020b; Feldman et al., 2020b; Balle al., 2019; Cheu al., 2019; Balle et al., 2020), but these works focus on the sequentially interactive case with n = 1, so the restriction amounts to cu & 1 (or cu = Ö(1). The non-sequential C-compositional part of Theorem D.4 will follow as corollary (Corollary D.1 ) of the following result which analyzes the privacy amplification in each round:
Theorem D.5 (Single round privacy amplification by shuffling). Let Ej & 16
/n, TEN
and let R (Z.-) : Xm
be an (6..%) DDD local randomizer for all Z Z(1:N) E ((r-1)xN
(1:r-1)
and i E [N], where X is an arbitrary set. Given a distributed data set X = (X1, .Nn)
X xn and Z (1:7>) consider the shuffled algorithu A₁, X (rr-1)xN zN that
first samples a random permutation x of [N] and then computes Zr = (Z (1) I( where 7 R (Z, x()) Then, A₁, is (E, (')DD.CDP, where
1) c
e e In(4/or)
Se
: 1+
(21)
VN
and 8- 5" + 2N nn In particular, i
O (+))
then
= e Im(1/8r)
(22)
V/V
Further, i & 1/n, then setting 8 = Nnól implies that
Cov (ovIm(1/nN6))) VN
(23)
and & & 7Nng which is in (0, 1) if we assume 6% E (0, 1.
We sometimes refer to the algorithm A² as the "shuffled algorithm derived from the randomizers ( From Theorem D.5, we obtain:
Corollary D.1 (R-round privacy amplification for C-compositional algorithms). Let A XIXN
zRXN be an R-round (eo, 6o)-ISRL-DP and C-compasitional algorithm such that Eo E (0, V and do =0,1), where X is an arbitrary set. Assume that in each round, the local randomizers R! (Z(::-1))) : x + are (Et, -DP for E [N], r E [R], where N ? 16 ln <o & d. and 8% & TAnNN Then, the shuffled algorithm A, XuxN - ZRXN derived from (R.)) ().3=,)))BeMMM.ett (i.e. Ag is the composition of the shuffled algorithms A defined in Theorem D.5) is (c, OCDP, where 8 & 14Nn 2R 8% and c O co In 1/n )
where
VN
<a so (0/11//Naiia
ggmin : min 8- In particular, if A E A. is compositional, then e = O
VN
29

---

Published as a conference paper at ICLR 2023
Proof. Let 8' := Σr Nnog and 8" == Nnóg. Then the (central) privacy loss of the full R-round
shuffled algorithm is bounded as
2 Σ (6)) 2 (Er)2
In(1/8))
(c
(c5)2ln(1/07)
(1)21((10") In(1/8))
Σ
0
+
N
N
=0 In(1/n(
VN
where the three (in)equalities follow in order from the Advanced Composition Theorem (Dwork & Roth, 2014), (23) in Theorem D.5, and C-compositionality of A combined with the assumption ED VN. Also, 8 8' E, 8" by the Advanced Composition Theorem, where d, & 7N by Theorem D.5. Hence & 14Nn Σ, %. In particular, if A is compositional, then C = O(1), so
60 In 10
-
VN
Remark D.1. The upper bounds assumed on &G and 8 in Theorem 2.2 ensure that d E (0, 1) and that the lower bounds of (Bassily et al., 2014) apply (see Theorem D.6). These assumptions are not very restrictive in practice, since 8h 8g < 1/n is needed for meaningful privacy guarantees (see e.g- Chapter 2 in (Dwork & Roth, 2014)) and R must be polynomial for the algorithm to run. To quote (Dwork& & Roth, 2014), "typically we are interested in values of 8 that are less than the inverse of any polynomial in the size of the database" (page 18). For larger 5 (e.g. 5 (1(/n)), there are examples of algorithms that satisfy the definition of DP but clearly violate any reasonable notion of privacy. For instance, an algorithm that outputs dgn random samples from each silo's 's data set is (0, DPS--DDD but completely violates the privacy of at least one person in each silo if do 2 1/n. Also, since N is the regime of interest (otherwise if N Ö(1), the CDP lower bounds of (Bassily et al., 2019) already match our upper bounds up to logarithms), the requirement that N be larger than 16 In(2 (2//8mmin))
n) is unimportant.
The sequentially interactive part of Theorem D.4 will be clear directly from the proof of Theorem D.5. We now turn to the proof of Theorem D.5, which uses the techniques from (Feldman et al., 2020b). First, we'll need some more notation. The privacy relation in (3) between random variables P and Q can be characterized by the hockey-stick divergence:
== m0 p(x) e e<v( where p and y denote the probability density or mass functions of P and Q respectively. Then (Q) & 5. Second, recall the total variation distance between
P
Q iff
(e,8)
P and Q is given by TV,P,Q) = & (p(x) - q(x))dx. Third, we recall the notion of group privacy:
group Definition 8 (Group DP). A randomized algorithi A: X. - Z is (c,5) group DP for groups of size N if A(X)
A(X)) for all X,X' X' N.N.
(r,5)
We'll also need the following stronger version of a decomposition from (Kairouz et al., 2015) and Lemma 3.2 of (Murtagh & Vadhan, 2016).
Lemma D.8 (Kairoouz et al., 2015)). Let Ro. R1 : : + Z be local randomizers such that (X)) and R₂ (X1) are (c, 0) indistinguishable. Then, there exists randomized algorithm U {Xo, X1} Z such that Rx(X)) c' U(x)) + -4,U(X)) and R₁ (X1) - + c' U(x))
Lemma D.8 follows from the proof of Lemma 3.2 in (Murtagh & Vadhan, 2016), noting that the weaker hypothesis assumed in Lemma D.8 sufficient for all steps to go through.
Definition 9 (Deletion Group DP). Algorithm R : X Z is (e, 8) deletion group DP for groups of size n if there exists a reference distribution such that R(x) ~ for all X E X".
(e.8)
It's easy to show that if R is (c, dedeletoo group DP for groups of size n, then R is (2c, (1 + c)) group DP for groups of size In addition, have the following result:
Peehhniallyy, this assumption on N is needed to ensure that the condition on e in Theorem D.5 is satisfied. similar restriction appears in Theorem 3.8 of (Feldman al., 2020b).
30

---

Published as a conference paper at ICLR 2023
Lemma D.9. Let Xu X" If R x 2 is (c, local randomizer, then R is (ne, (n((-))r8) deletion group DP for groups of size with reference distribution R(Xo) (i.e. R(X) R(Xo) for all X E X", where č ne and ne(n-1)6
(2,8)
Proof. By group privacy (see e.g. Theorem 10 (Kamath, 2020)), and the assumption that R is (c, 8)-DP, follows that R(X) and (X')) are (ne, ne(n-1)e8) indistngguishable for all X, X' x In particular, taking X' == Xo completes the proof.
Lemma D.10. Let R() X - be randomized algorithms (i [N] and let A, : X - ZN be the shuffled algorithm A,(X) : (Rx))())))); (X
derived from (R(N) HEINT
for X = (X1,... .N),, where π is a uniformly random permutation of [N]. Let Xo = (X1, X2, ... .N) and X1 = ".. .N),, ô (0,1) and p E 166m((/6) ,11. Suppose that for all i [M], X xm (X7, X1), there exists a distribution LO (X) such that
(x) = (x)) + 2 R (1 (1-
Then Axoo)) (e,5)
1 where
8 8/i((400) (1 1+
8 PN
< In
vpN
Proof. The proof mirrors the proof of Lemma 3.3 (Feldman et al., 2020b) closely, replacing their notation with ours. Observe that the DP assumption in Lemma 3.3 of (Feldman et al., 2020b) is not actually needed the proof.
Lemma D.11. Let R X - 2 be (c, deletion group DP for groups of size with reference distribution p. Then there exists a randomizer R' X" Z such that: (i) R' is (e, 0) deletion group DP for groups of size with reference distribution pł and (ii) (RX,).. R' (X)) & 6.
In particular, R' is (2c, 0) group DP for groups of size (by (i)).
Proof. The proof is nearly identical to the proof Lemma 3.7 in (Feldman et al., 2020b).
We also need the following stronger version of Lemma 3.7 from (Feldman et al., 2020b):
Lemma D.12. IfP( (ro.da) R(X}), then there exists randomizer R' x Z such that
R'(X)) (fo.0)
R(X9) and (V ((X))) & 60.
Proof. The proof follows the same techniques as Lemma 3.7 in (Feldman al., 2020b), noting that the weaker hypothesis in Lemma D.12 is sufficient for all the steps to go through and that the assumption of in (Feldman et al., 2020b) is not needed in the proof.
Lemma D.13 (Dwork & Roth, 2014), Lemma 3.17). Given random variables P, P.Q, P' and Q', if De'(P', Q') 6, TV,P, P') 8', and (Q, Q') & 8', then D (P,() d (et + 1)8'.
Lemma D.14 ((Feldman et al., 2020b), Lemma 2.3). Let and Q be distributions satisfying P (1 Po qPr and Q (1 Po 9Q1 for some q [0, 1}. Then for any 0, if cl + q(e - 1)), then
Der (PllQ) & g
Das (Pi11Q:)) (P.()))))))
We ready prove Theorem D.5:
31

---

Published as a conference paper at ICLR 2023
Proof of Theorem D.5. Let Xg. X, x=* be adjacent (in the CDP sense) distributed data sets (i.e.
[X,XX1] < 1). Assume WLOG that X, = (Xf. X2. .N) and X = (X), Xx...... .x), where X (Z1,0, 21,2."" ni,,n) # (Z1,1: 11,,1,21,2," 1.,.).
We can also assume WLOG that X, $ {X1, } for all j 12,-.,, by re-defining X' and R. if necessary.
Fix E [N E [R].Z Z- Zir-- Z E -("-1)xN, denote R(X) == R (Z. X) for X E X", and Ax(X) == (Z X). Draw π uniformly from the set of permutations of [N]. Now, since is (co, doD- R(x1) R(X)), so by Lemma D.12, there exists local (g).%)
randomizer R' such that R'(x R(XI) and TV (X),, & 6-- (5,.0)
Hence, by Lemma D.8, there exist distributions U(X)) and (x})) such that
e
R(x9) et +1
U(XT) + e +1 U(}))
(24)
and
e6
Rx
U(X9) +
e +1 +1 U(})).
(25)
e +
Denote Eo ==ne]] and ho = ne(n-1)655 By convexity of hockey-stick divergence and the hypothesis 2 R(X)), R(X)) for all X by Lemma D.9), we have
that R is (ch,6) DDP (hence R(X)
(60,50)
R(X) ((((X)) + R(X))) = for all X E X². That is, is (Fo, 50) deletion group DP for (g)
groups of size with reference distribution p. Thus, Lemma D.11 implies that there exists local randomizer R" such that (X) and p are (E..0) 0) indistinguishable and TV(R" R(X)) & 80 for all X. Then by the definition of (Fo, 0) indistinguishabiiity, for all X there exists a "left-over" distribution (X) such that R"(X) e9o + (1 - (LO(X)
1 (R(X)) + R(X +
20
(1 11/e))LO(3
Now, define a randomizer & by L(X :- R(X,), ((x+) =- Rx))) and
1
1
((X):
R(X
+
R'(
+ - 1/-
2e
2c
1
(X
+ -
+ (1 - )
(26)
26
20
for all X E X= (The equality follows from (24) and (25).)
Note
that (F((())),
0. TV(((X)). (({))
& and for all X
XTM (NP, X]), ((X) & TV(R(X),R" Rx))) + (X) 2ō0.
& 50 +
(X)) (n) 1)65 + 2,t 0o & (m)e())))6b)
26
Keeping r fixed (omitting scripts everywhere), for any i E [N] and Z : Zi.r-1 E 1)x- let (Z.-). ( (Z, -), and LO (Z, -) denote the randomizers resulting from the process described zd be defined exactly the same way as A
A, (same x) but with the randomizers R(0) replaced by ((,), Since A, applies each randomizer R()) exactly once and R(1) (Z, X (Z, X ( independent (conditional on Z Zi.-1) 14, we have (V, (c(X)) & (2 1 and (A, ), (X, & (2 1)- 188))8 (see (Den Hollander, 2012)). Now we claim that Ax(Xo) and Ac (X(, 1) are (c") indistinguishable for any 8" > 2e -Ne 118 Observe that this claim implies that AXo)) and Ax 1) are (t",3t) indistinguishable by Lemma 1.13 (with P Ac(Xo), == Ac(Xi),
above. Let Ac : X
A. (Xo), := A. ()) Therefore. it remains to prove the claim, i.e. to show that D (X)( A (X)) & 8 for any 8" -eeNe Ne "65/16
"This follows from the assumption given in the lead up to Definition 5 that (Z X) is conditionally independent of X' given Zu:r-1 for all Zi:r-1 and X # X'.
32

---

Published as a conference paper at ICLR 2023
(Z,
if = X if = X] otherwise.
Now, define C/ X)
=
( X
For any inputs Z, X, let (z, be
[ Z X)
defined exactly the same A, (, X) (same π) but with the randomizers R(o replaced by L Then by (24) and (25),
e
e
Ac(Xo)
Au (Xn)
Au (X1). c + 5 + Au and Ac(Xi) e% + Au (Xo)+
c +
(27)
Then by (26), for any X E Xm (xP. x and any Z Zirr1 E Z(r-1)xN, we have 2/ (Z, =
2 ((1 (, X + _ (5)
20th (z, x+) + E - ) (Z, X). Hence, Lemma D.10 (with p
20 e n implies that Ar (Xo) and (x (x)) are
log 1+ 8 6t0 In (1(48r)
86
,
VN
N
indistinguishable for any 8" > 2e -e-Ne- Applying Lemma D.14 with P :- Ac(Xo). Q
Q1 (x( and Po }/(P Qi) and convexity of the hockey-stick divergence yields that Ax(Xo) and Ac(X1) are (c", 5")) indistinguishable, as desired. This proves the claim and hence (by Lemma D.13, as described earlier) the theorem.
Ac(Xi), e'6-1 e Pi
Remark D.2. Notice that if A is sequentially interactive, then the proof of Theorem D). above almost immediately implies the sequentially interactive part of Theorem D.4. Essentially, just change notation: replace Z - by ((;--), the collection of (single) reports sent by the first i silos; note that E eo. % = ōo; and view the N reports as being sent in order instead of simultaneously. into the proof of Theorem 3.8 in (Feldman al., 2020b), which is for sequentially interactive algorithms.
Alternatively, plug our techniques for
Step 2: Combine Theorem D.4 with the following CDP SCO lower bounds which follow from (Bassily et al.. 2014; 2019) and the non-private SCO lower bounds (Nemirovskii & Yudin, 1983; Agarwal al., 2012):
Theorem D.6. (Bassily et al., 2019; 2014) Let μ. D, 0, L nD, and 8 o(1/NN). Consider D D
X = 1= 1 72l c Rd and W = B2 Rd. Let A: XUN - W be any (e, 8)DD)
algorithm. Then:
There exists a (p = 0) convex, linear (8-smooth for any B), L-Lipschitz loss f W x X - R and distribution D on X such that if X Dnn then the expected excess loss of A is lower bounded as
EF(A(X)) F* =
@ LD min VNn
Vd
1)
EnN
For L R μD, there exists a j-sstrongyy convex and smooth, L-Lipschitz loss f: W x X distribution D on X such that i DnNN then the expected excess loss of A is lower bounded as
R and
EF(A(()) F* क
0²
L
min {1,
JNN
For general L,P, D, the above strongly convex lower bound holds with the factor 12 replaced by LD.
Namely, if A is (eo, -IR-LDDD then (under the hypotheses of Theorem 2.2) A, is (e, CDDP for e Ö(ea/ /N), so Theorem D.6 implies that the excess loss of A, is lower bounded as in Theorem D.6 with replaced by so/ VN.
Step 3: We simply observe that when the expectation is taken over the randomness in sampling X DaxN the expected excess population loss of A, is identical to that of A since X, and X Xm(g) have the same distribution for i, π by the i.i.d. assumption. This completes the proof of Theorem 2.2.
33

---

Published as a conference paper at ICLR 2023
D.3.5 TIGHT EXCESS RISK BOUNDS FOR CROSS- DEVSICE FL WITHOUT A TRUSTED SERVER
We explain how our ISRL-DP excess risk bounds also imply tight excess risk bounds for algorithms that satisfy both ISRL-DP and user-level DP simaltaneously, which may be desirable for cross-device FL without a trusted server. Assume M = for simplicity and consider i.i.d. FL concreteness. 15 Given (c.6) 6) with e & 1, let eo e/n, 6g 6/4n $ 66(ne((=1)eo) = 6/ (f(ne(nn-))enn) and run Noisy (ISRL-DP) MB-SGD with noise calibrated to (<a, 6o). Then the algorithm also satisfies (c. -user level DP by Appendix C. Thus, by Theorem 2.1, we obtain hybrid BRRL-DP/user-eeel DP excess risk upper bounds. For example, in the convex case, we get
Vd1n(1/6u) EOTVNN
BF (p)) F =
LD
VNn
Vdln(n/0)
1
LD
CVN
VNn
V dln(n/o)
LD
(28)
CVN
Regarding lower bounds: note that the semantics of the hybrid ISRL-DPPuser-level DP notion are essentially identical to LDP, except that individual "records/items" are now thought of as datasets of size n. Thus, letting n = our ISRL-DP lower bounds (we think of each silo as having just one "record" even though that record is really dataset) yields lower bounds matching (up to logarithms) the upper bounds attained above. For example, putting n = 1 in the convex lower bound in Theorem 2.2 yields bound that matches (28), establishing the optimal FL rates (up to logarithmic factors) for this algorithm class. Note that the minimax risk bounds for ISRL-DP/user-leve DP hybrid algorithms resemble the bounds for LDP algorithms (Duchi et al., 2013), scaling with but not with n.
E PROOFS AND SUPPLEMENTAL MATERIAL FOR SECTION
E. MUTLI-STAGE IMPLEMENTATION OF ACCELERATED NOISY MB-SGD
Here we describe the multi-stage implementation of Accelerated Noisy MB-SGD that will use to further expedite convergence for strongly convex loss, which builds on (Ghadimi & Lan, 2013). As before, for SCO, silos sample locally without replacement in each round and set R |n/ K). Whereas for ERM, silos sample locally with replacement.
Multi-stage implementation of Algorithm 1: Inputs: U [R] such that ΣV Re R for R defined below; We W, A & F(wo)= - F*, V > O, and go 0.
For e [U] do the following:
1. Run RS rounds of Algorithm 1 using u/ I4-1, 1. (a,)aa and (nr bras where
28
128V
RR
max 4
1
r 1 = 4uk.
2
0r
r(r + 1)²
4V2
1/2
Us = max 2,,
3A2 (k- (k- + 1) R4 2)
2. Set Qk to Step 1.
ag WR. where wi, is the output of Step above. Then update i 1 and return
It's easy to see that the same arguments we use in this subsection for i.i.d. SCO can also be used to establish tight federated ERM bounds.
34

---

Published as a conference paper at ICLR 2023
E.2 COMPLETE VERSION AND PROOF OF THEOREM 3.1
We will state and prove the theorem for general M E [N] under Assumption 3. We first require some additional notation: Define the heterogeneity parameter
22
sup we'V
Σ [V(()-
(29)
which has appeared in (Khaled et al., 2019; Koloskova et al., 2020; Karimireddy al., 2020; Woodworth et al., 2020b). v² = 0 iff F, = F + a, for constants a; E R, i [M] ("homogeneous up transaltion").
Theorem E.1 (Complete version of Theorem 3.1). Let f(., be B-smooth for all E X. Assume co & (1 6n 10 Then, with o² 32L 25/662)/6a) One-Pass Accelerated Noisy MB-SGD is (Eo, 60) fo)-IRRL-DP DP. Moreover, there are choices of stepsize, batch size, and X > 0 such that
<gK²
Running One-Pore Accelerated Noisy MB-SGD on f(w. x) f(w, x) + 2 2|w wol 1 (where wo W) yields
2
EF ( F* ===
ΦD VnM
LD
(1/60))0))
N N (N=1)
VG 4/4/ Vddln(1/60)
CoRV M
g//3
conM'
(30)
If f(-,2) is j--ttrongly convex Vx E and k n¹' of One-OnePe Paee Accelerated Noisy MB-SGD directly on fyields with batch size K yields
2. then running the Multi-Stage Implementation
EF(wR) 02) -
6² La (Fd n.
+ IVRM (1 (1- N N-1 I(NSS)).
v²
-11
M 111
+
(31)
1 6n2M
Remark E.1. 1. For convex f. if =N=No Noo or
N - v US
(L) 1/5 2/ (d1(/d((1/)))))
3D 1/5 T
1/10
3/5 Φb
N - M
ED
then (30) recovers the bound (6) in Theorem 3.1 (M = N version), with N replaced by M. For p-strongly convex J, if M N or
N M
0² + VILL-dIn(1/6o)
VK
2n2
n
then (31) recovers the bound (7) in Theorem 3.1, with N replaced by M.
To prove Theorem E.I, we will need some preliminaries:
Lemma E.I. (Woodworth et al., 2020b, Lemma 4) Let F W - I be convex and 3-smooth. and suppose that the unbiased stochastic gradients g(w;) at each iteration have bounded variance
Elğ(w) FFw)) & 2 If wh is computed by R. steps of Accelerated MB-SGD the regularized objective F(w) = F(w) + 21 2 - IVR
[
wo 12, then
Wo
Vllwo- - =
EF EF (
p
R
R
We then have the following bound for the multi-stage protocol:
Lemma E.2. (Ghadimi & Lan, 2013. Proposition 7) Let f W Rd be p-strongly convex and 3-smooth, and suppose that the unbiased stochastic gradients ((,,) each iteration have bounded variance Rlg ((w)) V (ww)) & V2_1f T is computed by R steps of the Multi-Stage Accelerated MB-SGD, then
1 3
V2
EF (F - F $ A exp
PR
where A F(wo) F*.
35

---

Published as a conference paper at ICLR 2023
Of course, (Woodworth et al., 2020b, Lemma 4) and (Ghadimi & Lan, 2013, Proposition 7) stated for the non-private Accelerated MB-SGD (AC-SA). However, we observe that the bounds in (Woodworth et al., 2020b, Lemma 4) and (Ghadimi & Lan, 2013, Proposition 7) depend only on the stochastic gradient oracle via its bias and variance. Hence these results also apply to our (multi-stage implementation of) Accelerated Noisy MB-SGD. Next, bound the variance of our noisy stochastic gradient estimators:
Lemma E.3. Let X, Dj, Jr == N. Lies, R j (f(wr, + u.), where (zij) are sampled from X; and u, ~ No0 La)) is independent of V (Ww,, vig) for all i E [N], E [K]. Then
d²
M N- (I-N-T
22
do² M
Blg VF(W,))
MK +
M [N>1)
The three terms the right-hand side correspond (from left to right) to the variances of: local minibatch sampling within each silo, the draw of the silo set S, of size M, under Assumption 3, and the Gaussian noise. We now turn to the proof of Lemma E.3.
Proof of Lemma E.3. First, fix the randomness due to the size of the silo set M,. Now Gr 9r Ur, where Ur M, EM u, N(0, o² Ia) and ūr is independent of 9r M,
M, EvEs,
1 K; Σ}E[K] Vf(W,, z.y)) Hence,
Bl VF(W,,) B[l VF | + E
0²
E V VF(w,) )1 [|
M,
Let us drop the subscripts for brevity (denoting g gr. w wr. = Sr, and M, M, since they have the same distribution) and denote hú := K, Mi)
- V f(w, xz,z). Now, we have (conditionally on
Bllg [F(W)]
E
Sw, (w, VF( Mi
M1 SE
(hh Vk(w)) + 1 Σ VFi(w) VF(W) 12
E
Mi
M
Mi
SES
S
Σ -
M
iES
E
VF(w) (F(w) M1
M
SE
since, conditional on S, the cross-terms vanish by (conditional) independence of h2 and the non- random Lves (w) F(w)) for all i E S. Now bound @):
Es
Er.
hi(1o) (1) M
iES
Es
ER. hh(ww) V S.
S
< 15
K
iES
M 2
& E.g
K
36

---

Published as a conference paper at ICLR 2023
by conditional independence of h2 V.F and by FFy given S. Hence
1 M
E
Σ
he(w) VF((w)) Mi MiK
d²
sEs
Next we bound ① Denote y: == (F((w) and y N N
vi V((w). We claim b
E
Eies U/- 7 Mi
Mi Mi | 0². Assume WLOG that y (otherwise, consider
3/ y/ y. which has mean 0). In what follows, we shall omit the "conditional on M1" " notation (but continue condition on M2) and denote by & the collection of all (M) subsets of [M] of size
Mr. Now.
N
Vk
Selt
SES
Σ
y/ll +2 2
Σ
(Ur Ye)
N
SELt
SES
1
((V) -1 11 -1) Σ 11212 +2
N
N -
Σ LsTorEN
<eni (yt
Mi 2
Mi
M1
N.
llwll2 + MMMM 1)
Σ
Σ
<3h, vv)
N
N(N - 1)
leief'
Mi
(M1
N M1
N
2M 1)
+
Σ
1ua1l +
Σ
(v,, Be)
N
N -
N 1
N(N - 1)
EN
Mi M1 -1
N
2
M1 N M1 N
Σ y/
Σ
N N -1
N
N -
= Mi N M1
N N - Σ ||
N M1
E Mi
2.
N -
Hence M? E
IEies V.i(w) VF(w) 1
Mi
N- dي < N-T Mr Finally, we take expectation over the
randomness in Mi and use B[1 1/M to arrive at the lemma. Also, the result clearly holds when N since the b term is zero when there is no variance in silo sampling (which is the case when N = 1).
Proof of Theorem E.I. Privacy: By post-processing (Dwork & Roth, 2014, Proposition 2.1), suffices to show that the R n/K K noisy stochastic gradients computed in line 7 of Algo- rithm are (en, 50)-ISRL-DP. Further, since the batches sampled locally are disjoint (because we sample locally without replacement), parallel composition (McSherry. 2009) implies that if each update in line 7 is (Eo, IS)-LDDL then the full algorithm is (co. 66)-ISRL- Now re-
where A2 = SUPo,,X,~X: K Σ Vf(w, (s "(,"l = sup 2., R [V][(w,)) - VS(w, & 21 is the Le sensitivity of the non-private gradient update in line 7 of Algorithm 1: this follows from (Bun & Steinke, 2016, Propositions 1.3 and 1.6) and our assumption 6 & 8 (n1//))) Therefore, conditional on the private transcript of all other silos, our choice of o² implies that silo i's transcript is (En. 6o) for all i E [N]. which means that One-Pass Noisy Accelerated Distributed MB-SGD is (co, 8p -SSRI-DP.
call that the Gaussian mechanism provides (co, 6DP if d² >
8A3 (5////))
37

---

Published as a conference paper at ICLR 2023
Excess loss: 1. For the convex case, we choose
2D where V2
d²
+
N-M N-1 + de the variance of the noisy stochastic minibatch gradients, by Lemma E.3
M [NS1)
for our noise with variance o² 321,2 1n(1.25/6))
Now plugging V2 into Lemma E.I, setting
K
R n/K, and À == 2DVR yields
V
K2
&D
LD d1i((1/o))
VKeD N M vnM V N (N=I)-
EF(wR) (0) - F*
S
n²
vnM
KnK
Choosing K =
L (D)
2/5
3/6
(d1) 1/
implies (30).
2/3 Ms
2. For strongly convex loss, plug the estimate for V used above into Lemma E.2 with R = n/K to obtain
-11
u²K
(1 1 N -1)
M
L (dd1n(1/0o)) 1[N=1)
BF(wN) F* & exp
K KVn
pnM
PnM
1 Knog
Choosing K
yields (31).
Volu HA min
2 2=dim(1/8g)
aM
F PROOFS AND SUPPLEMENTARY MATERIAL FOR SECTION 4
F.1 PROOF OF THEOREM 4.1
We begin by considering 3-smooth f.
Theorem F.1 (Smooth ERM Upper Bound), Assume f(,xx) is 3-smooth for all a. Let eo &
(2/2)1(2/60) and a² 2561 it (tlm( ( (u(2/60)
2 22((2)))), 6n E 10, choose K A can
Ag
Then Algo-
n'
rithm 1 is (eo, 6o)-ISRL-DP. Further:
If fx(,,x) is convex, then rumning Algorithm 1 on the regularized objective f(w,
f(w,,) x) + + woll? with max ((V
1/2
8D
MMem [ln(1)66)
[LMKKNN Kdim(i]boo] (and
specified in the proof) yields
LD LDV(11(1/bb)
- - = =
(32)
ConMM
2. If f(,2) is pusttrongly convex, then running the multi-stage implementation (Appendix E. of Algo- en,²
rithm with R = max {VEn in yields
(AxuMee32 1.dd
[[MMK=N kain(1/6a) and Ax 3/ Px(wo) Fx
L2 (/d(m((160)) ( 10=((tid
E E
-
(33)
en
To prove Theorem F.1, we will require the following lemma: Lemma F.1 ((Lei et al., 2017)). Let (othee(N) be an arbitrary collection of vectors such that
D = 0. Further, let S be uniformly random subset of [ of M. Then,
E
Σ IES
Ñ-
M
Σ
N
|all
1 MM
N
N Σ
1)M
M
Proof of Theorem F.l. Privacy: ISRL-DP Algorithm 2 follows from ISRL-DP of the stochastic gradients ( in line of the algorithm (which established in Theorem D.1) and the post- processing property of DP (Dwork Roth, 2014, Proposition 2.1). Namely, since the choices of g2, K given in Theorem F.1 ensure that silos' local stochastic minibatch gradients are ISRL-DP
38

---

Published as a conference paper at ICLR 2023
and the iterates in Algorithm are functions of these private noisy gradients (which do not involve additional data queries), it follows that the iterates themselves are ISRL-DP.
Excess risk: 1. For
J w I R Lemma E.1 implies
3D2
VD VR'
( - F*
(34)
R
where V22 [n] El J. defined in line of Algorithm 1. Now Lemma F.I and L-Lipschitzness of f(, x) implies that
M, Lis, 9h v Fx (w ( 12 for T Zi=1 Vf(u, hurdd ; + u4
V
LMM)
sup [V vFx(w)1 & (M, M,K'
4L2
M,KnN
wEW
conditional on M,. Hence, taking total expectation with respect to M, and plugging this bound into (34) yields:
3D2
LIMKSAN) VMKR
(1/b)(
(Dx P
+
LD
R
VMan
by our choice of o² and independence of noises (uilies, across silos. Then one verifies that the prescribed choice of R yields (32).
2. Invoking Lemma E.2 with the same estimate for V2 obtained above gives
I,2 (1(MKK=N)) dl1n((R6)) Mcgn²
(f) Fx = Ax exp
(
(MMRR +
+ r
MKR
and plugging in the prescribed R completes the proof.
now re-state precise form Theorem 4.1 before providing proof:
Theorem F.2 (Precise Re-statement of Theorem 4.1). Let co & 2ln(2/50), do E (0, 1), choose
x² 256L Rl((222 2&B ln(2/60) and K > 22/200(2))6)) Then, Algorithm is (ea, 6o)-ISRL-
ntrb
DP. Further, there exist choices of 3 > O such that for Algorithm 2 run on fa(w, = mingew (f(v,x) + w v1?). we have:
If f(;22) is convex, then setting R max
Vileon 1 (MK=NN)) Kdln Vdln(1/bo)
yields
/dl(1//b))
E X
09
x
δ LD
(35)
ConvM
}) (in the
2. If f(-,z) is p-strongly convex and R = θ multi-stage implementation Appendix E, then
max
MMan ddlu11/5))
1 (MMKKNN) Kdlm(1/6o]
T,2 dlln(1/5))
EF F* δ
(36)
# Gnn 2
Proof. We established ISRL-DP in Theorem F.I. Excess risk: 1. By Lemma D.7 and Theorem F.I, we have
d
1
B7X(OR) - P s LD
+
MEER
3
R = max ((V
1/2
BD Mean
, (MMKNN)) Kdlm(1/bo)
Now choosing == fnny//
V (m(666)))
vdD
yields both the desired excess risk and communication complexity bound. By Lemma D.7 and Theorem F.I, we have
L dnn (R/60)
L?
E ( - f*
+
Mena
3
39

---

Published as a conference paper at ICLR 2023
R max (Ven In (AxuMein") L'dd
1 NM)) ( Now choosing 8 : p.Man yields
both the desired excess risk and communication complexity bound.
Remark F.1. The algorithm of (Girgis et al., 2021) requires R = Stegnn communications, making Algorithm faster by a factor of min(y ( Megn/Vd, MK). M = N and full batches are used, the advantage of our algorithm over that of (Girgis et al., 2021) is even more significant.
F.2 LOWER BOUNDS FOR ISRL-DP FEDERATED ERM
Formally, define the algorithm class (e 5u), to consist of those (sequentially interactive or C- compositional, ISRL-DP) algorithms A E C such that for any X E X, f FL,D, the expected empirical loss of the shuffled algorithm A, derived from A is upper bounded by the expected loss of A: EA (XA((X) & EEF((AX) Here A, denotes the algorithm that applies
the randomizer R₂ to (8) for all i, but otherwise behaves exactly like A. This is not very constructive definition but we will describe examples of algorithms in (ro. I (o) includes all C-compositional
sequentially interactive ISRL-DP algorithms that symmetric with respect to each of the N silos, meaning that the aggregation functions Or are symmetric (i.e. gr (z IN) gr (1): Zx(N)) for all permutations x) and in each round the randomizers
R R2 are the same for all silos E [NV]. (R()) can still change with though.) For example, Algorithm 2 and Algorithm are both in (EG Ru) :- (o). This is because the aggregation functions used in each round are simple averages of the M N noisy gradients received from all silos (and they are compositional) and the randomizers used by every silo in round r are identical: each adds the same Gaussian noise to the stochastic gradients. IB also includes sequentially interactive algorithms that choose the order in which silos are processed uniformly at random. This is because the distributions of the updates of A and A, are both averages over all permutations of [N] of the conditional (on т) distributions of the randomizers applied to the π r-permuted database. If A E B.)e,.)).C is sequentially interactive or compositional, we write E We now state and prove our ERM lower bounds:
Theorem F3. Lel 6o E (0, NJ, 6n = o(1/uN) and A E (eeo 6e). such that in every round E [R].
the local randomizers R.xi (Z (zrr)))) : X" - Z are (co, -DP for all i e [N], Z(r--1)
zr-IxN, with eb & 1, 8 o(1/nN R),, and N e 16 Then:
1. there exists (linear, hence B-smooth vB > 0) loss function f Fr.D and a database X E X (for some X) such that:
EXx(A(X)) - f = ā [DDmin
( {
)
NON 1)
Vd
2. There exists (p-smooth) -u.L.D and database X XNN such that =x= -
(.x((((X) - Px
( (r.Dmin min (2neNC4)) ( })
d
Further, if A L B, then the above lower bounds hold with 1
Proof. Step 1 is identical to Step I of the proof of Theorem 2.2. Step is very similar to Step 2 in the proof of Theorem 2.2, but now we use Theorem F.4 (below) instead of Theorem D.6 to lower bound the excess empirical loss of Ag. Step 3: Finally, the definition of IB implies that the excess risk of A is the same that of A,, hence the lower bound also applies to A.
Theorem F44. (Bassily et al., 2014) Let n. D, c > 0, L 2 μD, and ō = o(1/nN). Consider D Didd a Rd and W = () = Rd. Let A: x - W be any (e, C)DD 4
X' = D (= algorithu. Then:
There exists a (p zu==0 0) convex, linear (8-smooth for any 3), L-Lipschitz loss f W x X - R and database X N such that the expected empirical loss of A is lower bounded
vd EnN 1)
Efx(A(X)) P = = LD min
40

---

Published as a conference paper at ICLR 2023
2. There exists pu-ttrongly convex, p--moooth L-Lipschitz loss W x X R and database
X E X such that the expected empirical loss of A is lower bounded as
(Ax((( - P* ς2 (I.Dmin' -
(
d
G PROOFS AND SUPPLEMENTARY MATERIALS FOR SECTION
G.1 PROOF OF THROREMS 5.1
Theorem G.1 (Precise version of Theorem 5.1). Let & 11(22/6, E (0,1), and M >> 16 In (n(18RM2/N6) for (polynomial) R specified in the proof. Then, there is a constant C > such that setting o² == C1. RM In( (n(RM//NN)) (R(88) In(1,8) ensures that the shuffled version of Algo- N²N2c
rithm is (c, 6 Moreover, there exist 1r r and R-1 such that the shuffled version of Algorithm 2 achieves the following upper bounds:
If [C a) is convex, then
EF(ūR) === Ō
1
vdl((1/0) enN
LD
(37)
VnM
2. If f(,2) is p-strongly convex, then
L 1
dlm(1/0) en
EF(@R) - F ===
(38)
nM
Proof. We fix K for simplicity, but note that > 1 can also be used (see Lemma 3 in (Girgis al., 2021)). We shall also assume WLOG that f(.,2) is 3-smooth: the reduction non-smooth f follows by Nesterov smoothing, as in the proofs of Theorems 2.1 and 4.1. Our choices of R
shall be: := max
n 22 M
M min {n,
2=²N=
8D min VVM, en
Vd }) for convex f: and
dmd
R = max 11 N2
M
88 M
N
In
(DD n
dL2
Na min
n,
dM }) for strongly convex.
Privacy: Observe that in each round r, the model updates of the shuffled algorithm AC can be viewed
as post-processing of the composition (X) = SM samp NN (z(") ( z(,)), where SM uniformly randomly shuffles the M received reports, sampp,, the mechanism that chooses M reports uniformly at random from N, and Z sampi,, (R.,,
(xi,)),) where Rx)
V [f(w,, x)) + and u (0, La),). Recall (Theorem A.1 in (Dwork & Roth, 2014)) that o² = SL. ln(2/56) suffices to ensure that R, is (Eo, 6p) if &o & 1. Now note that M,(X) = RM (SM MampM,N((I,. XN), where R X - 2 is given by X + sampi, (R(z)), R((x)) and R.M X ZM is given by X - (R(X)), R((M)) for any X (X1, XNM) E M This is because we are applying the same randomizer (same additive Gaussian noise) across silos and the operators Sa and RM commute. (Also, applying a randomizer to all N silos and then randomly choosing M reports is equivalent to randomly choosing M silos and then applying the same randomizer to all M of these silos.) Therefore, conditional on the random subsampling of M out of silos (denoted (X1, .XM) for convenience), Theorem 3.8 in (Feldman et al., 2020b) implies that (R(I (R(II(1))).... R( R(Fa())))). ... R(II(M),1), R(I=(M)).)) is (2, 6) OCCP..
where 2 - o 50 (o/1((1/M5)) and 8 = 9M6 provided 6 & and M > 16 (which we VM
will see is satisfied by our assumption on MM. Next, privacy amplification by subsampling (see (Ullman, 2017) and Lemma 3 in (Girgis et al., 2021)) silos and local samples implies that M,
is (e", CDDP where e" = 2 NN
O
6 V In(/M86)) and d" = M nN
3 9M2 nn Sg. Finally,
nN
by the advanced composition theorem (Theorem 3.20 in (Dwork & Rothh 2014)), to ensure A, is 5" == 6/2R)- CDP. Using the two
8)DD), it suffices to make each round (c" :=
2 2116(1
equations to solve for E
V [ for some C >>> 0 and 8
CoNe
18RM2 we see that
nN5
41

---

Published as a conference paper at ICLR 2023
x² -0=0 - [.2In(RMM2 (Rn -
ensures that A. is (e, CC..P. i.c. that is 6)-DS. Note that our choices of It in the theorem (specifically R N/M and It > 50, & and éo & 1, so that Theorem 3.8 in (Feldman et al., 2020b) indeed gives us the amplification by shuffling result used above.
N²N M
ensure that
Excess risk: Note that shuffling does not affect the uniform stability of the algorithm. So we proceed similarly to the proof of Theorem 2.1, except o² now smaller.
1. Convex case: Set "r 7 1/R for all Now Lemma D.2, Lemma D.1, and Lemma D.6 (with
o² in the lemma replaced by the o² prescribed here) together imply for any v & 1/3 that
L2Ry nM
D
do²
EF F
+
L2/M
nR
M
Now plugging in := min
1/3,
DVM LR
min
Vn.
en.V
yields
dM Ia(2MM// (N)) (12/6) ln(1/6)
Vdln(RM2 N8) (n In (n(1)))
EF((R) F
F x
LD
max
VnM
enN
LD
en.V dM In(RM///DD In R In(1/))
BDa
min
RVM
M
R
Then one can verify that plugging in the prescribed R yields the stated excess population loss bound. p-stroongy convex case:
By Lemma D.6 (and its proof), we know there exists & 1/3 and {+r)__ such that
@ Px δ (DD*ex)
( exp
R
L
do²
2k
uR
μMR
Hence Lemma D.1 and Lemma D.2 imply
BF(@g) F* 3
BD
exp
R
L
L'd1n(1/8)
L
2x
HR
N
pMM
Then one verifies that the prescribed R is large enough to achieve the stated excess population loss bound.
G.2 SDP ONE-PASS ACCELERATED NOISY MB-SGD AND THE PROOF OF THEOREM 5.2
To develop an SDP variation One-Pass Accelerated Noisy MB-SGD, we will use the binomial noise-based protocol of (Cheu et al., 2021) (described in Algorithm 4) instead of using the Gaussian mechanism and amplification by shuffling. This is because for our one-pass algorithm, amplification by shuffling would result in an impractical restriction on Algorithm 4 invokes the SDP scalar summation subroutine Algorithm 5.
We recall the privacy and accuracy guarantees of Algorithm 4 below:
Lemma G.1 ((Cheu et al., 2021)). For any 0 & 15,0 8 1/2,d,N N, and L. there are choices of parameters b, e N and E (0, 1/2) for PID (Algorithm 5) such that, for X (x), xN) containing vectors of maximum norm [ax [xil| L, the following holds: 1)
Pree is ()DD): and 2) Proc (X) is an unbiased estimate of Σ with bounded variance
N
dI. log" (2) e2
E
Pwr (X;
Xi
=
With these building blocks in hand, we provide our SDP One-Pass Accelerated Noisy MB-SGD algorithm in Algorithm 6. We provide the general version of Theorem 5.2 for M & N:
42

---

Published as a conference paper at ICLR 2023
Algorithm 4 Pvec, shuffle protocol for vector summation (Cheu al., 2021)
1: Input: database of d-dimensional vectors X (X1,' ;Xx); privacy parameters c, 6; L.
2: procedure: Local Randomizer Rvee (x.)
3: for j [d]] do
4: Shift component enforce non-negativity: Wi, < Xi,5
5:
- RID (Was)
6: end for
7: Output labeled messages ((j, my)]
8: end procedure
9: procedure: Analyzer (y)
10: for j [d] do
11:
Run analyzer coordinate j's messages 2j AID(y,)
12: Re-center: 0j -
13: end for
14: Output the vector of estimates o = (01,'..oa) 08)
15:
end procedure
Algorithm 5 PID. shuffle protocol for summing scalars (Cheu al., 2021) gg be N:pe (0, })
1: Input: Scalar database X (x1,... xN) [0, LJN:
2: procedure: Local Randomizer Rin(x.)
3: Zt [æ=g/L].
4: Sample rounding value 771 Ber(z.g/ L xz).
5: Set é; F. + 7/1-
6: Sample privacy noise value Bin(b, p).
7: Report y; {0, 139+h containing á; 172 copies of and g + b (Φ, 122) copies of
8: end procedure
9: procedure: Analyzer AIn(S(y))
10: Output estimator (EE I Ett((y)))) - pbn).
1=
11: end procedure
43

---

Published as a conference paper at ICLR 2023
Algorithm 6 SDP Accelerated Noisy MB-SGD
1: Input: Data X; E X,", e [N], strong convexity modulus μ > 0, privacy parameters (e, 8),
iteration number It E N, batch size K E [n]], step size parameters (Mr]r (ar)rejm)
2: Initialize wo" Wo W and 1.
3: for T [R] do
4: Server updates and broadcasts wind -ataMuttell
(al((-a))ttm Wy-1
"r 1--(1-a)) w + N. N=+(1-a))p
5: for i S, in parallel do
6: Silo draws {x; from X, (without replacement) and computes 2
fV " )
7: end for
8: Server receives Dr M.K P
9: Server computes Wi == argmin (a, [Tr, w> + 1 w|]3] + [(1 - ar) 1/2 + 9r
|r--1 wl
2
10: Server updates and broadcasts w = a, W. + (1 w-
end for
12:
ag Output: WR
Theorem G.2 (Complete version of Theorem 5.2). Let f(-,2) be 3-smooth Vx E X. Assume & 15, 8 e (0, 2). Then, Algorithm 6 (c, 8).B). Moreover, there are choices of stepsize, batch size, and À > such that (for e defined in (29)):
Running Algorithm 6 on fw,,)) == f(W, x) + 2 2|w wol? (where wo W) yields
EF(wR) - =0==0
6D VnM
LD Vd (m(d/8)
N M
L 1/5 DA1S
\vdln(d/d)
en.
(N>1)
B1/3
em.33.5
(39)
2. If f(-,z) is p-strongly convex Vx E X and 2. then running the Multi-Stage Implementation of Algorithm (recall Appendix E. directly yields
(F
0g R
F
nM
Φ² La /kd (m1/6)
P. En²M²
+ WVRM
2
(1-
(1-N-1
(1-M-
M-
N
L(NSI)).
(40)
Remark G.1. 1. For convex if M or
N - (L3D2 1/5 (din(d/)))811
(D +
eM2
1/107
U N M
3/5
Ind (d/8)
then (39) recovers the bound (10) in Theorem 3.1 (M N version), with N replaced by M. 2. For j-strongly convex f, if M = or
N N N-M
8 VRIPd1m(1/0))
v2 s
M
then (40) recovers the bound (11) in Theorem 3.1, with N replaced by M.
Also, note that appealing privacy amplisication by subsampling would result in tighter excess risk bounds than those stated in Theorem G.2 when M < N, but would require a restriction & M/N. To avoid this restriction, we do not invoke privacy amplification by subsampling in our analysis.
Proof of Theorem G.2. Privacy: By post-processing (Dwork & Roth, 2014, Proposition 2.1), suffices to show that the R = n/ K noisy stochastic gradients computed in line of Algorithm (c, SDP. Further, since the batches sampled locally are disjoint (because sample locally without replacement), parallel composition (McSherry. 2009) implies that each update in line (e, 8)-SDP then the full algorithm is (c, SDPP. Since f(,,x) is I--Lipschitz, it follows directly from Lemma G. that each update in line 8 is 6)DPP
Excess loss: 1. For the convex case, we choose
2DVR" where V2
de MR
N ((N N-M Var(ğr) is the conditional variance of the noisy stochastic minibatch gra-
d12 (n2()/)) 2MKK
dients given Mr. by Lemma E.3. Also, conditional on Mr we have Var(ğr)
44

---

Published as a conference paper at ICLR 2023
by Lemma G.1 and independence of the data. Hence, taking total expectation over M,, get - M
V2 MK +
[[V=1)
N-M
+
AL
(n2(0)))
Now plugging V into Lemma E.I, setting
N-T
R n/K, and À == 2DVR yields
V.
3D²
6D LDVdln(djO) VKeD N - M N W-1 (N=1))
EF(wR) - F
n²
VnM
eMvKn
VnM
2/5
3/6 (d
4/ implies (39).
Choosing K
3D
M2
2. For strongly convex loss, we plug the same estimate for V2 used above into Lemma E.2 with R n/K K obtain
u²K
1 d (1 N 1) (NSI) / Kne M
M
(F( F & A exp
exp
1
K KVE
WmM
WnM
where A 3 F(wo)= F Choosing K
yields (40),
Viln(na min
H ISRL-DP UPPER BOUNDS WITH UNBALANCED DATA SET SIZES AND DIFFERING PRIVACY NEEDS ACROSS SILOS
In order to state the generalized versions of our upper bounds (for arbitrary n. c,, 8,, ie [N], will require some additional notation and assumptions.
H.1 ADDITIONAL NOTATION AND ASSUMPTIONS
First, we define generalization of (co, 6o)-ISRL-DP (as it was formally defined in Appendix B) that allows for differing privacy parameters across silos:
Definition 10. (Generalized Inter-Silo Record-Level Differential Privacy) Let (x( Σ/=1 (xrg)tz),,) .. E [N]. A randomized algorithm A is [(e, 6, if for all silos and all pi-adjacent X,, X²
= (R( (X.), R Z1 X.), ... RS 1. (c)
(R( (X)). R2 (Zi, x.), R (Zi.n-1. X!)),
where Z, = (R. 1,)r and Z = {R. (Z/ror X
We also allow for the weights put on each silo in the FL objective to differ and consider:
min WEW
F(w)
Σ p. Fi(w)
where ps E [0, 1] and N Ps 1. However, we will present our results for the case where pt for all i [N]. This is without loss of generality: given any F(w) ΣN p. Fi(w), we have (iit.,,,NNppfff.. 2x)]
Σ (w)),, where F.(w) Np. E2,-D, (f x.)]. Thus, results for the case of p; 1/N apply for general ps. but L gets replaced with 7, max,e[N] L, μ gets replaced with ğ min P.N p. and gets replaced with 3 P.N
F(w) E p. F((w)=
We will choose batch sizes K; such that K,/n; = Ki/n; for all 1 [N] in each round, and denote K mi Kç. In addition to the assumptions we made in the main body, we also refine the assumption {M, include description of the second moment of 1/M,:
Assumption In each round r, uniformly random subset S. of Mr [N] distinct silos is available to communicate with the server, where (My are independent random variables with
M := E( x and
337 :=
E MP
45

---

Published as a conference paper at ICLR 2023
For M [M] denote
1
TM M
(0))
where ((1 == max = [aX of > le > 7 (N)) = iin == min of (More
generally, whenever a bar and M subscript are appended to a parameter, it denotes the average of the M largest values.) Also, define
Σ = (((o)))
for any 1oth-11 S [0, oo).
Next, recall the heterogeneity parameter from (29):
N VF VF(w))
= sup we N
Lastly, for given parameters, denote
1
2 1n(2.5//8. (n(2/)))
&
fe [N].
Emax max(E1," .. ENN,
and
1 M₁
EM
E(,
M
In the case of balanced data and same parameters across silos, we have & = { = E for all i. In the general case, we have Emin & Emax-
H.2 PSEUDOCODE FOR NOISY ISRL-DP MB-SGD IN THE UNBALANCED CASE The generalized version Noisy ISRL-DP MB-SGD described Algorithm 7.
Algorithm 7 Noisy ISRL-DP MB-SGD
1: Input: N, d, R E N, (oi) = [0,00,, X; E X, for i E [N], loss function f(w, x), [K₃] = N, [mt)re[R] and (T)))((R)
2: Initialize We W.
R do 4: for S, in parallel do
3: for r E 1,
5: Server sends global model w, to silo
6: Silo draws K; samples o. uniformly from X, (for j e [K,] and noise u, ~ ((0,o
7: Silo i computes H. = K. ΣK1 Vi(w,, x(y) + un and sends to server.
8: end for
9: Server aggregates gr := Mr Lies, Dr.
Server updates wr+1 := Iw n.
11: end for
Output: HR In 2 W, where TR = - R-1 7,-
H.3 GENERAL UNBALANCED VERSION OF THEOREM 2.1
We first state the formal version of Theorem 2.1 for arbitrary n,, 6,, using the notation defined in Appendix H.I.
46

---

Published as a conference paper at ICLR 2023
Theorem H.1 (Generalized Version of Theorem 2.1). Ler (2( 6; (0, 1). Then, Algo- rithm 2 {le,, -
c.0 2561' Rin In( (.2R) In(2/6.) and K; 12/221(2/66)
-IRIL-DP of
Moreover,
with notation as in Appendix H.I, there are choices of algorithmic parameters such that: 1. 1f f() is convex, then
Smax
EF EF(uR) - F LD
+
d
min
Viuin M
M
M
2. If (() is p-strongly convex, then
(F(ØR) - - = L2
Smax
+ d min
(41)
M1mmin
M
M
Remark H.1. Note that 1/M' 3 L/M by the Souchy-Schwartz inequality. Both of the upper bounds in Theorem H.1 involve minima of the terms E/M' and Smax/M /M, which trade off the unbalancedness of silo data and privacy needs with the variance of 1/M,- In particular, if the variance of 1/ //M, is small enough that M. & Smes, then the excess risk bounds in Theorem H.1 depend on averages of the parameters across silos, ruther than maximums. FI. problems with unbalanced data and disparate privacy needs across a large number of silos, the difference between "average" and "max" can be substantial. On the other hand, if data is balanced and privacy needs are the same across silos, then Smax
=
&, = Emax = = in(2.RR 22.R/88 RRōy) ln(2/ (o(266)) 60)/n' c for all and E. > M so we recover Theorem 2.1,
Mi with dependence only the mean 1/ of 1/M, and not the square root of the second moment 1/M'.
To prove Theorem H.1, we need the following empirical loss bound for Algorithm 2, which general- izes Lemma D.6 to the unbalanced setting:
Lemma H.1. Let f W x X - TR. be p-strongly convex (with μ 0 ffrrr convex case). L-Lippchitz and 8-smooth in w for all x E X, where W is a closed convex set in Rd s.t. ||w- wwll & D for all
w, w W. Let X X. Then Algorithm 2 with of 2561.² R Int 2. In(2/6)) attains the following
empirical loss bounds as a function of step size and the number of rounds:
(Convex) For any & 1/3 and R E N. 7r 1/R, we have
D2
+ 17 (2ddmil d
Σ
o
EFX(OR) P
L2)
R
2
M
M
(Strongly Convex)
There exists a constant stepsize TJe = n & 1/3 such that if >
2x In
SyD²
then
L'd E/M' Smpse
((12 L,2
E Emax
E (w))
F
1 R + d min
(42)
M
M
Proof. By the proof of Lemma D.6, have:
E ||
w$1
M,
<(1
pm, E
lw,, w1 Mr
K,
+ E
Ir +
V f ( 255)
M,
M,
K
ieS.
j=1
which implies
Σ2 T
[wr+1 - wx 2²] < 5(1- (1-17,)B
[, 211 22, E[ Fx (wx) - + min
+I²
M'
M
(43)
47

---

Published as a conference paper at ICLR 2023
since || M2 Lies, and hence
M. M,
a M
2 & dE
& d min
mus
M'
using linearity of expectation for the first term in the minimum and Cauchy-Schwand inequality for the second term in the minimum. Now we consider the convex (f 0) and strongly convex (f > 0) cases separately.
Convex (μI 0) case: Re-arranging (43), we get
Σ
σ max
B[Fx (w,) - F
[B]]
w,
w |00+11 w =²1
dmmin
+
L2
2TT
M
M
Then for 77, = 17, the average iterate wR satisfies:
R-1
B T
x
El E[[x(w.) (w,) Fxx
1
1
[B[ [|,l - ===12 -||ur+1 20 [])
21j
r=0
Σ²
dmin
max
+ I!2
MM''
M
w*1l 112
Σ 2
+ 12).
+
d
R/
M
M
which proves part 1 of the lemma.
Strongly convex (μ 0) case: Note that (43) satisfies the conditions for Lemma D.5, with sequences
w 1/11 St
F[(x((W)) [
rt We
and parameters
Σ² M
o M
M4 2, c d min
I.2,
23, R.
Then Lemma D.5 and Jensen's 's inequality imply
( Fx = δ (3D² exp
-
R
2
1
{
E Emax
+
d
2K
p
R
M
M
where k = 3/u. Finally, plugging in R completes the proof.
We are prepared to prove Theorem H.1.
Proof of Theorem H.l. Privacy: The proof follows exactly as in the balanced case, since of is now calibrated to (c, 5.) for all i e [N].
We shall prove the results for the case when f(:, x)) is 3-smooth. The non-smooth case follows by Nesterov smoothing, in the proof of Theorem 2.1. 1. Convex case: By Lemma D.2 (and its proof), Lemma D. and Lemma H.1, we have:
Excess loss:
EF(#n) F* & a + (#)))))
F
2L
D
dmii
max 1
Mmiin M
R
2
M
M
R
=
Smax
D)2
$ 2T
dR
+1) nR.
Demin M
M
M
48

---

Published as a conference paper at ICLR 2023
for any & Choosing min (1/8,
LVR
min
V/mmm M vR
1,
an
max
E
M Emaa
yields
3D
1
= M
Smax
LD EF(@R) F
d
Vmmin
VR
Choosing 3 3D I
min
VMMminn
dmmn
Smax M
min (min M, max
M' =
M
Emaoe
completes the proof of the case.
2. ju-strongly convex case: By Lemma D.2 (and its proof), Lemma D.I, and Lemma H.l, we have:
EF(uR) F Efx (wx)
F*
4L
L?
E
Smax
+ Ö
d min
M 1)
R
M
for the 17 < 1/B prescribed in the proof of Lemma H.l and any 2x In
Bp
L
3/M Smax
Thus, choosing R 2n: In
DND L,d 3/M", fmax
Mu completes the proof.
Remark H.2. Generalized versions of the other upper bounds in this paper can also be easily derived with the techniques used above. The key takeaways are: a) the excess empirical risk (and the private in the SCO bounds) involve a minimum of two terms that trade off the degree of unbalancedness with the variance of 1/Mp- In particular, if the variance of 1/M, is sufficiently small (e.g. M, M, which what most existing works on FL assume), then the refined excess risk bounds depend on averages of the parameters across silos, rather than worst-case maximums. b) the generalization error scales with min n2.-
I NUMERICAL EXPERIMENTS: DETAILS AND ADDITIONAL RESULTS
In some plots this section, we include a parameter describing the heterogeneity of the FL problem:
N
Σ VE
=
which has appeared in (Khaled et al., 2019; Koloskova et al., 2020; Karimireddy al., 2020; Woodworth et al., 2020b). If the data is homogeneous, then all F; share the same minimizers, so vg O, but the converse is false.
ISRL-DP Local SGD runs as follows: in round r, each silo i E S, receives the global model w,, and takes K steps of noisy SGD (with one sample per step) with their local data: w wy- wis = witt- (VVff(uu fww. xx),) ) + ut) for E [K]. where x²,, is drawn uniformly at random from X; and uf N/O,, o"a)) for o² SL3RK lL Then silo sends its K-th iterate, wi*k nf
to the server; the server averages the iterates across all silos and updates the global model to Wr+1 Mr Eiss, k
I.1 LOGISTIC REGRESSION WITH MNIST
The data set can be downloaded from http: htttp:///aar /yann wttp:///co///////////c//// Our code does this for you automatically.
Experimental setup: To divide the data into N 25 silos and for preprocessing, we borrow code from (Woodworth et al., 2020b), which can downloaded from: https: papers-.p.... nips. ec wttpppppppeeeeeeeeeeeeeeeeeeceee httpp/pper/2/// 2000 html. available under a Creative Commons AttributionShhan Alike 3.0 license. There are 8673 training and 2168 test examples per silo; to expedite training, use only 1/7
49

---

Published as a conference paper at ICLR 2023
of the MNIST samples (n 1238 training, examples per silo). We fix 6; 8 1/n2 and test E {0.75, 1, 3, 6, 12, 18). The maximum v² is about 0.17 for this problem (corresponding to each silo having disjoint local data sets/pairs of digits).
Preprocessing: We used PCA to reduce the dimensionality to d 50. We used an 80/20 train/test split for all silos. To improve numerical stability, we clipped the input (w, x>) (i.e. projected it onto [-15, 15)) before feeding into logistic loss.
Hyperparameter tuning: For each algorithm and each setting of e, R. K, Ugg we swept through range of constant stepsizes and ran trials to find the (approximately) optimal stepsize for that particular algorithm and experiment. We then used the corresponding wn (averaged over the 3 runs) to compute test error. For (ISRL-DP) MB-SGD) the stepsize grid consisted of 10 evenly spaced points between e- and 1. For (ISRL-DP) Local SGD, the stepsizes were between e and e-1. We repeated this entire process 20 times for fresh train/test splits the data and reported the average test error in our plots.
Choice of o² and K: We used smaller noise (compared to the theoretical portion of the paper) to get better utility (at the cost of larger K/larger computational cost, which is needed for privacy):
o2 81.² 16(1 which provides ISRL-DP by Theorem of (Abadi et al., 2016) if K av'c (c.f.
n²c
2VR
Theorem 3.1 in (Bassily et al., 2019)). Here L 2 max | is an upper bound on the Lipschitz parameter the logistic loss and was computed directly from the training data.
To estimate vz. we followed the procedure used in (Woodworth et al., 2020b), using Newton's 's method to compute w" and then averaging V F; (w (w*) )2 over all i [N].
Additional experimental result: In Fig. 7, we show an additional experiment with M 18 available to communicate in each round. The results are qualitatively similar to the results presented in the main body for MNIST with M 25, 12.
18, 443, =022
0.24
Noisy MB SGD after 35 rounds
Noisy Local SGD after 35 rounds
0.22
MB SGD after 35 rounds
Avg. Test Error (20 Trials)
Local SGD after 35 rounds
0.20
0.18
0.16
0.14
0.0
25
5.0
7.5
10.0
12.5
15.0
17.5
E
Figure 7: Test error vs. e for binary logistic regression on MNIST. 8 = 1/n². We show 90% error bars over the 20 trials (train/test splits).
Limitations of Experiments: It is important to note that pre-processing and hyperparameter tuning (and estimation of I.) were not done in ISRL-DP manner, since did not want detract focus from evaluation of ISRL-DP FL algorithms." 16 As a consequence, the overall privacy loss for the entire experimental process is higher than the indicated in the plots, which solely reflects the privacy loss from running the FL algorithms with fixed hyperparameters and (pre-processed) data. Similar remarks apply for the linear regression experiments (see Appendix 1.2).
16See (Abadi et al., 2016; Liu & Talwar, 2019; Papernot & Steinke, 2021) and the references therein for discussion of DP PCA and DP hyperparameter tuning.
50

---

Published as a conference paper at ICLR 2023
1.2 LINEAR REGRESSION WITH HEALTH INSURANCE DATA
Data set: The data (https:/ available under an Open Database license, consists of Ñ 1338 observations. The target variable medical charges. There are 1 6 features: age, sex, BMI, number of children, smoker, and geographic region.
which is
Experimental setup: For given N, grouped data into N (almost balanced) silos by sorting y in ascending order and then dividing into N groups, the first N - 1 of size [1338/ N and the remaining points the last silo. For each N, we ran experiments with fresh random train/test (60 split. We tested e {.125, 25, 55, 1, 2, 3) and fixed ö; 1/ng for all experiments.
35. We ran 20 trials, each with
To estimate vg. we followed the procedure used in (Woodworth et al., 2020b), using Newton's method to compute w² and then averaging V F; (www) (w*) over all
[NV.
Preprocessing: We first numerically encoded the categorical variables and then standardized the numerical features age and BMI to have zero mean and unit variance.
Gradient clipping: In the absence of a reasonable priori bound the Lipschitz parameter of the squared loss (as is typical for unconstrained linear regression problems with potentially unbounded data), we incorporated gradient clipping (Abadi al., 2016) into the algorithms. We then calibrated the noise to the clip threshold L to ensure LDP. For fairness of comparison, we also allowed for clipping for the non-private algorithms (if it helped their performance).
Hyperparameter tuning: For each trial and each algorithm, we swept through log-scale grid of 10 stepsizes and 5 clip thresholds 3 times, selected the parameter that minimized average (over repetitions) training error (among all 10 x 5 = 50), and computed the corresponding average test error. The stepsize grids we used ranged from 1 for (ISRL-DP) Local SGD. The excess risk (train and test) we computed was for the normalized objective function F(u: (ww X. X.Y) Y)= = Y x 2/2.N, where No (1070, 268] (1070 for train, 268 for test) and X is No x d with d = 7 (including a column of all 1s) and Y E R The clip threshold grids were (100, 10 10 10 1032), with the last element corresponding to effectively no clipping.
and e² for (ISRL-DP) MB-SGD and from e 1 to
Choice of 2 and K: We used the same o² and K = described in Appendix I.1. However, here L is the clip threshold instead of the Lipschitz parameter.
ayfī 2/R
as in the logistic regression experiments
Relative Root Mean Square Error (RMSE): We scale our reported errors (in the plots) to make them more interpretable. We define the Relative (test) RMSE of an algorithm to be v M.SE/NMSS
(1 where NMSE ("Naiive Mean Square Error") is the (test) MSE incurred by the V Ei"ep -5ma))2
non-private naiive predictor that predicts y, to be Vmain the average of the training labels, for all test data [Neea]. Here Ú; the predicted label of the algorithm. Relative RMSE can be thought of as the Coefficient of Variation or Relative Standard Deviation of the predictions of the algorithm. Note that even though the naïive predictor is completely non-private and allowed to access the entire training data even when M < N (violating the decentralized data principle of FL), the ISRL-DP FL algorithms still outperform this predictor for most values of e (except for some experiments when R 0), as evidenced by values of Relative RMSE being below 1. For 1, ISRL-DP MB-SGD tends to outperform the naive predictor by 30- 40%.
Additional experimental results: In Fig. 8 and Fig. 9, we present results for experiments with additional settings of N and M. We observe qualitatively similar behavior as in the plots presented in the main body of the paper. In particular, ISRL-DP MB-SGD continues to outperform ISRL-DP Local SGD in most tested setups/privacy levels (especially the high-privacy regime). On the other hand, for some settings of M, NN K, we observe that ISRL-DP Local SGD outperforms ISRL-DP MB- MB-SGD as - (c.g. Fig. 9, and N M = 3). In general, we see that the utility impact of ISRL-DP is relatively insignificant for this problem when e 3.
51

---

Published as a conference paper at ICLR 2023
N M K 65, 61=64460691.6
Noisy MB SGD after 35 rounds
Noisy Local SGD after 35 rounds
Relative Test RMSE (20 Trials)
MB SGD after 35 rounds
Local SGD after 35 rounds
0.9
0.8
0.7
0.6
2.5
3.0
5, M 3, K 39, 0i 907736666.00
Noisy SGD after rounds
1.1
Noisy Local SGD after 35 rounds
Relative Test RMSE (20 Irail))
MB SGD after 35 rounds
1.0
Local SGD after rounds
0.9
0.7
0.6
0.5
1.0
1.5
Figure 8: Test error vs. e for linear regression on heterogeneous health insurance data. 1/re*. 90% emor bars are shown.
1.3 SOFTMAX REGRESSION WITH OBESITY DATASET
The data set can be freely downloaded from https://archive. .ic. www.eiii..i.e.eeeeeeooooo.eiieee edu/m1/ datasets physical+conditions The data contains 17 attributes (such age, gender, physical activity, eating habits, etc.) and 2111 records.
tstand+
Experimental setup: We divide the data into N heterogeneous silos based on the value of the target variable, obesity level, which is categorical and takes 7 values: Insufficient Weight, Normal Weight, Overweight Level Overweight Level Obesity Type Obesity Type II and Obesity Type III. We fix ó; = 5 = 1/n² and test {0.5, 1, 6, 9}. We ran three trials with a new train/test split in each trial and reported the average test error.
We numerically encode the categorical variables and standardize the continuous numerical features have mean zero and unit variance. We used 80/20 train/test split. We discarded a small number of (randomly selected) training samples from some silos order to obtain balanced silo sets, ease implementation of the noisy methods.
Preprocessing:
Hyperparameter tuning: For each algorithm and each setting c, R, K, we swept through a range of constant stepsizes find the (approximately) optimal stepsize for that particular algorithm and experiment. We then used the corresponding Wn to compute test error for that trial. For (ISRL-DP) MB-SGD, the stepsize grid consisted of evenly spaced points between e and e For (ISRI-DP))
52

---

Published as a conference paper at ICLR 2023
N 10, M = 5, K= 19, 03=134455525
1.2
Naisy MB SGD after rounds
Noisy Local SGD after 35 rounds
1.1
MB SGD after 35 rounds
Local SGD after 35 rounds
1.0
Relative RMSE
0.9
0.6
0.0
0.5
1.0
1.5
2.0
2.5
3.0
N = 10, M 10, K 19, Ui 133725427.
1.2
Noisy MB SGD after 35 rounds
Noisy Local SGD after 35 rounds
Relative Test RMSE (20 Trials)
MB SGD after 35 rounds
Local SGD after 35 rounds
1.0
0.8
0.7
0.0
0.5
1.0
1.5
2.0
2.5
3.0
Figure 9: Test error vs. e for linear regression on heterogeneous health insurance data. = 1/n². 90% error bars are shown.
53

---

Published as a conference paper at ICLR 2023
Local SGD, started with the same stepsize grid, but sometimes required additional tuning with smaller stepsizes (especially for small e) to find the optimal one.
Choice of o² and K:: We used smaller noise (compared to the theoretical portion of the paper) to get better utility (at the cost of larger K/larger computational cost, which is needed for privacy): σ² 81.2 (n(1/)) for ISRL-DP MB-SGD, which provides ISRL-DP by Theorem 1 of (Abadi et al., ndc2
2016) if K nye (c.f. Theorem 3.1 in (Bassily et al., 2019)). For ISRL-DP Local SGD, one needs 2VR
a² S1." In(168)RK since the sensitivity and number of gradient evaluations are both larger by n²t²
factor of K. Here L 2 maxxe | = 20 is an upper bound on the Lipschitz parameter of the softmax loss and was estimated directly from the pre-processed training data.
J LIMITATIONS AND SOCIETAL IMPACTS
J.1 LIMITATIONS
Our results rely certain assumptions (e.g convex, Lipschitz loss), which may be violated in certain practical applications. Moreover, our theoretical results require an a priori bound on the Lipschitz parameter (for noise calibration). While such bound is fairly easy to obtain for models such as logistic regression with data that is (known to be) bounded (e.g. our MNIST experiments), unrealistic for models such unconstrained linear regression with potentially unbounded data (e.g. our medical cost data experiments). In practice, in such situations, gradient clipping can be incorporated into our algorithms: we have shown empirically (medical cost data experiments) that MB-SGD still performs well with clipping. However, we did not obtain our theoretical results with gradient clipping. An interesting direction for future work would be to determine optimal rates for ISRL-DP FL without Lipschitzness and/or without convexity. Further, as we explained in Appendix I, pre- pre-processing and hyperparameter tuning (and estimation of L) were not done in a ISRL-DP manner in our numerical experiments, since did not want to detract focus from evaluation of ISRL-DP FL algorithms. As a consequence, the overall privacy loss for the entire experimental process is higher than the indicated in the plots, which solely reflects the privacy loss from running the FL algorithms with fixed hyperparameters and (pre-proce pre-pprceessed) data.
J.2 SOCIETAL IMPACTS
Our work provides algorithms for protecting the privacy of users during federated learning. Privacy usually thought of favorably: for example, the right to privacy is element of various legal systems. However, is conceivable that our algorithms could be misused by corporations and governments to justify malicious practices, such collecting personal data without users' permission. Also, the (necessarily) lower accuracy from privately trained models could have negative consequences: e.g. ISRL-DP model is used to predict the effects of climate change and the model gives less accurate and more optimistic results, then a government might use this as justification to improperly eliminate environmental protections. Nevertheless, believe the dissemination of -rreeerriii machine learning algorithms and greater knowledge about these algorithms provides a net benefit to society.
54


Reviews:
[{"review_id": "shfGjJN6Zuv", "reviewer": "Reviewer_SUpG", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This work studies Inter-silo record-level DP in cross-silo federated learning, where all communications to the server should satisfy item-level DP. The authors investigate convex optimization and design algorithms that achieve near-optimal performance for both convex and strongly convex cases. With amplification by shuffling, the error rate matches the optimal rate for central differential privacy. The results are supported by empirical evidence.", "summary_of_the_review": "This work provides convergence rates for SCO and ERM with convex losses under ISRL-DP, verified by experiment results. A minor issue is that the lower bound technique is indirectly proved and may not lead to tight rates for all parameter regimes. ", "strength_and_weaknesses": "Strengths\n- This work provides the first convergence results for convex optimization and ERM under ISRL-DP to the best of my knowledge.\n- Near-optimal rates are obtained for stochastic convex optimization and ERM for convex and strongly convex functions. \n- The practical setting where client data distributions are heterogenous is considered and convergence results are provided. \n- The authors provided empirical results for the proposed algorithms, and the performance is encouraging.\n\nWeakness\n- The lower bound proof uses an indirect approach using privacy amplification by shuffling. However, privacy amplification holds under certain conditions on $\\epsilon_0, \\delta_0$ and may lead to extra log factors, so tight lower bounds may not be obtained for all parameter regimes. What's the main difficulty in directly proving lower bounds for ISRL-DP?\n- Presentation: the table summarizing the results (figure 3) can be made larger and more readable. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XVwAYn3VMou", "reviewer": "Reviewer_beiC", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper considers a realistic DP notion called Inter-silo Record-level DP (ISRL-DP) which can address the shortcoming of central DP and LDP. An algorithm satisfying ISRL-DP requires that the output of this algorithm cannot be distinguished between two adjacent dataset of any agent, given all other agents’ dataset being fixed. The paper then gives a series of risk bounds for federated learning with ISRL-DP. The loss function is assumed to be convex in this paper. \n\n---\nFirst, under the homogeneous setting (i.e. the data distribution is the same across all agents), the paper shows noisy MiniBatch SGD is ISRL-DP. It then gives upper bounds of excess risk for convex and strongly convex loss function. It also gives lower bounds under the case of full participation (i.e. all agents participate in each round), which almost matches the upper bound. Furthermore, the lower bounds are quite general and can be reduced to existing lower bound for central-DP and local-DP.\n\nSecond, the paper considers a heterogeneous setting with full participation, and proposes an one-pass accelerated noisy MB-SGD algorithm with convergence guarantee under the convex and strongly convex loss function. Notably, the upper bound has a nearly optimal rate when the strongly convex loss function is well-conditioned, and is sub-optimal when the loss function is convex. \n\nThird, this paper considers the empirical excess risk minimization, and proposes an algorithm that achieves optimal rate. \n\nFourth, this paper considers a case with a trusted shuffler that can permute the datasets from all agents. It proposes an algorithm that can achieve optimal rate with central-DP under homogeneous agents. Under heterogeneous agents, nearly optimal rate is achieved under the extra assumption that the loss is smooth.\n\nSeveral experiments are conducted and the results corroborate the theory. \n", "summary_of_the_review": "I recommend accept.\n\n---\nMy reasons are the following:\nThe problem considered is meaningful and well-motivated. The ISRL-DP is an interesting topic and a theoretical analysis would be valuable to the community.\nThe theory looks solid and covers a variety of settings, most of which are practical. Although the homogeneous setting is not that interesting, I do not think this is a huge problem because it is only part of the paper, and even for the convex homogeneous case this paper seems to give (one of) the first analysis.\nThe proof is complete and looks credible. The proof (I read some of it) is well-written with plenty of explanations.  \nThere are experimental results to support the theory. \n\n---\nThere is something that needs improvement.\nPresentation: The main text should be organized better to make results and assumptions easier to follow. \n", "strength_and_weaknesses": "Strength:\n\n1. Meaningful problem setting: the ISRL-DP is a reasonable notion of DP with practical applications. This paper also explains this point clearly by listing scenarios under which ISRL-DP is appropriate (i.e. when a client only trust its own silo). Therefore, establishing theoretical guarantees for ISRL-DP is a meaningful problem. \n\n2. Solid theory: under the general setting of convex loss function, this paper considers a various of different settings including a (not complete) combination of the following: homogeneous versus heterogeneous agents; convex and strongly convex loss functions; smooth and general loss functions; existence of trusted shuffler or not. This paper gives algorithms for these settings with convergence rate guarantees and ISRL-DP.\n\nThe solid theory is accompanied by rather extensive experimental results. The performance of the proposed optimization algorithm is comparable to that of FedAvg which has no DP guarantee. \n\n---\nWeakness: \n\nThere is no major technical weakness of this paper in my opinion. Still, I think the following is worth mentioning. \n\n1. The homogeneous setting is over-simplified and not very realistic. Basically, since $f$ is the same for all agents, when the distribution $\\mathcal{D}_i$ is the same for all $i$, it means every agent is facing the same learning problem. This seems not very practical. \n\n2. The main text of this paper is not easy to read. The reason is that there are quite a few theoretical results with different assumptions. So it is a little hard to follow. \n\n---\nMinor comments/suggestions:\n\n1. It is confusing when the authors mentioned in the bottom of page 3 that in section 4 they consider a setting where $F$ is an empirical loss. Since from equation 1 and 2 the definition of $F$ involves an expectation over data distribution, the ‘empirical loss’ confused me when I read for the first time. \n\n2. I suggest making a table of results (i.e. convergence rate, etc.) and assumptions (i.e. smooth or not; convex or strongly convex, etc.). This table can help readers compare different results and follow the settings. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "FSg1TN9Bze", "reviewer": "Reviewer_aKXR", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes a notion called Inter-Silo Record-Level Differential Privacy that differentiates from the well studied central DP, client-level DP, and local DP.  Very detailed analyses for convex losses in various cases are conducted, and experiments are provided.", "summary_of_the_review": "This paper conducts thorough analysis the privacy notion ISRL-DP in federated learning, the results are solid. ", "strength_and_weaknesses": "Strength: \n1. The theoretical analysis of this paper is very thorough and informative, most cases with convex losses are considered and both upper bounds and lower bounds are derived. \n2. The considered privacy notion is of high practical relevance. \n\nWeakness:\n1. It could help audience to appreciate the significance of this work better if the authors can highlight the implications of ISRL-DP, and maybe give some examples instead of pure mathematical languages to illustrate this notion.\n2. It can be better if the authors can highlight the technical contributions of these analyses, like are there any technical challenges in obtaining these results comparing with other privacy notions, what make these results different from repeating the machinery of derivations in other DP notions. \n3. For the secure shuffle part, can the authors provide some more discussions with existing works such as [1]?\n\n[1] Cheu, A., Joseph, M., Mao, J., & Peng, B. (2021, September). Shuffle Private Stochastic Convex Optimization. In International Conference on Learning Representations.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Az950zvfqIY", "reviewer": "Reviewer_Gj6i", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper analyzes the convergence of FL with record-level DP. It establishes nearly tight upper and lower bound for Noisy-Distributed-MB-SGD in the i.i.d. setting. For the non-i.i.d. setting, it proposes a new DP-FL algorithm (a modified version of Noisy-SGD), and proves the upper bound of its convergence rate. In particular, the upper bound of the proposed algorithm nearly matches the optimal i.i.d. bound when the loss function is strongly convex. This paper further analyzes the upper bound of the convergence rate when the shuffle model is applied into FL. Finally, it conducts numerical experiments to examine the theoretical results.", "summary_of_the_review": "This paper presents some interesting theoretical results. In particular, it proves the tight upper and lower bounds for individual-level DP FL algorithms when silo data is i.i.d. On the other hand, the proposed non-i.i.d. algorithm is impractical, thus the empirical novelty and significance is somehow limited. ", "strength_and_weaknesses": "Strength:\n\n1. This paper fills some gaps in the field of (record-level) differentially private FL convergence analysis. In particular, the authors present the first tight convergence analysis of FL with record-level approximation DP.\n\t\n2. This work provides the first convergence analysis when the shuffle model is incorporated in FL to achieve DP.\n\nWeaknesses\n\n1. The motivation for Inter-Silo Record-Level Differential Privacy (ISRL-DP) is not clear. If I understand correctly, ISRL-DP is identical to the setting where record-level DP is incorporated into local model training process, e.g., train local models by DP-SGD [1], and then submit local model parameters to the (untrusted) server. In other words, it treats each FL party as a database, and answer the query from the server (i.e., submit local models) in a differentially private manner. Therefore, It is unclear to me what really is the difference between ISRL-DP and record-level DP.\n\n2. The proposed algorithm (Algorithm 1) seems impractical. The Accelerated Noisy MB-SGD algorithm samples batches without replacement. In this way, each individual record is only used exactly once for the gradient computation, and thus parallel composition can be applied to account the overall privacy loss. While this modification can help achieve a convergence rate that is close to the i.i.d. setting, I am afraid that this algorithm will perform poorly in practice, because each record is only used once during the entire FL training process. A more general and practical setting is that each record would be sampled multiple times (e.g., DP-SGD algorithm [1]).\n\n3. For the analysis of the non-i.i.d. setting, I do not understand how this paper quantifies the degree of non-i.i.d. In previous work [2], the non-i.i.d. degree is explicitly characterized by introducing a parameter ($\\Gamma$). \n\n======== Reference ========\n\n[1] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in CCS, 2016.\n\n[2] X. Li, K. Huang, W. Yang, S. Wang, and Z. Zhang, “On the convergence of fedavg on non-iid data,” in ICLR, 2019.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster