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 Õ(pd/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, indicating that the theoretical limit of stochastic convex optimization under DP is achievable.