On the Iteration Complexity of Oblivious First-Order Optimization Algorithms

Introduction

The ever-increasing utility of mathematical optimization in machine learning and other fields has led to a great interest in understanding the computational boundaries of solving optimization problems. Of a particular interest is the class of unconstrained smooth, and possibly strongly convex, optimization problems. Formally, we consider the following problem,

for some $L>0$, and possibly $\mu$-strongly convex, that is,

for some $\mu>0$. In this work, we address the question as to how fast can one expect to solve this sort of problems to a prescribed level of accuracy, using methods which are based on first-order information (gradients, or more generally sub-gradients) alone.

is at leastFollowing standard conventions, here, tilde notation hides logarithmic factors in the smoothness parameter, the strong convexity parameter and the distance of the initialization point from the minimizer.

where $\kappa\coloneqq L/\mu$ is the so-called condition number. This lower bound, although based on information considerations alone, is tight. Concretely, it is achieved by a combination of Nesterov’s well-known accelerated gradient descent (AGD, ) with an iteration complexity of

and the center of gravity method (MCG, ) whose iteration complexity is

Although the combination of MCG and AGD appear to achieve optimal iteration complexity, this is not the case when focusing on computationally efficient algorithms. In particular, the per-iteration cost of MCG scales poorly with the problem dimension, rendering it impractical for high-dimensional problems. In other words, not taking into account the computational resources needed for processing first-order information limits the ability of the oracle model to give a faithful picture of the complexity of optimization.

To overcome this issue recently proposed the framework of $p$-Stationary Canonical Linear Iterative ($p$-SCLI) in which, instead of modeling the way algorithms acquire information on the function at hand, one assumes certain dynamics which restricts the way new iterates are being generated. This framework includes a large family of computationally efficient first-order algorithms, whose update rule, when applied on quadratic functions, reduce to a recursive application of some fixed linear transformation on the most recent $p$ points (in other words, $p$ indicates the number of previous iterates stored by the algorithm in order to compute a new iterate). The paper showed that the iteration complexity of $p$-SCLIs over smooth and strongly convex functions is bounded from below by

Crucially, as opposed to the classical lower bounds in (1), the lower bound in (3) holds for any dimension $d>1$. This implies that even for fixed $d$, the iteration complexity of $p$-SCLI algorithms must scale with the condition number. That being said, the lower bound in (3) raises a few major issues which we wish to address in this work:

Practical first-order algorithms in the literature only attain this bound for $p=1,2$ (by standard gradient descent and AGD, respectively), so the lower bound appears intuitively loose. Nevertheless, showed that this bound is actually tight for all $p$. The reason for this discrepancy is that the bound for $p>2$ was shown to be attained by $p$-SCLI algorithms whose updates require exact knowledge of spectral properties of the Hessian, which is computationally prohibitive to obtain in large-scale problems. In this work, we circumvent this issue by systematically considering the side-information available to the algorithm. In particular, we show that under the realistic assumption, that the algorithm may only utilize the strong convexity and smoothness of the objective function, the lower bound in (3) can be substantially improved.

The lower bound stated above is limited to stationary optimization algorithms whose coefficients $\alpha_{j},\beta_{j}$ are not allowed to change in time (see Section 2.2).

The formulation suggested in does not allow generating more than one iterate at a time. This requirement is not met by many popular optimization problems for finite sums minimization.

Lastly, whereas the proofs in are elaborate and technically complex, the proofs we provide here are relatively short and simple.

In its simplest form, the framework we consider is concerned with algorithms which generate iterates by applying the following simple update rule repeatedly:

This basic formulation already subsumes popular first-order optimization algorithms. For example, at each iteration the Gradient Descent (GD) method generates a new iterate by computing a linear combination of the current iterate and the gradient of the current iterate, i.e.,

for some real scalar $\alpha$. Another important example is a stationary variant of AGD and the heavy-ball method (e.g., ) which generates iterates according to

