Faster Rates of Convergence to Stationary Points in Differentially Private Optimization
Authors: Raman Arora, Raef Bassily, Tomás González, Cristóbal A Guzmán, Michael Menart, Enayat Ullah
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We give a new construction that improves over the existing rates in the stochastic optimization setting, where the goal is to find approximate stationary points of the population risk given n samples. Our construction finds a O 1 n1/3 + d nε 1/2 -stationary point of the population risk in time linear in n. We also provide an efficient algorithm that finds an O d nε 2/3 stationary point in the finite-sum setting. This improves on the previous best rate of O d nε 1/2 . Furthermore, under the additional assumption of convexity, we completely characterize the sample complexity of finding stationary points of the population risk (up to polylog factors) and show that the optimal rate on population stationarity is Θ 1 n + d nε . Table 1. Results summary: We omit log factors and function-class parameters. The symbol stands for minimum of the quantities. |
| Researcher Affiliation | Academia | 1Department of Computer Science, The Johns Hopkins University 2Department of Computer Science & Engineering, The Ohio State University 3Translational Data Analytics Institute (TDAI), The Ohio State University 4Institute for Mathematical and Computational Engineering, Pontificia Universidad Cat olica de Chile. |
| Pseudocode | Yes | Algorithm 1 Tree-based Private Spider, Algorithm 2 Private Spider Boost, Algorithm 3 Recursive Regularization, Algorithm 4 JL method, Algorithm 5 Phased SGD, Algorithm 6 Output Perturbed SGD, Algorithm 7 Noisy GD |
| Open Source Code | No | The paper does not contain any explicit statements or links indicating the availability of open-source code for the described methodologies. |
| Open Datasets | No | The paper is theoretical and does not describe experiments run on specific datasets, thus it does not mention a publicly available dataset for training. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments, thus it does not specify training, validation, or test dataset splits. |
| Hardware Specification | No | This is a theoretical paper and does not describe empirical experiments, thus no hardware specifications are provided. |
| Software Dependencies | No | This is a theoretical paper and does not describe empirical experiments, thus no specific software dependencies with version numbers are provided. |
| Experiment Setup | No | This is a theoretical paper that focuses on algorithm design and analysis, and thus does not include details on experimental setup such as hyperparameters or training configurations. |