User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates

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...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-11
Main Authors: Hilal Asi, Liu, Daogao
Format: Article
Language:English
Subjects:
Algorithms
Convexity
Estimation
Functions (mathematics)
Mathematical analysis
Optimization
Outliers (statistics)
Polynomials
Privacy
Run time (computers)
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422