Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization
Authors: Guy Kornowski, Daogao Liu, Kunal Talwar
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study differentially private (DP) optimization algorithms for stochastic and empirical objectives which are neither smooth nor convex, and propose methods that return a Goldstein-stationary point with sample complexity bounds that improve on existing works. We start by providing a singlepass (ε, δ)-DP algorithm that returns an (α, β)stationary point as long as the dataset is of size eΩ(d/αβ3 + d/εαβ2), which is Ω(d) times smaller than the algorithm of Zhang et al. (2024) for this task, where d is the dimension. We then provide a multi-pass polynomial time algorithm which further improves the sample complexity to eΩ d/β2 + d3/4/εα1/2β3/2 , by designing a sample efficient ERM algorithm, and proving that Goldstein-stationary points generalize from the empirical loss to the population loss. |
| Researcher Affiliation | Collaboration | 1Weizmann Institute of Science; work done while interning at Apple. 2Google; work done while at University of Washington and Apple. 3Apple. Correspondence to: Guy Kornowski <EMAIL>, Daogao Liu <EMAIL>. |
| Pseudocode | Yes | Algorithm 1 Tree Mechanism Algorithm 2 Nonsmooth Nonconvex Algorithm (based on O2NC (Cutkosky et al., 2023)) Algorithm 3 Single-pass instantiation of O(zt) in Line 7 of Algorithm 2 Algorithm 4 Multi-pass instantiation of O(zt) in Line 7 of Algorithm 2 Algorithm 5 First-order instantiation of O(zt) in Line 7 of Algorithm 2 |
| Open Source Code | No | The paper does not contain any explicit statements about releasing code, nor does it provide links to code repositories. |
| Open Datasets | No | The paper discusses theoretical objectives like F(x) := E ξ P [f(x; ξ)] (stochastic) and b F D(x) := 1 Pn i=1 f(x; ξi) (ERM), and refers to a dataset D = (ξ1, . . . , ξn) Pn as a theoretical construct for analysis. It does not mention any specific named datasets (e.g., MNIST, CIFAR-10) that were used for experiments, nor does it provide any links, DOIs, or citations to actual datasets for public access. |
| Dataset Splits | No | The paper does not describe any empirical experiments involving specific datasets, and therefore, it does not mention any training/test/validation dataset splits. |
| Hardware Specification | No | The paper focuses on theoretical contributions regarding algorithms and sample complexity. It does not describe any experiments that would require specific hardware, and thus, no hardware specifications are provided. |
| Software Dependencies | No | The paper presents theoretical algorithms and their complexity analysis. It does not describe any implemented software or provide specific version numbers for software dependencies. |
| Experiment Setup | No | The paper details theoretical algorithms and proves their properties but does not describe an experimental setup, including hyperparameters or system-level training settings, as it does not present empirical results. |