Research map / Optimization / Nonconvex and smooth optimization
Second-Order Convergence in Private Stochastic 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 Gauss-PSGD, a perturbed SGD framework that uses model drift distance to detect saddle escape so it outputs a DP-SOSP directly, combined with an adaptive DP-SPIDER oracle to rectify prior DP-SOSP rates and extend to heterogeneous distributed learning.
Problem
Finding second-order stationary points under differential privacy in stochastic non-convex optimization, including distributed learning with heterogeneous data, where prior work had an incorrect error rate and needed a costly private model selection step.
Approach
Use the displacement of model iterates (model drift distance) as the saddle-escape criterion so that perturbed SGD directly outputs an approximate SOSP, leveraging inherent DP Gaussian noise for escape instead of extra injected noise, and an adaptive SPIDER oracle that queries full gradients based on cumulative drift.
Key results
- Ada-DP-SPIDER with Gauss-PSGD achieves alpha-SOSP with alpha = O~(1/n^{1/3} + (sqrt(d)/(n epsilon))^{2/5}), correcting the prior (sqrt(d)/(n epsilon))^{3/7} rate.
- Distributed variant gives the first DP-SOSP error bound under heterogeneous data: O~(1/(mn)^{1/3} + (sqrt(d)/(sqrt(m) n epsilon))^{2/5}).
- Private model selection in distributed high-dimensional settings degrades the error when d is large (constraint d <= min{(sqrt(m) n eps)^2, (sqrt(m) n eps)^{6/13}}).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the corrected error analysis with Ada-DP-SPIDER instead of the prior method | DP stochastic non-convex optimization · DP stochastic non-convex optimization | DP-SOSP error rate: \tilde{O}\big(\frac{1}{n^{1/3}} + \big(\frac{\sqrt{d}}{\epsilon n}\big)^{3/7}\big) -> \tilde{O}\left(\frac{1}{n^{1/3}} + | Helped |
| Extend Ada-DP-SPIDER to distributed clients | Gauss-PSGD · Distributed DP-SOSP with heterogeneous data | DP-SOSP error rate | Helped |
| Use model drift distance as the saddle-point escape criterion instead of function-value decrease | Gauss-PSGD · Non-convex stochastic optimization | SOSP identification | Helped |
| Avoid a separate private model selection procedure | Distributed DP-SOSP learning · Distributed DP-SOSP with heterogeneous data | selected-point SOSP error | Helped |
Surprising findings
- Directly correcting the analysis of the prior DP-SOSP method yields only a weaker (alpha, alpha^{2/5})-SOSP guarantee.
- Private model selection can degrade the overall error rate in high-dimensional distributed settings.
Limitations
- Assumes unbiased gradient oracle; does not cover gradient clipping, which is standard in DP training.
- Lower bound gap: the upper bound is not known to match the DP lower bound for non-convex SOSP.
- Analysis is theoretical; the numerical experiments are only briefly described.
Experimental setup
Metrics: convergence error rate gradient complexity
Baselines: DP-SOSP prior method with AboveThreshold selection DIFF2
Builds on: SPIDER perturbed gradient descent DIFF2 AboveThreshold
Closest papers by meaning
- Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations (ICLR 2025 · similarity 0.89)
- Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates (AAAI 2025 · similarity 0.88)
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions (NeurIPS 2024 · similarity 0.88)
- Adaptive Batch Size for Privately Finding Second-Order Stationary Points (ICLR 2025 · similarity 0.88)
- Dealing With Unbounded Gradients in Stochastic Saddle-point Optimization (ICML 2024 · similarity 0.88)
- How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimization (ICML 2024 · similarity 0.88)
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.