Lower Bounds for Higher-Order Convex Optimization

Introduction

State-of-the-art optimization for machine learning has shifted from gradient based methods, namely stochastic gradient descent and its derivatives [DHS11, JZ13], to methods based on higher moments. Notably, the fastest theoretical running times for both convex [ABH16, XYRK+16, BBN16] and non-convex [AAZB+17, CDHS16] optimization are attained by algorithms that either explicitly or implicitly exploit second order information and third order smoothness.

Of particular interest is Newton’s method, due to recent efficient implementations that run in near-linear time in the input representation. The hope was that Newton’s method, and perhaps higher order methods, can achieve iteration complexity that is independent of the condition number of the problem as well as of the dimensionality, both of which are extremely high for many large-scale applications.

In this paper we explore the limitations of higher-order iterative optimization, and show that unfortunately, these hopes cannot be attained without stronger assumptions on the underlying optimization problem. To the best of our knowledge, our results are the first lower bound for $k^{th}$ order optimization for $k\geq 2$ that includes higher-order smoothness. After the writing of the first manuscript we were made aware of the work by Arjevani et al. [ASS17] which provides lower bounds for these settings as well.

For the $k^{th}$-order derivatives to be informative, one needs to bound their rate of change, or Lipschitz constant. This is called $k^{th}$-order smoothness, and we denote it by $L_{k+1}$. In particular we assume that

where $\|\nabla^{k}f\|$ is defined as the induced operator norm with respect to the Euclidean norm. Our main theorem shows the following limitation of $k^{th}$-order iterative optimization algorithms:

where $c_{k}$ is a constant depending on $k$ and $B_{d}$ is defined to be the unit ball in $d$ dimensions.

Note that although the bound is stated for constrained optimization over the unit ball, it can be extended to an unconstrained setting via the addition of an appropriate scaled multiple of $\|x\|^{2}$. We leave this adaptation for a full version of this paper. Further as is common with lower bounds the underlying dimension $d$ is assumed to be large enough and differs for the determinisitc vs randomized version. Theorems 4.1 and 5.1 make the dependence precise.

For the case of $k=2$, the most efficient methods known are the cubic regularization technique proposed by Nesterov [Nes08] and an accelerated hybrid proximal extragradient method proposed by Monteiro and Svaiter [MS13]. The best known upper bound in this setting is $O\left(\frac{L_{3}}{\varepsilon}\right)^{2/7}$[MS13]. We show a lower bound of $\Omega\left(\left(\frac{L_{3}}{\varepsilon}\right)^{2/11}\right)$ demonstrating that the upper bound is nearly tight.

For the case of case of $k>2$, Baes [Bae09] proves an upper bound of $O\left(\left(\frac{L_{k+1}}{\varepsilon_{k}}\right)^{\frac{1}{k+1}}\right)$. In comparison Theorem 1.1 proves a lower bound of $\Omega\left(\left(\frac{L_{k+1}}{\varepsilon}\right)^{2/(5k+1)}\right)$.

1 Related work

The literature on convex optimization is too vast to survey; the reader is referred to [BV04, Nes04].

Lower bounds for convex optimization were studied extensively in the seminal work of [NY78]. In particular, tight first-order optimization lower bounds were established assuming first-order smoothness.(Also see [Nes04] for a concise presentation of the lower bound). In a recent work [AS16] presented a lower bound when given access to second-order derivatives. However a key component (as remarked by the authors themselves) missing from the bound established by [AS16] was that the constructed function was not third-order smooth. Indeed the lower bound established by [AS16] can be overcome when the function is third-order smooth (ref. [Nes08]). The upper bounds for higher-order oracles (assuming appropriate smoothness) was established by [Bae09].

Higher order smoothness has been leveraged recently in the context of non-convex optimization [AAZB+17, CDHS16, AZ17]. In a surprising new discovery, [CHDS17] show that assuming higher-order smoothness the bounds for first-order optimization can be improved without having explicit access to higher-order oracles. This is a property observed in our lower bound too. Indeed as shown in the proof the higher order derivatives at the points queried by the algorithm are always 0. For further details regarding first-order lower bounds for various different settings we refer the reader to [AWBR09, WS16b, AS16, ASSS15] and the references therein.

