Matthew Joseph
Research Areas
Authored Publications
Sort By
A Joint Exponential Mechanism for Differentially Private Top-k
Jenny Gillenwater
Monica Ribero Diaz
International Conference on Machine Learning (ICML) 2022
Preview abstract
We present a differentially private algorithm for releasing the sequence of $k$ elements with the highest counts from a data domain of $d$ elements. The algorithm is a ``joint'' instance of the exponential mechanism, and its output space consists of all $O(d^k)$ length-$k$ sequences. Our main contribution is a method to sample this exponential mechanism in time $O(dk\log(k) + d\log(d))$ and space $O(dk)$. Experiments show that this approach outperforms existing pure differentially private methods and often improves upon even approximate differentially private methods for moderate $k$.
View details
Preview abstract
In shuffle privacy, each user sends a collection of randomized messages to a trusted shuffler, the shuffler randomly permutes these messages, and the resulting shuffled collection of messages must satisfy differential privacy. Prior work in this model has largely focused on protocols that use a single round of communication to compute algorithmic primitives like means, histograms, and counts. In this work, we present interactive shuffle protocols for stochastic convex optimization. Our optimization protocols rely on a new noninteractive protocol for summing vectors of bounded $\ell_2$ norm. By combining this sum subroutine with accelerated gradient descent, Nesterov's smoothing method, and a careful alignment of noise level and mini-batch size, we obtain loss guarantees that significantly improve on those of the local model and sometimes match those of the central model.
View details
Preview abstract
In the shuffle model of differential privacy, data-holding users send randomized messages to a secure shuffler, the shuffler permutes the messages, and the resulting collection of messages must be differentially private with regard to user data. In the pan-private model, an algorithm processes a stream of data while maintaining an internal state that is differentially private with regard to the stream data. We give evidence connecting these two apparently different models.
Our results focus on robustly shuffle private protocols, whose privacy guarantees are not greatly affected by malicious users. First, we give robustly shuffle private protocols and upper bounds for counting distinct elements and uniformity testing. Second, we use pan-private lower bounds to prove robustly shuffle private lower bounds for both problems. Focusing on the dependence on the domain size k, we find that robust approximate shuffle privacy and approximate pan-privacy have additive error Θ(k^1/2) for counting distinct elements. For uniformity testing, we give a robust approximate shuffle private protocol with sample complexity O(k^2/3) and show that an Ω(k^2/3) dependence is necessary for any robust pure shuffle private tester. Finally, we show that this connection is useful in both directions: we give a pan-private adaptation of recent work on shuffle private histograms and use it to recover further separations between pan-privacy and interactive local privacy.
View details
Preview abstract
A differentially private algorithm guarantees privacy against an adversary that sees the output of the algorithm. We study pan-privacy, which guarantees privacy against an adversary that sees both the output and any single internal state of the algorithm during its computation. First, we motivate the single-intrusion assumption by showing that pan-privacy against multiple intrusions is equivalent to sequentially interactive local privacy. Next, we contextualize pan-privacy by analyzing the sample complexity of uniformity testing. We show that this sample complexity sits strictly between that of the central and (sequentially interactive) local models.
View details
