Private Stochastic Convex Optimization with Optimal Rates
Authors: Raef Bassily, Vitaly Feldman, Kunal Talwar, Abhradeep Guha Thakurta
NeurIPS 2019 | 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 for DP algorithms is equal to the larger of the optimal non-private excess population loss, and the optimal excess empirical loss of DP algorithms. This implies that, contrary to intuition based on private ERM, private SCO has asymptotically the same rate of 1/ n as non-private SCO in the parameter regime most common in practice. The best previous result in this setting gives rate of 1/n1/4. Our approach builds on existing differentially private algorithms and relies on the analysis of algorithmic stability to ensure generalization. |
| Researcher Affiliation | Collaboration | Raef Bassily The Ohio State University bassily.1@osu.edu Vitaly Feldman Google Research. Brain Team. Kunal Talwar Google Research. Brain Team. kunal@google.com Abhradeep Thakurta University of California Santa Cruz Google Research. Brain Team. |
| Pseudocode | Yes | Algorithm 1 ANSGD: Mini-batch noisy SGD for convex, smooth losses |
| Open Source Code | No | The paper does not provide an explicit statement or a specific link to source code for the methodology described. It refers to a full version on arXiv [BFTT19] for more details, but this does not constitute a code release. |
| Open Datasets | No | The paper does not mention any specific public datasets by name, nor does it provide links, DOIs, or formal citations for any datasets used in experiments. It refers generically to "samples z1, . . . , zn from the data distribution D" but no concrete dataset is identified. |
| Dataset Splits | No | The paper does not describe empirical experiments or provide any specific dataset split information (percentages, sample counts, or citations to predefined splits) for training, validation, or testing. |
| Hardware Specification | No | The paper does not provide specific hardware details (such as GPU/CPU models, processor types, or memory amounts) used for running experiments, as it focuses on theoretical contributions rather than empirical ones. |
| Software Dependencies | No | The paper does not provide specific ancillary software details, such as library or solver names with version numbers, as it focuses on theoretical analysis rather than empirical implementation details. |
| Experiment Setup | No | The paper specifies algorithmic parameters (e.g., step size η, mini-batch size m, number of iterations T, regularization parameter λ) as part of the theoretical algorithm descriptions, but it does not provide concrete experimental setup details or hyperparameter values used in an empirical setting, as no experiments are reported. |