Private Stochastic Convex Optimization: Optimal Rates in L1 Geometry
Authors: Hilal Asi, Vitaly Feldman, Tomer Koren, Kunal Talwar
ICML 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that, up to logarithmic factors the optimal excess population loss of any (ε, δ)-differentially private optimizer is p d/εn. The upper bound is based on a new algorithm that combines the iterative localization approach of Feldman et al. (2020a) with a new analysis of private regularized mirror descent. It applies to ℓp bounded domains for p [1, 2] and queries at most n3/2 gradients improving over the best previously known algorithm for the ℓ2 case which needs n2 gradients. Further, we show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by p log(d)/n + (log(d)/εn)2/3. This bound is achieved by a new variance-reduced version of the Frank-Wolfe algorithm that requires just a single pass over the data. We also show that the lower bound in this case is the minimum of the two rates mentioned above. |
| Researcher Affiliation | Collaboration | 1Department of Electrical Engineering, Stanford University 2Apple 3Blavatnik School of Computer Science, Tel Aviv University, and Google Research Tel Aviv. |
| Pseudocode | Yes | Algorithm 1 Noisy Mirror Descent, Algorithm 2 Localized Noisy Mirror Descent, Algorithm 3 Private Variance Reduced Frank-Wolfe |
| Open Source Code | No | The paper does not contain any statement or link indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | In this problem (DP-SCO), given n i.i.d. samples z1, . . . , zn from a distribution P, we wish to release a private solution x X Rd that minimizes the population loss F(x) = Ez P [f(x; z)] for a convex function f over x. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments or data, therefore there is no mention of training, validation, or test splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for running experiments or computations. |
| Software Dependencies | No | The paper focuses on theoretical algorithms and proofs and does not mention any specific software dependencies or their version numbers. |
| Experiment Setup | No | The paper is theoretical and describes algorithmic parameters as part of the algorithm design and analysis (e.g., 'Require: Dataset S = (z1, . . . , zn) Zn, convex set X, convex function h : X R, step sizes {ηk}T k=1, batch size b, initial point x0, number of iterations T;'), rather than detailing an experimental setup with specific hyperparameters for empirical evaluation. |