Lower Bounds for Non-Convex Stochastic Optimization

Introduction

Stochastic gradient methods—especially variants of stochastic gradient descent (SGD)—are the workhorse of modern machine learning and data-driven optimization more broadly. Much of the success of these methods stems from their broad applicability: any problem that admits an unbiased gradient estimator is fair game. Consequently, there is considerable interest in understanding the fundamental performance limits of methods using stochastic gradients across broad problem classes. For convex problems, a long line of work sheds lights on these limits, and they are by now well-understood. However, many problems of interest (e.g., neural network training) are not convex. This has led to intense development of improved methods for non-convex stochastic optimization, but little is known about the optimality of these methods. In this paper, we establish new fundamental limits for stochastic first-order methods in the non-convex setting.

The use of stationarity as a convergence criterion dates back to the early days of nonlinear optimization [cf. 45, 37]. Recent years have seen rapid development of a body of work that studies non-convex optimization through the lens of non-asymptotic convergence rates to $\epsilon$-stationary points . Another growing body of work motivates this study by identifying sub-classes of non-convex problems for which all stationary (or second-order stationary) points are globally optimal .

At the $t$th optimization step, the algorithm queries at a point $x^{(t)}$, the oracle draws $z^{(t)}\sim{}P_{z}$, and the algorithm observes the noisy gradient estimate $g(x^{(t)},z^{(t)})$. We make the standard assumption that the objective $F$ has bounded initial subobtimality and Lipschitz gradient:

Following common practice, we refer to functions $F$ with $L$-Lipschitz gradients as “$L$-smooth.”

The stochastic gradient $g$ satisfies a mean-squared smoothness property

The algorithm is allowed $K$ simultaneous queries: at step $t$, the algorithm queries $x^{(t,1)},\ldots,x^{(t,K)}$ and observes $g(x^{(t,1)},z^{(t)}),\ldots,g(x^{(t,K)},z^{(t)})$, where the random seed $z^{(t)}\sim{}P_{z}$ is shared.

We prove lower bounds for finding stationary points in the stochastic first-order oracle model. Our main result is Theorem 3, which states:

When $g$ also satisfies the mean-squared smoothness property (4), every randomized algorithm requires $c\cdot\left(\Delta{}\bar{L}\sigma\epsilon^{-3}+\sigma^{2}\epsilon^{-2}\right)$ oracle queries.

Both lower bounds hold for any number $K$ of simultaneous queries, with the dimension $d$ of the hard instance depending polynomially on $K$ and $\epsilon^{-1}$ (see expressions for $d$ in Section 1.2 below).

Our lower bounds continue to hold when the oracle is subject to more stringent assumptions. In particular, we show that gradient estimators of the form $g(x,z)=\nabla_{x}f(x,z)$ give rise to the same lower bounds; these gradient estimators arise in statistical learning problems such as empirical risk minimization. Furthermore, our results extend to active oracles where the algorithm may choose the seed $z$. This setting includes the special case of finite sum minimization, where $F(x)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(x)$, each oracle query consists of point $x$ and index $i$, and the oracle response is $\nabla f_{i}(x)$.

The main implications of our results are as follows.

Optimality of SGD and recent variance-reduction schemes. Our $\epsilon^{-4}$ lower bound matches (up to a numerical constant) the rate of convergence of SGD under assumptions (2) and (3), thereby characterizing the optimal complexity and proving that SGD attains it. Similarly, under the additional assumption (4) our $\epsilon^{-3}$ lower bound matches the rates of Fang et al. and Zhou et al. , thereby proving their optimality.

Separation between smoothness assumptions. Our results highlight that the mean-squared smoothness assumption (4) is critical for variance reduction: we prove that in its absence, any scheme will require a number of queries that scales as $\epsilon^{-4}$ at least. These results are salient, as this assumption appears in numerous recent works on non-convex optimization .

Separation between convex and non-convex stochastic optimization. Foster et al. show that for convex functions satisfying assumptions (2) and (3), the optimal rate for finding $\epsilon$-stationary points is $\widetilde{\Theta}(\sqrt{\Delta{}L\epsilon^{-2}}+\sigma^{2}\epsilon^{-2})$. Our $\Omega(\Delta L\sigma^{2}\epsilon^{-4})$ lower bound thus implies a gap between the convex and non-convex setting that scales as $\epsilon^{-2}$. Conceptually, both rates admit a simple interpretation. The convex complexity is the sum of the noiseless convex optimization complexity $\sqrt{\Delta{}L\epsilon^{-2}}$ and the estimation complexity $\sigma^{2}\epsilon^{-2}$. In contrast, in the non-convex case the noiseless complexity $\Delta L\epsilon^{-2}$ and the estimation complexity $\sigma^{2}\epsilon^{-2}$ multiply rather than add. This observation underpins our proofs.

2 Our approach

Proving the $\epsilon^{-3}$ lower bound requires additional nuance, as the “incoming coordinate” index $i_{x}$ is not continuous in $x$, and so the gradient estimator above does not satisfy the mean-square smoothness requirement (4). Leveraging the special structure of the noiseless construction once more, we design a continuous surrogate for $i_{x}$, and arrive at a mean-square smooth construction for which $g_{i_{x}}(x,z)$ is again non-zero only with probability $p$. Scaling this construction such that $L=\Theta(\bar{L}\epsilon/\sigma)$ yields the $\epsilon^{-3}$ lower bound.

For ease of exposition, we first carry out our proof strategy for the sub-class of “zero-respecting” algorithms, whose queries are non-zero only in coordinates where previous oracle responses were not zero. We then lift our results to the class of all randomized algorithms using the method of random rotations . On a high level, we argue that in a random coordinate system, any algorithm operating on our constructions is essentially zero-respecting.

Our lower bound constructions are high-dimensional. For zero-respecting algorithms, the dimension we require is exactly the number of relevant coordinates: $d_{\mathsf{zr}}=\Theta(\Delta L\epsilon^{-2})$ for the bounded variance case and $d_{\mathsf{zr}}=\Theta(\Delta\bar{L}\sigma^{-1}\epsilon^{-1})$ for the mean-square smooth case. To handle general, potentially randomized algorithms that allow $K$ simultaneous oracle queries for every random realization $z\sim P_{z}$, we add many irrelevant coordinates, and our proof requires dimension $\widetilde{O}(Kd_{\mathsf{zr}}^{2}/p)$, where $p=\Theta(\epsilon^{2}/\sigma^{2})$ is the progress probability. Lower bound constructions with dimension that scales polynomially in $\epsilon^{-1}$ are common , and natural for algorithms that (nominally) work in arbitrary Hilbert spaces. In the noiseless setting, obtaining tight and algorithm-independent lower bounds on dimension-independent convergence rates necessitates high-dimensional constructions; see Carmon et al. [13, Section 1.2] for additional discussion. Since the noiseless setting is a special case of our noisy setting, it seems likely that here too high-dimensional constructions are to some extent unavoidable.

3 Related work

Lower bounds for first-order convex optimization in the noiseless setting are well-studied . For $L$-smooth functions in the high-dimensional regime, it is well-known that \Theta\big{(}\sqrt{D^{2}L\epsilon^{-1}}\big{)} gradient evaluations are necessary and sufficient to find an $\epsilon$-suboptimal point given $x^{(0)}$ with $\left\|x^{(0)}-x^{\star}\right\|\leq{}D$; Nesterov’s accelerated gradient method achieves this rate.

