Differentially Private Nonparametric Regression Under a Growth Condition
Not on the map. Why?
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.
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
17 of 52 references.
References · 17
- 2014Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Boundscited by 107
- 2018Private PAC learning implies finite Littlestone dimensioncited by 74
- 2020An Equivalence Between Private Classification and Online Predictioncited by 64
- 2014Private Learning and Sanitization: Pure vs. Approximate Differential Privacycited by 63
- 2018Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domaincited by 61
- 2015Differentially Private Release and Learning of Threshold Functionscited by 60
- 2015Simultaneous Private Learning of Multiple Conceptscited by 34
- 2020Differentially Private Simple Linear Regressioncited by 34
- 2020Differentially Private Clustering: Tight Approximation Ratioscited by 34
- 2014Sample Complexity Bounds on Differentially Private Learning via Communication Complexitycited by 31
- 2019Privately Learning Thresholds: Closing the Exponential Gapcited by 31
- 2015On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalitiescited by 27
5 more
- 2019Differentially Private Bayesian Linear Regressioncited by 24
- 2020On the Equivalence between Online and Private Learnability beyond Binary Classificationcited by 12
- 2018Contextual bandits with surrogate losses: Margin bounds and efficient algorithmscited by 10
- 2020A Computational Separation between Private Learning and Online Learningcited by 8
- 2018How to Use Heuristics for Differential Privacycited by 6
Built on by
Citing papers per year: 2022: 1; 2023: 2.
3 papers.