Adaptive Batch Size for Privately Finding Second-Order Stationary Points

## Abstract

Abstract 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) demonstrated that an α 𝛼 \alpha italic_α -SOSP can be found with α = O ~ ⁢ ( 1 n 1 / 3 + ( d n ⁢ ε ) 3 / 7 ) 𝛼 ~ 𝑂 1 superscript 𝑛 1 3 superscript 𝑑 𝑛 𝜀 3 7 \alpha=\tilde{O}(\frac{1}{n^{1/3}}+(\frac{\sqrt{d}}{n\varepsilon})^{3/7}) italic_α = over~ start_ARG italic_O end_ARG ( divide start_ARG 1 end_ARG start_ARG italic_n start_POSTSUPERSCRIPT 1 / 3 end_POSTSUPERSCRIPT end_ARG + ( divide start_ARG square-root start_ARG italic_d end_ARG end_ARG start_ARG italic_n italic_ε end_ARG ) start_POSTSUPERSCRIPT 3 / 7 end_POSTSUPERSCRIPT ) , where n 𝑛 n italic_n is the dataset size, d 𝑑 d italic_d is the dimension, and ε 𝜀 \varepsilon italic_ε is the differential privacy parameter. Building on the SpiderBoost algorithm framework, we propose a new approach that uses adaptive batch sizes and incorporates the binary tree mechanism. Our method improves the results for privately finding an SOSP, achieving α = O ~ ⁢ ( 1 n 1 / 3 + ( d n ⁢ ε ) 1 / 2 ) 𝛼 ~ 𝑂 1 superscript 𝑛 1 3 superscript 𝑑 𝑛 𝜀 1 2 \alpha=\tilde{O}(\frac{1}{n^{1/3}}+(\frac{\sqrt{d}}{n\varepsilon})^{1/2}) italic_α = over~ start_ARG italic_O end_ARG ( divide start_ARG 1 end_ARG start_ARG italic_n start_POSTSUPERSCRIPT 1 / 3 end_POSTSUPERSCRIPT end_ARG + ( divide start_ARG square-root start_ARG italic_d end_ARG end_ARG start_ARG italic_n italic_ε end_ARG ) start_POSTSUPERSCRIPT 1 / 2 end_POSTSUPERSCRIPT ) . This improved bound matches the state-of-the-art for finding an FOSP, suggesting that privately finding an SOSP may be achievable at no additional cost.

## 1 Introduction

Privacy concerns have gained increasing attention with the rapid development of artificial intelligence and modern machine learning, particularly the widespread success of large language models. Differential privacy (DP) has become the standard notion of privacy in machine learning since it was introduced by Dwork et al. (). Given two neighboring datasets, $\mathcal{D}$ and $\mathcal{D}^{\prime}$, differing by a single item, a mechanism $\mathcal{M}$ is said to be $(\varepsilon,\delta)$-differentially private if, for any event $\mathcal{X}$, it holds that:

$$ $\displaystyle\Pr[\mathcal{M}(\mathcal{D})\in\mathcal{X}]\leq e^{\varepsilon} \Pr[\mathcal{M}(\mathcal{D}^{\prime})\in\mathcal{X}]+\delta.$ $$

In this work, we focus on the stochastic optimization problem under the constraint of DP.
The loss function is defined below:

$$ $\displaystyle F_{\mathcal{P}}(x):=\operatorname*{\mathbb{E}}_{z\sim\mathcal{P} }f(x;z),$ $$

where the functions may be non-convex, the underlying distribution $\mathcal{P}$ is unknown, and we are given a dataset $\mathcal{D}=\{z_{i}\}_{i\in[n]}$ drawn i.i.d. from $\mathcal{P}$.
Notably, our goal is to design a private algorithm with provable utility guarantees under the i.i.d. assumption.

Minimizing non-convex functions is generally challenging and often intractable, but most models used in practice are not guaranteed to be convex. How, then, can we explain the success of optimization methods in practice?
One possible explanation is the effectiveness of Stochastic Gradient Descent (SGD), which is well-known to be able to find an $\alpha$-first-order stationary point (FOSP) of a non-convex function $f$—that is, a point $x$ such that $\|\nabla f(x)\|\leq\alpha$—within $O(1/\alpha^{2})$ steps (Nesterov, ).
However, FOSPs can include saddle points or even local maxima. Thus, we focus on finding second-order stationary points (SOSP), for the non-convex function $F_{\mathcal{P}}$.

Non-convex optimization has been extensively studied in recent years due to its central role in modern machine learning, and we now have a solid understanding of the complexity involved in finding FOSPs and SOSPs (Ghadimi and Lan, ; Agarwal et al., ; Carmon et al., ; Zhang et al., ). Variance reduction techniques have been shown to improve the theoretical complexity, leading to the development of several promising algorithms such as Spider (Fang et al., ), SARAH (Nguyen et al., ), and SpiderBoost (Wang et al., ).
More recently, private non-convex optimization has emerged as an active area of research (Wang et al., ; Arora et al., ; Gao and Wright, ; Ganesh et al., ; Lowy et al., ; Menart et al., ).

### 1.1 Our Main Result

In this work, we study how to find the SOSP of $F_{\mathcal{P}}$ privately.
Let us formally define the FOSP and the SOSP.
For more on Hessian Lipschitz continuity and related background, see the preliminaries in Section 2.

###### Definition 1.1 (FOSP) .

For $\alpha\geq 0$, we say a point $x$ is an $\alpha$-first-order stationary point ($\alpha$-FOSP) of a function $g$ if $\|\nabla g(x)\|\leq\alpha$.

###### Definition 1.2 (SOSP, Nesterov and Polyak ( 2006 ); Agarwal et al. ( 2017 ) ) .

For a function $g:\mathbb{R}^{d}\to\mathbb{R}$ which is $\rho$-Hessian Lipschitz, we say a point $x\in\mathbb{R}^{d}$ is $\alpha$-second-order stationary point ($\alpha$-SOSP) of $g$ if $\|\nabla g(x)\|_{2}\leq\alpha\;\bigwedge\;\nabla^{2}g(x)\succeq-\sqrt{\rho
\alpha}I_{d}$.

Given the dataset size of $n$, privacy parameters $\varepsilon,\delta$, and functions defined over $d$-dimension space, Ganesh et al. () proposed a private algorithm that can find an $\alpha_{S}$-SOSP for $F_{\mathcal{P}}$ with

$$ $\displaystyle\alpha_{S}=\tilde{O}\big{(}\frac{1}{n^{1/3}}+(\frac{\sqrt{d}}{n \varepsilon})^{3/7}\big{)}.$ $$

However, as shown in Arora et al. (), the state-of-the-art bound for privately finding an $\alpha_{F}$-FOSP is tighter: (^1^11As proposed by Lowy et al. (), allowing exponential running time enables the use of the exponential mechanism to find a warm start, which can further improve the bounds for both FOSP and SOSP.)

$$ $\displaystyle\alpha_{F}=\tilde{O}\big{(}\frac{1}{n^{1/3}}+(\frac{\sqrt{d}}{n \varepsilon})^{1/2}\big{)}$ $$

When the privacy parameter $\varepsilon$ is sufficiently small, we observe that $\alpha_{F}\ll\alpha_{S}$. This raises the question: is finding an SOSP under differential privacy constraints more difficult than finding an FOSP?

This work improves the results of Ganesh et al. ().
Specifically, we present an algorithm that finds an $\alpha$-SOSP with privacy guarantees, where:

$$ $\displaystyle\alpha=\tilde{O}(\alpha_{F})=\tilde{O}\big{(}\frac{1}{n^{1/3}}+( \frac{\sqrt{d}}{n\varepsilon})^{1/2}\big{)}.$ $$

This improved bound suggests that when we try to find the stationary point privately, we can find the SOSP for free under additional (standard) assumptions.

