arXiv CSopen access

Shuffling-Aware Optimization for Private Vector Mean Estimation

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

machine learning, deep learning, neural networks

Shuffling-Aware Optimization for Private Vector Mean Estimation Shun Takagi LY Corporation, Tokyo, Japan [email protected]

Seng Pei Liew LY Corporation, Tokyo, Japan [email protected]

arXiv:2604.28032v1 [cs.LG] 30 Apr 2026

May 1, 2026 Abstract We study d-dimensional unbiased mean estimation in the single-message shuffle model, where each user sends a single privatized message and the analyzer only observes the shuffled multiset of reports. While minimax-optimal mechanisms are well understood in the local differential privacy setting, the corresponding notion of optimality after shuffling has remained largely unexplored. To address this gap, we introduce the recently proposed shuffle index and use it to formulate the post-shuffling mechanism design problem as an explicit optimization problem. We then establish a minimax lower bound on the achievable mean squared error in terms of the shuffle index, which implies that mechanisms that are optimal under LDP can become suboptimal once shuffling is applied. Finally, we construct an asymptotically minimax optimal mechanism in the high privacy regime, which as a consequence achieves a privacy-utility trade-off nearly identical to that of the central Gaussian mechanism.

Introduction

Differential privacy (DP) [15, 16] enables principled privacy-preserving data analysis. In the central model, a trusted curator collects raw data and releases a privatized aggregate, achieving strong utility at the cost of a strong trust assumption. In the local model (LDP) [14], each user randomizes their data before communication, removing the need for trust but often degrading accuracy significantly. The shuffle model [5, 11, 17, 20] offers an appealing intermediate point: users send locally randomized messages through an anonymization layer (the shuffler), which permutes the reports before analysis. By breaking the linkage between users and messages, shuffling amplifies privacy and can approach central-model utility. We focus on the single-message randomize-then-shuffle setting [5], where each user sends exactly one privatized message. This is the simplest and most practical instantiation of the shuffle model, and it also serves as a basic component for understanding more complex multi-message constructions [2]. Despite its importance, optimal mechanism design for fundamental statistical tasks in the single-message shuffle model remains poorly understood. d d In this work we study d-dimensional Pn mean estimation over the unit ℓ2 ball B2 . Given inputs x1 , . . . , xn ∈ B2 , 1 the goal is to estimate the mean n i=1 xi from the shuffled multiset of privatized messages. While minimaxoptimal mechanisms are well understood under LDP [1], the analogous question after shuffling has remained largely unexplored: which local randomizer yields the best accuracy under a shuffled DP constraint? A key difficulty is that privacy after shuffling is inherently global and depends on n and on privacy amplification, making it hard to pose an explicit optimization problem in terms of the local randomizer alone. As a result, existing approaches often design mechanisms for LDP and then apply amplification, implicitly assuming that local optimality transfers to the shuffled setting. We address this gap using the recently proposed shuffle index [26], a scalar quantity determined solely by the structure of the local randomizer. In the high privacy regime, the privacy profile [4] of the shuffled mechanism is asymptotically governed by the shuffle index in a monotone way as n → ∞, which allows us to replace a global (ε, δ) constraint by a local constraint. This yields a clean post-shuffling mechanism design problem: minimize the worst-case mean squared error (MSE) among unbiased single-message protocols subject to a shuffle-index constraint.

Our main results show that this formulation leads to a sharp minimax theory. We prove a minimax lower bound showing that any unbiased protocol with shuffle index χ must incur worst-case MSE at least dχ2 . This bound implies that LDP-optimal mechanisms can be suboptimal after shuffling. In particular, we show that PrivUnit [7], which is minimax-optimal for mean estimation under LDP, fails to attain the shuffle-index lower bound by a constant factor in high dimensions. Finally, we construct an explicit mechanism that asymptotically matches the lower bound in the high privacy regime. Our blanket-mixed Gaussian local randomizer outputs a Gaussian with mean 0 with some probability and otherwise outputs a Gaussian centered at the user’s input, together with a universal unbiased estimator. We achieve MSE dχ2 (1 + o(1)) as χ → ∞, establishing asymptotic minimax p optimality. Moreover, we prove a central-limit-type correspondence: in the high privacy regime εn = O( log n/n), the privacy profile of our shuffled mechanism converges to that of the central Gaussian mechanism with the matching noise level, which sharpens earlier order-level and empirical observations in [10] by establishing a precise theoretical correspondence, matching constants.

1.1

Related Work and Contributions

Lower bounds. For single-message shuffled mean estimation, most existing lower bounds are typically stated in a form that is uniform over ε [2, 5] (i.e., Ω d n−2/(d+2) ), which is well suited to the moderate-privacy regime but provides limited resolution in the high privacy scaling εn = o(1) as n → ∞. In the high privacy regime, it is common to compare shuffled protocols against trivial lower bounds obtained by invoking minimax lower bounds for mean estimation of the central model [8]. However, such central-model lower bounds ignore the shuffling structure entirely and can therefore be loose. Moreover, central-model lower bounds are rarely suited to resolving fine-grained privacy–utility trade-offs (e.g., matching leading constants). Upper bounds. In the single-message shuffle model, order-optimal protocols are known in the moderateprivacy regime εn = Θ(1) (see, e.g., Asi et al. [2], Balle et al. [5]). In the high privacy scaling εn = o(1), there are also constructions achieving the corresponding order-optimal rates up to constant factors [10]. Moreover, the resulting MSE is suggestive of convergence up to constants to that of the central Gaussian mechanism as εn decreases. What has been missing, however, is a theory establishing whether and in what sense single-message shuffling can match the central Gaussian trade-off in the high privacy regime, and how the approach to the Gaussian limit depends quantitatively on the scaling of εn . Scott et al. [25] propose a single-message vector aggregation protocol, but their analysis incurs additional error terms stemming from coordinate/dimension sampling, which can make the resulting upper bounds loose in regimes where one aims for sharp constants. While one can alternatively formulate and optimize protocols under an explicit communication constraint, as explored, for instance, by Chen et al. [10], in this work we primarily focus on the privacy-utility trade-off and do not attempt to optimize communication. Multi-message shuffling. Multi-message shuffle protocols appear in (at least) two distinct forms. In the first, each user decomposes their contribution into multiple messages (multi-message per user), which are then shuffled jointly. These additional messages can strictly increase what is achievable: in the 1dimensional mean estimation, there are multi-message constructions whose accuracy can surpass that of the central Gaussian mechanism at comparable privacy levels [21]. For d > 1, however, no comparably efficient multi-message-per-user protocols are known that provably beat the central Gaussian mechanism. In the second form, one repeats a single-message shuffled primitive over multiple rounds and composes the privacy losses (multi-round shuffling). This is the dominant approach in d > 1, where mean estimation is invoked repeatedly and one can exploit composition to convert many high privacy rounds into an overall moderate-privacy guarantee [2, 10]. Such multi-round constructions are known to approach the privacy-utility trade-off of the central model [18, 22], which in turn highlights the importance of understanding the singleround high privacy single-message primitive sharply, since it governs the per-round error and the quality of the composed guarantee. Contributions.

• Using the shuffle index, we formulate post-shuffle mechanism design for unbiased single-message mean estimation as an explicit optimization problem, and prove a sharp minimax lower bound MSE ≥ dχ2 in the high privacy regime. • We show that LDP-minimax-optimal primitives (e.g., PrivUnit) can be strictly suboptimal after shuffling and construct a blanket-mixed Gaussian mechanism that is asymptotically minimax optimal, achieving MSE = dχ2 (1 + o(1)) as χ → ∞. • In the high privacy scaling, we establish a Gaussian-limit correspondence: the privacy-utility trade-off of our shuffled mechanism converges to that of the central Gaussian mechanism with matching noise level, and we validate the theoretical predictions via numerical experiments.

Preliminaries

2.1

Notations

We write R for the set of real numbers. For d ≥ 1, let Bd2 := {x ∈ Rd : ∥x∥2 ≤ 1} and Sd−1 := {u ∈ Rd : ∥u∥2 = 1} denote the unit ℓ2 ball and the unit sphere, respectively. Throughout the paper, the input space is denoted by X ; we typically take X = Bd2 . Var and E denote variance and expectation, respectively. We use standard asymptotic notations O(·), o(·), Ω(·), ω(·), and Θ(·).

2.2

Single-message Shuffling

We briefly review the single-message randomize-then-shuffle model [5]. Definition 2.1 (Local randomizer with a blanket distribution [5]). A local randomizer is a randomized mechanism R : X → Y. For each input x ∈ X , we write Rx for the law of the random output R(x). We denote by Rx (y) the corresponding probability density function. If there exists a scalar γ ∈ (0, 1], a probability density RBG on Y, and a family of probability densities {Qx }x∈X on Y such that, for every x ∈ X and almost every y ∈ Y, Rx (y) = γ RBG (y) + (1 − γ) Qx (y), RBG is called a blanket distribution of R [26], and the scalar γ is called the blanket mass. We assume access to an ideal shuffler as a black box. Definition 2.2 (Single-message shuffling and shuffled mechanism). Let R be a local randomizer. Given a dataset x1:n ∈ X n , each user i ∈ [n] applies the local randomizer to obtain a single message Yi := R(xi ) ∈ Y. The shuffler is a randomized map S : Y n → Y n which samples a permutation π uniformly at random from the symmetric group on [n] and outputs S(y1 , . . . , yn ) := (yπ(1) , . . . , yπ(n) ). The shuffled mechanism is defined as M = S ◦ Rn , where Rn denotes the application of R independently to each record. Unbiased estimators.

Let R be a local randomizer. A pair (R, A) is called unbiased if EY ∼Rx [A(Y )] = x

for all x ∈ X .

In the dataset setting, we say that a pair (Rn , A) is unbiased if n

E[A(S ◦ Rn (x1:n ))] =

2.3

1X xi n i=1

for all x1:n ∈ X n .

Differential Privacy (DP)

We recall the notion of DP and express it in a form based on the hockey-stick divergence.

Definition 2.3 (Hockey-stick divergence). Let Y be an output space. Let P and Q be probability distributions on Y that admit densities p and q, and fix a parameter α ≥ 1. The hockey-stick divergence of P from Q of order α is Z Dα (P ∥Q) := p(y) − α q(y) + dy, Y

where [u]+ := max{u, 0}. Definition 2.4 (DP [6, 16]). A mechanism is a randomized map M : X n → Z that takes a dataset x1:n ∈ X n as input and outputs a random element of Z. For each dataset x1:n we write M(x1:n ) for the corresponding output distribution on Z, and we denote its density by the same symbol when convenient. For a mechanism M, ε ≥ 0, and δ ∈ [0, 1], M is (ε, δ)-DP if and only if δM (ε) := sup Deε M(x1:n ) M(x′1:n ) ≤ δ, x1:n ≃x′1:n

where x1:n ≃ x′1:n indicates that the datasets x1:n and x′1:n are neighboring. The function δM (ε) is referred to as the privacy profile of M [4]. We adopt zero-out neighboring [23] as the adjacency relation. To this end, introduce a special symbol ⊥∈ / X and consider the extended domain X⊥ := X ∪ {⊥}. For a, b ∈ X⊥ , we write a ≃ b if (a =⊥ and b ∈ X )

(b =⊥ and a ∈ X ).

Two datasets x1:n , x′1:n ∈ X⊥n are zero-out neighboring, denoted by x1:n ≃ x′1:n , if there exists i ∈ [n] such that xj = x′j for all j ̸= i and xi ≃ x′i . This is convenient for analysis in distributed settings where the dataset size is public. Moreover, the standard replace-one adjacency can be simulated by two zero-out neighboring steps. If a mechanism is (ε, δ)-DP under zero-out neighboring, then it is (2ε, 2δ)-DP under the replace-one adjacency. We may define the output distribution on input ⊥ arbitrarily, and we choose it to be the blanket distribution of the local randomizer to simplify the analysis: R⊥ := RBG .

2.4

Shuffle Index

