Lower Bounds for Finding Stationary Points II: First-Order Methods

Introduction

In Part I of this series , we establish the complexity of finding an $\epsilon$-stationary point (1) for algorithms that, at a query point $x$, have access to all derivatives of $f$. In contrast, in this paper we focus on first-order methods, which only query function values and gradients.

First-order methods are important in large-scale optimization for many reasons. Perhaps the two most salient are that each iteration is often inexpensive, and that on many problems, the number of iterations grows slowly (or not at all) with the problem dimension $d$. From a theoretical perspective, the latter property is captured by dimension-free convergence rates, where the worst case iteration count depends polynomially on the desired accuracy and measures of function regularity but has no explicit dependence on $d$. In non-convex optimization problems, regularity often comes by assuming bounded function value at the initial point $x^{(0)}$, i.e. $f(x^{(0)})-\inf_{x}f(x)\leq\Delta$ for some $\Delta>0$, and that ${\nabla}f$ is $L_{1}$-Lipschitz continuous. Under these conditions, classical gradient descent finds an $\epsilon$-stationary point in $2L_{1}\Delta\epsilon^{-2}$ iterations , a dimension-free guarantee.

Developing first-order methods for finding stationary points of non-convex functions with improved dimension-free rates of convergence is an area of active research . Under the additional assumption of Lipschitz second derivatives, we and Agarwal et al. propose randomized first-order methods with nearly dimension free rate $\epsilon^{-7/4}\log\frac{d}{\epsilon}$ (ignoring other problem-dependant constants). In a later paper , we propose a deterministic accelerated gradient-based method with complexity $\epsilon^{-7/4}\log\frac{1}{\epsilon}$, and under the further assumption of that $f$ has Lipschitz third derivatives, we show the same method attains rates of $\epsilon^{-5/3}\log\frac{1}{\epsilon}$. This raises the main question we address in this paper: how much further can this $\epsilon$ dependence can be improved, and what Lipschitz continuity assumptions are necessary?

In Table 1 we summarize our results, along with corresponding known upper bounds. We establish lower bounds on the worst-case oracle complexity of finding $\epsilon$-stationary points, where algorithms may access $f$ only through queries to an information oracle, that returns the value and some number of (or potentially all) derivatives of $f$ at the queried point. A lower bound $T_{\epsilon}$ means that for every algorithm $\mathsf{A}$, there exists a function $f$ in the allowed function class (e.g. functions with $f(x^{(0)})-\inf_{x}f(x)\leq\Delta$ and $L_{1}$-Lipschitz gradient) for which $\mathsf{A}$ requires at least $T_{\epsilon}$ oracle queries before returning an $\epsilon$-stationary point of $f$.

In Part I of this series we prove that no algorithm, even one given all derivatives of $f$ at each iteration, can improve on the $\epsilon^{-2}$ rate of gradient descent for the class of functions with bounded initial value and Lipschitz continuous gradient. Therefore, in distinction with the convex case, acceleration of gradient descent for non-convex optimization fundamentally depends on higher-order smoothness assumptions. We further show that, for the class of functions with $p$th order Lipschitz derivatives, no method can improve the rate $\epsilon^{-(p+1)/p}$ achieved by a $p$th-order method . However, this does not get at the crux of the issue we consider here—what is the best possible rate for first-order methods, given that higher-order derivatives are Lipschitz?

$\displaystyle\frac{3}{2}$ cubic-regularized Newton’s method $p=2$ $\displaystyle\frac{8}{5}$ first-order methods $p\geq 3$ $\displaystyle\frac{5}{3}$$\displaystyle\frac{12}{7}$ first-order methods $p=2$ $\displaystyle\frac{7}{4}$$\displaystyle 2$ gradient descent $p=1$ Thus, we establish two separations. First, no deterministic first-order method can achieve the rate of convergence $\epsilon^{-3/2}$ of Newton’s method. Second, the rate $\epsilon^{-5/3}\log\frac{1}{\epsilon}$ we achieve requires the assumption of Lipschitz third derivatives, as first-order methods assuming only Lipschitz Hessian must compute at least $\epsilon^{-12/7}$ function values and gradients to find an $\epsilon$-stationary point. We also show that the optimal rate for finding $\epsilon$-stationary points of convex functions with bounded initial value (i.e. $f(x^{(0)})-\inf_{x}f(x)\leq\Delta$) and $L_{1}$-Lipschitz gradient is $\widetilde{\Theta}(\sqrt{L_{1}\Delta}\epsilon^{-1})$. Given a bound $\|{x^{(0)}-x^{\star}}\|\leq D$ where $x^{\star}\in\mathop{\rm arg\hskip 1.00006ptmin}f$, as is standard for convex optimization, the optimal rate is $\widetilde{\Theta}(\sqrt{L_{1}D}\epsilon^{-1/2})$ . The two rates are not directly comparable. Finding stationary points is thus fundamentally easier for convex functions.

The starting point of our development is Nesterov’s [18, § 2.1.2] “worst function in the world,”

Throughout, we use Pi.$k$ to reference an item $k$ of Part I of this sequence , as we build off of many ideas there. In Section 2 we briefly summarize our framework (Sections Pi.LABEL:sec:prelims and Pi.LABEL:sec:anatomy). Section 3 begins the new analysis and contains lower bounds for finding stationary points of convex functions. In Section 4 we construct our hard non-convex instance, while in Section 5 we use this function to establish our main result: a lower bound on the complexity of finding stationary points using deterministic first-order methods. In Sections 6 we discuss some difficulties in sharpening or extending our lower bounds. Section 7 concludes by situating our work in the current literature and reflecting on its implications for future research.

Notation

A framework for lower bounds

For ease of reference, this section provides a condensed version of Sections Pi.LABEL:sec:prelims and Pi.LABEL:sec:anatomy of the first part of this series that lays out the notation, concepts and strategy we use to prove lower bounds. Here, we are deliberately brief; see for motivation, intuition and background for our definitions, as well as exposition of randomized and higher-order methods.

where $f_{x,v}^{(p)}(\cdot)$ is the $p$th derivative of $t\mapsto f_{x,v}(t)$. We occasionally refer to a function with Lipschitz $p$th order derivatives as $p$th-order smooth.

Let $p\geq 1$, $\Delta>0$ and $L_{p}>0$. Then the set

We also require the following important invariance notion [17, Ch. 7.2].

Every function class we consider is orthogonally invariant.

2 Algorithm classes

3 Complexity measures

We define the complexity of algorithm class $\mathcal{A}$ on function class $\mathcal{F}$ as

Table 1 provides upper and lower bounds on the quantity (4) for different choices of $\mathcal{A}$ and $\mathcal{F}$. For example, gradient descent guarantees \mathcal{T}_{\epsilon}\big{(}\mathcal{A}^{(1)}_{\textnormal{{det}}}\cap\mathcal{A}^{(1)}_{\textnormal{{zr}}},\mathcal{F}_{1}(\Delta,L_{1})\big{)}\leq 2\Delta L_{1}\epsilon^{-2}.

4 How to show a lower bound

