Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization

Abstract

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 single-pass $(\hat{I}\mu ,\hat{I}´)$-DP algorithm that returns an $(\hat{I}\pm ,{\hat{I}}^2)$-stationary point as long as the dataset is of size $\widetildeΩ(\sqrt{d}/αβ^{3}+d/εαβ^{2})$, which is $\hat{I}\text{c◯}(\sqrt{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 $\widetildeΩ\left(d/β^2+d^{3/4}/εα^{1/2}β^{3/2}\right)$, by designing a sample efficient ERM algorithm, and proving that Goldstein-stationary points generalize from the empirical loss to the population loss.

Accepted to ICML 2025; some fixes following reviews