Accuracy First: Selecting a Differential Privacy Level for
  Accuracy-Constrained ERM
  Traditional approaches to differential privacy assume a fixed privacy
requirement $\epsilon$ for a computation, and attempt to maximize the accuracy
of the computation subject to the privacy constraint. As differential privacy
is increasingly deployed in practical settings, it may often be that there is
instead a fixed accuracy requirement for a given computation and the data
analyst would like to maximize the privacy of the computation subject to the
accuracy constraint. This raises the question of how to find and run a
maximally private empirical risk minimizer subject to a given accuracy
requirement. We propose a general "noise reduction" framework that can apply to
a variety of private empirical risk minimization (ERM) algorithms, using them
to "search" the space of privacy levels to find the empirically strongest one
that meets the accuracy constraint, incurring only logarithmic overhead in the
number of privacy levels searched. The privacy analysis of our algorithm leads
naturally to a version of differential privacy where the privacy parameters are
dependent on the data, which we term ex-post privacy, and which is related to
the recently introduced notion of privacy odometers. We also give an ex-post
privacy analysis of the classical AboveThreshold privacy tool, modifying it to
allow for queries chosen depending on the database. Finally, we apply our
approach to two common objectives, regularized linear and logistic regression,
and empirically compare our noise reduction methods to (i) inverting the
theoretical utility guarantees of standard private ERM algorithms and (ii) a
stronger, empirical baseline based on binary search.
