Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps - Kulkarni, Janardhan (Jana); Tat Lee, Yin; Liu, Daogao (NeurIPS 2021, 2021)
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([N^[3/2]][d^[1/8]]+ [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. As a direct application, using the iterative localization approach of Feldman et al. [fkt20], we achieve the optimal excess population loss for stochastic convex optimization problem, with O(\[N^[5/4]d^[1/8],[ N^[3/2]][d^[1/8]]\]) gradient queries. Our work makes progress towards resolving a question raised by Bassily et al. [bfgt20], giving first algorithms for private ERM and SCO with subquadratic steps. We note that independently Asi et al. [afkt21] gave other algorithms for private ERM and SCO with subquadratic steps.