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 l(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 l(1) setting has nearly-optimal excess population risk (O) over tilde (root logd/n epsilon), and circumvents the dimension dependent lower bound of [AFKT21] 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 l1-case with smooth losses and polyhedral constraint, we provide the first nearly dimension independent rate, (O) over tilde (log2/3 d/(n epsilon)1/3) in linear time. For the constrained l(2)-case with smooth losses, we obtain a linear-time algorithm with rate (O) over tilde (1/n(1/3) + d(1/5)/(n epsilon)2/5) . Finally, for the l(2)-case we provide the first method for non-smooth weakly convex stochastic optimization with rate (O) over tilde (1/n(1/4) + d(1/6) (n epsilon)(1/3)) which matches the best existing non-private algorithm when d = O(root n). We also extend all our results above for the non-convex l(2) setting to the l p setting, where 1 < p <= 2, with only polylogarithmic (in the dimension) overhead in the rates.