Research map / Optimization / Nonconvex and smooth optimization
Private Zeroth-Order Nonsmooth Nonconvex Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a zeroth-order, differentially private algorithm for nonsmooth nonconvex stochastic optimization that combines online-to-nonconvex conversion with variance-reduced zeroth-order gradient oracles and the tree mechanism.
Problem
Private stochastic optimization of nonconvex, nonsmooth objectives using only function-value (zeroth-order) access, targeting Goldstein (delta,epsilon)-stationary points under Renyi differential privacy.
Approach
Applies O2NC to the uniform smoothing of the objective, builds a variance-reduced zeroth-order gradient oracle (gradient plus gradient-difference estimators, each averaging d i.i.d. random directions per data point), and privatizes the running sums with the tree mechanism, so noise is reduced by a factor of T^2 versus naive Gaussian noise.
Key results
- Achieves M = Omega~(d/(delta eps^3) + d^{3/2}/(rho delta eps^2)) data complexity for (alpha, alpha rho^2/2)-RDP and (delta,eps)-stationarity, matching the non-private zeroth-order rate in its leading term.
- Privacy comes for free when rho >= sqrt(d) eps, since the non-private term dominates.
- The naive Gaussian-noise approach yields O(d^{3/2} rho^{-1} delta^{-1} eps^{-3}), worse by a factor of 1/eps.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed private variance-reduced zeroth-order oracle with the tree mechanism instead of directly privatizing classical zeroth-order gradient estimators | O2NC for nonsmooth nonconvex optimization · Nonsmooth nonconvex stochastic optimization | data complexity: O(d^{3/2}\rho^{-1}\delta^{-1}\epsilon^{-3}) -> \tilde O\left( d\left(\frac{F^*L^2}{\delta\epsilon^3} + \frac{L^3}{\epsil | Helped |
| Use O2NC rather than a smooth optimization algorithm to optimize the smoothed objective | Private zeroth-order algorithm · Nonsmooth nonconvex stochastic optimization | dimension dependence: O(d^{3/2}\delta^{-1}\epsilon^{-3}) -> O(d\delta^{-1}\epsilon^{-3}) | Helped |
| Remove O2NC (ablation) | Private zeroth-order algorithm · Nonsmooth nonconvex stochastic optimization | dimension dependence: +\sqrt{d} | Hurt |
| Sample d i.i.d. uniform vectors per data point rather than using a single estimator | Private zeroth-order gradient and gradient-difference estimators · Nonsmooth nonconvex stochastic optimization | dimension dependence of variance: by a factor of d | Helped |
| Use a single uniform vector per data point instead of sampling d i.i.d. vectors (ablation) | Private zeroth-order gradient estimator · Nonsmooth nonconvex stochastic optimization | dimension dependence: +\sqrt{d} | Hurt |
| Replace the variance-reduced oracle and tree mechanism with direct Gaussian noise on classical zeroth-order gradient estimates (ablation) | O2NC for nonsmooth nonconvex optimization · Nonsmooth nonconvex stochastic optimization | data complexity: O(d^{3/2}\rho^{-1}\delta^{-1}\epsilon^{-3}) | Hurt |
Surprising findings
- Naive private zeroth-order O2NC with Gaussian noise is worse by a factor of 1/eps and never recovers the non-private rate for any rho.
Limitations
- Requires sampling d i.i.d. random directions per data point, which the authors consider a limitation.
- Optimality of the private rate is unproven; lower bounds remain open.
- Only zeroth-order private method; first-order private nonsmooth algorithms left for future work.
Experimental setup
Metrics: data complexity M for (delta,epsilon)-stationarity under (al
Baselines: naive private zeroth-order O2NC with Gaussian noise private smooth nonconvex optimization (Wang et al. style rate) non-private zeroth-order O2NC
Builds on: Online-to-Nonconvex Conversion tree mechanism uniform smoothing Goldstein stationarity
Closest papers by meaning
- Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization (ICML 2025 · similarity 0.91)
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions (NeurIPS 2024 · similarity 0.88)
- Convergent Privacy Loss of Noisy-SGD without Convexity and Smoothness (ICLR 2025 · similarity 0.86)
- Private Zeroth-Order Optimization with Public Data (NeurIPS 2025 · similarity 0.86)
- Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates (AAAI 2025 · similarity 0.86)
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.