For smooth high-dimensional non-convex optimization in the noiseless setting, Carmon et al. establish that $\Theta(\Delta{}L\epsilon^{-2})$ gradient evaluations are necessary and sufficient for finding $\epsilon$-stationary points; this rate is achieved by gradient descent. An earlier line of work develops lower bounds for finding stationary points of non-convex functions in the low-dimensional regime where $d$ is constant, but they obtain either weaker lower bounds or tight bounds that hold only for specific algorithm classes .

A long line of work on lower bounds for stochastic convex optimization traces back to Nemirovski and Yudin’s seminal information-based complexity . Extensions since then have allowed sharp dimension-dependent bounds via reductions to statistical estimation problems , as well as extension to structured problems common in machine learning, such as finite sums, by restrictions on the form of the update rules and high-dimensional constructions . Our technique for proving stochastic lower bounds differs qualitatively from these methods in that we preserve the sequential hardness of the noiseless non-convex lower bound construction of , and use the noise in the stochastic setting to amplify the hardness of this construction.

For non-convex stochastic optimization, few lower bounds are known. Drori and Shamir recently showed that SGD itself cannot obtain a rate better than $\epsilon^{-4}$ for finding $\epsilon$-stationary points, even for convex functions. This is an algorithm-specific result, whereas we show that no algorithm can improve over this rate. For finite sum problems where $F(x)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(x)$, Fang et al. show that $\Omega\left(\Delta{}\bar{L}\epsilon^{-2}\sqrt{n}\right)$ stochastic gradient queries are required to find a $\epsilon$-stationary point; SPIDER and SNVRG have matching upper bounds. This lower bound is incomparable to ours: the stochastic gradient construction in the paper has unbounded variance, so it cannot imply results along the lines of Theorem 3. Indeed, Fang et al. leave obtaining the $\epsilon^{-3}$ lower bound we provide in Theorem 3 as an open problem.

We now turn to upper bounds for finding stationary points in the stochastic setting. In the convex setting (where achieving approximate global optimality is possible and hence usually the goal) Allen-Zhu proposes algorithms with rates for finding stationary points improving over SGD, and Foster et al. give improvements on these bounds and establish their optimality. For the non-convex setting, Ghadimi and Lan establish an $O(\Delta{}L\sigma^{2}\epsilon^{-4})$ upper bound for SGD, and a large body of recent work attempts to improve this rate. These attempts roughly divide into two categories: variance reduction and high-order information.

Works in the variance reduction category make either the mean-squared smoothness assumption (4) or a stronger variant wherein every $g(\cdot,z)$ is $\bar{L}$-Lipschitz. The earliest results consider only the finite sum setting, and establish improved dependence on the number of summands . Under the bounded variance assumption (2), Lei et al. obtain a rate of $\epsilon^{-10/3}$, demonstrating that in the non-convex setting variance reduction provides benefits beyond finite sum optimization. Subsequent algorithms by Fang et al. and Zhou et al. obtain an improved rate of $\epsilon^{-3}$, which we prove is optimal. Recent work offers further refinements of these algorithms that also obtain the $\epsilon^{-3}$ rate.

Smoothness in higher derivatives, such as Lipschitz continuity of the Hessian, allows additional possibilities . Tripuraneni et al. provide a sub-sampled cubic regularization method that uses stochastic Hessian-vector products and attains a rate of $\epsilon^{-3.5}$ without relying on mean-squared smoothness (4) or simultaneous gradient queries. Fang et al. show that it is possible to obtain the rate $\epsilon^{-3.5}$ using SGD with perturbed gradients and restarts without the need for Hessian-vector products. Most works that assume Lipschitz Hessian also provide guarantees for finding second-order stationary points.

4 Organization

Section 2 introduces the formal oracle model in which we prove our lower bounds. In Section 3, we prove our results for the subclass of zero-respecting algorithms. In Section 4 we apply random rotations to prove lower bounds for all randomized algorithms, leading to our main result. Section 5 describes the extensions of our results to statistical learning and active oracles, and Section 6 concludes with discussion of some remaining open problems.

Setup

We study the stochastic optimization problem of finding an $\epsilon$-stationary point through the well-known framework of oracle complexity , which we set up formally in this section.

We develop lower bounds for algorithms that find stationary points of functions in the set

We state explicitly the value of the dimension $d$ required for each lower bound construction; the reader may otherwise regard $d$ as a free parameter.

of size $K$, and for each batch query $x^{(i)}$, the oracle $\mathsf{O}$ performs an independent draw $z^{(i)}\sim{}P_{z}$ and responds with

When $K=1$ this is the classical first-order stochastic optimization framework. By considering larger batches we can subsume variance-reduction methods such as SPIDER and SNVRG , both of which query each stochastic gradient at $K=2$ points.See also the $K$-parallel model of Nemirovski . Note that we allow the algorithm to observe the function value $F(x)$ exactly for each query, which is a weaker assumption than typical in lower and upper bounds for stochastic optimization.

where $r\sim P_{r}$ is drawn a single time at the beginning of the protocol (this is no loss of generality ). We define $\mathcal{A}_{\textnormal{{rand}}}(K)$ to be the class of all algorithms that follow the protocol (6) with $K$ batch queries per round.

We consider two natural classes of oracles. For the bounded variance class, denoted $\mathcal{O}(K,\sigma^{2})$, we require that the stochastic gradient be unbiased and have the bounded variance property (2), but otherwise allow arbitrary $g(x,z)$. This well-studied setting subsumes the standard analysis of stochastic gradient descent for finding approximate stationary points .

The bounded variance setting places few restrictions on the stochastic gradient function $g(x,z)$, but there are many applications in which the stochastic gradients may have additional structure. In the mean-squared smooth setting, we require that in addition to the bounded-variance property (2), the stochastic gradient satisfies the mean-squared smoothness property (4). We use $\mathcal{O}(K,\sigma^{2},\bar{L})$ to denote the class of all such oracles. By Jensen’s inequality, any function that admits an $\bar{L}$-mean-squared smooth oracle must itself be $\bar{L}$-smooth.

Our results also extend to more structured oracles appearing in the statistical learning and/or finite-sum settings. We defer the details to Section 5.

Our main results are tight lower bounds on the distributional complexity of finding $\epsilon$-stationary points. Let $\mathcal{P}[\mathcal{F}(\Delta,L)]$ be set of all distributions over $\mathcal{F}(\Delta,L)$; the distributional complexity in the bounded variance setting is

where the expectation is over the sampling of $F$ from $P_{F}$, the randomness in the oracle $\mathsf{O}$, and the randomness in the algorithm $\mathsf{A}$, though randomization in $\mathsf{A}$ does not affect distributional complexity . The distributional complexity for the mean-squared smooth setting is

Lower bounds for zero-respecting algorithms

Before presenting our results in full generality, we first develop the key components of our technique by proving lower bounds for a restricted class of zero-respecting algorithms . The class of zero-respecting algorithms generalizes the well-known linear span-assumption [see 34, Section 2.1.2], and encompasses many standard optimization algorithms. More importantly, the lower bound instances we introduce in this section form the core of our lower bounds for general algorithms via a reduction in the next section.