The last step in our preliminaries is to give an overview of our proof strategy; this is an abbreviated version of Section Pi.LABEL:sec:anatomy. There, we abstract classical techniques for lower bounds in convex optimization , presenting a generic method for proving lower bounds on deterministic methods (of any order) applied to functions in any orthogonally invariant class.

Our starting point is what we call a zero-chain, which distills the “chain-like” structure of Nesterov’s construction (2).

In Definition Pi.LABEL:def:zero-chain , we extend zero-chains to higher orders; in our terminology Nesterov’s function (2) is a first-order zero-chain, but not a second-order zero-chain. A first-order zero-chain limits the rate that zero-respecting algorithms acquire information from derivatives, forcing them to “discover” coordinates one by one, as the following observation makes clear.

The important insight, essentially due to Nemirovski and Yudin is that by using a resisting oracle that can adversarially rotate the function $f$, any lower bound for zero-respecting algorithms implies an identical bound for all deterministic algorithms:

Let $\mathcal{F}$ be an orthogonally invariant function class. Then

See Proposition Pi.LABEL:prop:prelims-det-zr for a more general version of this result.

This strategy highlights the importance of “dimension freedom,” because we take the dimension of $f_{\epsilon}$ to be at least $T$, which must thus grow inversely with $\epsilon$.

Lower bounds for finding stationary points of convex functions

While for convex optimization guarantees of small gradients are atypical topics of study, we nonetheless begin by considering the complexity of finding stationary points of smooth convex functions. This serves two purposes. First, it is a baseline for finding stationary points in the non-convex setting; based on algorithmic upper bounds due to Nesterov , we see that convexity makes this task fundamentally easier. Second, our lower bound construction for convex problems underpins our construction and analysis for general smooth (non-convex) functions in the sequel, allowing us to demonstrate our techniques in a simpler setting. Of course, in convex optimization, it is typically more useful to find points $x$ with small optimality gap, $f(x)\leq\inf_{z}f(z)+\epsilon$. Convexity allows efficient algorithms for guaranteeing such optimality, and typically one ignores questions of the magnitude of the gradient in favor of small optimality or duality gaps . Nonetheless, in some situations—such as certifying (near) dual feasibility or small constraint residuals in primal-dual or operator splitting algorithms [e.g. 7]—achieving small gradients is important.

We proceed as follows. In Section 3.1 we define the class of convex functions under consideration and a quadratic subclass. In Section 3.2, we construct a hard quadratic instance, and verify its key properties. Finally, in Section 3.3, we state, discuss and prove our lower bounds.

The collections of functions we consider are the following.

is the set of convex quadratic functions satisfying the above conditions.

Our results, following Nemirovski and Yudin and Nesterov , demonstrate that for deterministic first-order methods, the class $\mathcal{Q}\left(\Delta,L_{1}\right)$ is “hard enough,” in that it provides nearly sharp lower bounds for first-order methods, which immediately apply to $\mathcal{K}_{1}\left(\Delta,L_{1}\right)$ and $\mathcal{F}_{1}(\Delta,L_{1})$. We also have $\mathcal{Q}\left(\Delta,L_{1}\right)=\mathcal{F}_{1:p}(\Delta,L_{1},0,\ldots,0)$ or any $p\geq 2$.

In addition to functions restricted by initial optimality gap, we consider the following initial distance-based definition.

is the set of convex quadratic functions satisfying the above conditions.

2 The worst function in the (convex) world

For $\alpha=1$, $\hat{f}_{T,1}$ this is Nesterov’s “worst function in the world” [18, § 2.1.2]. The parameter $\alpha$ allows us to control $f(0)$ and thus provides a degree of freedom in satisfying the constraint $f(0)-\inf_{x}f(x)\leq\Delta$ for our lower bounds. By inspection,

is the unnormalized graph Laplacian of the simple path on $T$ vertices (see ) plus the term $\alpha$ in the position $L_{11}$, and $b=\alpha e^{(1)}$.

Let us now verify that $\hat{f}_{T,\alpha}$ meets the three requirements of our lower bound strategy.

Zero-chain $\hat{f}_{T,\alpha}$ is a first-order zero-chain.

$\hat{f}_{T,\alpha}$ has $4$-Lipschitz continuous gradient.

The unique minimizer of $\hat{f}_{T,\alpha}(x)$ is $x^{\star}=\mathbf{1}$, and $\left\|{x^{\star}}\right\|=\sqrt{T}$.

Substituting $z$ and $b$ into Eq. (7), we have that $x_{T}=0$ implies

3 Scaling argument and final bound

With our hard instance in place, we provide our lower bounds for finding stationary points of convex functions. We note that the lower bound for the class $\mathcal{Q}^{\rm dist}\left(D,L_{1}\right)$ also follows from the standard lower bounds on finding $\epsilon$-suboptimal points, since for every $q\in\mathcal{Q}^{\rm dist}\left(D,L_{1}\right)$ an $\epsilon$-stationary point is also $\epsilon D$-suboptimal.

Let $\epsilon,\Delta,D$, and $L_{1}$ be positive. Then

Let us discuss Theorem 1 briefly. Nesterov shows that for any $f\in\mathcal{K}^{\rm dist}_{1}\left(D,L_{1}\right)$, accelerated gradient descent applied to a regularized version of $f$ yields a point $x$ satisfying $\left\|{\nabla f(x)}\right\|\leq\epsilon$ after at most $O(\sqrt{L_{1}D}\epsilon^{-1/2}\log\frac{L_{1}D}{\epsilon})$ iterations. For $f\in\mathcal{K}_{1}\left(\Delta,L_{1}\right)$, a similar technique to Nesterov’s, which we provide for completeness in Appendix A.1, yields an upper complexity bound of $O(\sqrt{L_{1}\Delta}\epsilon^{-1}\log\frac{L_{1}\Delta}{\epsilon^{2}})$. Thus, to within logarithmic factors both bounds of Theorem 1 are sharp. It is illustrative to compare Theorem 1 to our results for non-convex but smooth functions, and we do so in detail in Sec. 7.1. The comparison shows that finding stationary points of smooth convex functions with first-order methods is fundamentally easier than finding stationary points of non-convex functions, even with higher-order smoothness and using higher-order methods.

4 Proof of Theorem 1

To define the difficult zero-chain $f$, we scale $\hat{f}_{T,\alpha}$ using two scalar parameters $\lambda,\sigma>0$, which we determine later, defining

We use the parameter $\lambda>0$ to control the first-order smoothness of $f$, as $\nabla^{2}f(x)=\lambda\nabla^{2}\hat{f}_{T,\alpha}(x/\sigma)$, while the parameter $\sigma$ controls the lower bound on $\left\|{{\nabla}f(x)}\right\|$ for $x_{T}=0$. We first show how to choose $\sigma$, depending on $T$, $\epsilon$, $\alpha$, and $\lambda$. By Lemma 1.iii, for every $x$ with $x_{T}=0$ we have

guarantees $\|{{\nabla}f(x)}\|>\epsilon$ for any $x$ such that $x_{T}=0$ and hence $\|{{\nabla}f(x^{(t)})}\|>\epsilon$ for all $t\leq T$.

