Oracle Complexity of Second-Order Methods for Smooth Convex Optimization

Introduction

We consider an unconstrained optimization problem of the form

where $f$ is a generic smooth and convex function. A natural and fundamental question is how efficiently can we optimize such functions.

We study this question through the well-known framework of oracle complexity (Nemirovsky and Yudin, 1983), which focuses on iterative methods relying on local information. Specifically, it is assumed that the algorithm’s access to the function $f$ is limited to an oracle, which given a point $\mathbf{w}$, returns the values and derivatives of the function $f$ at $\mathbf{w}$. This naturally models standard optimization approaches to unstructured problems such as Eq. (1), and allows one to study their efficiency, by bounding the number of oracle calls required to reach a given optimization error. Different classes of methods can be distinguished by the type of oracle they use. For example, gradient-based methods (such as gradient descent or accelerated gradient descent) rely on a first-order oracle, which returns gradients, whereas methods such as the Newton method rely on a second-order oracle, which returns gradients as well as Hessians.

The theory of first-order oracle complexity is quite well developed (Nemirovsky and Yudin, 1983; Nesterov, 2004; Nemirovski, 2005). For example, if the dimension is unrestricted, $f$ in Eq. (1) has $\mu_{1}$-Lipschitz gradients, and the algorithm makes its first oracle query at a point $\mathbf{w}_{1}$, then the worst-case number of queries $T$ required to attain a point $\mathbf{w}_{T}$ satisfying $f(\mathbf{w}_{T})-\min_{\mathbf{w}}f(\mathbf{w})\leq\epsilon$ is

where $D$ is an upper bound on the distance between $\mathbf{w}_{1}$ and the nearest minimizer of $f$. Moreover, if the function $f$ is also $\lambda$-strongly convex for some $\lambda>0$Assuming $f$ is twice-differentiable, this corresponds to $\nabla^{2}f(\mathbf{w})\succeq\lambda I$ uniformly for all $\mathbf{w}$., then the oracle complexity bound is

Both bounds are achievable using accelerated gradient descent (Nesterov, 1983).

However, these bounds do not capture the attainable performance of second-order methods, which rely on gradient as well as Hessian information. This is a central class of optimization methods, including the well-known Newton method and its many variants. Clearly, since these methods rely on Hessians as well as gradients, their oracle complexity can only be better than first-order methods. On the flip side, the per-iteration computational complexity is generally higher, in order to process the additional Hessian information (especially in high-dimensional problems where the Hessian matrix may be very large). Thus, it is natural to ask how much does this added per-iteration complexity pay off in terms of oracle complexity.

To answer this question, one needs good oracle complexity lower bounds for second-order methods, which establish the limits of attainable performance using any such algorithm. Perhaps surprisingly, such results do not seem to currently exist in the literature, and clarifying the oracle complexity of such methods was posed as an important open question (see for example Nesterov, 2008). The goal of this paper is to address this gap.

Specifically, we prove that when the dimension is sufficiently large, for the class of convex functions with $\mu_{1}$-Lipschitz gradients and $\mu_{2}$-Lipschitz Hessians, the worst-case oracle complexity of any deterministic algorithm is

This bound is tight up to constants, as it is matched by a combination of existing methods in the literature (see discussion below). Moreover, if we restrict ourselves to functions which are $\lambda$-strongly convex, we prove an oracle complexity lower bound of

Moreover, we establish that this bound is tight up to logarithmic factors (independent of $\epsilon$), utilizing a novel adaptation of the A-NPE algorithm proposed in Monteiro and Svaiter (2013) (see Appendix A). These new lower bounds have several implications:

Perhaps unexpectedly, Eq. (5) establishes that one cannot avoid in general a polynomial dependence on geometry-dependent “condition numbers” of the form $\mu_{1}/\lambda$ or $\mu_{2}D/\lambda$, even with second-order methods. This is despite the ability of such methods to favorably alter the geometry of the problem (for example, the Newton method is well-known to be affine invariant).

To improve on the oracle complexity of first-order methods for strongly-convex problems (Eq. (3)) by more than logarithmic factors, one cannot avoid a polynomial dependence on the initial distance $D$ to the optimum. This is despite the fact that the dependence on $D$ with first-order methods is only logarithmic. In fact, when $D$ is sufficiently large (of order $\frac{\mu_{1}^{7/4}}{\mu_{2}\lambda^{3/4}}$ or larger), second-order methods cannot improve on the oracle complexity of first-order methods by more than logarithmic factors.

In the convex case, second-order methods are again no better than first-order methods in certain parameter regimes (i.e., when $\mu_{2}\geq\mu_{1}^{7/4}\sqrt{D}/\epsilon^{3/4}$), despite the availability of more information.

Finally, we show how our proof techniques can be generalized, to establish lower bounds for methods employing higher-order derivatives. In particular, for methods using all derivatives up to order $k$, we show that for convex functions with $\mu_{k}$-Lipschitz k-th order derivatives, the oracle complexity is

Note that this directly generalizes Eq. (2) for $k=1$, and Eq. (4) when $k=2$ and $\mu_{1}$ is unrestricted.

Below, we review some pertinent results in the context of second-order methods. Related results in the contest of k-th order methods are discussed in Subsection 2.2.

Perhaps the most well-known and fundamental second-order method is the Newton method, which relies on iterations of the form $\mathbf{w}_{t+1}=\mathbf{w}_{t}-(\nabla^{2}f(\mathbf{w}))^{-1}\nabla f(\mathbf{w})$ (see e.g., Boyd and Vandenberghe (2004)). It is well-known that this method exhibits local quadratic convergence, in the sense that if $f$ is strictly convex, and the method is initialized close enough to the optimum $\mathbf{w}^{*}=\arg\min_{\mathbf{w}}f(\mathbf{w})$, then $\mathcal{O}(\log\log(1/\epsilon))$ iterations suffice to reach a solution $\mathbf{w}$ such that $f(\mathbf{w})-f(\mathbf{w}^{*})\leq\epsilon$. However, in order to get global convergence (starting from an arbitrary point not necessarily close to the optimum), one needs to make some algorithmic modifications, such as introducing a step size parameter or line search, employing trust region methods, or adding various types of regularization (see for example Conn et al. (2000) and references therein). Despite the huge literature on the subject, the worst-case global convergence behavior of these methods is not well understood (Nesterov and Polyak, 2006). For the Newton method with a line search, the number of iterations can be upper bounded by

