Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913471907495936 |
|---|---|
| author | Zhao, Puning Wu, Jiafei Liu, Zhe Wang, Chong Fan, Rongfei Li, Qingming |
| author_facet | Zhao, Puning Wu, Jiafei Liu, Zhe Wang, Chong Fan, Rongfei Li, Qingming |
| contents | 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ε)^{1-1/p})$ population risk with $ε\leq 1/\sqrt{d}$. We then propose an iterative updating method, which is more complex but achieves this rate for all $ε\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_09891 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates Zhao, Puning Wu, Jiafei Liu, Zhe Wang, Chong Fan, Rongfei Li, Qingming Machine Learning Cryptography and Security Data Structures and Algorithms 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ε)^{1-1/p})$ population risk with $ε\leq 1/\sqrt{d}$. We then propose an iterative updating method, which is more complex but achieves this rate for all $ε\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. |
| title | Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates |
| topic | Machine Learning Cryptography and Security Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.09891 |