SHUFFLE PRIVATE STOCHASTIC CONVEX OPTIMIZATION
Year: 2021

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. We present interactive shuffle protocols for stochastic convex optimization. Our protocols rely on a new noninteractive protocol for summing vectors of bounded `2 norm. By combining this sum subroutine with 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.

heading: 1 INTRODUCTION
text: In stochastic convex optimization, a learner receives a convex loss function ` : Θ×X → R mapping pairs of parameters and data points to losses, and the goal is to use data samples x1, . . . , xn to find a parameter θ to minimize population loss Ex∼D [`(θ, 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., 2006b), 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 a 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 n samples over a d-dimensional parameter space with privacy parameter ε, the optimal loss term due to privacy is O( √ d/(εn)) in the central model (Bassily et al., 2013; 2019; Feldman et al., 2020). In the local model, the optimal private loss term is O( √ d/(ε √ n)) 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 (Kasiviswanathan et al., 2011; Chan et al., 2012; Duchi et al., 2018; Duchi and Rogers, 2019; Joseph et al., 2019). This has motivated the exploration of models achieving a finer trade-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 a now-substantial body of work on shuffle privacy (Bittau et al., 2017; Cheu et al., 2019; Erlingsson et al., 2019; Balle et al., 2019; Ghazi et al., 2021; Balcer and Cheu, 2020; Feldman et al., 2021; Balcer et al., 2021), including steps toward real-world deployment (Google, 2021). However, comparatively little is known about shuffle private stochastic convex optimization.

heading: 1.1 OUR CONTRIBUTIONS
text: 1. We introduce sequentially interactive (each user participates in a single protocol round) and fully interactive (each user participates in arbitrarily many protocol rounds) variants
of the shuffle model of differential privacy1. 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 `2 sensitivity. By using multiple messages, our protocol is substantially more accurate than existing results (see Related Work).
3. We use our `2 summation protocol to derive several new shuffle private SCO guarantees (Table 1) via techniques including acceleration, Nesterov’s smoothing method in the sequential interactive model, and noisy gradient descent in the fully interactive model.

heading: 1.2 ADDITIONAL RELATED WORK
text: The vast majority of work on shuffle privacy studies the noninteractive model, but a few exceptions exist. Erlingsson et al. (2019) and Feldman et al. (2021) study a variant in which the shuffler is a layer that accepts randomizers from the analyst, assigns them randomly to users, and sends the permuted messages back to the analyzer. Feldman et al. (2021) also construct a basic protocol for SGD in this model. This model is similar to other work that achieves shuffle privacy guarantees by amplifying the local privacy guarantees of local randomizers (Balle et al., 2019). Erlingsson et al. (2020) also studied empirical risk minimization using shuffle-amplified 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 on amplification.
Another exception is the work of Beimel et al. (2020), where the shuffler broadcasts the permuted messages to all parties. Users then execute key exchange protocols, and Beimel et al. show that a first round of key exchange enables the use of multi-party computation (MPC) to simulate any central DP algorithm in the second round. Our results depart from theirs in two ways. First, we only assume that the shuffler sends outputs to the analyzer, not to individual users. Second, the MPC approach given by Beimel et al. requires an honest majority. Without an 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.1). Simultaneous independent work by Tenenbaum et al. (2021) also studies a sequentially interactive variant of the shuffle model in the context of multi-arm bandits. Their model of sequential interactivity is identical to ours, albeit for a different problem.
Girgis et al. (2021) provide a 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 `2 summation protocol requires one message from each user, and its second moment guarantee for the average gradient has a 1/b dependence on
1These terms are borrowed from local differential privacy (Duchi et al., 2018; Joseph et al., 2019).
batch size b (their Lemma 4). In contrast, our multi-message protocol obtains a better 1/b2 dependence. This is possible because our multi-message protocol does not rely on privacy amplification, and in particular circumvents their single-message lower bound (their Theorem 3). Kairouz et al. (2021b) 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 our vector sum protocol, though their O(d1/4/ √ n) SCO guarantee is weaker than our O(d1/3/n2/3) SCO guarantee (Theorem 4.7).
Concurrent work by Lowy and Razaviyayn (2021) study fully interactive shuffle private protocols with SCO guarantees matching ours (Section 4.2). There are 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 of real vectors. This assumption is 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 et al., 2019; Ghazi et al., 2019; Balcer and Cheu, 2020) and recent work has studied vector addition in the secure aggregation model (Kairouz et al., 2021a), which assumes the existence of a trusted aggregator that can execute modular arithmetic on messages. We expand on this work by introducing a shuffle private protocol for summing vectors with bounded `2 norm, with noise standard deviation proportional to the `2 sensitivity.

