Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates

We study convex optimization problems under differential privacy (DP). With heavy-tailed gradients, existing works achieve suboptimal rates. The main obstacle is that existing gradient estimators have suboptimal tail properties, resulting in a superfluous factor of d in the union bound. In this paper, we explore algorithms achieving optimal rates of DP optimization with heavy-tailed gradients. Our first method is a simple clipping approach. Under bounded p-th order moments of gradients, with n samples, it achieves Õ(√d/n+√d(√d/nε)1-1/p) population risk with ε≤ 1/√d. We then propose an iterative updating method, which is more complex but achieves this rate for all ε≤ 1. The results significantly improve over existing methods. Such improvement relies on a careful treatment of the tail behavior of gradient estimators. Our results match the minimax lower bound in {kamath2022improved}, indicating that the theoretical limit of stochastic convex optimization under DP is achievable.