在重尾梯度下实现纯ε差分隐私优化,达到最优风险率。
Optimal Rates for Pure $\varepsilon$-Differentially Private Stochastic Convex Optimization with Heavy Tails
- 基于损失函数的利普希茨扩展设计私有化优化框架。
- 在重尾条件下,实现与理论极限接近的最优误差率。
- 适用于损失函数无界的情况,适合高维结构化问题研究者。
我们研究了在纯ε-差分隐私(DP)约束下,具有重尾梯度的随机凸优化(SCO)。不同于以往假设损失函数的最坏情况利普希茨参数有界,本文仅假设损失的k阶矩有界,从而允许梯度分布无界且重尾,可得到更紧的过剩风险上界。已有工作已刻画ρ-零集中差分隐私(ρ-ZCDP)情形下的最小最大最优率,但纯ε-DP情形仍为开放问题。本文首次在该设置下刻画了纯ε-DP重尾SCO的最小最大过剩风险率(至对数因子),并提出一个在高概率下多项式时间内收敛的算法。当最坏情况利普希茨参数多项式有界时,该算法可确定性地运行于多项式时间。对于重要结构化问题类别——包括欧氏球、椭球和多面体上的铰链/ReLU型损失与绝对值损失——即使最坏情况利普希茨参数无穷大,亦能实现确定性多项式时间。我们的方法基于一种新颖的私有化优化利普希茨扩展的框架,并给出了几乎匹配的高概率下界。
原文摘要 · Abstract (English)
We study stochastic convex optimization (SCO) with heavy-tailed gradients under pure $\varepsilon$-differential privacy (DP). Instead of assuming a bound on the worst-case Lipschitz parameter of the loss, we assume only a bounded $k$-th moment. This assumption allows for unbounded, heavy-tailed stochastic gradient distributions, and can yield sharper excess risk bounds. Prior work characterized the minimax optimal rate for $ρ$-zero-concentrated DP SCO up to logarithmic factors in this setting, but the pure $\varepsilon$-DP case has remained open. We characterize the minimax optimal excess-risk rate for pure $\varepsilon$-DP heavy-tailed SCO up to logarithmic factors. Our algorithm achieves this rate in polynomial time with high probability. Moreover, it runs in deterministic polynomial time when the worst-case Lipschitz parameter is polynomially bounded. For important structured problem classes -- including hinge/ReLU-type and absolute-value losses on Euclidean balls, ellipsoids, and polytopes -- we achieve deterministic polynomial time even when the worst-case Lipschitz parameter is infinite. Our approach is based on a novel framework for privately optimizing Lipschitz extensions of the empirical loss. We complement our upper bound with a nearly matching high-probability lower bound.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。