Differentially Private Stochastic Optimization: New Results in Convex
  and Non-Convex Settings
  We study differentially private stochastic optimization in convex and
non-convex settings. For the convex case, we focus on the family of non-smooth
generalized linear losses (GLLs). Our algorithm for the $\ell_2$ setting
achieves optimal excess population risk in near-linear time, while the best
known differentially private algorithms for general convex losses run in
super-linear time. Our algorithm for the $\ell_1$ setting has nearly-optimal
excess population risk
$\tilde{O}\big(\sqrt{\frac{\log{d}}{n\varepsilon}}\big)$, and circumvents the
dimension dependent lower bound of \cite{Asi:2021} for general non-smooth
convex losses. In the differentially private non-convex setting, we provide
several new algorithms for approximating stationary points of the population
risk. For the $\ell_1$-case with smooth losses and polyhedral constraint, we
provide the first nearly dimension independent rate, $\tilde
O\big(\frac{\log^{2/3}{d}}{{(n\varepsilon)^{1/3}}}\big)$ in linear time. For
the constrained $\ell_2$-case with smooth losses, we obtain a linear-time
algorithm with rate $\tilde
O\big(\frac{1}{n^{1/3}}+\frac{d^{1/5}}{(n\varepsilon)^{2/5}}\big)$. Finally,
for the $\ell_2$-case we provide the first method for {\em non-smooth weakly
convex} stochastic optimization with rate $\tilde
O\big(\frac{1}{n^{1/4}}+\frac{d^{1/6}}{(n\varepsilon)^{1/3}}\big)$ which
matches the best existing non-private algorithm when $d= O(\sqrt{n})$. We also
extend all our results above for the non-convex $\ell_2$ setting to the
$\ell_p$ setting, where $1 < p \leq 2$, with only polylogarithmic (in the
dimension) overhead in the rates.