Given local randomizer R, define the generalized privacy amplification random variable [5, 26] ℓε ( · ; x, x′ , Rref ) : Y → R by Rx (Y ) − eε Rx′ (Y ) ℓε (Y ; x, x′ , Rref ) := . Rref (Y ) Using ℓ0 (·; x, x′ , Rref ) and blanket mass γ, we introduce two quantities that summarize the privacy amplification due to shuffling. Definition 2.5 (Shuffle index [26]). Let γ ∈ (0, 1] be the blanket mass of R. The lower shuffle index is r 1 χlo (R) := 1/ sup VarY ∼RBG [ℓ0 (Y ; x1 , x′1 , RBG )]. ′ γ x1 ≃x1 ∈X⊥ The upper shuffle index is χup (R) := 1/

sup

x1 ≃x′1 ∈X⊥ x∈X

q VarY ∼Rx [ℓ0 (Y ; x1 , x′1 , Rx )].

We have the inequality χup (R) ≥ χlo (R). We consider a class R of local randomizers such that every R ∈ R satisfies Assumption 2.8 of Takagi and Liew [26] (see Section B for details). The class R is substantially broader than the class of pure LDP mechanisms. In particular, it includes non-LDP mechanisms such as Gaussian-type randomizers. Roughly speaking, Assumption B.1 imposes mild regularity on the output distributions (e.g., absolute continuity for each input x and the absence of extremely heavy tails), while still covering a wide range of practically relevant mechanisms. For local randomizers in R, the privacy profile of S ◦ Rn can be characterized (up to asymptotically negligible factors) solely in terms of the shuffle indices. 4

Lemma 2.6 (Privacy profile bounds [26]). Let R ∈ R, and set χlo := χlo (R) and χup := χup (R). Assume p p lo that as n → ∞, εn = ω( 1/n) and εn = O log n/n . Then, there exist sequences eup n , en → 0 as n → ∞ such that fn,εn (χup ) 1 + eup ≤ δS◦Rn (εn ) ≤ fn,εn (χlo ) 1 + elo n n , where fn,ε (χ) := √

χ2 ε2 n 1 exp − . 2 2π χ3 ε2 n3/2

Note that fn,εn (χ) is decreasing in χ. Although the characterization is asymptotic, it shows that χlo (R) controls the upper bound and χup (R) controls the lower bound. Because fn,ε (χ) decreases with χ, larger shuffle indices lead to smaller δ, and thus yielding stronger privacy guarantees after shuffling.

Shuffle-Index-Based Optimization for Mean Estimation

In this section, we analyze post-shuffling mechanism design for mean estimation through a formulation based on the shuffle index. We begin by stating our main result, which establishes a Gaussian-limit correspondence for the optimal privacy-utility trade-off in the high privacy regime. To this end, we reduce the shuffled DP constraint to the shuffle index constraints. Then, we analyze the resulting optimization problem. Finally, we show that, from this perspective, PrivUnit can be strictly suboptimal after shuffling when d > 1.

3.1

Main Result