An algorithm $\mathsf{A}$ is zero-respecting if its queries at each round have support in the supports of all previous oracle responses:

A stochastic first-order algorithm $\mathsf{A}$ is zero-respecting if for any oracle $\mathsf{O}$ and any realization of $z^{(1)},z^{(2)},\ldots$, for all $t\geq 1$ and $k\in\left[K\right]$,

where \big{(}f^{(t,1)},g^{(t,1)}\big{)},\ldots,\big{(}f^{(t,K)},g^{(t,K)}\big{)}=\mathsf{O}_{F}\big{(}x^{(t)}_{\mathsf{A}[\mathsf{O}_{F}]},z^{(t)}\big{)} denote the oracle responses for round $t$.

We let $\mathcal{A}_{\textnormal{{zr}}}(K)$ denote the class of all zero-respecting algorithms. Our main result for this section is to establish tight lower bounds on the minimax oracle complexity for zero-respecting algorithms, which we denote by $\mathfrak{m}_{\epsilon}^{\mathsf{zr}}(K,\Delta,L,\sigma^{2})$ for the bounded variance setting and $\bar{\mathfrak{m}}_{\epsilon}^{\mathsf{zr}}(K,\Delta,\bar{L},\sigma^{2})$ for the mean-squared smooth setting; these complexities are as in (7) and (8), with $\mathcal{A}_{\textnormal{{zr}}}(K)$ replacing $\mathcal{A}_{\textnormal{{rand}}}(K)$. The zero-respecting structure allows us to attain tight lower bounds using $P_{F}$ supported on a single hard function.

At the core of our development is an embedding of the task of finding a stationary point into that of finding a point $x$ with high coordinate progress, which we define as

Our key insight is that in the stochastic setting, noise can amplify progress control: we construct stochastic gradient functions for which any zero-respecting algorithm requires many queries in order to activate one coordinate. We call such functions probabilistic zero-chains.

A stochastic gradient function $g(x,z)$ is a probability-$p$ zero-chain if

The next lemma formalizes the idea that any zero-respecting algorithm interacting with a probabilistic zero-chain requires many rounds to discover all coordinates.

We define two measures of the algorithm’s progress:

for all $t$, with probability 1, where we let $\gamma^{(0)}\equiv 0$. Therefore, it suffices to show that

To show this, first observe that with probability $1$,

where inequality $(\star)$ holds by the zero chain property (12), and the other inequalities hold by definition. Since $x^{(t)}\in\mathcal{G}^{(t-1)}$, we have that $g^{(t,k)}=g(x^{(t,k)},z^{(t)})$ is independent of $x^{(t)}$ given $\mathcal{G}^{(t-1)}$. Consequently, the zero-chain property (11) implies that

Therefore, denoting the increment $\iota^{(t)}\coloneqq\gamma^{(t)}-\gamma^{(t-1)}$, we have via the Chernoff method,

2 Lower bound for the bounded variance setting

Lemma 1 suggests a natural lower bound strategy:

Construct $g$, a probability-$p$ zero chain gradient estimator for $F$.

Together with Lemma 1, these steps guarantee that any zero-respecting algorithm interacting with $g$ will take at least $\Omega(T/p)$ rounds to make the gradient of $F$ small. We first execute our strategy for the bounded variance setting (2).

where the component functions $\Psi$ and $\Phi$ are

$F_{T}(0)-\inf_{x}F_{T}(x)\leq\Delta_{0}\cdot T$, where $\Delta_{0}=12$.

We now turn to the construction of a probabilistic zero-chain for $F_{T}$. The main technical difficulty in the construction lies in keeping the variance of the stochastic gradient function bounded and, in particular, independent of the dimension $T$. Indeed, consider a naive construction that when queried at point $x$, returns with probability $1-p$ and returns $\frac{1}{p}\cdot\nabla F_{T}(x)$ with probability $p$. While this is clearly a probability-$p$ zero-chain, the variance at point $x$ is \Omega\big{(}{\left\|\nabla F_{T}(x)\right\|^{2}_{2}}/{p}\big{)}, which can be as large as $T/p$. As we let the dimension $T$ depend polynomially on $1/\epsilon$, removing this dimension dependence from the variance is critical for making the oracle belong to $\mathcal{O}(K,\sigma^{2})$ after rescaling.

The stochastic gradient estimator $g_{T}$ is a probability-$p$ zero-chain, is unbiased for $\nabla F_{T}$, and has variance

where the last inequality follows from Lemma 2.3. ∎

With the construction in hand, we prove our first lower bound.

There exist numerical constants $c,c^{\prime}>0$ such that for all $L,\Delta,\sigma^{2}>0$ and $\epsilon\leq c^{\prime}\sqrt{L\Delta}$,

Constructions of dimension $d=O\left(\frac{\Delta{}L}{\epsilon^{2}}\right)$ realize the lower bound.

Before giving the proof, let us make a few remarks.

The bound is tight, in that it matches (up to a numerical constant) the convergence rate for SGD (which is zero-respecting) [27, Eq. (2.13)]. Note that the restriction that $\epsilon\leq c^{\prime}\sqrt{L\Delta}$ is without loss of generality, since for $\epsilon>c^{\prime}\sqrt{L\Delta}$ we have $\left\|\nabla{}F(0)\right\|=O(\epsilon)$ for all functions $F\in\mathcal{F}(\Delta,L)$, so an $\epsilon$-stationary point is trivial to find.

The optimal complexity $\Theta(\frac{\Delta{}L\sigma^{2}}{\epsilon^{4}})$ is the product of the first-order oracle complexity for the deterministic setting, which is $\Theta(\frac{\Delta{}L}{\epsilon^{2}})$ , and the sample complexity of estimating a single gradient to precision $\epsilon$, which is $\Theta(\frac{\sigma^{2}}{\epsilon^{2}})$. This is the first setting we are aware of where the product of these respective complexities characterizes the stochastic first-order complexity. Contrast to the convex setting, where the complexity scales with the sum .

The lower bound does not depend on $K$, meaning that additional batch queries cannot by themselves improve on the rate obtained by SGD. While at first glance this may seem like a strange consequence of the zero-respecting assumption, we will show that the same holds true for arbitrary algorithms, provided the dimension is sufficiently large.

Therefore, setting $p=\min\left\{(2\varsigma\epsilon)^{2}/\sigma^{2},1\right\}$ guarantees a variance bound of $\sigma^{2}$.

So with probability at least $1/2$, we have for all $t\leq{}{(T-1)}/{2p}$ and $k\in[K]$ that \big{\|}\nabla F^{\star}_{T}(x^{(t,k)}_{\mathsf{A}[\mathsf{O}_{F}]})\big{\|}>2\epsilon. Therefore,

where the last inequality uses that $\lfloor x\rfloor-1\geq{}x/2$ whenever $x\geq{}3$. ∎

3 Lower bound for the mean-squared smooth setting

which does not approach zero as $\delta\to{}0$.

We define a new stochastic gradient function $\bar{g}_{T}$ by replacing the indicator function in $g_{T}$ with the smoothed indicator $\Theta_{i}$:

This is simply an integrated bump function construction; see Figure 1.

$\Gamma(t)=0$ for all $t\in(-\infty,1/4]$.

$\Gamma(t)=1$ for all $t\in[1/2,\infty)$.

With these properties established, we prove the following mean-squared smooth analogue of Lemma 3.

The stochastic gradient estimator $\bar{g}_{T}$ is a probability-$p$ zero-chain, is unbiased for $\nabla F_{T}$, and satisfies

Our lower bound for the mean-squared smooth setting now follows from another simple scaling argument.

There exist numerical constants $c,c^{\prime}>0$ such that for all $\bar{L},\Delta,\sigma^{2}>0$ and $\epsilon\leq c^{\prime}\sqrt{\bar{L}\Delta}$,

Constructions of dimension $d=O(1+\frac{\Delta\bar{L}}{\sigma\epsilon})$ realize the lower bound.

Theorem 2 is tight, since the upper bounds for SPIDER and SNVRG match it up to constants. As with Theorem 1, the restriction $\epsilon\leq{}O(\sqrt{\bar{L}\Delta})$ is essentially without loss of generality. Theorem 2 leaves open the possibility that there exists an algorithm that achieves $O(\epsilon^{-3})$ in the mean-squared smooth setting using $K=1$; see Section 6 for further discussion.

We defer the proof of Theorem 2 to Appendix A.3, as it is very similar to that of Theorem 1. In particular, it uses the same scaling argument and replaces $L$ with roughly $\bar{L}\epsilon/\sigma$. This results in the final instance scaled as $F^{\star}_{T}(x)\propto{\epsilon\sigma\bar{L}^{-1}}F_{T}(\frac{\bar{L}x}{\sigma})$. The new scaling introduces an additional restriction that $\epsilon\leq{}O(\frac{\Delta\bar{L}}{\sigma})$. When this does not hold, one has $\frac{\Delta\bar{L}\sigma}{\epsilon^{3}}\geq{}c\cdot\frac{\sigma^{2}}{\epsilon^{2}}$, and the claimed lower bound follows from a standard estimation lower bound (see Lemma 10 in Appendix A.1).

Lower bounds for randomized algorithms

We now extend our lower bound construction for zero-respecting algorithms into a lower bound for arbitrary, potentially randomized algorithms. Our main theorem provides optimal lower bounds on the minimax complexities (7) and (8) for the bounded variance and mean-squared smooth settings.

There exist numerical constants $c,c^{\prime}>0$ such that for all $L,\Delta,\sigma^{2}>0$ and $\epsilon\leq c^{\prime}\sqrt{L\Delta}$,

and for all $\bar{L}>0$ and $\epsilon\leq c^{\prime}\sqrt{\bar{L}\Delta}$, we have

Constructions of dimension $\widetilde{O}\left(K\Delta^{2}L^{2}\sigma^{2}\epsilon^{-6}\right)$ realize the lower bound (23) and constructions of dimension $d=\widetilde{O}\left(K\Delta^{2}\bar{L}^{2}\epsilon^{-4}\right)$ realize the lower bound (24).

In the remainder of the section we outline the proof of Theorem 3; we defer all formal proofs to Appendix B. Our approach is to lift the instance developed in the previous section to a hard distribution over functions such that for any randomized algorithm a a function drawn from this distribution is hard high probability. This approach closely follows , though the analysis differs in a few technical points.

Given a function $F(x)$ and a gradient estimator $g(x,z)$, we define the rotated instance

Applying Lemma 5 to the hard instance $(F_{T},\bar{g}_{T})$ defined in Eq. (17) and (20) provides the lower bound we want, but restricted to algorithms with bounded iterates. To handle unbounded iterates, we follow Carmon et al. and compose the construction with a soft projection to a ball centered at the origin. Our final (unscaled) construction is

The corresponding stochastic gradient estimator is

where J(x)=\big{[}\frac{\partial\rho_{i}(x)}{\partial{}x_{j}}\big{]}_{i,j} is the Jacobian of $\rho$. The next lemma shows that this new construction is difficult for any algorithm in $\mathcal{A}_{\textnormal{{rand}}}$. The lemma has two components: First, since the iterates always satisfy $\left\|\rho(x^{(t,k)})\right\|\leq{}R$, we can apply Lemma 5 to this sequence to control progress. Second, the additional regularization term in (27) ensures that we cannot make the gradient small by increasing the norm, so low progress indeed implies large gradient.

Let $\mathsf{O}$ be any oracle with $\mathsf{O}_{\widehat{F}_{T,U}}(x,z)=(\widehat{F}_{T,U}(x),\widehat{g}_{T,U}(x,z))$, where $\widehat{F}_{T,U}$ is the compressed and rotated hard instance (27) and $\widehat{g}_{T,U}$ is the corresponding probability-$p$ zero chain (28). Let $\delta\in(0,1)$, $d\geq{}\lceil 18\cdot 230^{2}\frac{KT^{2}}{p}\log\frac{2KT^{2}}{p\delta}\rceil$, and $U$ be uniformly distributed on $\mathsf{Ortho}(d,T)$. Then for any $\mathsf{A}\in\mathcal{A}_{\textnormal{{rand}}}(K)$, with probability at least $1-\delta$,

All that remains is to verify that the final constructions (27) and (28) still satisfy the various boundedness properties required for the lower bound. The following bounds are a consequence of a generic result about rotation and soft projection, which we prove in Appendix B.3.

The function $\widehat{F}_{T,U}$ and stochastic gradient function $\widehat{g}_{T,U}$ satisfy the following properties for all $U\in\mathsf{Ortho}(d,T)$.

$\widehat{F}_{T,U}(0)-\inf_{x}\widehat{F}_{T,U}(x)\leq\Delta_{0}T$, where $\Delta_{0}=12$.

Extensions

While Theorem 3 constitutes our main technical result, implying lower bounds for methods using stochastic first-order information, it is interesting to extend the bounds to allow more sophisticated querying strategies and more informative oracles.

We prove Lemma 8 in Appendix C. With the lemma in hand, all that is required to prove the $\Omega(\tfrac{\Delta{}L\sigma^{2}}{\epsilon^{4}})$ lower bound for the bounded variance setting and the $\Omega(\tfrac{\Delta{}L\sigma}{\epsilon^{3}}+\frac{\sigma^{2}}{\epsilon^{2}})$ lower bound for the mean-squared smooth setting is to compose the instance with a rotation and soft projection as in (27), then rescale as in Theorem 3. This leads to the following result.

Theorem 3 holds (with different numerical constants) even when restricting the oracle class to statistical learning-type stochastic gradient functions of the form (30).

2 Active oracles