In parallel and independently, Arjevani et al. [ASS17] also obtain lower bounds for deterministic higher-order optimization. In comparison, their lower bound is stronger in terms of the exponent than the ones proved in this paper, and matches the upper bound for $k=2$. However, our construction and proof are simple (based on the well known technique of smoothing) and our bounds hold for randomized algorithms as well, as opposed to the their deterministic lower bounds.

2 Overview of Techniques

Our lower bound is inspired by the lower bound presented in [CHW12a]. In particular we construct the function as a piecewise linear convex function defined by $f(x)=\max_{i}\{a_{i}^{T}x\}$ with carefully constructed vectors $a_{i}$ and restricting the domain to be the unit ball. The key idea here is that querying a point reveals information about at most one hyperplane. The optimal point however can be shown to require information about all the hyperplanes.

Unfortunately the above function is not differentiable. We now smooth the function by the ball smoothing operator (defined in Definition 2.2) which averages the function in a small Euclidean ball around a point. We show (c.f. Corollary 2.4) that iterative application of the smoothing operator ensures $k$-differentiability as well as boundedness of the $k^{th}$-order smoothness.

Two key issues arise due to above smoothing. Firstly although the smoothing operator leaves the function unchanged around regions far away from the intersection of the hyperplanes, it is not the case for points lying near the intersection. Indeed querying a point near the intersection of the hyperplanes can potentially lead to leak of information about multiple hyperplanes at once. To avoid this, we carefully shift the linear hyperplanes making them affine and then arguing that this shifting indeed forces sufficient gap between the points queried by the algorithm and the intersections leaving sufficient room for smoothing.

Secondly such a smoothing is well known to introduce a dependence on the dimension $d$ in the smoothness coefficients. Our key insight here is that for the class of functions being considered for the lower bound (c.f. Definition 2.1) smoothing can be achieved without a dependence on the dimension(c.f. Theorem 2.3). This is essential to achieving dimension free lower bounds and we believe this characterization can be of intrinsic interest.

3 Organization of the paper

We begin by providing requisite notations and definitions for the smoothing operator and proving the relevant lemmas regarding smoothing in Section 2. In Section 3 we provide the construction of our hard function. In Section 4 we state and prove our main theorem (Theorem 4.1) showing the lower bound against determinsitic algorithms. We also prove Theorem 1.1 based on Theorem 4.1 in this Section. In Section 5 we state and prove the Theorem 5.1 showing the lower bound against randomized algorithms.

Preliminaries

2 Smoothing

In this section we define the smoothing operator and the requisite properties.

$f_{\delta,\Gamma}$ is differentiable and also $G$-lipschitz and $\Gamma$-invariant.

$\nabla f_{\delta,\Gamma}$ is $\frac{rG}{\delta}$-Lipschitz.

$\forall\;x:|f_{\delta,\Gamma}(x)-f(x)|\leq\delta G$

As stated before $f$ being $\Gamma$-invariant implies that there exists a function $g$ such that $f(x)=g(\Gamma x)$. Therefore we have that

The first inequality follows from Jensen’s inequality and the second inequality follows from noticing that $f$ being $G$-Lipschitz implies that $g$ is $G$-Lipschitz. We now have that

$f$ being $G$-Lipschitz immediately gives us $\forall\;x:|f_{\delta,\Gamma}(x)-f(x)|\leq\delta G$ ∎

Given a $G$-Lipschitz continuous function $f$ and an $r$-dimensional subspace $\Gamma$ such that $f$ is $\Gamma$-invariant, we have that the function $S_{\delta,\Gamma}^{k}f$ is $k$-times differentiable $\forall\;k$. Moreover we have that for any $x,y$

We will argue inductively. The base case ($k=0$) is a direct consequence of the function $f$ being $G$-Lipschitz. Suppose the theorem holds for $k-1$. To argue about $\|\nabla^{k}S_{\delta,\Gamma}^{k}f(x)-\nabla^{k}S_{\delta,\Gamma}^{k}f(y)\|$ we will consider the function $q_{i,v}(x)=\nabla^{i}S_{\delta,\Gamma}^{k-1}f(x)[v^{\otimes i}]$ for $i\in[k]$ and for a unit vector $v$. We will first consider the case $i<k$. Using the inductive hypothesis and the fact that smoothing and derivative commute for differentiable functions we have that

