mlsanityData to 14 Oct 2026

Private Zeroth-Order Nonsmooth Nonconvex Optimization

arXiv 2406.19579 ↗First posted 27 Jun 2024math.OC cs.CR cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

We introduce a new zeroth-order algorithm for private stochastic optimization on nonconvex and nonsmooth objectives. Given a dataset of size M, our algorithm ensures (α,αρ2/2)-R'enyi differential privacy and finds a (δ,ε)-stationary point so long as M=tildeOmegaleft(fracdδε3 + fracd3/2ρδε2right). This matches the optimal complexity of its non-private zeroth-order analog. Notably, although the objective is not smooth, we have privacy ``for free'' whenever ρ ≥ √dε.

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

Builds on

26 of 48 references.

References · 26

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  3. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  4. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  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. 2021Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 51
  12. 2021Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settingscited by 45
14 more
  1. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 45
  2. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 43
  3. 2020Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitationscited by 40
  4. 2021Oracle Complexity in Nonsmooth Nonconvex Optimizationcited by 39
  5. 2022Faster Rates of Convergence to Stationary Points in Differentially Private Optimizationcited by 32
  6. 2021On the Finite-Time Complexity and Practical Computation of Approximate Stationarity Concepts of Lipschitz Functionscited by 31
  7. 2019Efficient Privacy-Preserving Stochastic Nonconvex Optimizationcited by 27
  8. 2020Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Boundscited by 26
  9. 2014Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometrycited by 24
  10. 2023An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimizationcited by 23
  11. 2023Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimizationcited by 17
  12. 2020Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functionscited by 13
  13. 2022Momentum Aggregation for Private Non-convex ERMcited by 10
  14. 2022Differentially Private Online-to-Batch for Smooth Lossescited by 5

Built on by

Cited by year (2026 to 14 Oct)

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

8 papers.

  1. 2024Improved Sample Complexity for Private Nonsmooth Nonconvex Optimizationcited by 4
  2. 2024Differentially Private Bilevel Optimizationcited by 2
  3. 2024Adaptive Batch Size for Privately Finding Second-Order Stationary Pointscited by 2
  4. 2025Private Zeroth-Order Optimization with Public Datacited by 2
  5. 2026Position: Zeroth-Order Optimization in Deep Learning Is Underexplored, Not Underpoweredcited by 1
  6. 2025Privacy Amplification in Differentially Private Zeroth-Order Optimization with Hidden Statescited by 0
  7. 2025On the Inherent Privacy of Zeroth Order Projected Gradient Descentcited by 0
  8. 2026Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oraclescited by 0