Our main results consider a model in which the algorithm performs batches of $K$ simultaneous queries, but the random seed $z$ is drawn i.i.d. once per batch. Another stronger model allows active oracles, where the queries consist of both a point $x$ and a seed $z$ . Active oracles are essential to finite-sum optimization problems where $F(x)=\sum_{i=1}^{n}f_{i}(x)$ and are more general than our $K$-query oracles, since a randomized algorithm can simulate a $K$-query oracle using an active oracle by drawing $z\sim P_{z}$ and querying $(x^{(1)},z),\ldots,(x^{(K)},z)$. For convex finite-sum minimization problems, stochastic oracles are significantly weaker than active oracles . Nevertheless, in this section we show that our $\epsilon^{-4}$ lower bound for zero-respecting algorithms (Theorem 1) extends to active oracles, even with additional finite-sum structure ($\mathcal{Z}$ is finite, $P_{z}$ is uniform). We believe further extensions for randomized algorithms, mean-squared smooth gradient estimators and statistical learning oracles are straightforward, but we omit them for brevity.

The precise active oracle model we consider is as follows: at round $i$, the algorithm proposes a point $x^{(i)}$ and seed $z^{(i)}$ and receives an oracle response $(F(x^{(i)}),g(x^{(i)},z^{(i)}))=\mathsf{O}_{F}(x^{(i)},z^{(i)})$. As before, we assume that the stochastic gradients are unbiased and have variance bounded by $\sigma^{2}$, and we allow the algorithm to know the distribution $P_{z}$.

To obtain the hard active oracle construction, we take

Let $\delta\in(0,1)$, let $N,T>1$ be integers, let $\pi$ be a random permutation of $N^{T}$ elements and consider the active oracle $\mathsf{O}_{F_{T}}^{\pi}(x,i)=(F_{T}(x),g_{\pi}(x;i))$. Let $\{x^{(i)}\}$ be the iterates of any zero-respecting algorithm interacting with $\mathsf{O}_{F_{T}}^{\pi}$. Then, for $p=1/N$, with probability at least $1-\delta$ over the random choice of $\pi$,

Using the same scaling arguments as in the proof of Theorem 1, Lemma 9 implies an analogous lower bound for the active setting. However, the distributional complexity we now lower bound is slightly different, because we randomize over the choice of oracles instead of choosing a fixed oracle. Consequently, we let the supremum in Eq. (7) be over all distributions $P_{\mathsf{O}}$ on $\mathcal{O}(K,\sigma^{2})$, and take the expectation also with respect to a draw of $\mathsf{O}\sim P_{\mathsf{O}}$. (For zero-respecting lower bounds, we still replace $\mathcal{A}_{\textnormal{{rand}}}(K)$ with $\mathcal{A}_{\textnormal{{zr}}}(K)$ and it still suffices to consider point masses for $P_{F}$).

Theorem 1 also holds in the active oracle model, with the above complexity measure, finite $\mathcal{Z}$, and uniform $P_{z}$.

This lower bound has the following implication on minimax complexity: For every zero-respecting algorithm there exists a “hard” active oracle (corresponding to some permutation of the coordinates) for a scaled version of $F_{T}$ such that finding an $\epsilon$-stationary point requires at least $\Omega(\epsilon^{-4})$ iterations. Using the techniques of Section 4 we can lift these results to finite sum active oracle lower bounds for randomized algorithms. Moreover, the “different bit per coordinate” approach extends straightforwardly the mean-square smooth construction (20) as well as the “statistical learning” construction (31).

The set $\mathcal{Z}$ in the lower bounds described above is very large—since $N$ scales as ${\sigma^{2}}/{\epsilon^{2}}$ and $T$ is polynomial in $1/\epsilon$, the cardinality $|\mathcal{Z}|=N^{T}$ is super-exponential in $1/\epsilon$. Designing lower bound constructions with smaller cardinality $|\mathcal{Z}|=n$ remains an open problem. We note that for the mean-square smooth setting, the smallest possible value for $n$ is $\Omega(\sigma^{2}/\epsilon^{2})$, since for $n=o(\sigma^{2}/\epsilon^{2})$ the upper bound $O(\sqrt{n}\bar{L}\Delta\epsilon^{-2})$ attained by SPIDER will be smaller than the desired $n$-independent lower bound $\Omega(\bar{L}\Delta\sigma\epsilon^{-3})$. We also remark that Fang et al. prove a lower bound of $\Omega(\sqrt{n}\bar{L}\Delta\epsilon^{-2})$ for active oracles, but their construction does not keep the variance $\sigma^{2}$ bounded.

Discussion

We have established tight lower bounds on the stochastic first-order complexity of finding stationary points for non-convex functions, with and without mean-squared smoothness. We hope that the basic ideas behind our lower bound constructions will find further use in non-convex stochastic optimization. A few natural open questions and future directions along these lines are as follows.

In the mean-squared smooth setting, all known algorithms that achieve the optimal $O(\epsilon^{-3})$ oracle complexity (SPIDER , SNVRG ) require $K=2$ simultaneous queries. With $K=1$, the best result known for the mean-squared smooth setting is still the standard $O(\Delta{}L\sigma^{2}\epsilon^{-4})$ rate obtained by SGD. However, under additional higher-order smoothness assumptions, perturbed SGD can achieve convergence $O(\epsilon^{-3.5})$ with $K=1$ . It remains an open question whether any algorithm can achieve complexity scaling as $\epsilon^{-3}$ when $K=1$, or whether the $\epsilon^{-4}$ rate of SGD is optimal.

Rather than assuming a mean-squared smooth oracle, one can make the stronger assumption that the stochastic gradient function $g(\cdot,z)$ is smooth almost surely, or assume that the error $\left\|g(x,z)-\nabla{}F(x)\right\|$ is bounded by $\sigma$ almost surely. We are not aware of any algorithms that leverage such stronger assumptions, and yet extending our lower bounds to handle them seems non-trivial. Resolving the importance of these assumptions therefore remains an interesting topic for future work.

Our results resolve the complexity of finding first-order stationary points with stochastic first-order methods, but we have not addressed the oracle complexity of other basic non-convex stochastic optimization problems, such as finding first-order stationary points with higher-order smoothness (possibly with stochastic access to Hessian, Hessian vector-products, or other higher-order derivatives) or finding second-order stationary points. While our techniques extend to higher order derivatives and smoothness, obtaining tight lower bounds requires a dedicated treatment and may pose new challenges.

Acknowledgements

Part of this work was completed while the authors were visiting the Simons Institute for the Foundations of Deep Learning program. We thank Ayush Sekhari, Ohad Shamir, Aaron Sidford and Karthik Sridharan for several helpful discussions. YC was supported by the Stanford Graduate Fellowship. JCD acknowledges support from NSF CAREER award 1553086, the Sloan Foundation, and ONR-YIP N00014-19-1-2288. DF was supported by NSF TRIPODS award #1740751. BW was supported by the Google PhD Fellowship program.

References

Appendix

The functions $\Psi$ and $\Phi$ in (16) and their derivatives satisfy

where $(i)$ is a direct calculation using the definition (15) of $F_{T}$ and $(ii)$ follows from (35). ∎

The second result is an $\Omega(\frac{\sigma^{2}}{\epsilon^{2}})$ lower bound on the sample complexity of finding stationary points whenever $\epsilon\leq{}O(\sqrt{\Delta{}L})$. This result handles an edge case in the proof of Theorem 2. A similar lower bound appeared in Foster et al. , but the result we prove here is slightly stronger because it holds even for dimension $d=1$.

There exists a number $c_{0}>0$ such that for any number of simultaneous queries $K$, dimension $d$ and $\epsilon\leq{}\sqrt{\frac{\bar{L}\Delta}{8}}$, we have

