Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations

Introduction

This task plays a central role in the study of non-convex optimization: for functions satisfying a weak strict saddle condition (Ge et al. 2015), exact SOSPs (with $\epsilon=\gamma=0$) are local minima, and therefore the condition (1) serves as a proxy for approximate local optimality. However, it is NP-Hard to decide whether a SOSP is a local minimum or a high-order saddle point (Murty and Kabadi 1987). Moreover, for a growing set of non-convex optimization problems arising in machine learning, SOSPs are in fact global minima (Ge et al. 2015; Ge et al. 2016; Sun et al. 2018; Ma et al. 2019). Consequently, there has been intense recent interest in the design of efficient algorithms for finding approximate SOSPs (Jin et al. 2017; Allen-Zhu 2018a; Carmon et al. 2018; Fang et al. 2018; Tripuraneni et al. 2018; Xu et al. 2018; Fang et al. 2019).

This restriction typically arises due to computational considerations (when $\widehat{\nabla F}\left(\cdot{},z\right)$ is much cheaper to compute than $\nabla F(\cdot{})$, as in empirical risk minimization or Monte Carlo simulation), or due to fundamental online nature of the problem at hand (e.g., when $x$ represents a routing scheme and $z$ represents traffic on a given day). However, for many problems with additional structure, we have access to extra information. For example, we often have access to stochastic second-order information in the form of a Hessian estimator $\widehat{\nabla^{2}F}\left(x,z\right)$ satisfying

In this paper, we characterize the extent to which the stochastic Hessian information (3), as well as higher-order information, contributes to the efficiency of finding first- and second-order stationary points. We approach this question from the perspective of oracle complexity (Nemirovski and Yudin 1983), which measures efficiency by the number of queries to estimators of the form (2)—and possibly (3)—required to satisfy the condition (1).

We provide new upper and lower bounds on the stochastic oracle complexity of finding $\epsilon$-stationary points and ($\epsilon,\gamma)$-SOSPs. In brief, our main results are as follows.

Finding $\epsilon$-stationary points: The elbow effect. We propose a new algorithm that finds an $\epsilon$-stationary point ($\gamma=\infty$) with $O(\epsilon^{-3})$ stochastic gradients and stochastic Hessian-vector products. We furthermore show that this guarantee is not improvable via a complementary $\Omega(\epsilon^{-3})$ lower bound. All previous algorithms achieving $O(\epsilon^{-3})$ complexity require “multi-point” queries, in which the algorithm can query stochastic gradients at multiple points for the same random seed. Moreover, we show that $\Omega(\epsilon^{-3})$ remains a lower bound for stochastic $p$th-order methods for all $p\geq{}2$ and hence—in contrast to the deterministic setting—the optimal rates for higher-order methods exhibit an “elbow effect”; see Figure 1.

$(\epsilon,\gamma)$-stationary points: Improved algorithm and nearly matching lower bound. We extend our algorithm to find $(\epsilon,\gamma)$-stationary points using $O(\epsilon^{-3}+\epsilon^{-2}\gamma^{-2}+\gamma^{-5})$ stochastic gradient and Hessian-vector products, and prove a nearly matching $\Omega(\epsilon^{-3}+\gamma^{-5})$ lower bound.

We first describe our developments for the task of finding $\epsilon$-approximate first-order stationary points (satisfying (1) with $\gamma=\infty$), and subsequently extend our results to general $\gamma$. The reader may also refer to Table 1 for a succinct comparison of upper bounds.

Our approach builds on a line of work by Fang et al. 2018; Zhou et al. 2018; Wang et al. 2019; Cutkosky and Orabona 2019 that also develop algorithms with complexity $O(\epsilon^{-3})$, but require a “multi-point” oracle in which algorithm can query the stochastic gradient at multiple points for the same random seed. Specifically, in the $n$-point variant of this model, the algorithm can query at the set of points $(x_{1},\ldots,x_{n})$ and receive

and where the estimator $\widehat{\nabla F}(x,z)$ is unbiased and has bounded variance in the sense of (2). The aforementioned works achieve $O(\epsilon^{-3})$ complexity using $n=2$ simultaneous queries, while our new algorithm achieves the same rate using $n=1$ (i.e., $z$ is drawn afresh at each query), but using stochastic Hessian-vector products in addition to stochastic gradients. However, we show in Appendix B that under the statistical assumptions made in these works, the two-point stochastic gradient oracle model is strictly stronger than the single-point stochastic gradient/Hessian-vector product oracle we consider here. On the other hand, unlike our algorithm, these works do not require Lipschitz Hessian.

The algorithms that achieve complexity $O(\epsilon^{-3})$ using two-point queries work by estimating gradient differences of the form $\nabla F(x)-\nabla F(x^{\prime})$ using $\widehat{\nabla F}\left(x,z\right)-\widehat{\nabla F}\left(x^{\prime},z\right)$ and applying recursive variance reduction (Nguyen et al. 2017). Our primary algorithmic contribution is a second-order stochastic estimator for $\nabla F(x)-\nabla F(x^{\prime})$ which avoids simultaneous queries while maintaining comparable error guarantees. To derive our estimator, we note that $\nabla F(x)-\nabla F(x^{\prime})=\int_{0}^{1}\nabla^{2}F(xt+x^{\prime}(1-t))(x-x^{\prime})dt$, and use $K$ queries to the stochastic Hessian estimator (3) to numerically approximate this integral. More precisely, our estimator (5) only requires stochastic Hessian-vector products, whose computation is often roughly as expensive as that of a stochastic gradient (Pearlmutter 1994). Specifically, our estimator takes the form

For functions with Lipschitz gradient and Hessian, we prove an $\Omega(\epsilon^{-3.5})$ lower bound on the minimax oracle complexity of algorithms for finding stationary points using only stochastic gradients (2). We formally prove our results for the structured class of zero-respecting algorithms (Carmon et al. 2019a); the lower bounds extend to general randomized algorithms via similar arguments to Arjevani et al. 2019a. This lower bound is an extension of the results of Arjevani et al. 2019a, who showed that for functions with Lipschitz gradient but not Lipschitz Hessian, the optimal rate is $\Theta(\epsilon^{-4})$ using only stochastic gradients (2). Together with our new $O(\epsilon^{-3})$ upper bound, this lower bound reveals that stochastic Hessian-vector products offer an $\Omega(\epsilon^{-0.5})$ improvement in the oracle complexity for finding stationary points in the single-point query model. This contrasts the noiseless optimization setting, where finite gradient differences can approximate Hessian-vector products arbitrarily well, meaning these oracle models are equivalent.

For algorithms that can query both stochastic gradients and stochastic Hessians, we prove a lower bound of $\Omega(\epsilon^{-3})$ on the oracle complexity of finding an expected $\epsilon$-stationary point. This proves that our $O(\epsilon^{-3})$ upper bound is optimal in the leading order term in $\epsilon$, despite using only stochastic Hessian-vector products rather than full stochastic Hessian queries.

Notably, our $\Omega(\epsilon^{-3})$ lower bound extends to settings where stochastic higher-order oracles are available, i.e, when the first $p$ derivatives are Lipschitz and we have bounded-variance estimators $\{\widehat{\nabla^{q}F}(\cdot,\cdot)\}_{q\leq p}$. The lower bound holds for any finite $p$, and thus, as a function of the oracle order $p$, the minimax complexity has an elbow (Figure 1): for $p=1$ the complexity is $\Theta(\epsilon^{-4})$ (Arjevani et al. 2019a) while for all $p\geq 2$ it is $\Theta(\epsilon^{-3})$. This means that smoothness and stochastic derivatives beyond the second-order cannot improve the leading term in rates of convergence to stationarity, establishing a fundamental limitation of stochastic high-order information. This highlights another contrast with the noiseless setting, where $p$th order methods enjoy improved complexity for every $p$ (Carmon et al. 2019a).