where $\mu_{1},\mu_{2}$ are the Lipschitz parameters of the gradients and Hessians respectively, and assuming the function is $\lambda$-strongly convex (Kantorovich (1948), see also Boyd and Vandenberghe (2004)). Note that the first term captures the initial phase required to get sufficiently close to $\mathbf{w}^{*}$, whereas the second term captures the quadratically convergent phase. Although the final convergence is rapid, the first phase is the dominant one in the bound (unless $\epsilon$ is exceedingly small). If $f$ is self-concordantThat is, for any vectors $\mathbf{v},\mathbf{w}$, the function $g(t)=f(\mathbf{w}+t\mathbf{v})$ satisfies $|g^{\prime\prime\prime}(t)|\leq 2g^{\prime\prime}(t)^{3/2}$, this can be improved to

independent of the strong convexity and Lipschitz parameters (Nesterov and Nemirovskii (1994)). Unfortunately, not all practically relevant objective functions are self-concordant. For example, loss functions common in machine learning applications, such as the logistic loss $x\mapsto\log(1+\exp(-x))$, are not self-concordantThese can often be made self-concordant by re-scaling, smoothing and adding regularization (e.g. Bach (2010)), but even when possible, these modifications strongly affect the $f(\mathbf{w}_{1})-f(\mathbf{w}^{*})$ term in the bound, and prevents it from being independent of the strong convexity and Lipschitz parameters., and our own results utilize the simple but not self-concordant function $x\mapsto|x|^{3}$.

Returning to our setting of generic convex and smooth functions, and focusing on strongly convex functions for now, the best existing upper bounds (we are aware of) were obtained for cubic-regularized variants of the Newton method, where at each iteration one essentially minimizes a quadratic approximation of the function at the current point, regularized by a cubic term (Nesterov and Polyak, 2006; Nesterov, 2008). The existing analysis (in section 6 of Nesterov (2008)) implies an oracle complexity bound of at most

where $D=\|\mathbf{w}_{1}-\mathbf{w}^{*}\|$ is the distance from the initialization point $\mathbf{w}_{1}$ to the optimum $\mathbf{w}^{*}$ (see section 6 in Nesterov (2008), as well as Cartis et al. (2012) for another treatment of such cubic-regularized methods). However, as we show in Appendix A, a better oracle complexity bound can be obtained, by adapting the A-NPE method proposed in (Monteiro and Svaiter, 2013) and analyzed for convex functions, to the strongly convex case. The resulting complexity upper bound is

An alternative to the above is to use a hybrid scheme, starting with accelerated gradient descent (which is an optimal first-order method for strongly convex functions with Lipschitz gradients) and when close enough to the optimal solution, switch to a cubic-regularized Newton method, which is quadratically converging in that regionInstead of cubic-regularized Newton, one can also use the standard Newton method, although the resulting bound using the existing analysis will have slightly worse logarithmic factors.. The required number of iterations is then

where $D=\|\mathbf{w}_{1}-\mathbf{w}^{*}\|$ (see Nesterov (2004, 2008)). Clearly, by taking the best of Eq. (6) and Eq. (7) (depending on the parameters), one can theoretically attain an oracle complexity which is the minimum of Eq. (6) and Eq. (7). This minimum matches (up to a logarithmic factors) the lower bound in Eq. (5), which we establish in this paper.

It is interesting to note that the bounds in Eq. (6) and Eq. (7) are not directly comparable: The first bound has a polynomial dependence on $\mu_{2}/\lambda$ and $\|\mathbf{w}_{1}-\mathbf{w}^{*}\|$, and a logarithmic dependence on $\mu_{1}$, whereas the second bound has a polynomial dependence on $\mu_{1}/\lambda$, logarithmic dependence on $\|\mathbf{w}_{1}-\mathbf{w}^{*}\|$, and a logarithmic dependence on $\mu_{2}$. In a rather wide parameter regime (e.g. when $D$ is reasonably large, as often occurs in practice), the bound of the hybrid scheme can be better than that of pure second-order methods. In light of this, Nesterov (2008) raised the question of whether second-order schemes are indeed useful at the initial stage of the optimization process, for these types of problems. Our results indicate that indeed, in certain parameter regimes, this is not the case.

Analogous results can be obtained for convex (not necessarily strongly convex) smooth functions. Using an appropriate analysis of the accelerated cubic-regularized Newton method (Nesterov, 2008), one can attain a bound of

More recently, Monteiro and Svaiter (2013) proposed an accelerated hybrid proximal extragradient method, denoted as A-NPE, which attains a better bound of

In addition, using an optimal first-order method (such as accelerated gradient descent), one can attain a bound of

Clearly, by taking the best of the last two approaches (depending on the problem parameters), one can attain an oracle complexity equal to the minimum of the two bounds in Eq. (8) and Eq. (9). This is matched (up to constants) by the lower bound in Eq. (4), which we establish in this paper.

Finally, we discuss the few existing lower bounds known for second-order methods. If $\mu_{2}$ is not bounded (i.e.,the Hessians are not Lipschitz), it is easy to show that Hessian information is not useful. Specifically, the lower bound of Eq. (2) for first-order methods will then also apply to second-order methods, and in fact, to any method based on local information (see Nemirovsky and Yudin (1983, section 7.2.6) and Arjevani and Shamir (2016b)). Of course, this lower bound does not apply to second-order methods when $\mu_{2}$ is bounded. In our setting, it is also possible to prove an $\Omega(\log\log(1/\epsilon))$ lower bound, even in one dimension (Nemirovsky and Yudin, 1983, section 8.1.1), but this does not capture the dependence on the strong convexity and Lipschitz parameters. Some algorithm-specific lower bounds in the context of non-convex optimization are provided in Cartis et al. (2010). Finally, we were recently informed of a new work (Agarwal and Hazan (2017), yet unpublished at the time of writing), which uses a clean and elegant smoothing approach, to derive second- and higher-order oracle lower bounds directly from known first-order oracle lower bounds, as well as extensions to randomized algorithms. However, the resulting bounds are not as tight as ours.

Main Results

In this section, we formally present our main results, starting with second-order oracle complexity bounds (Subsection 2.1), and then discussing extensions to higher-order oracles (Subsection 2.2).