In this paper, we follow a generalized form of (4) which is exhibited by standard optimization algorithms: GD, conjugate gradient descent, sub-gradient descent, AGD, the heavy-ball method, coordinate descent, quasi-Newton methods, ellipsoid method, etc. The main difference being how much effort one is willing to put in computing the coefficients of the optimization process. We call these methods first-order $p$-Canonical Linear Iterative optimization algorithms (in this paper, abbr. $p$-CLI). We note that our framework (as a method to prove lower bounds) also applies to stochastic algorithms, as long as the expected update rule (conditioned on the history) follows a generalized form similar to (4).

In the context of machine learning, many algorithms for minimizing finite sums of functions with, possibly, a regularization term (also known as, Regularized Empirical Risk Minimization) also fall into our framework, e.g., Stochastic Average Gradient (SAG, ), Stochastic Variance Reduction Gradient (SVRG, ), Stochastic Dual Coordinate Ascent (SDCA, ), Stochastic Dual Coordinate Ascent without Duality (SDCA without duality, ) and SAGA , to name a few, and as such, are subject to the same lower bounds established through this framework.

In its full generality, the formulation of this framework is too rich to say much. In what follows, we shall focus on oblivious p-CLIs, which satisfy the realistic assumption that the coefficients $\alpha_{j},\beta_{j}$ do not depend on the specific function under consideration. Instead, they can only depend on time and some limited side-information on the function (this term will be made more precise in Definition 1). In particular, we show that the iteration complexity of oblivious $p$-CLIs over $L$-smooth and $\mu$-strongly convex functions whose coefficients are allowed to depend on $\mu$ and $L$ is

Note that, in addition to being dimension-independent (similarly to (3)), this lower bound holds regardless of $p$. We further stress that the algorithms discussed earlier which attain the lower bound stated in (3) are not oblivious and require more knowledge of the objective function.

In the paper, we also demonstrate other cases where the side-information available to the algorithm crucially affects its performance, such as knowing vs. not knowing the strong convexity parameter.

Finally, we remark that this approach of modeling the structure of optimization algorithms, as opposed to the more traditional oracle model, can be also found in . However, whereas these works are concerned with upper bounds on the iteration complexity, in this paper we primarily focus on lower bounds.

To summarize, our main contributions are the following:

In Section 2.1, we propose a novel framework which substantially generalizes the framework introduced in , and includes a large part of modern first-order optimization algorithms.

In Section 2.2, we identify within this framework the class of oblivious optimization algorithms, whose step sizes are scheduled regardless of the function at hand, and provide an iteration complexity lower bound as given in (7). We improve upon by establishing lower bounds which hold both for smooth functions and smooth and strongly convex functions, using simpler and shorter proofs. Moreover, in addition to being dimension-independent, the lower bounds we derive here are tight. In the context of machine learning optimization problems, the same lower bound is shown to hold on the bias of methods for finite sums with a regularization term, such as: SAG, SAGA, SDCA without duality and SVRG.

Some oblivious algorithms for $L$-smooth and $\mu$-strongly convex functions admit a linear convergence rate using step sizes which are scheduled regardless of the strong convexity parameter (e.g., standard GD with a step size of $1/L$. See Section 3 in and Section 5 in ). In Section 4.1, we show that adapting to ’hidden’ strong convexity, without explicitly incorporating the strong convexity parameter, results in an inferior iteration complexity of

This result sheds some light on a major issue regarding scheduling step sizes of optimization algorithms .

In Section 4.2, we discuss the class of stationary optimization algorithms, which use time-invariant step sizes, over $L$-smooth functions and show that they admit a tight iteration complexity of

In particular, this bound implies that in terms of dependency on the accuracy parameter $\epsilon$, SAG and SAGA admit an optimal iteration complexity w.r.t. the class of stochastic stationary $p$-CLIs. Acceleration schemes, such as , are able to break this bound by re-scheduling these algorithms in a non-stationary (though oblivious) way.

Framework

