PaperlayerView exact revision on arXiv

Source-linked AI summary

Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling

Vitaly Feldman, Audra McMillan, Kunal Talwar

arXiv:2012.12803v3cs.LGcs.CRcs.DSstat.ML

TL;DR

The paper addresses sub-optimal privacy amplification bounds for shuffled locally private data, especially when ε0 > 1. It introduces a simpler clone-based analysis for adaptive local randomizers and obtains asymptotically optimal dependence, tighter numerical bounds, and applications to frequency estimation and private SGD.

  • Problem

    Existing shuffle-amplification analyses have sub-optimal ε0 dependence for ε0 > 1 and do not apply to approximate-DP local randomizers.

  • Method

    The proof reduces adaptive local algorithms to a non-adaptive three-output clone-based analysis and supports tighter numerical evaluation.

  • Results

    The analysis achieves asymptotically optimal ε0 dependence, extends to approximate DP with nearly the same guarantees, and numerically gives tighter bounds than prior methods.

  • Takeaways & Limitations

    The result yields a nearly optimal low-communication shuffle-model frequency estimator and supports private SGD analysis with sampling without replacement.

  • Takeaways & Limitations

    The optimal dependence of δ on n and ε0 remains an open question.

Abstract

from arXiv · show

Recent work of Erlingsson, Feldman, Mironov, Raghunathan, Talwar, and Thakurta [EFMRTT19] demonstrates that random shuffling amplifies differential privacy guarantees of locally randomized data. Such amplification implies substantially stronger privacy guarantees for systems in which data is contributed anonymously [BEMMRLRKTS17] and has lead to significant interest in the shuffle model of privacy [CSUZZ19; EFMRTT19]. We show that random shuffling of $n$ data records that are input to $\varepsilon_0$-differentially private local randomizers results in an $(O((1-e^{-\varepsilon_0})\sqrt{\frac{e^{\varepsilon_0}\log(1/δ)}{n}}), δ)$-differentially private algorithm. This significantly improves over previous work and achieves the asymptotically optimal dependence in $\varepsilon_0$. Our result is based on a new approach that is simpler than previous work and extends to approximate differential privacy with nearly the same guarantees. Importantly, our work also yields an algorithm for deriving tighter bounds on the resulting $\varepsilon$ and $δ$ as well as Rényi differential privacy guarantees. We show numerically that our algorithm gets to within a small constant factor of the optimal bound. As a direct corollary of our analysis we derive a simple and nearly optimal algorithm for frequency estimation in the shuffle model of privacy. We also observe that our result implies the first asymptotically optimal privacy analysis of noisy stochastic gradient descent that applies to sampling without replacement.

1 Introduction

The paper develops a simpler analysis showing that shuffling locally private reports achieves asymptotically optimal dependence on the local privacy parameter. The approach extends to approximate differential privacy, tighter numerical bounds, frequency estimation, and shuffled-data private SGD.

  • Motivation: The prior amplification bound has sub-optimal dependence on ε0 when ε0 > 1 and does not cover approximate-DP local randomizers.In this regime, the prior central privacy parameter is ˜O(e3ε0/√n).
  • Main result: The paper proves that adaptive sequences of arbitrary ε0-DP local randomizers on a random permutation yield an (ε, δ)-DP algorithm.The result applies to n data items and uniformly random permutations.
  • Main result: When ε0 > 1, the dependence improves from e2.5ε0 to the asymptotically correct eε0/2, while matching existing bounds for ε0 < 1.The dependence is asymptotically optimal in both regimes.
  • Proof approach: The proof reduces adaptive shuffling analysis to a simple non-adaptive three-output algorithm, using the probability that local reports form clones.For ε0 > 1, privacy follows from the binomially distributed number of clones hiding a changed record.
  • Applications: The paper derives tighter numerical amplification bounds, a nearly optimal shuffle-model frequency estimator, and an analysis of private SGD using sampling without replacement.Numerical bounds are tighter than the closed-form bound, and the frequency estimator has low communication and server-side decoding time.
  • Extensions: The analysis extends to approximate differential privacy with essentially the same guarantees by converting the local randomizer through a total-variation approximation.The conversion bounds TV(A(x), A′(x)) by δ0 for every input.

2 Background and Preliminaries

