2024/10/08 by Guy Kornowski, Kornowski, Guy, Daogao Liu +3
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2410.05880
openalex publication_date 2024/10/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (ε,δ)-DP algorithm that returns an (α,β)-stationary point as long as the dataset is of size \widetildeΩ(√(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 \widetildeΩ(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.