Timezone: »
Poster
Private Query Release Assisted by Public Data
Raef Bassily · Albert Cheu · Shay Moran · Aleksandar Nikolov · Jonathan Ullman · Steven Wu
Wed Jul 15 05:00 AM -- 05:45 AM & Wed Jul 15 04:00 PM -- 04:45 PM (PDT) @ None #None
We study the problem of differentially private query release assisted by access to public data. In this problem, the goal is to answer a large class $\mathcal{H}$ of statistical queries with error no more than $\alpha$ using a combination of public and private samples. The algorithm is required to satisfy differential privacy only with respect to the private samples. We study the limits of this task in terms of the private and public sample complexities. Our upper and lower bounds on the private sample complexity have matching dependence on the dual VC-dimension of $\mathcal{H}$. For a large category of query classes, our bounds on the public sample complexity have matching dependence on $\alpha$.
Author Information
Raef Bassily (The Ohio State University)
Albert Cheu (Northeastern University)
Shay Moran (IAS, Princeton)
Sasho Nikolov (University of Toronto)
Jonathan Ullman (Northeastern University)
Steven Wu (University of Minnesota)
More from the Same Authors
-
2020 Poster: New Oracle-Efficient Algorithms for Private Synthetic Data Release »
Giuseppe Vietri · Grace Tian · Mark Bun · Thomas Steinke · Steven Wu -
2020 Poster: Structured Linear Contextual Bandits: A Sharp and Geometric Smoothed Analysis »
Vidyashankar Sivakumar · Steven Wu · Arindam Banerjee -
2020 Poster: Privately Learning Markov Random Fields »
Huanyu Zhang · Gautam Kamath · Janardhan Kulkarni · Steven Wu -
2020 Poster: Oracle Efficient Private Non-Convex Optimization »
Seth Neel · Aaron Roth · Giuseppe Vietri · Steven Wu -
2020 Poster: Private Reinforcement Learning with PAC and Regret Guarantees »
Giuseppe Vietri · Borja de Balle Pigem · Akshay Krishnamurthy · Steven Wu -
2019 Poster: Fair Regression: Quantitative Definitions and Reduction-Based Algorithms »
Alekh Agarwal · Miroslav Dudik · Steven Wu -
2019 Poster: Differentially Private Fair Learning »
Matthew Jagielski · Michael Kearns · Jieming Mao · Alina Oprea · Aaron Roth · Saeed Sharifi-Malvajerdi · Jonathan Ullman -
2019 Oral: Differentially Private Fair Learning »
Matthew Jagielski · Michael Kearns · Jieming Mao · Alina Oprea · Aaron Roth · Saeed Sharifi-Malvajerdi · Jonathan Ullman -
2019 Oral: Fair Regression: Quantitative Definitions and Reduction-Based Algorithms »
Alekh Agarwal · Miroslav Dudik · Steven Wu -
2019 Poster: Orthogonal Random Forest for Causal Inference »
Miruna Oprescu · Vasilis Syrgkanis · Steven Wu -
2019 Oral: Orthogonal Random Forest for Causal Inference »
Miruna Oprescu · Vasilis Syrgkanis · Steven Wu -
2019 Poster: Locally Private Bayesian Inference for Count Models »
Aaron Schein · Steven Wu · Alexandra Schofield · Mingyuan Zhou · Hanna Wallach -
2019 Oral: Locally Private Bayesian Inference for Count Models »
Aaron Schein · Steven Wu · Alexandra Schofield · Mingyuan Zhou · Hanna Wallach