All that remains is to choose $\lambda,T$, and $\alpha$ to guarantee that $f$ belongs to the appropriate quadratic class. By Lemma 1.ii, $f$ has $4\lambda$ Lipschitz gradient, so we take

and guarantee that $f$ has $L_{1}$-Lipschitz gradient. To guarantee that $f\in\mathcal{Q}\left(\Delta,L_{1}\right)$, Lemma 1.ii yields

where we have substituted our choice of $\sigma$ and $\lambda$ in the final equality. Defining

so to guarantee $f(0)-\inf_{x}f(x)\leq\Delta$, it suffices to choose

This gives the first part (8a) of the theorem. For inequality (8b), we must have $f\in\mathcal{Q}^{\rm dist}\left(D,L_{1}\right)$. Let $x^{\star}=\sigma\mathbf{1}$ denote the minimizer of $f$, so that

where again we have substituted our choices of $\sigma$ and $\lambda$ in the final equality. Consequently, to guarantee $\left\|{x^{\star}}\right\|\leq D$ it suffices to take

Constructing the non-convex hard instance

We illustrate the construction $\bar{f}_{T,\mu,r}$ in Figure 1; it is the sum of the convex hard instance (5) (with $\alpha=\sqrt{\mu}$) and a separable non-convex function. In the following lemma, which we prove in Appendix B.1, we list the important properties of $\Upsilon_{r}$.

The function $\Upsilon_{r}$ satisfies the following.

We have $\Upsilon_{r}^{\prime}(0)=\Upsilon_{r}^{\prime}(1)=0$

For all $x\leq 1$, $\Upsilon_{r}^{\prime}(x)\leq 0$, and for all $x\geq 1$, $\Upsilon_{r}^{\prime}(x)\geq 0$.

For every $r\geq 1$, $\Upsilon_{r}^{\prime}(x)<-1$ for every $x\in(-\infty,-0.1]\cup[0.1,0.9]$

Before formally stating the properties of $\bar{f}_{T,\mu,r}$, we provide a high-level explanation of the choice of $\Upsilon_{r}$. First, a necessary and sufficient condition for $\bar{f}_{T,\mu,r}$ to be a first-order zero-chain is that $\Upsilon_{r}^{\prime}(0)=0$. Second, examining the proof Lemma 1.iii we see that the gradient of the quadratic chain is smallest for vectors $x$ with entries $x_{1},x_{2},...,x_{T}$ that slowly decrease from 1 to 0. We design $\Upsilon_{r}$ to “punish” such slowly varying vectors, by demanding that $\Upsilon_{r}^{\prime}(x)$ be large for any $x$ far from both 0 and 1 (Lemma 2.iv); this is the key to improving Lemma 1.iii and the most important property of $\Upsilon_{r}$. Third, for every finite $r$ all the derivatives of $\Upsilon_{r}$ are Lipschitz, and as $r$ increases $\bar{f}_{T,\mu,r}$ converges to a quartic polynomial; in the limit $r=\infty$ we have $\Upsilon_{\infty}(x)=30x^{4}-40x^{3}+10$. This allows us to establish that Lipschitz continuity of derivatives beyond the third does not alter the $\epsilon$ dependence of our bounds. However, we cannot simply use $\Upsilon_{\infty}$, as its first three derivatives are unbounded. Lastly, we place the minimum of $\Upsilon_{r}(x)$ at $x=1$, so that the all-ones vector is the global minimizer of $\bar{f}_{T,\mu,r}$, and $\bar{f}_{T,\mu,r}(\mathbf{1})=0$; this is simply convenient for our analysis.

With our considerations explained, we verify the three components of our general strategy: $f$ is a first-order zero-chain, belongs to the relevant function classes, and has large gradient whenever $x_{T}=0$. We begin with the zero-chain property, which follows trivially from Lemma 2.i.

Crucially, $\bar{f}_{T,\mu,r}$ is only a first-order zero-chain (see Definition Pi.LABEL:def:zero-chain); were it a second-order zero-chain, the resulting lower bounds would apply to second-order algorithms as well, where Newton’s method achieves the rate $\epsilon^{-3/2}$ , which is strictly better than all of our lower bounds. We next show that any point $x$ for which $x_{T}=x_{T+1}=0$ has large gradient. This is the core technical result of our analysis.

We defer the full proof of this lemma to Appendix B.2 and sketch its main idea here. We may view any vector meeting the conditions of the lemma as a sequence going from $x_{0}:=1$ to $x_{T}=0$. Every such sequence must have a “transition region”, which we define roughly as the subsequence starting after the last $i$ such that $x_{i}>\frac{9}{10}$ and ending at the first (subsequent) $j$ such that $x_{j}<\frac{1}{10}$ (see Figure 2). Letting $m\in\{1,\ldots,T\}$ denote the length of this subsequence and ignoring constant factors, we establish that

The $(m+1/\sqrt{\mu})^{-3/2}$ bound comes from the quadratic chain in $\bar{f}_{T,\mu,r}$, which has large gradient for any sequence $x$ with sharp transitions; this is essentially Lemma 1.iii with $T=m$ and $\alpha=\sqrt{\mu}$. The $\mu\sqrt{m}$ bound is due to the non-convex $\Upsilon_{r}$ terms in $\bar{f}_{T,\mu,r}$, which by Lemma 2.iv contribute a term of magnitude $\mu$ to every entry of ${\nabla}\bar{f}_{T,\mu,r}$ in the transition region. These two bounds intersect at $m\approx 1/\sqrt{\mu}$, so the gradient has norm at least $\mu^{3/4}$ for every value of $m$.

Finally, we list the boundedness properties of our construction.

The function $\bar{f}_{T,\mu,r}$ satisfies the following.

$\bar{f}_{T,\mu,r}(0)-\inf_{x}\bar{f}_{T,\mu,r}(x)\leq\frac{\sqrt{\mu}}{2}+10\mu T$

The first part of the lemma follows from Lemma 2, which shows that $\inf_{x}\bar{f}_{T,\mu,r}(x)=\bar{f}_{T,\mu,r}(\mathbf{1})=0$, while $\bar{f}_{T,\mu,r}(0)=\sqrt{\mu}/2+T\mu\Upsilon_{r}(0)\leq\sqrt{\mu}/2+10\mu T$. The second part of the lemma follows directly from Lemma 2.v and that the quadratic chain $f(x)=\frac{\sqrt{\mu}}{2}(x_{1}-1)^{2}+\frac{1}{2}\sum_{i}(x_{i}-x_{i+1})^{2}$ has 4-Lipschitz gradient and 0-Lipschitz higher order derivatives. ∎

Lower bounds for first-order methods

We now give our main result: lower bounds for the complexity of finding $\epsilon$-stationary using the class $\mathcal{A}^{(1)}_{\textnormal{{det}}}\cup\mathcal{A}^{(1)}_{\textnormal{{zr}}}$ of first-order deterministic and/or zero-respecting algorithms, applied to functions in the class