As we discuss in Appendix B, for multi-point stochastic oracles (4), the rate $O(\epsilon^{-3})$ is attainable even without stochastic Hessian access. Moreover, our $\Omega(\epsilon^{-3})$ lower bound for stochastic $p$th order oracles holds even when multi-point queries are allowed. Consequently, when viewed through the lens of worst-case oracle complexity, our lower bounds show that even stochastic Hessian information is not helpful in the multi-point setting.

1.2 Second-order stationary points

We incorporate our recursive variance-reduced Hessian-vector product-based gradient estimator into an algorithm that combines SGD with negative curvature search. Under the slightly stronger (relative to (3)) assumption that the stochastic Hessians have almost surely bounded error, we prove that—with constant probability—the algorithm returns an $(\epsilon,\gamma)$-SOSP after performing $O(\epsilon^{-3}+\epsilon^{-2}\gamma^{-2}+\gamma^{-5})$ stochastic gradient and Hessian-vector product queries.

We prove a minimax lower bound which establishes that the stochastic second-order oracle complexity of finding $(\epsilon,\gamma)$-SOSPs is $\Omega(\epsilon^{-3}+\gamma^{-5})$. Consequently, the algorithms we develop have optimal worst-case complexity in the regimes $\gamma=O(\epsilon^{2/3})$ and $\gamma=\Omega(\epsilon^{0.5})$. Compared to our lower bounds for finding $\epsilon$-stationary points, proving the $\Omega(\gamma^{-5})$ lower bound requires a more substantial modification of the constructions of Carmon et al. 2019a and Arjevani et al. 2019a. In fact, our lower bound is new even in the noiseless regime (i.e., $\sigma_{1}=\sigma_{2}=0$), where it becomes $\Omega(\epsilon^{-1.5}+\gamma^{-3})$; this matches the guarantee of the cubic-regularized Newton’s method (Nesterov and Polyak 2006) and consequently characterizes the optimal rate for finding approximate SOSPs using noiseless second-order methods.

2 Further related work

We briefly survey additional upper and lower complexity bounds related to our work and place our results within their context. The works of Monteiro and Svaiter 2013; Arjevani et al. 2019b; Agarwal and Hazan 2018 delineate the second-order oracle complexity of convex optimization in the noiseless setting; Arjevani and Shamir 2017 treat the finite-sum setting.

For functions with Lipschitz gradient and Hessian, oracle access to the Hessian significantly accelerates convergence to $\varepsilon$-approximate global minima, reducing the complexity from $\Theta(\varepsilon^{-0.5})$ to $\Theta(\varepsilon^{-2/7})$. However, since the hard instances for first-order convex optimization are quadratic (Nemirovski and Yudin 1983; Arjevani and Shamir 2016; Simchowitz 2018), assuming Lipschitz continuity of the Hessian does not improve the complexity if one only has access to a first-order oracle. This contrasts the case for finding $\epsilon$-approximate stationary points of non-convex functions with noiseless oracles. There, Lipschitz continuity of the Hessian improves the first-order oracle complexity from $\Theta(\epsilon^{-2})$ to $O(\epsilon^{-1.75})$, with a lower bound of $\Omega(\epsilon^{-12/7})$ for deterministic algorithms (Carmon et al. 2017; Carmon et al. 2019b). Additional access to full Hessian further improves this complexity to $\Theta(\epsilon^{-1.5})$, and for $p$th-order oracles with Lipschitz $p$th derivative, the complexity further improves to $\Theta(\epsilon^{-(1+\frac{1}{p})})$ (Carmon et al. 2019a); see Figure 1.

3 Paper organization

We formally introduce our notation and oracle model in Section 2. Section 3 contains our results concerning the complexity of finding $\epsilon$-first-order stationary points: algorithmic upper bounds (Section 3.1) and algorithm-independent lower bounds (Section 3.2). Following a similar outline, Section 4 describes our upper and lower bounds for finding $(\epsilon,\gamma)$-SOSPs. We conclude the paper in Section 5 with a discussion of directions for further research. Additional technical comparison with related work is given in Appendix A and B, and proofs are given in Appendix C through Appendix G.

Setup

We study the problem of finding $\epsilon$-stationary and $(\epsilon,\gamma)$-second order stationary points in the standard oracle complexity framework (Nemirovski and Yudin 1983), which we briefly review here.

We consider $p$-times differentiable functions satisfying standard regularity conditions, and define

so that $L_{1:p}\coloneqq(L_{1},\dots,L_{p})$ specifies the Lipschitz constants of the $q$th order derivatives $\nabla^{q}F$ with respect to the operator norm. We make no restriction on the ambient dimension $d$.

For a given function $F\in\mathcal{F}_{p}(\Delta,L_{1:p})$, we consider a class of stochastic $p$th order oracles defined by a distribution $P_{z}$ over a measurable set $\mathcal{Z}$ and an estimator

where $\{\widehat{\nabla^{q}F}(\cdot,z)\}_{q=0}^{p}$ are unbiased estimators of the respective derivatives. That is, for all $x$, $\En_{z\sim{}P_{z}}[\widehat{F}(x,z)]=F(x)$ and $\En_{z\sim P_{z}}[\widehat{\nabla^{q}F}(x,z)]=\nabla^{q}F(x)$ for all $q\in[p]$. For $p\geq 2$ we assume without loss of generality that $\widehat{\nabla^{p}F}(x,z)$ is a symmetric tensor.

Given variance parameters $\sigma_{1:p}=(\sigma_{1},\ldots,\sigma_{p})$, we define the oracle class $\mathcal{O}_{p}(F,\sigma_{1:p})$ to be the set of all stochastic $p$th-order oracles for which the variance of the derivative estimators satisfies

We consider stochastic $p$th-order optimization algorithms that access an unknown function $F\in\mathcal{F}_{p}(\Delta,L_{1:p})$ through multiple rounds of queries to a stochastic $p$th-order oracle $(\mathsf{O}_{F}^{p},P_{z})\in\mathcal{O}_{p}(F,\sigma_{1:p})$. When queried at $x^{(t)}$ in round $t$, the oracle performs an independent draw of $z^{(t)}\sim P_{z}$ and answers with $\mathsf{O}_{F}^{p}(x^{(t)},z^{(t)})$. Algorithm queries depend on $F$ only through the oracle answers; see e.g. Arjevani et al. 2019a for a more formal treatment.

Complexity of finding first-order stationary points

In this section we focus on the task of finding $\epsilon$-approximate stationary points (satisfying $\|\nabla F(x)\|\leq\epsilon$). As prior work observes (Carmon et al. 2017; Allen-Zhu 2018a, cf.), stationary point search is a useful primitive for achieving the end goal of finding second-order stationary points (1). We begin with describing algorithmic upper bounds on the complexity of finding stationary points with stochastic second-order oracles, and then proceed to match their leading terms with general $p$th order lower bounds.

Our algorithms rely on recursive variance reduction (Nguyen et al. 2017): we sequentially estimate the gradient at the points $\{x^{(t)}\}_{t\geq 0}$ by accumulating cheap estimators of $\nabla F(x^{(\tau)})-\nabla F(x^{(\tau-1)})$ for $\tau=t_{0}+1,\ldots,t$, where at iteration $t_{0}$ we reset the gradient estimator by computing a high-accuracy approximation of $\nabla F(x^{(t_{0})})$ with many oracle queries. Our implementation of recursive variance reduction, Algorithm 1, differs from previous approaches (Fang et al. 2018; Zhou et al. 2018; Wang et al. 2019) in three aspects.

