Research map / Optimization / Nonconvex and smooth optimization
How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex 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 warm-start framework for differentially private non-convex optimization, where a private approximate risk minimizer initializes a private stationary-point finder (DP-SPIDER or DP-SPIDER-SOSP), yielding improved and sometimes optimal rates for stationary points.
Problem
Finding differentially private approximate first- and second-order stationary points of smooth non-convex empirical and population loss functions (and GLMs), where prior rates were (sqrt(d ln(1/δ))/εn)^{2/3} for empirical losses.
Approach
Generalize Nesterov's AGD-then-GD warm start to private non-convex optimization: run a private approximate risk minimizer (e.g., exponential mechanism or DP-SGD for quasar-convex/KL* losses) to reduce initial suboptimality, then run a DP stationary-point finder whose guarantee scales with that gap.
Key results
- Warm-start DP-SGD then DP-SPIDER achieves E||grad|| = O~(sqrt(d ln(1/δ))/(εn) d^{1/6}) for smooth non-convex ERM, improving the prior (sqrt(d ln(1/δ))/(εn))^{2/3} rate when d < nε.
- Optimal rate O~(sqrt(d ln(1/δ))/(εn)) achieved for quasar-convex and KL* empirical losses without assuming convexity.
- Preliminary experiments show the warm-start algorithm outperforms DP-SGD and DP-SPIDER baselines in the high privacy regime ε ≤ 1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Warm-start DP-SPIDER with DP-SGD | Synthetic non-convex optimization, training loss · Synthetic data (ε ≤ 1) | gradient norm | Helped |
| Warm-start DP-SPIDER with DP-SGD | Synthetic non-convex optimization, test loss · Synthetic data (ε ≤ 1) | gradient norm | Helped |
| Warm-start DP-SPIDER with DP-SGD | Synthetic non-convex optimization · Synthetic data (ε ∈ {2, 4}) | gradient norm | No clear effect |
Surprising findings
- For KL* losses, larger k does not yield faster stationary-point rates, unlike in the excess risk setting.
- In experiments the warm-start method sometimes performs worse than baselines despite theory suggesting it should never consistently do so, attributed to randomness.
Limitations
- Improvements over prior rates hold mainly when d < nε; for higher dimension DP-SPIDER is used instead.
- Experiments are small-scale synthetic simulations only (n = d = 100).
- Gap remains between upper bounds and lower bounds for general non-convex losses; the computationally efficient variants are not addressed.
Experimental setup
Datasets: synthetic data (unit ball samples, non-convex loss)
Benchmarks: synthetic non-convex loss f(w,x)=1/2[||w||^2+sin(||w||^2)]+x^T w
Metrics: gradient norm vs epsilon
Baselines: DP-SGD DP-SPIDER DP-SPIDER-SOSP JL method for GLMs
Builds on: DP-SPIDER exponential mechanism Nesterov warm start DP-SPIDER-SOSP
Closest papers by meaning
- Accelerated Stochastic Optimization Methods under Quasar-convexity (ICML 2023 · similarity 0.89)
- Second-Order Convergence in Private Stochastic Non-Convex Optimization (NeurIPS 2025 · similarity 0.88)
- Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization (ICML 2025 · similarity 0.87)
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · similarity 0.87)
- Differentially Private Optimization with Sparse Gradients (NeurIPS 2024 · similarity 0.87)
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions (NeurIPS 2024 · similarity 0.87)
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.