User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates
This work addresses the challenge of efficient and scalable privacy-preserving optimization for users with multiple data items, representing a significant improvement over prior methods that were either inefficient or had restrictive assumptions.
The paper tackles user-level differentially private stochastic convex optimization by developing efficient polynomial-time algorithms that achieve optimal rates for convex and strongly convex functions, requiring only logarithmic growth in the number of users relative to dimension, and also providing the first optimal rates for non-smooth functions in polynomial time.
We study differentially private stochastic convex optimization (DP-SCO) under user-level privacy, where each user may hold multiple data items. Existing work for user-level DP-SCO either requires super-polynomial runtime [Ghazi et al. (2023)] or requires the number of users to grow polynomially with the dimensionality of the problem with additional strict assumptions [Bassily et al. (2023)]. We develop new algorithms for user-level DP-SCO that obtain optimal rates for both convex and strongly convex functions in polynomial time and require the number of users to grow only logarithmically in the dimension. Moreover, our algorithms are the first to obtain optimal rates for non-smooth functions in polynomial time. These algorithms are based on multiple-pass DP-SGD, combined with a novel private mean estimation procedure for concentrated data, which applies an outlier removal step before estimating the mean of the gradients.