Whenever $\epsilon\leq{}\sqrt{\frac{\bar{L}\Delta}{8}}$, the number of samples required to obtain an $\epsilon$-stationary point in the global stochastic model defined above is $\Omega(1)\cdot\frac{\sigma^{2}}{\epsilon^{2}}$.

The proof follows standard arguments used to derive information-theoretic lower bounds for statistical estimation .

Now, we provide a distribution over the underlying instance by drawing $S$ uniformly from $\left\{\pm{}1\right\}$, and consider any algorithm that takes as input samples $z_{1},\ldots,z_{T}\sim P_{z}^{S}$, and returns iterate $\hat{x}$. To bound the expected norm of the gradient at $\hat{x}$ (over the randomness of the oracle, the randomness of the algorithm, and the choice of the underlying instance $S$), we define $\hat{S}\coloneqq\operatorname*{arg\,min}_{s^{\prime}\in\{1,-1\}}\|\nabla F_{s^{\prime}}(\hat{x})\|$, with ties broken arbitrarily. Observe that we have

where (i) follows by Markov’s inequality and (ii) follows because when $\hat{S}\neq{}S$, the definition of $\hat{S}$ implies

Finally, setting $r=\min\{\frac{\sigma}{2\bar{L}\sqrt{T}},\sqrt{\frac{2\Delta}{\bar{L}}}\}$, implies

A.2 Proof of Lemma 4

On the other hand, Lemma 2.4 gives us that

where the final transition used Lemma 2.3 and $\Theta_{i}^{2}(x)\leq 1$ for all $x$ and $i$, establishing the variance bound in (22) with $\varsigma=23$.

By Observation 1.3, $\Gamma_{i}$ is 6-Lipschitz. Since the Euclidean norm $\|\cdot\|$ is 1-Lipschitz, we have

That is, $\Theta_{i}$ is $6^{2}$-Lipschitz. Since $\Theta_{i}^{2}(y)\leq 1$ and $(\nabla_{i}F_{T}(x))^{2}\leq 23^{2}$ by Lemma 2.3, we have

for all $i$. Substituting back into (39) we obtain

A.3 Proof of Theorem 2

for all $t\leq{}{(T-1)}/{2p}$ and $k\in[K]$. It remains to choose $p$ and $L$ such that $\mathsf{O}_{F^{\star}_{T}}$ belongs to $\mathcal{O}(K,\sigma^{2},\bar{L})$. As in the proof of Theorem 1, setting $p=\min\left\{{(2\varsigma\epsilon)^{2}}/{\sigma^{2}},1\right\}$ and using Lemma 4 guarantees a variance bound of $\sigma^{2}$. Moreover, by Lemma 4 we have

guarantees membership in the oracle class and implies the lower bound

Appendix B Proofs from Section 4

where $r$ is the algorithm’s random seed. Further, recall that $x^{(i)}$ is a batch of $K$ queries,

For each $i$ and each $k\in\left[K\right]$, define

and let $g^{(i)}=(g^{(i,1)},\ldots,g^{(i,K)})$. To keep notation compact for the $K$-query setup, we adopt the following conventions throughout the proof:

Ug^{(i)}\coloneqq{}\big{[}Ug^{(i,1)},\ldots,Ug^{(i,K)}\big{]},

U^{\top}x^{(i)}\coloneqq{}\big{[}U^{\top}x^{(i,1)},\ldots,U^{\top}x^{(i,K)}\big{]}.

Following the strategy of Lemma 1, we define

The statement of the lemma is equivalent to

Note that by definition $\cap_{i=1}^{t}\mathfrak{V}^{(t)}$ implies that $\pi^{(t)}\leq\gamma^{(t-1)}\leq\gamma^{(t)}$, and therefore

We bound each of the terms above in turn. With an argument similar to the proof of Lemma 1 we show that

With an argument similar to the proof of Lemma 4 of , we show that

so that $\pi^{(t)},\gamma^{(t)}\in\mathcal{G}^{(t)}$. The definition of the probability-$p$ zero chain property is that

Therefore, denoting $\iota^{(t)}\coloneqq\gamma^{(t)}-\gamma^{(t-1)}$, we have via the Chernoff method

The following is a linear-algebraic fact.

For every $i\leq t$ and $j\leq T$, $\cap_{i^{\prime}\leq i}\mathfrak{G}_{j}^{(i^{\prime})}$ implies that

Consider the operator $\operatorname{\Pi}_{j-1}^{(i)}=I-\operatorname{P}_{j-1}^{(i)}$ and observe that $\operatorname{\Pi}_{j-1}^{(i)}\operatorname{\Pi}_{j-1}^{(i-1)}=\operatorname{\Pi}_{j-1}^{(i-1)}\operatorname{\Pi}_{j-1}^{(i)}=\operatorname{\Pi}_{j-1}^{(i-1)}$ by the nesting of the subspaces. Therefore

where the second equality uses that $\operatorname{\Pi}^{(0)}_{j-1}=\sum_{j^{\prime}=1}^{j-1}[u^{(j^{\prime})}][u^{(j^{\prime})}]^{\top}$ since $U$ is orthogonal.

Now, let $k\in\left[K\right]$ be fixed. Using the facts that $\operatorname{\Pi}_{j-1}^{(i)}x^{(i,k)}=x^{(i,k)}$ and $\langle u^{(j^{\prime})},u^{(j)}\rangle=0$ for any $j^{\prime}<j$, we may write

where the transitions above follow from $(i)$ Eq. (45), $(ii)$ the fact that $\left[\operatorname{\Pi}^{(i^{\prime})}_{j-1}\right]^{2}=\operatorname{\Pi}^{(i^{\prime})}_{j-1}$ and $(iii)$ Cauchy-Schwartz. Now, $\cap_{i^{\prime}\leq i}\mathfrak{G}_{j}^{(i^{\prime})}$ implies that

Moreover, the decomposition (45) implies that $\sum_{i^{\prime}=1}^{i}\operatorname{P}_{j-1}^{(i^{\prime}-1)}\operatorname{\Pi}^{(i^{\prime})}_{j-1}\operatorname{P}_{j-1}^{(i^{\prime}-1)}\preceq\operatorname{\Pi}_{j-1}^{(i)}\preceq I$. Therefore,

Substituting (47) and (48) into (46) gives the lemma. ∎

Lemma 12 has the following immediate consequence: for all $i\leq t$,

Furthermore, since $\gamma^{(1)}\leq\gamma^{(2)}\leq\cdots\gamma^{(t)}$,

Therefore, we may bound the failure probability of $\cap_{i\leq t}\mathfrak{V}^{(i)}$ as

where $z^{(i)}$ is the randomness of the oracle at iteration $i$. Fixing $i\leq t$, $j\leq T$, we also define

In other words, $x^{(1)},x^{(2)},\ldots,x^{(i)}$ are deterministic conditional on $\mathcal{U}_{j-1}^{(i-1)}$ and $\mathfrak{T}_{j}^{(i-1)}$.

