Private Query Release Assisted by Public Data

By Raef Bassily, Albert Cheu, Shay Moran, Aleksandar Nikolov, Jonathan Ullman, Zhiwei Steven Wu. 2020

53 citations recorded by the source corpus.

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. First, we show that we can solve the problem for any query class $\mathcal{H}$ of finite VC-dimension using only $d/\alpha$ public samples and $\sqrt{p}d^{3/2}/\alpha^2$ private samples, where $d$ and $p$ are the VC-dimension and dual VC-dimension of $\mathcal{H}$, respectively. In comparison, with only private samples, this problem cannot be solved even for simple query classes with VC-dimension one, and without any private samples, a larger public sample of size $d/\alpha^2$ is needed. Next, we give sample complexity lower bounds that exhibit tight dependence on $p$ and $\alpha$. For the class of decision stumps, we give a lower bound of $\sqrt{p}/\alpha$ on the private sample complexity whenever the public sample size is less than $1/\alpha^2$. Given our upper bounds, this shows that the dependence on $\sqrt{p}$ is necessary in the private sample complexity. We also give a lower bound of $1/\alpha$ on the public sample complexity for a broad family of query classes, which by our upper bound, is tight in $\alpha$.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

The Power of the Hybrid Model for Mean Estimation (2018, background): “Recently, theoretical works [9, 10] have explored the limits of this model’s power via lower bounds on the sample complexity of fundamental statistical problems.”
Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification (2020, methodology): “To implement this subroutine, we follow a long line of work that studies private data analysis with access to an auxiliary public dataset Sh drawn from the same distribution P , for which we don’t need to provide formal privacy guarantee [2, 3, 5, 16, 28].”
Differentially Private Fine-tuning of Language Models (2021, background): “Finally, other works (both theoretical and experimental) investigate the role of public data in private query release, synthetic data generation, and prediction (Ji & Elkan, 2013; Beimel et al., 2016; Alon et al., 2019; Nandi & Bassily, 2020; Bassily et al., 2020a;b; Liu et al., 2021).”
FedBE: Making Bayesian Model Ensemble Applicable to Federated Learning (2020, background): “Bassily et al. (2020a;b) also showed real cases where public data is available in differential privacy.”