Faster Privacy Accounting via Evolving Discretization
Authors: Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
ICML 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We implement our two-stage algorithm and compare it to baselines from the literature. We consider the sub-sampled Gaussian mechanism, which is a fundamental primitive in private machine learning and constitutes a core primitive of training algorithms that use differentially private stochastic gradient descent (DP-SGD) (see, e.g., (Abadi et al., 2016)). For 2^16 compositions and a standard deviation of 226.86 and with subsampling probability of 0.2, we obtain a speedup of 2.66 compared to the state-of-the-art. We also consider compositions of the widely-used Laplace mechanism. For 2^16 compositions, and a scale parameter of 1133.84 for the Laplace distribution, we achieve a speedup of 2.3 . The parameters were chosen such that the composed mechanism satisfies (ε = 1.0, δ = 10^−6)-DP. See Section 4 for more details.4. Experimental Evaluation of Two Stage Self Compose PRV |
| Researcher Affiliation | Industry | Badih Ghazi 1 Pritish Kamath 1 Ravi Kumar 1 Pasin Manurangsi 1 1Google Research, USA. |
| Pseudocode | Yes | Algorithm 1 Discretize RV (adapted from Gopi et al., 2021)Algorithm 2 Two Stage Self Compose PRVAlgorithm 3 Recursive Self Compose PRV |
| Open Source Code | No | We empirically evaluate Two Stage Self Compose PRV on the tasks of self-composing two kinds of mechanism acting on dataset of real values x1, . . . , xn as Laplace Mechanism : returns P i xi plus a noise drawn from L(0, b) given by the PDF P(x) = e |x|/b/2b. Poisson Subsampled Gaussian Mechanism with probability γ: Subsamples a random subset S of indices by including each index independently with probability γ. Returns P i S xi plus a noise drawn from the Gaussian distribution N(0, σ2). Both these mechanisms are highly used in practice. For each mechanism, we compare against the implementation by Gopi et al. (2021)2 (referred to as GLW) on three fronts: (i) the running time of the algorithm, (ii) the number of discretized buckets used, and (iii) the final estimates on δY k(ε) which includes comparing lower bound δY2(ε + εerr) δerr, estimates δY2(ε) and upper bounds δY2(ε εerr) + δerr. We use εerr = 0.1 and δerr = 10 10 in all the experiments. 2github.com/microsoft/prv accountant |
| Open Datasets | No | We empirically evaluate Two Stage Self Compose PRV on the tasks of self-composing two kinds of mechanism acting on dataset of real values x1, . . . , xn as Laplace Mechanism... Poisson Subsampled Gaussian Mechanism... The noise parameter of basic mechanism is chosen such that the final δ(ε) value after k-fold composition is equal to 10^−6 for each value of k.3 The exact choice of noise parameters used are shown in Figure 3. 3these values were computed using the Google DP accountant github.com/google/differential-privacy/tree/main/python. |
| Dataset Splits | No | No information on training/validation/test dataset splits is provided. |
| Hardware Specification | No | No hardware specifications are provided. |
| Software Dependencies | No | PLD implementations have been at the heart of many DP systems and open-source libraries including (Lukas Prediger, 2020; Google, 2020; Microsoft, 2021). |
| Experiment Setup | Yes | We use εerr = 0.1 and δerr = 10^−10 in all the experiments.For 2^16 compositions and a standard deviation of 226.86 and with subsampling probability of 0.2, we obtain a speedup of 2.66 compared to the state-of-the-art. We also consider compositions of the widely-used Laplace mechanism. For 2^16 compositions, and a scale parameter of 1133.84 for the Laplace distribution, we achieve a speedup of 2.3 . |