In the sequel we present our framework for analyzing first-order optimization algorithms. We begin by providing a precise definition of a class of optimization problems, accompanied by some side-information. We then formally define the framework of $p$-CLI algorithms and the corresponding iteration complexity.

A class of optimization problems $\mathcal{C}$ is an ordered pair of $(\mathcal{F},I)$, where $\mathcal{F}$ is a family of functions which defined over the same domain, and $I:\mathcal{F}\to\mathfrak{I}$ is a mapping which provides for each $f\in\mathcal{F}$ the corresponding side-information element in some set $\mathfrak{I}$. The domain of the functions in $\mathcal{F}$ is denoted by $\text{dom}(\mathcal{C})$.

For example, let us consider quadratic functions of the form

We now turn to rigorously define first-order $p$-CLI optimization algorithms. The basic formulation shown in (4) does not allow generating more than one iterate at a time. The framework which we present below relaxes this restriction to allow a greater generality which is crucial for incorporating optimization algorithms for finite sums (see Stochastic $p$-CLIs in Section 2.2). We further extend (4) to allow non-differentiable functions and constraints into this framework, by generalizing gradients to sub-gradients.

[First-order $p$-CLI] An optimization algorithm is called a first-order $p$-Canonical Linear Iterative ($p$-CLI) optimization algorithm over a class of optimization problems $\mathcal{C}=(\mathcal{F},I(\cdot))$, if given an instance $f\in\mathcal{F}$ and an arbitrary set of $p$ initialization points ${\mathbf{x}}^{0}_{1},\dots,{\mathbf{x}}^{0}_{p}\in\text{dom}(\mathcal{C})$, it operates by iteratively generating points for which

holds, where the coefficients $A^{k}_{ij},B^{k}_{ij}$ are some linear operators which may depend on $I(f)$.

Formally, the expression $A^{(k)}_{ij}\partial f$ in (10) denotes the composition of $A^{(k)}_{ij}$ and the sub-gradient operator. Likewise, the r.h.s. of (10) is to be understand as an evaluation of sum of two operators $A^{(k)}_{ij}\partial f$ and $B^{(k)}_{ij}$ at ${\mathbf{x}}^{(k)}_{j}$.

In this level of generality, this framework encompasses very different kinds of optimization algorithms. We shall see that various assumptions regarding the coefficients complexity and side-information yield different lower bound on the iteration complexity.

We note that although this framework concerns algorithms whose update rules are based on a fixed number of points, a large part of the results shown in this paper holds in the case where $p$ grows indefinitely in accordance with the number of iterations.

We now turn to provide a formal definition of Iteration Complexity. We assume that the point returned after $k$ iterations is ${\mathbf{x}}_{p}^{(k)}$. This assumption merely serves as a convention and is not necessary for our bounds to hold.

The iteration complexity $\mathcal{IC}(\epsilon)$ of a given $p$-CLI w.r.t. a given problem class $\mathcal{C}=(\mathcal{F},I)$ is defined to be the minimal number of iterations $K$ such that

uniformly over $\mathcal{F}$, where the expectation is taken over all the randomness introduced into the optimization process (see Stochastic $p$-CLIs below).

For simplicity, when stating bounds in this paper, we shall omit the dependency of the iteration complexity on the initialization points. The precise dependency can be found in the corresponding proofs.

2 Classification of First-order p𝑝p-CLIs and Scope of Work

As mentioned before, we cannot say much about the framework in its full generality. In this paper, we restrict our attention to the following three (partially overlapping) classes of $p$-CLIs:

where the coefficients are allowed to depend exclusively on side-information (see Definition 3). In particular, the coefficients are not allowed to change with time. Seemingly restrictive, this class of $p$-CLIs subsumes many efficient optimization methods, especially when coupled with stochasticity (see below). Notable stationary $p$-CLIs are: GD with fixed step size , stationary AGD and the Heavy-Ball method .

where the coefficients are allowed to depend on side-information, as well as to change in time. Notable algorithms here are GD and AGD with step sizes which are scheduled irrespectively of the function under consideration and the Sub-Gradient Descent method (e.g., ).

