Research map / Optimization / Nonconvex and smooth optimization
Adaptive Batch Size for Privately Finding Second-Order Stationary Points
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 private SpiderBoost-based SOSP finder with tree mechanism, adaptive batch sizes proportional to iterate movement, and a corrected Hessian-based saddle escape, achieving alpha = Õ(1/n^{1/3} + (sqrt(d)/(nε))^{1/2}) matching the best private FOSP rate.
Problem
Finding second-order stationary points (SOSP) of smooth non-convex population objectives under differential privacy is harder than FOSP by existing bounds, and a prior SOSP claim (Ganesh et al., 2023) has an issue in its saddle escape procedure.
Approach
Combine the tree mechanism with adaptive batch sizes B_t proportional to ||x_t - x_{t-1}|| for gradient-difference oracles, and escape saddles using stochastic power iteration with privately estimated Hessians, so privately finding an SOSP costs no more than finding an FOSP.
Key results
- Achieves alpha = Õ(1/n^{1/3} + (sqrt(d)/(nε))^{1/2}) for finding an SOSP under (ε,δ)-DP, matching the best private FOSP rate.
- Corrects the saddle escape issue in Ganesh et al. (2023), whose direct fix yields only a weaker minimum-eigenvalue bound.
- Treating B, G, M, rho as constants recovers alpha = Õ((sqrt(d)/(nε))^{1/2} + 1/n^{1/3}).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive batch sizes for gradient-difference estimates together with the tree mechanism | SpiderBoost-based private SOSP method · Private SOSP | alpha-SOSP error: (\frac{\sqrt{d}}{n\varepsilon})^{3/7} -> (\frac{\sqrt{d}}{n\varepsilon})^{1/2} | Helped |
| Use adaptive batch sizes for gradient-difference estimates (ablation) | SpiderBoost-based private SOSP method with the tree mechanism · Private SOSP gradient estimation | gradient-estimation accuracy | Helped |
| Replace adaptive batch sizes with a fixed batch size (ablation) | SpiderBoost-based private SOSP method using the tree mechanism · Private SOSP | alpha-SOSP error | Hurt |
| Replace the Gaussian mechanism with the tree mechanism while keeping a fixed batch size (ablation) | SpiderBoost-based private SOSP method · Private SOSP | gradient-estimation accuracy | No clear effect |
| Replace the tree mechanism with the Gaussian mechanism (ablation) | SpiderBoost-based private SOSP method · Private SOSP gradient estimation | gradient-estimation accuracy | Hurt |
Surprising findings
- Private SOSP finding appears achievable at no additional rate cost relative to private FOSP finding.
Limitations
- Non-private 1/n^{1/3} term is not improved in low dimension; open question.
- Improvement mainly affects privacy-dependent terms; results rely on smoothness, Hessian-Lipschitz, and bounded-gradient assumptions.
- Some alternative bounds require exponential running time, which is impractical.
Experimental setup
Metrics: convergence rate alpha as a function of n, d, epsilon
Baselines: Ganesh et al. (2023) private SOSP private FOSP state-of-the-art bound
Builds on: SpiderBoost Ganesh et al. 2023 private SOSP tree mechanism Gaussian mechanism
Closest papers by meaning
- 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.85)
- Private Zeroth-Order Nonsmooth Nonconvex Optimization (ICLR 2024 · similarity 0.84)
- The Computational Complexity of Finding Second-Order Stationary Points (ICML 2024 · similarity 0.84)
- Private Zeroth-Order Optimization with Public Data (NeurIPS 2025 · similarity 0.84)
- Optimal Best Arm Identification under Differential Privacy (NeurIPS 2025 · similarity 0.84)
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.