We begin by sketching the argument for $p=2$. In this case, we may take $r=1$, $\lambda\propto L_{1}$ and $\mu\propto L_{2}\sigma/\lambda$. This choice guarantees that $f$ has $L_{1}$-Lipschitz gradient and $L_{2}$-Lipschitz Hessian when $\mu\leq 1$, which we later verify using the assumption $\epsilon\leq L_{1}^{2}/L_{2}$. We then use Observation 2, Lemma 3 and Observation 1 to show that \mathsf{T}_{\epsilon}\big{(}\mathsf{A},f\big{)}\geq T+1 for every $\mathsf{A}\in\mathcal{A}^{(1)}_{\textnormal{{zr}}}$ whenever $\lambda\sigma\mu^{3/4}/4\geq\epsilon$, and conclude that $\sigma$ may scale as $\lambda^{1/7}\epsilon^{4/7}$ (since $\mu\propto L_{2}\sigma/\lambda$). By Lemma 4.i we have

so we can take $T\propto\Delta/(\lambda\mu\sigma^{2})\propto\Delta/(L_{2}\sigma^{3})$ to guarantee $f(0)-\inf_{x}f(x)\leq\Delta$, where we assume without loss of generality that $\lambda\sqrt{\mu}\sigma^{2}\leq\Delta$ (otherwise Theorem 1 dominates our bound). Substituting the expressions for $\sigma,\mu$ and $\lambda$ into the expression for $T$ gives the result for $p=2$.

For $p\geq 3$ we require a more careful argument, as we must simultaneously handle all orders of smoothness. To do so, we let $\mu=\bar{\mu}\sigma^{2}/\lambda$ and $r=\bar{r}/\sigma$, and show how to take $\bar{r}$ and $\bar{\mu}$ independently of $\epsilon$ (depending only on $L_{1},\ldots,L_{p}$). This allows us to obtain identical $\epsilon$-dependence for all $p\geq 3$.

To better understand the theorem, we give a few additional remarks.

In the paper , we propose the method “convex until proven guilty,” which augments Nesterov’s accelerated gradient method with implicit negative curvature descent. For the function classes $\mathcal{F}_{1:2}(\Delta,L_{1},L_{2})$ and $\mathcal{F}_{1:3}(\Delta,L_{1},L_{2},L_{3})$, it achieves rates of convergence $\widetilde{O}(\Delta L_{1}^{1/2}L_{2}^{1/4}\epsilon^{-7/4})$ and $\widetilde{O}(\Delta L_{1}^{1/2}L_{3}^{1/6}\epsilon^{-5/3})$, respectively. These results nearly match our lower bounds in Theorem 2; in the case of $p=2$, the gap (in terms of $\epsilon$) is of order $\epsilon^{-\frac{1}{28}}\log\frac{1}{\epsilon}$, while for $p\geq 3$, the gap is of order $\epsilon^{-\frac{1}{15}}\log\frac{1}{\epsilon}$. See further discussion in Sec. 7.1.

Choice of function class

The focus on the more restricted function classes $\mathcal{F}_{1:p}(\Delta,L_{1},...,L_{p})$—rather than the classes $\mathcal{F}_{p}(\Delta,L_{p})$ we study in Part I —makes our lower bounds stronger, and it is necessary for non-trivial results, since for any $p\geq 2$ and $\Delta,L_{p}>0$, the class $\mathcal{F}_{p}(\Delta,L_{p})$ contains functions impossible for first-order methods. Indeed, the class $\mathcal{Q}\left(\Delta,L_{1}\right)$ of $\Delta$-bounded $L_{1}$-smooth convex quadratics is a subset of $\mathcal{F}_{p}(\Delta,L_{p})$ for any $L_{1}<\infty$ and $L_{p}>0$. Therefore, by Theorem 1,

We thus limit our scope to functions with smooth lower order derivatives.

Conditions on the accuracy ϵbold-italic-ϵ\boldsymbol{\epsilon}

In Theorem 2 we require that $\epsilon^{q-1}\leq L_{1}^{q}/L_{q}$ for all $q\in\{2,\ldots,p\}$. For each $q$, we may rewrite this as $L_{q}^{1/q}\Delta\epsilon^{-(1+q)/q}\leq L_{1}\Delta\epsilon^{-2}$. In other words, these conditions ensure that $q$th order regularization-based methods have stronger convergence guarantees than gradient descent .

The case 𝒑=𝟏𝒑1\boldsymbol{p=1}

We state our bounds in Theorem 2 for $p\geq 2$. It is possible to use the construction (9) to prove a lower bound of $O(\Delta L_{1}\epsilon^{-2})$ on the time necessary for a deterministic first-order algorithm to find an $\epsilon$-stationary point for the class $\mathcal{F}_{1}(\Delta,L_{1})$. As Theorem Pi.LABEL:thm:fullder-final shows this lower bound holds for all randomized high-order algorithms, we do not pursue this.

The case 𝒑=𝟑𝒑3\boldsymbol{p=3}

We can slightly strengthen our lower bound in the case $p=3$, making it independent of $L_{2}$ for sufficiently small $\epsilon$. To achieve this we set $r=1$ in the definition of $\Upsilon_{r}$, take $\lambda\mu\propto L_{3}\sigma^{2}$, and argue that that the resulting construction has $O(\sigma)$-Lipschitz continuous Hessian, and $\sigma$ tends to zero as $\epsilon\to 0$. For sufficiently small $\epsilon$, we can then replace the minimum over $q\in\{2,3\}$ in the first claim of Theorem 2 with $L_{1}^{2/5}L_{3}^{1/5}\epsilon^{-8/5}$.

1 Lower bounds based on distance to optimality

For convex optimization problems, typical convergence guarantees depend on the distance of the initial point to the globally optimal set $\mathop{\rm arg\hskip 1.00006ptmin}_{x}f(x)$; the dependence on this distance may be polynomial for general convex optimization problems , while for smooth and strongly convex problems, the convergence guarantees depend only logarithmically on it. In the non-convex case, we can provide lower bounds that depend on the distance rather than the gap $\Delta:=f(x^{(0)})-\inf_{x}f(x)$. To that end, we consider the class

functions with $L_{q}$-Lipschitz $q$th derivatives (for each $q\in[p]$) and all global minima $x^{\star}$ satisfying $\left\|{x^{\star}}\right\|\leq D$. We obtain the bound, analogously to our results in Section Pi.LABEL:sec:fullder-distance, by “hiding” a sharp global minimum near the origin.

To state the theorem, we require an additional piece of notation. Let $B_{\epsilon}(\Delta,L_{1},\ldots,L_{p})$ be the lower bound Theorem 2 provides on \mathcal{T}_{\epsilon}\big{(}\mathcal{A}_{\textnormal{{det}}}\cup\mathcal{A}^{(1)}_{\textnormal{{zr}}},\mathcal{F}_{1:p}(\Delta,L_{1},...,L_{p})\big{)}, so