Stochasticity is an efficient machinery of tackling optimization problems where forming the gradient is prohibitive, but engineering an efficient unbiased estimator is possible. Such situations occur frequently in the context of machine learning, where one is interested in minimizing finite sums of large number of convex functions,

in which case, forming a sub-gradient of $F$ at a given point may be too expensive. Notable optimization algorithms for variants of this problem are: SAG, SDCA without duality, SVRG and SAGA, all of which are stationary stochastic $p$-CLIs. Moreover, as opposed to algorithms which produce only one new point at each iteration (e.g., (4)), these algorithms sometimes update a few points at the same time. To illustrate this, let us express SAG as a stochastic stationary $(m+1)$-CLI. In order to avoid the computationally demanding task of forming the exact gradient of $F$ at each iteration, SAG uses the first $m$ points to store estimates for the gradients of the individual functions

At each iteration, SAG sets ${\mathbf{y}}_{i}=\nabla f_{i}({\mathbf{x}}^{(k)}_{m+1})$ for some randomly chosen $i\in[m]$, and then updates ${\mathbf{x}}^{(k)}_{m+1}$ accordingly, by making a gradient step with a fixed step size using the new estimate for $\nabla F({\mathbf{x}}^{(k)}_{m+1})$. This implies that the expected update rule of SAG is stationary and satisfies (11).

As opposed to an oblivious schedule of step sizes, many optimization algorithms set the step sizes according to the first-order information which is accumulated during the optimization process. A well-known example for such a non-oblivious schedule is conjugate gradient descent, whose update rule can be expressed as follows:

The algorithms mentioned above: conjugate gradient descent, coordinate descent and Newton methods; as well as other non-oblivious $p$-CLI optimization algorithms, such as quasi-Newton methods (e.g., ) and the ellipsoid method (e.g., ), will not be further considered in this paper.

Lower Bounds on the Iteration Complexity of Oblivious p𝑝p-CLIs

Having formally defined the framework, we are now in position to state our first main result. Perhaps the most common side-information used by practical algorithms is the strong-convexity and smoothness parameters of the objective function. Oblivious $p$-CLIs with such side-information tend to have low per-iteration cost and a straightforward implementation. However, this lack of adaptivity to the function being optimized results in an inevitable lower bound on the iteration complexity:

Suppose the smoothness parameter $L$ and the strong convexity parameter $\mu$ are known, i.e., $I(\cdot)=\{L,\mu\}$. Then the iteration complexity of any oblivious, possibly stochastic, $p$-CLI optimization algorithm is bounded from below by

As discussed in the introduction, Theorem 1 significantly improves upon the lower obtained by in 3 major aspects:

It holds for both smooth functions, as well as smooth and strongly convex functions.

It considers a much wider class of algorithms, namely, methods which may use different step size at each iteration and may freely update each of the $p$ points.

We stress again that, in contrast to (1), this lower bound does not scale with the dimension of the problem.

The proof of Theorem 1, including logarithmic factors and constants which appear in the lower bound, is found in (A.1), and can be roughly sketched as follows. First, we consider $L$-smooth and $\mu$-strongly convex quadratic functions of the form

Next, we observe that each iteration of $p$-CLI involves application of $A\partial f+B$, which is a linear expression in $\partial f$ whose coefficients are some linear operators, on the current points ${\mathbf{x}}^{(k)}_{j},~{}j=1,\dots,p$, which are then summed up to form the next iterate. Applying this argument inductively, and setting the initialization points to be zero, we see that the point returned by the algorithm at the $k$’th iteration can be expressed as follows,

from below. To this end, we use the properties of the well-known Chebyshev polynomials, by which we derive the following lower bound:

The proof of the smooth non-strongly convex case is also based on a reduction from a minimization problem to a polynomial approximation problem, only this time the resulting approximation problem is slightly different (see Equation (21) in Appendix A.2).

