Lower Bounds for Differentially Private ERM: Unconstrained and
  Non-Euclidean
  We consider the lower bounds of differentially private empirical risk
minimization (DP-ERM) for convex functions in constrained/unconstrained cases
with respect to 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 which can generalize lower
bounds in constrained case to unconstrained case. For $(\epsilon,\delta)$-DP,
we achieve $\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 introducing a novel biased mean property for fingerprinting codes,
where $n$ is the size of the data-set and $d$ is the dimension.
