Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates
<|reference_start|>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 $\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.<|reference_end|>
@article{zhao2024differential,
    title={Differential Private Stochastic Optimization with Heavy-tailed Data:
  Towards Optimal Rates},
    author={Puning Zhao, Jiafei Wu, Zhe Liu, Chong Wang, Rongfei Fan, Qingming Li},
    journal={arXiv preprint arXiv:2408.09891},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.09891},
    primaryClass={cs.LG cs.CR cs.DS}
}