On User-Level Private Convex Optimization
Authors: Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, Chiyuan Zhang
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Collaboration | 1Google Research, Mountain View, CA 2Google Research, Thailand 3UCLA, Los Angles, CA. |
| Pseudocode | Yes | Algorithm 1 Del Output Pertε,δ, (f; x); Algorithm 2 SCOutput Pertε,δ,β,G,µ,K(ℓ; x); Algorithm 3 Phased-ERM.; Algorithm 4 Phased-SCO; Algorithm 5 Strongly-Convex-ERM; Algorithm 6 Strongly-Convex-SCO |
| Open Source Code | No | The paper does not provide any statement or link regarding the availability of its source code. |
| Open Datasets | No | The paper describes abstract dataset formulations (e.g., “n users, and let the input to the ith user be xi := (xi,1, . . . , xi,m)”) and discusses data distributions (e.g., “drawn i.i.d. from D”), but it does not specify any named public datasets or provide access information (links, citations with authors/year) for any dataset used. |
| Dataset Splits | No | The paper does not provide specific details about training, validation, or test dataset splits. Its analysis is theoretical, focusing on convergence rates and bounds rather than empirical evaluation on partitioned datasets. |
| Hardware Specification | No | The paper does not mention any specific hardware used for its research or experiments. |
| Software Dependencies | No | The paper does not list any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper describes theoretical algorithms and bounds, not empirical experiments. Therefore, it does not provide details about experimental setup, hyperparameters, or training configurations. |