It is instructive to contrast our approach with another structural approach for deriving lower bounds which was proposed by . Nesterov considerably simplifies the technique employed by Nemirovsky and Yudin at the cost of introducing additional assumption regarding the way new iterates are generated. Specifically, it is assumed that each new iterate lies in the span of all the gradients acquired earlier. Similarly to , this approach also does not yield dimension-independent lower bounds. Moreover, such an approach may break in presence of conditioning mechanisms (which essentially, aim to handle poorly-conditioned functions by multiplying the corresponding gradients by some matrix). In our framework, such conditioning is handled through non-scalar coefficients. Thus, as long as the conditioning matrices depend solely on $\mu,L$ our lower bounds remain valid.

Side-Information in Oblivious Optimization

Below we discuss the effect of not knowing exactly the strong convexity parameter on the iteration complexity of oblivious $p$-CLIs. In particular, we show that the ability of oblivious $p$-CLIs to obtain iteration complexity which scales like $\sqrt{\kappa}$ crucially depends on the quality of the strong convexity estimate of the function under consideration. Moreover, we show that stationary $p$-CLIs are strictly weaker than general oblivious $p$-CLIs for smooth non-strongly convex functions, in the sense that stationary $p$-CLIs cannot obtain an iteration complexity of $\mathcal{O}(\sqrt{L/\epsilon})$.

The fact that decreasing the amount of side-information increases the iteration complexity is best demonstrated by a family of quadratic functions which we already discussed before, namely,

It is further shown that this lower bound is tight (see Appendix A in ). In Theorem 1 we show that if both the smoothness and the strong convexity parameters $\{\mu,L\}$ are known then the corresponding lower bound for this kind of algorithms is

As mentioned earlier, this lower bound is tight and is attained by a stationary version of AGD.

However, what if only the smoothness parameter $L$ is known a-priori? The following theorem shows that in this case the iteration complexity is substantially worse. For reasons which will become clear later, it will be convenient to denote the strong convexity parameter and the condition number of a given function $f$ by $\mu(f)$ and $\kappa(f)$, respectively.

Suppose that only $L$ the smoothness parameter is known, i.e. $I(\cdot)=\{L\}$. If the iteration complexity of a given oblivious, possibly stochastic, $p$-CLI optimization algorithm is

Theorem 2 pertains to the important issue of optimal schedules for step sizes. Concretely, it implies that, in the absence of the strong convexity parameter, one is still able to schedule the step sizes according to the smoothness parameter so as to obtain exponential convergence rate, but only to the limited extent of linear dependency on the condition number (as mentioned before, this sub-optimality in terms of dependence on the condition number, can be also found in and ). This bound is tight and is attained by standard gradient descent (GD).

Theorem 2 also emphasizes the superiority of standard GD in cases where the true strong convexity parameter is poorly estimated. Such situations may occur when one underestimate the true strong convexity parameter by following the strong convexity parameter introduced by an explicit regularization term. Specifically, if $\hat{\mu}$ denotes our estimate for the true strong convexity parameter $\mu$ (obviously, $\hat{\mu}<\mu$ to ensure convergence), then Theorem 1 already implies that, for a fixed accuracy level, the worst iteration complexity of our algorithm is on the order of $\sqrt{L/\hat{\mu}}$, whereas standard GD with $1/L$ step sizes has iteration complexity on the order of $L/\mu$. Thus, if our estimate is too conservative, i.e., $\hat{\mu}<\mu^{2}/L$, then the iteration complexity of GD is $\mu/\sqrt{L\hat{\mu}}\geq 1$ times better. Theorem 2 further strengthen this statement, by indicating that if our estimate does not depend on the true strong convexity parameter, then the iteration complexity of GD is even more favorable with a factor of $\mu/\hat{\mu}\geq 1$, compared to our algorithm.

The proof of Theorem 2, which appears in Appendix A.2, is again based on a reduction to an approximation problem via polynomials. In contrast to the proof of Theorem 1 which employs Chebyshev polynomials, here only elementary algebraic manipulations are needed.