where we take $B_{\epsilon}=1$ if $\epsilon>0$ is larger than the settings Theorem 2 requires. Then by a reduction from our lower bounds on the complexity of $\mathcal{F}_{1:p}(\Delta,L_{1},...,L_{p})$, we obtain the following result.

We prove Theorem 3 in Appendix B.3. Theorem 3 shows that the lower bounds of Theorem 2 apply almost identically (to constant factors), except that we replace the function gap $\Delta$ in the lower bound with the quantity $\min_{q\in[p]}L_{q}D^{q+1}$. As the dependence of the lower bound on $\epsilon$ does not change, distance-based assumptions seem unlikely to help in the design of efficient optimization algorithms for non-convex functions.

2 Proof of Theorem 2

We must choose these parameters to guarantee the membership

For the bounded values constraint $f(0)-\inf_{x}f(x)\leq\Delta$, by Lemma 4.i it suffices to take

Thus, so long as we choose the constants $\mu,\sigma,\lambda,r$ to satisfy inequality (12), the preceding choice of $T$ guarantees $f\in\mathcal{F}_{1:p}(\Delta,L_{1},...,L_{p})$.

With this membership guaranteed, we consider the choices for $\lambda,\mu$, and $\sigma$ such that after $T$ iterations of a zero respecting first-order method, we have $\|{\nabla f(x)}\|\geq\epsilon$. Indeed, Observations 2 and 1 imply that if $x^{(1)}=0,x^{(2)},\ldots$ are the sequence of iterates produced by applying any zero-respecting (first-order) method to $f$, then $x^{(t)}_{T}=x^{(t)}_{T+1}=0$ for all $t\leq T$. Lemma 3 implies that $\|{{\nabla}\bar{f}_{T,\mu,r}\left(x^{(t)}/\sigma\right)}\|>\mu^{3/4}/4$ for any such iterate. Therefore, if we choose $\lambda>0,\mu\leq 1$, and $\sigma>0$ such that

then $\|{{\nabla}f\left(x^{(t)}\right)}\|=\lambda\sigma\|{{\nabla}\bar{f}_{T}(x^{(t)}/\sigma)}\|>\lambda\mu^{3/4}\sigma/4\geq\epsilon$ for all $t\leq T$. We thus obtain the guarantee

The same bound for the class $\mathcal{A}^{(1)}_{\textnormal{{det}}}$ then follows from Proposition 1. Our strategy is now the obvious one: we select $\lambda>0,0<\mu\leq 1,r\geq 1$, and $\sigma>0$ to satisfy the function membership constraints (12) and the large gradient guarantee (14). Substituting our choices into the boud (15) will then yield the lower bound in the theorem. We begin with the general case $p\geq 2$ and later provide a tighter construction for $p=2$.

To simplify the derivation, we define, for any $q\in[p]$

We choose $\bar{r}$ and $\bar{\mu}$ to guarantee that $f$ is appropriately smooth; in the sequel, we will choose $\sigma$ and $\lambda$ so that the gradient bound condition (14) holds. In this sense, we may choose $\bar{r}$ and $\bar{\mu}$ without consideration of $\epsilon$. Taking $\bar{r}=({\bar{L}_{1}/\bar{\mu}})^{1/2}$ guarantees the inequality (18) holds for $q=1$. Substituting this choice into the identical inequality for $q\in\{2,\ldots,p\}$ shows that we must have $\bar{\mu}^{(q-1)/2}\leq\bar{L}_{q}\bar{L}_{1}^{(q-3)/2}$ for each such $q$. Thus, the choice

satisfies inequality (18), and consequently, the smoothness condition (12) as well. We may therefore write $\bar{\mu}$ and $\bar{r}$ as

It remains to choose $\lambda,\sigma$, depending on $\epsilon$, to guarantee our gradient lower bound condition (14) holds, i.e. $4\epsilon\leq\lambda\mu^{3/4}\sigma=\lambda^{1/4}\bar{\mu}^{3/4}\sigma^{5/2}$. We thus set

We can now substitute back into our definitions $r=\bar{r}/\sigma$ and $\mu=\bar{\mu}\sigma^{2}/\lambda$ in Eq. (17) and verify that $r\geq 1$ and $\mu\leq 1.$ For $r$, we have

We now consider two cases; $\lambda\sqrt{\mu}\sigma^{2}\leq\Delta$ and $\lambda\sqrt{\mu}\sigma^{2}>\Delta$. In the first case (which holds for sufficiently small $\epsilon$), we substitute our choices of $\sigma,\lambda$ and $\mu$ into the time lower bound (15),

which is the desired bound, where in step $(i)$ we made use of $\lambda\sqrt{\mu}\sigma^{2}\leq\Delta$. When $\lambda\sqrt{\mu}\sigma^{2}>\Delta$, we show that the above bound is in fact smaller than the convex lower bound in Theorem 1. Indeed, substituting in our choices of $\lambda,\mu$ and $\sigma$, we see that $\lambda\sqrt{\mu}\sigma^{2}>\Delta$ implies

Taking a square root and substituting to our lower bound gives

completing the proof in the general case.

Functions with Lipschitz Hessian

For $p=2$, we keep the definitions (16) but replace the particular rescaling choices (17) with

Using $\mu\leq 1$, the above parameter setting satisfies inequality (12); $f$ has $L_{q}$-Lipschitz $q$th-order derivatives for $q=1,2$. To satisfy the gradient lower bound (14), i.e. $4\epsilon\leq\lambda\mu^{3/4}\sigma=\bar{L}_{1}^{1/4}\bar{L}_{2}^{3/4}\sigma^{7/4}$, we set

We can substitute into the definition $\mu=\frac{\bar{L}_{2}\sigma}{\lambda}$ to verify that $\mu\leq 1$:

If $\lambda\sqrt{\mu}\sigma^{2}\leq\Delta$ does not hold, we have

Taking a square root and substituting to our lower bound gives

due to Theorem 1, establishing the case $p=2$.

The challenge of strengthening Theorem 2

The lower bounds in Theorem 2 leave two avenues for improvement. The first is tightening our $\epsilon^{-12/7}$ and $\epsilon^{-8/5}$ lower bounds to match the known upper bounds of $\epsilon^{-7/4}$ and $\epsilon^{-5/3}$, for $p=2$ and $p=3$, respectively. The second improvement is to extend our lower bounds to randomized algorithms, as we did for the case of full derivative information in Section Pi.LABEL:sec:fullder-random. We discuss each of these in turn.

The core of our first-order lower bounds is Lemma 3, which establishes a lower bound of the form $\|{\bar{f}_{T,\mu,r}(x)}\|>\mu^{3/4}/4$ for vectors $x$ such that $x_{T}=x_{T+1}=0$ (i.e. any point that a first-order zero-respecting method can produce after $T$ iterations), where $\bar{f}_{T,\mu,r}$ is our unscaled hard instance (see definition (9)). Here we consider a slightly more general form,

The next lemma, whose proof we provide in Appendix B.4, shows such gradient norm upper bound for constructions of the form (19).

