Faster Differentially Private Convex Optimization via Second-Order Methods

We first develop a private variant of the regularized cubic Newton method of Nesterov and Polyak [NP06], and show that for the class of strongly convex loss functions, our algorithm has quadratic convergence and achieves the optimal excess loss.