Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions
<|reference_start|>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^{\text{th}}$-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_2 \cdot \frac 1 {\sqrt n} + G_k \cdot (\frac{\sqrt d}{n\epsilon})^{1 - \frac 1 k}$ under $(\epsilon, \delta)$-approximate differential privacy, up to a mild $\textup{polylog}(\frac{1}{\delta})$ factor, where $G_2^2$ and $G_k^k$ are the $2^{\text{nd}}$ and $k^{\text{th}}$ 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.<|reference_end|>
@article{asi2024private,
    title={Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality
  from Simple Reductions},
    author={Hilal Asi, Daogao Liu, Kevin Tian},
    journal={arXiv preprint arXiv:2406.02789},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.02789},
    primaryClass={cs.DS cs.CR cs.LG stat.ML}
}