Momentum Aggregation for Private Non-convex ERM
This work addresses privacy concerns in machine learning for non-convex optimization, offering incremental improvements in efficiency for differential privacy algorithms.
The paper tackles the problem of privacy-preserving non-convex Empirical Risk Minimization by introducing new algorithms that improve convergence guarantees, achieving a gradient norm bound of ̃O(d^{1/3}/(εN)^{2/3}) compared to the previous best of ̃O(d^{1/4}/√(εN)).
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 $(ε,δ)$-differential private algorithm that finds a gradient of norm $\tilde O\left(\frac{d^{1/3}}{(εN)^{2/3}}\right)$ in $O\left(\frac{N^{7/3}ε^{4/3}}{d^{2/3}}\right)$ gradient evaluations, improving the previous best gradient bound of $\tilde O\left(\frac{d^{1/4}}{\sqrt{εN}}\right)$.