Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions

We study the problem of differentially private stochastic convex optimization (DP-SCO) with heavy-tailed gradients, where we assume a kᵗʰ-moment bound on the Lipschitz constants of sample functions rather than a uniform bound. We propose a new reduction-based approach that enables us to obtain the first optimal rates (up to logarithmic factors) in the heavy-tailed setting, achieving error G₂ · 1 √ n + Gₖ · (√ d/nε)1 - 1 k under (ε, δ)-approximate differential privacy, up to a mild polylog(1/δ) factor, where G₂² and Gₖᵏ are the 2ⁿᵈ and kᵗʰ moment bounds on sample Lipschitz constants, nearly-matching a lower bound of [Lowy and Razaviyayn 2023]. We further give a suite of private algorithms in the heavy-tailed setting which improve upon our basic result under additional assumptions, including an optimal algorithm under a known-Lipschitz constant assumption, a near-linear time algorithm for smooth functions, and an optimal linear time algorithm for smooth generalized linear models.