Note that the inductive hypothesis implies that $q_{i,v}(x)$ is $\left(\frac{r}{\delta}\right)^{i}G$-Lipschitz and so is $S_{\delta,\Gamma}\;q_{i,v}(x)$ via Lemma 2.3. Therefore we have that

We now consider the case when $i=k$. By Lemma 2.3 we know that $S_{\delta,\Gamma}\;q_{i,v}(x)=\nabla^{i}S_{\delta,\Gamma}^{k}f(x)[v^{\otimes i}]$ is differentiable and therefore we have that $S_{\delta,\Gamma}^{k}f(x)$ is $k$ times differentiable. Further we have that

A direct application of Lemma 2.3 gives that

which implies using the fact that $f$ is $G$ Lipschitz that

Construction of the hard function

In this section we describe the construction of our hard function $f^{\dagger}$. Our construction is inspired by the information-theoretic hard instance of zero sum games of [CHW12b]. The construction of the function will be characterized by a sequence of vectors $X^{1\rightarrow r}=\{x_{1}\ldots x_{r}\}$, $x_{i}\in B_{d}$ and parameters $k,\gamma,\delta,m$. We assume $d>m\geq r$. To make the dependence explicit we denote the hard function as

Given a sequence of vectors $\{x_{1},x_{2},\ldots x_{r}\},x_{i}\in B_{d}$, let $X_{i}$ for $i\leq r$ be defined as the subspace spanned by the vectors $\{x_{1}\ldots x_{i}\}$. Further inductively define vectors $\{a_{1}\ldots a_{r}\}$ as follows.

If $x_{i}\perp X_{i-1}\neq 0$ (i.e. the perpendicular component of $x_{i}$ on the subspace $X_{i-1}$ is not zero), define

If indeed $x_{i}$ belongs to the subspace $X_{i}$, then $a_{i}$ is defined to be an arbitrary unit vector in the perpendicular subspace $X_{i-1}^{\perp}$. Further define an auxilliary function

Given the parameter $\gamma$, now define the following functions

With these definitions in place we can now define the hard function parameterized by $k,\delta$. Let $A$ be the subspace spanned by $\{a_{1}\ldots a_{r}\}$

$f^{\dagger}$ is convex and continuous. Moreover it is 1-Lipschitz and is invariant with the respect to the r dimensional subspace $A$.

$f^{\dagger}$ is $k$-differentiable with the Lipschitz constants $L_{i+1}\leq\left(\frac{r}{\delta}\right)^{i}$ for all $i\leq k$.

The following lemma provides a characterization of the derivatives of $f^{\dagger}$ at the points $x_{i}$.

Given a sequence of vectors $\{x_{1}\ldots x_{r}\}$ and parameters $\delta,\gamma,r,m$, let $\{g_{1}\ldots g_{r}\}$ be a sequence of functions defined as

We will first note the following about the smoothing operator $S^{k}_{\delta}$. At any point $x$ all the $k$ derivatives and the function value of $S^{k}_{\delta}f$ for any function $f$ depend only on the values of the function $f$ in a ball of radius atmost $k\delta$ around the point $x$. Consider the function $g_{r}$ and $g_{i}$ for any $i\in[r]$. Note that by definition of the functions $g_{i}$, for any $x$ such that

we have that $g_{i}(x)=g_{r}(x)$. Therefore to prove the lemma it is sufficient to show that

Lets first note the following facts. By construction we have that $\forall j>i,a_{j}^{T}x_{i}=0$. This immediately implies that

Further using the fact that $\|a_{j}\|\leq 1$, $\forall j\in[r]$ we have that

Further note that by construction $a_{i}^{T}x_{i}\geq 0$ which implies $a_{i}^{T}x+\left(1-\frac{j}{m}\right)\gamma\geq\left(1-\frac{i}{m}\right)\gamma$. Again using the fact that $\|a_{j}\|\leq 1$, $\forall j\in[r]$ we have that

The above equations in particular imply that as long as $2k\delta<\frac{\gamma}{m}$ , we have that

which as we argued before is sufficient to prove the lemma. ∎

Main Theorem and Proof

The main theorem (Theorem 4.1) follows immediately from the following main technical lemma by setting $\varepsilon=\frac{1}{2\sqrt{T}}$. For the randomized version the statement follows the same way from Theorem 5.1.