We consider a second-order oracle, which given a point $\mathbf{w}$ returns the function’s value $f(\mathbf{w})$, its gradient $\nabla f(\mathbf{w})$ and its Hessian $\nabla^{2}f(\mathbf{w})$, and algorithms, which produce a sequence of points $\mathbf{w}_{1},\mathbf{w}_{2},...,\mathbf{w}_{T}$, with each $\mathbf{w}_{t}$ being some deterministic function of the oracle’s responses at $\mathbf{w}_{1},\ldots,\mathbf{w}_{t-1}$. Our main results (for strongly convex and convex functions $f$ respectively) are provided below.

$f$ is $\lambda$-strongly convex, twice-differentiable, has $\mu_{1}$-Lipschitz gradients and $\mu_{2}$-Lipschitz Hessians, and has a global minimum $\mathbf{w}^{*}$ satisfying $\|\mathbf{w}_{1}-\mathbf{w}^{*}\|\leq D$.

The index $T$ required to ensure $f(\mathbf{w}_{T})-f(\mathbf{w}^{*})~{}\leq~{}\epsilon$ is at least

$f$ is convex, twice-differentiable, has $\mu_{1}$-Lipschitz gradients and $\mu_{2}$-Lipschitz Hessians, and has a global minimum $\mathbf{w}^{*}$ satisfying $\|\mathbf{w}_{1}-\mathbf{w}^{*}\|\leq D$.

The index $T$ required to ensure $f(\mathbf{w}_{T})-f(\mathbf{w}^{*})\leq\epsilon$ is at least

We emphasize that the theorems focus on the high-dimensional setting, where the dimension $d$ is not necessarily fixed and may depend on other problem parameters. Also, we note that the parameter constraints in Thm. 1 are purely for technical reasons (they imply that the different terms in the bound are at least some positive constant), and can probably be relaxed somewhat.

Let us compare these theorems to the upper bounds discussed in the related work section, which are

in the convex case. Our bound in the convex case is tight up to constants, and in the strongly convex case, up to a $\log(\mu_{1}\mu_{2}^{2}D^{2}/\lambda^{3})$ factor. We conjecture that some such logarithmic factor (possibly a smaller one) is indeed necessary, in order to get a tight interpolation to the $\Omega(\sqrt{\mu_{1}/\lambda}\cdot\log(\mu_{1}D^{2}/\epsilon))$ lower bound of first-order methods as $\mu_{2}\rightarrow\infty$ (see Nemirovsky and Yudin (1983, section 7.2.6) and Arjevani and Shamir (2016b)), and that it can be recovered with a more careful analysis of our construction. However, this involves some non-trivial technical challenges, which we leave to future work.

Comparing the lower and upper bounds in the strongly convex case, one can make the following observations:

The lower bound captures the two phases common in second-order methods such as the Newton method: An initial slow convergence from the initialization point to the local neighborhood of the optimum (captured by the $\min\left\{\sqrt{\frac{\mu_{1}}{\lambda}}~{},~{}\left(\frac{\mu_{2}}{\lambda}D\right)^{2/7}\right\}$ term), followed by a fast local quadratic convergence to the optimum (captured by the second term, which is doubly-logarithmic in the accuracy $\epsilon$).

Unless $\epsilon$ is exceedingly small, the oracle complexity is dominated by the geometry-dependent terms $\mu_{1}/\lambda$ and $\mu_{2}D/\lambda$. This is despite the fact that second-order methods can use Hessian information to alter the geometry of the problem (for example, the Newton method is well-known to be affine invariant).

If $\mu_{2}D/\lambda$ is sufficiently large (specifically, if $D$ is order of $\frac{\mu_{1}^{7/4}}{\mu_{2}\lambda^{3/4}}$ or larger), then the lower bound becomes at least $\sqrt{\mu_{1}/\lambda}$, which is no betters what can be obtained with first-order methods up to logarithmic factors (see Eq. (3)). Since $D$ often scales inversely with the strong convexity of the problem (e.g. since the strong convexity is due to a regularization term), this is a rather broad and reasonable regime.

On the other hand, if $\mu_{2}D/\lambda$ is smaller than $\sqrt{\mu_{1}/\lambda}$, then the oracle complexity can be significantly better than that of first-order methods, but this still comes at the inevitable price of a polynomial dependence on the distance $D$ from the optimum. In contrast, first-order methods have only a logarithmic dependence on $D$ (see Eq. (3)).

Similar types of conclusions regarding on the behavior of first and second-order methods can be drawn as in the strongly convex case. Namely, if $\mu_{2}D^{3}/\epsilon$ is large enough (specifically, if $\mu_{2}\geq\mu_{1}^{7/4}\sqrt{D}/\epsilon^{3/4}$), the complexity of second-order methods is not significantly better than what can be obtained with first-order methods.

2 Higher Order Oracles

In addition to first-order and second-order oracles, it is of interest to understand what can be achieved with methods employing higher order derivatives. It turns out that the techniques we use to establish our second-order lower bounds can be easily generalized to such higher-order methods.

More explicitly, we consider methods which can be modelled as interacting with a k-th order oracle, which given a point $\mathbf{w}$ returns the function’s value and all of its derivatives up to order $k$, namely, $f(\mathbf{w}),\nabla f(\mathbf{w}),\nabla^{2}f(\mathbf{w}),\ldots,\nabla^{k}f(\mathbf{w})$. Given access to such an oracle, the method produces a sequence of points $\mathbf{w}_{1},\mathbf{w}_{2},\ldots,\mathbf{w}_{T}$ as before (where each $\mathbf{w}_{t}$ is a deterministic function of the previous oracle responses). For simplicity, we will focus here on the case of convex functions (not necessarily strongly convex), where the $k$-th order derivative is Lipschitz continuous.

$f$ is convex, $k$ times differentiable, $k$-order smooth (i.e., $\|\nabla^{k}f(\mathbf{u})-\nabla^{k}f(\mathbf{v})\|\leq\mu_{k}\|\mathbf{u}-\mathbf{v}\|$) and has a global minimum $\mathbf{w}^{*}$ satisfying $\|\mathbf{w}_{1}-\mathbf{w}^{*}\|\leq D$.

The index $T$ required to ensure $f(\mathbf{w}_{T})-f(\mathbf{w}^{*})\leq\epsilon$ is at least

Note that this result directly generalizes existing results for first-order oracles ($k=1$), as well as our results for second-order oracles ($k=2$, when $\mu_{1}$ is unrestricted).

Finally, we compare our lower bound to the best upper bound we are aware of, established by Baes (2009) using a high-order method with oracle complexity of

