# Private Realizable-to-Agnostic Transformation with Near-Optimal Sample Complexity

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 34 references that are in the map.
- First posted on arXiv 1 Oct 2025.

## Builds on (most cited first, 16 of 16)

- [Preserving Statistical Validity in Adaptive Data Analysis](https://mlsanity.com/paper/1411.2664/) (2014)
- [Algorithmic Stability for Adaptive Data Analysis](https://mlsanity.com/paper/1511.02513/) (2015)
- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [An Equivalence Between Private Classification and Online Prediction](https://mlsanity.com/paper/2003.00563/) (2020)
- [Differentially Private Release and Learning of Threshold Functions](https://mlsanity.com/paper/1504.07553/) (2015)
- [Privacy-preserving Prediction](https://mlsanity.com/paper/1803.10266/) (2018)
- [A New Analysis of Differential Privacy's Generalization Guarantees](https://mlsanity.com/paper/1909.03577/) (2019)
- [Sample Complexity Bounds on Differentially Private Learning via Communication Complexity](https://mlsanity.com/paper/1402.6278/) (2014)
- [Sample-efficient proper PAC learning with approximate differential privacy](https://mlsanity.com/paper/2012.03893/) (2020)
- [Max-Information, Differential Privacy, and Post-Selection Hypothesis Testing](https://mlsanity.com/paper/1604.03924/) (2016)
- [Generalization for Adaptively-chosen Estimators via Stable Median](https://mlsanity.com/paper/1706.05069/) (2017)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [Closure Properties for Private Classification and Online Prediction](https://mlsanity.com/paper/2003.04509/) (2020)
- [Learning Privately with Labeled and Unlabeled Examples](https://mlsanity.com/paper/1407.2662/) (2014)
- [PAC learning with stable and private predictions](https://mlsanity.com/paper/1911.10541/) (2019)
- [Improved Bounds for Pure Private Agnostic Learning: Item-Level and User-Level Privacy](https://mlsanity.com/paper/2407.20640/) (2024)

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

- [Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back](https://mlsanity.com/paper/2511.12659/) (2025)

## Abstract (arXiv)

The realizable-to-agnostic transformation (Beimel et al., 2015; Alon et al., 2020) provides a general mechanism to convert a private learner in the realizable setting (where the examples are labeled by some function in the concept class) to a private learner in the agnostic setting (where no assumptions are imposed on the data). Specifically, for any concept class C and error parameter α, a private realizable learner for C can be transformed into a private agnostic learner while only increasing the sample complexity by widetildeO(VC(C)/α2), which is essentially tight assuming a constant privacy parameter varepsilon = Theta(1). However, when varepsilon can be arbitrary, one has to apply the standard privacy-amplification-by-subsampling technique (Kasiviswanathan et al., 2011), resulting in a suboptimal extra sample complexity of widetildeO(VC(C)/α2varepsilon) that involves a 1/varepsilon factor. In this work, we give an improved construction that eliminates the dependence on varepsilon, thereby achieving a near-optimal extra sample complexity of widetildeO(VC(C)/α2) for any varepsilon≤ 1. Moreover, our result reveals that in private agnostic learning, the privacy cost is only significant for the realizable part. We also leverage our technique to obtain a nearly tight sample complexity bound for the private prediction problem, resolving an open question posed by Dwork and Feldman (2018) and Dagan and Feldman (2020).