Another implication of Theorem 2 is that the coefficients of optimal stationary $p$-CLIs for smooth and strongly convex functions must have an explicit dependence on the strong convexity parameter. In the next section we shall see that this fact is also responsible for the inability of stationary $p$-CLIs to obtain a rate of $\mathcal{O}(\sqrt{L/\epsilon})$ for $L$-smooth convex functions.

2 No Acceleration for Stationary Algorithms over Smooth Convex Functions

Below, we prove that, as opposed to oblivious $p$-CLIs, stationary $p$-CLIs (namely, $p$-CLIs with time-invariant coefficients) over $L$-smooth convex functions can obtain an iteration complexity no better than $\mathcal{O}(L/\epsilon)$. An interesting implication of this is that some current methods for minimizing finite sums of functions, such as SAG and SAGA (which are in fact stationary $p$-CLIs) cannot be optimal in this setting, and that time-changing coefficients are essential to get optimal rates. This further motivates the use of current acceleration schemes (e.g., ) which turn a given stationary algorithm into an non-stationary oblivious one.

The proof of this result is based on a reduction from the class of $p$-CLIs over $L$-smooth convex functions to $p$-CLIs over $L$-smooth and $\mu$-strongly convex, where the strong convexity parameter is given explicitly. This reduction allows us to apply the lower bound in Theorem 2 on $p$-CLIs designed for smooth non-strongly convex functions.

We now turn to describe the reduction in detail. In his seminal paper, Nesterov presents the AGD algorithm and shows that it obtains a convergence rate of

The following lemma provides an upper bound on the iteration complexity of $p$-CLIs obtained through Scheme 4.2.

The convergence rate of a $p$-CLI algorithm obtained by applying Scheme 4.2, using the corresponding set of parameters $L,\mu,C,\alpha$, is

where $\kappa=L/\mu$ denotes the condition number.

Proof Suppose $\mathcal{P}$ is a $p$-CLI as stated in Scheme 4.2 and let $f$ be a $L$-smooth and $\mu$-strongly convex function. Each external iteration in this scheme involves running $\mathcal{P}$ for $k=\sqrt[\alpha]{4CL/\mu}$ iterations, Thus, for any arbitrary point $\bar{{\mathbf{x}}}$,

Also, $f$ is $\mu$-strongly convex, therefore

That is, after each external iteration the sub-optimality in the objective value is halved. Thus, after $T$ external iterations, we get

where $\bar{{\mathbf{x}}}^{0}$ denotes some initialization point. Hence, the iteration complexity for obtaining an $\epsilon$-optimal solution is

The stage is now set to prove the statement made at the beginning of this section. Let $\mathcal{P}$ be a stationary $p$-CLI over $L$-smooth functions with a convergence rate of $\mathcal{O}{\left(L/k^{\alpha}\right)}$, and let $\mu\in(0,L)$ be the strong convexity parameter of the function to be optimized. We apply Scheme 4.2 to obtain a new $p$-CLI, which according to Lemma 1, admits an iteration complexity of $\mathcal{O}{\left(\sqrt[\alpha]{\kappa}\ln(1/\epsilon)\right)}$. But, since $\mathcal{P}$ is stationary, the resulting $p$-CLI under Scheme 4.2 is again $\mathcal{P}$ (That is, stationary $p$-CLIs are invariant w.r.t. Scheme 4.2). Now, $\mathcal{P}$ is a $p$-CLI over smooth non-strongly convex, and as such, its coefficients do not depend on $\mu$. Therefore, by Theorem 2, we get that $\alpha\leq 1$. Thus, we arrive at the following corollary:

If the iteration complexity of a given stationary $p$-CLI over $L$-smooth functions is

The lower bound above is tight and is attained by standard Gradient Descent.

Summary

In this work, we propose the framework of first-order $p$-CLIs and show that it can be efficiently utilized to derive bounds on the iteration complexity of a wide class of optimization algorithms, namely, oblivious, possibly stochastic, $p$-CLIs over smooth and strongly-convex functions.

