We study the problem of Empirical Risk Minimization (ERM) with (smooth) nonconvex loss functions under the differentialprivacy (DP) model. Existing approaches for this problem mainly adopt gradient norms to measure the error, which in general cannot guarantee the quality of the solution. To address this issue, 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 bounded by $\tilde{O}(\frac{d\log (1/\delta)}{\log n\epsilon^2})$ in the $(\epsilon, \delta)$DP settings, where $n$ is the data size and $d$ is the dimensionality of the space. The $\frac{1}{\log n}$ term in the empirical risk bound can be further improved to $\frac{1}{n^{\Omega(1)}}$ (when $d$ is a constant) by a highly nontrivial analysis on the timeaverage 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 $n$ is large enough, there are $(\epsilon, \delta)$DP algorithms which can find an approximate local minimum of the empirical risk with high probability in both the constrained and nonconstrained settings. These results indicate that one can escape saddle points privately.
Author Information
Di Wang (State University of New York at Buffalo)
Changyou Chen (SUNY Buffalo)
Jinhui Xu (SUNY Buffalo)
Related Events (a corresponding poster, oral, or spotlight)

2019 Oral: Differentially Private Empirical Risk Minimization with Nonconvex Loss Functions »
Thu Jun 13th 09:20  09:25 AM Room Seaside Ballroom
More from the Same Authors

2019 Poster: On Sparse Linear Regression in the Local Differential Privacy Model »
Di Wang · Jinhui Xu 
2019 Oral: On Sparse Linear Regression in the Local Differential Privacy Model »
Di Wang · Jinhui Xu