Timezone: »

 
Poster
Concurrent Shuffle Differential Privacy Under Continual Observation
Jay Tenenbaum · Haim Kaplan · Yishay Mansour · Uri Stemmer

Wed Jul 26 02:00 PM -- 03:30 PM (PDT) @ Exhibit Hall 1 #329
in Poster Session 3 »
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) shuffler 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) shuffler model. Specifically, we give a summation algorithm with error $\tilde{O}(n^{1/(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 $\tilde{\Theta}(n^{1/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 $\tilde{O}(\sqrt{n})$ regret with $k= \tilde{\Omega}(\log n)$ concurrent shufflers.
[ PDF] 

Author Information

Jay Tenenbaum (Google)
Haim Kaplan (TAU, GOOGLE)
Yishay Mansour (Google and Tel Aviv University)
Uri Stemmer (Tel Aviv University and Google Research)

More from the Same Authors