On User-Level Private Convex Optimization
This addresses privacy-preserving optimization for users in machine learning, offering more flexible and efficient guarantees.
The paper tackles stochastic convex optimization with user-level differential privacy by introducing a new mechanism that removes smoothness assumptions and achieves dimension-independent minimum user requirements. The result shows convergence rates similar to prior work but with these key improvements.
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.