The above discussion implies also that $\operatorname{\Pi}_{j-1}^{(i)}$ and $\operatorname{P}_{j-1}^{(i-1)}$ are deterministic conditional on $\mathcal{U}_{j-1}^{(i-1)}$ and $\mathfrak{T}_{j}^{(i-1)}$. In contrast, we have the following characterization of $\hat{u}^{(j)}$.

Before proving Lemma 14, let us quickly show how it implies Lemma 13. Since $\hat{u}^{(j)}$ is conditionally uniformly distributed on a sphere in $\mathcal{S}^{\perp}$, and since the image $\operatorname{\Pi}_{j-1}^{i}\mathcal{S}^{\perp}$ has dimension at most $K$, we have

Throughout, for any sequence of vectors $v^{(1)},\ldots,v^{(N)}$, we adopt the notation $v^{(\geq n)}$ (respectively $v^{(<n)}$) for a matrix with columns $v^{(n)},v^{(n+1)},\ldots,v^{(N)}$ (respectively $v^{(1)},\ldots,v^{(n-1)})$. We define a number of densities as follows:

$p_{\geq j}$ denotes the density of $u^{(\geq j)}$ conditional on $\mathcal{U}_{j-1}^{(i-1)}$ and $\mathfrak{T}_{j}^{(i-1)}$.

(Pedantically, densities are with respect to the product of Lebesgue and counting measure.) With these definitions, we have

Fix $r,z^{(<i)}$ and $U$ such that $\mathfrak{T}_{j}^{(i-1)}$ holds and let $W$ be any orthogonal transformation preserving $\mathcal{S}$, i.e., a $d$ by $d$ matrix satisfying

Let ${x^{\prime}}^{(1)},\ldots,{x^{\prime}}^{(i-1)}$ denote the iterates produced by the algorithm when we replace $U$ with $U^{\prime}=WU$ (with $z^{(<i)}$ and $r$ unchanged). We argue inductively that

The equality (52) means that the transformation $U\mapsto WU$ leaves $\mathcal{U}_{j-1}^{(i-1)}$ unchanged and in particular that $\mathfrak{T}_{j}^{(i-1)}$ still holds. Thus,

by the orthogonal invariance of the distribution of $U$. Substituting $Wu^{(\geq j)}$ into equation (50) for $p_{\geq j}(\cdot\mid\mathcal{U}_{j-1}^{(i-1)},\mathfrak{T}_{j}^{(i-1)})$ gives

where we have used the facts that $\left[u^{(<j)},Wu^{(\geq j)}\right]=WU$ by definition of $W$, and that the quantity $U^{\top}x^{(<i)}$ appearing in (50) is $\mathcal{U}_{j-1}^{(i-1)}$-measurable and therefore independent of the argument to $p_{\geq j}(\cdot\mid\mathcal{U}_{j-1}^{(i-1)},\mathfrak{T}_{j}^{(i-1)})$. Applying the equalities (53) and (54) to the numerator of (55) and comparing to (50), we find that

B.2 Proof of Lemma 6

Before proving Lemma 6 we first list the relevant continuity properties of the compression function

For the second term, we again use that $\left\|\rho(x)\right\|\leq{}R$ to write

as long as $i\leq{}(T-\log(2/\delta))/2p$.

Using that $J(x)=\frac{I-\rho(x)\rho(x)^{\top}/R^{2}}{\sqrt{1+\left\|x\right\|^{2}/R^{2}}}$, this is equal to

Since $\left\|y^{(i,k)}\right\|\leq{}\left\|x^{(i,k)}\right\|\leq{}R/2$, this implies

Next, we handle the case where $\left\|x^{(i,k)}\right\|>R/2$. Here, we have

B.3 Proof of Lemma 7

To establish Lemma 7 we first prove a generic result showing that composition with the compression function $\rho$ and an orthogonal transformation $U$ never significantly hurts the regularity requirements in our lower bounds. In the following, we use the notation $a\vee b\coloneqq\max\{a,b\}$.

$\widehat{F}_{U}(0)-\inf_{x}\widehat{F}_{U}(x)\leq F(0)-\inf_{x}F(x)$.

For the variance bound (property 3), observe that we have

Lastly, to prove property 4 we first invoke the triangle inequality and the elementary inequality $(a+b)^{2}\leq{}2a^{2}+2b^{2}$.

For the first term, we use the Jacobian operator norm bound from (56) and the assumed mean-squared smoothness of $g$:

For the second term, we use the Jacobian Lipschitzness from (56):

We now use the assumed Lipschitzness of $F$ and variance bound for $g$:

For property 1, observe that $\widehat{F}_{T,U}(0)=F_{T}(0)$, and

For properties 2, 3, and 4 we observe from Lemma 16 that $\widehat{F}_{T,U}$ and $\widehat{g}_{T,U}$, ignoring the quadratic regularization term, satisfy the same smoothness, variance, and mean-squared smoothness bounds as in Lemma 2/Lemma 4/Lemma 8 up to constant factors. The additional regularization term in (27) leads to an additional $\eta=1/5$ factor in the smoothness and mean-squared-smoothness. ∎

B.4 Proof of Theorem 3

Given accuracy parameter $\epsilon$, initial suboptimality $\Delta$, smoothness parameter $L$ and variance parameter $\sigma^{2}$, we define for each $U\in\mathsf{Ortho}(d,T)$ a scaled instance

Therefore, setting $p=\min\left\{{(4\varsigma\epsilon)^{2}}/{\sigma^{2}},1\right\}$ guarantees a variance bound of $\sigma^{2}$.

Next, Let $\mathsf{O}$ be an oracle for which $\mathsf{O}_{F^{\star}_{T,U}}(x,z)=(F^{\star}_{T,U}(x),g^{\star}_{T,U}(x,z))$ for all $U\in\mathsf{Ortho}(d,T)$. Observe that for any $\mathsf{A}\in\mathcal{A}_{\textnormal{{rand}}}(K)$, we may regard the sequence \big{\{}x^{(i,k)}_{\mathsf{A}[\mathsf{O}_{F^{\star}_{T,U}}]}/\lambda\big{\}} as queries an algorithm $\mathsf{A}^{\prime}\in\mathcal{A}_{\textnormal{{rand}}}(K)$ interacting with the unscaled oracle $\mathsf{O}_{\widehat{F}_{T,U}}(x,z)=(\widehat{F}_{T,U}(x),\widehat{g}_{T,U}(x,z))$. Instantiating Lemma 6 for $\delta=\frac{1}{2}$, we have that w.p. at least $\frac{1}{2}$, \min_{k\in\left[K\right]}\big{\|}\nabla\widehat{F}_{T,U}\big{(}\frac{1}{\lambda}x^{(t,k)}_{\mathsf{A}[\mathsf{O}_{F^{\star}_{T,U}}]}\big{)}\big{\|}>\frac{1}{2} for all $t\leq{}\frac{T-2}{2p}$. Therefore,

where the second inequality uses that $\lfloor x\rfloor-2\geq{}x/4$ whenever $x\geq{}4$.

We use the scaling (60), choose $p=\min\left\{{(4\varsigma\epsilon)^{2}}/{\sigma^{2}},1\right\}$ as above, and let

Using Lemma 7 and the calculation from the proof of Theorem 2, this setting guarantees that $\mathsf{O}_{F^{\star}_{T,U}}(x,z)$ is in the class $\mathcal{O}(K,\sigma^{2},\bar{L})$. Consequently, the inequality (61) implies the lower bound

