在隐私保护下,突破传统光滑性限制,实现更优的优化性能。
Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Condition
- 基于Tsybakov噪声条件,放宽对损失函数光滑性的要求。
- 在小隐私预算下,仍保持与样本量、维度相关的最优误差界。
- 适用于梯度高阶矩有界的非 Lipschitz 损失场景,适合隐私敏感优化任务。
研究差分隐私环境下的随机凸优化(DP-SCO)。不同于以往工作,本文假设总体风险函数满足参数 $θ>1$ 的 Tsybakov 噪声条件(TNC),此时损失函数的 Lipschitz 常数可能极大甚至无界,但其梯度的 $\ell_2$-范数具有有界 $k$-阶矩($k\geq2$)。针对 $θ\geq2$ 的 Lipschitz 情况,提出一种 $(\varepsilon, δ)$-差分隐私算法,其在高概率下误差上界为 $\Tilde{O}\left(\left(\tilde{r}_{2k}(\frac{1}{\sqrt{n}}+(\frac{\sqrt{d}}{n\varepsilon}))^{\frac{k-1}{k}}\right)^{\frac{θ}{θ-1}}\right)$,其中 $n$ 为样本量,$d$ 为模型维度,$\tilde{r}_{2k}$ 仅依赖于梯度的 $2k$-阶矩。该界不依赖 Lipschitz 常数。进一步推广至 $θ\geq\barθ>1$($\barθ$ 已知)的情形。当隐私预算 $\varepsilon$ 足够小时,即使损失函数非 Lipschitz,也能获得上界 $\tilde{O}\left(\left(\tilde{r}_{k}(\frac{1}{\sqrt{n}}+(\frac{\sqrt{d}}{n\varepsilon}))^{\frac{k-1}{k}}\right)^{\frac{θ}{θ-1}}\right)$。下界方面,对任意 $θ\geq2$,在 $ρ$-零集中差分隐私下,私有最小最大率下界为 $Ω\left(\left(\tilde{r}_{k}(\frac{1}{\sqrt{n}}+(\frac{\sqrt{d}}{n\sqrt{ρ}}))^{\frac{k-1}{k}}\right)^{\frac{θ}{θ-1}}\right)$。
原文摘要 · Abstract (English)
We study Stochastic Convex Optimization in the Differential Privacy model (DP-SCO). Unlike previous studies, here we assume the population risk function satisfies the Tsybakov Noise Condition (TNC) with some parameter $θ>1$, where the Lipschitz constant of the loss could be extremely large or even unbounded, but the $\ell_2$-norm gradient of the loss has bounded $k$-th moment with $k\geq 2$. For the Lipschitz case with $θ\geq 2$, we first propose an $(\varepsilon, δ)$-DP algorithm whose utility bound is $\Tilde{O}\left(\left(\tilde{r}_{2k}(\frac{1}{\sqrt{n}}+(\frac{\sqrt{d}}{n\varepsilon}))^\frac{k-1}{k}\right)^\fracθ{θ-1}\right)$ in high probability, where $n$ is the sample size, $d$ is the model dimension, and $\tilde{r}_{2k}$ is a term that only depends on the $2k$-th moment of the gradient. It is notable that such an upper bound is independent of the Lipschitz constant. We then extend to the case where $θ\geq \barθ> 1$ for some known constant $\barθ$. Moreover, when the privacy budget $\varepsilon$ is small enough, we show an upper bound of $\tilde{O}\left(\left(\tilde{r}_{k}(\frac{1}{\sqrt{n}}+(\frac{\sqrt{d}}{n\varepsilon}))^\frac{k-1}{k}\right)^\fracθ{θ-1}\right)$ even if the loss function is not Lipschitz. For the lower bound, we show that for any $θ\geq 2$, the private minimax rate for $ρ$-zero Concentrated Differential Privacy is lower bounded by $Ω\left(\left(\tilde{r}_{k}(\frac{1}{\sqrt{n}}+(\frac{\sqrt{d}}{n\sqrtρ}))^\frac{k-1}{k}\right)^\fracθ{θ-1}\right)$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。