  We introduce new algorithms and convergence guarantees for privacy-preserving
non-convex Empirical Risk Minimization (ERM) on smooth $d$-dimensional
objectives. We develop an improved sensitivity analysis of stochastic gradient
descent on smooth objectives that exploits the recurrence of examples in
different epochs. By combining this new approach with recent analysis of
momentum with private aggregation techniques, we provide an
$(\epsilon,\delta)$-differential private algorithm that finds a gradient of
norm $\tilde O\left(\frac{d^{1/3}}{(\epsilon N)^{2/3}}\right)$ in
$O\left(\frac{N^{7/3}\epsilon^{4/3}}{d^{2/3}}\right)$ gradient evaluations,
improving the previous best gradient bound of $\tilde
O\left(\frac{d^{1/4}}{\sqrt{\epsilon N}}\right)$.