In Line 9 we estimate differences of the form $\nabla F(x^{(\tau)})-\nabla F(x^{(\tau-1)})$ by averaging stochastic Hessian-vector products. This allows us to do away with multi-point queries and operate under weaker assumptions than prior work (see Appendix B), but it also introduces bias to our estimator, which makes its analysis more involved. This is the key novelty in our algorithm.

Rather than resetting the gradient estimator every fixed number of steps, we reset with a user-defined probability $b$ (Line 5); this makes the estimator stateless and greatly simplifies its analysis, especially when we use a varying value of $b$ to find second-order stationary points.

We dynamically select the batch size $K$ for estimating gradient differences based on the distance between iterates (Line 3), while prior work uses a constant batch size. Our dynamic batch size scheme is crucial for controlling the bias in our gradient estimator, while still allowing for large step sizes as in Wang et al. 2019.

The core of our analysis is the following lemma, which bounds the gradient estimation error and expected oracle complexity. To state the lemma, we let $\{x^{(t)}\}_{t\geq 0}$ be sequence of queries to Algorithm 1, and let ${g^{(t)}=\textsf{HVP-RVR-Gradient-Estimator}_{\epsilon,b}(x^{(t)},x^{(t-1)},g^{(t-1)})}$ be the sequence of estimates it returns.

For any oracle in $\mathcal{O}_{2}(F,\sigma_{1:2})$ and $F\in\mathcal{F}_{2}(\Delta,L_{1:2})$, Algorithm 1 guarantees that

for all $t\geq{}1$. Furthermore, conditional on $x^{(t-1)}$, $x^{(t)}$ and $g^{(t-1)}$, the $t^{\textup{th}}$ execution of Algorithm 1 with reset probability $b$ uses at most

stochastic gradient and Hessian-vector product queries in expectation.

We prove the lemma in Appendix C by bounding the per-step variance using the HVP oracle’s variance bound (7), and by bounding the per-step bias relative to $\nabla F(x^{(t)})-\nabla F(x^{(t-1)})$ using the Lipschitz continuity of the Hessian.

Taking $T=\Omega(\frac{\Delta}{\eta\epsilon^{2}})$, we are guaranteed that a uniformly selected iterate has expected norm $O(\epsilon)$.

To account for oracle complexity, we observe from Lemma 1 that $T$ calls to Algorithm 1 require at most $T(\frac{\sigma_{1}^{2}b}{\epsilon^{2}}+1)+\sum_{t=1}^{T}\En{\|x^{(t)}-x^{(t-1)}\|^{2}}\cdot\big(\frac{\sigma_{2}^{2}+L_{2}\epsilon}{b\epsilon^{2}}\big)$ oracle queries in expectation. Using $x^{(t)}-x^{(t-1)}=\eta g^{(t-1)}$, Lemma 1 and (8) imply that $\sum_{t=1}^{T}\En{\|x^{(t)}-x^{(t-1)}\|^{2}}\leq O(T\epsilon^{2})$. We then choose $b$ to out the terms $T\big({\frac{\sigma_{1}^{2}b}{\epsilon^{2}}}\big)$ and $T\big({\frac{\sigma_{2}^{2}+L_{2}\epsilon}{b}}\big)$. This gives the following complexity guarantee, which we prove in Appendix E.1.

For any function $F\in\mathcal{F}_{2}\left(\Delta,L_{1},L_{2}\right)$, stochastic second-order oracle in $\mathcal{O}_{2}(F,\sigma_{1},\sigma_{2})$, and $\epsilon<\min\left\{\sigma_{1},\sqrt{\Delta{}L_{1}}\right\}$, with probability at least $\frac{3}{4}$, Algorithm 2 returns a point $\widehat{x}$ such that $\left\|\nabla F(\widehat{x})\right\|\leq\epsilon$ and performs at most

stochastic gradient and Hessian-vector product queries.

The oracle complexity of Algorithm 2 depends on the Lipschitz parameters of $F$ only through lower-order terms in $\epsilon$, with the leading term scaling only with the variance of the gradient and Hessian estimators. In the low noise regime where $\sigma_{1}<\epsilon$ and $\sigma_{2}<\max\{L_{1},\sqrt{L_{2}\epsilon}\}$, the complexity becomes $O(\Delta L_{1}\epsilon^{-2}+\Delta L_{2}^{0.5}\epsilon^{-1.5})$ which is simply the maximum of the noiseless guarantees for gradient descent and Newton’s method. We remark, however, that in the noiseless regime $\sigma_{1}=\sigma_{2}=0$, a slightly better guarantee $O(\Delta L_{1}^{0.5}L_{2}^{0.25}\epsilon^{-1.75}+\Delta L_{2}^{0.5}\epsilon^{-1.5})$ is achievable (Carmon et al. 2017).

In the noiseless setting, any algorithm that uses only first-order and Hessian-vector product queries must have complexity scaling with $L_{1}$, but full Hessian access can remove this dependence (Carmon et al. 2019b). We show that the same holds true in the stochastic setting: Algorithm 3, a subsampled cubic regularized trust-region method using Algorithm 1 for gradient estimation, enjoys a complexity bound independent of $L_{1}$. We defer the analysis to Appendix E.2 and state the guarantee as follows.

For any function $F\in\mathcal{F}_{2}\left(\Delta,\infty,L_{2}\right)$, stochastic second order oracle in $\mathcal{O}_{2}(F,\sigma_{1},\sigma_{2})$, and $\epsilon<\sigma_{1}$, with probability at least $\frac{3}{4}$, Algorithm 3 returns a point $\widehat{x}$ such that $\left\|\nabla F(\widehat{x})\right\|\leq\epsilon$ and performs at most

The guarantee of Theorem 2 constitutes an improvement in query complexity over Theorem 1 in the regime $L_{1}\gtrsim(1+\frac{\sigma_{1}}{\epsilon})(\sigma_{2}+\sqrt{L_{2}\epsilon})$. However, depending on the problem, full stochastic Hessians can be up to $d$ times more expensive to compute than stochastic Hessian-vector products.

2 Lower bounds

Having presented stochastic second-order methods with $O(\epsilon^{-3})$-complexity bound for finding $\epsilon$-stationary points, our we next show that this rates cannot be improved. In fact, we show that this rate is optimal even when one is given access to stochastic higher derivatives of any order. We prove our lower bounds for the class of zero-respecting algorithms, which subsumes the majority of existing optimization methods; see Appendix G.1 for a formal definition. We believe that existing techniques (Carmon et al. 2019a; Arjevani et al. 2019a) can strengthen our lower bounds to apply to general randomized algorithms; for brevity, we do not pursue it here.

The lower bounds in this section closely follow a recent construction by Arjevani et al. 2019a, who prove lower bounds for stochastic first-order methods. To establish complexity bounds for $p$th-order methods, we extend the ‘probabilistic zero-chain’ gradient estimator introduced in Arjevani et al. 2019a to high-order derivative estimators.The most technically demanding part of our proof is a careful scaling of the basic construction to simultaneously meet multiple Lipschitz continuity and variance constraints. Deferring the proof details to Appendix G.1, our lower bound is as follows.