Note that the upper bound contains an additional $(f(\mathbf{w}_{1})-f(\mathbf{w}^{*}))/\epsilon$ term, and moreover, the exponent (as a function of $k$) is larger than ours ($1/(k+1)$ vs. $2/(3k+1)$). Based on our results, we know that this upper bound is loose in the $k=2$ case, so we conjecture that it is indeed loose for all $k$, and can be improved.

Proof Ideas

The proofs of our theorems are based on a careful modification of a standard lower bound construction for first-order methods (see Nesterov (2004)). That construction uses quadratic functions, which in the convex case and ignoring various parameters, have a basic structure of the form

(more precisely, one considers $f_{T}(V\mathbf{w})$ for a certain orthogonal matrix $V$, and use additional parameters depending on the smoothness). A crucial ingredient of the proof is that the function $x\mapsto x^{2}$ has a value and derivative of zero at the origin, which allows us to construct a function which “hides” information from an algorithm relying solely on values and gradients. This can be shown to lead to an optimization error lower bound of the form $\min_{\mathbf{w}}f_{T}(\mathbf{w})-\min_{\mathbf{w}}f_{2T}(\mathbf{w})$ after $T$ oracle queries, which for first-order methods leads to an $\Omega(\mu_{1}D^{2}/T^{2})$ lower bound on the error, translating to an $\Omega(\sqrt{\mu_{1}D^{2}/\epsilon})$ lower bound on $T$. However, this construction leads to trivial bounds for second-order methods, since given the Hessian and a gradient of a quadratic function at just a single point, one can already compute the exact minimizer.

Our approach to handle second-order (and more generally, $k$-order) methods is quite simple: Instead of $x\mapsto x^{2}$, we rely on mappings of the form $x\mapsto|x|^{k+1}$, and use functions with the basic structure

The intuition is that $x\mapsto|x|^{k+1}$ has a value and first k derivatives of zero at the origin, and therefore variants of the function above can be used to “hide” information from the algorithm, even if it can receive Hessians or higher-order derivatives of the function. Another motivation for choosing such functions is that they are generally not self-concordant, and therefore the upper bounds relevant to self-concordant functions do not apply. We rely on this construction and arguments similar to those of first-order oracle lower bounds, to get our results.

In the derivation of our results for second-order methods, there are two technical challenges that need to be overcome: The first is that $f_{T}$, as defined above (for $k=2$), can be shown to have globally Lipschitz Hessians, but not globally Lipschitz gradients as required by our theorems. To tackle this, we replace the mapping $x\mapsto|x|^{3}$ by a more complicated mapping, which is cubic close to the origin and quadratic further away. This necessarily complicates the proof. The second challenge is that due to the cubic terms, computing the minimizer of $f_{T}$ and its minimal value is more challenging than in first-order lower bounds, especially in the strongly convex case (where we are unable to even find a closed-form expression for the minimizer, and resort to bounds instead). Again, this makes the analysis more complicated.

We conclude this section by sketching how our bounds can be derived in case of second-order methods, and in the simplest possible setting, where we wish to obtain an $\Omega((D^{3}/\epsilon)^{2/7})$ lower bound for the class of convex functions with Lipschitz Hessians (and no assumptions on the Lipschitz parameter of the gradients), assuming the algorithm makes its first query at the origin. In that case, consider the function $f_{T}$ in this class of the form

where $\gamma$ is a parameter to be chosen later. Computing the derivatives and setting to zero, and arguing that the minimizer must have non-negative coordinates, we get that the optimum satisfies

Now, using arguments very similar to those in first-order oracle complexity lower bounds (Nesterov, 2004), it is possible to construct a function for which the optimization error of the algorithm is lower bounded by $\min_{\mathbf{w}}f_{T}(\mathbf{w})-\min_{\mathbf{w}}f_{2T}(\mathbf{w})$. By the calculations above, this in turn equals

Using the fact that $\frac{1}{\sqrt{1+x}}\approx 1-\frac{1}{2}x$ for small $x$, this equals $\Omega(\gamma^{3/2}/T^{2})$. Choosing $\gamma$ on the order of $D^{2}/T$ (as required earlier to satisfy the norm constraint on the minimizer), we get a lower bound of $\Omega(D^{3}/T^{7/2})$ on the optimization error $\epsilon$, or equivalently, a lower bound of $\Omega((D^{3}/\epsilon)^{2/7})$ on $T$.

Proof of Thm. 1

We will assume without loss of generality that the algorithm initializes at $\mathbf{w}_{1}=\mathbf{0}$ (if that is not the case, one can simply replace the “hard” function $f(\mathbf{w})$ below by $f(\mathbf{w}-\mathbf{w}_{1})$, and the same proof holds verbatim). Thus, the theorem requires that our function has a minimizer $\mathbf{w}^{*}$ satisfying $\|\mathbf{w}^{*}\|\leq D$.

The proof is constructed of several parts: First, we analyze properties of the global minimum of $f$ (Subsection 4.1). Then, we prove the oracle complexity lower bound in Subsection 4.2 (depending on $\Delta,\gamma$), and finally, in Subsection 4.3, we choose the parameters so that $f$ indeed has the various geometric properties specified in the theorem.

The goal of this subsection is to prove the following proposition, which characterizes key properties of the global minimum of $f$:

Suppose that $\gamma\geq 10^{4}\left(\frac{\lambda}{\mu_{2}}\right)^{2}$ and $\Delta\geq\sqrt{\gamma}$. Then $f$ has a unique minimizer $\mathbf{w}^{*}$ which satisfies the following:

$\|\mathbf{w}^{*}\|^{2}\leq\frac{2\gamma^{7/4}}{(12\lambda/\mu_{2})^{3/2}}$ .

Since $f$ is strongly convex, its global minimizer is unique and well-defined. To prove the proposition, we will consider the simpler strongly-convex function

We begin with the following technical key result:

So by using Eq. (11) we get the desired equality. ∎

On the other hand, again by Lemma 1, we know that

2 Oracle Complexity Lower Bound

In this subsection, we prove the following oracle complexity lower bound, depending on the free parameter $\gamma$:

To prove the theorem, we will need the following key lemma, which establishes that oracle information at certain points $\mathbf{w}$ do not leak any information on some of the $\mathbf{v}_{1},\mathbf{v}_{2},\ldots$ vectors.

First, we compute $\mathbf{w}_{1}$ (which is possible since the algorithm is deterministic and $\mathbf{w}_{1}$ is chosen before any oracle calls are made).