It is also worth noting that, our improvement primarily affects terms dependent on the privacy parameters.
In the non-private setting, as $\varepsilon\to\infty$ (i.e., without privacy constraints), all the results discussed above achieve a bound of $\tilde{O}(1/n^{1/3})$,
which matches the non-private lower bound established by Arjevani et al. () in high-dimensional settings (where $d\geq\tilde{\Omega}(1/\alpha^{4})$).
However, to our knowledge, whether this non-private term of $\tilde{O}(1/n^{1/3})$ can be further improved in low dimension remains an open question.

###### Definition 1.1 (FOSP) .

###### Definition 1.2 (SOSP, Nesterov and Polyak ( 2006 ); Agarwal et al. ( 2017 ) ) .

### 1.2 Overview of Techniques

In this work, we build on the SpiderBoost algorithm framework, similar to prior approaches (Arora et al., ; Ganesh et al., ), to find second-order stationary points (SOSP) privately.
At a high level, our method leverages two types of gradient oracles: $\mathcal{O}_{1}(x)\approx\nabla f(x)$, which estimates the gradient at point $x$, and $\mathcal{O}_{2}(x,y)\approx\nabla f(x)-\nabla f(y)$, which estimates the gradient difference between two points, $x$ and $y$. When performing gradient descent, to compute the gradient estimator $\nabla_{t}$ at point $x_{t}$, we can either use $\nabla_{t}=\mathcal{O}_{1}(x_{t})$ for a direct estimate, or $\nabla_{t}=\nabla_{t-1}+\mathcal{O}_{2}(x_{t},x_{t-1})$ to update based on the previous gradient.
In our setting, $\mathcal{O}_{1}$ is more accurate but incurs higher computational or privacy costs.

The approach in Arora et al. () adopts SpiderBoost by querying $\mathcal{O}_{1}$ periodically: they call $\mathcal{O}_{1}$ once and then use $\mathcal{O}_{2}$ for $q$ subsequent queries, controlled by a hyperparameter $q$. Their method ensures the gradient estimators are sufficiently accurate on average, which works well for finding first-order stationary points (FOSP). However, finding an SOSP, where greater precision is required, presents additional challenges when relying on average-accurate gradient estimators.

To address this, Ganesh et al. () introduced a variable called $\mathrm{drift}_{t}:=\sum_{i=t_{0}+1}^{t}\|x_{i}-x_{i-1}\|^{2}$, where $t_{0}$ is the index of the last iteration when $\mathcal{O}_{1}$ was queried. If $\mathrm{drift}_{t}$ remains small, the gradient estimator stays accurate enough, allowing further queries of $\mathcal{O}_{2}$. However, if $\mathrm{drift}_{t}$ grows large, the gradient estimator’s accuracy deteriorates, signaling the need to query $\mathcal{O}_{1}$ for a fresh, more accurate estimate. This modification enables the algorithm to maintain the precision necessary for privately finding an SOSP.

Our improvement introduces two new components: the use of the tree mechanism instead of using the Gaussian mechanism as in Ganesh et al. (), and the implementation of adaptive batch sizes for constructing $\mathcal{O}_{2}$.

In the prior approach using the Gaussian mechanism, a noisy gradient estimator $\nabla_{t-1}$ is computed, and the next estimator is updated via $\nabla_{t}=\nabla_{t-1}+\mathcal{O}_{2}(x_{t},x_{t-1})+g_{t}$, where $g_{t}$ is Gaussian noise added to preserve privacy. Over multiple iterations, the accumulation of noise $\sum g_{t}$ can severely degrade the accuracy of the gradient estimator, requiring frequent re-queries of $\mathcal{O}_{1}$. On the other hand, the tree mechanism mitigates this issue when frequent queries to $\mathcal{O}_{2}$ are needed.

However, simply replacing the Gaussian mechanism with the tree mechanism and using a fixed batch size does not yield optimal results.
In worst-case scenarios, where the function’s gradients are large, the $\mathrm{drift}$ grows quickly, necessitating frequent calls to $\mathcal{O}_{1}$, which diminishes the advantages of the tree mechanism.

To address this, we introduce adaptive batch sizes. In Ganesh et al. (), the oracle $\mathcal{O}_{2}$ is constructed by drawing a fixed batch of size $B$ from the unused dataset and outputting $\mathcal{O}_{2}(x_{t},x_{t-1}):=\sum_{z\in S_{t}}\frac{\nabla f(x_{t};z)-
\nabla f(x_{t-1};z)}{B}$. Given an upper bound on $\mathrm{drift}$, they guaranteed that $\|x_{t}-x_{t-1}\|\leq D$ for some parameter $D$, thereby bounding the sensitivity of $\mathcal{O}_{2}$.

In contrast, we dynamically adjust the batch size in proportion to $\|x_{t}-x_{t-1}\|$, setting $B_{t}\propto\|x_{t}-x_{t-1}\|$, and compute $\mathcal{O}_{2}(x_{t},x_{t-1}):=\sum_{z\in S_{t}}\frac{\nabla f(x_{t};z)-
\nabla f(x_{t-1};z)}{B_{t}}$. Fixed batch sizes present two drawbacks: (i) when $\|x_{t}-x_{t-1}\|$ is large, the gradient estimator has higher sensitivity and variance, leading to worse estimate accuracy; (ii) when $\|x_{t}-x_{t-1}\|$ is small, progress in terms of function value decrease is limited. Using a fixed batch size forces us to handle both cases simultaneously: we must add noise and analyze accuracy assuming a worst-case large $\|x_{t}-x_{t-1}\|$, but for utility analysis, we pretend $\|x_{t}-x_{t-1}\|$ is small to examine the function value decrease. The adaptive batch size resolves this paradox: it allows us to control sensitivity and variance adaptively. When $\|x_{t}-x_{t-1}\|$ is small, we decrease the batch size but can still control the variance and sensitivity; when it is small, the function value decreases significantly, aiding in finding an SOSP.

By combining the tree mechanism with adaptive batch sizes, we improve the accuracy of gradient estimation and achieve better results for privately finding an SOSP.

### 1.3 Other Related Work

A significant body of literature on private optimization focuses on the convex setting, where it is typically assumed that each function $f(;z)$ is convex for any $z$ in the universe (e.g., (Chaudhuri et al., ; Bassily et al., , ; Feldman et al., ; Asi et al., ; Kulkarni et al., ; Carmon et al., )).

The tree mechanism, originally introduced by the differential privacy (DP) community (Dwork et al., ; Chan et al., ) for the continual observation,
has inspired tree-structure private optimization algorithms like Asi et al. (); Bassily et al. (); Arora et al. (); Zhang et al. ().
Some prior works have explored adaptive batch size techniques in optimization. For instance, De et al. () introduced adaptive batch sizing for stochastic gradient descent (SGD), while Ji et al. () combined adaptive batch sizing with variance reduction techniques to modify SVRG and Spider algorithms. However, these works’ motivations and approaches to setting adaptive batch sizes differ from ours. To the best of our knowledge, we are the first to propose using adaptive batch sizes in the context of optimization under differential privacy constraints.

Most of the non-convex optimization literature assumes that the functions being optimized are smooth. Recent work has begun addressing non-smooth, non-convex functions as well, as seen in Zhang et al. (); Kornowski and Shamir (); Davis et al. (); Jordan et al. ().

## 2 Preliminaries

Throughout the paper, we use $\|\cdot\|$ to represent both the $\ell_{2}$ norm of a vector and the operator norm of a matrix when there is no confusion.

###### Definition 2.1 (Lipschitz, Smoothness and Hessian Lipschitz) .

Let $\mathcal{K}\subseteq\mathbb{R}^{d}$. Given a twice differentiable function $f:\mathcal{K}\to\mathbb{R}$, we say $f$ is $G$-Lipschitz, if for all $x_{1},x_{2}\in\mathcal{K}$,
$|f(x_{1})-f(x_{2})|\leq G\|x_{1}-x_{2}\|$;
we say $f$ is $M$-smooth, if for all $x_{1},x_{2}\in\mathcal{K}$,
$\|\nabla f(x_{1})-\nabla f(x_{2})\|\leq M\|x_{1}-x_{2}\|$,
and we say the function $f$ is $\rho$-Hessian Lipschitz, if for all $x_{1},x_{2}\in\mathcal{K}$, we have $\|\nabla^{2}f(x_{1})-\nabla^{2}f(x_{2})\|\leq\rho\|x_{1}-x_{2}\|.$

