提出更优的差分隐私非凸-强凹极小极大优化方法，提升隐私保护下的模型精度。
Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization
- 设计新算法降低梯度噪声方差，改进隐私边界
- 理论最优误差率达 $\tilde{O}(\frac{d^{1/3}}{(nε)^{2/3}})$
- 适用于深度学习中的AUC最大化等场景
本文研究差分隐私（DP）模型下的有限求和极小极大优化问题。针对以往多集中于凸-凹或满足Polyak-Lojasiewicz条件的情形，本文聚焦非凸-强凹设置，涵盖深度学习中如深度AUC最大化等模型。首先分析了差分隐私版随机梯度下降上升（SGDA），证明其可实现经验风险梯度的 $l_2$-范数上界为 $\tilde{O}(\frac{d^{1/4}}{(nε)^{1/2}})$，其中 $d$ 为模型维度，$n$ 为样本量。随后提出新方法，将上界改进至 $\tilde{O}(\frac{d^{1/3}}{(nε)^{2/3}})$，达到当前非凸损失下差分隐私经验风险最小化的最优已知率。同时讨论了若干私有极小极大优化的下界。实验基于真实世界数据，在AUC最大化、生成对抗网络及时序差分学习任务中验证了理论分析的有效性。
原文摘要 · Abstract (English)
In this paper, we study the problem of (finite sum) minimax optimization in the Differential Privacy (DP) model. Unlike most of the previous studies on the (strongly) convex-concave settings or loss functions satisfying the Polyak-Lojasiewicz condition, here we mainly focus on the nonconvex-strongly-concave one, which encapsulates many models in deep learning such as deep AUC maximization. Specifically, we first analyze a DP version of Stochastic Gradient Descent Ascent (SGDA) and show that it is possible to get a DP estimator whose $l_2$-norm of the gradient for the empirical risk function is upper bounded by $\tilde{O}(\frac{d^{1/4}}{({nε})^{1/2}})$, where $d$ is the model dimension and $n$ is the sample size. We then propose a new method with less gradient noise variance and improve the upper bound to $\tilde{O}(\frac{d^{1/3}}{(nε)^{2/3}})$, which matches the best-known result for DP Empirical Risk Minimization with non-convex loss. We also discussed several lower bounds of private minimax optimization. Finally, experiments on AUC maximization, generative adversarial networks, and temporal difference learning with real-world data support our theoretical analysis.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。