Abstract
While many solutions for privacy-preserving convex empirical riskminimization (ERM) have been developed, privacy-preserving nonconvex ERMremains a challenge. We study nonconvex ERM, which takes the form of minimizinga finite-sum of nonconvex loss functions over a training set. We propose a newdifferentially private stochastic gradient descent algorithm for nonconvex ERMthat achieves strong privacy guarantees efficiently, and provide a tightanalysis of its privacy and utility guarantees, as well as its gradientcomplexity. Our algorithm substantially reduces gradient complexity whilematching the best previous utility guarantee given by Wang et al. (2017). Weextend our algorithm to the distributed setting using secure multi-partycomputation, and show it is possible for a distributed algorithm to match theprivacy and utility guarantees of a centralized algorithm in this setting. Ourexperiments on benchmark nonconvex ERM problems demonstrate superiorperformance in terms of both training cost and utility gains compared withprevious differentially private methods using the same privacy budgets.