###### Definition 2.1 (Lipschitz, Smoothness and Hessian Lipschitz) .

### 2.1 Other Techniques

As mentioned in the introduction, we use the tree mechanism (Algorithm 1) to privatize the algorithm, whose formal guarantee is stated below:

###### Theorem 2.2 (Tree Mechanism, Dwork et al. ( 2010 ); Chan et al. ( 2011 ) ) .

Let $\mathcal{Z}_{1},\cdots,\mathcal{Z}_{\Sigma}$ be dataset spaces, and $\mathcal{X}$ be the state space.
Let $\mathcal{M}_{i}:\mathcal{X}^{i-1}\times\mathcal{Z}_{i}\to\mathcal{X}$ be a sequence of algorithms for $i\in[\Sigma]$.
Let $\mathcal{A}:\mathcal{Z}^{(1:\Sigma)}\to\mathcal{X}^{\Sigma}$ be the algorithm that given a dataset $Z_{1:\Sigma}\in\mathcal{Z}^{(1:\Sigma)}$, sequentially computes $X_{i}=\sum_{j=1}^{i}\mathcal{M}_{i}(X_{1:j-1},Z_{i})+\mathrm{TREE}(i)$ for $i\in[\Sigma]$, and then outputs $X_{1:\Sigma}$.

Suppose for all $i\in[\Sigma]$, and neighboring $Z_{1:\Sigma},Z_{1:\Sigma}^{\prime}\in\mathcal{Z}^{(1:\Sigma)},\|\mathcal{M}_{i
}(X_{1:i-1},Z_{i})-\mathcal{M}_{i}(X_{1:i-1},Z_{i}^{\prime})\|\leq s$ for all auxiliary inputs $X_{1:i-1}\in\mathcal{X}^{i-1}$. Then setting $\sigma=\frac{4s\sqrt{\log\Sigma\log(1/\delta)}}{\varepsilon}$, Algorithm 1 is $(\varepsilon,\delta)$-DP.
Furthermore, with probability at least $1-\Sigma\cdot\iota$,
for all $t\in[\Sigma]:\|\mathrm{TREE}(t)\|\lesssim\sqrt{d\log(1/\iota)}\sigma$.

We also need the concentration inequality for norm-subGaussian random vectors.

###### Definition 2.3 (SubGaussian, and Norm-SubGaussian) .

We say a random vector $x\in\mathbb{R}^{d}$ is SubGaussian ($\mathrm{SG}(\zeta)$) if there exists a positive constant $\zeta$ such that $\operatorname*{\mathbb{E}}e^{\langle v,x-\operatorname*{\mathbb{E}}x\rangle}
\leq e^{\|v\|^{2}\zeta^{2}/2},\;\;\forall v\in\mathbb{R}^{d}$.
We say
$x\in\mathbb{R}^{d}$ is norm-SubGaussian ($\mathrm{nSG}(\zeta)$) if there exists $\zeta$ such that $\Pr[\|x-\operatorname*{\mathbb{E}}x\|\geq t]\leq 2e^{-\frac{t^{2}}{2\zeta^{2}}
},\forall t\in\mathbb{R}$.

###### Lemma 2.4 (Hoeffding type inequality for norm-subGaussian, Jin et al. ( 2019 ) ) .

Let $x_{1},\cdots,x_{k}\in\mathbb{R}^{d}$ be random vectors, and for each $i\in[k]$, $x_{i}\mid\mathcal{F}_{i-1}$ is zero-mean $\mathrm{nSG}(\zeta_{i})$ where $\mathcal{F}_{i}$ is the corresponding filtration.
Then there exists an absolute constant $c$ such that for any $\delta>0$, with probability at least $1-\omega$,
$\|\sum_{i=1}^{k}x_{i}\|\leq c\cdot\sqrt{\sum_{i=1}^{k}\zeta_{i}^{2}\log(2d/
\omega)}$,
which means $\sum_{i=1}^{k}x_{i}$ is $\mathrm{nSG}(\sqrt{c\log(d)\,\sum_{i=1}^{k}\zeta_{i}^{2}})$.

###### Theorem 2.5 (Matrix Bernstein Inequality, Tropp et al. ( 2015 ) ) .

Consider a finite sequence of independent, random matrices $X_{1},\cdots,X_{n}$ with common dimensions $d\times d$ and $\operatorname*{\mathbb{E}}[X_{i}]=0,\|X_{i}\|\leq L$ a.s., $\forall i$.
Let $\sigma^{2}=\|\sum_{i=1}^{n}\operatorname*{\mathbb{E}}[X_{i}^{2}]\|$. Let $S=\sum_{i=1}^{n}X_{i}$.
Then for any $t\geq 0$, we have

$$ $\displaystyle\Pr[\|S\|\geq t]\leq d\cdot\exp(-\frac{-t^{2}}{\sigma^{2}+Lt/3}).$ $$

Figure: Algorithm 1 Tree Mechanism

###### Theorem 2.2 (Tree Mechanism, Dwork et al. ( 2010 ); Chan et al. ( 2011 ) ) .

###### Definition 2.3 (SubGaussian, and Norm-SubGaussian) .

###### Lemma 2.4 (Hoeffding type inequality for norm-subGaussian, Jin et al. ( 2019 ) ) .

###### Theorem 2.5 (Matrix Bernstein Inequality, Tropp et al. ( 2015 ) ) .

## 3 SOSP

We make the following assumption for our main result.

###### Assumption 3.1 .

Let $G,\rho,M,B>0$.
Any function drawn from $\mathcal{P}$ is $G$-Lipschitz, $\rho$-Hessian Lipschitz, and $M$-smooth, almost surely.
Moreover, we are given a public initial point $x_{0}$ such that $F_{\mathcal{P}}(x_{0})-\inf_{x}F_{\mathcal{P}}(x)\leq B$.

We modify the Stochastic SpiderBoost used in Ganesh et al. () and state it in Algorithm 2.
The following standard lemma plays a crucial role in finding stationary points of smooth functions:

###### Lemma 3.2 .

Assume $F$ is $M$-smooth and let $\eta=1/M$.
Let $x_{t+1}=x_{t}-\eta\widetilde{\nabla}$.
Then we have
$F(x_{t+1})\leq F(x_{t})+\eta\|\widetilde{\nabla}_{t}\|\cdot\|\nabla F(x_{t})-
\widetilde{\nabla}_{t}\|-\frac{\eta}{2}\|\widetilde{\nabla}_{t}\|^{2}.$
Moreover, if $\|\nabla F(x_{t})\|\geq\gamma$ and $\|\widetilde{\nabla}_{t}-\nabla F(x_{t})\|\leq\gamma/4$, we have

$$ $\displaystyle F(x_{t+1})-F(x_{t})\leq-\eta\|\widetilde{\nabla}_{t}\|^{2}/16.$ $$

###### Proof.

By the assumption of the smoothness, we know

$$ $\displaystyle F(x_{t+1})$ $\displaystyle\leq F(x_{t})+\langle\nabla F(x_{t}),x_{t+1}-x_{t}\rangle+\frac{M }{2}\|x_{t+1}-x_{t}\|^{2}$ $\displaystyle=F(x_{t})-\eta/2\|\widetilde{\nabla}_{t}\|^{2}-\langle\nabla F(x_ {t})-\widetilde{\nabla}_{t},\eta\widetilde{\nabla}_{t}\rangle$ $\displaystyle\leq F(x_{t})+\eta\|\nabla F(x_{t})-\widetilde{\nabla}_{t}\|\cdot \|\widetilde{\nabla}_{t}\|-\frac{\eta}{2}\|\widetilde{\nabla}_{t}\|^{2}.$ $$

