Oracle Efficient Private Non-Convex Optimization
  One of the most effective algorithms for differentially private learning and
optimization is objective perturbation. This technique augments a given
optimization problem (e.g. deriving from an ERM problem) with a random linear
term, and then exactly solves it. However, to date, analyses of this approach
crucially rely on the convexity and smoothness of the objective function,
limiting its generality. We give two algorithms that extend this approach
substantially. The first algorithm requires nothing except boundedness of the
loss function, and operates over a discrete domain. Its privacy and accuracy
guarantees hold even without assuming convexity. This gives an oracle-efficient
optimization algorithm over arbitrary discrete domains that is comparable in
its generality to the exponential mechanism. The second algorithm operates over
a continuous domain and requires only that the loss function be bounded and
Lipschitz in its continuous parameter. Its privacy analysis does not require
convexity. Its accuracy analysis does require convexity, but does not require
second order conditions like smoothness. Even without convexity, this algorithm
can be generically used as an oracle-efficient optimization algorithm, with
accuracy evaluated empirically. We complement our theoretical results with an
empirical evaluation of the non-convex case, in which we use an integer program
solver as our optimization oracle. We find that for the problem of learning
linear classifiers, directly optimizing for 0/1 loss using our approach can
out-perform the more standard approach of privately optimizing a
convex-surrogate loss function on the Adult dataset.