Moreover the function is guaranteed to be $k$-differentiable with Lipschitz constants $L_{i+1}$ bounded as

We first prove Theorem 1.1 in the deterministic case using Theorem 4.1.

Given an algorithm ALG and numbers ${\mathcal{L}}_{k+1},k$ define $\varepsilon_{0}({\mathcal{L}}_{k+1},k)\triangleq{\mathcal{L}}_{k+1}/(10k)^{k}$. For any $\varepsilon\leq\varepsilon_{0}$ pick a number $\mathcal{T}$ such that

Note that by the guarantee in Equation (4.1) we get that $h(x)$ is $k^{th}$-order smooth with coefficient at most ${\mathcal{L}}_{k+1}$. Note that since this is a scaling of the original hard function $f^{\dagger}$ the lower bound applies directly and therefore ALG cannot achieve accuracy

in less that $T=c_{k}\left(\frac{{\mathcal{L}}_{k+1}}{\varepsilon}\right)^{\frac{2}{5k+1}}$ iterations which finishes the proof of the theorem. ∎

Consider a deterministic algorithm $Alg$. Since $Alg$ is deterministic let the first point played by the algorithm be fixed to be $x_{1}$. We now define a series of functions $f^{\dagger}_{i}$ inductively for all $i=\{1,\ldots T\}$ as follows

The above definitions simulate the deterministic algorithm Alg with respect to changing functions $f^{\dagger}_{i}$. $Inp_{i}^{x}$ is the input the algorithm will receive if it queried point $x_{i}$ and the function was $f^{\dagger}_{i}$. $x_{i+1}$ is the next point the algorithm Alg will query on round $i+1$ given the inputs $\{Inp_{1}^{x}\ldots Inp_{i}^{x}\}$ over the previous rounds. Note that thus far these quantities are tools defined for analysis. Since Alg is deterministic these quantities are all deterministic and well defined. We will now prove that the function $f^{\dagger}_{T}$ defined in the series above satisfies the properties required by the Theorem 4.1. Bounded Lipschitz Constants Using Corollary 2.4 and the fact that $f^{\dagger}$ has Lipschitz constant bounded by 1 we get that the function $f^{\dagger}_{T}$ has higher order Lipschitz constants bounded above as

Let $\{y_{0}\ldots y_{T}\}$ be the points queried by the algorithm Alg when executed on $f^{\dagger}_{T}$. We need to show that

Equation 4.7 follows as a direct consequence of the following two claims.

We have that for all $i\in[1,T]$, $y_{i}=x_{i}$ where $x_{i}$ is defined by Equation 4.6.

To remind the reader $x_{i}$ were variables defined by Equation (4.6) and $y_{i}$ are the points played by the algorithm Alg when run on $f^{\dagger}_{T}$. Claim 4.2 shows that even though $f^{\dagger}_{T}$ was constructed using $x_{i}$ the outputs produced by the algorithm does not change.

Claim 4.2 and Claim 4.3 derive Equation 4.7 in a straightforward manner thus finishing the proof of Theorem 4.1.

We now provide the proofs of Claim 4.2 and Claim 4.3.

We will prove the claim inductively. The base case $x_{1}=y_{1}$ is immediate because Alg is deterministic and therefore the first point queried by it is always the same. Further note that $y_{i}$ for $i\geq 2$ is defined inductively as follows.

where $Inp_{i}^{x}$ is as defined in Equation (4.5). To see this note that

Equation (4.10) is a direct consequence of Lemma 3.3 by noting that $2k\delta_{T}\leq\gamma/T$ which is true by definition of these parameters. ∎

Using Lemma 3.3 we have that $f^{\dagger}_{i}(x_{i})=f^{\dagger}_{T}(x_{i})$. Further Equation (3.6) implies that

Now using (3.3) using we get that every point in $\{x_{1}\ldots x_{T}\}$ is such that

The above follows by the choice of parameters and $T$ being large enough. This finishes the proof of Claim 4.3. ∎

Lower Bounds against Randomized Algorithms

