In this paper, we revisit the problem of Differentially Private Stochastic Convex Optimization (DP-SCO) with heavy-tailed data, where the gradient of the loss function has bounded moments. Instead of the case where the loss function is Lipschitz or each coordinate of the gradient has bounded second moment studied previously, we consider a relaxed scenario where each coordinate of the gradient only has bounded (1 + v)-th moment with some v ∈ (0, 1]. Firstly, we start from the one dimensional private mean estimation for heavy-tailed distributions. We propose a novel robust and private mean estimator which is optimal. Based on its idea, we then extend to the general d-dimensional space and study DP-SCO with general convex and strongly convex loss functions. We also provide lower bounds for these two classes of loss under our setting and show that our upper bounds are optimal up to a factor of O(Poly(d)). To address the high dimensionality issue, we also study DP-SCO with heavy-tailed gradient under some sparsity constraint (DP sparse learning). We propose a new method and show it is also optimal up to a factor of O(s∗), where s∗ is the underlying sparsity of the constraint.
|Original language||English (US)|
|Title of host publication||Proceedings of the 31st International Joint Conference on Artificial Intelligence, IJCAI 2022|
|Editors||Luc De Raedt, Luc De Raedt|
|Publisher||International Joint Conferences on Artificial Intelligence Organization|
|Number of pages||7|
|State||Published - 2022|
|Event||31st International Joint Conference on Artificial Intelligence, IJCAI 2022 - Vienna, Austria|
Duration: Jul 23 2022 → Jul 29 2022
|Name||IJCAI International Joint Conference on Artificial Intelligence|
|Conference||31st International Joint Conference on Artificial Intelligence, IJCAI 2022|
|Period||07/23/22 → 07/29/22|
Bibliographical noteFunding Information:
Di Wang and Yulian Wu were support in part by the baseline funding BAS/1/1689-01-01, funding from the CRG grand URF/1/4663-01-01 and funding from the AI Initiative REI/1/4811-10-01 of King Abdullah University of Science and Technology (KAUST). Xiuzhen Cheng and Youming Tao were partially supported by National Key R&D Program of China (No. 2019YFB2102600).
© 2022 International Joint Conferences on Artificial Intelligence. All rights reserved.
ASJC Scopus subject areas
- Artificial Intelligence