Steven Wu (UMN)

Apr 15.

Title and Abstract

How to Use Heuristics for Differential Privacy
We develop theory for using heuristics to solve computationally hard problems in differential privacy. Heuristic approaches have enjoyed tremendous success in machine learning, for which performance can be empirically evaluated. However, privacy guarantees cannot be evaluated empirically, and must be proven  —  without making heuristic assumptions. We show that learning problems over broad classes of functions can be solved privately and efficiently, assuming the existence of a non-private oracle for solving the same problem. Our first algorithm yields a privacy guarantee that is contingent on the correctness of the oracle. We then give a reduction which applies to a class of heuristics which we call certifiable, which allows us to convert oracle-dependent privacy guarantees to worst-case privacy guarantee that hold even when the heuristic standing in for the oracle might fail in adversarial ways. Finally, we consider a broad class of functions that includes most classes of simple boolean functions studied in the PAC learning literature, including conjunctions, disjunctions, parities, and discrete halfspaces. We show that there is an efficient algorithm for privately constructing synthetic data for any such class, given a non-private learning oracle. This in particular gives the first oracle-efficient algorithm for privately generating synthetic data for contingency tables. The most intriguing question left open by our work is whether or not every problem that can be solved differentially privately can be privately solved with an oracle-efficient algorithm. While we do not resolve this, we give a barrier result that suggests that any generic oracle-efficient reduction must fall outside of a natural class of algorithms (which includes the algorithms given in this paper).

Bio

Steven Wu is an Assistant Professor in computer science at the University of Minnesota. During 2017-2018, he was a post-doc researcher at Microsoft Research-New York City. Before that he received his PhD in computer science at the University of Pennsylvania, where he was co-advised by Michael Kearns and Aaron Roth. His research interests lie in algorithms and machine learning, especially in the areas of privacy-preserving data analysis, fairness in machine learning, and algorithmic economics. He is the recipient of a Google Faculty Research Award, a J.P. Morgan Faculty Award, and the Morris and Dorothy Rubinoff Dissertation Award