We begin by specifying the high-privacy scaling regime in which our results apply. Definition 3.1 regime). Fix a constant σ > 0 and a sequence {εn }n≥1 such that εn = p (σ-high privacy √ O log n/n and εn = ω(1/ n) . Let fn,ε (σ) be defined as in Lemma 2.6. We say that a sequence {(εn , δn )}n≥1 is in the σ-high privacy regime if δn = fn,εn (σ) 1 + en

for some sequence en → 0.

To build intuition for this high-privacy regime, we first recall the central Gaussian mechanism for mean estimation. For σ > 0 and x1:n ∈ (Bd2 )n , define the central Gaussian mechanism GM(σ) by n

GM(σ)(x1:n ) :=

1X σ xi + √ Z, Z ∼ N (0, Id ). n i=1 n

(1)

The mean squared error of GM is h i d σ2 2 E ∥GM(σ)(x1:n ) − x̄∥2 = . (2) n Under the zero-out neighboring relation, the ℓ2 -sensitivity of the mean is 1/n. We write δGM(σ) (ε) for the privacy profile of the Gaussian mechanism [3]. By construction, GM(σ) satisfies (εn , δn )-DP in the σ-high privacy regime. p √ Proposition 3.2. Assume that εn = O log n/n and εn = ω(1/ n). Then, for each σ > 0, the sequence n o εn , δGM(σ) (εn ) lies in the σ-high privacy regime. n≥1

p √ log n/n and εn = ω(1/ n), the 2 dominant behavior of the privacy profile is governed by the exponential term exp − σ2 ε2n n : since ε2n n → ∞ but ε2n n = O(log n), δGM(σ) (εn ) decays between exp(−ω(1)) and n−Θ(1) (and becomes polynomially small precisely when ε2n n = Θ(log n)). If a mechanism Mn is DP with (εn , δn ) in the σ-high privacy regime, then its privacy profile at level εn is asymptotically no larger than that of the central Gaussian mechanism GM(σ); equivalently, Mn provides privacy that is (to leading order) at least as strong as GM(σ). The proof is given in Appendix A.1. In the scaling regime εn = O

Problem Formulation Here, we formulate the post-shuffling mechanism design problem directly under an (ε, δ)-DP constraint. Let R : Bd2 → Y be a local randomizer and let An : Y n → Rd be an analyzer. Given a dataset x1:n ∈ (Bd2 )n , each user produces a single message Yi = R(xi ), the shuffler outputs S(Y1:n ), and the analyzer returns An (S(Y1:n )). We measure performance by the worst-case squared ℓ2 loss Errn (R, An ) := 

1X sup E An (S(Rn (x1:n ))) − xi n i=1 n x1:n ∈(Bd 2)

 .

(3)

For n = 1 (i.e., Err1 ), S is the identity map, and R1 = R. Let δS◦Rn (ε) denote the privacy profile of the shuffled mechanism. We consider the minimax design problem: inf

inf

R∈R {An }n≥1

lim sup n · Errn (R, An ) s.t. n→∞

(R , An ) is unbiased for all sufficiently large n, δS◦Rn (εn ) ≤ δn

(4)

for all sufficiently large n,

This problem formalizes post-shuffling mechanism design: among all single-message shuffled protocols that are (εn , δn )-DP after shuffling and unbiased for mean estimation over Bd2 , find the one minimizing the worst-case MSE. Let Err⋆DP ({(εn , δn )}n≥1 ) denote the optimal value for the problem (4) (i.e., lim supn→∞ nErrn (R⋆ , A⋆n )). The Gaussian Limit Correspondence of Shuffling. We now state our main result: in the σ-high privacy regime, the optimal worst-case MSE in the single-message shuffle model matches that of GM(σ) asymptotically. Theorem 3.3 (Gaussian Limit Correspondence). Fix a constant σ > 0. In the σ-high privacy regime {(εn , δn )}n≥1 d σ 2 ≤ Err⋆DP ({(εn , δn )}n≥1 ) ≤ d σ 2 1 + η(σ) , where η(σ) ≥ 0 depends only on σ and satisfies η(σ) = O(σ −2/3 ) as σ → ∞. A proof is provided in Section A.7. In other words, in the σ-high privacy regime, the optimal single-message shuffle protocol achieves a privacy-utility trade-off that is asymptotically identical to GM(σ) up to vanishing relative error. Both the lower and upper bounds are proved via a shuffle-index-based analysis developed in Section 3.2.

3.2

Reduction to Shuffle-Index-Based Optimization

Here, our goal is to reduce the n-user design problem (4) to a single-user design problem with the shuffle indices, and then to solve the resulting problem via matching lower and upper bounds. Single-user shuffle-index constrained problems. under shuffle-index constraints. min

R∈R, x b

s.t.

We consider the following single-user design problems

Err1 (R, x b) EY ∼Rx x b(Y ) = x,

∀ x ∈ Bd2 ,

(5)

∀ x ∈ Bd2 ,

(6)

χlo (R) ≥ χ, and min

R∈R, x b

s.t.

Err1 (R, x b) EY ∼Rx x b(Y ) = x, χup (R) ≥ χ.

Let Err⋆lo (χ) and Err⋆up (χ) denote the optimal values of (5) and (6), respectively. 6

Relating the shuffled-DP design problem. We now relate the n-user design problem (4) to the singleuser problems with shuffle indices. The next lemma shows that, in the χ-high privacy regime, the optimal risk under an (εn , δn ) shuffled-DP constraint is sandwiched between the optimal single-user risks under the shuffle index constraint of χ. Lemma 3.4 (Reduction to shuffle-index constraints). Fix a constant χ > 0. Let {(εn , δn )}n≥1 be in the χ-high privacy regime. Then, given any η > 0 Err⋆up (χ) ≤ Err⋆DP ({(εn , δn )}n≥1 ) ≤ Err⋆lo (χ + η). We perform two reductions. First, by the unbiasedness constraint, the n-user design problem reduces to a single-user design problem [1]. Second, Lemma 2.6 converts the shuffled-DP constraint at {(εn , δn )}n≥1 in χ-high privacy regime into shuffle-index constraints with χ. The full proof is provided in Section A.2. Consequently, we can sandwich the n-user design problem (4) between single-user problems under shuffleindex constraints. Thus, analyzing the lower and upper bounds of these problems yields corresponding bounds for (4). Lower bound. The upper shuffle index χup controls a χ2 -type discrepancy of the worst-case neighboring output distributions Rx1 and Rx′1 . Intuitively, larger χup means that Rx1 and Rx′1 are harder to distinguish. Therefore, we can employ the Hammersley-Chapman-Robbins-type lower bound [24]: under unbiasedness, small distinguishability forces a universal variance lower bound. Formally, we have the following result. Theorem 3.5. Let R ∈ R be a local randomizer with χup (R) < ∞ and x b be any unbiased estimator. Then, Err1 (R, x b) ≥ d χup (R)2 . The proof is found in Appendix A.3. Upper bound.

Next, we show that the lower bound is asymptotically attainable under a χlo constraint.

Corollary 3.6. As χ → ∞, 3 Err⋆lo (χ) ≤ d χ2 1 + χ−2/3 + O(χ−4/3 ) . 2 Corollary 3.6 is proved constructively in Section 4, where we present an explicit local randomizer (the blanket-mixed Gaussian mechanism) together with a universal unbiased estimator achieving the stated risk.

3.3

Suboptimality of Existing Mechanisms in d > 1

PrivUnit [7, 14] is optimal in LDP [1], but once we apply shuffling, it no longer achieves the optimal performance when d > 1. Proposition 3.7. Consider the input domain X = Sd−1 ⊂ Rd for PrivUnit where d > 1. Let PrivUnit(p, θ) be the PrivUnit local randomizer, and let χlo := χlo (PrivUnit(p, θ)). For any choice of {θd }d≥2 , let x bd be an unbiased estimator for PrivUnit(p, θd ). Then, χlo → ∞, Err1 (PrivUnit(p, θd ), x bd ) = C(θd , d)dχ2lo 1 + O(χ−1 lo ) for some quantity C(θd , d) > 0 depending only on (θd , d). Moreover, the best achievable leading constant is bounded away from 1: π lim inf inf C(θ, d) ≥ . d→∞ θ∈[−1,1] 2 We defer the proof to Appendix A.4. Intuitively, PrivUnit is constrained to a two-level cap-vs-complement reweighting of the uniform measure on Sd−1 . Therefore, once the shuffle-index budget fixes the allowable reweighting magnitude, there is essentially no remaining freedom to maximize the input-direction mean shift that controls the risk, which leads to suboptimality. 7

Optimality in the case of d = 1. In one dimension, PrivUnit reduces to randomized response RR, which is the important primitive in shuffling (see, e.g., Asi et al. [2], Balle et al. [5]). RR asymptotically attains the lower bound. Proposition 3.8. Consider the input domain X = S0 ⊂ R for RR(p). Let RR(p) be the randomized response local randomizer, and let χlo be its lower shuffle index. Let x b1 be an unbiased estimator for RR(p). Then, χlo → ∞, −2 Err1 (RR(p), x b1 ) = χ2lo 1 + χ−1 lo + O(χlo ) . See Appendix A.5 for the proof. Remark 3.9 (Kashin-based reductions). Kashin-based reductions [9, 10, 19] provide a convenient way to turn d-dimensional mean estimation over Bd2 into a collection of scalar problems by mapping x to a coefficient vector z = z(x) ∈ RN in a fixed frame so that x = U z and ∥z∥∞ ≤ √KN ∥x∥2 . This allows one to plug in a mechanism that is (near-)optimal in the one-dimensional setting described above at the level of the induced scalar subproblem. However, the reduction itself typically incurs a nontrivial distortion constant K = Θ(1) (and generally K > 1) in worst case. Consequently, the overall protocol can suffer a constant-factor loss in worst-case MSE due solely to the ℓ2 → ℓ∞ coordinate transformation.

Blanket-Mixed Gaussian Mechanism

The shuffle-index formulation implies that existing mechanisms can be suboptimal after shuffling. Here, we construct an explicit local randomizer that matches the shuffle-index lower bound asymptotically.

4.1

Mechanism

Algorithm 1 defines our blanket-mixed Gaussian local randomizer. Given input x, it outputs a blanket sample Y ∼ N (0, σ02 Id ) with probability γ, and with probability 1 − γ it outputs an informative sample Y ∼ N (x, σ02 Id ). The role of γ is to explicitly embed a blanket into the mechanism; the mechanism is designed for amplification via shuffling. Unbiased estimator Given a single message Y ∈ Rd produced by Algorithm 1, we use the linear estimator x b(Y ) :=

1 Y. 1−γ

(7)

This choice is universal. Indeed, for any x ∈ X , Algorithm 1 outputs Y ∼ γ N (0, σ02 Id ) + (1 − γ) N (x, σ02 Id ), so E[Y ] = (1 − γ)x and hence 1 EY ∼Rx x b(Y ) = E[Y ] = x. 1−γ

4.2

Analysis and Parameter Optimization BMG

Let R be the Blanket-Mixed Gaussian Mechanism (BMG) in Algorithm 1 with parameters (γ, σ0 ). Then its lower shuffle index admits the exact expression χlo RBMG

γ 1 . · (1 − γ)2 e1/σ02 − 1

We can express σ0 in terms of γ and χlo . Therefore, for a fixed lower shuffle index budget χ > 0, substituting σ0 into the expression of the risk yields Err1 =

d γ + . γ 1−γ (1 − γ)2 log 1 + (1−γ)2 χ2

Therefore, we can easily optimize γ numerically to minimize Err1 under the constraint χlo (RBMG ) ≥ χ. This optimization yields the following result. 8

Algorithm 1 Blanket-Mixed Gaussian Mechanism 1: Input: w ∈ X⊥ , where X := {x ∈ Rd : ∥x∥2 ≤ 1} and X⊥ := X ∪ {⊥} 2: Parameters: dimension d ≥ 1, blanket mass γ ∈ (0, 1], Gaussian scale σ0 > 0 3: Output: a single message Y ∈ Rd 4: if w =⊥ then 5: Sample Y ∼ N (0, σ02 Id ) 6: return Y 7: end if 8: Sample B ∼ Bernoulli(γ) 9: if B = 1 then 10: Sample Y ∼ N (0, σ02 Id ) 11: else 12: Sample Y ∼ N (w, σ02 Id ) 13: end if 14: return Y

Theorem 4.1. Fix d ≥ 1. There exists a choice of parameters (γ, σ0 ) such that χlo (RBMG ) ≥ χ and, as χ → ∞, 3 −2/3 BMG 2 −4/3 Err1 (R ,x b) = d χ 1 + χ +O χ . 2 The detailed derivation of χlo and Err1 and the proof are deferred to Appendix A.6.

4.3

The Gaussian local randomizer (γ = 0 case)

When χup > χlo , this upper bound can be loose, and in fact χup > χlo holds for most local randomizers, including BMG. While the relative gap can vanish in the high-privacy regime (i.e., χup /χlo → 1 as χlo → ∞), the indices typically remain distinct for finite parameters, so a nonzero absolute gap may persist. A particularly interesting special case is the Gaussian local randomizer obtained by setting γ = 0 in BMG. Proposition 4.2. Consider the Gaussian local q randomizer RGL = N (x, σ02 Id ), x ∈ Bd2 , together with the x GL unbiased estimator x b(Y ) = Y . Let χchua := 1/ VarY ∼RGL ℓ Y ; e, 0, R where e ∈ Sd−1 . Then, as 0 −e −e σ0 → ∞ (equivalently χchua → ∞), 9 −4 Err1 (RGL , x b) = d χ2chua 1 + χ−2 + O(χ ) . chua 2 chua See Appendix A.8 for the proof. Proposition 4.2 shows that the Gaussian local randomizer has a particularly sharp utility with respect to χchua : the excess over the leading term decays at rate O(χ−2 chua ), −2/3 which is faster than BMG, whose excess term is O(χlo ). χchua is induced from the conjecture 3.2 of Chua et al. [12], which implicates that, for RGL , the privacy profile can be upper bounded in terms of χchua , namely as n → ∞, δS◦RGLn (εn ) ≤ fn,εn (χchua ) (1 + o(1)). This means that we can use χchua instead of χlo (RGL ) to upper bound the privacy guarantee. Unfortunately, the conjecture is currently open, so we cannot yet turn this observation into an unconditional privacy–utility guarantee. While our numerical search did not reveal counterexamples, this does not constitute evidence of the conjecture’s validity. Thus, proving or refuting this conjecture remains a significant and challenging open problem, and would directly sharpen the privacy-utility trade-off.

Figure 1: Utility comparison at Figure 2: Privacy profile (up- Figure 3: Scaling with n with fixed fixed (n, δ) = (104 , 10−5 ). per bound) comparison at fixed local randomizer with (γ, σ0 ) = (n, RMSE) = (103 , 3.16). (0.95, 4.6).

Numerical Evaluation

We provide a numerical illustration of the Gaussian correspondence behavior induced by shuffling (Theorem 3.3). We plot the theoretical privacy-utility trade-offs implied by our analysis, and compare the proposed shuffled BMG mechanism (BMG) and the case of γ = 0 against the central Gaussian mechanism (GM) with sensitivity 1/n. Setup and parameter tuning. We consider d-dimensional mean estimation, butpsince both GM and BMG have Errn error that scales as d, we report the per-coordinate error RMSE = Errn /d. The BMG parameters (γ, σ0 ) are chosen using the optimization described in Section 4.2. To evaluate the (ε, δ)-DP guarantee, we compute certified numerical upper bounds using the FFT-based accountant of Takagi and Liew [26] (see Appendix C for details). Utility curves at fixed (n, δ) (Figure 1). We first fix n = 104 , δ = 10−5 , and plot the resulting RMSE as a function of ε. Figure 1 shows that in the high privacy regime (i.e., small ε), the RMSE curve of BMG approaches that of GM. This numerically supports the prediction that shuffling yields a central-limit effect, leading to a privacy-utility trade-off that is nearly GM in the high privacy regime. Privacy profiles at fixed RMSE (Figure 2). Next, we fix n = 103 and the target accuracy level to RMSE = 3.16, and plot the upper bounds of privacy profile δ(ε) as a function of ε. As shown in Figure 2, the numerically evaluated privacy profile of the shuffled BMG closely matches that of GM in the practical range of ε. Scaling with the number of users (Figure 3). We next examine how the correspondence manifests as we vary the number of users n. We fix the local randomizer to a single instance of BMG same as that of Figure 2 (i.e., calibrated at n = 103 so that the shuffled protocol attains target accuracy RMSE = 3.16 at δ = 10−5 ). We then sweep n ∈ {102 , 103 , 104 }, and for each n compute the privacy level εn such that BMG is (εn , 10−5 )-DP. To compare against the GM, we calibrate the noise standard deviation so that it satisfies the same privacy constraint (εn , 10−5 ). The resulting curves show that the RMSE of BMG closely tracks that of GM. Notably, the agreement is already strong at n = 102 , indicating that the correspondence behavior induced by shuffling becomes practically relevant at small sample sizes.

Discussion

On the unbiasedness constraint. We impose unbiasedness throughout in order to pursue sharp constantlevel minimax optimality rather than merely order-optimal rates, in the same spirit as Asi et al. [1]. Under this restriction, we are able to (i) reduce post-shuffling mechanism design to an explicit single-user optimization problem governed by the shuffle index and (ii) prove a universal minimax lower bound that reveals that

existing mechanisms can become strictly suboptimal after shuffling. That said, unbiasedness is a substantive structural constraint, and it remains an open question whether allowing biased estimation can strictly improve the privacy-utility trade-off, potentially yielding protocols whose achievable trade-off is strictly better than the central Gaussian mechanism. On the high privacy regime and composition Gaussian DP (GDP) [13] offers a clean view of multi√ round composition for mean estimation with the central Gaussian mechanism. Consider running GM( T σ) independently for T rounds on the same dataset and releasing the average of the T outputs. Because GDP is closed under composition and the squared GDP parameter adds across rounds, this averaged T -round procedure has the same overall GDP guarantee as a single execution of GM(σ), and it also attains the same mean-squared error. Since single-message shuffling has a privacy profile approaching that of the central Gaussian mechanism in the high privacy regime, we expect a similar near-lossless composition behavior for multi-round shuffled protocols: repeating a high privacy single-message shuffled primitive should yield, in the moderate-privacy regime, a privacy-utility trade-off close to the central Gaussian baseline. A fully rigorous statement would require tighter composition tools, which we leave for future work.

Conclusion

In this work, we formulated and analyzed post-shuffling mechanism design as an explicit optimization problem via the shuffle index. In the χ-high privacy regime, we established a sharp minimax lower bound dχ2 on the worst-case MSE for unbiased protocols, implying that existing mechanisms can become strictly suboptimal after shuffling. We further constructed BMG that asymptotically achieves this lower bound, and proved a Gaussian-limit correspondence showing that its privacy profile converges to that of the central Gaussian mechanism under the matching noise level. This provides a principled explanation of previously observed Gaussian-like behavior under shuffling [10], sharpening earlier order-level and empirical comparisons by establishing a constant-accurate theoretical correspondence. Several directions remain open. An important next step is to improve the convergence rate (i.e., tighten the vanishing excess term) O(χ−2/3 ). It is also of interest to extend the shuffle-index-based formulation beyond mean estimation to other fundamental estimation and learning tasks. Finally, developing tighter composition analyses for multi-round shuffled protocols may extend the constant-level correspondence beyond the high privacy regime.

References [1] Hilal Asi, Vitaly Feldman, and Kunal Talwar. Optimal Algorithms for Mean Estimation under Local Differential Privacy. In Proceedings of the 39th International Conference on Machine Learning, pages 1046–1056. PMLR, June 2022. URL https://proceedings.mlr.press/v162/asi22b.html. [2] Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy Nguyen, Kunal Talwar, and Samson Zhou. Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages. In Proceedings of the 41st International Conference on Machine Learning, pages 1945–1970. PMLR, July 2024. URL https://proceedings.mlr.press/v235/asi24a.html. [3] Borja Balle and Yu-Xiang Wang. Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising. In Proceedings of the 35th International Conference on Machine Learning, pages 394–403. PMLR, July 2018. URL https://proceedings.mlr.press/v80/balle18a. html. [4] Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https://proceedings.neurips.cc/paper_files/paper/2018/ hash/3b5020bb891119b9f5130f1fea9bd773-Abstract.html.

[5] Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. The Privacy Blanket of the Shuffle Model. In Advances in Cryptology – CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part II, pages 638–667, Berlin, Heidelberg, August 2019. Springer-Verlag. ISBN 978-3-030-26950-0. doi: 10.1007/978-3-030-26951-7 22. URL https://doi.org/10.1007/978-3-030-26951-7_22. [6] Gilles Barthe and Federico Olmedo. Beyond Differential Privacy: Composition Theorems and Relational Logic for f-divergences between Probabilistic Programs. In David Hutchison, Takeo Kanade, Josef Kittler, Jon M. Kleinberg, Friedemann Mattern, John C. Mitchell, Moni Naor, Oscar Nierstrasz, C. Pandu Rangan, Bernhard Steffen, Madhu Sudan, Demetri Terzopoulos, Doug Tygar, Moshe Y. Vardi, Gerhard Weikum, Fedor V. Fomin, Rūsiņš Freivalds, Marta Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming, volume 7966, pages 49–60. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. ISBN 978-3-642-39211-5 978-3-642-39212-2. doi: 10.1007/978-3-642-39212-2 8. URL http://link.springer.com/10.1007/978-3-642-39212-2_8. [7] Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers. Protection Against Reconstruction and Its Applications in Private Federated Learning, June 2019. URL http: //arxiv.org/abs/1812.00984. [8] T. Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 49(5):2825–2850, October 2021. ISSN 0090-5364, 2168-8966. doi: 10.1214/21-AOS2058. URL https://projecteuclid.org/journals/annals-of-statistics/volume-49/issue-5/ The-cost-of-privacy--Optimal-rates-of-convergence-for/10.1214/21-AOS2058.full. [9] Wei-Ning Chen, Peter Kairouz, and Ayfer Ozgur. Breaking the Communication-Privacy-Accuracy Trilemma. In Advances in Neural Information Processing Systems, volume 33, pages 3312– 3324. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/paper/2020/hash/ 222afbe0d68c61de60374b96f1d86715-Abstract.html. [10] Wei-Ning Chen, Dan Song, Ayfer Ozgur, and Peter Kairouz. Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation. In Proceedings of the 37th International Conference on Neural Information Processing Systems. arXiv, April 2023. doi: 10.48550/arXiv.2304.01541. URL http://arxiv.org/abs/2304.01541. [11] Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. Distributed Differential Privacy via Shuffling. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, pages 375–403, Cham, 2019. Springer International Publishing. ISBN 978-3-030-17653-2. doi: 10.1007/978-3-030-17653-2 13. [12] Lynn Chua, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, and Chiyuan Zhang. How Private are DP-SGD Implementations? In Proceedings of the 41st International Conference on Machine Learning, pages 8904–8918. PMLR, July 2024. URL https://proceedings.mlr.press/ v235/chua24a.html. [13] Jinshuo Dong, Aaron Roth, and Weijie J. Su. Gaussian Differential Privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3–37, February 2022. ISSN 1369-7412, 14679868. doi: 10.1111/rssb.12454. URL https://academic.oup.com/jrsssb/article/84/1/3/7056089. [14] John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Local Privacy and Statistical Minimax Rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 429–438, October 2013. doi: 10.1109/FOCS.2013.53. URL https://ieeexplore.ieee.org/document/6686179. [15] Cynthia Dwork. Differential Privacy. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Programming, pages 1–12, Berlin, Heidelberg, 2006. Springer. ISBN 978-3-540-35908-1. doi: 10.1007/11787006 1.

[16] Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. Foundations and Trends® in Theoretical Computer Science, 9(3-4):211–407, 2013. ISSN 1551305X, 1551-3068. doi: 10.1561/0400000042. URL http://www.nowpublishers.com/articles/ foundations-and-trends-in-theoretical-computer-science/TCS-042. [17] Ú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 Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’19, pages 2468–2479, USA, January 2019. Society for Industrial and Applied Mathematics. [18] Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Shuang Song, Kunal Talwar, and Abhradeep Thakurta. Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation. arXiv:2001.03618 [cs], January 2020. URL http://arxiv.org/abs/2001.03618. [19] Vitaly Feldman, Cristóbal Guzmán, and Santosh Vempala. Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization. Mathematics of Operations Research, 46(3):912–945, August 2021. ISSN 0364-765X. doi: 10.1287/moor.2020.1111. URL https://pubsonline.informs. org/doi/abs/10.1287/moor.2020.1111. [20] Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 954–964. arXiv, February 2022. doi: 10.1109/ FOCS52979.2021.00096. URL https://ieeexplore.ieee.org/document/9719772. [21] Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, and Amer Sinha. Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message. In Proceedings of the 38th International Conference on Machine Learning, pages 3692–3701. PMLR, July 2021. URL https://proceedings.mlr.press/v139/ghazi21a.html. [22] Antonious Girgis, Deepesh Data, and Suhas Diggavi. Renyi Differential Privacy of The Subsampled Shuffle Model In Distributed Learning. In Advances in Neural Information Processing Systems, volume 34, pages 29181–29192. Curran Associates, Inc., 2021. URL https://proceedings.neurips.cc/paper/ 2021/hash/f44ec26e2ac3f1ab8c2472d4b1c2ea86-Abstract.html. [23] Peter Kairouz, Brendan Mcmahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and Private (Deep) Learning Without Sampling or Shuffling. In Proceedings of the 38th International Conference on Machine Learning, pages 5213–5225. PMLR, July 2021. URL https: //proceedings.mlr.press/v139/kairouz21b.html. [24] E.L. Lehmann and George Casella. Theory of Point Estimation. Springer Texts in Statistics. SpringerVerlag, New York, 1998. ISBN 978-0-387-98502-2. doi: 10.1007/b98854. URL http://link.springer. com/10.1007/b98854. [25] Mary Scott, Graham Cormode, and Carsten Maple. Aggregation and Transformation of VectorValued Messages in the Shuffle Model of Differential Privacy. IEEE Transactions on Information Forensics and Security, 17:612–627, 2022. ISSN 1556-6021. doi: 10.1109/TIFS.2022.3147643. URL https://ieeexplore.ieee.org/document/9696239/. [26] Shun Takagi and Seng Pei Liew. Analysis of Shuffling Beyond Pure Local Differential Privacy, January 2026. URL http://arxiv.org/abs/2601.19154.

Missing Proofs

A.1

Proposition 3.2

p √ Proposition 3.2. Assume that εn = O log n/n and εn = ω(1/ n). Then, for each σ > 0, the sequence n o εn , δGM(σ) (εn ) lies in the σ-high privacy regime. n≥1

Proof. We begin by relating the privacy profile of the central Gaussian mechanism to the asymptotic template fn,ε (·). Lemma A.1 Gaussian privacy profile matches fn,ε (·)). Fix any sequence {εn }n≥1 with εn = q (Asymptotic log n O and εn = ω √1n and σ > 0. Then, as n → ∞, n δGM(σ) (εn ) = fn,εn (σ) 1 + o(1) . Proof. For the Gaussian mechanism with ℓ2 -sensitivity ∆ and noise standard deviation σgm , the analytic privacy profile admits the closed form (see, e.g., Balle and Wang [3]) ∆ εσgm εσgm ∆ − eε Φ − , (8) − − δGM (ε) = Φ 2σgm ∆ 2σgm ∆ √ where Φ is the standard normal CDF. In our setting, σgm = σ/ n and ∆ = 1/n. Define √ a := εσ n,

b :=

1 √ . 2σ n

Substituting into (8) and using Φ̄(t) := 1 − Φ(t) gives δGM(σ) (ε) = Φ̄(a − b) − eε Φ̄(a + b). We now use the Mills ratio expansion: as t → ∞, 1 1 −5 − 3 + O(t ) , Φ̄(t) = ϕ(t) t t

2 1 ϕ(t) := √ e−t /2 . 2π

(9)

(10)

Apply (10) with t = a ± b. Since b2 , ϕ(a ± b) = ϕ(a) exp ∓ab − 2

ab = ε/2,

we obtain ε/2 −b2 /2

δGM(σ) (ε) = ϕ(a)e

# 1 1 1 1 −5 −5 − + O(a ) − − + O(a ) . a − b (a − b)3 a + b (a + b)3

Next, expand the bracketed term in b/a (with b = o(a), since a → ∞ and b → 0): 1 1 1 1 2b b − − − = + O . 3 3 2 a − b (a − b) a + b (a + b) a a4

(11)

(12)

Substituting (12) into (11) and using e−b /2 = 1 + o(1) yields 2b δGM(σ) (ε) = ϕ(a)eε/2 1 + o(1) . 2 a √ √ Finally, since ε → 0 we have eε/2 = 1 + o(1), and plugging in a = εσ n and 2b = 1/(σ n) gives 2 2 1 ε σ n 1 δGM(σ) (ε) = √ exp − · 3 2 3/2 1 + o(1) , 2 σ ε n 2π which is exactly fn,ε (σ) (1 + o(1)). Applying this with (ε, σ) = (εn , σ) completes the proof. 14

(13)

Let {εn }n≥1 satisfy εn = O

log n n

and εn = ω

√1 n

and fix any σ > 0. By Lemma A.1, as n → ∞ we

have δGM(σ) (εn ) = fn,εn (σ) 1 + o(1) . Define en := o(1) so that en → 0 and δGM(σ) (εn ) = fn,εn (σ) 1 + en . Therefore, by Definition σ), the sequence {(εn , δGM(σ) (εn ))}n≥1 lies in the σ-high privacy q 3.1 (with χ = log n regime if εn = O and εn = ω √1n . n

A.2

Theorem 3.4

Lemma 3.4 (Reduction to shuffle-index constraints). Fix a constant χ > 0. Let {(εn , δn )}n≥1 be in the χ-high privacy regime. Then, given any η > 0 Err⋆up (χ) ≤ Err⋆DP ({(εn , δn )}n≥1 ) ≤ Err⋆lo (χ + η). Proof. We first outline the structure of the argument. The key point is that, under the unbiased meanestimation constraint, the n-user shuffled design problem can be reduced to a single-user estimation problem in the same spirit as [1]. After performing this reduction, the remaining task is to relate the shuffled-DP constraint to shuffle-index constraints via Lemma 2.6. This yields two single-user optimization problems, one governed by χup (R) and the other by χlo (R), which lead respectively to the lower and upper bounds in the statement. Accordingly, we proceed in two steps. We begin with the reduction from the n-user optimization to single-user estimation, and then we prove the desired upper and lower bounds separately. A.2.1

Reduction to single-user estimation

We first reformulate the n-user design problem by replacing the shuffled-DP constraint with an explicit shuffle-index constraint on the local randomizer R, which leads to (14) (and analogously (15)). Err⋆,uni (χ) := inf lo

inf

R∈R {An }n≥1

s.t.

lim sup n · Errn (R, An ) n→∞

(Rn , An ) is unbiased for all sufficiently large n,

(14)

χlo (R) ≥ χ, Err⋆,uni up (χ) := inf

inf

R∈R {An }n≥1

s.t.

lim sup n · Errn (R, An ) n→∞

(Rn , An ) is unbiased for all sufficiently large n,

(15)

χup (R) ≥ χ. Let Err⋆lo (χ) and Err⋆up (χ) denote the optimal values of (5) and (6), respectively. ⋆,uni Errup (χ) denote the optimal values of (14) and (15), respectively.

Let Err⋆,uni (χ) and lo

We can reduce these n-user optimization problems to single-user estimation problems. Lemma A.2 (Reduction to single-user estimation). Fix χ > 0. Then Err⋆lo (χ) = Err⋆,uni (χ). lo Err⋆up (χ) = Err⋆,uni up (χ). The proof is given in Appendix A.2.4.

A.2.2

Upper bound

Fix any η > 0. Let (Rη , x bη ) be an (exact or ζ-approximate) minimizer for the single-user shuffle-index constrained problem (5) at level χ + η, i.e., η EY ∼Rηx x b (Y ) = x for all x ∈ Bd2 , χlo (Rη ) ≥ χ + η, Err1 (Rη , x bη ) ≤ Err⋆lo (χ + η) + ζ, where ζ > 0 is arbitrary. η Step 1: Privacy p feasibility under p (εn , δn ). Apply Lemma 2.6 (upper bound direction) to R . Since εn → 0, εn = ω( 1/n), and εn = O( log n/n), there exists a sequence elo (η) → 0 such that for all sufficiently n large n, δS◦(Rη )n (εn ) ≤ fn,εn χlo (Rη ) 1 + elo (16) n (η) .

Using χlo (Rη ) ≥ χ + η and that fn,ε (·) is decreasing, we obtain δS◦(Rη )n (εn ) ≤ fn,εn (χ + η) 1 + elo n (η) .

(17)

Next, compare fn,εn (χ + η) and fn,εn (χ): 3

(χ + η)2 − χ2 2 exp − εn n . (18) 2 p Since η > 0 is fixed and ε2n n → ∞ (because εn = ω( 1/n)), the right-hand side of (18) tends to 0. From the definition 3.1, we have δn = fn,εn (χ)(1 + en ) with en → 0. Therefore, combining (17) and (18), we conclude that for all sufficiently large n, fn,εn (χ + η) = fn,εn (χ)

χ χ+η

δS◦(Rη )n (εn ) ≤ δn .

(19)

Hence the shuffled mechanism induced by Rη is (εn , δn )-DP for all sufficiently large n. Step 2: Risk bound.

Define an n-user analyzer Aη : Y n → Rd by n

Aη (y1:n ) :=

1X η x b (yi ), n i=1

which is permutation-invariant and hence compatible with shuffling. Since (Rη , x bη ) is unbiased at the single-user level, ((Rη )n , Aη ) is unbiased for the mean. Moreover, by Lemma A.2, Errn (Rη , Aη ) =

1 Err1 (Rη , x bη ). n

Combining this with (19), we see that (Rη , Aη ) is feasible for (4) (for all sufficiently large n), and thus Err⋆DP ({(εn , δn )}n≥1 ) ≤ lim sup nErrn (Rη , Aη ) = Err1 (Rη , x bη ) ≤ Err⋆lo (χ + η) + ζ. n→∞

Finally, letting ζ ↓ 0 proves the claim. A.2.3

Lower bound

Assume throughout that (εn , δn ) is in the χ-high privacy regime (Definition 3.1). We prove the lower bound Err⋆up (χ) ≤ Err⋆DP ({(εn , δn )}n≥1 ).

Step 1: Any shuffled-DP feasible R must satisfy χup (R) ≥ χ. Fix any local randomizer R ∈ R and any analyzer A such that (Rn , A) is unbiased and the shuffled mechanism is (εn , δn )-DP, i.e., δS◦Rn (εn ) ≤ δn .

(20)

We claim that necessarily χup (R) ≥ χ for all sufficiently large n. p p Suppose for contradiction that χup (R) < χ. Since εn → 0, εn = ω( 1/n), and εn = O( log n/n) by the definition of the high privacy regime, we may apply Lemma 2.6 to obtain a sequence eup n → 0 such that, for all sufficiently large n, δS◦Rn (εn ) ≥ fn,εn χup (R) 1 + eup (21) n , where fn,ε (χ) is defined in Lemma 2.6. On the other hand, since (εn , δn ) is in the χ-high privacy regime, there exists a sequence en → 0 such that, for all sufficiently large n, δn = fn,εn (χ) (1 + en ). (22) Combining (20), (21), and (22) yields, for all sufficiently large n, fn,εn χup (R) 1 + eup ≤ fn,εn (χ) (1 + en ). n

(23)

Now consider the ratio 3

χ2 − χup (R)2 2 εn n . exp 2 p Since χup (R) < χ, we have χ2 − χup (R)2 > 0, and since εn = ω( 1/n) we have ε2n n → ∞. Therefore, fn,εn (χup (R)) = fn,εn (χ)

χ χup (R)

fn,εn (χup (R)) −→ ∞. fn,εn (χ) Moreover, (1 + eup n )/(1 + en ) → 1. Hence, for all sufficiently large n, fn,εn χup (R) 1 + eup > fn,εn (χ) (1 + en ), n which contradicts (23). This proves the claim: χup (R) ≥ χ

(24)

Step 2: Reduction to the χup -constrained minimax risk. By (24), every protocol feasible for (4) (i.e., unbiased and shuffled-DP at level (εn , δn )) is also feasible for the shuffled-index constrained problem defining Err⋆,uni up (χ) (namely, the same unbiasedness constraint together with χup (R) ≥ χ). Therefore the feasible set of (4) is contained in the feasible set of the χup -constrained problem, and consequently the optimal value satisfies Err⋆DP ({(εn , δn )}n≥1 ) ≥ Err⋆,uni (25) up (χ). ⋆ Finally, by Lemma A.2 we have Err⋆,uni up (χ) = Errup (χ). Substituting into (25) yields

Err⋆DP ({(εn , δn )}n≥1 ) ≥ Err⋆up (χ), as desired.

A.2.4

Lemma A.2

Lemma A.2 (Reduction to single-user estimation). Fix χ > 0. Then Err⋆lo (χ) = Err⋆,uni (χ). lo Err⋆up (χ) = Err⋆,uni up (χ). 17

Proof. The reduction is in the same spirit as the canonicalization results of Asi et al. [1] for unbiased local protocols. We first establish two auxiliary results: Lemma A.3 and Lemma A.4, and then use them to prove Lemma A.2. Lemma A.3 (Post-processing for shuffle indices). Let R ∈ R be a local randomizer that admits a blanket distribution RBG with blanket mass γ ∈ (0, 1], i.e., for every x ∈ X⊥ and a.e. y ∈ Y, Rx (y) = γ RBG (y) + (1 − γ) Qx (y) for some family of densities {Qx }x∈X⊥ . Let K : Y → Z be an arbitrary (possibly randomized) post-processing map, i.e., a Markov kernel from Y to Z. Define the post-processed randomizer R′ := K ◦ R : X⊥ → Z,

R′x := K ◦ Rx .

Then R′ admits a blanket distribution R′BG := K ◦ RBG with blanket mass at least γ, and moreover its shuffle indices satisfy χup (R′ ) ≥ χup (R), χlo (R′ ) ≥ χlo (R). Proof. We first show that R′ admits a blanket of mass γ. Applying K to the blanket decomposition of Rx yields R′x = K ◦ Rx = γ (K ◦ RBG ) + (1 − γ) (K ◦ Qx ). Thus, R′BG := K ◦ RBG is a valid blanket distribution of R′ with blanket mass γ (and hence the maximal blanket mass γ ′ of R′ satisfies γ ′ ≥ γ). We next prove the monotonicity of the lower shuffle index. Fix x ≃ x′ and consider the generalized privacy amplification random variable with reference RBG : ℓ0 (Y ; x, x′ , RBG ) :=

Rx (Y ) − Rx′ (Y ) , RBG (Y )

Y ∼ RBG .

Let Z ∼ R′BG be obtained by sampling Y ∼ RBG and then applying Z | Y ∼ K(· | Y ). Define analogously ℓ′0 (Z; x, x′ , R′BG ) :=

R′x (Z) − R′x′ (Z) . R′BG (Z)

Then, for RBG -a.e. y and R′BG -a.e. z, ℓ′0 (z; x, x′ , R′BG ) = E[ℓ0 (Y ; x, x′ , RBG ) | Z = z] . Indeed, writing K(z | y) for the kernel density, we have Z R′x (z) − R′x′ (z) = K(z | y) Rx (y) − Rx′ (y) dy,

R′BG (z) =

Z K(z | y)RBG (y) dy,

and the claim follows by Bayes’ rule. Therefore, by the law of total variance, Var(ℓ′0 (Z; x, x′ , R′BG )) = Var(E[ℓ0 (Y ; x, x′ , RBG ) | Z]) ≤ Var(ℓ0 (Y ; x, x′ , RBG )) . Combining this with γ ′ ≥ γ yields 1 1 Var(ℓ′0 (Z; x, x′ , R′BG )) ≤ Var(ℓ0 (Y ; x, x′ , RBG )) . γ′ γ Taking the supremum over x ≃ x′ and the square root gives χlo (R′ ) ≥ χlo (R). The proof for the upper shuffle index is analogous. For any fixed x ∈ X , let Y ∼ Rx and obtain Z by applying the same post-processing kernel K. Then, defining ℓ0,x (Y ; x1 , x′1 ) :=

Rx1 (Y ) − Rx′1 (Y ) , Rx (Y )

ℓ′0,x (Z; x1 , x′1 ) := 18

R′x1 (Z) − R′x′ (Z) 1

R′x (Z)

one similarly has ℓ′0,x (Z; x1 , x′1 ) = E[ℓ0,x (Y ; x1 , x′1 ) | Z] , and hence Var ℓ′0,x (Z; x1 , x′1 ) ≤ Var(ℓ0,x (Y ; x1 , x′1 )) . Taking the supremum over x1 ≃ x′1 and x ∈ X , and then the square root, concludes that χup (R′ ) ≥ χup (R). Lemma A.4 (Additivization via a Markov kernel). Fix n ≥ 2. Let R be any local randomizer and let A be any unbiased estimator in the single-message shuffle model. Then there exists a Markov kernel K : Y → Rd Pn 1 + such that, letting A (z1:n ) := n i=1 zi , the estimator A+ is unbiased with respect to the local randomizer K ◦ R : X → Rd , and moreover, Errn (K ◦ R, A+ ) ≤ Errn (R, A). Proof. Define the composed analyzer Ae := A ◦ S. Since shuffling is a post-processing operation, the singlee with message shuffled protocol (R, A) can be equivalently viewed as the (non-shuffled) local protocol (R, A) n the same output distribution. In particular, unbiasedness is preserved: for all datasets x1:n ∈ X , n h i X e n (x1:n )) = E[A(S(Rn (x1:n )))] = 1 E A(R xi . n i=1 Therefore, we may invoke a canonicalization (additivization) argument in the spirit of Proposition 3.3 of Asi e there exists a Markov kernel K : Y → Rd such that, A, et al. [1]. Concretely, for any unbiased Panalyzer n 1 ′ + letting R := K ◦ R and A (z1:n ) := n i=1 zi , the estimator A+ is unbiased with respect to R′ and satisfies e Errn (R′ , A+ ) ≤ Errn (R, A). Unlike [1], we do not require R to satisfy ε-LDP; the canonicalization construction we use relies only on unbiasedness. The only closure property needed under post-processing concerns the shuffle-index constraints, which is guaranteed by Lemma A.3. Proof of Lemma A.2 We prove the claim for the χlo -constrained problem; the proof for χup is identical by using the corresponding monotonicity in Lemma A.3. Recall that Err⋆n,lo (χ) is the optimal value of (14) and Err⋆lo (χ) is the optimal value of (5). Step 1: ≤ direction. Let (R, x b) be any feasible solution to the single-user problem (5), i.e., EY ∼Rx [b x(Y )] = x for all x ∈ Bd2 and χlo (R) ≥ χ. Define an n-user protocol by applying R independently to each user and using the additive estimator n 1X A(y1:n ) := x b(yi ), y1:n ∈ Y n , n i=1 (which is permutation-invariant and hence unaffected by shuffling). Then the resulting estimator is unbiased: E[A(S(Rn (x1:n )))] =

n n 1X 1X E[b x(Yi )] = xi . n i=1 n i=1

Moreover, writing Yi ∼ Rxi independently and setting ∆i := x b(Yi ) − xi , we have E[∆i ] = 0 and hence E A(Y1:n ) −

n n n 2 2 1X 1X 1 X xi = E ∆i = 2 E∥∆i ∥22 , n i=1 n i=1 n i=1 2 2

where the cross terms vanish by independence and mean-zero. Taking the supremum over x1:n ∈ (Bd2 )n yields 1 1 Errn (R, A) = sup EY ∼Rx ∥b x(Y ) − x∥22 = Err1 (R, x b). n x∈Bd2 n Since (R, A) is feasible for (14), we obtain Err⋆n,lo (χ) ≤ Err⋆lo (χ). 19

Step 2: ≥ direction. Let (R, A) be any feasible n-user solution to (14), i.e., A is unbiased for S ◦ Rn and e χlo (R) ≥ χ. Define the non-shuffled analyzer Ae := A ◦ S. Since shuffling is post-processing, the pair (R, A) induces the same output distribution and remains unbiased: n h i X e n (x1:n )) = E[A(S(Rn (x1:n )))] = 1 xi . E A(R n i=1

e Applying Lemma a Markov kernel K : Y → Rd such that, letting R′ := K ◦ R and PnA.4 to (R, A), we obtain 1 + + A (z1:n ) := n i=1 zi , the estimator A is unbiased with respect to R′ and Errn (R′ , A+ ) ≤ Errn (R, A).

(26)

By Lemma A.3, χlo (R′ ) = χlo (K ◦ R) ≥ χlo (R) ≥ χ, so (R′ , A+ ) is feasible for (14). Now let Zi ∼ R′xi be independent and define Ξi := Zi − xi . Unbiasedness implies E[Ξi ] = 0, and thus E A+ (Z1:n ) −

n n n 2 2 1X 1X 1 X xi = E Ξi = 2 E∥Ξi ∥22 , n i=1 n i=1 n i=1 2 2

and hence Errn (R′ , A+ ) =

1 1 sup EZ∼R′x ∥Z − x∥22 = Err1 (R′ , id), n x∈Bd2 n

where id : Rd → Rd denotes the identity estimator. Since id is an admissible unbiased estimator for R′ , the single-user optimum satisfies Err⋆lo (χ) ≤ Err1 (R′ , id). Combining the last two displays with (26) gives Errn (R, A) ≥ Errn (R′ , A+ ) =

1 1 Err1 (R′ , id) ≥ Err⋆lo (χ). n n

Taking the infimum over all feasible (R, A) for (14) yields Err⋆n,lo (χ) ≥ Err⋆lo (χ). Conclusion.

Combining the ≤ and ≥ directions proves Err⋆n,lo (χ) = Err⋆lo (χ).

The statement for Err⋆n,up (χ) follows by the same argument, replacing χlo by χup throughout.

A.3

Theorem 3.5

Theorem 3.5. Let R ∈ R be a local randomizer with χup (R) < ∞ and x b be any unbiased estimator. Then, Err1 (R, x b) ≥ d χup (R)2 . Proof. Let R : X⊥ → Y be a local randomizer, and let x b : Y → Rd be an unbiased estimator in the sense that EY ∼Rx x b(Y ) = x for all x ∈ X⊥ , where we interpret ⊥ as contributing 0 to the mean and thus require EY ∼R⊥ [b x(Y )] = 0.

Fix an arbitrary reference point x ∈ X . By mutual absolute continuity due to R ∈ R, for every x′ ∈ X⊥ the Radon–Nikodym derivative dRx′ wx′ ;x (y) := (y) dRx is well-defined Rx -a.s. For x1 , x′1 ∈ X⊥ , define ℓx1 ,x′1 ;x (y) := wx1 ;x (y) − wx′1 ;x (y). Then EY ∼Rx [ℓx1 ,x′1 ;x (Y )] = 0. Moreover, by a change of measure and unbiasedness, for any x′ ∈ X⊥ , EY ∼Rx′ [b x(Y )] = EY ∼Rx x b(Y ) wx′ ;x (Y ) = x′ . Subtracting the identities for x′ equal to x1 and x′1 yields EY ∼Rx x b(Y ) ℓx1 ,x′1 ;x (Y ) = x1 − x′1 .

(27)

Let φ ∈ (Rd )∗ be any linear functional. Applying φ to (27) gives h i EY ∼Rx φ(b x(Y )) ℓx1 ,x′1 ;x (Y ) = φ(x1 − x′1 ). Since ERx [ℓx1 ,x′1 ;x (Y )] = 0, we may center φ(b x(Y )) to obtain h i EY ∼Rx φ(b x(Y )) − ERx [φ(b x(Y ))] ℓx1 ,x′1 ;x (Y ) = φ(x1 − x′1 ). By Cauchy–Schwarz, 1/2 1/2 φ(x1 − x′1 ) ≤ VarY ∼Rx φ(b x(Y )) VarY ∼Rx ℓx1 ,x′1 ;x (Y ) , and hence VarY ∼Rx φ(b x(Y )) ≥

2 φ(x1 − x′1 ) . VarY ∼Rx ℓx1 ,x′1 ;x (Y )

(28)

We now identify ℓx1 ,x′1 ;x with the generalized privacy amplification random variable at ε = 0: ℓx1 ,x′1 ;x (y) =

Rx1 (y) − Rx′1 (y) = ℓ0 (y; x1 , x′1 , Rx ) . Rx (y)

Thus, by the definition of the upper shuffle index, sup

sup VarY ∼Rx [ℓ0 (Y ; x1 , x′1 , Rx )] ≤

x1 ≃x′1 ∈X⊥ x∈X

1 , χup (R)2

or equivalently, for every x ∈ X and every neighboring pair x1 ≃ x′1 , VarY ∼Rx [ℓ0 (Y ; x1 , x′1 , Rx )] ≤

1 . χup (R)2

(29)

Next, fix j ∈ [d] and take φ(v) = vj in (28). Choose a zero-out neighboring pair (x1 , x′1 ) = (ej , ⊥), where ej is the j-th standard basis vector (note that ej ∈ Bd2 and ej ≃⊥). Then φ(x1 − x′1 ) = 1, and combining (28) with (29) yields VarY ∼Rx x bj (Y ) ≥ χup (R)2 for all x ∈ X . (30) Finally, since x b is unbiased, for any x ∈ X we have d d X X EY ∼Rx ∥b x(Y ) − x∥22 = EY ∼Rx (b xj (Y ) − xj )2 = VarY ∼Rx x bj (Y ) , j=1

j=1

and therefore by (30), d X EY ∼Rx ∥b x(Y ) − x∥22 ≥ χup (R)2 = d χup (R)2 . j=1

Taking the supremum over x ∈ Bd2 ⊆ X gives Err1 (R, x b) = sup EY ∼Rx ∥b x(Y ) − x∥22 ≥ d χup (R)2 , x∈Bd 2

which proves the claim.

A.4

Proposition 3.7

Proposition 3.7. Consider the input domain X = Sd−1 ⊂ Rd for PrivUnit where d > 1. Let PrivUnit(p, θ) be the PrivUnit local randomizer, and let χlo := χlo (PrivUnit(p, θ)). For any choice of {θd }d≥2 , let x bd be an unbiased estimator for PrivUnit(p, θd ). Then, χlo → ∞, Err1 (PrivUnit(p, θd ), x bd ) = C(θd , d)dχ2lo 1 + O(χ−1 lo ) for some quantity C(θd , d) > 0 depending only on (θd , d). Moreover, the best achievable leading constant is bounded away from 1: π lim inf inf C(θ, d) ≥ . d→∞ θ∈[−1,1] 2 Proof. Definition A.5 (PrivUnit local randomizer [7, 14]). Fix d ≥ 2 and let the input domain be X = Sd−1 ⊂ Rd . Fix parameters p ∈ [0, 1] and θ ∈ [−1, 1]. For an input v ∈ Sd−1 define the spherical cap Cθ (v) := {u ∈ Sd−1 : ⟨u, v⟩ ≥ θ}. Let U ∼ Unif(Sd−1 ) and define q(θ, d) := Pr ⟨U, v⟩ < θ ,

1 − q(θ, d) = Pr U ∈ Cθ (v) ,

which depends only on (θ, d) by rotational symmetry. The PrivUnit local randomizer PrivUnit(p, θ) is the map R : Sd−1 → Sd−1 defined by: given input v ∈ Sd−1 , output a random Y ∈ Sd−1 such that ( Unif Cθ (v) , with probability p, Y ∼ Unif Cθ (v)c , with probability 1 − p, where Unif(A) denotes the uniform distribution on a measurable set A ⊆ Sd−1 with respect to the uniform probability measure on Sd−1 . Fix d ≥ 2 and a threshold θ ∈ [−1, 1]. Let v ∈ Sd−1 be an arbitrary input and let U ∼ Unif(Sd−1 ). Write T := ⟨U, v⟩,

q := Pr(T < θ),

1 − q = Pr(T ≥ θ).

E[U | T < θ] = β v.

Since E[T ] = 0, we have (1 − q)α + qβ = 0, hence β=−

1−q α. q

(31)

Step 1: PrivUnit and its mean. Fix p ∈ [0, 1]. PrivUnit(p, θ) outputs Y distributed as U | (T ≥ θ) with probability p and as U | (T < θ) with probability 1 − p. Therefore, 1−q E[Y ] = p αv + (1 − p) βv = pα − (1 − p) α v = m v, q where, defining ∆ := p + q − 1, m=α

∆ . q

(32)

Step 2: Reduction to linear unbiased estimators. Let x b : Sd−1 → Rd be any (possibly randomized) d−1 estimator such that E[b x(Y ) | v] = v for all v ∈ S . We show that, without loss of generality, we may restrict attention to estimators of the form x b(y) = a y for a scalar a. (i) Orthogonal equivariance of PrivUnit. For any orthogonal matrix U ∈ O(d), PrivUnit(p, θ) satisfies the equivariance relation d RU v = U Rv , i.e., if Y ∼ Rv then U Y ∼ RU v . (This holds because the spherical cap condition ⟨u, v⟩ ≥ θ is preserved under orthogonal transformations.) (ii) Symmetrization of the estimator. Let U ∼ Haar(O(d)) be independent of everything else, and define the symmetrized estimator x e(y) := EU U ⊤ x b(U y) . This definition depends only on the observation y and does not depend on the unknown input v. Unbiasedness is preserved. For any v ∈ Sd−1 and Y ∼ Rv , let Y ′ ∼ RU v . By (i), we may couple so that Y ′ = U Y . Then E[e x(Y ) | v] = EU U ⊤ E x b(U Y ) | v, U = EU U ⊤ E x b(Y ′ ) | U v = EU [U ⊤ (U v)] = v, so x e is unbiased whenever x b is unbiased. Risk does not increase. By Jensen’s inequality and orthogonality of U , for any v ∈ Sd−1 , h 2 i E ∥e x(Y ) − v∥22 | v = E EU U ⊤ x b(U Y ) − v 2 v ≤ EU E ∥U ⊤ x b(U Y ) − v∥22 | v, U = EU E ∥b x(U Y ) − U v∥22 | v, U . Using U Y ∼ RU v from (i) and the fact that the map w 7→ E[∥b x(Y ) − w∥22 | w] is constant over w ∈ Sd−1 by the same symmetry, we conclude that sup E ∥e x(Y ) − v∥22 | v ≤ sup E ∥b x(Y ) − v∥22 | v . v∈Sd−1

v∈Sd−1

Hence, for minimax risk, it is without loss of generality to assume that the estimator is orthogonally equivariant, i.e., x e(U y) = U x e(y) ∀ U ∈ O(d), ∀ y ∈ Sd−1 . (iii) Form of an orthogonally equivariant map on the sphere. Let e1 be the first basis vector and let H := {U ∈ O(d) : U e1 = e1 } be its stabilizer subgroup. Equivariance implies x e(e1 ) = x e(U e1 ) = U x e(e1 ) for all U ∈ H. The only vectors fixed by all U ∈ H are multiples of e1 , so x e(e1 ) = ae1 for some scalar a. For a general y ∈ Sd−1 , pick V ∈ O(d) with V e1 = y; then x e(y) = x e(V e1 ) = V x e(e1 ) = a V e1 = a y. Therefore, without loss of generality, we may assume x b(y) = a y. Finally, imposing unbiasedness gives a E[Y | v] = v, and since E[Y | v] = mv (from Step 1), we obtain a = 1/m. Hence it suffices to analyze the estimator x b(Y ) = Y /m. 23

Step 3: Exact ℓ2 risk under the optimal unbiased estimator. Since ∥Y ∥2 = 1 almost surely and ∥v∥2 = 1, we compute Err1 (PrivUnit(p, θ), x b) = E ∥Y /m − v∥22 1 2 = 2 E∥Y ∥22 − ⟨E[Y ], v⟩ + ∥v∥22 m m 1 1 = 2 − 2 + 1 = 2 − 1. m m In the high privacy regime, we have m → 0, hence 1 1 + o(1) . 2 m

(33)

q2 1 + o(1) . α 2 ∆2

(34)

Err1 (PrivUnit(p, θ), x b) = Combining (32) and (33) yields Err1 (PrivUnit(p, θ), x b) =

Step 4: Relating ∆ to the lower shuffle index χlo . Let µ denote the uniform probability measure on Sd−1 . With respect to µ, the output density of PrivUnit(p, θ) at input v takes two values:  p  , u ∈ Cθ (v), h := 1−q fv (u) = 1−p  ℓ := , u ∈ Cθ (v)c . q Recall we adopt zero-out adjacency and set R⊥ := RBG := µ. Then for neighboring inputs (v, ⊥) we have ℓ0 (u; v, ⊥, RBG ) = fv (u) − 1. A direct calculation using Eµ [fv (U )] = 1 shows VarU ∼µ [fv (U ) − 1] = (1 − q)

p − (1 − q) 2 1−q

(1 − p) − q 2 q

∆2 . q(1 − q)

Let γ be the blanket mass of PrivUnit with blanket distribution µ. By definition of χlo , γ q(1 − q) 1 = , ∆2 Var [f (U ) − 1] U ∼µ v γ

χ2lo = 1

equivalently

∆2 =

γ q(1 − q) . χ2lo

(35)

Substituting (35) into (34) gives Err1 (PrivUnit(p, θ), x b) =

1 q · χ2 1 + O(χ−1 lo ) . 1 − q γ α2 lo

(36)

Step 5: High privacy scaling and the leading constant. The high privacy regime for PrivUnit corresponds to ∆ → 0, i.e., p → 1 − q, which makes the output distribution approach µ. In this regime h → 1 and ℓ → 1, hence the maximal blanket mass satisfies γ → 1. Therefore the leading constant in (36) is C(θ, d) :=

1 q · , 1 − q d α2

so that

Err1 (PrivUnit(p, θ), x b) = C(θ, d) d χ2lo 1 + o(1) .

This proves the first displayed claim of the proposition. Step 6: Asymptotic lower bound on the best constant over θ as d → ∞. To optimize over θ in √ high dimension, consider a sequence θ = θ with τ := θ d = O(1). By the classical normal approximation d d √ for spherical marginals, Z := d T converges in distribution to N (0, 1), which implies q = Pr(T < θd ) → Φ(τ ),

1 − q → Q(τ ) := 1 − Φ(τ ),

and

1 1 α = E[T | T ≥ θd ] = √ E[Z | Z ≥ τ ] (1 + o(1)) = √ λ(τ ) (1 + o(1)), d d

where λ(τ ) := ϕ(τ )/Q(τ ) and ϕ, Φ are the standard normal pdf and cdf. Plugging these into C(θ, d) yields C(θd , d) =

Φ(τ ) Q(τ ) Φ(τ ) 1 (1 + o(1)) = (1 + o(1)) =: C(τ ) (1 + o(1)). · Q(τ ) λ(τ )2 ϕ(τ )2

It remains to minimize C(τ ) = Φ(τ )Q(τ )/ϕ(τ )2 over τ ∈ R. The function C is even since Φ(−τ ) = Q(τ ) and ϕ(−τ ) = ϕ(τ ). Moreover, π (1/2)(1/2) √ = . C(0) = 2 2 (1/ 2π) A direct differentiation of log C(τ ) shows that τ = 0 is the unique global minimizer: ϕ(τ ) ϕ(τ ) d log C(τ ) = − + 2τ, dτ Φ(τ ) Q(τ ) which is strictly positive for τ > 0 and strictly negative for τ < 0. Consequently, inf C(τ ) = C(0) =

τ ∈R

π . 2

Therefore, lim inf d→∞

inf

C(θ, d) ≥ inf C(τ ) = τ ∈R

θ∈[−1,1]

π , 2

which completes the proof.

A.5

Proposition 3.8

Proposition 3.8. Consider the input domain X = S0 ⊂ R for RR(p). Let RR(p) be the randomized response local randomizer, and let χlo be its lower shuffle index. Let x b1 be an unbiased estimator for RR(p). Then, χlo → ∞, −2 Err1 (RR(p), x b1 ) = χ2lo 1 + χ−1 lo + O(χlo ) . Proof. Let d = 1 and X = S0 = {−1, +1}. For any θ ∈ (−1, 1), the spherical cap {u ∈ S0 : ⟨u, x⟩ ≥ θ} degenerates: since S0 = {±1} and ⟨u, x⟩ ∈ {±1}, we have ⟨u, x⟩ ≥ θ ⇐⇒ ⟨u, x⟩ = +1 ⇐⇒ u = x. Hence, for any such θ, PrivUnit(p, θ) is equivalent to the sign-flip (randomized response) mechanism ( x with prob. p, Y = x ∈ {±1}. −x with prob. 1 − p, In particular, we may fix θ = 0 without loss of generality and write RR(p) for this mechanism. Unbiased estimation and Err1 . Let t := 2p−1 ∈ (0, 1) (we assume p ≥ 1/2; this is the relevant high privacy direction). Then E[Y | x] = tx. The estimator x b1 (Y ) := Y /t is unbiased since E[b x1 (Y ) | x] = E[Y | x]/t = x. Moreover, since Y 2 = 1 a.s., " # 2 Y 1 1 1 2 Err1 (RR(p), x b1 ) = sup E −x x = sup 2 E[Y | x] − 2 E[xY | x] + 1 = 2 − 1. t t t t x x∈{±1}

Computing χlo . Let Rx denote the law of Y given input x ∈ {±1}. Under the zero-out convention we take R⊥ = RBG . The maximal blanket mass is X γ= inf Rx (y). y∈{±1}

x∈{±1}

When p ≥ 1/2, we have inf x Rx (+1) = 1 − p and inf x Rx (−1) = 1 − p, hence γ = 2(1 − p) = 1 − t,

RBG (+1) = RBG (−1) = 12 .

and

For neighboring inputs (x, ⊥), the generalized amplification variable at ε = 0 is ℓ0 (y; x, ⊥, RBG ) =

Rx (y) − RBG (y) . RBG (y)

Taking x = +1 (the case x = −1 is identical), we have R+1 (+1) = p = (1 + t)/2 and R+1 (−1) = 1 − p = (1 − t)/2, so ℓ0 (+1) = t, ℓ0 (−1) = −t. Therefore, for Y ∼ RBG , Var[ℓ0 (Y )] = t2 , and by the definition of χlo , 1

χ2lo = 1

γ VarY ∼RBG [ℓ0 (Y )]

γ 1−t = 2 . 2 t t

Equivalently, t solves the quadratic equation χ2lo t2 + t − 1 = 0, so (taking the positive root) t=

Expansion for χlo → ∞.

Using

−1 +

1 + 4χ2lo . 2χ2lo

(37)

q p 1 + 4χ2lo = 2χlo 1 + 4χ12 = 2χlo 1 + 8χ12 + O(χ−4 lo ) , (37) yields lo

1 1 − 2 + O(χ−3 lo ). χlo 2χlo

Hence, 1 1 −2 2 = χlo 1 + + O(χlo ) , t2 χlo and therefore Err1 (RR(p), x b1 ) =

1 t2

−2 − 1 = χ2lo 1 + χ−1 lo + O(χlo ) ,

(χlo → ∞),

2 where the subtraction of 1 is absorbed into the O(χ−2 lo ) term after factoring out χlo . This proves the claimed expansion.

A.6

Theorem 4.1

Theorem 4.1. Fix d ≥ 1. There exists a choice of parameters (γ, σ0 ) such that χlo (RBMG ) ≥ χ and, as χ → ∞, 3 −2/3 BMG 2 −4/3 Err1 (R ,x b) = d χ 1 + χ +O χ . 2 Proof. Throughout, write A := 1 − γ ∈ (0, 1] and recall that the blanket distribution is RBG = N (0, σ02 Id ). 26

Step 1: Exact formula for χlo (R). Fix x ∈ X and let ϕσ0 (y) denote the density of N (0, σ02 Id ). The released distribution under input x is the mixture Rx = γ N (0, σ02 Id ) + A N (x, σ02 Id ),

R⊥ = RBG = N (0, σ02 Id ).

Hence, with respect to RBG , the likelihood ratio is ⟨x, y⟩ ∥x∥2 dRx ϕσ (y − x) 2 − . (y) = γ + A 0 = γ + A exp dRBG ϕσ0 (y) σ02 2σ02 For the zero-out neighbor pair (x, ⊥), the corresponding centered blanket-referenced difference equals Rx (y) − R⊥ (y) dRx ∥x∥22 ℓ0 (y; x, ⊥, RBG ) = − − 1 . = (y) − 1 = A exp ⟨x,y⟩ 2 2 σ0 2σ0 RBG (y) dRBG Under Y ∼ RBG = N (0, σ02 Id ) we have ⟨x, Y ⟩ ∼ N (0, σ02 ∥x∥22 ), and therefore h ⟨x, Y ⟩ ∥x∥2 i h ⟨x, Y ⟩ ∥x∥2 i ∥x∥2 2 2 2 E exp − = 1, E exp 2 − = exp . σ02 2σ02 σ02 σ02 σ02 It follows that

VarY ∼RBG [ℓ0 (Y ; x, ⊥, RBG )] = A2 exp(∥x∥22 /σ02 ) − 1 .

By monotonicity in ∥x∥2 and sup∥x∥2 ≤1 ∥x∥2 = 1, the worst case occurs at ∥x∥2 = 1, hence s r 1 A2 1/σ2 VarY ∼RBG [ℓ0 (Y ; x, x′ , RBG )] = e 0 −1 . sup γ γ x≃x′ Recalling the definition of χlo , we obtain the exact identity 1 γ 1 γ = · . χlo (R)2 = 2 · 1/σ2 A e 0 −1 (1 − γ)2 e1/σ02 − 1 Step 2: Worst-case squared error of the unbiased estimator. Consider the linear estimator x b(Y ) = Y /A, which is unbiased. For any x ∈ X , since x b(Y ) is unbiased for x, E ∥b x(Y ) − x∥22 = tr(Cov(b x(Y ))) . The distribution Rx is a two-component Gaussian mixture with common covariance σ02 Id and means 0 and x. Thus E[Y ] = (1 − γ)x = Ax, Cov(Y ) = σ02 Id + γA xx⊤ . Here, Cov(Y ) = E[Cov(Y | B)] + Cov(E[Y | B]) . Since Cov(Y

| B) = σ02 Id for both B = 0, 1, E[Cov(Y | B)] = σ02 Id .

and Cov(E[Y | B]) = γ(0 − Ax)(0 − Ax)⊤ + A(x − Ax)(x − Ax)⊤ = γA2 xx⊤ + Aγ 2 xx⊤ = γA xx⊤ . Therefore, Cov(Y ) = σ02 Id + γA xx⊤ . Therefore, 1 σ02 γ Cov(Y ) = Id + xx⊤ , 2 2 A A A and taking the trace yields the exact squared error Cov(b x(Y )) =

d σ2 γ E ∥b x(Y ) − x∥22 = 20 + ∥x∥22 A A Maximizing over ∥x∥2 ≤ 1 gives the worst-case single-user MSE d σ2 γ sup E ∥b x(Y ) − x∥22 = 20 + . A A x∈X 27

(38)

Step 3: Tuning of (γ, σ0 ) under χlo (R) ≥ χ. Fix χ > 0 and write A := 1 − γ ∈ (0, 1) and t := 1/σ02 > 0. Imposing the equality constraint χlo (R) = χ is without loss of generality for an upper bound (we are free to pick any feasible parameters), and yields the exact relation 1−A 1−A γ t ⇐⇒ t = log 1 + 2 2 . (39) e −1= 2 2 = 2 2 A χ A χ A χ Define u :=

1−A . A2 χ2

Then t = log(1 + u). In the strong-privacy regime we will choose A → 0, hence u → 0 as χ → ∞. Choice of parameters. Set A := χ−2/3 ,

γ := 1 − A,

σ02 := 1/t,

t := log(1 + u),

(40)

where u = (1 − A)/(A2 χ2 ) as above. With this choice, u=

1−A 1 1 = 2 2− = χ−2/3 − χ−4/3 . A2 χ2 A χ Aχ2

(41)

In particular, for all sufficiently large χ, we have 0 < u ≤ 1/2, so the Taylor expansion of log(1 + u) with a controlled remainder applies. A useful analytic bound. For u ∈ (0, 1/2], define u2 Rlog (u) := log(1 + u) − u − 2

A standard remainder bound (e.g. from the Lagrange form of the Taylor remainder, using that |(log(1+u))(3) | = 2/(1 + u)3 ≤ 2 on [0, 1/2]) gives |Rlog (u)| ≤ Clog u3

for all u ∈ (0, 1/2],

for some universal constant Clog > 0. Consequently, u t = log(1 + u) = u 1 − + ρ(u) , 2

|ρ(u)| ≤ Clog u2 .

(42)

(43)

Expansion of the dominant term 1/(A2 t). Using (43), 1 1 1 = 2 · . u 2 A t A u 1 − 2 + ρ(u) 1 For χ large enough, u is small and thus − u2 + ρ(u) ≤ 1/4, so we may use the expansion 1+z = 1 − z + O(z 2 ) u with z = − 2 + ρ(u) to obtain 1 u = 1 + + O(u2 ), (44) 1 − u2 + ρ(u) 2

where the O(u2 ) term is uniform for all sufficiently large χ. Next, observe that 1 1 A2 χ2 χ2 = = . · A2 u A2 1 − A 1−A

(45)

Since A = χ−2/3 → 0, we also have the geometric expansion 1 = 1 + A + O(A2 ). 1−A

(46)

Combining (44), (45), and (46) yields u 1 2 2 2 1 + A + = χ + O(A + u + Au) . A2 t 2

(47)

With our choice (40) and (41), we have A = χ−2/3 and u = χ−2/3 + O(χ−4/3 ), so A+

u 1 3 = χ−2/3 + χ−2/3 + O(χ−4/3 ) = χ−2/3 + O(χ−4/3 ), 2 2 2

and moreover A2 + u2 + Au = O(χ−4/3 ). Plugging into (47) gives the refined asymptotic 3 −2/3 1 2 −4/3 = χ 1 + χ + O(χ ) . A2 t 2

(48)

Mixture penalty term. The second term in the exact worst-case MSE (38) is γ 1−A 1 = = − 1 = χ2/3 − 1. A A A Therefore, for fixed d ≥ 1, γ/A = O(χ−4/3 ), dχ2

(49)

so it contributes only to the O(χ−4/3 ) remainder in the relative error. Conclusion. Substituting (48) and (49) into the exact MSE expression (38) yields 3 −2/3 −4/3 2 2 + O(χ ) , sup E ∥b x(Y ) − x∥2 = dχ 1 + χ 2 ∥x∥2 ≤1 with (γ, σ0 ) as in (40). This proves the claimed upper bound for Err1 under the constraint χlo (R) ≥ χ.

A.7

Theorem 3.3

Theorem 3.3 (Gaussian Limit Correspondence). Fix a constant σ > 0. In the σ-high privacy regime {(εn , δn )}n≥1 d σ 2 ≤ Err⋆DP ({(εn , δn )}n≥1 ) ≤ d σ 2 1 + η(σ) , where η(σ) ≥ 0 depends only on σ and satisfies η(σ) = O(σ −2/3 ) as σ → ∞. Proof. Fix σ > 0 and assume that {(εn , δn )}n≥1 lies in the σ-high privacy regime (Definition 3.1). Step 1: Reduction to shuffle-index constrained problems.

By Lemma 3.4, for any η > 0,

Err⋆up (σ) ≤ Err⋆DP ({(εn , δn )}n≥1 ) ≤ Err⋆lo (σ + η).

(50)

Step 2: Lower bound. Consider the single-user optimization problem (6) with constraint χup (R) ≥ σ. By Theorem 3.5, for any feasible pair (R, x b) we have Err1 (R, x b) ≥ d χup (R)2 ≥ d σ 2 . Taking the infimum over all feasible (R, x b) yields Err⋆up (σ) ≥ d σ 2 . Combining (50) and (51) gives Err⋆DP ({(εn , δn )}n≥1 ) ≥ d σ 2 . 29

(51)

Step 3: Upper bound. Fix η = 1. We invoke the explicit upper bound proved in Corollary 3.6: there exist constants χ0 ≥ 1 and C > 0 such that for all χ ≥ χ0 , 3 −2/3 ⋆ 2 −4/3 Errlo (χ) ≤ d χ 1 + χ +Cχ . (52) 2 Using the right inequality in (50) (with η = 1) yields Err⋆DP ({(εn , δn )}n≥1 ) ≤ Err⋆lo (σ + 1).

(53)

Case 1: σ + 1 ≥ χ0 . Combining (53) with (52) (applied at χ = σ + 1) gives 3 ⋆ −2/3 −4/3 2 + C (σ + 1) . ErrDP ({(εn , δn )}n≥1 ) ≤ d (σ + 1) 1 + (σ + 1) 2

(54)

Define for σ ≥ χ0 − 1, (σ + 1)2 η(σ) := σ2

3 1 + (σ + 1)−2/3 + C (σ + 1)−4/3 2

− 1.

(55)

Then (54) rewrites as Err⋆DP ({(εn , δn )}n≥1 ) ≤ d σ 2 1 + η(σ) ,

for all n sufficiently large.

Moreover, since the bracketed factor in (55) is at least 1 and (σ + 1)2 /σ 2 ≥ 1, we have η(σ) ≥ 0 for all σ ≥ χ0 − 1. Finally, as σ → ∞, (σ + 1)2 (σ + 1)2 3 −2/3 −4/3 η(σ) = −1 + (σ + 1) + C(σ + 1) = O(σ −1 ) + O(σ −2/3 ) = O(σ −2/3 ). σ2 σ2 2 Case 2: σ + 1 < χ0 . In this case, we simply define η(σ) ≥ 0 large enough so that Err⋆lo (σ + 1) ≤ d σ 2 1 + η(σ) . For example, it suffices to take

Err⋆lo (σ + 1) η(σ) := max 0, − 1 . d σ2

With this definition, the bound Err⋆DP ({(εn , δn )}n≥1 ) ≤ d σ 2 1 + η(σ)

holds for all n sufficiently large by (53). Moreover, this definition affects η(σ) only on the bounded interval σ ∈ (0, χ0 − 1) and therefore does not change the asymptotic statement η(σ) = O(σ −2/3 ) as σ → ∞. Conclusion.

A.8

Combining the lower and upper bounds established above completes the proof.

Proposition 4.2

Proposition 4.2. Consider the Gaussian local q randomizer RGL = N (x, σ02 Id ), x ∈ Bd2 , together with the x unbiased estimator x b(Y ) = Y . Let χchua := 1/ VarY ∼RGL ℓ0 Y ; e, 0, RGL where e ∈ Sd−1 . Then, as −e −e σ0 → ∞ (equivalently χchua → ∞), Err1 (R

,x b) = d χ2chua

9 −2 −4 1 + χchua + O(χchua ) . 2

Proof. Consider the Gaussian local randomizer Rx = N (x, σ02 Id ),

x ∈ Bd2 ,

which corresponds to the case γ = 0. A natural unbiased per-message estimator is x b(Y ) = Y,

since E[Y | x] = x.

Hence the (single-user) worst-case squared error is Err1 (R, x b) := sup E ∥b x(Y ) − x∥22 = E∥Z∥22 = dσ02 , x∈Bd 2

Z ∼ N (0, σ02 Id ).

(56)

Step 1: computing a concrete variance term for χchua . ℓ0 (y; x1 , x′1 , Rx ) =

Recall

Rx1 (y) − Rx′1 (y) . Rx (y)

Write σ 2 := σ02 and Rµ = N (µ, σ 2 ). Let U be any orthogonal matrix. Since Y ∼ N (µ, σ 2 Id ) implies U Y ∼ N (U µ, σ 2 Id ), and Gaussian density ratios are preserved under the change of variables y 7→ U y, we have d

ℓ0 (Y ; x1 , x′1 , Rx ) = ℓ0 (U Y ; U x1 , U x′1 , RU x ), and hence Var[ℓ0 (Y ; x1 , x′1 , Rx )] is invariant under applying the same rotation to (x1 , x′1 , x). Therefore, we may rotate coordinates so that x1 = e1 , x′1 = 0, and x = −e1 . Moreover, ℓ0 (y; e1 , 0, R−e1 ) depends on y only through the one-dimensional projection ⟨y, e1 ⟩, and for Y ∼ N (−e1 , σ 2 Id ) we have ⟨Y, e1 ⟩ ∼ N (−1, σ 2 ). Identifying this coordinate with R, we may write x1 = 1, x′1 = 0, and x = −1 without loss of generality. Using the Gaussian density ratio identity ϕµ1 ,σ2 (y) (µ1 − µ2 )y µ21 − µ22 = exp − , ϕµ2 ,σ2 (y) σ2 2σ 2 we obtain

2y R1 (y) = exp 2 , R−1 (y) σ

and therefore

y 1 R0 (y) = exp 2 + 2 , R−1 (y) σ 2σ

2y 1 y ℓ0 (y) = ℓ0 (y; 1, 0, R−1 ) = exp 2 − exp 2 + 2 . σ σ 2σ

(57)

Let Y ∼ Rx = N (−1, σ 2 ). Using the Gaussian MGF E[etY ] = exp(tµ + 12 t2 σ 2 ) with µ = −1, one checks E[ℓ0 (Y )] = 0, and hence Var[ℓ0 (Y )] = E[ℓ0 (Y )2 ]. Expanding the square in (57) and taking expectations term-by-term yields 2 2 2 VarY ∼N (−1,σ2 ) [ℓ0 (Y )] = e4/σ − 2e2/σ + e1/σ . (58) 2

V (σ 2 ) := e4/σ − 2e2/σ + e1/σ , Then, by definition of χchua , χchua (R)2 =

1 1 . = ′ VarY ∼Rx [ℓ0 (Y ; x1 , x1 , Rx )] V (σ 2 ) 2

c Step 2: asymptotic expansion as σ0 → ∞. Let a := 1/σ 2 . Using eca = 1+ca+ c2 a2 + c6 a3 + 24 a4 +O(a5 ), we expand (58):

9 49 75 V (σ 2 ) = a + a2 + a3 + a4 + O(a5 ). 2 6 8

(59)

Inverting the series gives χ2chua (σ 2 ) =

1 1 9 145 2 3 4 = 1 − a + a − 27a + O(a ) V (σ 2 ) a 2 12 9 145 1 27 1 2 =σ − + − 4 +O 6 . 2 12 σ 2 σ σ

(60)

Step 3: expressing σ02 (hence Err1 ) as a series in χchua . Reverting the expansion (60) yields, as χchua → ∞, σ 2 = χ2chua +

9 145 −2 651 −4 − χchua + χchua + O χ−6 chua . 2 12 8 31

(61)

Conclusion (error expansion).

Combining (56) and (61), we obtain

145 −2 9 d χchua + O d χ−4 Err1 (R, x b) = d σ02 = d χ2chua + d − chua , 2 12

(σ0 → ∞).

Regularity conditions for the local randomizer

Assumption B.1 (Regularity conditions for the local randomizer). Consider the local randomizer R : X⊥ → Y and recall that we set R⊥ := RBG under zero-out adjacency. We assume that there exists ρ0 > 0 such that, for every pair x1 ̸= x′1 ∈ X⊥ and every reference distribution Rref ∈ RBG ∪ Rx : x ∈ X , the following conditions hold uniformly over all ε ≤ ρ0 . (1) Uniform moment bounds. For every integer k ≥ 1, EY ∼Rref |ℓε (Y ; x1 , x′1 , Rref )|k < ∞. (2) Non-degenerate variance. The variance σ 2 := VarY ∼Rref ℓ0 (Y ; x1 , x′1 , Rref ) is strictly positive R Rx1 (y)2 R Rx′1 (y)2 when Rx1 ̸= Rx′1 . Moreover, the following conditions hold: Rref (y) dy < ∞ and Rref (y) dy < ∞. (3) Structural condition. Either of the following holds. (Cont) ℓε (Y ; x1 , x′1 , Rref ) has a nontrivial absolutely continuous component with respect to Lebesgue measure whose support contains a fixed nondegenerate bounded interval I ⊂ R independent of ε. (Bound) There exists a constant C < ∞ such that |ℓε (Y ; x1 , x′1 , Rref )| ≤ C almost surely. Assumption B.1 is mild: any nontrivial local randomizer that satisfies pure LDP automatically satisfies these conditions, and even when pure LDP does not hold, if the privacy amplification random variable ℓ0 (Y ; x1 , x′1 , Rref ) is non-degenerate (i.e., not almost surely constant), then one can enforce the bounded case (Bound) in (3) by truncating the output space to a large but bounded interval (i.e., by slightly modifying the local randomizer).

Computing the shuffled (ε, δ) guarantee

Lemma 5.3 of Balle et al. [5] implies that the shuffled blanket-mixed Gaussian mechanism is (ε, δ(ε))-DP with ! # " M 0 X 1 ℓε (Yi ) δ(ε) ≤ E nγ i=1 +

where

i.i.d.

M0 ∼ Bin(n, γ), Y1 , Y2 , . . . ∼ RBMG BG , and (a)+ := max{a, 0}. In the zero-out adjacency model, the neighboring inputs are x ∈ X and ⊥, and RBMG is the blanket ⊥ distribution. BMG RBMG = N (0, σ02 Id ), BG = R⊥

RBMG = γ N (0, σ02 Id ) + (1 − γ) N (x, σ02 Id ). x Hence, for any ε > 0 RBMG (y) − eε RBMG (y) x ⊥ RBMG (y) BG ⟨y, x⟩ ∥x∥22 = γ + (1 − γ) exp − − eε . σ02 2σ02

ℓε (y) :=

(62)

Therefore, we can compute the distribution of ℓε (Y ), which enables the rigorous numerical upper bounds using the FFT-based accountant of Takagi and Liew [26], which computes the required convolution terms efficiently with explicit truncation/discretization/wrap-around error bounds. 32

Record · ID 146931 · SHA-256 96191662832ba700
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.