A construction of dimension $\Theta\Bigl(\frac{\Delta}{\epsilon}\min\Bigl\{\min_{q\in\{2,\ldots,p\}}\left(\frac{\sigma_{q}}{\sigma_{1}}\right)^{\frac{1}{q-1}},\min_{q^{\prime}\in\{1,\ldots,p\}}\left(\frac{L_{q^{\prime}}}{\epsilon}\right)^{1/q^{\prime}}\Bigr\}\Bigr)$ realizes this lower bound.

For second-order methods (with $p=2$), Theorem 3 specializes to the oracle complexity lower bound

which is tight in that it matches (up to numerical constants) the convergence rate of Algorithm 2 in the regime where $\Delta\sigma_{1}\sigma_{2}\epsilon^{-3}$ dominates both the upper bound in Theorem 1 and expression (10). The lower bound (10) is also tight when the second-order information is not available or reliable ($\sigma_{2}$ is infinite or very large, respectively): Standard SGD matches the $\epsilon^{-4}$ term (Ghadimi and Lan 2013), while more sophisticated variants based on restarting (Fang et al. 2019) and normalized updates with momentum (Cutkosky and Mehta 2020) match the $\epsilon^{-3.5}$ term (the former up to logarithmic factors)—neither of these algorithms requires stochastic second derivative estimation.

Theorem 3 implies that while higher-order methods (with $p>2$) might achieve better dependence on the variance parameters than the upper bounds for Algorithm 2 or Algorithm 3, they cannot improve the $\epsilon^{-3}$ scaling. This highlights a fundamental limitation for higher-order methods in stochastic non-convex optimization which does not exist in the noiseless case. Indeed, without noise the optimal rate for finding $\epsilon$-stationary point with a $p$th order method is $\Theta(\epsilon^{-1+\frac{1}{p}})$ Carmon et al. 2019a; we illustrate this contrast in Figure 1.

Altogether, the results presented in this section fully characterize (with respect to dependence on $\epsilon$) the complexity of finding $\epsilon$-stationary points with stochastic second-order methods and beyond in the single-point query model. We briefly remark that lower bound in (9) immediately extends to multi-point queries, which shows that even second-order methods offer little benefit once two or more simultaneous queries are allowed.

Complexity of finding second-order stationary points

Having established rates of convergence for finding $\epsilon$-stationary points, we now turn our attention to $(\epsilon,\gamma)$-second order stationary points, which have the additional requirement that $\lambda_{\min}(\nabla^{2}F(x))\geq-\gamma$, i.e. that $F$ is $\gamma$-weakly convex around $x$. This section follows the general organization of the prequel: we first design and analyze an algorithm with improved upper bounds, and then develop nearly-matching lower bounds that apply to a broad class of algorithms.

Our first contribution for this section is an algorithm that enjoys improved complexity for finding $(\epsilon,\gamma)$-second-order stationary points, and that achieves this using only stochastic gradient and Hessian-vector product queries. To guarantee second-order stationarity, we follow the established technique of interleaving an algorithm for finding a first-order stationary point with negative curvature descent (Carmon et al. 2017; Allen-Zhu 2018a). However, we employ a randomized variant of this approach. Specifically, at every iteration we flip a biased coin to determine whether to perform a stochastic gradient step or a stochastic negative curvature descent step.

Our algorithm estimates stochastic gradients using the HVP-RVR scheme (Algorithm 1), where the value of the restart probability $b$ depends on the type of the previous step (gradient or negative curvature). To implement negative curvature descent, we apply Oja’s method (Oja 1982; Allen-Zhu and Li 2017) which detects directions of negative curvature using only stochastic Hessian-vector product queries. For technical reasons pertaining to the analysis of Oja’s method, we require the stochastic Hessians to be bounded almost surely, i.e., $\|\widehat{\nabla^{2}F}\left(x,z\right)-\nabla^{2}F(x)\|_{\rm op}\leq\bar{\sigma}_{2}$ a.s.; we let $\overline{\mathcal{O}}_{2}(F,\sigma_{1},\bar{\sigma}_{2})$ denote the class of such bounded noise oracles. Under this assumption, Algorithm 4—whose description is deferred to the Appendix F---enjoys the following convergence guarantee. The notation $\widetilde{O}(\cdot)$ hides lower-order terms and logarithmic dependence on the dimension $d$. See the proof in Appendix F for the complete description of the algorithm and the full complexity bound, including lower order terms.

For any function $F\in\mathcal{F}_{2}(\Delta,L_{1:2})$, stochastic Hessian-vector product oracle in $\overline{\mathcal{O}}_{2}(F,\sigma_{1},\bar{\sigma}_{2})$, $\epsilon\leq\min\left\{\sigma_{1},\sqrt{\Delta L_{1}}\right\}$, and $\gamma\leq\min\left\{\bar{\sigma}_{2},L_{1},\sqrt{\epsilon{}L_{2}}\right\}$, with probability at least $\frac{5}{8}$ Algorithm 4 returns a point $\widehat{x}$ such that

stochastic gradient and Hessian-vector product queries.

Similar to the case for finding $\epsilon$-stationary points (see discussion preceding Theorem 2), using full stochastic Hessian information allows us to design an algorithm (Algorithm 5) which removes the dependence on $L_{1}$ from the theorem above. Moreover, estimating negative curvature directly from empirical Hessian estimates saves us the need to use Oja’s method, which means that we do not need the additional boundedness assumption on the stochastic Hessian used by Algorithm 4. We defer the complete description and analysis for Algorithm 5 to Appendix F.2, and state its complexity guarantee below.

For any function $F\in\mathcal{F}_{2}(\Delta,\infty,L_{2})$, stochastic second order oracle in $\mathcal{O}_{2}(F,\sigma_{1},\sigma_{2})$, $\epsilon\leq\sigma_{1}$, and $\gamma\leq\min\big\{\sigma_{2},\sqrt{\epsilon{}L_{2}},\Delta^{\frac{1}{3}}L_{2}^{\frac{2}{3}}\big\}$, with probability at least $\frac{3}{5}$ Algorithm 5 returns a point $\widehat{x}$ such that

2 Lower bounds

We now develop lower complexity bounds for the task of finding $(\epsilon,\gamma)$-stationary points. To do so, we prove new lower bounds for the simpler sub-problem of finding a $\gamma$-weakly convex point, i.e., a point $x$ such that $\lambda_{\min}(\nabla^{2}F(x))\geq-\gamma$ (with no restriction on $\|\nabla F(x)\|$). Lower bounds for finding $(\epsilon,\gamma)$-SOSPs follow as the maximum (or, equivalently, the sum) of lower bounds we develop here and the lower bounds for finding $\epsilon$-stationary points given in Theorem 6. To see why this is so, let $F_{\epsilon}$ and $F_{\gamma}$ be hard instances for finding $\epsilon$-stationary and $\gamma$-weakly-convex points respectively, and consider the “direct sum” $F_{\epsilon,\gamma}(x)\vcentcolon=\frac{1}{2}F_{\epsilon}(x_{1},\ldots,x_{d})+\frac{1}{2}F_{\gamma}(x_{d+1},\ldots,x_{2d})$; this is a hard instance for finding $(\epsilon,\gamma)$-SOSPs that inherits all the regularity properties of its constituent functions.

The basic construction we use here is a modification of the zero-chain introduced in Carmon et al. 2019a (see (75) in Appendix G) in which large $\lambda_{\min}(\nabla^{2}F(x))$ is possible only when essentially none of the entries of $x$ is zero. Given $T>0$, we define the hard function

where $\Psi(x)\vcentcolon=\exp(1-\frac{1}{(2x-1)^{2}})\boldsymbol{1}\left\{x>\frac{1}{2}\right\}$ (as in Carmon et al. 2019a) and $\Lambda(x)\coloneqq 8(e^{\frac{-x^{2}}{2}}-1)$.

