# Private Query Release Assisted by Public Data

arXiv: https://arxiv.org/abs/2004.10941 · HTML: https://mlsanity.com/paper/2004.10941/

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Apr 2020.

## Built on by (most cited first, 27 of 27)

- [Differentially Private Fine-tuning of Language Models](https://mlsanity.com/paper/2110.06500/) (2021)
- [Iterative Methods for Private Synthetic Data: Unifying Framework and New Methods](https://mlsanity.com/paper/2106.07153/) (2021)
- [Public Data-Assisted Mirror Descent for Private Model Training](https://mlsanity.com/paper/2112.00193/) (2021)
- [Leveraging Public Data for Practical Private Query Release](https://mlsanity.com/paper/2102.08598/) (2021)
- [Why Is Public Pretraining Necessary for Private Model Training?](https://mlsanity.com/paper/2302.09483/) (2023)
- [Private Estimation with Public Data](https://mlsanity.com/paper/2208.07984/) (2022)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [Selective Pre-training for Private Fine-tuning](https://mlsanity.com/paper/2305.13865/) (2023)
- [Privately Learning Subspaces](https://mlsanity.com/paper/2106.00001/) (2021)
- [Private Distribution Learning with Public Data: The View from Sample Compression](https://mlsanity.com/paper/2308.06239/) (2023)
- [Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes](https://mlsanity.com/paper/2307.07604/) (2023)
- [Joint Selection: Adaptively Incorporating Public Information for Private Synthetic Data](https://mlsanity.com/paper/2403.07797/) (2024)
- [Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Free](https://mlsanity.com/paper/2305.09668/) (2023)
- [Mean Estimation Under Heterogeneous Privacy Demands](https://mlsanity.com/paper/2310.13137/) (2023)
- [Oracle-Efficient Differentially Private Learning with Public Data](https://mlsanity.com/paper/2402.09483/) (2024)
- [Public-data Assisted Private Stochastic Optimization: Power and Limitations](https://mlsanity.com/paper/2403.03856/) (2024)
- [On the Benefits of Public Representations for Private Transfer Learning under Distribution Shift](https://mlsanity.com/paper/2312.15551/) (2023)
- [Can Membership Inferencing be Refuted?](https://mlsanity.com/paper/2303.03648/) (2023)
- [Private Domain Adaptation from a Public Source](https://mlsanity.com/paper/2208.06135/) (2022)
- [Credit Attribution and Stable Compression](https://mlsanity.com/paper/2406.15916/) (2024)
- [Locally Private Sampling with Public Data](https://mlsanity.com/paper/2411.08791/) (2024)
- [PCDP-SGD: Improving the Convergence of Differentially Private SGD via Projection in Advance](https://mlsanity.com/paper/2312.03792/) (2023)
- [Private Estimation when Data and Privacy Demands are Correlated](https://mlsanity.com/paper/2407.11274/) (2024)
- [Managing Correlations in Data and Privacy Demand](https://mlsanity.com/paper/2509.02856/) (2025)
- [Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness](https://mlsanity.com/paper/2602.20585/) (2026)
- [Differentially Private Domain Adaptation with Theoretical Guarantees](https://mlsanity.com/paper/2306.08838/) (2023)
- [Lower Bounds for Public-Private Learning under Distribution Shift](https://mlsanity.com/paper/2507.17895/) (2025)

## Abstract (arXiv)

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 H of statistical queries with error no more than α 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 H of finite VC-dimension using only d/α public samples and √pd3/2/α2 private samples, where d and p are the VC-dimension and dual VC-dimension of 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/α2 is needed. Next, we give sample complexity lower bounds that exhibit tight dependence on p and α. For the class of decision stumps, we give a lower bound of √p/α on the private sample complexity whenever the public sample size is less than 1/α2. Given our upper bounds, this shows that the dependence on √p is necessary in the private sample complexity. We also give a lower bound of 1/α on the public sample complexity for a broad family of query classes, which by our upper bound, is tight in α.