This section introduces differential privacy, central and local privacy models, and the shuffle model. It also reviews privacy amplification by subsampling and divergence tools used to analyze indistinguishability.

  • Differential privacy: Differential privacy measures algorithmic stability by bounding how output distributions change when one input is replaced.The common formulation uses (ε, δ)-indistinguishability.
  • Privacy models: In the central model, a trusted curator holds individual data and releases an analysis whose outputs satisfy differential privacy.Neighboring databases differ in one individual’s data.
  • Privacy models: In the local model, each client randomizes its data before sending a report, reducing the need to trust the curator.A local randomizer must produce indistinguishable outputs for every pair of inputs.
  • Local protocols: Adaptive local protocols allow each client’s randomizer to depend on preceding reports while remaining differentially private for every auxiliary input.This models server communication based on earlier client messages.
  • Shuffle model: The shuffle model adds a shuffler that anonymizes client reports by applying a random permutation before releasing them to the server.Reports are typically encrypted so the shuffler cannot decrypt them while the server can.
  • Amplification tools: Privacy amplification by subsampling analyzes an algorithm run on a uniformly random subset of a larger dataset, while hockey-stick divergence characterizes (ε, δ)-indistinguishability.The divergence preserves privacy under post-processing.

3 Improved Guarantees for Privacy Amplification by Shuffling

The paper gives an improved privacy-amplification upper bound for adaptive ε0-DP local randomizers under shuffling, together with a reduction to a simple three-output non-adaptive analysis. The proof also supports tighter numerical bounds and extends to approximately differentially private randomizers.

  • Theorem 3.1 gives an improved privacy-amplification guarantee for adaptive ε0-DP randomizers, particularly in the high-ε0 regime.
  • The theorem applies when ε0 ≤ log(n / (16 log(2/δ))); outside this regime, the paper asks whether the bound continues to hold.
  • Theorem 3.2 provides an efficient numerical method for a tighter amplification bound by computing indistinguishability for specific multinomial distributions.
  • The proof reduces adaptive shuffled local algorithms to a simple non-adaptive local algorithm with three outputs, using a clone-based mixture interpretation of local randomizer outputs.
  • For each non-special data point, the reduction assigns probability at least e^-ε0/2 to cloning either neighboring reference output, producing random numbers of both clone types.
  • The approximate-DP extension has an ε bound matching Theorem 3.1, while the dependence of δ on n and ε0 remains an open question.

4 A Tighter Analysis for Specific Randomizers

The section develops a refined privacy-amplification analysis that exploits properties of specific local randomizers, yielding tighter bounds and an empirical method for evaluating them. Applied to k-randomized response, the analysis shows privacy amplification improves as the alphabet size increases.

  • 4.1 k-Randomized Response: For k-randomized response, the refined analysis gives a privacy-amplification result whose dependence on k improves as k increases.This theoretical behavior corroborates empirical results and is accompanied by a method for empirically computing the privacy guarantee.
  • Theorem 4.1 analyzes adaptive ε0-DP randomizers applied sequentially after a uniformly random permutation of the data.The neighboring datasets differ in one record, and the local randomizers may depend on previous outputs.
  • The proof reduces shuffled outputs to postprocessed multinomial distributions with a Bernoulli perturbation, enabling an (ε, qδ)-indistinguishability guarantee under a condition on p.The stated condition is p ≥ 8 ln(2/δ) / n.
  • The refined theorem provides tighter privacy-amplification bounds for specific local randomizers and can also be used to rederive the general bound.The general rederivation has a slightly worse constant factor.
  • 4.1 k-Randomized Response: k-randomized response reports the true value with probability (e^ε0 − 1)/(e^ε0 + k − 1) and otherwise reports a random value from the alphabet.The mechanism maps [k] to [k].
  • 4.1 k-Randomized Response: When k is small, the refined bound matches Theorem 3.1; when k and ε0 are large, ε scales like e^ε0√k/n.

5 Applications

The paper applies privacy amplification by shuffling to frequency estimation and private stochastic gradient descent, obtaining nearly optimal estimation guarantees and a tighter analysis for sampling without replacement.

  • 5.1 Frequency and Distribution Estimation: Nearly optimal utility/privacy trade-offs follow for frequency and distribution estimation in both local and central differential privacy models.The resulting protocols also use low communication.
  • 5.1 Frequency and Distribution Estimation: The amplification result enables a single-round, low-communication shuffle algorithm whose distribution-estimation error matches central-model optimal error up to an O(log(1/δ)) factor.This uses locally differentially private results with asymptotically optimal accuracy.
  • 5.1 Frequency and Distribution Estimation: For frequency estimation, central-model error is optimal up to a 1/√n additive term that is necessary for single-message shuffle protocols.The additive term is comparable to statistical error.
  • 5.1 Frequency and Distribution Estimation: The frequency-estimation protocol uses server-side decoding time ˜O(n + k) and a single message from each local randomizer.The supplied passages do not state the complete message-length expression here.
  • 5.2 Privacy Analysis of Private Stochastic Gradient Descent: For private stochastic gradient descent, shuffling supports almost the same utility with sampling without replacement instead of sampling with replacement.Without-replacement sampling is described as more common and typically more efficient in practice, with simpler generalization-error analysis.
  • 5.2 Privacy Analysis of Private Stochastic Gradient Descent: For one pass with ε0 > 1, the privacy analysis is tighter than the prior sampling-with-replacement analysis.For multiple passes, the analysis incurs an extra log(1/δ) factor in privacy loss.