We believe that these results are just the tip of the iceberg, and the generality offered by this framework can be successfully instantiated for many other classes of algorithms. For example, it is straightforward to derive a lower bound of $\Omega(1/\epsilon)$ for 1-CLIs over 1-Lipschitz (possibly non-smooth) convex functions using the following set of functions

How to derive a lower bound for other types of $p$-CLIs in the non-smooth setting is left to future work.

This research is supported in part by an FP7 Marie Curie CIG grant, the Intel ICRI-CI Institute, and Israel Science Foundation grant 425/13. We thank Nati Srebro for several helpful discussions and insights.

References

Appendix A Proofs

Let us apply the given oblivious $p$-CLI algorithm on a quadratic function of the form

Our next step is to reduce the problem of minimizing $f$ to a polynomial approximation problem. We claim that for any $k\geq 1$ and $i\in[d]$ there exist $d$ real polynomials $s_{k,i,1}(\eta),\dots,s_{k,i,d}(\eta)$ of degree at most $k-1$, such that

Let us prove this claim using mathematical induction. For $k=1$ we have

showing that the base case holds. For the induction step, assume the statement holds for some $k>1$ with $s_{k,i,j}(\eta)$ as above. Then,

The expression inside the last parenthesis is a vector with $d$ entries, each of which contains a real polynomial of degree at most $k$. This concludes the induction step (note that the derivations of equalities (18) and (A.1) above are exactly where we use the fact that there is no functional dependency of $A^{(k)}_{ij}$ and $B^{(k)}_{ij}$ on $\eta$).

By Lemma 2 in appendix B, there exists $\eta\in[\mu,L]$, such that

where $\kappa=L/\mu$. Defining $Q$ and ${\mathbf{q}}$ accordingly, and choosing, e.g., ${\mathbf{v}}=R{\mathbf{e}}_{1}$ where $R$ denotes a prescribed distance, yields

Using the fact that $f$ is $\mu$-strongly convex concludes the proof of the first part of the theorem.

Thus, choosing ${\mathbf{v}}=R{\mathbf{e}}_{1}$ concludes the proof.

A.2 Proof for Theorem 2

The proof of this theorem follows the exact reduction used in the proof of Theorem 1 (see Appendix A.1 above). The only difference is that here $\mu$ is allowed to be any real number in $(0,L)$. This consideration reduces our problem into, yet another, polynomial approximation problem. For completeness, we provide here the full proof.

Let us apply the given oblivious $p$-CLI algorithm on a quadratic function of the form

Our next step is to reduce the problem of minimizing $f$ to a polynomial approximation problem. We claim that for any $k\geq 1$ and $i\in[d]$ there exist $d$ real polynomials $s_{k,i,1}(\eta),\dots,s_{k,i,d}(\eta)$ of degree at most $k-1$, such that

Let us prove this claim using mathematical induction. For $k=1$ we have,

showing that the base case holds. For the induction step, assume the statement holds for some $k>1$ with $s_{k,i,j}(\eta)$ as above, then

The expression inside the last parenthesis is a vector with $d$ entries, each of which contains a real polynomial of degree at most $k$. This concludes the induction step. (note that the derivations of equalities (23) and (A.2) above are exactly where we use the fact that there is no functional dependency of $A^{(k)}_{ij}$ and $B^{(k)}_{ij}$ on $\eta$).

By Lemma 4, there exists $\eta\in(L/2,L)$, such that

Defining $Q$ and ${\mathbf{q}}$ accordingly, and choosing, e.g., ${\mathbf{v}}=R{\mathbf{e}}_{1}$ where $R$ denotes a prescribed distance, yields

Using the fact that $f$ is $L/2$-strongly convex concludes the proof.

Appendix B Technical Lemmas

Below, we provide 3 lemmas which are used to bound from below the quantity $|s(\eta)\eta+1|$ over different domains of $\eta$, where $s(\eta)$ is a real polynomial. For brevity, we denote the set of real polynomials of degree $k$ by $\mathcal{P}_{k}$.

