Differentially Private Empirical Risk Minimization with Non-convex Loss Functions

We study the problem of Empirical Risk Minimization (ERM) with (smooth) non-convex loss functions under the differential-privacy (DP) model. We first study the expected excess empirical (or population) risk, which was primarily used as the utility to measure the quality for convex loss functions. Specifically, we show that the excess empirical (or population) risk can be upper (formula presented) bounded by (formula presented)-DP settings, log (formula presented) is the data size and (formula presented) is the dimensionality of the space. The term in the empirical 1 log (formula presented)risk bound can be further improved to¹ (formula presented) is a constant) by a highly non-trivial analysis on the time-average error. To obtain more efficient solutions, we also consider the connection between achieving differential privacy and finding approximate local minimum. Particularly, we show that when the size (formula presented) is large enough, there are (formula presented)-DP algorithms which can find an approximate local minimum of the empirical risk with high probability in both the constrained and non-constrained settings. These results indicate that one can escape saddle points privately.