Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps

Understand

We study the differentially private Empirical Risk Minimization (ERM) and Stochastic Convex Optimization (SCO) problems for non-smooth convex functions.

• We get a (nearly) optimal bound on the excess empirical risk and excess population loss with subquadratic gradient complexity.
• More precisely, our differentially private algorithm requires $O(\frac{N^{3/2}}{d^{1/8}}+ \frac{N^2}{d})$ gradient queries for optimal excess empirical risk, which is achieved with the help of subsampling and smoothing the function via convolution.
• This is the first subquadratic algorithm for the non-smooth case when $d$ is super constant.