Differentially Private Nonparametric Regression Under a Growth Condition
This work addresses the challenge of ensuring privacy in machine learning for regression tasks, providing a theoretical foundation for broader applicability beyond restrictive conditions, though it is incremental in extending prior results.
The paper tackles the problem of differentially private nonparametric regression by establishing that a class is privately learnable under a relaxed growth condition, specifically when the limit inferior of η times the sequential fat shattering dimension approaches zero, which is the first such guarantee for classes with diverging dimensions.
Given a real-valued hypothesis class $\mathcal{H}$, we investigate under what conditions there is a differentially private algorithm which learns an optimal hypothesis from $\mathcal{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 $\mathcal{H}$ is necessary for private learnability. Here online learnability of $\mathcal{H}$ is characterized by the finiteness of its $η$-sequential fat shattering dimension, ${\rm sfat}_η(\mathcal{H})$, for all $η> 0$. In terms of sufficient conditions for private learnability, Jung et al. (2020) showed that $\mathcal{H}$ is privately learnable if $\lim_{η\downarrow 0} {\rm sfat}_η(\mathcal{H})$ is finite, which is a fairly restrictive condition. We show that under the relaxed condition $\lim \inf_{η\downarrow 0} η\cdot {\rm sfat}_η(\mathcal{H}) = 0$, $\mathcal{H}$ is privately learnable, establishing the first nonparametric private learnability guarantee for classes $\mathcal{H}$ with ${\rm sfat}_η(\mathcal{H})$ diverging as $η\downarrow 0$. Our techniques involve a novel filtering procedure to output stable hypotheses for nonparametric function classes.