Summarizing, tightening our lower bounds seems to require a construction that is not of the form (19). This does not eliminate more general (non-convex) interactions, e.g. of the form $\Lambda(x_{i},x_{i+1})$ rather than $\Lambda(x_{i+1}-x_{i})$. The proof technique of Lemma 3 should provide useful “sanity checks” when considering alternative constructions.

2 A bound for randomized algorithms

In Section Pi.LABEL:sec:fullder-random we extend our lower bound for \mathsf{T}_{\epsilon}\big{(}\mathcal{A}_{\textnormal{{det}}}\cup\mathcal{A}_{\textnormal{{zr}}},\mathcal{F}_{p}(\Delta,L_{p})\big{)} to the broader class of randomized algorithms $\mathcal{A}_{\textnormal{{rand}}}$ with access to all derivatives at query point $x$. We do this by making our hard function insensitive: the individual “linking” terms $\Psi(x_{i})\Phi(x_{i+1})$ are identically zero for $x_{i}$ near 0. A natural question is whether the same methodology (originally proposed in ) can extend Theorem 2 to the class of randomized first-order algorithms, $\mathcal{A}^{(1)}_{\textnormal{{rand}}}$. Direct application of that technique cannot work in our case, for a simple reason: it applies to randomized algorithms of any order. In other words, if we modify our hard instance construction (9) to be a robust zero-chain (Definition Pi.LABEL:def:robust-zero-chain), any lower bounds it implies hold for all algorithms in $\mathcal{A}_{\textnormal{{rand}}}$, where $\epsilon^{-(p+1)/p}$ rates are achievable, so we could not provide sharper lower bounds than Theorem Pi.LABEL:thm:fullder-final.

Nevertheless, the ideas introduced in Section Pi.LABEL:sec:fullder-random might still be of use. Specifically, consider a modification of the construction (9) where $\Upsilon_{r}(x)$ is identically zero for sufficiently small $x$, say $|x|<0.05$, while still satisfying Lemma 2, thus making the non-convex component of $\bar{f}_{T,\mu,r}$ insensitive. As explained above, also making the convex quadratic component of $\bar{f}_{T,\mu,r}$ insensitive (as Woodworth and Srebro do) is unworkable in our setting, as it results in a robust zero-chain equally hard for all high-order algorithms. Instead, we may keep the quadratic component unchanged—and hence sensitive—and try to carry out the proof of Lemma Pi.LABEL:lem:fullder-rand-slow. Doing so, we see that the inductive argument allows us to ignore the insensitive non-convex component of $\bar{f}_{T,\mu,r}$, leaving us to contend only with the (randomly rotated) quadratic chain. Thus, the difficulty here appears closely related to proving a lower bound for randomized first-order methods applied for optimization of convex quadratics. Such lower bounds remain elusive, and we believe finding them is an important open problem.

Concluding remarks

Here we situate our work in the literature, discuss its implications, and provide a few possible extensions.

In conjunction with known upper bounds, our lower bounds characterize the optimal rates for finding stationary points. Our lower bounds are sharp to within constant factors for algorithms with full derivative information , and (perhaps) slightly loose for first-order algorithms. These characterizations yield a few insights.

For the class $\mathcal{F}_{1}(\Delta,L_{1})$ of $L_{1}$-smooth functions, first-order methods—specifically gradient descent—attain the optimal rate $L_{1}\Delta\epsilon^{-2}$; no higher-order randomized method can attain improved performance over the entire function class. The intuition here is that $\mathcal{F}_{1}(\Delta,L_{1})$ contains functions whose Hessian and higher order derivatives may vary arbitrarily sharply, and providing no useful information for optimization.

When higher-order derivatives are also Lipschitz continuous the picture changes fundamentally: there is a strict separation between (deterministic) second-order and first-order methods. In particular, cubic regularization of Newton’s method achieves $\epsilon$ dependence $\epsilon^{-3/2}$ for functions with Lipschitz Hessian, while no deterministic first-order method can have better time complexity than $\epsilon^{-8/5}$, regardless of how many derivatives are Lipschitz. Note that when the Hessian is Lipschitz, our definition of first-order algorithms allows for algorithms that rely on Hessian-vector products, as they can be estimated to arbitrary accuracy in two gradient evaluations.

The effect of high-order smoothness on first-order methods

For $\mathcal{F}_{1:2}(\Delta,L_{1},L_{2})$, the class of functions with Lipschitz gradient and Hessian, our lower bound scales as $\epsilon^{-12/7}$, while for the class $\mathcal{F}_{1:3}(\Delta,L_{1},L_{2},L_{3})$ of functions with Lipschitz third order derivative our “convex until proven guilty” method achieves the rate $\epsilon^{-5/3}\log\frac{1}{\epsilon}$. As $\frac{5}{3}<\frac{12}{7}$, this proves a separation between the optimal rate for first-order methods with second- and third-order smoothness.

In contrast, orders of smoothness beyond the third offer limited room for improvement in $\epsilon$ dependence; the lower bound $\epsilon^{-8/5}$ holds for all function classes $\mathcal{F}_{1:p}(\Delta,L_{1},...,L_{p})$ with $p\geq 3$, while the method does not enjoy improved guarantees with Lipschitz fourth-order derivatives. The “robustness” of the lower bound to higher-order smoothness stems from the fact that our hard instance $\bar{f}_{T,\mu,r}$ becomes a quartic polynomial in the limit $r\to\infty$, and we choose $r$ inversely proportional to $\epsilon$. As we discuss in [9, Lemma 4], our guarantee $\epsilon^{-5/3}\log\frac{1}{\epsilon}$ cannot improve using fourth-order smoothness because of symmetries in the fourth-order Taylor expansion. Quartic polynomials thus appear to play a central role in the complexity of first-order methods for smooth optimization.

Convex vs. non-convex functions

Our results show that convexity makes finding stationary points fundamentally—and significantly—easier. For first-order methods and functions with bounded initial sub-optimality, the rate $\epsilon^{-1}\log\frac{1}{\epsilon}$ is achievable for first-order smooth convex functions, while the lower bound $\epsilon^{-8/5}$ holds for non-convex functions with arbitrarily high-order smoothness. For methods using higher-order derivatives, our lower bounds for finding stationary points of non-convex functions are $\epsilon^{-(p+1)/p}\to\epsilon^{-1}$ as the order $p$ of smoothness grows. However, similar to Appendix A.1, the results can show that for convex functions with Lipschitz Hessian, a second-order method achieves the strictly better rate $\epsilon^{-6/7}\log\frac{1}{\epsilon}$.

Another striking difference between convex and non-convex functions is the effect of replacing the bound on the initial function value (i.e. $f(x^{(0)})-\inf_{x}f(x)\leq\Delta$) with a bound on the initial distance to the global minimizer $x^{\star}$ (i.e. $\left\|{x^{(0)}-x^{\star}}\right\|\leq D$). For non-convex function classes, we show lower bounds with the same $\epsilon$ dependence regardless of which type of bound is used. In contrast, for convex function the optimal rates scale as $\sqrt{\Delta}\epsilon^{-1}$ and $\sqrt{D}\epsilon^{-1/2}$, again a gap in $\epsilon$ dependence. The rates are not directly comparable; one can construct families of functions where $D$ grows with the dimension while $\Delta$ remains constant.

