On User-Level Private Convex Optimization
Badih Ghazi Pritish Kamath Ravi Kumar Raghu Meka Pasin Manurangsi Chiyuan Zhang
We introduce a new mechanism for stochastic convex optimization (SCO) with
user-level differential privacy guarantees. The convergence rates of this
mechanism are similar to those in the prior work of Levy et al. (2021);
Narayanan et al. (2022), but with two important improvements. Our mechanism
does not require any smoothness assumptions on the loss. Furthermore, our
bounds are also the first where the minimum number of users needed for
user-level privacy has no dependence on the dimension and only a logarithmic
dependence on the desired excess error. The main idea underlying the new
mechanism is to show that the optimizers of strongly convex losses have low
local deletion sensitivity, along with an output perturbation method for
functions with low local deletion sensitivity, which could be of independent
interest.