We provide a randomized construction for the function $f^{\dagger}$. The construction is the same as in Section 3 but we repeat it here for clarity. We sample a random $T$ dimensional basis $\{a_{1}\ldots a_{T}\}$. Let $A_{i}$ be the subspace spanned by $\{a_{1}\ldots a_{i}\}$ and $A_{i}^{\perp}$ be the perpendicular subspace. Further define an auxilliary function

Given a parameter $\gamma$, now define the following functions

The following key lemma will be the main component of the proof.

Let $\{x_{1}\ldots x_{T}\}$ be the points queried by a randomized algorithm throughout its execution on the function $f^{\dagger}$. With probability at least $1-\delta$ (over the randomess of the algorithm and the selection of $f^{\dagger}$) the following event $\mathcal{E}$ happens

Using the above lemma we first demonstrate the proof of Theorem 5.1. We will assume the event $\mathcal{E}$ in Lemma 5.2 happens.

Now using Equation (5.2) we get that every $x_{i}$ is such that

The last inequality follows by the choice of parameters. This finishes the proof of Theorem 5.1. ∎

We will use the following claims to prove the lemma. For any vector $x$, define the event $\mathcal{E}_{i}(x)=\big\{\forall j\geq i\;\;|a_{j}^{T}x|\leq\frac{1}{20T^{1.5}}\big\}$. The event we care about then is

$\forall x$ if $\mathcal{E}_{i}(x)$ holds, then $[f^{\dagger}(x),\nabla f^{\dagger}(x)\ldots\nabla^{k}f^{\dagger}(x)]$ all depend only on $\{a_{1}\ldots a_{i}\}$.

For any $i\in[T]$, if $\forall j<i$ if we have that $\mathcal{E}_{j}(x_{j})$ holds then we have that with probability at least $1-\frac{\delta}{T}$(over the choice of $a_{i}$ and the randomness of the algorithm) the event $\mathcal{E}_{i}(x_{i})$ happens.

Claim 5.3 is a robust version of the argument presented in the proof of Theorem 4.1. Claim 5.4 is a byproduct of the fact that in high dimensions the corelation between a fixed vector and a random small basis is small. Claim 5.3 is used to prove the Claim 5.4.

Lemma 5.2 now follows via a simple inductive argument using Claim 5.4 which is as follows

Lets first note the following facts. By the definition of $\mathcal{E}_{i}(x)$ we have that $\forall j>i,f_{j}(x)\leq\frac{1}{20T^{1.5}}$. This immediately implies that

The above equations imply that as long as $2k\delta_{T}+\frac{1}{10T^{1.5}}<\frac{\gamma}{T}$ (which is true by the choice of parameters), we have that

which is sufficient to prove Claim 5.3. ∎

Consider any $i\in[T]$. Given $\mathcal{E}_{j}(x_{j})$ is true for all $j<i$, applying Claim 5.3 for all $j<i$, implies that all the information that the algorithm possesses is only a function of $\{a_{1}\ldots a_{i-1}\}$ and the internal randomness of the algorithm. Further we can assume that the basis $\{a_{1}\ldots a_{T}\}$ is chosen by the inductive process which picks $a_{i}$ uniformly randomly from the subspace $A_{i-1}^{\perp}$.

Therefore we have that the choice of the remaining basis $\{a_{i}\ldots a_{T}\}$ is uniformly distributed in a subspace of dimension $d-i+1$ completely independent of any vector $x_{i}$ the algorithm might play. Since we wish to bound the absolute value of the inner product we can assume $\|x_{i}\|=1$ Otherwise the absolute value of the inner product is only lower.

The rest of the argument follows the argument by [WS16a](Proof of Lemma 7). Note that for $y_{1}$ this probability amounts to the surface area of a sphere above the caps of radius $\sqrt{1-(\frac{1}{20T^{1.5}})^{2}}$ relative to the surface area of the unit sphere. This surface area is smaller than the relative surface area of a sphere of radius $\sqrt{1-(\frac{1}{20T^{1.5}})^{2}}$. Formally this gives us

Applying the argument inductively we get that

The last line follows from the choice of $d=\Omega\left(T^{3}\log(\delta T^{2})\right)$. ∎

Acknowledgements

The authors would like to acknowledge and thank Ohad Shamir for providing insightful comments on the first draft of this manuscript and Brian Bullins and Gopi Sivakanth for helpful suggestions. The first author is supported in part by Elad Hazan’s NSF grant 1523815.

References