改进隐私保护下寻找二阶驻点的算法，效果媲美一阶驻点。
Adaptive Batch Size for Privately Finding Second-Order Stationary Points
- 采用自适应批量大小与二叉树机制，修正原有方法缺陷。
- 隐私条件下找到二阶驻点的误差上界为 $O(\frac{1}{n^{1/3}} + (\frac{\sqrt{d}}{nε})^{1/2})$。
- 成果接近最优一阶驻点性能，适合关注隐私优化的机器学习研究者。
在差分隐私约束下，找到一阶驻点（FOSP）与二阶驻点（SOSP）之间仍存在差距，且尚不清楚后者是否更难。此前工作声称可实现 $α=O(\frac{1}{n^{1/3}} + (\frac{\sqrt{d}}{nε})^{3/7})$，但其鞍点逃逸过程存在分析漏洞，导致保证弱化。本文基于 SpiderBoost 框架，提出使用自适应批量大小和二叉树机制的新方法，不仅修复了该问题，还实现了 $α=O(\frac{1}{n^{1/3}} + (\frac{\sqrt{d}}{nε})^{1/2})$，达到当前最优一阶驻点水平，表明在隐私保护下寻找二阶驻点可能无需额外代价。
原文摘要 · Abstract (English)
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(\frac{1}{n^{1/3}}+(\frac{\sqrt{d}}{nε})^{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(\frac{1}{n^{1/3}}+(\frac{\sqrt{d}}{nε})^{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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。