Returning to $\Delta$-value-bounded function classes, we see one more large difference between the convex and non-convex case; convex rates scale as $\sqrt{\Delta}$ while all the non-convex rates scale linearly with $\Delta$. This arises from fundamental differences in the convergence “mechanism” for convex and non-convex optimization. The analysis of non-convex optimization schemes typically revolves around a progress argument, where one shows that, as long as $\|{{\nabla}f(x^{(t)})}\|>\epsilon$, the guarantee $f(x^{(t+1)})\leq f(x^{(t)})-p_{\epsilon}$ holds for some quantity $p_{\epsilon}$ (e.g. for gradient descent $p_{\epsilon}=\epsilon^{2}/(2L_{1})$). The number of iterations to find an $\epsilon$-stationary point $x_{s}$ is therefore at most $[f(x^{(0)})-f(x_{s})]/p_{\epsilon}\leq\Delta/p_{\epsilon}$, which scales linearly in $\Delta$. By our lower bounds, such progress arguments are, in a sense, optimal. Conversely, in convex optimization we may control either the gap $f(x^{(t)})-f(x^{\star})$ or the distance $\left\|{x^{(t)}-x^{\star}}\right\|$, and this interplay (see Appendix A.1) allows stronger arguments than those based purely on function progress.

2 Further research

There exists a gap in polynomial $\epsilon$ dependence between our lower bounds (Theorem 2) and the best known upper bounds for first-order methods with higher-order smoothness. We do not believe the upper bounds of are improvable by different analysis or by any algorithmic change that maintains the general structure of alternating between accelerated gradient descent and negative curvature exploitation. In conjunction with our arguments in Section 6.1 about the structure of our lower bounds, resolution of the optimal rate will likely provide either a method with a substantially different approach to accelerating gradient descent in the smooth non-convex setting or a new lower bound construction.

Finite sum and stochastic problems

Smooth, non-convex, finite-sum and stochastic optimization problems are important, arising (for example) in the training of neural networks. This motivates the design and analysis of efficient methods for finding stationary points in such problems, and researchers have successfully developed variance reduction and acceleration techniques for these settings . However, no corresponding lower bounds are available. Woodworth and Srebro , show how to establish lower bounds for convex finite sum problems. Combined with the developments in our paper, we believe their techniques should extend to finding stationary points of non-convex problems. An important conclusion of is that randomized selection of the component function is crucial to efficient convergence: in contrast to our results, they show a separation between deterministic and randomized finite sum complexity.

Second-order stationary points

Approximate stationary points are not always close to local minima, and so it is interesting to consider stronger convergence guarantees. Second-order stationarity (also known as the second-order necessary condition for local optimality) is the most popular example; for a function $f$, a point $x$ is $(\epsilon_{1},\epsilon_{2})$-second-order stationary if $\left\|{{\nabla}f(x)}\right\|\leq\epsilon_{1}$ and $\nabla^{{2}}f(x)\succeq-\epsilon_{2}I$. Efficient first-order methods for finding second-order stationary points exist . Moreover, it is possible to generically transform methods for finding $\epsilon$-stationary points into methods that find $(\epsilon,O(\epsilon^{s}))$-second-order stationary points, for some $0<s<1$, without changing the $\epsilon$ dependence of the complexity [9, Appendix C], but such modifications introduce dependence logarithmic in the problem dimension $d$.

Clearly, lower bounds for finding $\epsilon_{1}$-stationary points also apply to finding $(\epsilon_{1},\epsilon_{2})$-second-order stationary points. However, attaining second-order stationarity with first-order methods is fundamentally more difficult than attaining only stationarity. There are no dimension-free guarantees: the results of Simchowitz et al. imply $\Omega(\log d)$ dimension dependence for all randomized first-order algorithms that escape saddle points. Moreover, for deterministic first-order algorithms it is easy to construct a resisting oracle that forces $\Omega(d)$ dimension dependence (consider $f(Rx)$ with $f(x)=-x_{1}^{2}$ and adversarially chosen rotation $R$), implying strong separation between deterministic and randomized first-order methods for finding second-order stationary points. It will be interesting to investigate such issues further.

Acknowledgments

OH was supported by the PACCAR INC fellowship. YC and JCD were partially supported by the SAIL-Toyota Center for AI Research, NSF-CAREER award 1553086, and a Sloan Foundation Fellowship in Mathematics. YC was partially supported by the Stanford Graduate Fellowship and the Numerical Technologies Fellowship.

References

Appendix A Additional results for convex functions

Here we give a first-order method that finds $\epsilon$-stationary points of a function $f\in\mathcal{K}_{1}\left(\Delta,L_{1}\right)$ in $O(\sqrt{L_{1}\Delta}\epsilon^{-1}\log\frac{L_{1}\Delta}{\epsilon^{2}})$ iterations. The method consists of Nesterov’s accelerated gradient descent (AGD) applied on the sum of $f$ and a standard quadratic regularizer.

Our starting point is AGD for strongly convex functions; a function $f$ is $\sigma$-strongly convex if

Moreover, for any such $f$ we have $\left\|{{\nabla}f(x)}\right\|^{2}\leq 2L_{1}(f(x)-f(x^{\star}_{f}))$ [6, Eq. (9.14)], and consequently

Using our complexity notation, we may rewrite this as

Now suppose that $f$ is convex with $L_{1}$-Lipschitz gradient but not necessarily strongly-convex. We can add strong convexity to $f$ by means of a proximal term; for any $\sigma>0$, the function

is $\sigma$-strongly-convex with $(L_{1}+\sigma)$-Lipschitz gradient. With this in mind, we define a proximal version of AGD as follows,

With a careful choice of $\sigma$, $\mathsf{PAGD}_{\sigma,L_{1}}$ achieves the desired upper bound.

Let $\Delta,L_{1}$ and $\epsilon$ be positive, and let $\sigma=\frac{\epsilon^{2}}{3\Delta}$. Then, algorithm $\mathsf{PAGD}_{\sigma,L_{1}}\in\mathcal{A}^{(1)}_{\textnormal{{det}}}$ satisfies

For any $f\in\mathcal{K}_{1}\left(\Delta,L_{1}\right)$, recall that $f_{\sigma}(x):=f(x)+\frac{\sigma}{2}\left\|{x}\right\|^{2}$ and let

be the sequence of iterates $\mathsf{PAGD}_{\sigma,L_{1}}$ produces on $f$. Then by guarantee (21), we have

For any point $y$ such that $f_{\sigma}(y)=f(y)+\frac{\sigma}{2}\left\|{y}\right\|^{2}\leq f_{\sigma}(0)=f(0)$, we have

Clearly, $f_{\sigma}(x_{f_{\sigma}}^{\star})\leq f_{\sigma}(0)$ and by guarantee (20) we also have $f_{\sigma}(x^{(T)})\leq f_{\sigma}(0)$. Consequently,