By Proposition 1, we can lower bound the above by

Using the strong convexity of $f$, we therefore get

To make the right-hand side smaller than $\epsilon$, $T$ must satisfy

Assuming $\epsilon<\frac{108^{2}\cdot\lambda^{3}}{\mu_{2}^{2}}$, then

We now turn to argue that we can also lower bound $T$ by $\frac{\gamma^{1/4}}{7\sqrt{12\lambda/\mu_{2}}}$. Otherwise, suppose by contradiction that we can have $f(\mathbf{w}_{T})-f(\mathbf{w}^{*})\leq\epsilon$ for some $T<\frac{\gamma^{1/4}}{7\sqrt{12\lambda/\mu_{2}}}$. From Proposition 1 we know that

To make the right-hand side smaller than $\epsilon$, $T$ must satisfy

But since we assume $\epsilon<\frac{\gamma\lambda}{8}$, this is at least $\frac{\gamma^{1/4}}{7\sqrt{12\lambda/\mu_{2}}}$, contradicting our earlier assumption.

Overall, we showed that $T$ is lower bounded by both $\frac{\gamma^{1/4}}{7\sqrt{12\lambda/\mu_{2}}}$, as well as $\log_{2}\log_{18}\left(\frac{108^{2}\cdot\lambda^{3}}{\mu_{2}^{2}\epsilon}\right)-1$, hence proving Proposition 2.

3 Setting the γ,Δ𝛾Δ\gamma,\Delta Parameters

In the following lemma, we establish the strong convexity and smoothness parameters of $f$ (depending on the parameter $\Delta$ which is still free at this point).

$f$ is $\lambda$-strongly convex and twice-differentiable, with $\mu_{2}$-Lipschitz Hessians and $\left(\frac{2\mu_{2}\Delta}{3}+\lambda\right)$-Lipschitz gradients.

Since $f$ is a sum of convex, twice-differentiable functions and the $\lambda$-strongly convex function $\frac{\lambda}{2}\|\mathbf{w}\|^{2}$, it is clearly $\lambda$-strongly convex and twice-differentiable. Thus, it only remains to calculate the Lipschitz parameter of the gradients and Hessians.

By definition of $g$, it is easily verified that

which is a $2$-Lipschitz function bounded in $[0,2\Delta]$. This implies that $g^{\prime}(x)$ is $2\Delta$-Lipschitz. Letting $\mathbf{r}_{i}:=\mathbf{e}_{i}-\mathbf{e}_{i+1}$, we can write $\hat{f}$ as

Since this is a sum of positive-semidefinite matrices with non-negative coefficients (as we showed that $g^{\prime\prime}(x)\in[0,2\Delta]$ for all $x$), it follows that its spectral norm is at most

Overall, we showed that $\|\nabla^{2}\hat{f}(\mathbf{w})\|\leq\frac{2\mu_{2}\Delta}{3}+\lambda$, so the gradients of $f$ are $\left(\frac{2\mu_{2}\Delta}{3}+\lambda\right)$-Lipschitz.

hence $\nabla^{2}\hat{f}(\mathbf{w})$ is $\mu_{2}$-Lipschitz. ∎

We now collect the ingredients necessary to fix $\gamma,\Delta$ and hence prove our theorem. Combining the previous lemma, Proposition 1 and Proposition 2, and recalling that we want $f$ to have $\mu_{1}$-Lipschitz gradients and $\mu_{2}$-Lipschitz Hessians, with an optimizer $\mathbf{w}^{*}$ satisfying $\|\mathbf{w}^{*}\|\leq D$, we have an oracle complexity lower bound of the form

Picking $\Delta=\sqrt{\gamma}$, using the fact that $\mu_{1}\geq\lambda$ (as any $\lambda$-strongly convex function must have gradients with Lipschitz parameter at least $\lambda$), and rewriting the last two conditions, this is equivalent to

Since the first condition needs to hold anyway, we can allow ourself to make the second condition stronger, by substituting $10^{4}(\lambda/\mu_{2})^{2}$ in lieu of $\gamma$ in the second condition. Doing this, simplifying, and merging the last two conditions, the set of condition above is implied by requiring

Clearly, to make the lower bound in Eq. (19) as large as possible, we should pick the largest possible $\gamma$, namely $\gamma=\min\left\{\left(\frac{3(\mu_{1}-\lambda)}{2\mu_{2}}\right)^{2},\sqrt{\frac{D^{8}(12\lambda)^{6}}{2^{4}\mu_{2}^{6}}}\right\}$, and to ensure that the other conditions hold, require that

Simplifying a bit, these two conditions are implied by requiring

Finally, let us plug our choice of $\gamma=\min\left\{\left(\frac{3(\mu_{1}-\lambda)}{2\mu_{2}}\right)^{2},\sqrt{\frac{D^{8}(12\lambda)^{6}}{2^{4}\mu_{2}^{6}}}\right\}$ into the lower bound in Eq. (19). We thus get an oracle complexity lower bound of

To simplify the bound a bit, we note that we can lower bound $\mu_{1}-\lambda$ by $\frac{67}{68}\mu_{1}$ (possible by Eq. (20)), and lower bound $\log_{2}\log_{18}\left(\frac{108^{2}\cdot\lambda^{3}}{\mu_{2}^{2}\epsilon}\right)-1$ by $\frac{1}{2}\log\log_{18}\left(\frac{\lambda^{3}}{\mu_{2}^{2}\epsilon}\right)$, by assuming that $\epsilon\leq c\lambda^{3}/\mu_{2}^{2}$ for some small enough $c$ (in other words, increasing the constant in the third condition in Eq. (20)). Finally, using the fact that $\max\{a,b\}\geq(a+b)/2$, the result in the theorem follows.

Proof of Thm. 2

Similarly to the strongly convex case, we will assume without loss of generality that the algorithm initializes at $\mathbf{w}_{1}=\mathbf{0}$, since otherwise one can simply replace the “hard” function $f(\mathbf{w})$ below by $f(\mathbf{w}-\mathbf{w}_{1})$, and the same proof holds verbatim. Thus, the theorem requires that our function has a minimizer $\mathbf{w}^{*}$ satisfying $\|\mathbf{w}^{*}\|\leq D$.

This function is easily shown to be convex and twice-differentiable, with $\mu_{1}$-Lipschitz gradients and $\mu_{2}$-Lipschitz Hessians (the proof is identical to the proof of Lemma 8). Our goal will be to show a lower bound on the optimization error using this type of function.

