Faster Differentially Private Convex Optimization via Second-Order Methods

Differentially private (stochastic) gradient descent is the workhorse of differentially private machine learning in both the convex and non-convex settings. Without privacy constraints, second-order methods, like Newton's method, converge faster than first-order methods like gradient descent. In this work, we investigate the prospect of using the second-order information of loss function to accelerate differentially private convex optimization. We first develop a private variant of the regularized cubic Newton method of Nesterov and Polyak [NP06] for the class of strongly convex loss functions. We show that our algorithm achieves the optimal excess loss and attains the same (optimal) rate of convergence as its non-private counterparts. We then design a practical second-order DP algorithm for the unconstrained logistic regression problem. We empirically study the performance of our algorithm. We show that our algorithm almost always achieves the best excess loss for a wide range of ε ∈ [0.01, 10] on many challenging datasets. Furthermore, the run-time of our algorithm is 10×-40× faster than DPGD.