提升隐私保护下非光滑非凸优化的样本效率，关键突破在降低数据需求。
Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization
- 提出单遍和多遍隐私算法，用更少数据找近似最优解
- 多遍算法样本复杂度降低至 $\widetildeΩ\left(d/β^2 + d^{3/4}/εα^{1/2}β^{3/2}\right)$
- 适合关注隐私与计算效率平衡的机器学习研究者
我们研究针对随机与经验目标的差分隐私（DP）优化算法，这些目标既不光滑也不凸。本文提出方法可返回一个Goldstein-驻点，并实现比现有工作更优的样本复杂度。首先给出一种单遍$(ε,δ)$-DP算法，在数据集大小为$\widetildeΩ(\sqrt{d}/αβ^{3}+d/εαβ^{2})$时可返回$(α,β)$-驻点，相比Zhang等[2024]的方法减少$Ω(\sqrt{d})$倍。随后设计一种多遍多项式时间算法，将样本复杂度进一步降至$\widetildeΩ\left(d/β^2 + d^{3/4}/εα^{1/2}β^{3/2}\right)$，通过构造高效率的ERM算法，并证明Goldstein-驻点能从经验损失推广到总体损失。
原文摘要 · Abstract (English)
We study differentially private (DP) optimization algorithms for stochastic and empirical objectives which are neither smooth nor convex, and propose methods that return a Goldstein-stationary point with sample complexity bounds that improve on existing works. We start by providing a single-pass $(ε,δ)$-DP algorithm that returns an $(α,β)$-stationary point as long as the dataset is of size $\widetildeΩ(\sqrt{d}/αβ^{3}+d/εαβ^{2})$, which is $Ω(\sqrt{d})$ times smaller than the algorithm of Zhang et al. [2024] for this task, where $d$ is the dimension. We then provide a multi-pass polynomial time algorithm which further improves the sample complexity to $\widetildeΩ\left(d/β^2+d^{3/4}/εα^{1/2}β^{3/2}\right)$, by designing a sample efficient ERM algorithm, and proving that Goldstein-stationary points generalize from the empirical loss to the population loss.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。