6 Numerical Results

The numerical experiments compare the paper’s closed-form and numerically computed amplification bounds with prior general bounds and binary randomized-response bounds, including Rényi differential privacy evaluations.

  • Numerical Computation: Theorem 3.2 provides an efficient numerical method that produces a tighter amplification bound than the paper’s closed-form bound.The implementation numerically computes an indistinguishability bound for multinomial random variables.
  • Privacy Amplification Bounds: In all tested parameter regimes, Clones gives a tighter bound than BBGN’19 and BKMTT’20.The improvement is particularly pronounced when ε0 is large.
  • Privacy Amplification Bounds: For large n, Clones closely tracks the 2RR lower bound, particularly for small ε0.The 2RR lower bound is also a lower bound on any general privacy amplification result.
  • Privacy Amplification Bounds: Figure 2 compares closed-form bounds, shown as dotted lines, with numerically computed bounds, shown as solid lines.The comparison includes this work, BBGN19, BKMTT20, and bounds specific to 2RR from CSUZZ19.
  • Rényi Differential Privacy: The RDP evaluation computes Rényi divergence between two specific multinomial distributions and compares the resulting bound with GDDSK’21.The privacy parameter is plotted as a function of the RDP order α.

A Proof of Lemma 3.5

The proof reduces the relevant shuffled privacy analysis to comparing two closely related distributions generated from binomial random variables, then uses concentration and convexity arguments to establish indistinguishability.

  • Proof Strategy: The proof first upper-bounds divergence between a pair of simpler distributions before analyzing the target distributions.This reduction is the first step in proving Lemma 3.5.
  • Concentration Bounds: Chernoff and Hoeffding bounds provide high-probability control of the sampled variables under the lemma’s parameter condition.The supplied proof passage states that this control holds with probability δ under a lower bound on p.
  • Binomial Construction: The proof samples C ∼ Bin(n − 1, p) and A ∼ Bin(C, 1/2), then compares distributions differing by one output count.The distributions are P = (A + 1, C − A) and Q = (A, C − A + 1).
  • Conclusion: The resulting pair P and Q is (ε, δ)-indistinguishable.This establishes the privacy relation required by Lemma 3.5.
  • Divergence Argument: Advanced joint convexity of the hockey-stick divergence completes the proof of Lemma 3.5.The proof also invokes convexity of the hockey-stick divergence for the final comparison.

B Tails of the Privacy Loss

The tail analysis tests whether amplification persists beyond the closed-form bound’s stated condition and finds a sharp transition in shuffled privacy loss as δ varies.

  • Parameter Condition: The closed-form amplification bound is valid only when log(2/δ) ≤ n e^ε0 / 16.The section asks whether this condition is merely a proof artifact or reflects an inherent boundary.
  • Figure 4: Figure 4 compares exact shuffled binary randomized-response privacy loss with the numerical general upper bound as δ varies.Horizontal dotted lines mark log(1/δ) = n e^−ε0 / 2.
  • Observed Transition: Across all three tested ε0 settings, privacy loss sharply transitions from ε < ε0 to ε = ε0.The transition closely aligns with log(1/δ) = n e^−ε0 / 2.

C Proof of Proposition 3.8

The proof transforms approximate-DP local randomizers into nearby deletion-DP randomizers, then reduces shuffled neighboring datasets to a tractable divergence calculation. Total variation perturbations are accumulated across the sequence and converted back using hockey-stick divergence.

  • Reduction to deletion privacy: Lemma 3.7 replaces a deletion (ε, δ)-DP randomizer with a deletion ε-DP randomizer within total variation distance δ.The replacement randomizer also satisfies replacement 2ε-DP.
  • Reduction to deletion privacy: The transformed randomizer is decomposed using two neighboring-output distributions and an auxiliary randomized component.This creates a common mixture structure for all other inputs while preserving the relevant privacy comparison.
  • Error transfer: Total variation errors from all n randomizers increase the final δ by at most (e^ε + 1)(1 + e^−ε0/2)nδ0.The remaining task is to bound the hockey-stick divergence between the transformed shuffled distributions.
  • Divergence calculation: The shuffled distributions reduce, after postprocessing, to binomial variables that differ by shifting one count between two components.The variables use C ∼ Bin(n −1, e^−ε0) and A ∼ Bin(C, 1/2).