We begin with the following technical lemma:

for all $t=1,2,\ldots,T$, where $\delta$ is non-negative and independent of t. Moreover,

Taking the derivative and setting to zero, we get that the

for all $j\in\{2,3,\ldots,T-1\}$. By definition of $g$, it is easily verified that $g^{\prime}$ is a strictly monotonic (hence invertible) function, so the above implies $\hat{w}^{*}_{j-1}-\hat{w}^{*}_{j}=\hat{w}^{*}_{j}-\hat{w}^{*}_{j+1}$ for all $j\in\{2,3,\ldots,T-1\}$, as well as $\hat{w}^{*}_{T-1}-\hat{w}^{*}_{T}=\hat{w}^{*}_{T}$. From this, it follows by straightforward induction that $\hat{w}^{*}_{T+1-t}=t\cdot\hat{w}^{*}_{T}$, from which the first displayed equation in the lemma follows. This also implies $g^{\prime}(T\hat{w}^{*}_{T})+g^{\prime}(\hat{w}^{*}_{T})=\gamma$, and since $g^{\prime}$ is strictly monotonic, we have that $\hat{w}^{*}_{T}$ is uniquely defined, and since the other coordinates of $\hat{\mathbf{w}}^{*}$ are also uniquely defined given $\hat{w}^{*}_{T}$, we get that $\hat{\mathbf{w}}^{*}$ is unique. Finally, $\delta$ (and hence $\hat{w}_{t}^{*}$ for all $t$) is necessarily non-negative, since otherwise $\hat{w}^{*}_{1}$ is negative, which would imply $\hat{f}_{T}(\hat{\mathbf{w}}^{*})>0$, even though $\hat{f}_{T}(\mathbf{0})=0$, violating the fact that $\hat{\mathbf{w}}^{*}$ minimizes $\hat{f}_{T}$. ∎

The main technical result in this subsection is the following proposition, which characterizes $\|\hat{\mathbf{w}}^{*}\|$ and $\hat{f}_{T}(\hat{\mathbf{w}}^{*})$ under various parameter regimes. By the discussion above and definition of $f_{T}$, we have

which will be used in the remainder of the proof of our theorem.

The function $\hat{f}_{T}$ and its minimizer $\hat{\mathbf{w}}^{*}$ has the following properties, depending on the values of $\gamma,\Delta,T$:

To prove the proposition, we will consider three regimes, depending on $T,\delta,\Delta$: Namely, $T\delta\leq\Delta$, $\frac{\Delta}{T}<\delta\leq\Delta$ and $\delta>\Delta$. We will show that each regime corresponds to one of the three regimes specified in the proposition, and prove the relevant bounds.

Case 1: $T\delta\leq\Delta$. In that case, $\hat{w}^{*}_{1},\hat{w}^{*}_{T}$ as well as $\hat{w}^{*}_{i}-\hat{w}^{*}_{i+1}$ for all $i=2,\ldots,T-1$ in the definition of $\hat{f}_{T}$ all lie in the interval where $g$ is a cubic function. Using Lemma 9,

Therefore, our condition $T\delta\leq\Delta$ is exactly equivalent to $\gamma\leq\frac{\Delta^{2}\left(1+T^{2}\right)}{T^{2}}$, namely the first regime discussed in the proposition. We now establish the relevant bounds:

where in the calculation above we used fact $\sum_{t=1}^{T}t^{2}\leq\int_{1}^{T+1}t^{2}dt<\frac{(T+1)^{3}}{3}$.

Case 2: $\frac{\Delta}{T}<\delta\leq\Delta$. In this case, by Lemma 9, $\hat{w}^{*}_{T}\leq\Delta$ but $\hat{w}^{*}_{1}>\Delta$. Therefore, in the definition $\hat{f}_{T}(\hat{\mathbf{w}}^{*})$, $g(\hat{w}^{*}_{1})$ lies in the quadratic region of $g$, whereas $g(\hat{w}^{*}_{T})$ and $g^{\prime}(\hat{w}^{*}_{i}-\hat{w}^{*}_{i+1})$ for all $i$ lies in the cubic region of $g$. As a result,

Plugging in $w^{*}_{T}=\delta$ and $w^{*}_{1}=T\cdot\delta$, we get

and therefore (using the fact $\delta\geq 0$, see Lemma 9),

This, plus the assumption $\frac{\Delta}{T}<\delta\leq\Delta$, is equivalent to $\frac{\Delta^{2}\left(1+T^{2}\right)}{T^{2}}<\gamma\leq 2\Delta^{2}T$, hence showing that we are indeed in the second regime as specified in our proposition. Turning to calculate the relevant bounds, we have

which by definition of $\delta$ above and the inequality $\sqrt{1+x}\leq 1+\frac{1}{2}x$ for all $x\geq 0$, is at most $\frac{\left(\gamma+\Delta^{2}\right)^{2}(T+1)^{3}}{12\Delta^{2}T^{2}}$.

Case 3: $\delta>\Delta$. In this case, by Lemma 9, we have $\hat{w}^{*}_{1}>\hat{w}^{*}_{T}=\hat{w}^{*}_{i}-\hat{w}^{*}_{i+1}>\Delta$, which implies that in the definition of $\hat{f}_{t}(\hat{\mathbf{w}}^{*})$, these terms all lie in the quadratic region of $g$. Therefore,

Note that this, plus our assumption $\delta>\Delta$, is equivalent to $\gamma>2\Delta^{2}T$, which shows that we are indeed in the third regime as specified in our proposition. Turning to calculate $\|\hat{\mathbf{w}}^{*}\|$ and $\hat{f}_{T}(\hat{\mathbf{w}}^{*})$, we have

2 Oracle Complexity Lower Bound

Given the expressions on the optimal value of $\hat{f}_{T}$, derived in the previous subsection, we turn to explain how the oracle complexity lower bound is derived. The argument is very similar to the strongly convex case (proof of Thm. 1, subsection 4.2): Specifically, consider the function $f_{2T}$, given by

Given an algorithm, we choose $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{T}$ to be orthogonal unit vectors, so that each $\mathbf{v}_{t}$ is orthogonal to the first $t$ points $\mathbf{w}_{1},\mathbf{w}_{2},\ldots,\mathbf{w}_{t}$ computed by the algorithm (this is possible, since the gradients and Hessians of $f_{2T}$ at each $\mathbf{w}_{t}$ reveals no information on future $\mathbf{v}_{t}$’s – see Lemma 7). Also, we let $\mathbf{v}_{T+1},\ldots,\mathbf{v}_{2T}$ equal $\mathbf{v}_{T}$.

