Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Condition

Abstract

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 $\hat{I}¸>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\ge 2$. For the Lipschitz case with $\hat{I}¸\ge 2$, we first propose an $(\epsilon ,\hat{I}´)$-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 $\hat{I}¸\ge \bar{\hat{I}}¸>1$ for some known constant $\bar{\hat{I}}¸$. Moreover, when the privacy budget $\epsilon$ is small enough, we show an upper bound of $\tilde{O}\left({\left({\tilde{r}}_k(\frac{1}{\sqrt{n}}+(\frac{\sqrt{d}}{n\epsilon }){)}^{\frac{k-1}{k}}\right)}^{\frac{\hat{I}}{¸}}\hat{I}¸-1\right)$ even if the loss function is not Lipschitz. For the lower bound, we show that for any $\hat{I}¸\ge 2$, the private minimax rate for $\ddot{I}$-zero Concentrated Differential Privacy is lower bounded by $\hat{I}\text{c◯}\left({\left({\tilde{r}}_k(\frac{1}{\sqrt{n}}+(\frac{\sqrt{d}}{n\sqrt{\ddot{I}}}){)}^{\frac{k-1}{k}}\right)}^{\frac{\hat{I}}{¸}}\hat{I}¸-1\right)$.