heading: 2 PRELIMINARIES
text: Differential Privacy. Throughout, let X be a data universe, and suppose that each of n users has one data point from X . Two datasets X,X ′ ∈ Xn 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 et al. (2006b)). An algorithm A satisfies (ε, δ)-differential privacy if, for every X ∼ X ′ and every event Z, PA [A(X) ∈ Z] ≤ eε · PA [A(X ′) ∈ Z] + δ.
Because Definition 2.1 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, it will also be useful to rephrase DP as a divergence constraint. Definition 2.2. The δ-Approximate Max Divergence between distributions X and Y is
Dδ∞(X||Y ) = max Z⊆supp(X):Pr[X∈Z]≥δ
[ log
Pr[X ∈ Z]− δ Pr[Y ∈ Z]
] .
Fact 2.3. Algorithm A is (ε, δ)-DP if and only if, for all X ∼ X ′, Dδ∞(A(X)||A(X ′)) ≤ ε.
A key property of DP is closure under post-processing. Fact 2.4 (Proposition 2.1 (Dwork and Roth, 2014)). Fix any function f . If A is (ε, δ)-differentially private, then the composition f ◦ A is also (ε, δ)-differentially private.
Shuffle Privacy. In the shuffle model (Bittau et al., 2017; Cheu et al., 2019; Erlingsson et al., 2019), we do not require users to trust the operator of A. Instead, we make the narrower assumption that there is a trusted shuffler: 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 randomizerR : X → Y∗ and analyzer A : Y∗ → Z . In an execution of P on X , each user i computes R(Xi)—possibly using public randomness—and sends the resulting messages yi,1, yi,2, . . . to the shuffler S . S reports ~y to an analyzer, where ~y is a uniformly random permutation of all user messages. The final output of the protocol is A(~y).
We now define our privacy objective in the shuffle model, often shorthanded as “shuffle privacy”. Definition 2.6 (Cheu et al. (2019); Erlingsson et al. (2019)). P = (R,A) is (ε, δ)-shuffle differentially private if the algorithm (S ◦ Rn)(X) := S(R(X1), . . . ,R(Xn)), i.e. the analyzer’s view of
the shuffled messages, is (ε, δ)-differentially private. The privacy guarantee is only over the internal randomness of the users’ randomizers and the shuffler.
A drawback of the preceding definition of shuffle protocols is that it limits communication to 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 shuffle protocol transcripts, and let R denote the universe of randomizers. A sequentially interactive shuffle protocol P consists of initial local randomizer R0, analyzer A, and update function U : Tr → [n]×R. Let Trt denote the transcript after t rounds of the protocol. In each round t of P , the analyzer computes (nt,Rt) = U(Trt−1), nt new users applyRt 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(TrT ).
This formalizes the idea that the analyzer looks at the past shuffled outputs to 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 one computation. More generally, we can 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 U : Tr→ 2[n] ×R selects an arbitrary subset of users in each round. In particular, a 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 a user multiple times in practice (Kairouz et al., 2021b; 2019).
For sequentially and fully interactive shuffle protocols, the definition of privacy is identical: the view of the transcript satisfies DP. The noninteractive definition is 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 an input database and outputs the resulting transcript. Then P is (ε, δ)-shuffle differentially private ifMP is (ε, δ)-differentially private.
Stochastic Convex Optimization. Let closed convex Θ ⊂ Rd with diameter D be our parameter space. We always assume loss functions `(θ, x) that are convex and L-Lipschitz in Θ. Definition 2.10. Loss function ` : Θ×X → R is convex in Θ if, for all x ∈ X , for all t ∈ [0, 1] and θ, θ′ ∈ Θ, `(tθ + (1 − t)θ′, x) ≤ t`(θ, x) + (1 − t)`(θ′, x). ` is L-Lipschitz in Θ if for all x ∈ X and θ, θ′ ∈ Θ, |`(θ, x)− `(θ′, x)| ≤ L‖θ − θ′‖2.
In some cases, we also assume that our loss function ` is β-smooth and/or λ-strongly convex. Definition 2.11. Loss function ` : Θ×X → R is β-smooth over Θ if, for every x ∈ X and for every θ, θ′ ∈ Θ, ‖∇`(θ, x)−∇`(θ′, x)‖2 ≤ β‖θ − θ′‖2. ` is λ-strongly convex in Θ if, for all x ∈ X , for all t ∈ [0, 1] and θ, θ′ ∈ Θ, `(tθ + (1− t)θ′, x) ≤ t`(θ, x) + (1− t)`(θ′, x)− λt(1−t)2 ‖θ − θ ′‖22.
Our goal is to minimize population loss. We will view each user as a sample from D, and our protocols will learn from these samples 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 ` : Θ × X → R be a loss function. Then algorithm A : X ∗ → Θ has population loss EA,D [ `(θ̄,D) ] = Eθ∼A(Dn) [Ex∼D [`(θ, x)]].

heading: 3 VECTOR SUMMATION
text: In this section, we provide a shuffle private protocol PVEC for summing vectors of bounded `2 norm. This contrasts with existing work, which focuses on `1 sensitivity. PVEC will be useful for the gradient descent steps of our algorithms in Section 4. PVEC relies on d invocations of a scalar sum protocol P1D, one for each dimension. We describe this scalar summation subroutine in Section 3.1, then apply it to vector summation in Section 3.2. Proofs for results in this section appear in Appendix A

heading: 3.1 SCALAR SUM SUBROUTINE
text: We start with the pseudocode for P1D, a shuffle protocol for summing scalars. As is generally the case for shuffle protocols, the overall protocol decomposes P1D = (R1D,A1D) into randomizer and analyzer components: each user i computes a collection of messages ~yi ∼ R1D(xi), the shuffler S aggregates and permutes these messages to produce ~y ∈ {0, 1}(g+b)n, and the analyzer takes the result as input for its final analysis A1D(S(~y)). P1D uses the fixed-point encoding presented by Cheu et al. (2019) and ensures privacy using a generalization of work by Balcer and Cheu (2020).
Algorithm 1 P1D, a shuffle protocol for summing scalars 1: Parameters: Scalar database X = (x1, . . . , xn) ∈ [0,∆]n; g, b ∈ N; p ∈ (0, 1/2) 2: procedure LOCAL RANDOMIZER R1D(x) 3: Set x← bxg/∆c 4: Sample rounding value η1 ∼ Ber(xg/∆− x) 5: Set x̂← x+ η1 6: Sample privacy noise value η2 ∼ Bin(b, p) 7: Report x̂+ η2 copies of 1 and g + b− (x̂+ η2) copies of 0 8: end procedure 9: procedure ANALYZER A1D (S(~y))
10: Output estimator ∆g (( ∑(g+b)n i=1 yi)− pbn) 11: end procedure
P1D’s privacy guarantee is instance-specific: for every pair of inputs, we bound the approximate maxdivergence between output distributions as a function of the change in inputs. Previously proposed by Chatzikokolakis et al. (2013), this property will be essential when proving that PVEC is private. Lemma 3.1. Fix any number of users n, ε ≤ 15, and 0 < δ < 1/2. Let g ≥ ∆ √ n, b > 180g
2 ln(2/δ) ε2n ,
and p = 90g 2 ln(2/δ) bε2n . Then 1) for any neighboring databases X ∼ X ′ ∈ [0,∆]n that differ on user u, Dδ∞((S ◦ Rn1D)(X)||(S ◦ Rn1D)(X ′)) ≤ ε · ( 2 g + |xu−x′u| ∆ ) , and 2) for any input database
X ∈ [0,∆]n, P1D(X) is an unbiased estimate of ∑n i=1 xi and has variance O( ∆2 ε2 log 1 δ ).
We defer the proof to Appendix A. Claim 1 follows first from the observation that the adversary’s view is equivalent to the sum of the message bits. This sum has binomial noise, which was first analyzed by Dwork et al. (2006a) in the context of central DP. We adapt work on a shuffle private variant due to Ghazi et al. (2021) to incorporate a dependence on the per-instance distance between databases. Claim 2 follows as a straightforward calculation.
Lemma 3.1 holds when all n users follow the protocol. We call these users honest. It is possible to prove a more general version of Lemma 3.1 whose parameters smoothly degrade with the fraction of honest users (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 P1D in a black-box manner. It is therefore possible to replace it with a lower-communication subroutine for scalar sum (Balle et al., 2019). However, this improved communication requires a more complicated protocol with an additional subroutine. Our work focuses on sample complexity guarantees, so we use P1D for clarity. Nonetheless, we note that each user sends g + b ≈ ∆ √ n + ∆2 log(1/δ)/ε2 bits in P1D, and the analyzer processes these in time O((g + b)n). Scaling these quantities by d yields guarantees for PVEC in the next subsection. Moreover, it is possible to remove the communication dependence on ∆ by having users scale down their inputs by ∆ before running P1D, running P1D as if ∆ = 1, and then scaling up the final output by ∆ to compensate; this does not affect the overall unbiasedness or variance guarantees. Improving the communication efficiency of these protocols may be an interesting direction for future work.

heading: 3.2 VECTOR SUM
text: Below, we present the pseudocode for PVEC, again decomposing into randomizer and analyzer components. Note that we view the vector ~y to be the collection of all shuffled messages and, since
the randomizers labels these messages by coordinate, ~yj consists of the messages labelled j. The accompanying guarantee for PVEC appears in Theorem 3.2.
Algorithm 2 PVEC, a shuffle protocol for vector summation 1: Input: database of d-dimensional vectors ~X = (~x1, · · · , ~xn); privacy parameters ε, δ; ∆2. 2: procedure LOCAL RANDOMIZER RVEC(~xi) 3: for coordinate j ∈ [d] do 4: Shift data to enforce non-negativity: ~wi,j ← ~xi,j + (∆2, . . . ,∆2) 5: ~mj ← R1D(~wi,j) 6: end for 7: Output labeled messages {(j, ~mj)}j∈[d] 8: end procedure 9: procedure ANALYZER AVEC(~y) 10: for coordinate j ∈ [d] do 11: Run analyzer on j’s messages zj ← A1D(j, ~yj) 12: Re-center: oj ← zj −∆2 13: end for 14: Output the vector of estimates ~o 15: end procedure
Theorem 3.2. For any 0 < ε ≤ 15, 0 < δ < 1/2, d, n ∈ N, and ∆2 > 0, there are choices of parameters b, g ∈ N and p ∈ (0, 1/2) for P1D (Algorithm 3.1) such that, for inputs ~X = (~x1, . . . , ~xn) of vectors with maximum norm ||~xi||2 ≤ ∆2, 1) PVEC is (ε, δ)-shuffle private and, 2) PVEC( ~X) is an unbiased estimate of ∑n i=1 ~xi and has bounded variance
E ∥∥∥∥∥PVEC( ~X)− n∑ i=1 ~xi ∥∥∥∥∥ 2
2
 = O(d∆22 ε2 log2 d δ ) .
The proof relies on a variant of advanced composition (Lemma 3.3). Although the proof follows many of the same steps as prior work, the statement is somewhat nonstandard because it uses the divergence between two specific algorithm executions, rather than the worst-case divergence of a generic differential privacy guarantee. This enables us to use Lemma 3.1. Lemma 3.3. Fix any γ ∈ (0, 1) and neighboring databases X,X ′ ∈ Xn. For all j ∈ [d], suppose algorithmAj : Xn → Y use independent random bits and satisfies D δj ∞(Aj(X)||Aj(X ′)) ≤ εj . Let
ε′ = d∑ j=1 εj(e εj − 1) + 2 √√√√log(1/γ) d∑ j=1 ε2j and δ ′ = d∑ j=1 δj + γ.
Then Dδ ′ ∞(A1(X), . . . ,Ad(X)||A1(X ′) . . . ,Ad(X ′)) ≤ ε′.
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 P1D by PVEC 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 3.1. The fact that we know a bound on sensitivity allows us to bound the (squared) `2 norm of the vector of divergences. This norm is implicit within Lemma 3.3, so the target theorem follows by re-scaling of parameters and substitution.

heading: 4 CONVEX OPTIMIZATION
text: We now apply PVEC to convex optimization. Section 4.1 describes shuffle protocols that are sequentially interactive and solicit one input from each user.2 Section 4.2 offers stronger utility guarantees via fully interactive protocols that query users multiple times. Complete proofs of all results in this section, along with communication and runtime guarantees, appear in Appendix B.
2Since sequentially interactive protocols process data online, our sequentially interactive shuffle protocols also have straightforward pan-private (Dwork et al., 2010a) analogues with the same guarantees; see Appendix C for details.

heading: 4.1 SEQUENTIALLY INTERACTIVE PROTOCOLS
text: Our first sequentially interactive protocol is a simple instantiation of noisy mini-batch SGD, PSGD. This baseline algorithm achieves population loss O ( d1/4√ εn ) (Theorem 4.1), which already improves on the locally private guarantee. However, in a departure from the central and local models, we then show that a still better O ( d1/3
(εn)2/3
) loss guarantee is possible (Theorem 4.7) using a more complex
algorithm PAGD that smooths the loss function and employs accelerated SGD.
Convex ` We start with PSGD. Because PSGD is sequentially interactive, for a fixed number of users n, the batch size b is inversely proportional to the number of iterations T . As a result, Theorem 4.1 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 n, batch size b, privacy parameter ε, δ, step size η, Lipschitz parameter L
1: Initialize parameter estimate θ0 ∈ Θ, and set number of iterations T = n/b 2: for t = 1, 2, . . . , T do 3: Compute gradient at θt−1, ḡt ← 1bPVEC (∇θ`(θt−1, xt,1), · · · ,∇θ`(θt−1, xt,b); ε, δ, L) 4: Update parameter estimate θt ← πΘ (θt−1 + ηḡt) 5: end for 6: Output 1T ∑T−1 t=0 θt
Theorem 4.1. Let loss function ` be convex, L-Lipschitz over a closed convex set Θ ⊂ Rd of diameter D, θ̄ = 1T ∑T−1 t=0 θt, b = √ d log(d/δ) ε , T = n/b, η = εbD L √ T (εb+ √ dL log(d/δ))
, and ε ≤ 15. Then PSGD is (ε, δ)-shuffle private and has population loss
EPSGD,D [ `(θ̄,D) ] ≤ min
θ∈Θ `(θ,D) +O
( d1/4DL log1/2(d/δ)√
εn
) .
Privacy—for PSGD and our other protocols, which all rely on PVEC—follows from the fact that the L-Lipschitz assumption ensures that a loss gradient has `2 norm at most L. The utility proof proceeds by viewing each noisy gradient step as a 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 [ `(θ̄,D) ] ≤ min
θ∈Θ `(θ,D) + D
2 2ηT + ηL2G 2 .
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 to 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, a 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) of Lan (2012). Theorem 4.3. Let ` be convex, β-smooth, and L-Lipschitz over closed convex set Θ ⊂ Rd of diameter D. Denote θ̄ = θagt+1. Let batch size b = n3/5d1/5L2/5 log2/5(d/δ) ε2/5β2/5D2/5 , Lt = 1t+1 ((T + 2) 3/2 σ
D + β), αt = 2 t+2 , and ε ≤ 15. Then PAGD is (ε, δ)-shuffle private with population loss
EPAGD,D [ `(θ̄,D) ] ≤ min
θ∈Θ `(θ,D) +O ( DL√ n + d2/5β1/5D6/5L4/5 log4/5(d/δ) ε4/5n4/5 ) .
The proof of Theorem 4.3 is similar to that of Theorem 4.1. The main difference is that we rely on an oracle utility guarantee that is specific to accelerated gradient descent:
Algorithm 4 PAGD, Sequentially interactive shuffle private AC-SA Require: Number of users n, batch size b, privacy parameters ε, δ, Lipchitz parameter L, learning
rate sequence {Lt}, {αt} 1: Initialize parameter estimate θag1 = θ1 ∈ Θ, and set number of iterations T = bn/bc 2: for t = 1, 2, . . . , T do 3: Update middle parameter estimate θmdt ← αtθt + (1− αt)θ ag t .
4: Estimate gradient at θmdt , ḡt ← 1bPVEC ( ∇θ`(θmdt , xt,1), · · · ,∇θ`(θmdt , xt,b); ε, δ, L ) 5: Update parameter estimate θt+1 ← arg minθ∈Θ { 〈ḡt, θ − θt〉+ Lt2 ‖θ − θt‖ 2 2
} 6: Update aggregated parameter estimate θagt+1 ← αtθt+1 + (1− αt)θ ag t 7: end for 8: Output θagT+1
Lemma 4.4 (Theorem 2 (Lan, 2012)). Suppose PAGD receives a noisy gradient oracle with variance (at most) σ in each iteration. Taking Lt = 1t+1 ((T + 2) 3/2 σ D + β), αt = 2 t+2 , then the expected error of PAGD can be bounded as
E [ `(θ̄,D) ] ≤ min
θ∈Θ `(θ,D) +O
( βD2
T 2 + Dσ√ T
) .
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 technique. In particular, for a non-smooth loss function, we approximate it with a smooth function by exploiting Moreau-Yosida regularization. We then optimize the smooth function via PAGD. This is not the first application of Moreau-Yosida regularization in the private optimization literature (Bassily et al., 2019), but we depart from past work by combining it with acceleration to attain a better guarantee. We start by recalling the notion of the β-Moreau envelope, using the language of Bassily et al. (2019). Definition 4.5. For β > 0 and convex f : θ → Rd, the β-Moreau envelope fβ : θ → Rd of f is
fβ(θ) = min θ′∈Θ
( f(θ′) + β
2 ‖θ − θ′‖22
) .
The following properties of the β-Moreau envelope will be useful. Lemma 4.6 (Nesterov (2005)). Let f : θ → Rd be a convex function, and define the proximal operator proxf (θ) = arg minθ′∈Θ ( f(θ′) + 12‖θ − θ ′‖22 ) . For β > 0:
1. fβ is convex, 2L-Lipschitz and β-smooth.
2. ∀θ ∈ Θ,∇fβ(θ) = β(θ − proxf/β(θ)).
3. ∀θ ∈ Θ, fβ(θ) ≤ f(θ) ≤ fβ(θ) + L 2
2β .
Informally, we use Lemma 4.6 as follows. First, claim 1 enables us to optimize fβ using PAGD. Inside PAGD, we use claim 2 to compute the desired gradients of fβ and obtain a loss guarantee for fβ using Theorem 4.3. Finally, claim 3 bounds the change in loss between fβ and the true function f as a function of β. We then choose β to minimize the overall loss guarantee. Theorem 4.7. Let ` be convex and L-Lipschitz over a closed convex set Θ ⊂ Rd of diameter D and ε ≤ 15. Then combining PAGD with the above smoothing method yields an (ε, δ)-shuffle private algorithm with population loss
E [ `(θ̄,D) ] ≤ min
θ∈Θ `(θ,D) +O ( DL√ n + d1/3DL log2/3(d/δ) ε2/3n2/3 ) .
Strongly convex function When the function is strongly convex, we use a folklore reduction from the convex setting: start from arbitrary point θ0 ∈ Θ, and apply a convex optimization algorithm
k = O(log log n) times, where the j-th (j ∈ [k]) application uses the output from previous phase as the initial point and nj = n/k samples. In the strongly convex but possibly non-smooth case, we 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 of Feldman et al. (2020); the adaptation for our setting requires, among other modifications, a more careful analysis of the optimization trajectory. Theorem 4.8. Let ` be λ-strongly convex and L-Lipschitz over a closed convex set Θ ⊂ Rd of diameter D and ε ≤ 15. Then combining PAGD with the reduction above yields an (ε, δ)-shuffle private algorithm with population loss
E [ `(θ̄,D) ] ≤ min
θ∈Θ `(θ,D) + Õ
( L2
λn + d2/3L2 log4/3(d/δ) λε4/3n4/3
) .
If the loss function is also β-smooth, then the population loss can be improved to
E [ `(θ̄,D) ] ≤ min
θ∈Θ `(θ,D) + Õ
( L2
λn + dβ1/2L2 log2(d/δ) λ3/2ε2n2
) .

heading: 4.2 FULLY INTERACTIVE PROTOCOL
text: We conclude with fully interactive protocols, which allow a user to 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 to logarithmic factors. The pseudocode of our protocol PGD is shown in Algorithm 5. For strongly convex functions, we further divide users into disjoint groups and apply a fully interactive protocol PGD to each group in sequence, using the parameter estimate learned from one group as the initial parameter estimate for the next.
Algorithm 5 PGD, Fully interactive shuffle private gradient descent Require: Number of users n, privacy parameters ε, δ, Lipschitz parameter L, number of iterations
T , step size η 1: Initialize parameter estimate θ0 ← 0 2: for t = 1, 2, . . . , T do 3: Compute the gradient at θt,
ḡt ← 1
n PVEC
( ∇θ`(θt, x1), · · · ,∇θ`(θt, xn);
ε 2 √ 2T log(1/δ) , δ T + 1 , L ) 4: Compute and store the parameter θt+1 ← πΘ (θt + ηḡt) 5: end for 6: Output final estimate θ̄ ← 1T ∑T−1 t=0 θt
Theorem 4.9. Let ` be convex and L-Lipschitz over a closed convex set Θ ⊂ Rd of diameter D and ε ≤ 15. Then the protocol PGD is (ε, δ)-shuffle private with population loss
E [ `(θ̄,D) ] ≤ min
θ∈Θ `(θ,D) +O ( DL√ n + d1/2DL log3/2(d/δ) εn ) .
If ` is λ-strongly convex, we can further improve the population loss to
E [ `(θ̄,D) ] ≤ min
θ∈Θ `(θ,D) +O
( L2
λ
[ 1
n + d log3(d/δ) ε2n2
]) .
Details appear at the end of Appendix B; since the algorithm and analysis combines previouslydiscussed 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 PGD to these disjoint groups of users in sequence.

heading: A PROOFS FOR SUM
text: The goal of this section is to prove Lemma 3.1 and Theorem 3.2.

heading: A.1 PROOFS FOR SCALAR SUM
text: 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 : Xn → Z and parameters p ∈ (0, 1/2] and m ∈ N, let Mm,p,f : Xn → Z be the algorithm that samples η ∼ Bin(m, p) and returns f(X) + η. For any t ∈ N, X ∼ X ′ such that |f(X)− f(X ′)| ≤ t, and α ∈ (0, 1) where αmp ≥ 2t,
Dδ∞(Mm,p,f (X)||Mm,p,f (X ′)) ≤ ε
where ε = |f(X)− f(X ′)| ln 1+α1−α and δ = 2 exp(−α 2mp/10).
Proof. Fix any set of integers Z. We will show that P [Mm,p,f (X) ∈ Z] ≤ exp ( |f(X)− f(X ′)| · ln 1+α1−α ) P [Mm,p,f (X) ∈ Z]
+ 2 exp(−α2mp/10)
which is equivalent to the divergence bound.
For any integer i, we use the notation Z − i to denote the set {z − i | z ∈ Z}. Then P [Mm,p,f (X) ∈ Z] = ∑ z∈Z Pη∼Bin(m,p) [η = z − f(X)]
= ∑
ẑ∈Z−f(X)
Pη∼Bin(m,p) [η = ẑ]
≤ ∑
ẑ∈(Z−f(X))∩Q Pη∼Bin(m,p) [η = ẑ] + ∑ ẑ /∈Q Pη∼Bin(m,p) [η = ẑ] . (1)
The last inequality holds for any set Q. Our specific Q is
Q := { q ∈ Z |
Pη∼Bin(m,p) [η = q] Pη∼Bin(m,p) [η = q + f(X)− f(X ′)]
< exp ( |f(X)− f(X ′)| · ln 1+α1−α )} .
Recall that we supposed |f(X)− f(X ′)| ≤ t ≤ αmp2 . The following fact comes from Lemma 4.12 in Ghazi et al. (2021): for any k ∈ [−t, t],
PY∼Bin(m,p) [ Pη∼Bin(m,p) [η = Y ] Pη∼Bin(m,p) [η = Y + k] ≥ exp ( |k| · ln 1+α1−α )] ≤ 2 exp(−α2mp/10).
Then by substitution, (1) ≤ ∑
ẑ∈(Z−f(X))∩Q
exp ( |f(X)− f(X ′)| · ln 1+α1−α ) Pη∼Bin(m,p) [η = ẑ + f(X)− f(X ′)]
+ 2 exp(−α2mp/10) = ∑
ẑ∈(Z−f(X′))∩Q
exp ( |f(X)− f(X ′)| · ln 1+α1−α ) Pη∼Bin(m,p) [η = ẑ]
+ 2 exp(−α2mp/10) ≤ exp ( |f(X)− f(X ′)| · ln 1+α1−α ) P [Mm,p,f (X ′) ∈ Z] + 2 exp(−α2mp/10).
With Lemma A.1 in hand, we now turn to proving our main result for scalar sum, Lemma 3.1.
Lemma A.2 (Restatement of Lemma 3.1). Fix any number of users n, ε ≤ 15, and 0 < δ < 1/2. Let g ≥ ∆ √ n, b > 180g
2 ln(2/δ) ε2n , and p = 90g2 ln(2/δ) bε2n . Then 1) for any neighboring databases X ∼ X ′ ∈ [0,∆]n that differ on user u, Dδ∞((S ◦Rn1D)(X)||(S ◦Rn1D)(X ′)) ≤ ε · ( 2 g + |xu−x′u| ∆ ) ,
and 2) for any input database X ∈ [0,∆]n, the P1D(X) is an unbiased estimate of ∑n i=1 xi and has variance O(∆ + ∆ 2
ε2 log 1 δ ).
Proof. We first prove item 1. On input X , the shuffler produces a uniformly random permutation of the (g + b)n bits y1, . . . y(g+b)n. For each user i, let zi be the sum of the messages sent by user i, zi = ∑g+b j=1 ~yi,j . Then the random variable for permutations of y1, . . . y(g+b)n can also be
viewed as a post-processing of the random variable Z = ∑n i=1 zi. Let Z
′ be the analogue of Z for input database X ′, differing in user u. Then by the data-processing inequality, it suffices to prove Dδ∞(Z||Z ′) ≤ ε · (2/g + |xu − x′u|/∆). By the definition of R1D, Z is distributed as x̂u + ∑ i 6=u x̂u + Bin(bn, p) while Z
′ is distributed as x̂′u + ∑ i6=u x̂u + Bin(bn, p). We have therefore reduced the analysis to that of the binomial mechanism. Our next step is to justify that Lemma A.1 applies to our construction. Specifically, we must identify α,m, t and show p < 1/2, |x̂u − x̂′u| ≤ t, and αmp ≥ 2t. We set m = bn, t = g, and α = ε/3g. Our assumption on b implies that p < 1/2. And the fact that x̂i, x̂ ′ i both lie in the interval [0, g] implies |x̂i − x̂′i| ≤ g = t. So it remains to prove αmp ≥ 2t:
αmp = α · bn · 90g 2 ln(2/δ)
bε2n
= α · 90g 2 ln(2/δ)
ε2
= 30g ln(2/δ) ε > 2g ln(2/δ) (ε < 15) > 2t. (δ < 1/2, t = g)
Next, we derive the target bound on the divergence. Via Lemma A.1, we have that
Dδ̂∞((S ◦ Rn1D)(X)||(S ◦ Rn1D)(X ′)) ≤ ε̂,
where
ε̂ = |x̂u − x̂′u| ln 1 + α
1− α ≤ |x̂u − x̂′u| · 3α (α small)
= ε · 1 g · |x̂u − x̂′u|
≤ ε · 1 g · ( 2 + |xu − x′u| · g ∆ ) (Discretization)
= ε · ( 2
g + |xu − x′u| ∆ ) and
δ̂ = 2 exp(−α2mp/10) ≤ 2 exp ( −α2 · 9 · g 2 ln(2/δ)
ε2
) = δ.
Moving to item 2, observe that the sum of the messages produced by user i is xi + η1 + η2. Since η1 was drawn from Ber(xig/∆ − xi), E [η1] = xig/∆ − xi and Var [η1] ≤ 1/4 since any Bernoulli random variable has variance ≤ 1/4. Meanwhile, η2 is a sample from Bin(b, p) so E [η2] = bp and Var [η2] = bp(1−p) ≤ bp. Recall our definition above of zi = ∑b+g j=1 ~yi,j . Then E [zi] = xig/∆+bp
and, by the independence of η1 and η2, Var [zi] ≤ 1/4 + bp. Extending this over all n users yields E [ ∑n i=1 zi] = g ∆ ∑n i=1 xi + bnp and Var [ ∑n i=1 zi] ≤ n/4 + bnp. A1D shifts and rescales this quantity, so its final output is unbiased
E
[ ∆
g (( n∑ i=1 zi ) − bnp )] = n∑ i=1 xi
and, by our assumption that g ≥ ∆ √ n and choice of p,
Var
[ ∆
g (( n∑ i=1 zi ) − bnp )] ≤ ∆ 2 g2 (n 4 + bnp ) = O ( 1 + ∆2bnp g2 ) = O ( ∆2 ε2 log 1 δ ) .

heading: A.2 PROOFS FOR VECTOR SUM
text: Having completed our analysis of P1D, 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 γ ∈ (0, 1) and neighboring databases X,X ′ ∈ Xn. For all j ∈ [d], suppose algorithm Aj : Xn → Y use independent random bits and satisfies D δj ∞(Aj(X)||Aj(X ′)) ≤ εj . Let
ε′ = d∑ j=1 εj(e εj − 1) + 2 √√√√log(1/γ) d∑ j=1 ε2j and δ ′ = d∑ j=1 δj + γ.
Then Dδ ′ ∞(A1(X), . . . ,Ad(X)||A1(X ′) . . . ,Ad(X ′)) ≤ ε′.
Our proof follows the steps in (Dwork et al., 2010b; Asi et al., 2019) with some 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 D(Y ||Z) = Ey∈Y [ log Pr[Y = y]
Pr[Z = z]
] .
The Max Divergence between Y and Z is
D∞(Y ||Z) = max S⊆supp(Y )
[ log
Pr[Y ∈ S] Pr[Z ∈ S]
] .
The total variation distance between Y and Z is
∆(Y,Z) = max S⊆supp(Y )
|PY (S)− PZ(S)|.
The following lemma relating these notions comes from Dwork and Roth (2014).
Lemma A.5 (Lemma 3.17 and 3.18 (Dwork and Roth, 2014)). Given random variables Y and Z,
1. We have both Dδ∞(Y ||Z) ≤ ε and Dδ∞(Z||Y ) ≤ ε if and only if there exists random variables Y ′, Z ′ such that ∆(Y, Y ′) ≤ δ/(eε + 1) and ∆(Z,Z ′) ≤ δ/(eε + 1), and D∞(Y ′||Z ′) ≤ ε, and D∞(Z ′||Y ′) ≤ ε.
2. If D∞(Y ||Z) ≤ ε and D∞(Z||Y ) ≤ ε, then D(Y ||Z) ≤ ε(eε − 1).
For the first claim, Dwork and Roth (2014) only explicitly proves that D∞(Y ′||Z ′) ≤ ε, but their construction of Y ′ and Z ′ also implies D∞(Z ′||Y ′) ≤ ε. We now have the tools to prove our variant of advanced composition, Lemma A.3.
Proof of Lemma A.3. For any neighboring datasets X and X ′, let Y = (Y1, Y2, . . . , Yd) and Z = (Z1, Z2, . . . , Zd) denote the outcomes of runningA1, . . . ,Ad on X,X ′ respectively. By Fact 2.3 and the first part of Lemma A.5, there exist random variables Y ′ = (Y ′1 , . . . , Y ′ d) and Z ′ = (Z ′1, . . . , Z ′ d) such that, for any j ∈ [d], the following four inequalities hold: (i) ∆(Yj , Y ′j ) ≤ δj/(eεj + 1), (ii) ∆(Zj , Z ′ j) ≤ δj/(eεj + 1), (iii) D∞(Y ′j ||Z ′j) ≤ εj , and (iv) D∞(Z ′j ||Y ′j ) ≤ εj . Then
∆(Y, Y ′),∆(Z,Z ′) ≤ d∑ j=1 δj eεj + 1 < 1 2 d∑ j=1 δj .
Consider the outcome set B = {v ∈ Rd : Pr[Y ′ = v] ≥ eε′ Pr[Z ′ = v]}. It remains to prove Pr[Y ′ ∈ B] ≤ γ. For any fixed realization v = (v1, . . . , vd) ∈ Rd, we have
log
( Pr[Y ′ = v]
Pr[Z ′ = v]
) = d∑ j=1 log ( Pr[Y ′j = vj ] Pr[Z ′j = vj ] ) , d∑ j=1 cj
where the first step follows from independence and the last step defines cj . Since D∞(Y ′j ||Z ′j) ≤ εj and D∞(Z ′j ||Y ′j ) ≤ εj , we know that |cj | ≤ εj , and by the second part of Lemma A.5
Evj∼Yj [cj ] = Evj∼Yj
[ log ( Pr[Y ′j = vj ]
Pr[Z ′j = vj ]
)] ≤ εj(eεj − 1).
Thus we have
Pr [Y ′ ∈ B] = Pr  d∑ j=1 cj ≥ ε′ 
= Pr  d∑ j=1 cj ≥ d∑ j=1 εj(e εj − 1) + 2 √√√√log(1/γ) d∑ j=1 ε2j  ≤ γ. by a Chernoff-Hoeffding bound. Tracing back, P [Y ′ ∈ B] ≤ γ implies Dγ∞(Y ′||Z ′) ≤ ε′. Our previous bounds on ∆(Y, Y ′) and ∆(Z,Z ′) then give D ∑d j=1 δj+γ ∞ (Y ||Z) ≤ ε′.
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 < ε ≤ 15, 0 < δ < 1/2, d, n ∈ N, and ∆2 > 0, there are choices of parameters b, g ∈ N and p ∈ (0, 1/2) for P1D (Algorithm 3.1) such that, for inputs ~X = (~x1, . . . , ~xn) of vectors with maximum norm ||~xi||2 ≤ ∆2, 1) PVEC is (ε, δ)-shuffle private and, 2) PVEC( ~X) is an unbiased estimate of ∑n i=1 ~xi and has bounded variance
E ∥∥∥∥∥PVEC( ~X)− n∑ i=1 ~xi ∥∥∥∥∥ 2
2
 = O(d∆22 ε2 log2 d δ ) .
Proof. We set g = max(2∆2 √ n, √ d, 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, ~x1 6= ~x′1. Then the `2 sensitivity is∥∥∥∥∥ n∑ i=1 ~xi − n∑ i=1 ~x′i ∥∥∥∥∥ 2 = ‖~x1 − ~x′1‖2 ≤ 2∆2. (2)
From our definition of ~wi,j in line 4 of the pseudocode for PVEC and the fact that ‖~xi‖2 ≤ ∆2, ~wi,j ≥ 0 and ~wi,j ≤ ‖~xi‖∞ + ∆2 ≤ ‖~xi‖2 + ∆2 ≤ 2∆2. This means the sensitivity of the value of ~wi,j is 2∆2.
For each coordinate j ∈ [d], we use aj to denote the absolute difference in the j-th coordinate, aj := |~x1,j − ~x′1,j | = |~w1,j − ~w′1,j |
Let γ, δ̂ = δ/(d + 1) and ε̂ = ε/18 √ log(1/γ). Because g ≥ 2∆2 √ n, we may use Lemma 3.1 to set b, p such that
Dδ̂∞((S ◦ Rn1D)(Wj)||(S ◦ Rn1D)(W ′j)) ≤ ε̂ · ( 2
g + aj 2∆2
) , εj
where we use Wj to denote (w1,j , . . . , wn,j) and the last step defines εj . Notice that∑ j∈[d] ε2j = ε̂ 2 · ∑ j∈[d] 4 g2 + 2aj ∆2g + a2j 4∆22
≤ ε̂2 · ( 4d
g2 + 2‖~x1 − ~x ′1‖1 ∆2g + ‖~x1 − ~x ′1‖22 4∆22
) (Def of aj)
≤ ε̂2 ·
( 4d
g2 +
2 √ d‖~x1 − ~x ′1‖2
∆2g + ‖~x1 − ~x ′1‖22 4∆22
)
≤ ε̂2 ·
( 4d
g2 +
4 √ d
g + 1
) (Via (2))
≤ ε̂2 · (4 + 4 + 1) = 9ε̂2 (3)
The final inequality comes from the fact that g ≥ √ d. By our choices of ε̂, γ, and δ̂, we apply Lemma 3.3 to conclude that
Dδ∞((S ◦ RnVEC)( ~X)||(S ◦ RnVEC)( ~X ′)) ≤ d∑ j=1 εj(e εj − 1) + 2 √√√√log(1/γ) d∑ j=1 ε2j
≤ d∑ j=1 2ε2j + 2 √√√√log(1/γ) d∑ j=1 ε2j
≤ 18ε̂2 + 6ε̂ √
log(1/γ) (Via (3)) ≤ ε (Choice of ε̂)
which is precisely (ε, δ)-differential privacy by Fact 2.3. Note that the second inequality holds because g ≥ 4 implies εj ≤ ε̂ ≤ ε/18. Since ε ≤ 15, we get εj < 1, and eεj − 1 ≤ 2εj . The estimator produced byPVEC is unbiased because each invocation ofP1D yields unbiased estimates. And we have, by linearity and the variance bound of P1D,
E ∥∥∥∥∥PVEC( ~X)− n∑ i=1 ~xi ∥∥∥∥∥ 2
2
 = d∑ j=1 E ∣∣∣∣∣PVEC( ~Xj)− n∑ i=1 ~xi,j ∣∣∣∣∣ 2  = O(d∆22 ε̂2 log ( 1 δ̂ )) .
The theorem statement follows by substitution.

heading: A.3 ROBUST PRIVACY OF SUM
text: We now discuss the robustness of our privacy guarantees, as mentioned at the end of Section 3.1. In more detail, we slightly generalize the privacy analysis of P1D to account for the case where a γ fraction of the users are honest. Because P1D is used as a building block for the other protocols we 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 et al. (2021)). Fix γ ∈ (0, 1]. A protocol P = (R,A) is (ε, δ, γ)-robustly shuffle differentially private if, for all n ∈ N and γ′ ≥ γ, the algorithm S◦Rγ′n is (ε, δ)-differentially private. In other words, P guarantees (ε, δ)-shuffle privacy whenever at least a γ fraction of users follow the protocol.
Although the above definition only explicitly handles drop-out attacks by 1− γ malicious users, this is without loss of generality: any messages sent to the shuffler from the malicious users constitute a post-processing of S ◦ Rγn.
Now, we show that reducing the number of participants in P1D loosens the bound on the divergence in a smooth fashion. Because P1D is the building block of our other protocols, they inherit its robustness. The statement requires γ ≥ 1/3, but this constant is arbitrary; changing it to a different value will only influence the lower bound on g. Claim A.8. Fix any γ ∈ [1/3, 1], any number of users n, ε ≤ 1, and 0 < δ < 1. If g ≥ 3, b > 180 · g 2
ε2n ln 2 δ , and p = 90 ·
g2
bε2n ln 2 δ then, for any neighboring databases X ∼ X ′ ∈ [0,∆]n that differ on user u,
Dδ∞((S ◦ R γn 1D)(X)||(S ◦ R γn 1D)(X ′)) ≤ ε γ · ( 2 g + |xu − x′u| ∆ ) .
This implies P1D satisfies (O(ε/γ), δ, γ)-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(γbn, p). This means we take m = γbn. We again set t = g but now α = ε/3γg. Note that α < 1/3 because ε ≤ 1 and γg > 3γ > 1. As before, our assumption on b implies that p < 1/2 and we have |x̂u − x̂′u| ≤ g = t. So it remains to prove αmp ≥ 2t in order to apply Lemma A.1:
αmp = α · γbn · 90g 2 ln(2/δ) bε2n = α · γ · 90g 2 ln(2/δ) ε2 = 30g ln(2/δ) ε > 2t
Now we derive the target bound on the divergence. Via Lemma A.1, we have that
Dδ̂∞((S ◦ Rn1D)(X)||(S ◦ Rn1D)(X ′)) ≤ ε̂, where
ε̂ = |x̂u − x̂′u| ln 1 + α
1− α ≤ |x̂u − x̂′u| · 3α (α small)
= ε γ · 1 g · |x̂u − x̂′u|
≤ ε γ · 1 g · ( 2 + |xu − x′u| · g ∆ ) (Discretization)
= ε γ · ( 2 g + |xu − x′u| ∆ ) and
δ̂ = 2 exp(−α2mp/10)
= 2 exp(−α2 · 9γ · g 2 ln(2/δ)
ε2 )
= 2 exp(− 1 γ · ln(2/δ))
≤ 2 exp(− ln(2/δ)) = δ
This concludes the proof.
When we replace ε in the proof of Theorem 3.2 with ε/γ, we can invoke Claim A.8 to derive the following statement about the robust shuffle privacy of PVEC. Corollary A.9. For any 0 < ε ≤ 1, 0 < δ < 1, d, n ∈ N, and ∆2 > 0, there are choices of parameters b, g ∈ N and p ∈ (0, 1/2) for P1D (Algorithm 3.1) such that, for inputs ~X = (~x1, . . . , ~xn) of vectors with maximum norm ||~xi||2 ≤ ∆2 and any γ ∈ [1/3, 1], PVEC is (ε/γ, δ, γ)-robustly 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.

heading: B PROOFS FOR SECTION 4

heading: B.1 PROOFS FOR SECTION 4.1
text: We start by proving the guarantee for PSGD, Theorem 4.1. 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 Θ ⊂ Rd, we say G : Θ→ Rd is an LG-noisy gradient oracle for ` if for every θ ∈ Θ, (1) EG [G(θ)] ∈ ∂`(θ), and (2) EG [ ||G(θ)||22 ] ≤ L2G. Furthermore, we say
the gradient oracle G has variance at most σ2 if EG [ ‖G(θ)− EG [G(θ)] ‖22 ] ≤ σ2.
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 iteration, then its output satisfies
E [ `(θ̄,D) ] ≤ min
θ∈Θ `(θ,D) + D
2 2ηT + ηL2G 2 .
We now have the tools to prove Theorem 4.1.
Proof of Theorem 4.1. 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 t ∈ {0, 1, . . . , T − 1}, we write the gradient ḡt = 1b ∑b i=1∇θ`(θt−1, xt,i) + Zt. By Theorem 3.2, we know that Ext,1,...,xt,b,Zt [ḡt] = Ex∼D [∇θ`(θt−1, x)]
and
Ext,1,...,xt,b,Zt [ ||ḡt||22 ] = Ext,1,...,xt,b,Zt ∣∣∣∣∣ ∣∣∣∣∣1b b∑ i=1 ∇θ`(θt−1, xt,i) + Zt ∣∣∣∣∣ ∣∣∣∣∣ 2
2  = Ext,1,...,xt,b ∣∣∣∣∣ ∣∣∣∣∣1b b∑ i=1 ∇θ`(θt−1, xt,i) ∣∣∣∣∣ ∣∣∣∣∣ 2
2 + E [‖Zt‖22] ≤ L2 +O ( dL2 log2(d/δ)
b2ε2
) , (4)
where the second equality uses the independence of the data and noise, and the inequality follows from ` being L-Lipschitz and Theorem 3.2.
The gradient ḡt therefore qualifies as a noisy gradient oracle call with L2G = L 2 +O
( dL2 log2(d/δ)
b2ε2
) .
By Lemma 4.2 and the fact that there are n/b iterations, we get E [ `(θ̄,D) ] ≤ min
θ∈Θ `(θ,D) + D
2 2ηT + ηL2G 2
≤ min θ∈Θ `(θ,D) + DLG√ T
(AM-GM ineq.)
= min θ∈Θ
`(θ,D) +D
√ 1
T
( L2 +O ( dL2 log2(d/δ)
b2ε2
))
= min θ∈Θ
`(θ,D) +O DL √ b
n + d log2(d/δ) ε2bn  (T = n/b) = min
θ∈Θ `(θ,D) +O
( d1/4DL log1/2(d/δ)√
εn
) ,
The final step uses our choice of b = √ d log(d/δ)
ε
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 ∈ [T ], let Zt be the noise introduced by the summation protocol PVEC and let ḡt = 1b ∑b i=1∇θ`(θt−1, xt,i) + Zt. We first bound the variance:
E [ ‖G(θt−1)− E [G(θt−1)] ‖22 ] = Ext,1,...,xt,b,Zt ∣∣∣∣∣ ∣∣∣∣∣1b b∑ i=1 ∇θ`(θt−1, xt,i) + Zt − Ex∼D [∇`(θt−1, x)] ∣∣∣∣∣ ∣∣∣∣∣ 2
2  = Ext,1,...,xt,b ∥∥∥∥∥1b b∑ i=1 ∇`(θt−1, xt,i)− Ex∼D [∇`(θt−1, x)] ∥∥∥∥∥ 2
2 + E [‖Zt‖22] = Var [ 1
b b∑ i=1 ∇`(θt−1, xt,i)
] + E [ ‖Zt‖22
] = 1
b Var [∇`(θt−1, xt,1)] + E
[ ‖Zt‖22 ] = 1
b Ext∼D
[ ‖∇`(θt−1, xt)− Ex [∇`(θt−1, x)]‖22 ] + E [ ‖Zt‖22 ] = O ( L2
b + dL2 log2(d/δ) b2ε2
) . (5)
The second equality comes from the fact that the data and noise are independent, the fourth equality uses the independence of xt,1, · · · , xt,b and (5) follows from Theorem 3.2. Next, we use the following result from Lan (2012).
Lemma B.3 (Restatement of Lemma 4.4). Suppose PAGD receives a noisy gradient oracle with variance (at most) σ2 in each iteration. Taking Lt = 1t+1 ((T + 2) 3/2 σ D + β), αt = 2 t+2 , then the population loss of PAGD can be bounded as
E [ `(θ̄,D) ] ≤ min
θ∈Θ `(θ,D) +O
( βD2
T 2 + Dσ√ T
) .
In our case, we have σ2 = L 2 b + dL2 log2(d/δ) b2ε2 so that
E [ `(θ̄,D) ] ≤ min
θ∈Θ `(θ,D) +O
( βD2
T 2 + Dσ√ T
)
≤ min θ∈Θ `(θ,D) +O βD2 T 2 + D √ L2 b + dL2 log2(d/δ) b2ε2√ T  ≤ min
θ∈Θ `(θ,D) +O
( βD2
T 2 + DL√ bT +
√ dDL log(d/δ)
bε √ T
)
= min θ∈Θ
`(θ,D) +O
( b2βD2
n2 + DL√ n +
√ dDL log(d/δ)
ε √ bn
)
= min θ∈Θ
`(θ,D) +O
( d2/5β1/5D6/5L4/5 log4/5(d/δ)
ε4/5n4/5 + DL√ n
) .
The first step follows from Lemma 4.4, and the second step comes from Eq. (5). In the last step, we substitute b = n
3/5d1/5L2/5 log2/5(d/δ) ε2/5β2/5D2/5 .
Next, we prove our improved guarantee for convex losses by combining PAGD and smoothing (Theorem 4.7).
Proof of Theorem 4.7. We directly optimize the loss function `β with PAGD. PAGD only requires the gradient∇`β(θmdt , x) (t ∈ [T ]). By the second item in Lemma 4.6, this can be obtained by computing β(θmdt − prox`/β(θmdt )). Moreover, since `β is 2L-Lipschitz, PAGD still guarantees (ε, δ)-differential privacy with a constant scaling of the noise. For accuracy, we have that
E [ `(θ̄,D) ] −min θ∈Θ `(θ,D) ≤ E [ `β(θ̄,D) ] −min θ∈Θ `β(θ,D) + L2 β
≤ O ( DL√ n ) +O ( d2/5β1/5D6/5L4/5 log4/5(d/δ) ε4/5n4/5 ) + L2 β
≤ O ( DL√ n + d1/3DL log2/3(d/δ) ε2/3n2/3 ) .
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 `β is β-smooth, and the last step comes from our choice of β = ε
2/3n2/3L d1/3D log2/3(d/δ) .
Finally, we prove Theorem 4.8, which applies to strongly convex ` and is the final result about sequentially interactive protocols.
Proof of Theorem 4.8. 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.
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 θ̄i be the output of the i-th phase and θ∗ = arg minθ∈Θ `(θ,D). Denote D2i = E [ ‖θ̄i − θ∗‖22 ] and
∆i = E [ `(θ̄i,D)− `(θ?,D) ] .
Due to the λ-strong convexity, we have D2i ≤ 2∆iλ . Since the guarantee of Theorem 4.7 uses D as a bound on the distance between the starting point and optimum, we have
∆i+1 ≤ C ( DiL√ ni + d1/3DiL log 2/3(d/δ)
ε2/3n 2/3 i
) ≤ √
2∆i λ · C ( L √ ni + d1/3L log2/3(d/δ)
ε2/3n 2/3 i ) := √
∆iE
Here C is an universal constant, and the last step defines E. Hence, one has
∆i+1 E2
≤ √
∆i E2 .
We know that ∆1 ≤ 2L2/λ (due to strong convexity), E2 ≥ 2L2/λn (due to definition), and therefore, ∆1/E2 ≤ O(n). Hence, after k = O(log log n) phases, we have ∆k/E2 ≤ 2, and the population loss is
E [ `(θ̄,D) ] ≤ min
θ∈Θ `(θ,D) +O  1 λ · ( L √ nk + d1/3L log2/3(d/δ)
n 2/3 k ε 2/3 )2 ≤ min
θ∈Θ `(θ,D) + Õ
( L2
λn + d2/3L2 log4/3(d/δ) λε4/3n4/3
) .
This completes the proof for the non-smooth setting. Turning to the setting where ` is also β-smooth, let A = d
2/5β1/5L4/5 log4/5(d/δ) ε4/5 . Then our algorithm guarantees
∆i+1 ≤ C
( AD
6/5 i
n 4/5 i
+ LDi√ ni
) ≤ 2C ( A∆ 3/5 i
λ3/5n 4/5 i
+ L √
∆i√ λni
) (6)
for some constant C > 1.
First, suppose there exists i ∈ [k] such that ∆i is already small, i.e. ∆i ≤ 210C4 ( L2
λni +
A5/2
λ3/2n2i
) := T.
Then we claim ∆t ≤ 210C4 ( L2
λni + A
5/2
λ3/2n2i
) holds for all t ≥ i. We divide into cases.
Case 1. Suppose L 2
λni ≤ A
5/2
λ3/2n2i . Then we have
∆i+1 ≤ 4C · ( 26C3 A5/2
λ2/3n2i+1 + 25C3
LA5/4
λ5/4n 3/2 i+1
)
≤ 4C · ( 26C3 A5/2
λ2/3n2i + 25C3
A5/2
λ2/3n2i ) ≤ 210C4 A 5/2
λ3/2n2i .
The first step follows from Eq. (6), ni = ni+1 = n/k, the second step follows our assumption.
Case 2. Suppose L 2
λni ≥ A
5/2
λ3/2n2i . Then we have
∆i+1 ≤ 4C · ( 26C3 AL6/5
λ6/5n 7/5 i+1
+ 25C3 L2
λni+1
)
≤ 4C · ( 26C3 L2
λni + 25C3
L2
λni ) ≤ 210C4 L 2
λni .
The first step follows from Eq. (6), ni = ni+1 = n/k, the second step follows our assumption. Next, suppose ∆i ≤ T = 210C4 ( L2
λni + A
5/2
λ3/2n2i
) , then we claim that ∆i+1 is decreasing, i.e.,
∆i+1 ≤ ∆i. Suppose this does not hold, since we have one of the following should hold
2C A∆
3/5 i
λ3/5n 4/5 i+1
≥ ∆i 2
or 2C L √ ∆i√ λni+1 ≥ ∆i 2 .
We argue this can not happens, since the former one implies ∆i ≤ 25C5/2 A 5/2
λ3/2n2i and the later implies
∆i ≤ 24C2 Lλni .
Combining the above argument, we know that ∆i is decreasing, until it goes below a threshold T , and after that, the value ∆i will always below such the threshold T . Now, suppose after k = O(log log n) iterations, ∆k is still above the threshold T , then we know {∆i}i∈[k] is decreasing and we divide the algorithmic procedure into two phases. In the first phase, we have L √
∆i√ λn ≤ A∆
3/5 i
λ3/5n 4/5 i
, this happens
when ∆i ≥ L 10λ
A10n3i , and the algorithm satisfies
∆i+1 ≤ 4C A∆
3/5 i
λ3/5n 4/5 i+1
= 4C A∆
3/5 i
λ3/5n 4/5 i
.
For the second phase, we have L √
∆i√ λn ≥ A∆
3/5 i
λ3/5n4/5 and this happens when this happens when ∆i ≤
L10λ A10n3i , and the algorithm satisfies
∆i+1 ≤ 4C L √ ∆i√ λni+1 = 4C L √ ∆i√ λni .
We know one of the two phases will run for more than Ω(log log n) iterations. Suppose the former
case holds, i.e., ∆i+1 ≤ 4C A∆
3/5 i
λ3/5n 4/5 i
. Let E = ( 4CA
λ3/5n 4/5 i
)5/2 ≤ 25C5/2 A 5/2
λ3/2n2i . Then, we have
∆i+1 E ≤ ( ∆i E )3/5 .
It is easy to verify that ∆1/E ≤ poly(n), and therefore, after Ω(log log n) iterations, we know that ∆i will drop below O(E) = 25C5/2 A 5/2
λ3/2n2i ≤ T .
When later case holds, i.e., ∆i+1 ≤ 4C L √
∆i√ λni . Let E = 16C2 L 2 λni , then we know that
∆i+1 E ≤ ( ∆i E )1/2 .
It is easy to verify that ∆1/E ≤ poly(n), and therefore, after Ω(log log n) iterations, we know that ∆i will drop below O(E) = 16C2 L 2
λni ≤ T .
In summary, taking k = Ω(log log n), we know that
E [ `(θ̄k,D) ] −min θ∈Θ `(θ,D) = ∆k ≤ T = 210C4 ( L2 λnk + A5/2 λ3/2n2k ) ≤ Õ ( L2
λn + dβ1/2L2 log(d/δ)2 λ3/2ε2n2
) .
This concludes the proof.

heading: B.2 PROOFS FOR SECTION 4.2
text: We now turn to proofs for our fully interactive protocol, PGD. The first step will be proving Lemma B.6, which provides a privacy and population loss guarantee for PGD when the loss function ` is smooth. We will later combine this analysis for smooth losses with the smoothing trick used in the previous section to obtain guarantees for non-smooth losses. Since PGD 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 a result bounding empirical loss. Lemma B.4 (Bubeck et al. (2015)). Let ` be convex and L-Lipschitz over closed convex set Θ ⊂ Rd of diameter D. Let σ2 denote the variance of the privacy noise in the gradient update step of PGD. For any set of data points S and η > 0, the output of PGD satisfies
E [ `(θ̄, S) ] −min θ∈Θ `(θ, S) ≤ D 2 2ηT + η(L2 + σ2) 2 .
Next, we bound generalization error. Lemma B.5 (Lemma 3.4 (Bassily et al., 2019)). Suppose ` is convex, L-Lipschitz, and β-smooth over closed convex set Θ ⊂ Rd of diameter D and η ≤ 2β . Then PGD is α-uniformly stable with α = L2 Tηn . In other words, it satisfies
ES∼Dn [ |`(θ̄, S)− `(θ̄,D)| ] ≤ L2Tη
n .
With these two tools, we can state and prove Lemma B.6 Lemma B.6. Let ` be convex, L-Lipschitz, and β-smooth over a closed convex set Θ ⊂ Rd of diameter D. Then PGD is (ε, δ)-shuffle private with population loss
E [ `(θ̄,D) ] ≤ min
θ∈Θ `(θ,D) +O ( DL√ n + d1/2DL log3/2(d/δ) εn ) .
Proof. For the privacy guarantee, since each iteration guarantees ( ε 2 √ 2T log(1/δ) , δT+1 )-differential privacy, and the algorithm runs for T iterations in total, advanced composition implies (ε, δ)-shuffle privacy overall.
We now focus on the loss guarantee. First, by Lemma B.4, the empirical loss satisfies
E [ `(θ̄;S) ] ≤ min
θ∈Θ `(θ;S) +
D2 2ηT + ηL2G 2
≤ min θ∈Θ
`(θ;S) + D2 2ηT + ηL2 2 +O
( ηdTL2 log3(nd/δ)
2n2ε2 ) where the second step follows from L2G ≤ L2 + O( dTL2 log3(nd/δ) n2ε2 ) (see Eq. (4)). Moreover, by Lemma B.5, we know the generalization error is most L2 Tηn . Hence, for S ∼ D n,
E [ `(θ̄;D) ] −min θ∈Θ `(θ,D) ≤E [ |`(θ̄,D)− `(θ̄, S)| ] + E [ `(θ̄, S)−min θ∈Θ `(θ, S) ] ≤ D 2
2ηT + ηL2 2 + ηdTL2 log3(nd/δ) 2n2ε2 + L2 Tη n
≤ O
DL √ d log3(nd/δ)
εn + DL√ n  The second step follows from Lemma B.5 and Lemma 4.2. Especially, we take expectation over S ∼ Dn in Lemma 4.2. The last step follows by taking η = D
L √ T
and T = min{n, ε 2n2
d log2(nd/δ) }. We
use δ 1/n for the final statement.
We can now prove Theorem 4.9. As done previously, we use Moreau envelope smoothing to apply the guarantee of Lemma B.6. For the strongly convex case, we apply the same reduction to 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 `β with β = LD min (√ n, εn d1/2 log3/2(nd/δ) ) . Optimizing `β yields
ES∼Dn [ `(θ̄;D) ] −min θ∈Θ `(θ̄,D)
≤ ES∼Dn [ `β(θ̄;D) ] −min θ∈Θ `β(θ̄,D) + L2 2β
≤ O ( DL√ n + d1/2DL log3/2(d/δ) εn ) + LD · ( 1 2 √ n + d1/2 log3/2(d/δ) 2εn )
= O ( DL√ n + d1/2DL log3/2(d/δ) εn ) .
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 β.
For strongly convex losses, we use the same reduction as (Feldman et al., 2020).
Lemma B.7 (Theorem 5.1 in (Feldman et al., 2020)). Suppose for any loss function that is convex and L-Lipschitz over a closed convex set Θ ⊂ Rd of diameter D, there is an (ε, δ)-differentially private algorithm that achieves excess population loss of order
LD ( 1√ n + √ d ρn ) .
Then for any λ-strongly convex, L-Lipschitz loss function, there is an (ε, δ)-differentially private algorithm that achieves excess population loss of order
L2
λ
( 1
n +
d
ρ2n2
) .
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 ρ = ε
log3/2(nd/δ) , we get the desired guarantee for strongly
convex functions.

heading: B.3 SCO COMMUNICATION AND RUNTIME
text: Recall from the discussion at the end of Section 3.1 that, with the scaling by ∆ trick, each user sends O(d[ √ n+ log(1/δ)/ε2]) bits in each n-user invocation of PVEC, and the analyzer processes these in
time O(dn[ √ n+ log(1/δ)/ε2]). 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. In the algorithm described in Theorem 4.1, each user sends O(d[ √ b+ log(1/δ)/ε2]) bits and the total runtime is
O ( dn [√ b+ log(1/δ)
ε2
]) = O ( dn [ d1/4 √ log(d/δ)
ε +
log(1/δ)
ε2
]) .
Corollary B.9. In the algorithm described in Theorem 4.3, each user sends O(d[ √ b+ log(1/δ)/ε2]) bits and the total runtime is
O ( dn [√ b+ log(1/δ)
ε2
]) = O ( dn [ d1/10n3/10L1/5 log1/5(d/δ)
ε1/5β1/5D1/5 +
log(1/δ)
ε2
]) .
Corollary B.10. In the algorithm described in Theorem 4.7, each user sendsO(d[ √ b+log(1/δ)/ε2]) bits and the total runtime is
O ( nd [√ b+ log(1/δ)
ε2
]) = O ( nd [ d1/6n1/6 log1/3(d/δ)
ε1/3 +
log(1/δ)
ε2
]) .
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. In the algorithm described in Theorem 4.9, each user sends
O ( dT [√ n+ log(1/δ)
ε2
]) = min { n,
ε2n2
d log2(nd/δ)
} ·O ( d [√ n+ log(1/δ)
ε2 ]) bits in total, and the total runtime is
O ( dnT [√ n+ log(1/δ)
ε2
]) = min { n,
ε2n2
d log2(nd/δ)
} ·O ( dn [√ n+ log(1/δ)
ε2
]) .

heading: C PAN PRIVATE CONVEX OPTIMIZATION
text: 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-processing algorithm’s internal state. We formalize the model and provide definition in Section C.1, 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).

heading: C.1 MODELS AND DEFINITION
text: 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 a 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 is below. Definition C.1. An online algorithm Q is defined by an internal algorithm QI and an output algorithm QO. Q processes a stream of elements through repeated application of QI : X × I → I, which (with randomness) maps a stream element and internal state to an 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-privacy requires the algorithm’s internal state and output to be differentially private with regard to neighboring streams. Definition C.2 (Dwork et al. (2010a); Amin et al. (2020)). Given an online algorithm Q, let QI(X) denote its internal state after processing stream X , and let X≤t be the first t elements of X . We say Q is (ε, δ)-pan-private if, for every pair of neighboring streams X and X ′, every time t and every set of internal state, output state pairs T ⊂ I ×O,
PQ [( QI(X≤t),QO(QI(X)) ) ∈ T ] ≤ eε · PQ [( QI(X ′≤t),QO(QI(X ′)) ) ∈ T ] + δ. (7)
When δ = 0, we say Q is ε-pan-private.

heading: C.2 ALGORITHMS
text: Due to the structural similarity between sequential shuffle privacy and pan-privacy, all the results developed in Section 4.1 have pan-private counterparts. Theorem C.3. Suppose a convex loss function ` is L-Lipschitz over a closed convex set Θ ⊂ Rd, then there exists an algorithm with output θ̄ that guarantees (ε, δ)-pan privacy, and:
(1) When the loss function is non-smooth, then the population loss satisfies
`(θ̄,D) ≤ min θ∈Θ `(θ,D) +O ( DL√ n + d1/3DL log1/3(1/δ) ε2/3n2/3 ) .
(2) When the loss function is β-smooth, then the population loss satisfies
`(θ̄,D) ≤ min θ∈Θ `(θ,D) +O ( DL√ n + d2/5β1/5D6/5L4/5 log2/5(1/δ) ε4/5n4/5 ) .
(3) When the loss function is λ-strongly convex, then the population loss satisfies
`(θ̄,D) ≤ min θ∈Θ `(θ,D) + Õ
( L2
λn + d2/3L2 log2/3(1/δ) λε4/3n4/3
) .
(4) When the loss function is λ-strongly convex and β-smooth then the the population loss satisfies
`(θ̄,D) ≤ min θ∈Θ
`(θ,D) + Õ ( L2
λn + dβ1/2L2 log(1/δ) λ3/2ε2n2
) .
Proof. We analyze the pseudocode presented in Algorithm 6. Although it does not explicitly obey the syntax of an online algorithm given in Definition C.1, it is straightforward to see that the internal state is the tuple (θt, θ ag t , θ md t , gt) and an update to gt occurs when any data point is read. The updates to the θ variables also occur after the last data point of a batch is read.
We first prove Algorithm 6 is (ε, δ)-pan private.
Lemma C.4. For 0 < ε, δ < 1, Algorithm 6 is (ε, δ)-pan-private.
Algorithm 6 Pan-private AC-SA Require: Batch size b, privacy parameter ε, stream length n, learning rate sequence {Lt}, {αt}
1: Initialize noise parameter ζ2 ← 8L 2 log(2/δ) b2ε2 2: Initialize parameter estimate θag1 = θ1 ∈ Θ, and set number of iterations T = bn/bc 3: for t = 1, 2, . . . , T do 4: Draw fresh noise Zt ← N ( 0, ζ2Id
) 5: Initialize gradient estimate ḡt ← Zt 6: for i = 1, 2, . . . , b do 7: Update gradient estimate ḡt ← ḡt + 1b∇θ`(θ md t , xt,i) 8: end for 9: ḡt ← ḡt +N ( 0, ζ2Id
) 10: Update parameter estimate θt+1 ← arg minθ∈Θ { 〈ḡt, θ − θt〉+ Lt2 ‖θ − θt‖ 2 2
} 11: Update aggregated parameter estimate θagt+1 ← αtθt+1 + (1− αt)θ ag t 12: Update middle parameter estimate θmdt+1 ← αtθt+1 + (1− αt)θ ag t . 13: end for 14: Output θagT+1
Proof. Let t∗ (resp. i∗) be the batch number (resp. position within the batch) where the adversary intrudes. We will show that
Dδ∞(θt∗ , θ ag t∗ , θ md t∗ , gt∗ , θ ag T+1||θ ′ t∗ , θ ag t∗ ′, θmdt∗ ′, g′t∗ , θ ag T+1 ′) ≤ ε
where the ′ indicates variables generated from an execution on neighboring stream X ′.
For neighboring streams X,X ′, let t denote the batch number and let i denote the number of the sample within the batch where the two streams differ. We will perform case analysis around t.
Case 1: t∗ < t. Here, the tuple (θt∗ , θ ag t∗ , θ md t∗ , gt∗) is identically distributed with (θ ′ t∗ , θ ag t∗ ′, θmdt∗ ′, g′t∗) which means we only need to prove Dδ∞(θ ag T+1||θ ag T+1 ′) ≤ ε.
Observe that θagT+1 (resp. θ ag T+1 ′) is a post-processing of (θt, θ ag t , θ md t , gt) (resp. (θ ′ t, θ ag t ′, θmdt ′, g′t)), which means that we only need to bound Dδ∞(θt, θ ag t , θ md t , gt||θ′t, θ ag t ′, θmdt
′, g′t). Furthermore, the parameter estimates are generated from a post-processing of the gradient updates, it suffices to bound Dδ∞(gt||g′t) after line 9. Recall the Gaussian mechanism:
Lemma C.5. For ε < 1 and function f : An → Bd on size-n databases with `2-sensitivity
∆2(f) = max neighboring a,a′∈An
||f(a)− f(a′)||2
outputting
f(a) +N ( 0, 2∆2(f) 2 log(2/δ)
ε2 Id ) where Id is the d-dimensional identity matrix, is (ε, δ)-centrally private.
For a proof, refer to Theorem A.1 in the survey of Dwork and Roth (Dwork and Roth, 2014).
Since ` is L-Lipschitz in θ, for any x we have ||5θ`(·, x)||2 ≤ L. Thus
max x,x′∈X
||5θ`(·, x)−5θ`(·, x′)||2 ≤ 2L.
Thus if we define f(xt,1, . . . , xt,b) = 1b ∑b i=15θ`(θt, xt,i), we get ∆2(f) ≤ 2L b . By Lemma C.5, it
follows that our addition of Zt ∼ N ( 0, 8L 2 log(2/δ) b2ε2 ) noise guarantees (ε, δ)-privacy
Case 2: t∗ = t. We break into more cases around i∗.
When i ≤ i∗ < b, the adversary only observes a change to the gradient (line 7). Specifically, the tuple (θt∗ , θ ag t∗ , θ md t∗ , θ ag T+1) is identically distributed with (θ ′ t∗ , θ ag t∗ ′, θmdt∗ ′, θagT+1 ′) which means it suffices to prove Dδ∞(gt||g′t) ≤ ε after line 7. This follows from the privacy of the Gaussian mechanism.
When i ≤ b = i∗, observe that the parameter updates are post-processing of the gradient update. We again use the privacy of the Gaussian mechanism.
When i∗ < i, we re-use the arguments from Case 1. The noise from line 9 provide privacy.
Case 3: t∗ > t. Observe that θagT+1 (resp. θ ag T+1 ′) is a post-processing of (θt∗ , θ ag t∗ , θ md t∗ , gt∗) (resp. (θ ′ t∗ , θ ag t∗ ′, θmdt∗
′, g′t∗)), which means that we only need to bound Dδ∞(θt∗ , θ ag t∗ , θ md t∗ , gt∗ ||θ′t∗ , θ ag t∗ ′, θmdt∗
′, g′t∗). But the random variables in question are obtained by post-processing (θt, θ ag t , θ md t , gt) and (θ ′ t, θ ag t ′, θmdt
′, g′t). We use the same line of reasoning as Case 1 to bound the divergence.
The main tool for our utility guarantees is bounding the variance of the noise added for privacy, analogous to the variance guarantee of Theorem 3.2. Once we have that result, the remaining analyses are essentially unchanged from their shuffle counterparts, apart from slightly different choices for parameters b and β, which are straightforward algebraic consequences of the different variance guarantee. As a result, we only bound the variance.
For each time step t ∈ [T ], the gradient ḡt = 1b ∑b i=1∇θ`(θt−1, xt,i) + Zt,a + Zt,b, where
Zt,a,Zt,b ∼ N ( 0, ζ2Id ) . It is clearly an unbiased estimator and the variance satisfies
Ext,1,...,xt,b,Zt,a,Zt,b ∣∣∣∣∣ ∣∣∣∣∣1b b∑ i=1 ∇θ`(θt−1, xt,i) + Zt,a + Zt,b − Ex∼D [∇`(θt−1, x)] ∣∣∣∣∣ ∣∣∣∣∣ 2
2  = Ext,1,...,xt,b ∥∥∥∥∥1b b∑ i=1 ∇`(θt−1, xt,i)− Ex∼D [∇`(θt−1, x)] ∥∥∥∥∥ 2
2 + E [‖Zt,a|22]+ E [‖Zt,b‖22] = 1
b Ext∼D
[ ‖∇`(θt−1, xt)− Ex [∇`(θt−1, x)]‖22 ] + E [ ‖Zt,a‖22 ] + E [ ‖Zt,b‖22 ] = O ( L2
b + dL2 log(1/δ) b2ε2
) .
The first step follows from the fact that the noise Zt,a,Zt,b is independent of the data xt,1, · · · , xt,b, and the second step follows from the independence of xt,1, · · · , xt,b. The last step follows from Zt,a,Zt,b ∼ N ( 0, ζ2Id ) and ζ2 ← 8L 2 log(2/δ) b2ε2 .

Review summaries:
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. 

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. 

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.   The 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.