Appendix C Proofs from Section 5

For all $i\geq{}j$, $\nabla_{i}\Theta_{j}(x)$ is well-defined with

Moreover, $\Theta_{j}$ satisfies the following properties:

$\left\|\nabla{}\Theta_{j}(x)\right\|\leq{}6^{2}$.

$\left\|\nabla\Theta_{j}(x)-\nabla\Theta_{j}(y)\right\|\leq{}10^{4}\cdot\left\|x-y\right\|$.

First, we verify that the function $x_{i}\mapsto{}\left\|\Gamma(\left\lvert x_{\geq{}j}\right\rvert)\right\|$ is differentiable everywhere for each $i$. From here it follows from Observation 1 that $\Theta_{j}(x)$ is differentiable, and (64) follows from the chain rule. Let $i\geq{}j$, and let $a=\sqrt{\sum_{k\geq{}j,k\neq{}i}\Gamma^{2}(\left\lvert x_{k}\right\rvert)}$. Then $\left\|\Gamma(\left\lvert x_{\geq{}j}\right\rvert)\right\|=\sqrt{a^{2}+\Gamma^{2}\left(\left\lvert x_{i}\right\rvert\right)}$. This function is clearly differentiable with respect to $x_{i}$ when $a>0$, and when $a=0$ it is equal to $\Gamma(\left\lvert x_{i}\right\rvert)$, which is also differentiable.

To proceed, we state some useful facts, all of which follow from Observation 1.3:

$\Gamma^{\prime}$ is 128-Lipschitz, and in particular $\Gamma^{\prime}(1-\left\|\Gamma(\left\lvert x\right\rvert)\right\|)\leq{}128\cdot\left\|\Gamma(\left\lvert x\right\rvert)\right\|$ (since $\Gamma^{\prime}(1)=0$).

$\left\|\mu(x)\right\|\leq{}6\cdot\left\|\Gamma(\left\lvert x\right\rvert)\right\|$ for all $x$.

$\left\|\mu(x)-\mu(y)\right\|\leq{}(128\cdot 1+6^{2})\cdot\left\|x-y\right\|=164\cdot\left\|x-y\right\|$ for all $x,y$.

Using the first, second, and third facts, we bound the first term as

For the second term, we apply the second fact and the triangle inequality to upper bound by

Using the fourth fact and the assumption that $\left\|\Gamma(\left\lvert x\right\rvert)\right\|\leq{}\left\|\Gamma(\left\lvert y\right\rvert)\right\|$, we have

Using the third fact and $\left\|\Gamma(\left\lvert x\right\rvert)\right\|\leq{}\left\|\Gamma(\left\lvert y\right\rvert)\right\|$, we have

Gathering all of the constants, this establishes that

We are now ready to prove Lemma 8. For ease of reference, we restate the construction (31):

To begin, we introduce some shorthand. Define

The gradient of the noiseless hard function $F_{T}$ can then be written as

With these definitions, we have the expression

To bound the variance and mean-squared smoothness of $\nabla f_{T}$, we begin by analyzing the sparsity pattern of the error vector

As in Lemma 4, we have $\nu_{i}(x,z)=1$ for all $i<i_{x}$ and $g_{i}(x,z)=\nabla{}_{i}F_{T}(x)=0$ for all $i>i_{x}$. Thus, using the expression (66) along with (68), we have

It follows immediately that the variance can be bounded as

From (65) we have $\left\|\nabla{}\Theta_{i_{x}}(x)\right\|\leq{}6^{2}$, and from (35) we have $|H(x,y)|\leq{}12$, so the first term contributes at most $\tfrac{2\cdot{}144\cdot{}6^{4}}{p}$. Since $|\Theta_{i}(x)|\leq{}1$, Lemma 2 implies that the second and third term together contribute at most $\tfrac{4\cdot{}23^{2}}{p}$. To conclude, we may take

We bound $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ using similar arguments to Lemma 4. Focusing on $\mathcal{E}_{1}$, and letting $i\in\left\{i_{x},i_{y}\right\}$ be fixed, we have

Note that by Lemma 17, (i) $\Theta_{i}$ is $6^{2}$ Lipschitz and $\Theta_{i}\leq{}1$ and (ii) $h_{1}$ is $23$-Lipschitz and $\left\lvert h_{1}\right\rvert\leq{}5$ (from Observation 2 and Lemma 2). Consequently,

Since $h_{2}$ is $23$-Lipschitz and has $\left\lvert h_{2}\right\rvert\leq{}20$, an identical argument also yields that

To bound $\mathcal{E}_{3}$, we use the earlier observation that for all $i$ and $j\neq i_{x}$ we have $H(x_{j-1},x_{j})\nabla_{i}\Theta_{j}(x)=0$, and likewise that $H(y_{j-1},y_{j})\nabla_{i}\Theta_{j}(y)=0$ for all $j\neq{}i_{y}$. This allows us to write

Letting $j\in\left\{i_{x},i_{y}\right\}$ be fixed, we upper bound the inner summation as

We may now upper bound this quantity by applying the following basic results:

$\left\lvert H(x_{j-1},x_{j})-H(y_{j-1},y_{j})\right\rvert\leq{}20\left\|x-y\right\|$, by (35).

$\left\|\nabla\Theta_{j}(y)\right\|\leq{}6^{2}$ by Lemma 17.1.

$\left\|\nabla\Theta_{j}(x)-\nabla\Theta_{j}(y)\right\|\leq{}10^{4}\cdot\left\|x-y\right\|$, by Lemma 17.2.

It follows that $\mathcal{E}_{3}\leq{}3\cdot{}10^{10}\cdot{}\left\|x-y\right\|^{2}$. Collecting the bounds on $\mathcal{E}_{1}$, $\mathcal{E}_{2}$, and $\mathcal{E}_{3}$, this establishes that

C.2 Active oracles

Given the bound (73), the remainder of the proof is identical to that of Lemma 1, with $2p$ replacing $p$. To see why (73) holds, let $(x^{(1)},i^{(1)}),\ldots,(x^{(t)},i^{(t)})\in\mathcal{G}^{(t-1)}$ denote the sequence of queries made by the algorithm. We first observe that, by the construction of $g_{\pi}$, we have $\gamma^{(t)}=1+\gamma^{(t-1)}$ only if $\zeta_{1+\gamma^{(t-1)}}(\pi(i^{(t)}))=1$. Therefore,

Next, let $b\in\{0,1\}^{N^{T}}$ denote a (random) vector whose $i$th entry is $b_{i}\coloneqq\zeta_{1+\gamma^{(t-1)}}(\pi(i))$. The vector $b$ has $N^{T-1}$ elements equal to 1 and its distribution is permutation invariant. Note that, by construction, the vector $b$ is independent of $\{\zeta_{j}(\pi(i))\}_{j\neq 1+\gamma^{(t-1)},i\in N^{T}}$. Consequently, the gradient estimates $g^{(1)},\ldots,g^{(t-1)}$ depend on $b$ only through their $(1+\gamma^{(t-1)})$th coordinate, which for iterate $t^{\prime}\leq t-1$ is