PROBE on Privacy Optimizations

Organized by Anupam Gupta, Carnegie Mellon University
In collaboration with Frank McSherry and Kunal Talwar, Microsoft Research

With the abundance of information available to us nowadays, the question of data privacy has become increasingly important, and must be dealt with in broader contexts than realized before.  For example, most algorithms reveal information about the input in the solutions they output: imagine a company that wants to open warehouses to serve clients. If it uses a good optimization procedure to open warehouses in certain locations, the very knowledge of these warehouse locations (and the locations of their clients) is liable to leak information about who their clients are. A simple way not to leak any private information is to use no input information in the computation---but while this ensures privacy, there is no utility in such an algorithm. On the other hand, algorithms making near-optimal decisions risk leaking information about the input data.

Exploring the tension between privacy and utility has been the focus of much recent study.  It is clear that Computational Thinking can have a deep impact, and that privacy can be viewed as a computational resource much like processor cycles and memory. We can, in fact, design algorithms to strike the best trade-off between utility and privacy.

In this PROBE we will develop "private" optimization algorithms: these are algorithms that explicitly consider privacy issues, and give a quantifiable trade-off between the value of the objective function, and the privacy guarantee. There are a wide variety of notions of privacy (e.g., "differential privacy", which captures the notion that no user should be lose his privacy appreciably by participating), and the goal is to investigate the possibilities and limitations of algorithms that maintain these notions of privacy whilst still giving us near-optimal solutions.

Data privacy is likely to be an increasing concern for all of us, and it is important that we bring computational thinking to bear on this problem, so that we can develop new rigorous approaches to identify and tackle the many challenges that arise here.

Papers

Differentially Private Approximation Algorithms
Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, Kunal Talwar
August 14, 2009