# Differentially Private Nonparametric Regression Under a Growth Condition

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 52 references that are in the map.
- First posted on arXiv 24 Nov 2021.

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

- [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014)
- [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)
- [Private Learning and Sanitization: Pure vs. Approximate Differential Privacy](https://mlsanity.com/paper/1407.2674/) (2014)
- [Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain](https://mlsanity.com/paper/1803.02596/) (2018)
- [Differentially Private Release and Learning of Threshold Functions](https://mlsanity.com/paper/1504.07553/) (2015)
- [Simultaneous Private Learning of Multiple Concepts](https://mlsanity.com/paper/1511.08552/) (2015)
- [Differentially Private Simple Linear Regression](https://mlsanity.com/paper/2007.05157/) (2020)
- [Differentially Private Clustering: Tight Approximation Ratios](https://mlsanity.com/paper/2008.08007/) (2020)
- [Sample Complexity Bounds on Differentially Private Learning via Communication Complexity](https://mlsanity.com/paper/1402.6278/) (2014)
- [Privately Learning Thresholds: Closing the Exponential Gap](https://mlsanity.com/paper/1911.10137/) (2019)
- [On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities](https://mlsanity.com/paper/1510.03925/) (2015)
- [Differentially Private Bayesian Linear Regression](https://mlsanity.com/paper/1910.13153/) (2019)
- [On the Equivalence between Online and Private Learnability beyond Binary Classification](https://mlsanity.com/paper/2006.01980/) (2020)
- [Contextual bandits with surrogate losses: Margin bounds and efficient algorithms](https://mlsanity.com/paper/1806.10745/) (2018)
- [A Computational Separation between Private Learning and Online Learning](https://mlsanity.com/paper/2007.05665/) (2020)
- [How to Use Heuristics for Differential Privacy](https://mlsanity.com/paper/1811.07765/) (2018)

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

- [Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization](https://mlsanity.com/paper/2303.12921/) (2023)
- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes](https://mlsanity.com/paper/2211.09101/) (2022)

## Abstract (arXiv)

Given a real-valued hypothesis class H, we investigate under what conditions there is a differentially private algorithm which learns an optimal hypothesis from H given i.i.d. data. Inspired by recent results for the related setting of binary classification (Alon et al., 2019; Bun et al., 2020), where it was shown that online learnability of a binary class is necessary and sufficient for its private learnability, Jung et al. (2020) showed that in the setting of regression, online learnability of H is necessary for private learnability. Here online learnability of H is characterized by the finiteness of its η-sequential fat shattering dimension, rm sfatη(H), for all η > 0. In terms of sufficient conditions for private learnability, Jung et al. (2020) showed that H is privately learnable if limη downarrow 0 rm sfatη(H) is finite, which is a fairly restrictive condition. We show that under the relaxed condition lim infη downarrow 0 η · rm sfatη(H) = 0, H is privately learnable, establishing the first nonparametric private learnability guarantee for classes H with rm sfatη(H) diverging as η downarrow 0. Our techniques involve a novel filtering procedure to output stable hypotheses for nonparametric function classes.