mlsanityData to 14 Oct 2026

Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization

arXiv 2410.05880 ↗First posted 8 Oct 2024cs.LG cs.CR math.OCcited by 4

Not on the map. Why?

Abstract (arXiv)

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 widetildeOmega(√d/αβ3+d/εαβ2), which is Omega(√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 widetildeOmegaleft(d/β2+d3/4/εα1/2β3/2right), by designing a sample efficient ERM algorithm, and proving that Goldstein-stationary points generalize from the empirical loss to the population loss.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 27 of its 44 references that are in the map. First posted on arXiv 8 Oct 2024.

Builds on

27 of 44 references.

References · 27

  1. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,352
  2. 2019Introduction to Online Convex Optimizationcited by 803
  3. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  4. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  5. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  6. 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 198
  7. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  8. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
  9. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 128
  10. 2015An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedbackcited by 111
  11. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 106
  12. 2016The Landscape of Empirical Risk for Non-convex Lossescited by 86
15 more
  1. 2022Private Convex Optimization via Exponential Mechanismcited by 49
  2. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 45
  3. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 43
  4. 2021Oracle Complexity in Nonsmooth Nonconvex Optimizationcited by 39
  5. 2021A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensionscited by 39
  6. 2022Faster Rates of Convergence to Stationary Points in Differentially Private Optimizationcited by 32
  7. 2023Deterministic Nonsmooth Nonconvex Optimizationcited by 26
  8. 2023An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimizationcited by 23
  9. 2023ReSQueing Parallel and Private Stochastic Convex Optimizationcited by 17
  10. 2022No Dimension-Free Deterministic Algorithm Computes Approximate Stationarities of Lipschitzianscited by 16
  11. 2023Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Riskscited by 12
  12. 2024How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimizationcited by 10
  13. 2022The cost of nonconvexity in deterministic nonsmooth optimizationcited by 9
  14. 2024Private Zeroth-Order Nonsmooth Nonconvex Optimizationcited by 8
  15. 2023Goldstein Stationarity in Lipschitz Constrained Optimizationcited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 1; 2026: 2.

4 papers.

  1. 2024Adaptive Batch Size for Privately Finding Second-Order Stationary Pointscited by 2
  2. 2025Purifying Approximate Differential Privacy with Randomized Post-processingcited by 2
  3. 2026Stability and Generalization of Stochastic Nonconvex Optimization under Heavy-Tailed Noise: From Gradient Norm to Goldstein Stationaritycited by 0
  4. 2026The Exponential Price of Determinism in Nonsmooth Nonconvex Optimizationcited by 0