Our design for the function $\Lambda$ guarantees that any query whose last coordinate is zero has significant negative curvature, while maintaining the original chain structure which guarantees that zero-respecting algorithms require many queries before “discovering” the last coordinate. We complete the construction by specifying a collection of stochastic derivative estimators similar to those in Section 4.2, except for that we choose the stochastic gradient estimator $\widehat{\nabla G_{T}}$ to be exactly equal to $\nabla G_{T}$, so that the lower bound holds even for $\sigma_{1}=0$; Appropriately scaling $G_{T}$ allows us to tune the Lipschitz constants of its derivatives and the variance of the estimators, thereby establishing the following complexity bounds (see Appendix G.2 for a full derivation).

Let $p\geq 2$ and $\Delta,L_{1:p},\sigma_{1:p}>0$ be fixed. If $\gamma\leq O(\min\{\sigma_{2},L_{1}\})$, then there exists ${F\in\mathcal{F}_{p}\left(\Delta,L_{1:p}\right)}$ and $(\mathsf{O}^{\,p}_{F},P_{z})\in\mathcal{O}_{p}(F,\sigma_{1:p})$ such that for any stochastic $p$th-order zero-respecting algorithm, the number of queries to $\mathsf{O}^{\,p}_{F}$required to obtain a $\gamma$-weakly convex point with constant probability is at least

A construction of dimension $\Theta\Bigl(\frac{\Delta}{\gamma}\min\Bigl\{\min_{q\in\{3,\ldots,p\}}\left(\frac{\sigma_{q}}{\sigma_{2}}\right)^{\frac{2}{q-2}},\min_{q^{\prime}\in\{2,\ldots,p\}}\left(\frac{L_{q^{\prime}}}{\gamma}\right)^{\frac{2}{q^{\prime}-1}}\Bigr\}\Bigr)$ realizes the lower bound.

Theorem 6 is new even in the noiseless case (in which $\sigma_{1}=\dots=\sigma_{p}=0$), where it specializes to

For the class $\mathcal{F}_{p}(\Delta,L_{p})$, the lower bound (13) further simplifies to $\Delta{}L_{p}^{\frac{2}{p-1}}\gamma^{-\frac{p+1}{p-1}}$, which is attained by the $p$th-order regularization method given in Cartis et al. 2017. Together, these results characterize the deterministic complexity of finding $\gamma$-weakly convex points with noiseless $p$th-order methods.

Returning to the stochastic setting, the bound in Theorem 6, when combined with Theorem 3, implies the following oracle complexity lower bound bound for finding $(\epsilon,\gamma)$-SOSPs with zero-respecting stochastic second-order methods ($p=2$):

Our lower bound matches the $\epsilon^{-3}+\gamma^{-5}$ terms in the upper bound given by Theorem 4, but does not match the mixed term $\epsilon^{-2}\gamma^{-2}$ appearing in the upper bound. Young’s inequality only gives $\epsilon^{-3}+\gamma^{-5}\geq\Omega(\epsilon^{-9/5}\gamma^{-2})$. Overall, the rates match whenever $\gamma=\Omega(\epsilon^{0.5})$ or $\gamma=O(\epsilon^{2/3})$.

Theorem 6 is suggestive of another “elbow” phenomenon: In the stochastic regime, the rate does not improve beyond $\gamma^{-3}$ for $p\geq 3$, while the optimal rate in the noiseless regime, $\gamma^{-\frac{p+1}{p-1}}$, continues improving for all $p$. Indeed, when high-order noise moments are assumed finite, the term $\min_{q\in\{3,\ldots,p\}}\left({\sigma_{q}}/{\sigma_{2}}\right)^{\frac{2}{q-2}}$ can longer be disregarded. This, in turn, implies that for sufficiently small $\gamma$, one cannot improve over $\gamma^{-3}$-scaling, as seen by (12). However, we are not yet aware of an algorithm using stochastic third-order information or higher that can achieve the $\gamma^{-3}$ complexity bound.

Conclusion

This paper provides a fairly complete picture of the worst-case oracle complexity of finding stationary points with a stochastic second-order oracle: for $\epsilon$-stationary points we characterize the leading term in $\epsilon^{-1}$ exactly and for ($\epsilon,\gamma$)-SOSPs we characterize the leading term in $\gamma^{-1}$ for a wide range of parameters. Nevertheless, our results point to a number of open questions.

Our upper and lower bounds (in Theorem 5 and Theorem 6) resolve the optimal rate to find an $(\epsilon,\gamma)$-stationary point for $p=2$, i.e., when $F$ is second-order smooth and the algorithm can query stochastic gradient and Hessian information. Furthermore, Theorem 3 shows that higher order information ($p\geq 3$) cannot improve the dependence of the rate on the first-order stationarity parameter $\epsilon$. However, our lower bound for dependence on $\gamma$ scales as $\gamma^{-5}$ for $p=2$, but scales as $\gamma^{-3}$ for $p\geq 3$. The weaker lower bound for $p\geq 3$ leaves open the possibility of a stronger upper bound using third-order information or higher.

For statistical learning and sample average approximation problems, it is natural to consider problem instances of the form $F(x)=\En\big[\widehat{F}(x,z)\big]$. For this setting, a more powerful oracle model is the global oracle, in which samples $z^{(1)},\ldots,z^{(n)}$ are drawn i.i.d. and the learner observes the entire function $\widehat{F}(\cdot,z^{(t)})$ for each $t\in[n]$. Global oracles are more powerful than stochastic $p$th order oracles for every $p$, and lead to improved rates in the convex setting (Foster et al. 2019). Is it possible to beat the $\epsilon^{-3}$ elbow for such oracles, or do our lower bounds extend to this setting?

Our lower bounds show that stochastic higher-order methods cannot improve the $\epsilon^{-3}$ oracle complexity attained with stochastic gradients and Hessian-vector products. Furthermore, in the multi-point query model, stochastic second-order information does not even lead to improved rates over stochastic first-order information. However, these conclusions could be artifacts of our worst-case point of view—are there natural families of problem instances for which higher-order methods can adapt to additional problem structure and obtain stronger instance-dependent convergence guarantees? Developing a theory of instance-dependent complexity that can distinguish adaptive algorithms stands out as an exciting research prospect.

Acknowledgements

We thank Blake Woodworth and Nati Srebo for helpful discussions. YA acknowledges partial support from the Sloan Foundation and Samsung Research. JCD acknowledges support from the NSF CAREER award CCF-1553086, ONR YIP N00014-19-2288, Sloan Foundation, NSF HDR 1934578 (Stanford Data Science Collaboratory), and the DAWN Consortium. DF acknowledges the support of TRIPODS award 1740751. KS acknowledges support from NSF CAREER Award 1750575 and a Sloan Research Fellowship.

References

Appendix A Detailed comparison with existing rates

Appendix B Comparison: multi-point queries and mean-squared smoothness

Stochastic first-order methods that utilize variance reduction (Lei et al. 2017; Fang et al. 2018; Zhou et al. 2018) employ the following mean-squared smoothness (MSS) assumption on the stochastic gradient estimator:

Algorithms that take advantage of the MSS structure rely on the following additional simultaneous query assumption (which is a special case of (4) for $n=2$):

In empirical risk minimization problems, $z$ represents the datapoint index and possibly data augmentation parameters, and the value of $z$ is typically part of the query, which means that assumption (16) indeed holds. In certain online learning settings, however, the assumption can fail. For example, the variable $z$ could represent the instantaneous power demands in an electric grid, and testing two grid configurations for the same grid state might be impractical.