When $\|\nabla F(x_{t})\|\geq\gamma$ and $\|\widetilde{\nabla}_{t}-\nabla F(x_{t})\|\leq\gamma/4$, the conclusion follows from the calculation.

∎

One of the main challenges to finding the SOSP, compared with finding the FOSP, is showing the algorithm can escape from saddle points, which was addressed by previous results (e.g.,Jin et al. ()) and was established in the DP literature as well:

###### Lemma 3.3 (Essentially from Wang et al. ( 2019a ) ) .

Under Assumption 3.1, run SGD iterations $x_{t+1}=x_{t}-\eta\nabla_{t}$, with step size $\eta=1/M$.
Suppose $x_{0}$ is a saddle point satisfying $\|\nabla F(x_{0})\|\leq\alpha$ and $\textup{smin}(\nabla^{2}F(x_{0}))\leq-\sqrt{\rho\alpha}$, $\alpha=\gamma\log^{3}(dBM/\rho\iota)$.
If $\nabla_{0}=\nabla F(x_{0})+\zeta_{1}+\zeta_{2}$ where $\|\zeta_{1}\|\leq\gamma$, $\zeta_{2}\sim\mathcal{N}(0,\frac{\gamma^{2}}{d\log(d/\iota)}I_{d})$, and $\|\nabla_{t}-\nabla F(x_{t})\|\leq\gamma$ for all $t\in[\Gamma]$, with probability at least $1-\iota$, one has
$F(x_{\Gamma})-F(x_{0})\leq-\Omega\big{(}\frac{\gamma^{3/2}}{\sqrt{\rho}\log^{3
}(\frac{dMB}{\rho\gamma\iota})}\big{)},$
where $\Gamma=\frac{M\log(\frac{dMB}{\rho\gamma\iota})}{\sqrt{\rho\gamma}}$.

Lemma 3.3 suggests that, if we meet a saddle point, then after the following $\tilde{O}(1/\sqrt{\gamma})$ steps, the function value will decrease by at least $\tilde{\Omega}(\gamma^{3/2})$.
This means the function value decreases by $\tilde{\Omega}(\gamma^{2})$ on average for each step.
Similar to the proof in Ganesh et al. (), we have the following guarantee of Stochastic SpiderBoost:

###### Proposition 3.4 .

Under Assumption 3.1 and with gradient oracles such that $\|\widetilde{\nabla}_{t}-\nabla F(x_{t})\|\leq\gamma$ for any $t\in[T]$, setting
$T=\tilde{O}(B/\eta\gamma^{2})$ and $\zeta=\gamma/\sqrt{\log(d/\iota)}$ and supposing it does not halt before completing all $T$ iterations, with probability at least $1-T\iota$, at least one point in the output set $\{x_{1},\cdots,x_{T}\}$ of Algorithm 2 is $\tilde{O}(\gamma)$-SOSP.

The proof intuition of Proposition 3.4 is, if we do not find an $O(\gamma)$-SOSP, then on average, the function value will at least decrease by $\Omega(\eta/\gamma^{2})$.
As we know $F_{\mathcal{P}}(x_{0})\leq F_{\mathcal{P}}^{*}+B$, hence $O(B/\eta\gamma^{2})$ steps can ensure we find an $O(\gamma)$-SOSP.
See more discussion on Proposition 3.4 in the Appendix.

Figure: Algorithm 2 Stochastic Spider

Algorithm 2 follows the SpiderBoost framework. We either query $\mathcal{O}_{1}$ to estimate the gradient itself or query $\mathcal{O}_{2}$ to estimate the gradient difference over the last consecutive points.
The term $\mathrm{drift}$ controls the estimated error. When $\mathrm{drift}_{t}$ is small, we know $\Delta_{t}$ is still a good estimator, and when $\mathrm{drift}_{t}$ is large, we draw a fresh estimator from $\mathcal{O}_{1}$.
The term $\mathrm{frozen}$ is used for the technical purpose of applying Lemma 3.3.
When we meet a potential saddle point, we add Gaussian noise $g_{t}$ to escape from the saddle point and set $\mathrm{frozen}$ to be $\Gamma$; this ensures that we won’t add the Gaussian again in the following $\Gamma$ steps.

###### Assumption 3.1 .

###### Lemma 3.2 .

###### Proof.

###### Lemma 3.3 (Essentially from Wang et al. ( 2019a ) ) .

###### Proposition 3.4 .

### 3.1 Constructing Private Gradient Oracles

We construct the gradient oracles below in Algorithm 3.

Figure: Algorithm 3 gradient oracles

###### Lemma 3.5 (Gradient oracles with bounded error) .

Under assumption 3.1, let $\iota>0$ and use Algorithm 3 as instantiations of $\mathcal{O}_{1}$ and $\mathcal{O}_{2}$.
If $\mathcal{D}$ is i.i.d. drawn from distribution $\mathcal{P}$,
we have:
$(1)$ for any $x_{t}$, we have $\operatorname*{\mathbb{E}}[\mathcal{O}_{1}(x_{t})]=\nabla F(x_{t})$ and

$$ $\displaystyle\Pr[\|\mathcal{O}_{1}(x_{t})-\nabla F(x_{t})\|\geq\zeta_{1}]\leq\iota,$ $$