With this choice, it is easily verified that

which is clearly no better than $\min_{\mathbf{w}}f_{T}(\mathbf{w})$, where $f_{T}$ is defined with the same $\mathbf{v}_{1},\ldots,\mathbf{v}_{T}$. Therefore, we can lower bound the optimization error $f_{2T}(\mathbf{w}_{T})-\min_{\mathbf{w}}f_{2T}(\mathbf{w})$ by $\min_{\mathbf{w}}f_{T}(\mathbf{w})-\min_{\mathbf{w}}f_{2T}(\mathbf{w})$. Moreover, by Eq. (21), this equals

Using proposition 3, we can now plug in these minimal values, depending on the various parameter regimes, and get an oracle complexity lower bound. Computing these bounds and parameter regimes (while picking the free parameter $\gamma$ appropriately) is performed in the next subsection.

3 Setting the γ𝛾\gamma Parameter

To simplify notation, we let $\hat{f}^{*}_{T}$ and $\hat{f}^{*}_{2T}$ be shorthand for $\min_{\mathbf{w}}\hat{f}_{T}(\mathbf{w})$ and $\min_{\mathbf{w}}\hat{f}_{2T}(\mathbf{w})$ respectively, with minimizers $\hat{\mathbf{w}}^{*}_{T}$ and $\hat{\mathbf{w}}^{*}_{2T}$. We will consider three regimes, depending on the relationships between $D,\Delta,T$.

Using this and the assumption on the parameters, we get that $\gamma\leq\Delta^{2}<\frac{\Delta^{2}\left(1+4T^{2}\right)}{4T^{2}}<\frac{\Delta^{2}\left(1+T^{2}\right)}{T^{2}}$ , and therefore, we are in the first regime for both $f_{T}$ and $f_{2T}$ as specified in proposition 3. Plugging in the bound on $\|\hat{\mathbf{w}^{*}}\|^{2}$ in that regime, and using the fact that $\Delta^{2}\leq\gamma$ by the assumption above, we have

Using the results from proposition 3 for the first regime we can compute the optimization error bound

Where in the first inequality we used the fact that $1-\frac{1}{2}x\leq\frac{1}{\sqrt{1+x}}\leq 1-\frac{1}{2}x+\frac{3}{8}x^{2}$ for all $x\geq 0$ and for the last inequality we assumed that $T\geq 2$. In the case that $T=1$, the final result still holds. Hence, the suboptimality is at least $\frac{\mu_{2}D^{3}}{16000T^{7/2}}$.

Using this and the assumption on the parameters, we get that $\frac{\Delta^{2}\left(1+T^{2}\right)}{T^{2}}<\gamma<2\Delta^{2}T$, and therefore, we are in the second regime for both $f_{T}$ and $f_{2T}$ as specified in proposition 3. Plugging in the bound on $\|\hat{\mathbf{w}^{*}}\|^{2}$ in that regime, and using the fact that $\Delta^{2}<\gamma$ by the assumption above, we have

Turning to compute the optimization error bound, and letting $\delta_{T},\delta_{2T}$ denote the quantity $\delta$ in proposition 3 for $\hat{f}_{T}$ and $\hat{f}_{2T}$ respectively, we have

To continue, we use the following auxiliary lemma:

$\left(2\delta_{2T}-\delta_{T}\right)\left(T\left(\Delta^{2}+\gamma\right)-\Delta T^{2}\left(2\delta_{2T}+\delta_{T}\right)\right)\geq 0$

First we will prove that $T\left(\Delta^{2}+\gamma\right)-\Delta T^{2}\left(2\delta_{2T}+\delta_{T}\right)\geq 0$.

Since $\delta_{T}=-\Delta T+\Delta T\sqrt{1+\frac{\gamma+\Delta^{2}}{\Delta^{2}T^{2}}}$ and using $\sqrt{1+x}\leq 1+\frac{1}{2}x$ for $x\geq 0$ we have that:

To complete the proof, it remains to show that $2\delta_{2T}-\delta_{T}\geq 0$. We have

Define $\alpha:=\frac{\gamma+\Delta^{2}}{\Delta^{2}T^{2}}\geq 0$. Hence, we need to prove:

Which is true since $\sqrt{1+\alpha}\leq 1+\frac{1}{2}\alpha$. ∎

With this lemma, we can lower bound the optimization error in Eq. (23) by

To continue, we note that by definition of $\delta_{T},\delta_{2T}$ and the fact that $1+\frac{1}{2}x-\frac{1}{8}x^{2}\leq\sqrt{1+x}\leq 1+\frac{1}{2}x$, we have

Using this inequality, and the fact $(a-b)^{3}\leq a^{3}-b^{3}$ for $a\geq b\geq 0$, we can lower bound Eq. (24) by

Hence, the suboptimality is at least $\frac{\mu_{2}D^{3}}{30000T^{7/2}}$.

Using this and the assumption on the parameters, we get that $\gamma>4\Delta^{2}T$, and therefore, we are in the third regime for both $f_{T}$ and $f_{2T}$ as specified in proposition 3. Plugging in the bound on $\|\hat{\mathbf{w}}^{*}_{2T}\|^{2}$ in that regime, and using the fact that $2\Delta^{2}<\gamma$ by the assumption above, we have

Now, by the assumptions that $T\Delta^{3}<\frac{\Delta D^{2}}{48T^{2}}$ and by using the fact that $1-x\leq\frac{1}{1+x}\leq 1-x+x^{2}$ for all $x\geq 0$, the optimization error bound is

In the last inequality we assumed that $T\geq 3$. For $T=1,2$ it can be easily verified that the inequality holds. Hence, using $\Delta=\frac{3\mu_{1}}{2\mu_{2}}$ the suboptimality is at least $\frac{\mu_{1}D^{2}}{576T^{2}}$.

4 Wrapping Up

Combining the three cases from the previous subsection, we see that we get the following lower bound

Equating these bounds to $\epsilon$, and solving for $T$, the theorem follows.

Proof of Thm. 3

By the following lemma, $f_{T}(\mathbf{w})$ is $k$-times differentiable, with $\mu_{k}$-Lipschitz $k-th$ order derivative tensor.

