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

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 ℓ₂-norm gradient of the loss has bounded k-th moment with k ≥ 2. For the Lipschitz case with θ ≥ 2, we first propose an ( (ε, δ)-DP algorithm whose utility bound is (˜r^Õ_2k ( √¹_n + (^√d nε k−1 )) k ) θ θ−1 ) in high probability, where n is the sample size, d is the model dimension, and ˜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 θ ≥^¯θ > 1 for some known constant^¯θ. Moreover, when the privacy budget ε is small enough, we show an upper bound of ( Õ (˜rk ( √¹_n + (^√d nε k−1 )) k ) θ θ−1 ) even if the loss function is not Lipschitz. For the lower bound, we show that for any θ ≥ 2, the ( private minimax rate for ρ-zero Concentrated Differential Privacy is lower bounded by Ω (˜rk ( √¹_n + (^√ ) θ ) d n^√ k−1 θ−1 ρ)) k .