where $\zeta_{1}=O((G\sqrt{\log(d/\iota)/b})$.
$(2)$ for any $x_{t},x_{t-1}$, we have $\operatorname*{\mathbb{E}}[\mathcal{O}_{2}(x_{t},x_{t-1})]=\nabla F(x_{t})-
\nabla F(x_{t-1})$ and

$$ $\displaystyle\Pr[\|\mathcal{O}_{2}(x_{t},x_{t-1})-(\nabla F(x_{t})-\nabla F(x_ {t-1}))\|\geq\zeta_{2}]\leq\iota,$ $$

where $\zeta_{2}=O(M\|x_{t}-x_{t-1}\|\sqrt{\log(d/\iota)/b_{t}})$.

###### Proof.

For each data $z\sim\mathcal{P}$, we know

$$ $\displaystyle\operatorname*{\mathbb{E}}\nabla f(x_{t};z)-\nabla F(x_{t})=0, \quad\|\nabla f(x_{t};z)-\nabla F(x_{t})\|\leq 2G.$ $$

Then the conclusion follows from Lemma 2.4.

Similarly, for each data $z\sim\mathcal{P}$, we know

$$ $\displaystyle\operatorname*{\mathbb{E}}(\nabla f(x_{t};z)-\nabla f(x_{t-1};z)) -(\nabla F(x_{t};z)-\nabla F(x_{t-1};z))=0,$ $\displaystyle\|(\nabla f(x_{t};z)-\nabla f(x_{t-1};z))-(\nabla F(x_{t};z)- \nabla F(x_{t-1};z))\|\leq 2M\|x_{t}-x_{t-1}\|.$ $$

The statement (2) also follows from Lemma 2.4.
∎

From now on, we adopt Algorithm 3 as the gradient oracles for Line 5 and Line 7 respectively in Algorithm 2, and we set $\eta=1/M$.
We then bound the error between gradient estimator $\nabla_{t}$ and the true gradient $\nabla F(x_{t})$ for Algorithm 2.

###### Lemma 3.6 .

Suppose the dataset is drawn i.i.d. from the distribution $\mathcal{P}$.
For any $1\leq t\leq T$ and letting $\tau_{t}\leq t$ be the largest integer such that $\mathrm{drift}_{\tau_{t}}$ is set to be 0, with probability at least $1-T\iota$, for some universal constant $C>0$, we have

$$ $\displaystyle\|\nabla_{t}-\nabla F(x_{t})\|^{2}\leq C(\frac{G^{2}}{b}+\sum_{i= \tau_{t}+1}^{t}M^{2}\|x_{i}-x_{i-1}\|^{2}/b_{i})\log(Td/\iota).$ (1) $$

###### Proof.

We consider the case when $t=\tau_{t}$ first, i.e., we query $\mathcal{O}_{1}$ to get $\nabla_{t}$.
Then Equation (1) follows from Lemma 3.5.

When $t>\tau_{t}$, then for each $i$ such that $\tau_{t}<i\leq t$, we know conditional on $\nabla_{i-1}$, we have

$$ $\displaystyle\operatorname*{\mathbb{E}}[\Delta_{i}\mid\nabla_{i-1}]=\nabla F(x _{i})-\nabla F(x_{i-1}).$ $$

That is $\Delta_{i}-(\nabla F(x_{i})-\nabla F(x_{i-1}))$ is zero-mean and $\mathrm{nSG}(M\|x_{i}-x_{i-1}\|\sqrt{\log(dT/\iota)}/\sqrt{b_{i}})$ by applying Lemma 3.5.
Then Equation (1) follows from applying Lemma 2.4.
∎

Now, we consider the noise added from the tree mechanism to make the algorithm private.

###### Lemma 3.7 .

If we set $\sigma=(\frac{G}{b}+\max_{t}\frac{\|\widetilde{\nabla}_{t}\|}{b_{t}})\log(1/
\delta)/\varepsilon$, in the tree mechanism (Algorithm 1) and use Algorithm 3 as gradient oracles, then Algorithm 2 is $(\varepsilon,\delta)$-DP.

###### Proof.

It suffices to consider the sensitivity of the gradient oracles.

Consider the sensitivity of $\mathcal{O}_{1}$ first.
Let $\mathcal{O}(x_{t})^{\prime}$ denote the output with the neighboring dataset.
Then it is obvious that

$$ $\displaystyle\|\mathcal{O}_{1}(x_{t})-\mathcal{O}_{1}(x_{t})^{\prime}\|\leq \frac{G}{b}.$ $$

As for the sensitivity of $\mathcal{O}_{2}$, we have

$$ $\displaystyle\|\mathcal{O}_{2}(x_{t},x_{t-1})-\mathcal{O}_{2}(x_{t},x_{t-1})^{ \prime}\|\leq\frac{M\|x_{t}-x_{t-1}\|}{b_{t}}=\frac{\|\widetilde{\nabla}_{t}\| }{b_{t}}.$ $$

The privacy guarantee follows from the tree mechanism (Theorem 2.2).
∎

With the noise added from the tree mechanism in mind,
now we get the high-probability error bound of our gradient estimators $\widetilde{\nabla}_{t}$.

###### Lemma 3.8 .

In Algorithm 2, setting $b=G\sqrt{d}/\varepsilon\alpha+G^{2}/\alpha^{2},b_{t}=\max\{\frac{\|\widetilde{
\nabla}_{t}\|\cdot\sqrt{d}}{\alpha\varepsilon},\frac{\kappa\cdot\|\widetilde{
\nabla}_{t}\|}{\alpha^{2}},1\}$, and $\sigma=2\log(1/\delta)\alpha/\sqrt{d}$ correspondingly according to Lemma 3.7,
for each $t\in[T]$, we know Algorithm 2 is $(\varepsilon,\delta)$-DP, and with probability at least $1-\iota$, $\|\widetilde{\nabla}_{t}-\nabla F(x_{t})\|\leq\gamma$, where
$\gamma=\tilde{O}(\alpha).$

###### Proof.

By our setting of parameters, we know

$$ $\displaystyle(\frac{G}{b}+\max_{t}\frac{\|\widetilde{\nabla}_{t}\|}{b_{t}}) \leq 2\varepsilon\alpha/\sqrt{d}.$ $$

Then our choice of $\sigma$ ensures the privacy guarantee by Lemma 3.7.

For any $t\in[T]$, we have

$$ $\displaystyle\|\widetilde{\nabla}_{t}-\nabla F(x_{t})\|\leq\underbrace{\| \widetilde{\nabla}_{t}-\nabla_{t}\|}_{(1)}+\underbrace{\|\nabla_{t}-\nabla F(x _{t})\|}_{(2)}.$ $$

By Theorem 2.2, we know

$$ $\displaystyle(1)\leq\max_{t}\|\mathrm{TREE}(t)\|\leq\sigma\sqrt{d\log(T)}\leq \sigma\sqrt{d\log n}\lesssim\alpha\sqrt{\log n}\leq\tilde{O}(\gamma).$ $$

By Lemma 3.6 and our parameter settings, we have

$$ $\displaystyle\|\nabla_{t}-\nabla F(x_{t})\|^{2}\lesssim$ $\displaystyle(\alpha^{2}+\sum_{i=\tau_{t}+1}^{t}\|\widetilde{\nabla}_{t}\|^{2} /b_{t})\log(nd/\iota)$ $\displaystyle\lesssim$ $\displaystyle(\alpha^{2}+\sum_{i=\tau_{t}+1}^{t}\|\widetilde{\nabla}_{t}\| \cdot\min\{\frac{\alpha\varepsilon}{\sqrt{d}},\alpha^{2}/\kappa\})\log(nd/\iota)$ $\displaystyle\leq$ $\displaystyle(\alpha^{2}+\kappa\cdot\min\{\frac{\alpha\varepsilon}{\sqrt{d}}, \alpha^{2}/\kappa\})\log(nd/\iota)$ $\displaystyle\lesssim$ $\displaystyle\alpha^{2}\log(nd/\iota).$ $$

Hence we conclude that $(2)\lesssim\alpha\sqrt{\log(nd/\iota)}$, which completes the proof.
∎

We need to show that we can find an $\gamma$-SOSP before we use up all the functions.
We need the following technical Lemma:

###### Lemma 3.9 .

Consider the implementation of Algorithm 2.
Suppose the size of dataset $\mathcal{D}$ can be arbitrarily large with functions drawn i.i.d. from $\mathcal{P}$,
and we run the algorithm until finding an $\tilde{O}(\gamma)$-SOSP, then
with probability at least $1-T\iota$, the total number of functions we will use is bounded by

$$ $\displaystyle\tilde{O}\Big{(}\frac{bBM}{\kappa\gamma}+BM(\frac{\sqrt{d}}{ \gamma^{2}\varepsilon}+\frac{\kappa}{\gamma^{3}}+\frac{1}{\gamma^{2}})\Big{)}.$ $$

###### Proof.

By Proposition 3.4, setting $T=\tilde{O}(B/\eta\gamma^{2})$ suffices to find an $\tilde{O}(\gamma)$-SOSP.
Let $\{x_{1},\cdots,x_{t}\}$ be the outputs of the algorithms, where $t\leq T$ denotes the step we halt the algorithm.
We show

$$ $\displaystyle\sum_{i=1}^{t}\|\widetilde{\nabla}_{i}\|_{2}\lesssim\tilde{O}(BM/ \gamma).$ (2) $$

Denote the set $S:=\{i\in[t]:\|\widetilde{\nabla}_{i}\|\leq\gamma\}$.
As $|S|\leq T=\tilde{O}(B/\eta\gamma^{2})$, we know $\sum_{i\in S}\|\widetilde{\nabla}_{i}\|\leq\tilde{O}(B/\eta\gamma)$.

Now consider the set $S^{c}:=[t]\setminus S$ denoting the index of steps when the norm of the gradient estimator is large.
It suffices to bound $\sum_{i\in S^{c}}\|\widetilde{\nabla}_{i}\|_{2}$.

By Lemma 3.2, we know when $\|\widetilde{\nabla}_{i}\|\geq\gamma$, $F(x_{i+1})-F(x_{i})\leq-\eta\|\widetilde{\nabla}_{i}\|^{2}/16$, and when $\|\widetilde{\nabla}_{i}\|\leq\gamma,F(x_{i+1})\leq F(x_{i})+\eta\gamma^{2}$.
Given the bound on the function values, we know

$$ $\displaystyle\sum_{i\in S^{c}}\|\widetilde{\nabla}_{i}\|^{2}\leq\tilde{O}(B/ \eta).$ $$

Hence

$$ $\displaystyle\sum_{i\in S^{c}}\|\widetilde{\nabla}_{i}\|\leq\frac{\sum_{i\in S ^{c}}\|\widetilde{\nabla}_{i}\|^{2}}{\gamma}\leq\tilde{O}(\frac{B}{\eta\gamma}).$ $$

This completes the proof of Equation (2).

The total number of functions we used for $\mathcal{O}_{1}$ is upper bounded by $b\cdot\frac{\sum_{i\in[t]\|\widetilde{\nabla}_{i}\|}}{\kappa}=\tilde{O}(bBM/
\kappa\gamma)$.
The total number of functions we used for $\mathcal{O}_{2}$ is upper bounded as follows:

$$ $\displaystyle\sum_{i\in[t]}b_{t}\lesssim(\frac{\sqrt{d}}{\alpha\varepsilon}+ \frac{\kappa}{\alpha^{2}})\sum_{i\in[t]}\|\widetilde{\nabla}_{t}\|+T\leq BM \cdot\tilde{O}(\frac{\sqrt{d}}{\gamma^{2}\varepsilon}+\frac{\kappa}{\gamma^{3} }+\frac{1}{\gamma^{2}}).$ $$

This completes the proof.
∎

Given the dataset size requirement, we can get the final bound on finding SOSP.

###### Lemma 3.10 .

With $\mathcal{D}$ of size $n$ drawn i.i.d. from $\mathcal{P}$, setting $\kappa=\max\{\frac{\alpha\sqrt{d}}{\varepsilon},(BGM)^{1/3}\}$,

$$ $\displaystyle\alpha=O\Big{(}((BGM)^{1/3}+\sqrt{BM})(\frac{\sqrt{d}}{n \varepsilon})^{1/2}+\frac{B^{\frac{2}{9}}M^{\frac{2}{9}}G^{\frac{5}{9}}+B^{ \frac{4}{9}}M^{\frac{4}{9}}G^{\frac{1}{9}}}{n^{1/3}}+\frac{(MB)^{1/2}}{\sqrt{n }}\Big{)},$ $$

and other parameters as in Lemma 3.8, with probability at least $1-\iota$, at least one of the outputs of Algorithm 2 is $\gamma$-SOSP, with $\gamma=\tilde{O}(\alpha)$.

###### Proof.

By Lemma 3.9 and our parameter settings, we need

$$ $\displaystyle n\geq\tilde{\Omega}\big{(}\frac{bBM}{\kappa\gamma}+BM(\frac{ \sqrt{d}}{\gamma^{2}\varepsilon}+\frac{\kappa}{\gamma^{3}}+\frac{1}{\gamma^{2} })\big{)}.$ $$

First,

$$ $\displaystyle n\geq\tilde{\Omega}(\frac{bBM}{\kappa\gamma})=\Theta(\frac{BGM \sqrt{d}}{\kappa\varepsilon\gamma^{2}}+\frac{G^{2}BM}{\kappa\gamma^{3}}) \Leftarrow\gamma\geq\tilde{O}(\frac{(BGM)^{1/3}d^{1/4}}{\sqrt{n\varepsilon}}+ \frac{B^{\frac{2}{9}}M^{\frac{2}{9}}G^{\frac{5}{9}}}{n^{1/3}}).$ $$

Secondly,

$$ $\displaystyle n\geq\tilde{\Omega}(BM\sqrt{d}/\gamma^{2}\varepsilon)\Leftarrow \gamma\geq\tilde{O}(\sqrt{BM}(\frac{\sqrt{d}}{n\varepsilon})^{1/2}).$ $$

Thirdly,

$$ $\displaystyle n\geq\tilde{\Omega}(BM\kappa/\gamma^{3})\Leftrightarrow n\geq \tilde{\Omega}(BM(\frac{\sqrt{d}}{\gamma^{2}\varepsilon})+B^{4/3}M^{4/3}G^{1/3 }/\gamma^{3})$ $\displaystyle\Leftarrow\gamma\geq\tilde{O}(\sqrt{BM}(\frac{\sqrt{d}}{n \varepsilon})^{1/2}+\frac{B^{\frac{4}{9}}M^{\frac{4}{9}}G^{\frac{1}{9}}}{n^{1/ 3}}).$ $$

Finally,

$$ $\displaystyle n\geq\tilde{\Omega}(MB/\gamma^{2})\Leftarrow\gamma\geq\tilde{O}( \frac{(MB)^{1/2}}{\sqrt{n}}).$ $$

Combining these together, we get the claimed statement.

∎

Combining Lemma 3.7 and Lemma 3.10, we have the following main result for finding SOSP privately:

###### Theorem 3.11 .

Given $\varepsilon,\delta>0$, with gradient oracles in Algorithm 3, setting $b=G(\sqrt{d}/\varepsilon\alpha+1/\alpha^{2}),b_{t}=\max\{\frac{\|\widetilde{
\nabla}_{t}\|\cdot\sqrt{d}}{\alpha\varepsilon},\frac{\|\widetilde{\nabla}_{t}
\|\kappa}{\alpha^{2}},1\}$, $\kappa=\max\{\frac{\alpha\sqrt{d}}{\varepsilon},(BGM)^{1/3}\}$ and $\sigma=\alpha/\sqrt{d}$, Algorithm 2 is $(\varepsilon,\delta)$-DP, and if the dataset is i.i.d. drawn from the underlying distribution $\mathcal{P}$, at least one of the output of is $\tilde{O}(\alpha)$-SOSP, where

$$ $\displaystyle\alpha=O\Big{(}((BGM)^{1/3}+\sqrt{BM})(\frac{\sqrt{d}}{n \varepsilon})^{1/2}+\frac{B^{\frac{2}{9}}M^{\frac{2}{9}}G^{\frac{5}{9}}+B^{ \frac{4}{9}}M^{\frac{4}{9}}G^{\frac{1}{9}}}{n^{1/3}}+\frac{(MB)^{1/2}}{\sqrt{n }}\Big{)}$ $$

###### Remark 3.12 .

If we treat the parameters $B,G,M$ as constants $O(1)$, then we get $\alpha=\tilde{O}((\frac{\sqrt{d}}{n\varepsilon})^{1/2}+\frac{1}{n^{1/3}})$ as claimed before in the abstract and introduction.

If we make further assumptions, like assuming the functions are defined over a constraint domain $\mathcal{X}\subset\mathbb{R}^{d}$ of diameter $R$ and we allow exponential running time, we can get some other standard bounds that can be better than Theorem 3.11 in some regimes.
See Appendix A.2 for more discussions.

###### Lemma 3.5 (Gradient oracles with bounded error) .

###### Proof.

###### Lemma 3.6 .

###### Proof.

###### Lemma 3.7 .

###### Proof.

###### Lemma 3.8 .

###### Proof.

###### Lemma 3.9 .

###### Proof.

###### Lemma 3.10 .

###### Proof.

###### Theorem 3.11 .

###### Remark 3.12 .

## 4 Discussion

We combine the concepts of adaptive batch sizes and the tree mechanism to improve the previous best results for privately finding SOSP. Our approach achieves the same bound as the state-of-the-art method for finding FOSP, suggesting that privately finding an SOSP may incur no additional cost.

Several interesting questions remain. First, what is the tight bound for privately finding FOSP and SOSP? Second, can the adaptive batch size technique be applied in other settings? Could it offer additional advantages, such as reducing runtime in practice?
Finally, while we can obtain a generalization error bound of $\sqrt{d/n}$ using concentration inequalities and the union bound, can we achieve a better generalization error bound for the non-convex optimization?

## Appendix A Appendix

### A.1 Discussion of Proposition 3.4

Proposition 3.4 has become a standard result in non-convex optimization.
Ganesh et al. [] assume two kinds of gradient oracles that satisfy the norm-Subgaussian definition below:

###### Definition A.1 (SubGaussian gradient oracles) .

For a $G$-Lipschitz and $M$-smooth function $F$:
$(1)$ We say $\mathcal{O}_{1}$ is a first kind of $\zeta_{1}$ norm-subGaussian Gradient oracle if given $x\in\mathbb{R}^{d}$, $\mathcal{O}(x)$ satisfies $\operatorname*{\mathbb{E}}\mathcal{O}_{1}(x)=\nabla F(x)$ and $\mathcal{O}_{1}(x)-\nabla F(x)$ is $\mathrm{nSG}(\zeta_{1})$.
$(2)$ We say $\mathcal{O}_{2}$ is a second kind of $\zeta_{2}$ norm-subGaussian stochastic Gradient oracle if given $x,y\in\mathbb{R}^{d}$, $\mathcal{O}_{2}(x,y)$ satisfies that $\operatorname*{\mathbb{E}}\mathcal{O}_{2}(x,y)=\nabla F(x)-\nabla F(y)$ and $\mathcal{O}_{2}(x,y)-(\nabla F(x)-\nabla F(y))$ is $\mathrm{nSG}(\zeta_{2}\|x-y\|)$.

In Definition A.1, the oracles are required to be unbiased with norm-subGaussian error. While this condition is sufficient, it is not necessary. These two types of gradient oracles are then used to construct gradient estimators whose errors are tightly controlled with high probability (Lemma3.3 in Ganesh et al. []). Proposition 3.4 can be established directly using Lemma 3.3 from Ganesh et al. [], as demonstrated in the proof of Lemma 3.6 in the same work.
We include the proof here for completeness.

###### Proof of Proposition 3.4 .

By Lemma 3.2 and the precondition that $\|\widetilde{\nabla}_{t}-\nabla F(x_{t})\|\leq\gamma$, we know that, if $\|\nabla F(x_{t})\|\geq 4\gamma$, then $F(x_{t+1})-F(x_{t})\leq-\eta\|\widetilde{\nabla}\|^{2}/16$.
Otherwise, $\|\nabla F(x_{t})\|<4\gamma$.
If $\|\nabla F(x_{t})\|<4\gamma$ but $x_{t}$ is a saddle point, then by Lemma 3.3, we know

$$ $\displaystyle F(x_{t+\Gamma})-F(x_{t})\leq-\tilde{\Omega}(\gamma^{3/2}/\sqrt{ \rho}),$ $$

where $\Gamma=\tilde{O}(M/\sqrt{\rho\gamma})$.
Then if none of point in $\{x_{i}\}_{i\in[T]}$ is an $\tilde{O}(\gamma)$-SOSP, then we know $F(x_{T})-F(x_{0})<-B$, which is contradictory to Assumption 3.1.
Hence at least one point in $\{x_{i}\}_{i\in[T]}$ should be an $\tilde{O}(\gamma)$-SOSP, and hence complete the proof.

∎

###### Definition A.1 (SubGaussian gradient oracles) .

###### Proof of Proposition 3.4 .

### A.2 Other results

The first result is combining the current result in finding the SOSP of the empirical function $F_{\mathcal{D}}(x):=\frac{1}{n}\sum_{\zeta\in\mathcal{D}}f(x;\zeta)$, and then apply the generalization error bound as follows:

###### Theorem A.2 .

Suppose $\mathcal{D}$ is i.i.d. drawn from the underlying distribution $\mathcal{P}$ and under Assumption 3.1.
Additionaly assume $f(;\zeta):\mathcal{X}\to\mathbb{R}$ for some constrained domain $\mathcal{X}\subset\mathbb{R}^{d}$ of diameter $R$.
Then we know for any point $x\in\mathcal{X}$, with probability at least $1-\iota$, we have

$$ $\displaystyle\|\nabla F_{\mathcal{P}}(x)-\nabla F_{\mathcal{D}}(x)\|\leq\tilde {O}(\sqrt{d/n}),\|\nabla^{2}F_{\mathcal{P}}(x)-\nabla^{2}F_{\mathcal{D}}(x)\| \leq\tilde{O}(\sqrt{d/n}).$ $$

###### Proof.

We construct a maximal packing $\mathcal{Y}$ of $O((R/r)^{d})$ points for $\mathcal{X}$, such that for any $x\in\mathcal{X}$, there exists a point $y\in\mathcal{Y}$ such that $\|x-y\|\leq r$.

By Union bound, the Hoeffding inequality for norm-subGaussian (Lemma 2.4 and the Matrix Bernstein Inequality(Theorem 2.5), we know with probability at least $1-\tau$, for all point $y\in\mathcal{Y}$, we have

$$ $\displaystyle\|\nabla F_{\mathcal{P}}(y)-\nabla F_{\mathcal{D}}(y)\|\leq\tilde {O}(L\sqrt{d\log(R/r)/n}),\|\nabla^{2}F_{\mathcal{P}}(y)-\nabla^{2}F_{\mathcal {D}}(y)\|\leq\tilde{O}(M\sqrt{d\log(R/r)/n}).$ (3) $$

Conditional on the above event Equation (3).
Choosing $r\leq\min\{1,M/\rho\}\sqrt{d/n}$, then by the assumptions on Lipschitz and smoothness, we have for any $x\in\mathcal{X}$, there exists $y\in\mathcal{Y}$ such that $\|x-y\|\leq r$, and

$$ $\displaystyle\|\nabla F_{\mathcal{P}}(x)-\nabla F_{\mathcal{D}}(x)\|\leq$ $\displaystyle\|\nabla F_{\mathcal{P}}(x)-\nabla F_{\mathcal{P}}(y)\|+\|\nabla F _{\mathcal{P}}(y)-\nabla F_{\mathcal{D}}(y)\|+\|\nabla F_{\mathcal{D}}(y)- \nabla F_{\mathcal{D}}(x)\|$ $\displaystyle\leq$ $\displaystyle\tilde{O}(L\sqrt{d/n}).$ $$

Similarly, we can show

$$ $\displaystyle\|\nabla^{2}F_{\mathcal{P}}(x)-\nabla^{2}F_{\mathcal{D}}(x)\|\leq \tilde{O}((M+\rho r)\sqrt{d/n})=\tilde{O}(M\sqrt{d/n}).$ $$

∎

The current SOTA of finding SOSP privately of $F_{\mathcal{D}}$ is from Ganesh et al. [], where they can find an $\tilde{O}((\sqrt{d}/n\varepsilon)^{2/3})$-SOSP.
Combining the SOTA and Theorem A.2, we can find the $\alpha$-SOSP of $F_{\mathcal{P}}$ privately with

$$ $\displaystyle\alpha=\tilde{O}(\frac{\sqrt{d}}{n}+(\frac{\sqrt{d}}{n\varepsilon })^{2/3}).$ $$

If we allow exponential running time, as Lowy et al. [] suggests, we can find an initial point $x_{0}$ privately to minimize the empirical function and then use $x_{0}$ as a warm start to improve the final bound further.

###### Theorem A.2 .

###### Proof.

## Peer Reviews

confidence: 4
contribution: 4
initial_rating: 8
presentation: 4
questions: Can the authors expand the related work section by briefly comparing this work to the momentum-based variance-reduction methods like [1] and
DP-SRM ([2])? I think these papers are somewhat relevant.

[1]: Tran, Hoang, and Ashok Cutkosky. "Momentum aggregation for private non-convex ERM." Advances in Neural Information Processing Systems 35 (2022): 10996-11008.

[2]: Wang, Lingxiao, et al. "Efficient privacy-preserving stochastic nonconvex optimization." Uncertainty in Artificial Intelligence. PMLR, 2023.
soundness: 3
strengths: 1. The authors present in a nice and neat way.

2. This paper studies a timely and interesting problem - finding SOSP privately. 

3. The authors introduced simple yet effective tools to solve this problem effectively. Tree mechanism has been applied in many DP papers but this paper illustrates its power when combined with the adaptive batch size. And the analysis part is non-trivial. This technique might be applicable to other private optimization problems.
summary: The authors find that finding second-order stationary points privately can be as fast as finding first-order stationary points privately at a rate of $\tilde{O} (\frac{1}{n^{\frac{1}{3}}} + (\frac{\sqrt{d}}{n\epsilon})^{\frac{1}{2}} )$.
weaknesses: I see no apparent weaknesses in this paper.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 4
questions: I was a bit surpised that the private rate only improved from $\tilde{O}((\sqrt{d}/\epsilon n)^{3/7})$ to $\tilde{O}((\sqrt{d}/\epsilon n)^{1/2})$ after what seem at a high level like fairly substantial improvements to the algorithm. Is this bound known to be tight for FOSP?

> In our setting, $\mathcal{O}_1$ is more accurate but incurs higher computational or privacy costs.

This point is not entirely clear to me and it seems very foundational to the structure of the algorithm. Why shouldn't we just query $\mathcal{O}_1$ every time? I assume it is related to the sensitivity of the queries. It would be helpful for the authors to clarify the motivation for using both oracles by explicitly state the tradeoff between using $\mathcal{O}_1$ and $\mathcal{O}_2$ in terms of accuracy, privacy cost, and/or computational complexity.

> When the privacy parameter $\epsilon$ is sufficiently small, we observe that $\alpha_F \ll \alpha_S$.

I am not completely following this either. If $n$ and $d$ are fixed and we take $\epsilon \to 0$, then eventually we should have $(\sqrt{d}/\epsilon n)^{1/2} > (\sqrt{d}/\epsilon n)^{3/7}$. Could the authors explain the regime (in terms of relationships between $n$, $d$, and $\epsilon$) where the improvement is most significant and clarify whether there are any limitations of their approach as $\epsilon$ becomes very small?
soundness: 4
strengths: The paper proposes a novel algorithm for an important problem in private machine learning. The algorithm improves meaningfully on the previous state-of-the-art in multiple clear ways.

The writing is generally clear and ideas are easy to follow.
summary: This paper studies privately finding second-order stationary points of stochastic optimization problems. This problem is a relevant to private machine learning. A related problem is privately finding first-order stationary points. First-order stationary points include saddle points and local optima, making them less valuable for machine learning compared to second-order stationary points, which exclude saddle points.

The paper gives a differentially private algorithm for finding second-order stationary points. Prior state-of-the-art had a rate higher than for first-order stationary points. This work achieves rate-parity between second-order and first-order stationary points under differential privacy.

The prior state-of-the-art algorithm involves infrequent gradient queries interspersed with many gradient-difference queries. The queries are answered by randomly subsampling the dataset by a fixed-size batch. Gaussian noise is introduced to ensure privacy. A drift variable tracks the total amount of l2-movement of the variable and a fresh gradient query is made when the drift crosses a threshold, which ensures that the gradient estimates do not deteriorate significantly.

This work improves upon the prior work in two ways. First, the Gaussian noise mechanism is replaced with a correlated noise mechanism that reduces the cumulative noise introduced by successive gradient-difference queries. Second, the batch-size for gradient-difference queries between two points is chosen adaptively in proportion to the l2-distance between the two points. Due to the underlying smoothness assumption, the sensitivity of the gradient-difference queries grows in proportion to this distance. Thus adaptive batch-sizes allows for more targeted noise levels and also tightens the utility-analysis.
weaknesses: My only concern is a lack of experimental results. It would be nice to see a small experiment comparing the algorithm to the prior state-of-the-art in order to give a sense of whether the new algorithm is practical to run or not as well as whether the theoretical improvements actually translate into substantive improvement in the quality of the SOSP. In particular, I would be interested to see how the runtime as well as the $\alpha$ value of your approach compares to prior approaches on benchmark problem instances of increasing size.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: A minor question, does the norm in the paper mean $l_2$ norm?
soundness: 3
strengths: This paper addresses an important problem by improving the theoretical bound for achieving a second-order stationary point (SOSP) under differential privacy constraints, aligning it with the bound for a first-order stationary point (FOSP). Leveraging the tree mechanism in differentially private continuous observation, which has been shown to achieve asymptotically minimal error, the paper successfully reduces the error for SOSP.  I believe the idea is noval and the contribution is sufficient.
summary: This paper improves the theoretical bounds for reaching a Second-Order Stationary Point (SOSP) under differential privacy constraints. By employing an adaptive batch size and replacing the independent Gaussian mechanism with a private tree mechanism, the paper effectively reduces the error in achieving SOSP. Detailed theoretical proofs are provided.
weaknesses: 1. There is a line of work that further improves the theoretical bound of the tree mechanism, called matrix mechanism [1]. It improves the bound of the tree mechanism by a constant factor. When training a model, it generally works better than the tree mechanism [2]. I would like to hear some discussions about whether using the matrix mechanism can help improve the theoretical analysis.

2. I am confused by how you describe the adaptive batch size, the expression of $b_t$ in Lemma 3.8 depends on $\tilde{\Delta}_t$. Is  $\tilde{\Delta}_t$ private? If you need to change the batch size based on the dataset, there's a risk of leaking private information when the batch size is not protected. Could you explain how you make the batch size private?

3. As stated in point 2, the notations sometimes confuse me. If would be great if there is a table of notion provided, which would help the paper more readable.

[1] Fichtenberger, Hendrik, Monika Henzinger, and Jalaj Upadhyay. "Constant matters: Fine-grained error bound on differentially private continual observation." In International Conference on Machine Learning, pp. 10072-10092. PMLR, 2023.

[2] Choquette-Choo, Christopher A., Arun Ganesh, Ryan McKenna, H. Brendan McMahan, John Rush, Abhradeep Guha Thakurta, and Zheng Xu. "(Amplified) Banded Matrix Factorization: A unified approach to private training." Advances in Neural Information Processing Systems 36 (2024).

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: - The notation $\mathcal{O}_1$ and $\mathcal{O}_2$ for the gradient oracles could be confusing, as it resembles the common asymptotic notation $O$. An alternative notation might reduce ambiguity.
- How do the assumptions in this work compare to those in related papers? A comparison could add useful context.
- The current approach allows each data point to be seen only in one of the inner loop of the SPIDER algorithm. Could sample complexity be improved by sharing data across outer loops while tracking privacy using composition and subsampling amplification?
soundness: 4
strengths: - The paper provides a theoretical improvement over the existing methods, particularly by achieving faster convergence to second-order stationary points under privacy constraints.
- The proofs are thorough and well-written, giving strong support to the theoretical claims.
- The paper gives sound reasons for developing the algorithm, which addresses both theoretical and practical needs in private stochastic optimization.
summary: This paper presents a new algorithm for private stochastic optimization that builds on the SPIDER algorithm, incorporating a well-known differential privacy technique called the "tree mechanism" and an adaptive batch-size approach. The adaptive strategy adjusts the batch size based on a bias-variance criterion. The authors provide proofs showing that their algorithm achieves faster convergence rates to second-order stationary points than previous methods.
weaknesses: - The structure and flow could be improved, and feels a bit rushed. At times, the paper feels like a sequence of technical lemmas without enough overview or context, which can make it hard to follow.
- The paper does not include an empirical evaluation of the proposed method. Although the main focus is on theoretical improvement, a comparison with other methods in private stochastic optimization would be helpful to understand the practical performance of the algorithm.

Meta-review: This paper uses adaptive batch sizes and incorporates the binary tree mechanism to improve the task of privately finding an SOSP. The derived bound matches the state-of-the-art in finding a FOSP, suggesting that privately finding a SOSP can be achieved at no additional cost. 

The reviewers converged in praise of the novelty and significance of this theoretical work. The paper is well written and generally clear (after the discussion phase). All the reviewers provided positive scores and thus, I'm happy to recommend acceptance of this work with a spotlight presentation.

Decision: Accept (Spotlight)