# Privately Answering Classification Queries in the Agnostic PAC Model

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jul 2019.

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

- [Differentially Private Fine-tuning of Language Models](https://mlsanity.com/paper/2110.06500/) (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)
- [Private Estimation with Public Data](https://mlsanity.com/paper/2208.07984/) (2022)
- [Private Distribution Learning with Public Data: The View from Sample Compression](https://mlsanity.com/paper/2308.06239/) (2023)
- [Certification for Differentially Private Prediction in Gradient-Based Training](https://mlsanity.com/paper/2406.13433/) (2024)
- [Unbounded Differentially Private Quantile and Maximum Estimation](https://mlsanity.com/paper/2305.01177/) (2023)
- [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)
- [Private Everlasting Prediction](https://mlsanity.com/paper/2305.09579/) (2023)
- [Private Domain Adaptation from a Public Source](https://mlsanity.com/paper/2208.06135/) (2022)
- [Private Truly-Everlasting Robust-Prediction](https://mlsanity.com/paper/2401.04311/) (2024)
- [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)
- [Differentially Private Domain Adaptation with Theoretical Guarantees](https://mlsanity.com/paper/2306.08838/) (2023)
- [Enhancing Differentially Private Linear Regression via Public Second-Moment](https://mlsanity.com/paper/2508.18037/) (2025)
- [Private Prediction via Shrinkage](https://mlsanity.com/paper/2602.05219/) (2026)
- [Differentially Private Truncation of Unbounded Data via Public Second Moments](https://mlsanity.com/paper/2602.22282/) (2026)

## Abstract (arXiv)

We revisit the problem of differentially private release of classification queries. In this problem, the goal is to design an algorithm that can accurately answer a sequence of classification queries based on a private training set while ensuring differential privacy. We formally study this problem in the agnostic PAC model and derive a new upper bound on the private sample complexity. Our results improve over those obtained in a recent work [BTT18] for the agnostic PAC setting. In particular, we give an improved construction that yields a tighter upper bound on the sample complexity. Moreover, unlike [BTT18], our accuracy guarantee does not involve any blow-up in the approximation error associated with the given hypothesis class. Given any hypothesis class with VC-dimension d, we show that our construction can privately answer up to m classification queries with average excess error α using a private sample of size ≈ fracdα2,maxleft(1, √m,α3/2right). Using recent results on private learning with auxiliary public data, we extend our construction to show that one can privately answer any number of classification queries with average excess error α using a private sample of size ≈ fracdα2,maxleft(1, √d,αright). When α=Oleft(frac1√dright), our private sample complexity bound is essentially optimal.