Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions
AuthorsHilal Asi, Daogao Liu, Kevin Tian
AuthorsHilal Asi, Daogao Liu, Kevin Tian
We study the problem of differentially private stochastic convex optimization (DP-SCO) with heavy-tailed gradients, where we assume a -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 under -approximate differential privacy, up to a mild factor, where and are the and moment bounds on sample Lipschitz constants, nearly-matching a lower bound of (Lowy et al. 2023).
Self-attention and masked self-attention are at the heart of Transformers' outstanding success. Still, our mathematical understanding of attention, in particular of its Lipschitz properties — which are key when it comes to analyzing robustness and expressive power — is incomplete. We provide a detailed study of the Lipschitz constant of self-attention in several practical scenarios, discussing the impact of the sequence length and layer...
July 9, 2021research area Methods and Algorithms, research area Privacyconference ICML
Stochastic convex optimization over an -bounded domain is ubiquitous in machine learning applications such as LASSO but remains poorly understood when learning with differential privacy. We show that, up to logarithmic factors the optimal excess population loss of any -differentially private optimizer is The upper bound is based on a new algorithm that combines the...