Shuffle Private Stochastic Convex Optimization
Authors: Albert Cheu
Matthew Joseph
Jieming Mao
Binghui Peng
Venue: ICLR 2022 Poster (2022)
Keywords: shuffle privacy
stochastic convex optimization
differential privacy

Abstract: In shuffle privacy, each user sends a collection of randomized messages to a trusted shuffler, the shuffler randomly permutes these messages, and the resulting shuffled collection of messages must satisfy differential privacy. Prior work in this model has largely focused on protocols that use a single round of communication to compute algorithmic primitives like means, histograms, and counts. In this work, we present interactive shuffle protocols for stochastic convex optimization. Our optimization protocols rely on a new noninteractive protocol for summing vectors of bounded $\ell_2$ norm. By combining this sum subroutine with techniques including mini-batch stochastic gradient descent, accelerated gradient descent, and Nesterov's smoothing method, we obtain loss guarantees for a variety of convex loss functions that significantly improve on those of the local model and sometimes match those of the central model.

Published as a conference paper at ICLR 2022
SHUFFLE PRIVATE STOCHASTIC CONVEX OPTIMIZATION
Albert Cheu
Matthew Joseph Google Research mt. je.jossephgoooo com
Jieming Mao Google Research mac maojm@goog
Georgetown University ac2305@geerrgetowm.eeo
Binghui Peng Columbia University bp2601 0 @ww.emoiaaa.....mmmmm..mmm..a..e edu
ABSTRACT
In shuffle privacy, each user sends a collection of randomized messages to a trusted shuffler, the shuffler randomly permutes these messages, and the resulting shuffled collection of messages must satisfy differential privacy. Prior work in this model has largely focused on protocols that use single round of communication compute algorithmic primitives like means, histograms, and counts. We present interactive shuffle protocols for stochastic convex optimization. Our protocols rely on a new noninteractive protocol for summing vectors of bounded l, norm. By combining this sum subroutine with mini-bater stochastic gradient descent, accelerated gradient descent, and Nesterov's s smoothing method, we obtain loss guarantees for variety convex loss functions that significantly improve on those of the local model and sometimes match those of the central model.
INTRODUCTION
In stochastic convex optimization, a learner receives a convex loss function é: O X + mapping pairs of parameters and data points to losses, and the goal is to use data samples 21...., T, to find a parameter minimize population loss Ez-D [e(0, .x)] over unknown data distribution D. The general applicability of this framework has motivated a long line of work studying stochastic convex optimization problems under the constraint of differential privacy (Dwork et al. (006b), which guarantees that the solution found reveals little information about the data used during optimization.
This has led to guarantees for both the central and local models of differential privacy. Users in central differential privacy must trust central algorithm operator, while users in local differential privacy need not trust anyone outside their own machine. These different protections lead to different utility guarantees. When optimizing from samples over d-dimensional parameter space with privacy parameter e, the optimal loss term due to privacy is O dd((e)) in the central model (Bassily et al. 2013 2019 Feldman al. 2020). In the local model, the optimal private loss term is O ((Vd/(e//) For sequentially interactive protocols (Duchi et al. 2018) and a class of compositional fully interactive protocols (Lowy and Razaviyayn 2021).
A similar utility gap between central and local privacy also appears in many other problems (Ka- siviswanathan et al. 2011 Chan et al. 2012: Duchi al.] [2018] Duchi and Rogers 2019 Joseph et 20.1). This has motivated the exploration of models achieving a finer tradc-off between privacy and utility. One such notion of privacy is shuffle privacy (Cheu et al. 2019 |Erlingsson et al. 2019). Here, users send randomized messages to a shuffler, which permutes the collection of messages before they are viewed by any other party. In conjunction with work on building shufflers via onion routing, multi-party computation, and secure computation enclaves, this simple model has led to sow-substantial body of work on shuffle privacy (Bittau et al., 2017 Cheu et al. 2019 Erlingsson et al. 2019 Balle al.] 2019 Ghazi et al. 2021 Balcer and Cheu 2020 Feldman et al. 202 Balcer et al. 2021), including steps toward real- world deployment (Google 2021). However, comparatively little is known about shuffle private stochastic convex optimization.

---

Published as a conference paper at ICLR 2022
1.1 OUR CONTRIBUTIONS
We introduce sequentially interactive (cach user participates a single protocol round) and fully interactive (each user participates in arbitrarily many protocol rounds) variants the shuffle model differential privacy" This distinction is useful because, while full interactivity offers the strongest possible asymptotic guarantees, the practical obstacles to making multiple queries to a user over the duration of a protocol (Kairouz et al. 2021b 2019) make sequentially interactive protocols more realistic.
2. We construct a noninteractive shuffle private protocol for privately computing a sum with bounded & sensitivity. By using multiple messages, protocol is substantially more accurate than existing results (see Related Work).
3. We use our le summation protocol to derive several new shuffle private SCO guarantees (Ta- ble D via techniques including acceleration, Nesterov's 's smoothing method in the sequential interactive model, and noisy gradient descent in the fully interactive model.
Loss Function
Sequential
Full
Convex
0
22/3/2/3
d2/3
(Thm. 4.7
O
vd cm
(Thm. 4.9
d2/s
Convex and smooth
o
(Thm. 4.3
E47 2475
d2/3
Strongly convex
o
(Thm. 4.8
(Thm. 4.9
Strongly convex and smooth
O
zタn (Thm. 4.8
Table 1:
The guarantees proved in this paper. is the dimension of the parameter space O is the privacy parameter, and n is the number of data points. For neatness, this table omits the non- private 1/ //n term, logarithmic terms, and other parameters like Lipschitz constants, parameter space diameter, and smoothness. Full statements appear the referenced theorems.
1.2 ADDITIONAL RELATED WORK
The vast majority of work on shuffle privacy studies the noninteractive model, but few exceptions exist, [rlingsson
(219)) and Feldman al. (202I) study variant in which the shuffler is layer that accepts randomizers from the analyst, assigns them randomly to users, and sends the permuted messages back the analyzer. Feldman et al. (202T) also construct basic protocol for SGD this model. This model is similar to other work that achieves shuffle privacy guarantees by amplifying the local privacy guarantees of local randomizers (Baile et al. 2019) EElingsson al, (2020) also studied empirical risk minimization using ahmfiie-aplliiedd sequentially interactive locally private protocols. The main difference between that work and ours is that we only require that the view of the shuffled outputs across rounds satisfies differential privacy, and can therefore avoid relying amplification.
Another exception the work of Beimel et al. (222)), where the shuffler broadcasts the permuted messages all parties. Users then execute key exchange protocols, and Beimel et al. show that a first round of key exchange enables the use multi-party computation (MPC) to simulate any central DP algorithm in the second round. Our results depart from theirs in two ways. First, only assume that the shuffler sends outputs to the analyzer, not to individual users. Second, the MPC approach given by Beimel al. requires honest majority. Without honest majority, the differential privacy guarantees of their simulation fail. In contrast, the privacy guarantees of our shuffle protocols degrade smoothly with the fraction of honest users, which can be anything larger than an arbitrary constant (see discussion at the end of Section 3.T). Simultaneous independent work by TTnenbaum et al. (202I) also studies a sequentially interactive variant of the shuffle model in the context multi-arm bandits. Their model of sequential interactivity is identical to ours, albeit for different problem.
These borrowed from local differential privacy Duchi al. 2018 Joseph al.
2019
2

---

Published as a conference paper at ICLR 2022
Girgis et al. (2021) provide fully interactive shuffle private protocol for empirical risk minimization (ERM). In contrast, we provide both sequentially and fully interactive protocols for SCO, which optimizes population rather than empirical loss. Their &g summation protocol requires from each user, and its second moment guarantee for the average gradient has a 1/b dependence on batch size b (their Lemma 4). In contrast, our multi-message protocol obtains better 1 /B2 dependence. This is possible because our melti-message protocol does not rely on privacy amplification, and in particular circumvents their single-message lower bound (their Theorem 3). Kairouz al. (202Ib) study DP-FTRL, which uses a single pass, extends to nonconvex losses, does not rely on shuffling or amplification, and satisfies central DP. It is possible to adapt their algorithm to sequentially interactive shuffle privacy using vector sum protocol, though their O(d//4/ /vn) SCO guarantee is weaker than our Odd2/s/r/ /n2/3) SCO guarantee (Theorem 4.7
message
Concurrent work by Lowy and Razaviyayn (2021) study fully interactive shuffle private protocols with SCO guarantees matching ours (Section 4.2). There two key differences between their work and ours. First, they do not provide sequentially interactive protocols, Second, their fully interactive protocols assume that users can send messages consisting real vectors. This assumption difficult to satisfy in practice (Canonne et al. 2020 Kairouz et al. 2021a). As a result, our protocols (and most of those in the shuffle privacy literature) rely only on discrete messages.
Finally, several shuffle private protocols are known for the simpler problem of summing scalars (Cheu et al. 2019 Balle al., 2019 Ghazi al.) 2019 Balcer and Cheu 2020) and recent work has studied vector addition in the secure aggregation model Kairouz et al. 202 which assumes the existence of a trusted aggregator that can execute modular arithmetic on messages. We expand on this work by introducing shuffle private protocol for summing vectors with bounded lg norm, with noise standard deviation proportional to the &g sensitivity.
2 PRELIMINARIES
Differential Privacy. Throughout, let X be data universe, and suppose that each of n users has one data point from X. Two datasets X, X' E X are neighbors, denoted X ~ X', if they differ in the value of at most one user. Differential privacy is defined with respect to neighboring databases. Definition 2.1 (Dwork al. (2006b)). An algorithm A satisfies (e, d) diffffreret privacy if. for every ~ X' and every event Z, PA [A(X) E Z] S ef (AAXA(X)) E 2] + 6.
assumes that the algorithm A has "central" access to compute on the entire raw dataset, we call this central privacy for brevity. For brevity, we will often use differential privacy and DP interchangeably. At times, will also be useful to rephrase DP as divergence constraint.
Because Definition 2.1
Definition 2.2. The 6-Approximate Max Divergence between distributions X and Y is
Pr[X E Z| - Pr[Y E Z]
D (XIlY)
max (xsupp(X)=PxXee
log
Fact 2.3. Algorithm is (e, 6D if and only if. for all X X', D& (A(X)]IA(X') s
A key property of DP is closure under post- posseprocessing.
Fact 2.4 (Proposition 2.1 (Dwork and Roth 2014)). Fix any function f. If is (e, ddifffrrrre
private, then the composition J G.A A is also (e, 8) diffferreny private.
Shuffle Privacy. The shufile model (Bittau et al. 2017 Cheu et al. 2019 Erlingsson al. 2019)
does not require users to trust the operator of A. Instead, we make the narrower assumption that there a trusted shuffier: users pass messages to the shuffler, the shuffler permutes them, and the algorithm A operates on the resulting shuffled output, thus decoupling messages from the users that sent them.
Definition 2.5. A one-round shuffle protocol P is specified by a local randomizer R + y and analyzer A:y² - Z. In execution P on X, each user i computes Rossiiyossibl using public randomness and sends the resulting messages yi,1 1r.2,... to the shuffler S. reports ij to an analyzer. where ÿ is uniformly random permutation of all user messages. The final output of the protocol is A(T)-
We now define our privacy objective in the shuffle model, often shorthanded "shuffle privacy"'
3

---

Published as a conference paper at ICLR 2022
Definition 2.6 (Cheu et al. (2019) Erlingsson et al. (201 p= (R. is (c, o--sffffle differen- tially private if the algorithm (S R" [=)()==== ((1(( R(Xa)), i.e. the analyzer's 's view of the shuffled messages, is (E, d differenniilll private. The privacy guarantee is only over the internal randomness of the users' randomizers and the shuffler.
drawback of the preceding definition of shuffle protocols is that it limits communication one round. It is not possible, for example, to adjust the randomizer assigned to user i based on the messages reported from user i 1. This is an obstacle to implementing adaptive algorithms like gradient descent. We therefore extend the shuffle model with the following sequentially interactive and fully interactive variants. Sequential interactivity breaks the data into batches and runs a different shuffle protocol on each batch in (possibly adaptive) sequence.
Definition 2.7. Let Tr denote the universe of shufile protocol transcripts, and let R denote the universe of randomizers. A sequentially interactive shuffle protocol P consists of initial local randomizer Ro, analyzer A, and update function U: Tr + [n] R. Let Tr, denote the transcript after t rounds of the protocol. In each round of P, the analyzer computes (nt, R2) U (Tr,,1)) n, new users apply RR to their data points, and S shuffles the result and relays it back to A. At the conclusion of a T-round protocol, the analyzer releases final output A(Trr).
This formalizes the idea that the analyzer looks the past shuffled outputs determine how many and what kind of randomizers to pass to the next batch of users. Note that, in a sequentially interactive protocol, each user only participates in computation. More generally, we further allow the analyzer to repeatedly query users. This leads us to the fully interactive model.
Definition 2.8. A fully interactive shuffle protocol P is identical to a sequentially interactive shuffle protocol, except the update function : Tr -> 2 R selects an arbitrary subset of users in each round. In particular, user may participate in multiple rounds.
The main advantage of full interactivity is that it offers the strongest formal utility guarantees (see Section 4); the main advantage of sequential interactivity is that it is typically difficult to query user multiple times in practice (Kairouz et al.) 20216 2019).
For sequentially and fully interactive shuffle protocols, the definition of privacy is identical: the view of the transcript satisfies DP. The noninteractive definition a special case of this general definition.
Definition 2.9. Given shuffle protocol P, let Mp: X + Tr denote the central algorithm that simulates P on input database and outputs the resulting transcript. Then P is (e, 8)-suffle ( difffeerentillly private.
differentially private if Mp is (e,
Stochastic Convex Optimization. Let closed convex θ c Rd with diameter D be parameter space. We always assume loss functions E(0, 2) that are convex and L-Lipschitz θ.
Definition 2.10. Loss function f: ② x X' + convex in θ if. for all X, for all t [0, and 0, 0' E O, E(t0 + (1 t)0', .r) I tl(0, x) + (1 t)e(0', x). E is L-Lipschitz in θ for all X and 0, 0' E e |E(0, x)) ((0', x>] I T.110 0'
In some cases, we also assume that our loss function f is 8-smooth and/or X-strongly convex.
Definition 2.11. Loss function E: θ x X - IR is B-smooth over θ if. for every x: E X and for every 0, 0' = θ, [V((0, x²) Vi(0', =2)12 S B||0 0' 12 lg. l is A-strongly convex in for all X, for all t E [o, 1| and 0, E θ, E(10 + +(1 1)0"xz) x) < 1l(0 + +(1 - 1))(0', x) Ar(l-t)
0' 13
Our goal is to minimize population loss. We view each user as a sample from D, and our protocols learns through repeated interaction with the shuffler rather than direct access to the samples.
Definition 2.12. Let D be a distribution over X, and let f: θ x X + be a loss function. Then algorithm A: X θ has population loss EADDD [e(O, D)] Ee~Ay [E [e(0,
VECTOR SUMMATION
In this section, we provide shuffle private protocol PvEC for summing vectors of bounded & norm. This contrasts with existing work, which focuses on e sensitivity. PvEC will be useful for the gradient descent steps of our algorithms in Section 4 Pvvc relies on invocations of scalar sum protocol
4

---

Published as a conference paper at ICLR 2022
PID, one for each dimension. We describe this scalar summation subroutine in Section 3.1 then apply it to vector summation Section 3.2 Proofs for results in this section appear in Appendix
3.1 SCALAR SUM SUBROUTINE
We start with the pseudocode for PID. a shuffle protocol for summing scalars. As is generally the case for shuffle protocols, the overall protocol decomposes PID = (ID):AD)) into randomizer and analyzer components: each user computes a collection of messages ii ~> (2;( the shuffler aggregates and permutes these messages to produce ! E (0, 1) ((0+b)n and the analyzer takes the result as input for its final analysis AID(ū). PID uses the fixed-point encoding presented by Cheu ct al. 2019) and ensures privacy using generalization work by Balcer and Cheu (2020).
Algorithm 1 PID. shuffle protocol for summing scalars
1: Parameters: Scalar database X (.1,...,, ,n)) E [], g. (0,1/2)
2: procedure LOCAL RANDOMIZER RId(w)
3: Set - [
4: Sample rounding value 171 Ber(xg/A A-F) -)
5: Set & <
6: Sample privacy noise value 1/2 Bin(b. p)
7: Report è + copies of and + (i + 72) copies of 0
8: end procedure
9: procedure ANALYZER Aid (7)
Output estimator A (o+bb) yı) pbb)
end procedure
PID't 's privacy guarantee is instance-specific: for every pair of inputs, we bound the approximate max- divergence between output distributions as a function of the change in inputs. Previously proposed by Chatzikokolakis al. 2013), this property will be essential when proving that PvEC is private.
15, and 0 < d 1/2. Let g AVT. 180g In(28) ln(2/8)
Lemma 3.1. Fix any number of users
and p 90g" ln(2/8) Then I) for any neighboring databases X X' E [0, that differ b
u, D ((S (X))( Rx))("))) Se. Re (u-=-a) and 2) for any input database
X E A]" (ID(X) is an unbiased estimate of Ei= and has variance O log }
We defer the proof to Appendix A Claim follows first from the observation that the adversary's view is equivalent the sum of the message bits. This sum has binomial noise, which was first analyzed by Dwork et al. (206a)) in the context of central DP. We adapt work on a shuffle private variant due to Ghazi al.
2021 incorporate dependence the per-instance distance between databases. Claim 2 follows as straightforward calculation.
Lemma 3.1 holds when all n users follow the protocol. We call these users honest. possible to prove a more general version of Lemma 3.1 whose parameters smoothly degrade with the fraction of honest (see Appendix A.3 This robust variant of shuffle privacy was originally defined in work by Balcer et al. (2021) and naturally extends to PvEC-
The remaining analysis uses PID in a black-box manner. It is therefore possible replace it with a cwwer-communication subroutine for scalar sum (Balle et al., 2019).. However, this improved communication requires more complicated protocol with an additional subroutine. Our work focuses on sample complexity guarantees, so we use PID for clarity. Nonetheless, we note that each user sends + b Ra A n + A" (// bits in PID, and the analyzer processes these in time O((g + b)m) Scaling these quantities by yields guarantees for Pvec in the next subsection. Moreover, it is possible to remove the communication dependence on A by having users scale down their inputs by A before running PID, running PID if A 1, and then scaling up the final output by A to compensate; this does not affect the overall unbiasedness or variance guarantees. Improving the communication efficiency of these protocols may be interesting direction for future work.
5

---

Published as a conference paper at ICLR 2022
3.2 VECTOR SUM
Below, we present the pseudocode for Pvec, again decomposing into randomizer and analyzer components. Note that view the vector ! be the collection of all shuffled messages and, since the randomizers labels these messages by coordinate, Y, consists of the messages labelled j. The accompanying guarantee for Pvcc appears in Theorem 3.2
Algorithm 2 VVCC. shuffle protocol for vector summation
1: Input: database of d-dimensional vectors X (#1,-.. J.):: privacy parameters E, 8; A2.
2: procedure LOCAL RANDOMIZER (T,c(
3:
for coordinate j [d] do
4: Shift data to enforce non-negativity: Wai t- Eig (A2..... A2)
5: mi < RID (W),)
6: end for
7: Output labeled messages {(i, my)
8: end procedure
9: procedure ANALYZER AVEC(ī)
for coordinate j [d] do
11:
Run analyzer on j's messages Rj + AID(j.
12:
Re-center: 0j + 2j n
13: end for
14:
Output the vector estimates ō
15:
end procedure
Theorem 3.2. For any < E S 15, 0 < 8 < 1/2, n, N. and D2 > O, there are choices of parameters b,g g E N and E (0,1/2) for PiD (Algorithm 3.1 such that, for inputs X ".....,,,y
of vectors with maximum norm || S A2. 1) Pvec is (s, d) -shufffe private and, 2) Pvoc is an unbiased estimate of > I; and has bounded variance
(
dD E2
d 8
E
PVEC X
Σ b O
=
log
2
The proof relies on variant of advanced composition (Lemmaa 3.3). Although the proof follows many of the same steps prior work, the statement is somewhat nonstandard because it the divergence between two specific algorithm executions, rather than the worst-case divergence of generic differential privacy guarantee. This enables to use Lemma 3.1
Lemma 3.3. Fix any 7 E (0, 1) and neighboring databases X, X' E X". For all j E [d]. suppose algorithm Aj xm y use independent random bits and satisfies (A()
ej. Let
d E5(E - -1) + + 2 log(1/7)
d'=
Σ
and = > 8, +
1=1
1=1
Then D A,))))
Ax(x')) E..
We defer the proof of Theorem 3.2 to Appendix A.2 but sketch the outline here. For any neighboring pair of datasets, the j-th invocation of PID by Pvvc produces one of two message distributions such that the divergence between them is roughly proportional to the gap in the j-th coordinate of the input. This is immediate from Lemma The fact that we know bound on sensitivity allows to bound the (squared) f2 norm of the vector of divergences. This norm is implicit within Lemma 3.3 so the target theorem follows by re-scaling parameters and substitution.
CONVEX OPTIMIZATION
We now apply PvEc to convex optimization. Section
4. describes shuffle protocols that are sequen- tially interactive and solicit one input from each user Section 4.2 offers stronger utility guarantees
Since sequentially interactive protocols process data online, sequentially interactive shuffle protocols also have straightforward pan-rrivate Dwork al. 2010a) analogues with the same guarantces; Appendix C

---

Published as a conference paper at ICLR 2022
via fully interactive protocols that query multiple times. Complete proofs of all results in this section, along with communication and runtime guarantees, appear in Appendix
4.1 SEQUENTIALLY INTERACTIVE PROTOCOLS
Our first sequentially interactive protocol is simple instantiation of noisy mini-batch SGD, PSGD- This baseline algorithm achieves population loss O'd'// /VE)) (Theorem 4.1). which already im- proves on the locally private guarantee, However, in a departure from the central and local models, we then show that a still better (dd'/3 ((m))//3) loss guarantee possible (Theorem 4.7 using a more complex algorithm PAGD that smooths the loss function and employs accelerated SGD.
Convex f We start with PSGD. Because PSGD is sequentially interactive, for a fixed number of users n, the batch size b is inversely proportional the number of iterations T. As result, Theorem 4. chooses b to balance the noise added to each gradient step (which decreases with b) with the number of steps taken (which also decreases with b).
Algorithm 3 PSGD. Sequentially interactive shuffle private SGD
Require: Number of users batch size b, privacy parameter 6, step size 7,, Lipschitz parameter L 1: Initialize parameter estimate Bu E O and set number of iterations T n//b
2: for t = 2, do
3: Compute gradient at 1 Dt - - P 11,,) Vol(0-11.
4: Update parameter estimate 0g Th (0t-1 199t))
5: end for
6: Output 7 ΣT-10 O:
Theorem 4.1. Let loss function convex, T--Lipschitz over a closed convex set θ Ted of diameter ebD
D. 0 ΣT- 0g, b logg///88 T n/b, 1) LVT(ebb log(d/ō)} and 15. Then PSOD
is (e, -)shuueefflle private and has population loss
Exsao: D [(( < min E(0, () +)+ +0 Log log (d/0) (d/0))
8EB
VEn
Privacy-for PSGD and our other protocols, which all rely on PveC followsllos from the fact that the T--Lipschitz assumption ensures that loss gradient has la norm at most L.. The utility proof proceeds by viewing each noisy gradient step as call to a noisy gradient oracle. This enables us to use a standard result for gradient oracle SGD.
Lemma 4.2 Bubeck et al. (2015)). Suppose PSGD queries an Lg-noisy gradient oracle at each iteration, then its output satisfies [e(0, D)] S mingee E(0, D) +
D2
242
2n7
In our case, we can bound the noise level LG as a function of our problem and privacy parameters, including the batch size. We then choose the batch size minimize the overall loss guarantee.
Convex and smooth Next, we obtain a better loss guarantee than Theorem 4.1 when the loss function is also smooth. The key insight is that by using acceleration, better trade-off between noise level and number of iterations is possible. The resulting algorithm. PAGD, can be seen as a private version of the accelerated stochastic approximation algorithm (AC-SA) Lan (2012).
Theorem 4.3. Let f be convex, 3-smooth, and L-Lipschitz over closed convex set θ C Rd of diameter
D. Denote 0 = 60g Let batch size 1 2215 (d)))) L. = + ((T + 2)3/2
D - B),
2215ga/5 p2/5
0t t42: and ε < 15. Then PAGD (E,S)-shuffle private with population loss
DL
La/á ///5 14/5 (d/8)
EAAG. [((0 < min E(0, D) BE0
4/5m1/6
The proof of Theorem 4.3 is similar to that Theorem 4.1 oracle utility guarantee that is specific accelerated gradient descent:
The main difference is that we rely on an
7

---

Published as a conference paper at ICLR 2022
Algorithm 4 PAGD. Sequentially interactive shuffle private AC-SA
Require: Number of users n,, batch size b, privacy parameters e, 6, Lipchitz parameter learning rate sequence { [Lr] {ay}
Initialize parameter estimate 07 01 E O and set number of iterations T= [n/b]]
2: for t = 1,2....., do
3: Update middle parameter estimate 0pd + a;O, + (1 0r, )R.
4: Estimate gradient emmd 9t - Pvcc ( ,xt,1),
Voe(o .r,,)iE, L)
5: Update parameter estimate f2+1 f arg minøge { (ā.. 0 - 02) + 10 0c1l))
6: Update aggregated parameter estimate 0,4 + 0,0 + (1 a, 10.5
7:
end for
8: Output 0741
Lemma 4.4 (Theorem Lan 2012 ) Suppose PAGD receives a noisy gradient oracle with variance
(at most) a in each iteration. Taking L ++1 ((T + 2)3//2 B -3),at 142' then the expected error of PPAG AGD can be bounded as
BD T
Do
E [((0, D)) S min ((0,D) + +0 Age
Smoothing for convex non-smooth Perhaps surprisingly, when the target loss function is convex and non-smooth, the SGD approach of algorithm PSGD is suboptimal. We improve the convergence rate by combining the accelerated gradient descent method PAGD with Nesterov's smoothing tech- nique. In particular, for non-smooth loss function, approximate it with smooth function by exploiting Moreau- Yosida regularization. We then optimize the smooth function via PAGD- This not the first application of Moreau- Yosida regularization in the private optimization literature (Bassily et al.) (019),, but we depart from past work by combining it with acceleration to attain better guarantee. We start by recalling the notion of the 3-Moreau envelope, using the language of Bassily et al. (2019).
Definition 4.5. For B > 0 and convex f: 0 - R.d, the 3-Moreau envelope fa: 0 + RR. of
(1(' + - 11000'113
Sa(0) = min d'Ee
The following properties of the 3-Moreau envelope will be useful.
Lemma 4.6 (Nesterov (2005)). Let : 0 Rd be convex function, and define the proximal operator prox, (0) = arg mengree (f(0") + 1 - 0' (1)). For 3 >
1. fa is convex, 2--Lipschitz and B-smooth.
2. V0 θ, (f) B(0 prox, ;ro
_2 3. 4O E e, (0) < (0) < (0) + 23
Lemma 4.6 follows. First, claim enables optimize fa using PAGD- Inside PAGD. we use claim 2 to compute the desired gradients of fe and obtain a loss guarantee for fa using Theorem 4.3) Finally, claim 3 bounds the change in loss between fa and the true function as a function of B. We then choose B to minimize the overall loss guarantee.
Informally,
Theorem 4.7. Let be convex and L-piiphhitz over a closed convex set C Rdd of diameter and < 15. Then combining PAGD with the above smoothing method yields an (c,8)-shuffle private algorithm with population loss
DL
d DL 2/3
E [e(0, D) < min ((, +
Vn
2/3
Strongly convex function When the function is strongly convex, we use a folklore reduction from the convex setting: start from arbitrary point 0g O, and apply convex optimization algorithm
8

---

Published as a conference paper at ICLR 2022
k = Olog n)) times, where the j-th (j [k]) application uses the output from previous phase as the initial point and n, = n/k samples. apply the smoothing version of PAGD used in Theorem 4.7 In the strongly convex and smooth case, we apply the version of PAGD used in Theorem 4.3 A similar approach appears in the work Feldmaaan et al. (2020); the adaptation for our setting requires, among other modifications, more careful analysis of the optimization trajectory.
the strongly convex but possibly non-smooth case,
Theorem 4.8. Let be X-strongly convex and L-Lipschitz over a closed convex set C. R of diameter D and 15. Then combining PAGD with the reduction above yields an (E, 6h-suuffeee private algorithm with population loss
L2 An
L2
l/
E [(( Di] - min ((, +
REG
n/ 4/3
the loss function is also B-smooth, then the population loss can be improved to
L2a
dB L. (d/8)
[e(0, D)] min ((0, D) +
BE
An
23
4.2 FULLY INTERACTIVE PROTOCOL
We conclude with fully interactive protocols, which allow user participate in multiple shuffles. In this expanded setting, a version of PSGD obtains loss guarantees that match those of the central model of DP, up logarithmic factors. The pseudocode of our protocol PaD is shown in Algorithm For strongly convex functions, we further divide users into disjoint groups and apply a fully interactive protocol PGD each group in sequence, using the parameter estimate learned from one group the initial parameter estimate for the next.
Algorithm PGD. Fully interactive shuffle private gradient descent
Require: Number of users n, privacy parameters E, 6, Lipschitz parameter L, number of iterations T. step size
1: Initialize parameter estimate 0u + 0
2: for 1, 2, ., do
3: Compute the gradient at Oz:
gt - Pvec (vol(0,z1)).... Tel(0r,In))
2 2T T L)
E
4: Compute and store the parameter P + The (0, + ng))
5: end for
6: Output final estimate < -i-100 0z
Theorem 4.9. Let convex and Lipshiit over a closed convex set C Rdd of diameter and < 15. Then the protocol PED is (e, 8)-shuffle private with population loss
DL Vn
d/2 log
D)] < min E(0, ((0,D)+0 + E [e(0,
6EB
If é >-strongly convex, we can further improve the population loss to
I
d dlog (d/6)
E [(0 D)
< min 8(0, D) + +
lee
z2n²
Details appear at the end of Appendix B since the algorithm and analysis combines previously- discussed components, we sketch them here. The analysis employs the same Moreau envelope approach used in Theorem 4.7 However, unlike in the analysis of Theorem 4.7] we no longer require acceleration. Advanced composition and an appropriate setting of the parameters completes the result. For strongly convex function, we need to further split users into log log n disjoint groups and apply PaD these disjoint groups of users in sequence.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
We thank the anonymous ICLR reviewers for their helpful comments. Binghui Peng is supported by Christos Papadimitriou's NSF grant CCF-1763970 AF, CCF-1910700 AF, DMS-2134059 and a softbank grant, and by Xi Chen's NSF grant CCF-1703925 and IIS-1838155 Albert Cheu is supported in part by gift Georgetown University. Part of his work was done while he was a PhD student at Northeastern University.
10

---

Published as a conference paper at ICLR 2022
REFERENCES
Kareem Amin, Matthew Joseph, and Jieming Mao. Pan-private uniformity testing. In Conference on Learning Theory (COLT), 2020.
Hilal Asi, John Duchi, and Omid Javidbakht. Element level differential privacy: The right granularity of privacy. arXiv preprint arXiv: 291..9442.42422 2019.
Victor Balcer and Albert Cheu. Separating local & shuffled differential privacy via histograms, In iiformattion-hhorree Cryptography (ITC) 2020, 2020.
Victor Balcer, Albert Cheu, Matthew Joseph, and Jieming Mao. Connecting robust shuffle privacy and pan-privacy. In Symposium on Discrete Algorithms (SODA). 2021.
Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. Differentially private summation with multi-message shuffling. Arxiv, abs/1 0911//99900111110 16, 2019.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Foundations of Computer Science (FOCS), 2013.
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradcep Guha Thakurta. Private stochastic convex optimization with optimal rates. In Neural Information Processing Systems (NeurIPS), 2019.
Amos Beimel, Iftach Haitner, Kobbi Nissim, and Uri Stemmer. On the round complexity of the shuffle model. In Rafael Pass and Krzysztof Pictrzak, editors, Theory of Cryptography Conference (TCC), 2020.
Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld. Prochlo: Strong privacy for analytics in the crowd. In Symposium on Operating Systems Principles (SOSP), 2017.
Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 2015.
Clément Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differential privacy. In Neural Information Processing Systems (NeurIPS), 2020.
TH Hubert Chan, Flaine Shi, and Dawn Song. Optimal lower bound for differentially private multi-party aggregation. European Symposium on Algorithms (ESA), 2012.
Konstantinos Chatzikokolakis, Miguel E. Andrés, Nicolás Emilio Bordenabe, and Catuscia Palamidessi. Broadening the scope of differential privacy using metries. In Privacy Enhanc- ing Technologies Symposium (PETS), 2013.
Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. Distributed differential privacy via shuffling. In Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT)) 2019.
John Duchi and Ryan Rogers. Lower bounds for locally private estimation via communication complexity. In Conference on Learning Theory (COLTT) 2019.
John C Duchi, Michael Jordan, and Martin J Wainwright. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 2018
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 2014.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, 2006a.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference (TCC), 2006b.

---

Published as a conference paper at ICLR 2022
Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N Rothblum, and Sergey Yekhanin. Pan-private streaming algorithms. In Innovations in Computer Science (ICS), 2010a.
Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 51-60, IEEE, 2010b.
Ülfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. In Symposium on Discrete Algorithms (SODA). 2019.
Ülfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Shuang Song, Kunal Talwar, and Abhradeep Thakurta. Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation. arviv preprint wwXiv:2001006611 2020.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in linear time. In Symposium on the Theory of Computing (STOC), 2020.
Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In Symposium on the Foundations of Computer Science (FOCS), 2021.
Badih Ghazi, Rasmus Pagh, and Ameya Velingker. Scalable and differentially private distributed aggregation in the shuffled model. Arxiv, 2019.
Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, and Ameya Velingker. On the power of multiple anonymous messages. In Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) 2021.
Antonious Girgis, Deepesh Data, Suhas Diggavi, Peter Kairouz, and Ananda Theertha Suresh.
Shuffled model of differential privacy in federated learning. In Artificial Intelligence and Statistics (AISTATS), 2021.
Google. Cobalt: Telemetry with built-in privacy. http:s://ffucsii..ooo..soo. cobalt 2021. Accessed: 05-21-2021.
Matthew Joseph, Jieming Mao, Seth Neel, and Aaron Roth. The role of interactivity in local differential privacy. In Symposium on the Foundations of Computer Science (FOCS), 2019.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. arXiv preprint arXiv:1912.04997 2019.
Peter Kairouz, Ziyu Liu, and Thomas Steinke. The distributed discrete gaussian mechanism for federated learning with secure aggregation. In Neural Information Processing Systems (NeurIPS), 2021a.
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. In International Conference on Machine Learning (ICML), 2021b.
Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 2011.
Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Program- ming, 2012.
Andrew Lowy and Meisam Razaviyayn. Private federated learning without trusted server: Optimal algorithms for convex losses. arXiv preprint arXiv:2106.09779, 2021.
Yu Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 2005.
Jay Tenenbaum, Haim Kaplan, Yishay Mansour, and Uri Stemmer. Differentially private bandits in the shuffle model. arXiv preprint 10X.v:2006.02900.
12

---

Published as a conference paper at ICLR 2022
A PROOFS FOR SUM
The goal of this section is to prove Lemma 3.1 and Theorem 3.2
A.1 PROOFS FOR SCALAR SUM
We first state a technical lemma adapted from Lemma 4.12 in the work of Ghazi et al. (2021). Our lemma expresses divergence in terms of the per-instance distance between databases, which is necessary for the per-instance statement in Lemma 3.1
Lemma A.1. For any function f X -> and parameters p E (0, and m N, let Mm.... X" + E be the algorithm that samples n Bin(m,, p) and returns f(X) n. For any tE X X' such that (f(X) - -(X')) S t, and a E (0,1) where amp 2 2t,
D (M. f.f MX.
SE
where 1f(X) - f(X') In t and 6 2 eexp(=a²mip mp/ mp/10)-
Proof. Fix any of integers Z. We will show that
P [M (X) Z] s exp (15(X) ((x))-((X')) In 1 PP [M..p.(X) 2
+ 2 eexp(-a m0mmmmp111))
which is equivalent to the divergence bound.
For any integer i, we use the notation Z - i to denote the set fz - - il E Z}. Then
P pM (X) E Z)= = >
Bp [n = 2 - f(X)]
=EZ
Σ
P Pln(mmmpp))) In 11=1]
REZ-f(X)
Σ
Bin(m.))) (n =
Σ
Pr Bin(m.)) (1 = 2].
=E(Z-F(X))NQ
20Q
The last inequality holds for any set Q. Our specific Q is
Q { E
P (p-Bin(m.pp) [1] = g) po-Bin(m.))) (7 ((X) [(X'] < exp ((X') [2
Recall that we supposed [f(X) f(X') Sts ampp The following fact comes from Lemma 4.12 in Ghazi et al. (2021): for any & 1-,,4]
(in(Bimmm.))) in= Y 2 exp [Al In [too ) s 2exp(_a'mm)
Bin(m.p) [n = Y]
Py Bin(m))
Then by substitution,
Σ
exp ((1))-(xX)) In L-a I-a
P. By f(X) f(X')l
=E(2-1(x))ng
2 eexp(_aa2m 10)
Σ exp (1f(X) - ff('') In 1+ sE(2 (1X))n
Py.-Bi((mp)) In
1-a
eexp(-a2mp)
S exp (1f(X) - -((X') In [M..p.(X')) E Z] 2-22epp 2=xp((aammp/10)
1-a
With Lemma A.I in hand, turn proving our main result for scalar sum, Lemma
13

---

Published as a conference paper at ICLR 2022
Lemma A.2 (Restatement of Lemma p.1. Fix any number of users n, E S 15, and 0 < å < 1/2.
Let 2 AVR,
180g" In(2/6) and 90g" In(2/4) Then 1) for any neighboring databases S2 - x
be
X ~ X' E 10, A that differ on user u, D ((S o R (X))(( o Ri))(x))) S E. (3 ++
A
and 2) for any imput database X E [0, [0, the (I)(X) is an unbiased estimate of Ei=1 It and has variance O + A log }).
Proof. We first prove item On input X, the shuffler produces a uniformly random permutation of the (g + b)n bits y1.... b)n+ For each user i, let 2; be the sum of the messages sent by user i, 2; = ΣØ Di.j. Then the random variable for permutations of yl.-.. y1:-.-V(g-b)> can also be viewed as a post-processing of the random variable Z = Σi= Let Z' be the analogue of Z for input database X', differing in user u. Then by the processoosssing inequality, it suffices to prove D (2)l2') I E (2/9 + I l²)/A)).
By the definition of RID. Z is distributed as f. + Eiiz Ru + Bin p) while Z' is distributed as E + iinu En + Bin(bn, p). We have therefore reduced the analysis to that of the binomial mechanism. Our next step is to justify that Lemma A. T applies to our construction. Specifically, we must identify
/ and show p < 1/2, [... F' S I, and ammp 2 2/.
We set m = bn, = g. and a e/3g. Our assumption on b implies that p < 1/2. And the fact that i. o both lie in the interval [0, g] implies |é; 1 S g = t.. So it remains to prove amp 2 2t:
omm a: hm 90g² l2(2/))
b
a 90g² (2
g² ln
E > 2y (n(/))
(E < 15)
> 2t.
(6 < 1/2,t g)
Next, we derive the target bound on the divergence. Via Lemma A.1 we have that
(SS (X)]() (x') s é
where
1
In
1 a
< 6
H
3c
(a small)
g
1
Fa
x'y .9
<
2
(Discretization)
g
A
2
J'yl
A
and
= 2 exp(
(222 am2mm/10
10)
-a² 9. g² ln((1/)) = 8.
< cxx
E²
Moving to item 2, observe that the sum of the messages produced by user i is H, + +1) + 72- Since 771 was drawn from Ber(z,g/ A I,), [n]] x,g/ A I; and Var [m] < 1/4 since any Bernoulli random variable has variance < 1/4. Meanwhile, 772 is sample from Bin (b, p) so E Inal = bp and
Var [na] bp(1 - p) E bp. Recall our definition above of 2; ΣE Vh. Then E [=]] x.g/ A + hp
14

---

Published as a conference paper at ICLR 2022
and, by the independence of 7/ and 72. Var [2,] 1/4 + bp. Extending this over all users yields E EE zi| >i=1 24 + bmp and Var |i== zi| I n/4 + bnp. AId shifts and rescales this
quantity, its final output is unbiased
Σ
24
bmp
=
02
g
i=1
and, by our assumption that g 2 A Av and choice of p.
Var
A
g
Σ Y=1
2i
bmp)
g²
2
n
+
hmp)
=0(1
A
A
g²
=
A² log
A.2 PROOFS FOR VECTOR SUM
Having completed our analysis PID. we now turn to PveC- The first step in this direction is proving the following variant of advanced composition:
Lemma A.3 (Restatement of Lemma 3.3
Fix any Y 10, and neighboring databases X, X
X For all j E [d], suppose algorithm Aj x - y use independent random bits and satisfies
$ Eg. Lel
é' Σ C5(Efs 11) -1) 2 log (1/7) log(1/7)
Σ
and 8' = Σ6 8g +7 j=1
Then Do (Xi(X), AXXOIIX(X Aa(x') Se.
Our proof follows the steps in (Dwork et al. 2010b; Asi al. 2019) with minor adaptations.
We provide the detailed proof for completeness. We first provide some useful definitions.
Definition A.4. Given random variables Y and Z, the KL. Divergence between Y and Z is
Pr|Y y] Pr|Z
D(Y EyEY
log
The Max Divergence between Y and Z is
Pr|Y e S log
Doc (YIIZ) =
max SCsupp(Y)
Pr[Z E S
The total variation distance between Y and Z is
AY 7) max SCsupp(Y)
(Pr(S) -Px(())
The following lemma relating these notions comes from Dwork and Roth (2014).
Lemma A.5 (Lemma 3.17 17 and 3.18 (Dwork and Roth 2014)). Given random variables Y and Z.
1. We have both DE (Y] I and D& (2 ( Y) < if and only if there exists random variables Y' Z' such that A(Y,Y") 0/(e- + 1) and A(2, Z") < 8/(e= + 1), and
Dxc (Y'llZ)) < E, and D (Z'( S..
2. If D (Y
and D YZ then D(Y E( - 1).
For the first claim, Dwork and Roth 2014 only explicitly proves that D (Y' I2) I E, but their construction of y" and Z' also implies D (Z'[[(")) < s.
We now have the tools prove variant of advanced composition, Lemma A.3
15

---

Published as a conference paper at ICLR 2022
Proof of Lemma A.3 For any neighboring datasets X and X', let Y (Y, Yg.... Y2) and Z (Z1, Zz...., Za) denote the outcomes of running Aq...., A. on X, X' respectively. By Fact 2.3 and the first part of Lemma A.5 there exist random variables Y' = (Yi,..... ....... Y. and 2' = (Z) ................................ Z1) [d). the following four inequalities hold: (i) (Y Yj) I 6 + 1), (ii)
such that, for any j E
AZ2 2,) - /,/ (c5 + 1). (iii) Do (Y)1 I Ej. and (iv) Do 2 ())) S Eg. Then
83
E0; 8j.
e +1
Consider the outcome set B = (u E Rd Pr(Y" = r) 2 é²¹ Pr(z = v]}. It remains to prove Pr[Y" E B] S 7. For any fixed realization (V1,..., U1) E R2 we have
Pr(Y' Pr = v)
Pr|Y = 2زا Pr[Z) = wy]
log
log
- Σ 9
j=l
where the first step follows from independence and the last step defines Cj. Since Doe Z11 S E and Do (Z) E Ej. we know that |cyl I Ej. and by the second part of Lemma A.5
1oo8
Pr[y2
m/1 PriZz = vy] ]
Begny, [cy] = Besnyr
log
Sey(e5 - 1).
Thus have
Pr|Y's E B Pr
Σ
9j 26'
j=1
Pr
Σ 9 j=1
Σ ==1
(11 +2 ( 1og(1/1 1/7))
Σ of 3-
by Srrnoff-Hoeffdiigg bound. Tracing back, P PY E B S implies D% (Y'IZ')) - E'. Our previous bounds on AY,, Y!) and A(Z, 2') then give D ビ 6547 (YllZ) <
Finally, we can now prove Theorem 3.2 our primary guarantee for vector summation.
Theorem A.6 (Restatement of Theorem 3.2 For any 0 < E < 15, < 5 < 1/2, d, n E N, and A2 O, there are choices of parameters b, g N and p (0, 1/2) for Pid (Algorithm 3.1 such that, for inputs X (Ji,....5 F.) of vectors with maximum norm ||7: 2|2 S A2. PyEc is (e, 5)-shuffle private and, 2) (X) is an unbiased estimate of Ei=1 E. and has bounded variance
)
27
n
2 d (
d log
E
PvEC (X)
=0
22
8
Proof. We set max(2A n. Vd.4). We will choose b, p later in the proof.
Fix neighboring databases of vectors X and X'. We assume without loss of generality that the databases differ only in the first user, F + F. Then the & sensitivity is
n
Σ
प E1l12 2Ag-
2
From our definition of W. in line 4 of the pseudocode for PvEC and the fact that ||/|| S A2, Wij 2 0 and Wh, < | + A < || + A < 242. This means the sensitivity of the value of wis 2A2.
For each coordinate j E [d], we use aj to denote the absolute difference in the j-th coordinate,
aj = 1
|t -w1,)
16

---

Published as a conference paper at ICLR 2022
Let y, 6/(d + and é set b, such that
Because 9 2A2vn, may use Lemma 3.1 to
D& (SS (Wb)(W))llle Rib)(w))) S
2
0
2
where we use W to denote (Wi,5....
Wn.5) and the last step defines E.. Notice that
Σ
62
Σ
4
+
2aj
g²
22
4
sE|d]
jEId
4d
Filli
211
(Def of a,)
g²
2g
4A3
4d
2 d
Fill2
10 #
SEe.
g²
A2g
4
4d
4vd
+
(Via
9²
9
S
(4 4 1)
9
(3)
The final incquality comes from the fact that 3.3 to conclude that
2 Vd. By our choices of é, 7ys and d, we apply Lemma
D& ((S RV (X))l(S (X'))()))) S Σ
Eg(e55 -1)+2 2 log(1/>)
2 + 2
V
log log(l/7)
Σ ==1
j=1
< 18 + GE /og(111)
(Via (3)
6
(Choice of é)
which is precisely (e, dddifferenna privacy by Fact 2.3 Note that the second inequality holds
because g 2 4 implies ej S é S e/18. Since e S 15, we get Ej < 1, and e - S 28,-
The estimator produced by Pvac is unbiased because each invocation of PID yields unbiased estimates. And we have, by linearity and the variance bound PID.
E Prec
- Σ Z 1=1
E
(vec(X))
- Σ Dess 1=1
= =0
dA3 E2
log
)
1
j=1
The theorem statement follows by substitution.
L
A.3 ROBUST PRIVACY OF SUM
We now discuss the robustness our privacy guarantees, as mentioned at the end of Section 3.1 In more detail, slightly generalize the privacy analysis of PiD account for the case where fraction of the users are honest. Because PiD used as a building block for the other protocols describe, this robustness carries over. We first present the definition of robust shuffle privacy originally given by Balcer et al. (2021).
Definition A.7 (Balcer al. (002I). Fix E (0, A protocol (R, (s, 8, robbusly shuffle differentially private if. for all n andd 2 7, the algorithm SoR'a (e, -)diiferrettiall private. In other words, P guarantees (e, 0)-shuffle privacy whenever at least a fraction of users follow the protocol.
Although the above definition only explicitly handles drop-out attacks by 1 1 malicious users, this without loss of generality: any messages sent to the shuffler from the malicious users constitute a post-processing of S pm
17

---

Published as a conference paper at ICLR 2022
Now, show that reducing the number of participants in Pio loosens the bound on the divergence in a smooth fashion. Because PID is the building block of our other protocols, they inherit its robustness. The statement requires 7 2 1/3, but this constant is arbitrary; changing it to different value will only influence the lower bound on
Claim A.8. Fix any Y E [1/3, 11. any number of users E S and 0 < < 1. Ifg 2
g² In then, for any neighboring databases ~ X' E [0, b > 180 x² In 2. and p = 90 betn
sôn that differ user
D ((S R RDD RTD)( _
(2 9
Eu 2'u
A
This implies PID satisfies (0(e/)), 8, -robust shuffle privacy.
Proof. The proof proceeds almost identically with that of Item 2 in Lemma 3.1 The key change is that privacy noise is now drawn from Bin(ybn, p). This means take ybn We again set t t= but now a = E/3yg. Note that a < 1/3 because E S 1 and 7g > 37 > 1.
As before, assumption b implies that p < 1/2 and we have ja_ x g t. So it remains to prove omp 2 21. in order to apply Lemma A.I
90g² ln(2/))
90,² In(00)
30g ln(2/5) 21
ompp = a ybn
b
2²
Now we derive the target bound on the divergence. Via Lemma A.
we have that
De ((S (X)](S) (X))) é,
where
1 a
ju
H/ In
1- a
$
1.
Hy 30
(a small)
γ
Fn x'ul .9
S
+
(Discretization)
A
8
2
x'y1
9
and
= 2exp( -a a mp/ 10)
g² ln(2/8)
2exp( -a² 2 97
g²
= 2exp( - In(2/5))
< 2exp (In((20)) 8
This concludes the proof.
When we replace in the proof of Theorem 3.2 with e/n, following statement about the robust shuffle privacy of PvEC-
invoke Claim A.8 derive the
Corollary A.9. For any 0 < < 1, 0 < 6 < 1, d, n E N, and 42 0, there choices of parameters b. N and p E (0, 1/2) for PID (Algorithm
3.1 such for inputs X = (FI.... H.)
of vectors with maximum norm ||7.1|2 2| < A2 and any E 11/3, 11, Pvrc is (8/7,, 6, rroobuuslly shuffle private
Because PVEC serves as a primitive for our optimization protocols, each round of those protocols ensures privacy in the face of two-thirds corruptions. For comparison, the generic construction by Beimel et al. (2020) is able to simulate arbitrary centrally private algorithms but requires an honest majority.
18

---

Published as a conference paper at ICLR 2022
B PROOFS FOR SECTION
B. PROOFS FOR SECTION
We start by proving the guarantee for PSGD, Theorem The first step is to formally define the gradient oracle setup that will be necessary for several of our results.
Definition B.1. Given function over θ C Rd, say G: θ + F is Lg-noisy gradient oracle for for every E @ (1) Eg [G(O] E de( and (2) Ba || the gradient oracle G has variance at most o² Ea [[]G(A) Ea
S Lg Furthermore, we say
The following lemma is standard for (noisy) stochastic gradient descent.
Lemma B.2 (Restatement of Lemma 4.2). Suppose PSGD queries an LG-noisy gradient oracle at
each Meration, then its output satisfies
D
nLe
E [e(0, D)) < min mine(0, D)
+
9EB
21/T
We now have the tools prove Theorem
Proof of Theorem 4.7 The privacy guarantee follows directly from the privacy guarantee of the vector summation protocol (see Theorem 3.2). and the fact that the algorithm queries each user at most once.
For the accuracy guarantee, our algorithm directly optimizes the excess population loss. For each time step 10.1,.... 1}, we write the gradient Ir Em= Vgl(O:-1, + Z,. By Theorem 3.2
we know that
B 11 [0c] ENND (ol(Or-
and
Ex Exg, 2om Pe, [100112] = En, Er. Bt.
((00-11,3 + Zr
1=1
E Ly
Vol (0--1, x(,1)
+ +E
|
(dL
1.2 + 0
(4)
82g2
where the second equality uses the independence of the data and noise, and the inequality follows from & being T--Lipschitz and Theorem 3.2
The gradient Je therefore qualifies as noisy gradient oracle call with 43 L + O
(dL3 log (d/8)
By Lemma 4.2 and the fact that there are n/b iterations, we get
D2
[e(0, D)] < min ((0, D) +
6E0
2nT 2
DLG
min ((0,D)
(AM-GM ineq.)
BE0
VT
ddL"log"
dL2 log (d/8)
min {(0, D) + DV T dee
12+0
12g2
b
min {(,, D) 0 de0
DL
(T = n/bb
22b
d/4 Dog"oo 1/2 (d(/)
min ((0, D) O
Ven
19

---

Published as a conference paper at ICLR 2022
The final step uses our choice of v log(d/6)
Next, we prove the guarantee for PAGD, Theorem 4.3
Proof of Theorem 4.3 The privacy guarantee follows directly from the privacy guarantee of the vector summation protocol (see Theorem 3.2 and the fact that the algorithm queries each user at most once, and the remaining computation is post-processing.
We now prove the accuracy guarantee. For any iteration [T]. let Ze be the noise introduced by the summation protocol Vec and let D. = Ei= Vol(0--1.21,) + Z, We first bound the variance:
E [[]G(0,-1)
E (((()=1))
V Vol(O + Zi - -EEDD (e((0-11, x)
6
iml
b
-Be
Σ
(((0=-1,2(,) BEND [V((0=-1,2]]
+ 1
1=1
b
Var
Ve(02-10 F2,s)
+E [1
i=1
Var VE(00-1,, + E
Zz
b
1
[VV((0-11
Ex
[((0,-1,
=1]1 + [
211
1.2
dL. log2 log
(5)
62
The second equality comes from the fact that the data and noise are independent, the fourth equality uses the independence of 2r,1,--, Rd and (5) follows from Theorem 3.2 Next, we use the following result from Lan (2112).
Lemma B.3 (Restatement of Lemma 4.4). Suppose P AGD receives noisy gradient oracle with variance (at most) o² in each iteration. Taking L = ++1 ((T + 2)3/2g 3), 0, -42 population loss of PGD can be bounded as
2 then the
3D2 T
Do
E [[(0,D)]
S min ((, + DEG
+
VT
In our case, we have a² 12 +
dI Ing (d/8)
that
6²
B1)
Do
[e(0,,D]]
min (0, D) +0 o=0
+
T2
VT
BD2
DV
D
L2
dLa (d/b)
b2g2
min (0, +0
+
o
T2
VT
(BD2
DL
min (0,, D) + leo
+
+
T2
VbT
BEVT
123D2
DL
VdDLlog(d/0
min (00, D) + + #ee
n2
Vni
eybn
L/5/1//5 6
I,/6 log
4/5
(d/5)
DL Vn
min (), + l20
4/5
The first step follows from Lemma 4.4 and the second step comes from Eq. (5). In the last step, we substitute b n3//2t/0 12/5 (d//)
20

---

Published as a conference paper at ICLR 2022
Next, prove improved guarantee for convex losses by combining PAGD and smoothing (Theorem 4.7).
Proof of Theorem 4.7 We directly optimize the loss function Lg with PAGD. PAGD only requires the gradient ve mm x) (t E [T]). By the second item in Lemma 4.6 this can be obtained by computing ( (Omd)) )). Moreover, since lg is 2L-Lipschitz, PAGD still guarantees (E, 8--iifferential
3( p /
privacy with a constant scaling of the noise. For accuracy, we have that
L
E [ D)] min ((0, D) S E [es(0, D)]
min la(O, D)
FeB
BEB
B d=/ / D 6/5 1, 1,55 log 4/5 (d/8)
DL
1
+
vn
24/3
B
DL
DL 22/3n2/3
log (d/6)
0
vn
The first step follows from the third item in Lemma 4.6 the second step follows from the guarantee of PAGD (Theorem 4.3 and the fact that Eg is ff-mmooth and the last step comes from our choice of
d-/3 log (dfo)"
Finally, we prove Theorem sequentially interactive protocols.
4.8 which applies to strongly convex l and the final result about
The privacy guarantee follows from the previously-proven privacy guarantee for PAGD and the fact that we split the users into disjoint subsets. The rest of the proof focuses on the population loss.
Proof of Theorem 4.8
We begin with the non-smooth setting. The high level idea for this case is that both the population loss and the distance to optimal solution shrink in each iteration. By recursively applying the shuffle private convex algorithm and solving the recursion, one can get improved convergence rate. Let 0g
be the output of the i-th phase and d arg minøge {(0, D). Denote D E [|0, [ and
A; = E [e(,,, D) - E(00, D.
Due to the A-strong convexity, we have D < 2 Since the guarantee of Theorem 4.7 uses D as bound on the distance between the starting point and optimum, we have
A+t1 SC
(DL (Tn
+
A/3 D/3 bogg
2//
(d/)))
2/3
24:
(4
C
Vn,
L
1 L Log 2/3 (d/0) 2og
2/ 2/3
A
Here C' is an universal constant, and the last step defines E. Hence, one has
D E
A
E
We know that A < 2L2/X / (due to strong convexity), E² > 2L2 / (due to definition), and therefore, A E² < Onn). Hence, after (log log n) phases, we have A < and the population loss is
//3 L log 2/3 2)
L
E ((0
< min ((, + l50
T4k
2//3 n
2/3
L2
2/3 log
1/3 (d/0)
< min ((0, D) + δ
+
#E0
An
4/3
21

---

Published as a conference paper at ICLR 2022
This completes the proof for the non-smoote setting. Turning to the setting where is also 8-smooth, let A d=/6 ///0 log4/6 (d/0). Then our algorithm guarantees
g4/5
AD 4/5
6/5
LD;
AA, 3/5
LV
441 SC
2C
(6)
Vng
A3/5m
4/5
Vnn,
for some constant 1.
First, suppose there exists i [k] such that A, is already small, i.e.
1,2
45/2
A, x C
T.
Amg
13/2n2
Then we claim A $ 04
L2 Ang
//2 A3/3
holds for all i. We divide into cases.
Case 1. Suppose
La
4//2 23/2n
Then we have
An;
A
LA4/44
Ait1
4C
+
C
3/2 X2/3n
X5/
A
A5/2
4C
28
+
X2/3n²
X2/3n2
A5/2
< 0
X3/2n1
The first step follows from Eq. (6. = ni+1 n/k /k, the second step follows our assumption.
Case Suppose
La
45/2 1372m
Then we have
An;
AL6/5
L
5415A0. 40
C
10/5
7/5
Xn++1
L
C L?2
$ 40
28
+
An;
An4
La
< c
An;
The first step follows from Eq. (6) n4 11++1 n/k, the second step follows assumption.
then we claim that A++1 is decreasing, i.e., A1+1 S A,. Suppose this does not hold, since we have one of the following should hold
Next, suppose A; < T = c
Xn;
1.2
+
33/2 X3/2m
AA 3/5
A;
LV
A 2
2C
2C
33/5
4/5
We argue this can not happens, since the former one implies A, < 5522 40/2 X
and the later implies
Am. A; < 22 L
Combining the above argument, know that A; is decreasing, until it goes below a threshold T' and after that, the value A, will always below such the threshold T. Now, suppose after l: = Olog log n) iterations, A is still above the threshold T, then we know (As)ee(a) is decreasing and we divide the
algorithmic procedure into two phases. In the first phase, we have LVA. <
VAn X3/o 475 this happens
3/3/5
when A; 2
and the algorithm satisfies 2
_
A43/5
3/3/5
A S 4C
4C
13/5m
4/5
23/5m,
4/5'
22

---

Published as a conference paper at ICLR 2022
For the second phase, we have LVA. vAn
X3754470 and this happens when this happens when A; S
AA3/5
A and the algorithm satisfies n
LVA.
LVA.
A 4C
40
Vxn++1
Vnn
We know one of the two phases will run for more than Qilog log n) iterations. Suppose the former
5/2
case holds, i.., A++1 I 40
23/6n
AA//
1/5-
Let E
X3/6n
ACA
475
25/02/2
x
A
Then, have
A+t1 A
3/5
E
E
easy to verify that A E S poly(n), and therefore, after 2loog log n) iterations, we know that A; will drop below O(E) 2
44/2
T.
When later case holds, i.e., Ai+1 I LV
Let = 16C L² Am,
then we know that
VAn,
A 1/2
A
E
E
It is easy to verify that A & poly(n), and therefore, after (loog log n) iterations, we know that A; will drop below O(E) 16C L²
An. <.
In summary, taking k =Soolo log rt), we know that
L
A5/2
E [[(0,, D)] min ((,, D) 4 S TT= 20
Ang
13/2n1
12 log(d/6)2
2 +
An
2
This concludes the proof.
B.2 PROOFS FOR SECTION 4.2
We now turn proofs for our fully interactive protocol, PGD. The first step will be proving B.6ma|B.6] which provides a privacy and population loss guarantee for PoD when the loss function é smooth. We will later combine this analysis for smooth losses with the smoothing trick used in the previous section to obtain guarantees for non- non-smooth losses. Since POD passes the training data more than once and does not directly optimize the excess population loss, the proof of Lemma B.6 proceeds by bounding the empirical loss and the generalization error separately. First, we recall result bounding empirical loss.
Lemma B.4 (Bubeck et al. (0155). Let e be convex and T--Lipschitz closed convex Q Rd of diameter D. Let a² denote the variance of the privacy noise in the gradient update step of PaD- For any set of data points S and n > the output of PGD satisfies
2
(I2
+ 02)
E [((0,)) min ((0,S) <
+
#E0
2n
2
Next, we bound generalization error.
Lemma B.5 (Lemma 3.4 (Bassily et al. 2019)). Suppose & convex, L-Lipschitz, and 3-smooth over closed convex set θ C. Te of diameter D and S 3.2 Then PED is c-uniformly stable with
TT In other words, it satisfies
ESnDE [1E(0.5) E(0, D)I $ 1 Tn
23

---

Published as a conference paper at ICLR 2022
With these two tools, state and prove Lemma B.6
Lemma B.6. Let be convex, L-Lipschitz, and 3-smooth over closed convex set è C R of diameter D. Then PoD is (E, 8)-shuffle private with population loss
DL d DL
d log 3/2 (d/8)
E [e(0,
D)]
min (0, +0
le
Vn
ET
Proof. For the privacy guarantee, since each iteration guarantees
2 27 T+1 differennial
privacy, and the algorithm runs for T iterations in total, advanced composition implies (e, -h-shefe privacy overall.
We now focus on the loss guarantee. First, by Lemma B.4
the empirical loss satisfies
D
nLC
E [e(}:S)]
< min E(;: S)
+
21/
1
nL?
IdT L² log" (nd/o)
min {(;; S) lE
+0
2//T
2
2n
where the second step follows from L3 < L² + O
LT (nd/6) (see Eq. (4). Moreover, by
2 n²
Lemma B.5 we know the generalization error is most
Hence, for S ~ D",
E [)]
min E(0,D) SE [le(0, D) - (), + E(O,S) min C(), S) BEB
D
nT?
qdT T.2 loggg/ddd// (nd/o)
+ I,² Tn
2TyT
2n?E2
n
DLy dllog (nd/5)
DL
0
en
The second step follows from Lemma B.5 and Lemma
4.2
Especially, take expectation over e²,
~ D in Lemma 4.2 The last step follows by taking use 8 < 1/n for the final statement.
LVT and = min(n, (nd/)))) } We
We can now prove Theorem As done previously, we use Moreau envelope smoothing to apply the guarantee Lemma B.6 For the strongly convex case, we apply the same reduction the convex case as used by Feldman et al. (2020).
Proof of Theorem 4.9
The privacy guarantees are inherited from Lemma B.6
We employ Moreau
envelope smoothing, as described in Lemma 4.6 and used earlier in the proof of Theorem 4.7 to
construct &g with = 1 min (Vi,, ax/2 log (o/3/ Optimizing ég yields
ESND" [e(0: D)]
min ((0,D) D)
L
< ES [6: D)]
min (0 D) + 6EB
2/
DL
1/2 DL 3/2
(22 (d/6)
1
/ log
log
3/2 3/2 (d/8)
0
+ LD.
+
Vn
en
2/n
2
DL
1/2
Q2/2DL log 3/2
Vn
en
The first step follows from the third item in Lemma 4.6 and the second step follows from Lemma B.6 and the definition of B.
For strongly convex losses, the same reduction (Feldman al. 2020
24

---

Published as a conference paper at ICLR 2022
Lemma B.7 (Theorem 5.1 in (Feldman al. 2020 Suppose for any loss function that is convex and L-Lipschitz over a closed convex set è R of diameter D, there is an (E, (E,8) -.ff))reereentiallyy private algorithm that achieves excess population loss of order
1
vd
LD
VT
pm
Then for any X-strongly convex, L-Lipschitz loss function, there is an (dfffddifferenttiall private algorithm that achieves excess population loss of order
L
1211d À
-
p pn2
We note that this reduction works for the fully interactive model and keeps the privacy guarantee. In particular, one can divide users into the same set of groups as (Feldman et al. 2020) and apply PGD sequentially to these groups. By taking (nd2/)( we get the desired guarantee for strongly convex functions.
B.3 SCO COMMUNICATION AND RUNTIME
Recall from the discussion at the end of Section 3.1 that, with the scaling by A trick, each user sends Old[vn + ( /=2) bits in each n-user invocation of Pvcc, and the analyzer processes these in time O(dn( + log(1 /e)) Communication and runtime guarantees each for SCO algorithm then follow as simple corollaries based on the number of rounds and the batch size in each round.
Corollary B.8. the algorithm described in Theorem 4.1 each user sends Odd log(1 log(1/5)/ee) bits and the total runtime is
o odn [ob++b++ 1og(1/0))
E2 (
100(///0)==0
dn d'/4 log(d/8)
log(1/5)
g2
Corollary B.9. In the algorithm described in Theorem 4.3 each user sends O ( 1og(1)))) bits and the total runtime is
o dn VV++ 1og(1/0) E²
-000) dn
//100 n 1/10 1,1/ 1/ (d/88)
log(1/0)
+ e2
2//5///551/5
Corollary B.10. In the algorithm described in Theorem bits and the total runtime is
4.7 each user sends Old / log (1//(1//)))) (1/))/22)
o nd Vb Vb+ log(1/6) =0 (
nd /6 1/6 log (d/08)
log(1/8)
e//
e2
Note that the preceding corollary omits the time complexity of the smoothing step. A short discussion of doing this efficiently appears in Section 4 of the work of Bassily et al. (2019). Corollary B.11. the algorithu described Theorem 4.9 each user sends
o
( V (
log(1/5) E²
1) min
}.0( va log(1/0) n. d dog 2llog(nd))) (nd/8)
22n2
8²
bits in total, and the total runtime is
o ( (nnT [v++ 1og(1/8))
/
min {
( d dlog dlog((nd }
e2n²
(0 dn vn log(1/0)
/
x²
E2
C PAN PRIVATE CONVEX OPTIMIZATION
Finally, we turn to pan-privacy, where we assume users/data arrive in a stream, and the goal is to guarantee differential privacy against a single intrusion into the stream- peounn-poeessing algorithm's 's internal state. We formalize the model and provide definition in Section C.I and provide algorithms in Section C.2 Pan-privacy was introduced by Dwork et al. (2010a); we use the presentation given by Amin et al. 2020) and Balcer et al. (2021)
25

---

Published as a conference paper at ICLR 2022
C.I MODELS AND DEFINITION
Our focus will be on online algorithms. They receive raw data one element at a time in a stream. At each step in the stream, the algorithm receives data point, updates its internal state based on this data point, and then proceeds to the next element. The only way the algorithm "remembers" past elements is through its internal state. The formal definition we use below.
Definition C.1. An online algorithm Q is defined by an internal algorithm QI and an outpur algorithm Co- Q processes a stream of elements through repeated application of QI : X x I + I, which (with randomness) maps stream element and internal state internal state. At the end of the stream, Q publishes a final output by executing Qo on its final internal state.
As in the case of datasets, we say that two streams X and X' are neighbors if they differ in at most one element. Pan Pan-privacy requires the algorithm's 's internal state and output to be differentially private with regard to neighboring streams.
Definition C.2 (Dwork et al. (2010a); Amin al. (2020)). Given an online algorithm Q. let (x denote its internal state after processing stream X, and let X be the first t elements of X. We say Q is (e, -a--8))--pppaa aun-private if, for every pair of neighboring streams X and X', every time and every set of internal state, output state pairs T CI x O,
Pe (Xxx( (x()r(X))) E TT] s .P (Qx(())) Ro(2((X))))) e TT] + (7)
When 8 O, we say Q s-pan-private.
C.2 ALGORTHTS
Due to the structural similarity between sequential shuffle privacy and pan-privacy, all the results developed in Section 4.1 have pan-prive ann-private counterparts.
Theorem C.3. Suppose convex loss function is L-Lipschitz over a closed convex O C RR
then there exists an algorithm with output 0 that guarantees (e, 6 privacy, and:
(1) When the loss function is non-smooth, then the population loss satisfies
((, < min 8(0, D) () + DL d DL /3 (L/0)
(
BEB
2/33
(2) When the loss function is 3-smooth, then the population loss satisfies
((,, D) < min E(, D) + DL
d2/5
31/3 ///3
66/5 1,4/5 log
2/5 2/2 (1/8)
4/55
(3) When the loss function is X-strongly convex, then the population loss satisfies
L
223 log lo/
((0, D) < min E(O, ((0,D) D) +
e50
An
4/3
(4) When the loss function is X-strongly convex and 3-smooth then the the population loss satisfies
+ + L2
d log(1/6)
E(0, D) < min 6(,, ((0
W
An
X3/2g2m2
Proof. We analyze the pseudocode presented Algorithm Although it does not explicitly obey the syntax of online algorithm given in Definition C.1 is straightforward the tuple (0,, 8th fmm J.) and an update to J. occurs when any data point is read. The updates to the 0 variables also occur after the last data point of batch is read.
that the internal state
We first prove Algorithm 6 is (s, 8)-pan private.
Lemma C.4. For 0 < 8 < 1, Algorithm 6 is (e, pappaaa-rive
26

---

Published as a conference paper at ICLR 2022
Algorithm 6 Pan-private AC-SA
Require: Batch size privacy parameter E, stream length 7t, learning rate sequence {Lr). {ar)
1: Initialize noise parameter X² s1." (2g(2/8)
2: Initialize parameter estimate 87 01 O and set number of iterations T = |n//b]
3: for ( 1, ,,, , do
4: Draw fresh noise Z. N (0, <2
5: Initialize gradient estimate 9t < Ze
6: for i 1....... b do
7:
Update gradient estimate 9: t Dt + Vol(Ord I(,e) end for De + + (0,
8:
9:
10: Update parameter estimate 0z+1 arg mingee { (er, 0 -0) 10 0. 0,112
Update aggregated parameter estimate 0 + a,0++1 + (1 at )0
12:
Update middle parameter estimate 0,4 <- a,0++1 + 01 00E
13:
end for
14:
Output 07+1
Proof. Let t" (resp. i²) be the batch number (resp. position within the batch) where the adversary intrudes. We will show that
(0r, 6, 0,5,07 0Td Ir., 177+1116.... 0,44.,,,4 0. 0 F... 67 S
where the indicates variables generated from an execution on neighboring stream X'.
For neighboring streams X', let t denote the batch number and let denote the number of the sample within the batch where the two streams differ. We will perform case analysis around
Case 1: t" < t. Here, the tuple (0r., , 0nd Jr-) is identically distributed with (0/-.0%' which means we only need to prove D (0T T+1 [094 SE
1 , F(-)
Observe that 0 (resp. 07 ') is a post-processing of (0,, ,,,, ,0md (rnd (resp. (0/, 001 00md . J.)), which means that only need bound D (6,, 0:0h em Jel10', 0:E 6md I.)) Furthermore, the parameter estimates are generated from a post-processing of the gradient updates, it suffices to bound DÅ (9lll after line 9. Recall the Gaussian mechanism:
Lemma C.5. For e < 1 and function f: A + Bd on size-n databases with Ez-sensitivity
A2(5)
max
(Iʃ(a) f(a')(()
neighboring E..
outputting
f(a) 1o)+N(() (0. 2 (0,5+N(,.6//8 It
where La is the d-dimensional identity matrix, is (e, centrally private.
For proof, refer to Theorem A.1 in the survey of Dwork and Roth (Dwork and Roth 2014).
Since f L-Lipschitz in f, for any x we have l| 1) S L. Thus
max n. Ex
/1 Vol(, Il1 s 2L.
Thus if we define f ( Ft.b) follows that our addition of Z, N (o. 8L* (2g(2
E Vol(O,, we get A²()) S 2. By Lemma C.5
noise guarantees (e, (E, -ppivvyy
6
Case 2: 1" t. We break into more cases around a".
When <- < b, the adversary only observes change the gradient (line 7). Specifically, the tuple (f2-, 8-5 gmd 005_)) is identically distributed with (6'.,, 0:5 1,0md 8 ') which means it suffices prove 5 (g.llg) < é after line 7. This follows from the privacy of the Gaussian mechanism.
27

---

Published as a conference paper at ICLR 2022
When i I b = i", observe that the parameter updates are post- post-processing of the gradient update. We again use the privacy of the Gaussian mechanism.
When 1"
re-use the arguments from Case 1. The noise from line 9 provide privacy.
Case 3:
t
Observe that 07 (resp. 0f+1) ) a post-processing of
gm T..) (resp. (0',. 67 1 : Opr ...-)) D) which means that we only need to bound
Do (0z., fe fite Te. 10/-, 0:5", Op ...)), But the random variables in question are obtained by
post-processing (0,, fe 0r -ee) and (6, 0: ".0mdd. .g)). We use the same line of reasoning as Case
I to bound the divergence.
The main tool for utility guarantees bounding the variance of the noise added for privacy, analogous to the variance guarantee Theorem 3.2 Once we have that result, the remaining analyses essentially unchanged from their shuffle counterparts, apart from slightly different choices for parameters b and B, which are straightforward algebraic consequences of the different variance guarantee. As result, we only bound the variance.
For each time step E [T), the gradient 9: 1 E.= (o Zz, + Zt where Zt,,, Zeb ~ N (0, is clearly an unbiased estimator and the variance satisfies
E 11.
a oe((,-1, + Zz, + Zr EEED [V((O,
b
b
27
Er
1((0--1, - ExND [V((0,-1,
+ E Zr.
+
E
ZZ 1
BENDD
[VV((0-1,
E. [V((0-1,,))]1
+E Zr,a
+E
| 1
1.2
dL, log(1111))
+
b
b2g2
The first step follows from the fact that the noise a, Ze, independent of the data "". Fr, and the second step follows from the independence of Tt,1," Lt,b. The last step follows from Zr Z,, ~ N (0, and <² + SL3 (og(2/8)
28


Reviews:
[{"review_id": "_zNuydBBR3M", "reviewer": "Reviewer_6c6H", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The main strength of this paper is that, to the best of my knowledge, it is the first paper to show that there is a non-central DP setting (the full shuffle-DP setting described earlier) in which one can achieve the same excess population bounds as are possible in the central DP setting for SCO. The authors also show that in the weaker sequential model, one can still get improved excess population loss compared to the local setting. In summary, these results nicely and newly fill the gap between what is possible in the (non-shuffled) local and central settings for private SCO. I also think it is very nice that the same vector sum estimator is able to be slotted into a variety of different algorithms, and view this as a strength of the paper - it is possible that for other SCO algorithms which have been tried in the central DP literature that improve over SGD under various assumptions, one can slot in the vector sum estimator of this paper and get shuffle-DP error bounds that are not much worse \"for free\". If so I could see this paper having a sizeable impact on both the theoretical literature, and on how models are trained using DP in practice. As far as the writing itself, I felt the paper was nicely organized and easy to read. The authors build up the results nicely, progressing slowly from scalar sums, to vector sums, to algorithms using vector sums to arrive at their main results, and the analysis is intuitively presented. The authors also do a good job in the introduction with explaining the setting and comparing to past results to highlight the novelties of their paper in what is a quickly growing area.\n\nI don't feel the paper has any real major weaknesses, but for completeness sake I'll address some parts of the paper that may be viewed as weaknesses. For one, there is no experimental work in the paper to show how well the algorithms do in practice. However, in some sense experiments may not be necessary - the only real difference from DP-SGD from a utility perspective is the noise being added to the gradients, which is from a near-normal distribution, so if my understanding is correct it is likely the performance of the algorithms in this paper would compare to the performance of DP-SGD but with a different scale of noise depending on the dimension/number of samples. Another possible weakness is that once one has the vector sum estimator, which follows from a composition theorem constructed by the authors, many of the SCO results are just \"plug-and-play\" or variants of existing analyses, i.e. most of the technical novelty is in the vector sum estimator. However, I wouldn't mark down the paper for this aspect; I think the vector sum estimator is by itself a very nice contribution for the reasons mentioned before, and I think it is also a nice \"story\" that in the shuffle model, we can apply algorithms/analyses that are very similar to what is used in the central model, just with added variance due to the local randomizers.", "summary_of_the_paper": "This papers considers stochastic convex optimization (SCO) in the shuffle-DP model. In particular, the authors consider two models for shuffle-DP: A \"sequential\" model where the analyzer operates in rounds, and in each round a new set of users participate in a local-DP protocol, and a new \"full\" model in which the analyzer can request a specific subset of users to participate in each round, which allows users' data to be queried more than once. The authors show that in the full model, one can retrieve excess population loss bounds matching the best possible bounds in the central DP setting. Furthermore, they show even the sequential model offers improved excess population bounds over the best possible bound of sqrt(d/n) in the local setting. \n\nThe key technical ingredient is a shuffle-DP randomizer for estimating the sum of vectors, each stored by a user, when the vectors have bounded $\\ell_2$-sensitivity (which corresponds to a Lipschitz assumption on each loss function in SCO), in contrast with existing work which focused on $\\ell_1$-sensitivity. The authors build off a scalar sum estimator and then use a composition theorem to prove privacy of the vector sum estimator as composition of scalar sum estimators, and then bound the variance of this estimator, and then use it to compute batch gradients in existing optimization algorithms such as gradient descent, stochastic gradient descent, and the accelerated stochastic approximation algorithm. For some of these results, a variance bound on the batch gradient immediately gives an excess empirical loss bound. In some other settings there is no plug-and-play error bound, so instead they need appeal to arguments/reductions similar to those appearing before in the central DP SCO literature, but with some elements specialized to their setting.", "summary_of_the_review": "Overall I greatly enjoyed reading the paper and think the results have a lot of potential for impact, both theoretically and practically. In particular the vector sum estimator provided by the authors is a tool that I could easily see being used by other papers to establish results in the shuffle-DP setting, and even just focusing on the error bounds, the optimal excess loss in the full shuffle model is quite a nice result, and the results for the sequential shuffle model also nicely improve on the results for SCO in the standard local DP model. In addition, the paper is nicely written and easy-to-read, and in turn ready for presentation at a major conference. For these reasons I recommend accepting the paper.", "strength_and_weaknesses": "", "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": {}}, {"review_id": "TZHfpn8UIr", "reviewer": "Reviewer_Frn5", "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": "The main contribution of the paper is the non-interactive mechanism to compute \\ell_2 norm of a given vector. This in turn builds on the mechanism given by Balcer and Cheu for privately scalar sum. The algorithm for SGD is pretty straightforward and the analysis is also standard in the literature. In total, the \"proposed\" new contribution of the paper is the scalar sum protocol. \n\nThe scalar sum protocol is a generalization of Balcer and Cheu. The difference between the two protocols is that the randomizer of this protocol also uses how many random copies of both 0s and 1s should be sent. Each of these numbers is itself a random variable. The sampling probability for both Bernoulli and Binomial samples itself depends on the input! I found this rather surprising that they were able to prove privacy for such a protocol. However, I feel that the protocol itself reduces to the binomial mechanism proposed in Dwork et al. 2006 when we set $g \\approx \\sqrt{n}$. I would like to know what is the difference? In particular, when all $x$ are close to 0, then step 5 with high probability would not add anything to $\\bar x$ and all we are left with is the Binomial mechanism. In particular, step 5 is more of a randomized rounding and I can see as post-processing. I do not see why it helps in privacy, and if it does not, then the mechanism is just the Binomial mechanism of \"Our data, ourselves: Privacy via distributed noise generation.” If there is no difference then there is nothing new in this paper!\n\nApart from this, I have some serious questions about the applicability of this paper:\n1. The choice of $g$ defines how many bits everyone has to send. That means, that every user has to send $\\sqrt{n}$ bits, where $n$ are the participating parties. Now, in the setting where the shuffle model would be used in practice is where we try to train an ML model using private federated learning. There, in practice, we will never know in advance what is the value of $n$. How would the user know how many bits he has to send?\n2. Second, and this is also a glaring problem with Balcer and Cheu, is that the randomizer sends a certain number of copies of 1s and 0s. This number is a random variable that depends on the privacy noise. An architecture for shuffler would need to know what is the input size to design the permutation. Oblivious permutation itself takes $O(m \\log m)$ time, where $m$ is the input, but it crucially depends that we know the number $m$. If you want to implement a permutation where the size of the permutation matrix is a random variable, you would need to impose some more trust assumptions. This has been studied in the security and crypto community and easy deanonymization is possible. That is one reason why the IKOS 2006 assumed $m$ is known.  \n3. The authors give an algorithm and analyze it under various settings for SGD. However, they fail to compare it \"Practical and Private (Deep) Learning Without Sampling or Shuffling\" (ICML 21) That paper does a very good job of arguing why sampling and shuffling are problematic in large-scale deployment. However, more importantly, they give an algorithm that meets the bounds one get by shuffling or sampling (up to $\\log n$ factor; which I think can be improved using better data structure). Their privacy guarantee more crucially does not depend on convexity, a significant departure from previous work in this area starting with Song et al. What this paper throws under the rug is the fact that epsilon when you are training or using convex optimization would never be less than $1$. So, after getting the terms which is true for any epsilon, they always make the assumption that $\\epsilon$'s are small! In practice, using Honaker's improvement on binary tree mechanism, I would not be surprised that the ICML 21 paper would be better than the submission in all axis once the privacy budget is reasonable for where we use any private convex optimization. \n4. Finally, the proof of the composition theorem is essentially the proof of composition theorem from \"Boosting and DP\" paper. The current paper can appeal to Chernoff while the Boosting and DP paper required Azuma as they had to deal with a martingale (and their composition was more general). \n\nI have a few more small questions that I will leave to ask during the reviewer-author engagement. \n\n\nPost author's response phase: The authors have answered most of my questions in a timely manner. I really appreciate their response. It helped me better understand the paper. I would ideally like to give a paper an accept (a rating of 7), which I cannot find. So, I would request the AC to consider this remark over the score given in the Recommendation section.", "summary_of_the_paper": "The paper studies stochastic convex optimization in the shuffle model of privacy. They claim a new non-interactive algorithm for privately computing \\ell_2 norm, which would be useful in the stochastic gradient descent algorithm. ", "summary_of_the_review": "The paper studies stocastic convex optimization in shuffle model; however, to my understanding, most of the results are known or are folklore. Also, they fail to compare with the most relevant and recent already published work. \n\nI have studied the proof and they are correct (more so, because most of them follow the standard ideas or the results follow from previous works).", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "QtyeixS_yq6", "reviewer": "Reviewer_tikt", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Strength:\n- The proposed interactive models are reasonable extensions of the non-interactive shuffle privacy model.\n- The paper reveals non-trivial bounds on the excess errors of the shuffle private stochastic convex optimizations.\n- The error bound in the convex and fully interactive case matches the known best error in the central model.\n\nWeakness:\n- The tightness of the bounds in the sequential model is unclear.\n\n\nOverall, I recommend acceptance. This paper is well-written and has significant advances in the field of shuffle differential privacy. \n\nThe sequential and fully interactive models in the shuffle privacy are natural and reasonable extensions from the non-interactive model as well as the interactive models in the local privacy. I guess these models are acceptable even in real-world situations (particularly the sequential interactive model).\n\nThe authors introduce a novel analysis for the scalar sum, revealing the instance-specific privacy guarantee. This technique enables us to obtain the lower dimensional dependency on the error of the vector sum protocol. \n\nThe excess error bounds on the shuffle private stochastic convex optimization seem to be significant contributions to the related fields. \n\nOne possible drawback is the unclarity in the tightness of the bounds. In all cases, the first terms in the error bounds match the lower bound on the non-private first-order stochastic convex optimization. The second terms in the strongly convex and smooth case in the sequential model and all cases in the full model match the known best result in the central model. It is likely to be tight in these cases. The other cases, however, are unclear. The discussions about the tightness of these bounds are helpful for the reader.", "summary_of_the_paper": "The authors deal with the stochastic convex optimization problem under the shuffle differential privacy constraint. They extend the existing non-interactive shuffle privacy model to the interactive ones, sequential and full interactive models. Under these interactive models, they propose the shuffle private SCO algorithms with the analyses of the excess error bounds. To construct their algorithms, they introduce a novel shuffle private estimation mechanism for the sum of the vectors. ", "summary_of_the_review": "Overall, I recommend acceptance. This paper is well-written and has significant advances in the field of shuffle differential privacy. One possible weakness is unclearly in the tightness of bounds in the sequential model.", "strength_and_weaknesses": "", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "1ALzCTZMQfT", "reviewer": "Reviewer_d49M", "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": "Strengths: \n\n-The privacy mechanism for vector summation is interesting. It differs from the standard use of additive noise (usually Gaussian or Laplace) in DP optimization. It is also somewhat novel, as most prior works were for vectors with bounded $L_1$ sensitivity instead of $L_2$ (or used privacy amplification, c.f. Girgis et al (2021)). \n\n-The problem is interesting, considering the practical relevance of shuffle DP (as an intermediate trust model between local and central DP) and the importance of SCO. In light of the work of Erlingsson et al. (2020) and Girgis et al. (2021) on shuffle DP ERM, SCO is a natural next step. \n\n-The bounds seem good, especially Theorem 4.9 since it shows optimality. \n\n-The paper is well-written and the results seem correct.   \n\nWeaknesses: \n-For me, the weakest link of the paper is Section 4.1 (sequentially interactive SCO). The results are suboptimal as they stand, so one wonders why they are useful. The authors do mention that in practice, sometimes only one query per user is possible, which provides some motivation for sequentially interactive algorithms. Can the authors provide references and practical examples to support this claim? I would also like to see other arguments motivating the importance of sequentially interactive protocols. In addition, the paper would be greatly strengthened by either improving the bounds in Section 4.1 (to match the existing central DP lower bounds) or adding nearly tight lower bounds for sequentially interactive algorithms to show a separation between sequential and full interactivity for this problem and establishing near optimality of their bounds. Joseph et al. (2019) seems like a relevant work for this. \n\n-Missed related work: 1. There is a very relevant contemporaneous work that should be cited/discussed in the final version of the paper by Lowy & Razaviyayn (2021)  https://arxiv.org/abs/2106.09779. They cover a more general problem of federated learning, but setting $n=1$ and $M=N$ in their Theorem 4.1 recovers your Theorem 4.9. They use different protocols and only have fully interactive algorithms. They also use acceleration and smoothing for some of their results. I don't hold this one against the authors since it is concurrent, but a discussion of this work should be added to the Related Work section of the final version of the paper. 2. Erlingsson et al. (2020) (\"ESA Revisited..\") should also be referenced with Girgis et al (2021) in the context of shuffle DP ERM. 3. Smith et al. (2017) (\"Is interaction necessary...\") uses acceleration (Theorem 20), as does Lowy & Razaviyayn (2021)--these should be discussed, and the sentence \"we are not aware of previous private SCO results relying on acceleration\" in Contribution 3 should be removed. \n\n-Intro: $O(\\sqrt{d}/\\epsilon \\sqrt{n})$ is optimal in the local model is true, but I think Duchi et al (2013) only proves it for sequentially interactive pure DP algorithms, right? However, Lowy & Razaviyayn (2021) show that the same optimal loss bound holds for approximate DP fully interactive algorithms. \n\n-Definition 2.7 seems unnecessarily abstract; would be good to explain intuitively \n\n-\"allow the analyzer to adaptively choose which subset of users to query..\" is not the main/important difference between full and sequential interactivity; sequential algorithms also choose which subset of users to query in each round (but not adaptively). I would either delete this part of the sentence or emphasize \"adaptively\"; the main distinction is in the second part of the sentence (repeated querying). \n\n-Lemma 3.1: y is never explicitly defined; you should define it and say it lives in $[0,1]^{g+b}$; \"$P_{1D}(S(y))$ is an unbiased estimate...\" is not technically correct (as it is a tuple)--I think you mean \"$A_{1D}(S(y))$ is an unbiased estimate...\"? \n\n-Algorithms 3 and 5: it looks like you are doing gradient ascent instead of descent\n\n-Section 4.1 initial paragraph: include $\\epsilon$ in these loss bounds\n\n-Restriction on epsilon should be included in statements of all theorems in Section 4. You require $\\epsilon \\leq 1$ for privacy of your vector summation protocol, right? Also, for advanced composition in Theorem 4.9, you need some restriction (even if very mild and possibly subsumed by the restriction needed for vector summation) to bound $e^{\\epsilon'} \\leq 2 \\epsilon'$. Also, I think you may need to shrink the inputs to your vector summation protocol by constant factor (something like $2\\sqrt{2}$) to get exactly $(\\epsilon, \\delta)$-DP in Theorem 4.9. \n\n-Clarify wording in \"combining it with acceleration to attain a better guarantee\": the guarantee is not better than that attained in Bassily et al. (2019). \n\n-\"optimization trajectory\": what does this mean? \n\n-Theorem 4.9: I think you are missing a $lambda$ in the denominator of the second term? (Or the units are wrong.); also, you should include runtime and/or communication complexity guarantees (and do the same for results in Section 4.1.)\n\n-Proof of Lemma 3.1. Clarify/highlight where/how shuffling is used to provide privacy (if at all). It wasn't clear to me. Would same privacy guarantee hold without shuffling? Also, explain why $Var(\\eta_1) \\leq 1/4.$ ", "summary_of_the_paper": "The paper provides shuffle DP algorithms and population loss upper bounds for stochastic convex optimization (SCO). They include both sequentially interactive and fully interactive algorithms. Their fully interactive upper bounds match the central DP lower bounds. They propose a private protocol for vector summation that serves as the privacy workhorse of their algorithms; they combine this protocol with variants of (accelerated) gradient descent and SGD to obtain their results. ", "summary_of_the_review": "The paper is interesting, well-written, and seems correct. It is a solid work, but would be greatly strengthened by providing *tight* bounds for sequentially interactive algorithms and/or strengthening the motivation for sequentially interactive algorithms. Additionally, there are a number of minor issues (described above) that should be addressed. I consider the paper marginally below acceptance threshold in its current form, but would be open to recommending acceptance upon satisfactory revision. \n\n__\n\nEdit: The authors have addressed my concerns and revised the manuscript. I recommend acceptance. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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:

Meta-review: This work is on stochastic convex optimization (SCO) in shuffle differential privacy (DP) models. In SCO, a learner receives a convex loss function L: Theta x X -> Reals, where Theta is a d-dimensional vector of parameters and X is a set of data points. The objective is to use samples x1, x2, …, xn to find a parameter theta that minimizes the loss E_{x ~ D}[L(theta,x)], where the distribution D on X is unknown. The shuffle models considered are a ``sequential" model where the analyzer operates in rounds (and where a new set of users participate in a local DP protocol in every round), and a new, stronger "full" model in which the analyzer can request a specific subset of users to participate in a round, which in particular allows users' data to be queried more than once. This work shows that in the full model, one can develop excess population loss bounds matching the known best-possible bounds in centralized DP; it is also shown that even the weaker sequential model offers improved excess population loss bounds over the best-possible bound of sqrt(d/n) in the local setting.

The reviewers appreciated the novelty and technical depth of this work (despite concerns about part of the work being taking “off the shelf” results).
Decision: Accept (Poster)