We observe that assuming access to both an MSS gradient estimator and simultaneous two-point queries is stronger than assuming a bounded variance stochastic Hessian-vector product estimator. This holds because the former allows us to simulate the latter with finite differencing. Formally, we have the following.

Let $F$ have $L_{2}$-Lipschitz Hessian, let $\widehat{\nabla F}$ satisfy (15), and assume we have access to a two-point query oracle as in (16). Then, for any $\delta>0$ and every unit-norm vector $u$, the Hessian-vector product estimator

which implies the bound on the bias. To bound the variance, we note that

We conclude from Observation 1 that Algorithm 2, which only requires stochastic Hessian-vector products, attains $O(\epsilon^{-3})$ complexity under assumptions no stronger than previous algorithms. In fact, we show now that our assumptions are in fact strictly weaker than prior work. That is, while an MSS gradient estimator implies a bounded variance Hessian estimator, the opposite is not true in general. This is simply due to the fact that in our oracle model, $\widehat{\nabla F}$ and $\widehat{\nabla^{2}F}$ can be completely unrelated. Consider for example the case where $P_{z}$ is uniform on $\{-1,1\}$ and

Clearly $\widehat{\nabla F}$ is not MSS, even though $\widehat{\nabla^{2}F}$ has zero variance.

There is, however, an important setting where bounded variance for $\widehat{\nabla^{2}F}$ does imply that $\widehat{\nabla F}$ is MSS. Suppose that the derivative of $\widehat{\nabla F}(x,z)$ exists, and has the form

That is, the Hessian estimator is the Jacobian of the gradient estimator. In this case, bounded variance for the Hessian estimator implies mean-squared smoothness.

Taking the squared norm, applying Jensen’s inequality, and substituting the variance bound (3) gives the MSS property (15). ∎

The property (18) holds for empirical risk minimization, where we have the more general relation $\widehat{\nabla^{p}F}(x,z)=\nabla^{p}\widehat{F}(x,z)$ for any $p$; That is, all the stochastic derivative estimators are themselves the derivatives of a single stochastic function. Therefore, by Observation 1 and Observation 2, in empirical risk minimization settings, mean-square smoothness is essentially equivalent to bounded variance of the stochastic Hessian estimator.

Appendix C Variance-reduced gradient estimator (HVP-RVR)

In this section we prove Lemma 1. First, we formally describe the protocol in which our optimization algorithms query the gradient estimator HVP-RVR-Gradient-Estimator described in Algorithm 1, and define some additional notation.

Given a function $F\in\mathcal{F}_{2}(\Delta,L_{1},L_{2})$ and a stochastic second-order oracle in $\mathcal{O}_{2}(F,\sigma_{1:2})$, the optimization algorithm interacts with HVP-RVR-Gradient-Estimator by sequentially querying points $\left\{x^{(t)}\right\}_{t=1}^{\infty}$ with reset probabilities $\left\{b^{(t)}\right\}_{t=1}^{\infty}$, to obtain estimates $g^{\left(t\right)}$ for $\nabla F(x^{(t)})$ for each time $t$; that is,

where $\mathsf{A}^{(t)},\mathsf{B}^{(t)}$ are measurable mappings modeling the optimization algorithm and $\{r^{(t)}\}$ is an independent sequence of random seeds. This level of formalism is not used within the proof, but we include it here for clarity. That is, Lemma 1 holds for any sequence of queries where $x^{(t)}$, and $b^{(t)}$ are adapted to the filtration

but $b^{(t)}$ is independent of $\mathcal{G}^{(t-1)}$ and $g^{\left(t-1\right)}$.

Lemma 1 is an immediate consequence of Lemma 2 and Lemma 3, proven below, which respectively establish the estimator’s error and complexity bounds.

Given a function $F\in\mathcal{F}_{2}(\Delta,\infty,L_{2})$, a stochastic oracle in $\mathcal{O}_{2}(F,\sigma_{1:2})$, and initial points $x^{(0)}$ and $g^{(0)}=\bot$, let $\{g^{(t)}\}_{t\geq 0}$ denote the sequence of gradient estimates at $\{x^{(t)}\}_{t\geq 0}$ respectively, returned by HVP-RVR-Gradient-Estimator under the protocol (19). Then, for all $t\geq 1$,

whence the result follows by a simple induction whose basis is

Moreover, conditional on $C^{(t)}=0$, we have from the definition of the gradient estimator that

where $x^{(t,k)}$ and $x^{(t,k)}$ respectively denote the values of $x^{(k)}$ and $z^{(k)}$ (defined on Line 9) during the $t^{\text{th}}$ call to Algorithm 1.

We may therefore decompose the error conditional on $C^{(t)}=0$ as

where $\left(i\right)$ is due to $\mathfrak{e}^{(t-1)}\in\mathcal{G}^{(t)}$ and $\left(ii\right)$ is due to Young’s inequality.

The facts that $z^{(t,k)}$ is independent from $\mathcal{G}^{(t)}$, that $\nabla F(x^{(t)})-\nabla F(x^{(t-1)})\in\mathcal{G}^{(t)}$, and that $\widehat{\nabla^{2}F}(\cdot)$ is unbiased give

for every $t$. Consequently, the scaling (22) and Hessian estimator variance bound imply

where the equality $(\star)$ above is due to the fact that $z^{(t,1)},\ldots,z^{(t,K^{(t)})}$ are i.i.d., as well as $x^{(t,k)}-x^{(t,k-1)}=\frac{1}{K^{(t)}}(x^{(t)}-x^{(t-1)})$.

Substituting back through equations (25), (24), (23), (21) and (20), we have

as required; the second inequality follows from algebraic manipulation and the fact that $\mathfrak{e}^{(t-1)}$ is independent of $b^{(t)}$ by assumption. ∎

The following lemma bounds the number of oracle queries made per call to the gradient estimator.

where the final inequality follows from $\left\lceil x\right\rceil\leq x+1$. ∎

Appendix D Supporting technical results

In order to find the negative curvature direction at a given point or to build a cubic regularized sub-model, Algorithm 3 and Algorithm 5 estimate the Hessian by computing an empirical average of the stochastic Hessian queries to the oracle. The following lemma is a standard result which bounds the expected error for the empirical Hessian.

This is an immediate consequence of Lemma 5 below, using $A_{i}\vcentcolon={}\widehat{\nabla^{2}F}(x,z^{(i)})$ and $B\vcentcolon={}\nabla^{2}F(x)$. ∎

We drop the normalization by $n$ throughout this proof. We first symmetrize. Observe that by Jensen’s inequality we have

where the second inequality follows by Jensen. We now apply the matrix Khintchine inequality (Mackey et al. 2014, Corollary 7.4), which implies that

Putting all the developments so far together and taking expectation with respect to $A$, we have

To obtain the final result we normalize by $n^{2}$. ∎

D.2 Descent lemma for stochastic gradient descent

The following lemma characterizes the effect of gradient descent update step used by Algorithm 2 and Algorithm 4.

Given a function $F\in\mathcal{F}_{2}(\Delta,L_{1},\infty)$, a point $x$, and gradient estimator $g{}$ at x, define

Then, for any $\eta\leq\frac{1}{2L_{1}}$, the point $y$ satisfies

Since, the gradient of $F$ is $L_{1}$-Lipschitz, we have

