Lower Bounds for Differentially Private ERM: Unconstrained and Non-Euclidean

Zhou Lu, Daogao LiuICLR 2023 · OpenReview

Abstract

We consider the lower bounds of differentially private empirical risk minimization (DP-ERM) for convex functions in both constrained and unconstrained cases concerning the general $\ell_p$ norm beyond the $\ell_2$ norm considered by most of the previous works. We provide a simple black-box reduction approach that can generalize lower bounds in constrained to unconstrained cases. Moreover, for $(\epsilon,\delta)$-DP, we achieve the optimal $\Omega(\frac{\sqrt{d \log(1/\delta)}}{\epsilon n})$ lower bounds for both constrained and unconstrained cases and any $\ell_p$ geometry where $p\geq 1$ by considering $\ell_1$ loss over the $\ell_{\infty}$ ball.
BibTeX
@inproceedings{lu2023lower,
  author = {Zhou Lu and Daogao Liu},
  title = {{Lower Bounds for Differentially Private ERM: Unconstrained and Non-Euclidean}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=Jqas82UP428},
}

Loading related content...

Figure