Adaptive Batch Size for Privately Finding Second-Order Stationary Points
Not on the map. Why?
Abstract (arXiv)
There is a gap between finding a first-order stationary point (FOSP) and a second-order stationary point (SOSP) under differential privacy constraints, and it remains unclear whether privately finding an SOSP is more challenging than finding an FOSP. Specifically, Ganesh et al. (2023) claimed that an α-SOSP can be found with α=O(frac1n1/3+(frac√dnε)3/7), where n is the dataset size, d is the dimension, and ε is the differential privacy parameter. However, a recent analysis revealed an issue in their saddle point escape procedure, leading to weaker guarantees. Building on the SpiderBoost algorithm framework, we propose a new approach that uses adaptive batch sizes and incorporates the binary tree mechanism. Our method not only corrects this issue but also improves the results for privately finding an SOSP, achieving α=O(frac1n1/3+(frac√dnε)1/2). This improved bound matches the state-of-the-art for finding a FOSP, suggesting that privately finding an SOSP may be achievable at no additional cost.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 26 of its 39 references that are in the map. First posted on arXiv 10 Oct 2024.
Builds on
26 of 39 references.
References · 26
- 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
- 2015An Introduction to Matrix Concentration Inequalitiescited by 397
- 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
- 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
- 2017How to Escape Saddle Points Efficientlycited by 285
- 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
- 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
- 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
- 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 106
- 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
- 2021Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 51
- 2021Oracle Complexity in Nonsmooth Nonconvex Optimizationcited by 39
14 more
- 2021A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensionscited by 39
- 2022Faster Rates of Convergence to Stationary Points in Differentially Private Optimizationcited by 32
- 2023Deterministic Nonsmooth Nonconvex Optimizationcited by 26
- 2022Constant matters: Fine-grained Complexity of Differentially Private Continual Observationcited by 23
- 2023ReSQueing Parallel and Private Stochastic Convex Optimizationcited by 17
- 2016Big Batch SGD: Automated Inference using Adaptive Batch Sizescited by 13
- 2022Private Convex Optimization in General Normscited by 13
- 2023Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Riskscited by 12
- 2022Momentum Aggregation for Private Non-convex ERMcited by 10
- 2024How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimizationcited by 10
- 2024Private Zeroth-Order Nonsmooth Nonconvex Optimizationcited by 8
- 2023Differentially Private Optimization for Smooth Nonconvex ERMcited by 5
- 2023Differentially Private Non-Convex Optimization under the KL Condition with Optimal Ratescited by 4
- 2024Improved Sample Complexity for Private Nonsmooth Nonconvex Optimizationcited by 4
Built on by
Citing papers per year: 2025: 1; 2026: 1.
2 papers.