Concurrent Shuffle Differential Privacy Under Continual Observation
Not on the map. Why?
Abstract (arXiv)
We introduce the concurrent shuffle model of differential privacy. In this model we have multiple concurrent shufflers permuting messages from different, possibly overlapping, batches of users. Similarly to the standard (single) shuffle model, the privacy requirement is that the concatenation of all shuffled messages should be differentially private. We study the private continual summation problem (a.k.a. the counter problem) and show that the concurrent shuffle model allows for significantly improved error compared to a standard (single) shuffle model. Specifically, we give a summation algorithm with error tildeO(n1/(2k+1)) with k concurrent shufflers on a sequence of length n. Furthermore, we prove that this bound is tight for any k, even if the algorithm can choose the sizes of the batches adaptively. For k=log n shufflers, the resulting error is polylogarithmic, much better than tildeTheta(n1/3) which we show is the smallest possible with a single shuffler. We use our online summation algorithm to get algorithms with improved regret bounds for the contextual linear bandit problem. In particular we get optimal tildeO(√n) regret with k= tildeOmega(log n) concurrent shufflers.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 32 of its 56 references that are in the map. First posted on arXiv 29 Jan 2023.
Builds on
32 of 56 references.
References · 32
- 2021Practical and Private (Deep) Learning without Sampling or Shufflingcited by 169
- 2018Amplification by Shuffling: From Local to Central Differential Privacy via Anonymitycited by 163
- 2018Distributed Differential Privacy via Shufflingcited by 115
- 2018Differentially Private Contextual Linear Banditscited by 82
- 2019The Privacy Blanket of the Shuffle Modelcited by 73
- 2020Sequential Batch Learning in Finite-Action Linear Contextual Banditscited by 63
- 2022Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streamscited by 59
- 2020Locally Differentially Private (Contextual) Bandits Learningcited by 52
- 2017Prochlo: Strong Privacy for Analytics in the Crowdcited by 51
- 2020Private Reinforcement Learning with PAC and Regret Guaranteescited by 51
- 2020Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluationcited by 39
- 2019An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rulecited by 37
20 more
- 2020Multi-Armed Bandits with Local Differential Privacycited by 37
- 2021The Price of Differential Privacy under Continual Observationcited by 32
- 2021Generalized Linear Bandits with Local Differential Privacycited by 29
- 2022Shuffle Private Linear Contextual Banditscited by 27
- 2022Almost Tight Error Bounds on Differentially Private Continual Countingcited by 25
- 2017Achieving Privacy in the Adversarial Multi-Armed Banditcited by 24
- 2021Differentially Private Multi-Armed Bandits in the Shuffle Modelcited by 24
- 2021Differentially Private Regret Minimization in Episodic Markov Decision Processescited by 23
- 2020Local Differential Privacy for Regret Minimization in Reinforcement Learningcited by 22
- 2019Scalable and Differentially Private Distributed Aggregation in the Shuffled Modelcited by 20
- 2020Local Differential Privacy for Bayesian Optimizationcited by 19
- 2021Shuffle Private Stochastic Convex Optimizationcited by 17
- 2021Privacy Amplification via Shuffling for Linear Contextual Banditscited by 17
- 2020(Locally) Differentially Private Combinatorial Semi-Banditscited by 14
- 2021Differentially Private Histograms under Continual Observation: Streaming Selection into the Unknowncited by 14
- 2021Differential Privacy in the Shuffle Model: A Survey of Separationscited by 14
- 2021Differentially Private Algorithms for Graphs Under Continual Observationcited by 12
- 2021No-Regret Algorithms for Private Gaussian Process Bandit Optimizationcited by 11
- 2023Differentially Private Continual Releases of Streaming Frequency Moment Estimationscited by 10
- 2022On Differentially Private Counting on Treescited by 7
Built on by
Citing papers per year: 2023: 1; 2024: 0; 2025: 1.
2 papers.