Let $s(\eta)\in\mathcal{P}_{k}$, and let $0<\mu<L$. Then,

Proof Denote $q(\eta)\coloneqq T_{k+1}^{-1}\left(\frac{L+\mu}{L-\mu}\right)T_{k+1}\left(\frac{2\eta-\mu-L}{L-\mu}\right)$, where $T_{k}(\eta)$ denotes the Chebyshev polynomial of degree $k$,

It follows that $|T_{k+1}(\eta)|\leq 1$ for $\eta\in$ and

Accordingly, $|q(\eta)|\leq T_{k+1}^{-1}\left(\frac{L+\mu}{L-\mu}\right),~{}\eta\in[\mu,L]$ and

Suppose, for the sake of contradiction, that

Thus, for $r(\eta)=q(\eta)-(1+s(\eta)\eta))$, we have $r(\theta_{j})>0$ for even $j$, and $r(\theta_{j})<0$ for odd $j$. Hence, $r(\eta)$ has $k+1$ roots in $[\mu,L]$. But, since $r(0)=0$ and $\mu>0$, it follows $r(\eta)$ has at least $k+2$ roots, which contradicts the fact that the degree of $r(\eta)$ is at most $k+1$. Therefore,

where $\kappa=L/\mu$. Since $(\kappa+1)/(\kappa-1)\geq 1$, we have by Equation (27),

Let $s(\eta)\in\mathcal{P}_{k}$, and let $0<L$. Then,

where $T_{k}(\eta)$ is the $k$’th Chebyshev polynomial (see (27)). Let us show that $q(\eta)$ is a polynomial of degree $k+1$ and that $q(0)=1$. The following trigonometric identity

together with (27), yields the following recurrence formula

Noticing that $T_{0}(\eta)=1$ and $T_{1}(\eta)=x$ (also by (27)), we can use mathematical induction to prove that Chebyshev polynomials of odd degree have only odd powers and that the corresponding coefficient for the first power $\eta$ in $T_{2k+3}(\eta)$ is indeed $(-1)^{k}(2k+3)$. Equivalently, we get that $q(\eta)$ is a polynomial of degree $k+1$ and that $q(0)=1$. Next, note that for

Now, suppose, for the sake of contradiction, that

We proceed in a similar way to the proof of Lemma 2. For $r(\eta)=q(\eta)-(1+s(\eta)\eta))$, we have $r(\theta_{j})>0$ for even $j$, and $r(\theta_{j})<0$ for odd $j$. Hence, $r(\eta)$ has $k+1$ roots in $[\theta_{k+1},L]$. But, since $r(0)=0$ and $\theta_{k+1}>0$, it follows $r(\eta)$ has at least $k+2$ roots, which contradicts the fact that degree of $r(\eta)$ is a at most $k+1$. Therefore,

Let $s(\eta)\in\mathcal{P}_{k}$, and let $0<L$. Then exactly one of the two following holds:

For any $\epsilon>0$, there exists $\eta\in(L-\epsilon,L)$ such that

Proof It suffices to show that if (1) does not hold then $s(\eta)\eta+1=(1-\eta/L)^{k+1}$. Suppose that there exists $\epsilon>0$ such that for all $\eta\in(L-\epsilon,L)$ it holds that

and denote the corresponding coefficients by $q(\eta)=\sum_{j=0}^{k+1}q_{i}\eta^{j}$. We show by induction that $q_{j}=0$ for all $j=0,\dots,k$. For $j=0$ we have that since for any $\eta\in(0,1-(L-\epsilon)/L)$

Now, if $q_{0}=\dots=q_{m-1}=0$ for $m<k+1$ then

Thus, proving the induction claim. This, in turns, implies that $q(\eta)=q_{k+1}\eta^{k+1}$. Now, by Equation (28), it follows that $q_{k+1}=q(1)=1$. Hence, $q(\eta)=\eta^{k+1}$. Lastly, using Equation (28) again yields