Timezone: »

 
Poster
Private Isotonic Regression
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi

Wed Nov 30 02:00 PM -- 04:00 PM (PST) @ Hall J #826
in Poster Session 4 »
In this paper, we consider the problem of differentially private (DP) algorithms for isotonic regression. For the most general problem of isotonic regression over a partially ordered set (poset) $\mathcal{X}$ and for any Lipschitz loss function, we obtain a pure-DP algorithm that, given $n$ input points, has an expected excess empirical risk of roughly $\mathrm{width}(\mathcal{X}) \cdot \log|\mathcal{X}| / n$, where $\mathrm{width}(\mathcal{X})$ is the width of the poset. In contrast, we also obtain a near-matching lower bound of roughly $(\mathrm{width}(\mathcal{X}) + \log |\mathcal{X}|) / n$, that holds even for approximate-DP algorithms. Moreover, we show that the above bounds are essentially the best that can be obtained without utilizing any further structure of the poset.In the special case of a totally ordered set and for $\ell_1$ and $\ell_2^2$ losses, our algorithm can be implemented in near-linear running time; we also provide extensions of this algorithm to the problem of private isotonic regression with additional structural constraints on the output function.
Keywords: differential privacy · isotonic regression · posets
[ Paper]  [ Poster]  [ OpenReview]  [ Topia] 

Author Information

Badih Ghazi (Google)
Pritish Kamath (Google Research)
Ravi Kumar (Google)
Pasin Manurangsi (Google)

More from the Same Authors