Adaptive Batch Size for Privately Finding Second-Order Stationary Points

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.

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

However, as shown in Arora et al. (2023), the state-of-the-art bound for privately finding an $\alpha_{F}$-FOSP is tighter: ¹¹1As proposed by Lowy et al. (2024), 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.

When the privacy parameter $\varepsilon$ is sufficiently small, and the error term depending on it dominates the non-private term $1/n^{1/3}$, 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?

Moreover, as pointed out by Tao et al. (2025), the results in Ganesh et al. (2023) may be overly optimistic. In particular, the saddle point escape subprocedure used in Ganesh et al. (2023) was designed for the full-batch setting. However, to mitigate dependence issues, the algorithm performs only a single pass over the $n$ functions and relies on minibatches instead. A direct fix for this issue leads to a weaker guarantee on the minimum eigenvalue of the Hessian, specifically,

which fails to satisfy Definition 1.2. To address this, Tao et al. (2025) proposed an alternative correction, but their method resulted in weaker theoretical guarantees than Ganesh et al. (2023) originally claimed, yielding

This work improves upon the results of Ganesh et al. (2023). In addition, we introduce a new saddle point escape subprocedure that correctly addresses the issue in Ganesh et al. (2023) while fully recovering—and even strengthening—the theoretical guarantees.

Specifically, we present an algorithm that finds an $\alpha$-SOSP with privacy guarantees, where:

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. (2023) 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.

In this work, we build on the SpiderBoost algorithm framework, similar to prior approaches (Arora et al., 2023; Ganesh et al., 2023), 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. (2023) 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. (2023) 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. (2023), 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. (2023), 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.

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., 2011; Bassily et al., 2014, 2019; Feldman et al., 2020; Asi et al., 2021; Kulkarni et al., 2021; Carmon et al., 2023; Gopi et al., 2023)).

The tree mechanism, originally introduced by the differential privacy (DP) community (Dwork et al., 2010; Chan et al., 2011) for the continual observation, has inspired tree-structure private optimization algorithms like Asi et al. (2021); Bassily et al. (2021); Arora et al. (2023); Zhang et al. (2024). One can also use the matrix mechanism Fichtenberger et al. (2023) which improves the tree mechanism by a constant factor. Some prior works have explored adaptive batch size techniques in optimization. For instance, De et al. (2016) introduced adaptive batch sizing for stochastic gradient descent (SGD), while Ji et al. (2020) 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. (2020); Kornowski and Shamir (2021); Davis et al. (2022); Jordan et al. (2023).

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

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

We present the subprocedure for escaping saddle points in this section, with its pseudocode provided in Algorithm 2. The core idea is straightforward: given a sufficiently accurate estimate of the function’s Hessian, we can apply the power method to escape the saddle point. If the Hessian’s smallest eigenvalue is sufficiently negative, then after a certain number of steps, the iterate will have moved a significant distance, resulting in a substantial decrease in function value—indicating a successful escape.

The Gaussian noise $\zeta_{t-1}$ added in Line 5 is for the privacy purpose. We have the following guarantee of Algorithm 2:

We have the following guarantee on $g_{t}$:

Let $\varrho_{t}=\nabla F(x_{t})-g_{t}$ denote the difference between the true gradient and our estimation. We use the following standard technical claims to connect the distance of the trajectory and the function value change.

In Algorithm 2, we halt the algorithm whenever we find a point $x_{t}$ such that $\|x_{t}-x_{0}\|_{2}\geq\Xi$. We use the following lemma to demonstrate that a large distance at $x_{t}$ means a large function value decrease at $x_{t}$, that is, it escapes from the saddle point successfully:

Similar to previous works Jin et al. (2017); Wang et al. (2019a), we use a coupling argument to prove that we can escape the saddle point with high probability. Fix the sequence of Gaussian noise $(\zeta_{1},\cdots,\zeta_{\Gamma})$ and ensure $\|\zeta_{t}\|_{2}\leq\gamma$ for all $t\in[\Gamma]$.

Let $y(x)$ denote the output $y$ conditional on the first iterate $x_{1}=x$. Define the set of stuck region around $x_{0}-\eta g$:

where $r=O(\eta\gamma)$. Suppose $x_{0}$ is the saddle point, and let $\mathbf{e}_{1}$ be the minimum eigenvector of $H$. We have the following Lemma:

With these Lemmas, we can complete the proof of Theorem 3.4. In particular, Theorem 3.4 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.

Algorithm 3 follows the SpiderBoost framework. We primarily focus on gradient oracles and estimators for simplicity, as the Hessian case follows the same principle. Moreover, we allow a larger error tolerance for a Hessian estimate $H_{t}$, approximately $\sqrt{\rho\gamma}$, compared to the gradient, which is $\gamma$. We discuss some key variables and parameters in it.

We either query $\mathcal{O}_{1}$ to estimate the gradient directly or query $\mathcal{O}_{2}$ to estimate the gradient difference between consecutive points. The term $\mathrm{drift}$ controls the estimated error: when $\mathrm{drift}_{t}$ is small, $\Delta_{t}$ remains a reliable estimator; when $\mathrm{drift}_{t}$ exceeds the threshold determined by the parameter $\kappa$, we obtain a fresh estimate from $\mathcal{O}_{1}$.

The term $\mathrm{frozen}$ serves a technical role in the application of Theorem 3.4; specifically, when a potential saddle point is detected, we invoke the subprocedure described in Algorithm 2.

The variable $\mathrm{count}$ tracks the number of saddle point escapes since the last fresh gradient estimate $\Delta_{t}$ and Hessian estimate $H_{t}$. Once $\mathrm{count}$ exceeds the threshold $\tau$, we force a fresh query to $\mathcal{O}_{1}$ and $\mathcal{O}_{3}$ to ensure privacy, following the Gaussian Mechanism.

We have the following guarantee of Algorithm 3.

The proof intuition of Proposition 3.10 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 the proof of Proposition 3.10 in the Appendix.

It suffices to build the private oracles with provable utility guarantees. We construct the gradient oracles below in Algorithm 4.

From now on, we adopt Algorithm 4 as the gradient oracles for Line 6 and Line 10 respectively in Algorithm 3, 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 3.

Now, we consider the noise added from the tree mechanism and the noise added in the stochastic power method to make the algorithm private.

With the noise added in mind, we get the high-probability error bound of gradient estimators $\widetilde{\nabla}_{t}$ and Hessian estimators $H_{t}$.