$f_{T}(\mathbf{w})$ is $k$-times differentiable, with $\mu_{k}$-Lipschitz $k-th$ order derivative tensor.

Similarly to Lemma 8, we can assume without loss of generality, that the vectors $\mathbf{v}_{1},\mathbf{v}_{2},...,\mathbf{v}_{T}$ correspond to the standard basis vectors $\mathbf{e}_{1},\mathbf{e}_{2},...,\mathbf{e}_{T}$, so we can examine the Lipschitz property of

By Differentiating $k$ times, we have that

Note that for a $k$-th order symmetric tensor $T$ , the operator norm equals (see e.g. (Mu et al., 2015)):

Where in the first inequality we used that $\|\mathbf{r}_{i}\|\leq\sqrt{2}~{}~{}~{}\forall i$.

for some $\delta>0$ and all $t=1,2,\ldots,T$ and

Where we used $\sum_{t=1}^{T}\left(1-\frac{t}{1+T}\right)^{2}\leq\frac{1}{3}(1+T)$ as in Proposition 3.

2 Oracle Complexity Lower Bound

The derivation of the lower complexity bound will be exactly the same as in Subsection 5.2.

In Subsection 5.2 we showed that we can lower bound the optimization error $f_{2T}(\mathbf{w}_{T})-\min_{\mathbf{w}}f_{2T}(\mathbf{w})$ by $\min_{\mathbf{w}}f_{T}(\mathbf{w})-\min_{\mathbf{w}}f_{2T}(\mathbf{w})$. Using the fact that

Letting $f_{T}^{*}$ and $\hat{f}_{T}^{*}$ to be the minimal values of $f_{T}$ and $\hat{f}_{T}$ respectively, and by using equation Eq. (6.1) then

The last inequality holds for $k=1,T\geq 3$, $k=2,T\geq 2$ or $k\geq 3,T\geq 1$. It can be verified that for the other cases, the inequality above holds.

Since we want $f_{T}^{*}-f_{2T}^{*}$ to be as large as possible, we will set $\gamma$ to be as large as possible, under the constraint that $\|\mathbf{w}^{*}_{2T}\|\leq D$. By Eq. (6.1) we can choose

Thus, according to the discussion in Subsection 6.2, the final bound is

and the number of iterations required for having $\min_{\mathbf{w}}f_{T}(\mathbf{w})-\min_{\mathbf{w}}f_{2T}(\mathbf{w})<\epsilon$ , $T_{\epsilon}$ must satisfy

Where $c=\left(\frac{1}{12}\right)^{\frac{1}{5}}\cdot\left(\frac{\sqrt{2}}{3}\right)^{\frac{4}{5}}$.

Acknowledgments

We thank Yurii Nesterov for several helpful comments on a preliminary version of this paper, as well as Naman Agarwal, Elad Hazan and Zeyuan Allen-Zhu for informing us about the A-NPE algorithm of Monteiro and Svaiter (2013).

References

Appendix A An Improved Second-Order Oracle Complexity Bound for Strongly Convex Functions

In this section, we show how the A-NPE algorithm of Monteiro and Svaiter , which is a second-order method analyzed for smooth convex functions, can be used to yield near-optimal performance if the function is also strongly convex. Rather than directly adapting their analysis, which is non-trivial, we use a simple restarting scheme, which allows one to convert an algorithm for the convex setting, to an algorithm in the strongly convex settingWe note that the reverse direction, of adapting strongly convex optimization algorithms to the convex case, is more common in the literature, and can be achieved using regularization or more sophisticated approaches [Allen-Zhu and Hazan, 2016]..

Our algorithm is described as follows: In the first phase, we apply a generic restarting scheme (based on [Arjevani and Shamir, 2016a, Subsction 4.2]), where we repeatedly run A-NPE for a bounded number of steps, followed by restarting the algorithm, running it from the last iterate obtained. By strong convexity, we show that each such epoch reduces the suboptimality by a constant factor. Once we reach a point sufficiently close to the global optimum, we switch to the second phase, where we use the cubic-regularized Newton method to get a quadratic convergence rate.

To formalize this, let us first analyze the convergence rate of the first phase. We assume that we use the algorithm described in Monteiro and Svaiter [2013, Subsection 7.4]Specifically, since in our framework we do not limit computational resources, we assume that the minimization problem in Eq. (6.1) of Monteiro and Svaiter can be solved exactly.. By [Monteiro and Svaiter, 2013, Theorem 6.4 and Theorem 3.10], we have that the $t$’th iterate satisfies

where $\mu_{2}$ is the Lipschitz constant of $\nabla^{2}f$, $\mathbf{w}_{1}$ is the initialization point, $\mathbf{w}^{*}$ is the unique minimizer (due to strong convexity) of $f$, $D$ bounds $\|\mathbf{w}_{1}-\mathbf{w}^{*}\|$ from above, and $c>0$ is some universal constant. Since $f$ is also assumed to be $\lambda$-strongly convex, we have

iterations, we see that $f(\mathbf{w}_{t})-f(\mathbf{w}^{*})\leq{(f(\mathbf{w}_{1})-f(\mathbf{w}^{*}))}/{2}$. Now, since the distance from $\mathbf{w}_{t}$ to $\mathbf{w}^{*}$ is also smaller than $D$, we may initialize the algorithm at the last iterate returned by the previous run and run it for $\tau$ iterations to reduce $f(\mathbf{w}_{t})-f(\mathbf{w}^{*})$ in, yet again, a factor of 2. Applying the algorithm for $T$ iterations (and restarting the algorithmic parameters after every $\tau$ iterations) yields

Equivalently, to obtain an $\epsilon$-optimal solution, we need at most

oracle calls (note that this restarting scheme can be applied also on uniform convex functions of any order (defined in, e.g., (Vladimirov et al. )).

Next, after performing a number of iterations sufficiently large to obtain high accuracy solutions, we proceed to the second phase of the algorithm where cubic-regularized Newton steps are applied (see Nesterov ). According to that analysis, after reducing the optimization error to below $\lambda^{3}/4\mu_{2}^{2}$, the number of cubic-regularized Newton steps required to achieve an $\epsilon$-suboptimal solution is

Thus, using the $\mu_{1}$-Lipschitzness of the gradient to bound $f(\mathbf{w}_{1})-f(\mathbf{w}^{*})$ from above by $\mu_{1}D^{2}/2$, we get that the overall number of iterations is at most