{"ID":2874794,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.04668","arxiv_id":"2509.04668","title":"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 $θ\u003e1$, 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θ\u003e 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)$.","short_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 $θ\u003e1$, where the Lipschitz constant of the loss could be extremely large or even unbounded, but the $\\...","url_abs":"https://arxiv.org/abs/2509.04668","url_pdf":"https://arxiv.org/pdf/2509.04668v1","authors":"[\"Difei Xu\",\"Meng Ding\",\"Zihang Xiang\",\"Jinhui Xu\",\"Di Wang\"]","published":"2025-09-04T21:30:44Z","proceeding":"cs.LG","tasks":"[\"cs.LG\"]","methods":"[]","has_code":false}