where $\left(i\right)$ uses that $y-x=\eta g$, $\left(ii\right)$ is due to the Cauchy-Schwarz inequality, $\left(iii\right)$ is given by an application of the AM-GM inequality and $\left(iv\right)$ holds because $\eta\leq\frac{1}{2L_{1}}$. Finally, $\left(v\right)$ follows by invoking Jensen’s inequality for the function $\left\|\cdot\right\|^{2}$ to upper bound $\left\|\nabla F(x)\right\|^{2}\leq 2\left(\left\|\nabla F(x-g)\right\|^{2}+\left\|g\right\|^{2}\right)$. Rearranging the terms in (26), we get,

D.3 Descent lemma for cubic-regularized trust-region method

The following lemmas establish properties for the updates step involving constrained minimization of the cubic regularized model in used in Algorithm 3 and Algorithm 5.

Since $\nabla^{2}F$ is $L_{2}$-Lipschitz, we have

where $\left(i\right)$ follows by the definition of the operator norm and $\left(ii\right)$ follows by observing that $\left\|y-x\right\|\leq\eta$. Rearranging the terms, we have

Under the same setting as Lemma 7, the point $y$ satisfies

Since one of the two cases ($\left\|y-x\right\|<\eta$ or $\left\|y-x\right\|=\eta$) must hold, we have,

Rearranging the terms, and using the fact that $M\geq 2L_{2}$, we have

Finally, using the fact that for any $a,b\geq 0$, $\min\left\{a,b\right\}\leq a\boldsymbol{1}\left\{b\geq a\right\}$, we have

where $\Pr(\cdot)$ and $\En\left[\cdot\right]$ are taken with respect to the randomness over $H$ and $g$.

For the ease of notation, let $\chi$ and $\zeta$ denote the error in the gradient estimator $g$ and the hessian estimator $H$ at $x$ respectively, i.e.

We prove the desired statement by combining the following two results.

First, plugging $x=x$, and $z=y$ in to Lemma 7, we have

Taking expectations on both the sides, we get,

where the last inequality follows from an application of Jensen’s inequality.

Similarly, plugging $x=x$, $z=y$ in Lemma 8, we get

Raising both the sides with the exponent of $\frac{3}{2}$, we get

Taking expectations on both the sides and rearranging the terms implies that

where the last inequality follows from an application of the Jensen’s inequality.

The final statement follows from the above inequality by using the definition of $\chi$ and $\zeta$.

D.4 Stochastic negative curvature search

The following lemma establishes properties of the negative curvature search step used in Algorithm 4 and Algorithm 5.

where $r$ is an independent Rademacher random variable and $u$ is an arbitrary unit vector such that $H[u,u]\leq-2\gamma$. Then, the point $y$ satisfies

where $\Pr(\cdot)$ and $\En\left[\cdot\right]$ are taken with respect to the randomness in $H$ and $r$.

In the second case, Taylor expansion for $F(y)$ at $F(x)$ implies that

Taking expectation on both the sides gives the desired statement:

The following lemma establishes properties of Oja’s method ($\mathsf{Oja}$), as used in Algorithm 4.

$u=\bot$, and $\nabla^{2}F(x)\succeq-2\gamma I$.

if $u\neq\bot$, then $\left\|u\right\|=1$ and $\langle u,\nabla^{2}F(x)u\rangle\leq-\gamma$.

Moreover, when invoked as above, the procedure uses at most

queries to the stochastic Hessian-vector product oracle.

Appendix E Upper bounds for finding ϵ\epsilon-stationary points

In the following, we first show that Algorithm 2 returns a point $\widehat{x}$ such that, $\En\left[\left\|\nabla F(\widehat{x})\right\|\right]\leq 32\epsilon$. We then bound the expected number of oracle queries used throughout the execution. In the proof, we show convergence to a $32\epsilon$-stationary point. A simple change of variable, i.e. running Algorithm 2 with $\epsilon\leftarrow\frac{\epsilon}{32}$, returns a point $\widehat{x}$ that enjoys the guarantee that $\left\|\nabla F(\hat{x})\right\|\leq\epsilon$.

where the last inequality follows from the fact that $F(x^{(0)})-F(x^{(T+1)})\leq\Delta$. Next, taking expectation on both the sides (with respect to the stochasticity of the oracle and the algorithm’s internal randomization), we get

Using Lemma 2, we have $\En\left[\left\|\nabla F(x^{(t)})-g^{\left(t\right)}\right\|^{2}\right]\leq\epsilon^{2}$ for all $t\geq 1$. Dividing both the sides by $\frac{\eta T}{8}$, and plugging in the value of the parameters $T$ and $\eta$, we get,

Thus, for $\widehat{x}$ chosen uniformly at random from the set $\left(x^{(t)}\right)_{t=1}^{T}$, we have

Finally, Markov’s inequality implies that with probability at least $\frac{7}{8}$,

Algorithm 2 queries the stochastic oracle in only when it invokes HVP-RVR in Line 5 to compute the gradient estimate $g^{(t)}$ at time $t$. Let $M$ denote the total number of oracle calls made up until time $T$. Invoking Lemma 3 to bound the expected number of stochastic oracle calls for each $t\geq 1$, and ignoring all the mutiplicative constants, we get

where $\left(i\right)$ is given by plugging in the update rule from Line 6 and by dropping multiplicative constants, $\left(ii\right)$ is given by rearranging the terms, plugging in the value of $T$ and using that $T\geq 1$ (to simplify the ceiling operator) under the assumption $\epsilon\leq\sqrt{\Delta L_{1}}$, and $\left(iii\right)$ follows by observing that

as a consequence of Lemma 2 and the bound in (33). Next, note that since we assume $\epsilon<\sigma_{1}$, and since we have $\eta\leq\frac{1}{2\sqrt{\sigma_{2}^{2}+\epsilon L_{2}}}$, the parameter $b$ is equal to $\frac{\eta\epsilon\sqrt{\sigma_{2}^{2}+\epsilon L_{2}}}{\sigma_{1}}$ (as this is smaller than $1$). Thus, plugging the value of $b$ and $\eta$ in the bound (35), we get,

Using Markov’s inequality, we have that with probability at least $\frac{7}{8}$,

The final statement follows by taking a union bound with failure probabilities for (34) and (36). ∎

E.2 Proof of Theorem 2

In the following, we first show that Algorithm 3 returns a point $\hat{x}$, such that with probability at least $\frac{7}{8}$, $\left\|\nabla F(\hat{x})\right\|\leq 350\epsilon$. We then bound, with probability at least $\frac{7}{8}$, the total number of oracle queries made up until time $T$.

Note that, using Lemma 2 and Lemma 4, we have for all $t\geq 0$,

Thus, for each $t\geq{}1$, invoking Lemma 9 and plugging in the bounds from (37), and using the value of $\eta$, we get

Telescoping this inequality from $t=1$ to $T$, we have that

where the equality follows because $\widehat{x}$ is sampled uniformly at random from the set $\left\{x^{(t)}\right\}_{t=2}^{T+1}$. Next, using the fact that, $F(x^{(t)}){}-F\left(x^{(T+1)}\right)\leq\Delta$, rearranging the terms, and plugging in the value of $T$, we get

Thus, with probability at least $\frac{7}{8}$,

Algorithm 3 queries the stochastic oracle in Line 6 and Line 7 only to compute the respective Hessian and gradient estimates. Let $M_{h}$ and $M_{g}$ denote the total number of stochastic oracle queries made by Line 6 and Line 7 till time $T$ respectively. Further, Let $M=M_{h}+M_{g}$ denote the total number of oracle queries made till time $T$.