D Proof of Theorem 4.1

The proof represents adaptive shuffled local randomizers through a four-outcome mixture and reduces neighboring-dataset divergence to multinomial count distributions. A postprocessing argument then transfers the resulting indistinguishability to the algorithm’s outputs.

  • Theorem setup: Theorem 4.1 analyzes adaptive ε0-DP randomizers applied sequentially to a uniformly random permutation of n data items.Auxiliary inputs may depend on earlier outputs, and the algorithm releases the sequence of randomized outputs.
  • Mixture decomposition: Each local output is decomposed into three distinguished components with probability p and an auxiliary component with probability 1 − 3p.The decomposition uses distributions Q(i)_0, Q(i)_1 and LO(i) for each adaptive history.
  • Postprocessing reduction: A postprocessing function maps multinomial counts plus a Bernoulli variable to outputs distributed identically to the two neighboring executions.The count vector follows MultNom(n −1; p, p, p, 1 −3p), while Γ ∼ Bern(q).
  • Divergence bound: The divergence analysis compares shifted multinomial count distributions and applies hockey-stick divergence convexity to obtain the theorem’s indistinguishability bound.The construction introduces κ distributions for the shifted count components and uses postprocessing to invoke a multinomial divergence lemma.

E Proof of Corollary 4.2

The corollary specializes the four-outcome decomposition to k-ary randomized response. Substituting the resulting mixture parameters into Theorem 4.1 yields the privacy guarantee for the shuffled algorithm.

  • Specialization to frequency mechanisms: The proof chooses the uniform distribution on [k] as the common component and a point mass at the randomized-response output as the input-dependent component.This realizes each k-ary randomized-response local randomizer within the decomposition required by Theorem 4.1.
  • Parameter substitution: The decomposition parameters are q = (e^ε0 − 1)/(e^ε0 + k − 1) and p = k/((k + 1)(e^ε0 + k − 1)).These parameters connect k-ary randomized response to the general mixture theorem.
  • Privacy conclusion: The condition p ≥ 8 ln(2/δ)/n permits Theorem 4.1 to establish (ε, δ)-indistinguishability for neighboring datasets.The corollary’s final ε bound is obtained by substituting the specialized p and q into the theorem.

F Implementation of Clones, empirical

The implementation computes tighter amplification bounds by evaluating hockey-stick divergence for binomial mixtures and using monotonicity, interval approximation, and binary search. A correctness proposition guarantees the resulting ε, δ pair is valid for the analyzed distributions.

  • Divergence computation: The shuffled privacy calculation reduces to two mixtures of (A, C), where C ∼ Bin(n −1, e^−ε0) and A ∼ Bin(C, 1/2).The mixtures differ by whether one count is shifted, with mixing probability q = e^ε0/(e^ε0 + 1).
  • Fixed-count calculation: For fixed c, Lemma F.1 identifies the threshold region where the hockey-stick integrand is positive and computes its contribution from binomial tail probabilities.The implementation uses γP and γQ to evaluate the relevant tails for each sign direction.
  • Efficient approximation: The contribution B(c, ε, ε0, b) decreases with c, enabling Algorithm 6 to sample every Sth c value and bound intermediate intervals conservatively.This monotonicity reduces computation while preserving an upper bound on the divergence.
  • Search and guarantee: Binary search over ε uses the approximate minimal δ for each candidate ε and returns an ε for which the distributions are (ε, δ)-indistinguishable.Proposition F.3 states that the output of BinS is a valid privacy bound for P and Q.

G Implementation of 2RR, lower bound

The implementation analyzes shuffled binary randomized response by comparing neighboring output distributions and uses exact discrete computations with binary search to bound privacy.

  • Binary randomized response maps each client’s binary value to a privatized bit before the reports are randomly permuted.
  • The analysis defines privacy through the minimal ε for which the shuffled outputs are (ε, δ)-indistinguishable, maximizing over neighboring datasets.
  • The lower-bound implementation uses the neighboring datasets X0 = (0, ..., 0) and X1 = (1, 0, ..., 0).
  • Binary search evaluates the smallest δ for candidate ε values and returns εL, producing a lower bound on the minimal ε.
  • Because the output distributions are discrete, their probability density functions can be computed explicitly when n is not too large.
  • Exact computation up to numerical precision makes Algorithm 7 move in the correct direction at every iterate, yielding the guarantee εδ ≥ ε.
Loading 2012.12803v3…