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 $\tilde{O}(\sqrt{d/n}+\sqrt{d}(\sqrt{d}/n\epsilon)^{1-1/p})$ population risk with $\epsilon\leq 1/\sqrt{d}$. We then propose an iterative updating method, which is more complex but achieves this rate for all $\epsilon\leq 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 \cite{kamath2022improved}, indicating that the theoretical limit of stochastic convex optimization under DP is achievable.

本研究针对在差分隐私框架下的凸优化问题，解决了已有研究在重尾梯度条件下达到的次优速率问题。我们提出了一种简单的剪裁方法和一种迭代更新方法，显著改进了梯度估计器的尾部特性，从而实现了最优的DP优化速率，匹配了现有的最小最大下界，表明在差分隐私下的随机凸优化的理论极限是可达的。

重尾数据下的差分隐私随机优化：朝向最优速率