In what follows, we first bound $\En\left[M_{h}\right]$ and $\En\left[M_{g}\right]$. Then, we invoke Markov’s inequality to deduce that the desired bound on $M$ holds with probability at least $\frac{7}{8}$.

Bound on $\En\left[M_{h}\right]$. Since the algorithm queries the stochastic Hessian oracle $n_{H}$ times per iteration, $M_{h}=T\cdot n_{H}$. Plugging the values of $T$, $n_{H}$ and $M$ as specified in Algorithm 3, and ignoring multiplicative constant, we get,

where the first inequality above follows from the fact that $\frac{\Delta\sqrt{M}}{\epsilon^{1.5}}\geq 1$ under the natural choice for the precision parameter $\epsilon\leq\Delta^{\frac{2}{3}}M^{\frac{1}{3}}$ and using the identity $\left\lceil x\right\rceil\leq x+1$ for $x\geq 0$.

Bound on $\En\left[M_{g}\right]$. Invoking Lemma 3 for each $t\geq 1$, we get

where $\left(i\right)$ follows by observing $\left\|x^{(t)}-x^{(t-1)}\right\|\leq\eta$ due to the update rule in Line 8 and $\left(ii\right)$ is given by plugging in the value of $T\leq O(\frac{\Delta}{\eta\epsilon})$ for the natural choice of parameter $\epsilon=O(\Delta^{\frac{2}{3}}M^{\frac{1}{3}})$. Next, note that since $M>L_{2}$, and since we assume $\epsilon<\sigma_{1}$, the parameter $b$ is equal to $\frac{\eta\sqrt{\sigma_{2}^{2}+\epsilon L_{2}}}{25\sigma_{1}}$ (which is smaller than $1$). Thus, plugging the value of $b$ and $\eta$ in the bound (40), we get

where the second equality follows by using that $\epsilon\leq{}\sigma_{1}$ to simplify the term $\frac{\Delta\sqrt{M}}{\epsilon^{1.5}}$.

Adding (41) and (39), the total number of oracle queries made by Algorithm 3 till time $T$ is bounded, in expectation, by

Using Markov’s inequality, we get that, with probability at least $\frac{7}{8}$,

The final statement follows by taking a union bound for the failure probability of (38) and (42).

Appendix F Upper bounds for finding (ϵ,γ)(\epsilon,\gamma)-second-order-stationary points

To begin, note that, for any $t\geq 1$, there are two scenarios: (a) either $Q_{t}=1$ and $x^{(t+1)}$ is set using the update rule in Line 8, or, (b) $Q_{t}=0$ and we set $x^{(t+1)}$ using Line 11, respectively. We analyze the two cases separately below.

Taking expectation on both the sides, while conditioning on the event that $Q_{t}=1$, we get

where the last inequality follows using Lemma 2.

Let $\mathsf{E}^{\mathsf{Oja}}(t)$ denote the event that $\mathsf{Oja}$ succeeds at time $t$, in the sense that the event in Lemma 11 holds: $(i)$ if $u^{(t)}=\bot$ then $\nabla^{2}F(x^{(t)})\succeq-2\gamma I$, and $(ii)$ otherwise, $u^{(t)}$ satisfies $\langle u^{(t)},\nabla^{2}F(x^{(t)})u^{(t)}\rangle\leq-\gamma$.

Then, using Lemma 12, we are guaranteed that

In particular, we are guaranteed by Lemma 11 that

Combining the two cases ($Q_{t}=0$ and $Q_{t}=1$) from (43) and (44) above, we get

Using that $\En\left[\left\|\nabla F(x^{(t)})\right\|^{2}\right]\geq(8\epsilon)^{2}\cdot\Pr\left(\left\|\nabla F(x^{(t)})\right\|\geq 8\epsilon\right)$ and that $\delta\leq{}\frac{\gamma}{1600L_{1}}$, we have

Telescoping this inequality for $t$ from $1$ to $T$ and using the bound $\En\left[F(x^{(1)})-F(x^{(T+1)})\right]\leq\Delta$, we get

where $\left(i\right)$ follows because $\widehat{x}$ is sampled uniformly at random from $\left(x^{(t)}\right)_{t=1}^{T}$ and $\left(ii\right)$ follows from Lemma 14. Rearranging the terms, we get

For any $t>0$, there are two scenarios, either (a) $Q_{t}=1$ and we go through Line 8, or (b) $Q_{t}=0$ and Line 18 is executed. Thus,

We denote the two terms on the right hand side above by $(\text{\bf A})$ and $(\text{\bf B})$, respectively. We bound them separately as follows.

Bound on $(\text{\bf A})$. Using Lemma 3 with the fact that $\Pr\left(Q_{t}=0\right)=1-p$, we get

where $\left(i\right)$ is given by plugging in $\|x^{(t)}-x^{(t-1)}\|=\gamma/L_{2}$. The inequality $\left(ii\right)$ follows by using the bound on $T\cdot(1-p)$ from Lemma 14.

Bound on $(\text{\bf B})$. Using Lemma 3 with the fact that $\Pr\left(Q_{t}=1\right)=p$, we get

where $\left(i\right)$ follows by plugging in the update rule from Line 8 (when $Q_{t}=1$), $\left(ii\right)$ follows by rearranging the terms and using the bound on $T\cdot p$ from Lemma 14, and $\left(iii\right)$ is follows from the choices of $b_{g}$ (in particular, our assumption that $\epsilon\leq{}\sigma_{1}$ implies that $b_{g}=\frac{\eta\epsilon\sqrt{\bar{\sigma}_{2}^{2}+\epsilon L_{2}}}{\sigma_{1}}$) and $\eta$, as well as the following bound for $\En\left[\frac{1}{T}\sum_{t=1}^{T}\left\|g^{\left(t\right)}\right\|^{2}\right]$:

where the last inequality is uses Lemma 2 and Lemma 13.

Combining the bounds from (50) and (51) in (49), we have

Using the law of total probability with the observation that Algorithm 4 enters Line 11 only if $Q_{t}=0$, we get

where $n_{H}$ denotes the number of oracle queries made by $\mathsf{Oja}$, the last inequality follows by bounding $T\cdot(1-p)$ as in (47). Note that Lemma 11 implies that for $\delta=\frac{\gamma}{1600L_{1}}$,

Plugging in the value of $\eta$ from Algorithm 4 and $n_{H}$ from (54), and using Markov’s inequality, we get that, with probability at least $\frac{15}{16}$,

The final statement follows by taking a union bound for the failure probability of the claims in (48) and (55). ∎

Under the setting of Theorem 4, we are guaranteed that

Taking conditional expectations, this further implies that

Otherwise, using a third-order Taylor expansion, and following the same reasoning as the proof of Lemma 10, we have

Combining this bound with the earlier inequalities (and being rather loose with constants), we conclude that

Under the same setting as Theorem 4, the point $\widehat{x}$ returned by Algorithm 4 satisfies

Starting from (46) in the proof of Theorem 4, we have

Telescoping this inequality for $t$ from $1$ to $T$ and using that $F(x^{(1)})-F(x^{(T+1)})\leq\Delta$, we get

where the last inequality follows from Lemma 14. Rearranging the terms, we get

where the last inequality uses that $\delta\leq{}\frac{\gamma}{1600L_{1}}$. ∎

For the values of the parameters $T$ and $p$ specified in Algorithm 4,

Since, $\eta\leq\frac{1}{2\sqrt{L_{1}^{2}+\bar{\sigma}_{2}^{2}+\epsilon L_{2}}}\leq\frac{1}{2L_{1}}$ and $\epsilon\leq\sqrt{\Delta L_{1}}$, we have that