In inequality $(i)$ we substituted bounds (22) and (24), and in $(ii)$ we used $\sigma=\epsilon^{2}/(3\Delta)$. We conclude that \mathsf{T}_{\epsilon}\big{(}\mathsf{PAGD}_{\sigma,L_{1}},f\big{)}\leq T, and substituting (24) and the definition of $\sigma$ into (23) we have

Without loss of generality, we may assume $\frac{2L_{1}\Delta}{\epsilon^{2}}\geq 1$, as otherwise \mathsf{T}_{\epsilon}\big{(}\mathsf{PAGD}_{\sigma,L_{1}},f\big{)}=1. We thus simplify the expression slightly to obtain the proposition. ∎

A.2 The impossibility of approximate optimality without a bounded domain

We make the following inductive claim: if $f(x)\leq\inf_{y}f(y)+\epsilon=\epsilon$, then

for all $i\leq T$. Indeed, each term in the sum (25) defining $f$ is non-negative, so for the base case of the induction $i=1$, we have $\lambda(\sigma-\beta x_{1})^{2}\leq\epsilon$, or $\left|x_{1}-\sigma\beta^{-1}\right|\leq\beta^{-1}\sqrt{\epsilon/\lambda}$. For $i<T$, assuming that $x_{i}$ satisfies the bound (26), we have that $\lambda(x_{i}-\beta x_{i+1})^{2}\leq\epsilon$, which implies

which is the desired claim (26) for $x_{i+1}$.

The bound (26) implies $x_{i}\neq 0$ for all $i\leq T$ whenever $\sigma\geq(1-\beta)^{-1}\sqrt{\epsilon/\lambda}$. Therefore, we choose $\beta$ to satisfy $\sigma=(1-\beta)^{-1}\sqrt{\epsilon/\lambda}$, that is

for which $0<\beta<1$ since we assume $\epsilon<\Delta$. Thus, we guarantee that when $x_{T}=0$ we must have $f(x)>\inf_{y}f(y)+\epsilon$, giving the result. ∎

Appendix B Technical results

Parts i and ii are evident from inspection, as

To see the part iii, note that $\Upsilon_{r}$ is non-increasing for every $x<1$ and non-decreasing for every $x>1$ and therefore $x=1$ is its global minimum. That $\Upsilon_{r}(1)=0$ is immediate from its definition, and, for every $r$, $\Upsilon_{r}(0)=120\int_{0}^{1}\frac{t^{2}(1-t)}{1+(t/r)^{2}}dt\leq 120\int_{0}^{1}t^{2}(1-t)dt=10$. To see part iv, note that $|\Upsilon_{r}^{\prime}(x)|\geq|\Upsilon_{1}^{\prime}(x)|$ for every $r\geq 1$, and a calculation shows $|\Upsilon_{1}^{\prime}(x)|>1$ for $x\in\left({-\infty},{-0.1}\right]\cup[0.1,0.9]$ (see Figure 1).

To see the fifth part of the claim, note that

where the functions $\varphi_{1}$ and $\varphi_{2}$ are $\varphi_{1}(\xi)=\xi/(1+\xi^{2})$ and $\varphi_{2}(\xi)=1/(1+\xi^{2})$. We thus bound the derivatives of $\varphi_{1}$ and $\varphi_{2}$. We begin with $\varphi_{2}$, which we can write as the composition $\varphi_{2}(x)=(h\circ g)(x)$ where $h(x)=\frac{1}{x}$ and $g(x)=1+x^{2}$. Let $\mathcal{P}_{k,2}$ denote the collection of all partitions of $\{1,\ldots,k\}$ where each element of the partition has at most $2$ indices. That is, if $P\in\mathcal{P}_{k,2}$, then $P=(S_{1},\ldots,S_{l})$ for some $l\leq k$, the $S_{i}$ are disjoint, $1\leq|S_{i}|\leq 2$, and $\cup_{i}S_{i}=[k]$. The cardinality $|\mathcal{P}_{k,2}|$ is the number of matchings in the complete graph on $k$ vertices, or the $k$th telephone number, which has bound [12, Lemma 2]

We may then apply Faà di Bruno’s formula for the chain rule to obtain

where $\mathsf{C}_{i}(P)$ denotes the number of sets in $P$ with precisely $i$ elements. Of course, we have $|x|^{\mathsf{C}_{1}(P)}/(1+x^{2})^{|P|}\leq 1$, and thus

The proof of the upper bound on $\varphi_{1}^{(k)}(x)$ is similar ($2\varphi_{1}(x)=\frac{d}{dx}[(\hat{h}\circ g)(x)]$ with $\hat{h}(x)=\log x$ and $g$ as defined above), so for every $r\geq 1$ and $p\geq 1$, the $p+1$-th derivative of $\Upsilon_{r}$ has the bound

where $c<\infty$ is a numerical constant. ∎

B.2 Proof of Lemma 3

so that $x_{j}\leq 0.9$ for every $j>i$. Note that $i_{1}=0$ when $x_{i}\leq 0.9$ for every $i\in[T+1]$. This is a somewhat special case due to the coefficient $\sqrt{\mu}\leq 1$ of the first “link” in the quadratic chain term in (9). To handle it cleanly we define

Continuing with construction of the transition region, we make the following definition.

and let $m^{\prime}=i_{2}^{\prime}-i_{1}$, so $m^{\prime}\geq 1$. Roughly, our transition region consists of the $m^{\prime}$ indices $i_{1}+1,\ldots,i_{2}^{\prime}$, but for technical reasons we attach to it the following decreasing ‘tail’.

With these definitions, $i_{2}$ is well-defined and $0\leq i_{1}<i_{2}\leq T$, since $x_{T+1}-x_{T}=0$. We denote the transition region and associated length by

We illustrate our definition of the transition region in Figure 3.

Let us describe the transition region. In the “head” of the region, we have $0.1\leq x_{i}\leq 0.9$ for every $i\in\left\{i_{1}+1,\ldots,i_{2}^{\prime}-1\right\}$; a total of $m^{\prime}-1$ indices. The “tail” of the transition region is strictly decreasing, $x_{i_{2}}<x_{i_{2}-1}<\cdots<x_{i_{2}^{\prime}}$. Moreover, for any $j\in\{i_{2}^{\prime}+1,\ldots i_{2}-1\}$ such that $x_{j}>-0.1$, the decrease is rapid; $x_{j}<x_{j-1}-0.2/(m^{\prime}-1+1/\alpha)$. This descriptions leads us to the following technical properties.

$x_{i_{1}}>0.9>0.1>x_{i_{2}}$ and $-x_{i_{2}}+\left(m-1+\alpha^{-1}\right)\left(x_{i_{2}+1}-x_{i_{2}}\right)>-0.3$.

We defer the proof of the lemma to the end of this section, continuing the proof assuming it.

We now lower bound $\|{\nabla\bar{f}_{T,\mu,r}(x)}\|$. For notational convenience, define $g_{i}=\mu\Upsilon_{r}^{\prime}\left(x_{i}\right)$, and recalling that $x_{T}=x_{T+1}=0$, we see that the norm of the gradient of $\bar{f}_{T,\mu,r}$ is