Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization
<|reference_start|>Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization: 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 $(\epsilon,\delta)$-DP algorithm that returns an $(\alpha,\beta)$-stationary point as long as the dataset is of size $\widetilde{\Omega}\left(1/\alpha\beta^{3}+d/\epsilon\alpha\beta^{2}+d^{3/4}/\epsilon^{1/2}\alpha\beta^{5/2}\right)$, which is $\Omega(\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{\Omega}\left(d/\beta^2+d^{3/4}/\epsilon\alpha^{1/2}\beta^{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.<|reference_end|>
@article{kornowski2024improved,
    title={Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization},
    author={Guy Kornowski, Daogao Liu, Kunal Talwar},
    journal={arXiv preprint arXiv:2410.05880},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.05880},
    primaryClass={cs.LG cs.CR math.OC stat.ML}
}