Efficient First-order Methods for Convex Minimization: a Constructive Approach

Introduction

Convex optimization plays a central role in many fields of applications, including optimal control, machine learning and signal processing. In particular, when a large number of variables are involved within a convex optimization problem, the use of first-order methods is more and more widespread due to their typically very attractive low computational cost per iteration. This low computational cost comes, however, at a price: first-order methods often suffer from potentially slow convergence speeds, making them appropriate mostly for obtaining low to medium accuracy solutions. Nevertheless, first-order methods remain the methods of choice in many applications and currently receive a lot of attention from the optimization community, which constantly aims at improving them.

An effective and fruitful approach used for analyzing and comparing first-order methods is the study of their worst-case behavior through the black-box model. In this setting, methods are only allowed to gain information on the objective through an oracle, which provides the value and the gradient of the objective at selected points. Historically, this approach was largely motivated by the seminal work of Nemirovski and Yudin Book:NemirovskyYudin , and later by the work of Nesterov Book:Nesterov . These works established lower and upper bounds on the worst-case performances of first-order methods on several important classes of problems and initiated the search for optimal algorithms, which exhibit the best possible worst-case performances (up to a constant factor) for the class of problems they were designed to solve.

In this work, we consider the generic task of designing first-order methods for convex minimization. The suggested approach starts from a conceptual method that does not have an efficient implementation. Then, we show, from the analysis of this method, that one can construct efficient implementations that benefits from the same worst-case guarantees. This design approach has been considered several times in the past, see lemarechal1997variable ; nemirovski2004prox and many more. Here, unlike the alluded works, the chosen conceptual method is a very fundamental method capable of handling diverse families of problems, making the design approach applicable to a variety of settings. The conceptual algorithm we choose is a variant of the conjugate-gradient method, whose analysis therefore occupies an important place in the sequel.

A large number of generic techniques for developing optimization methods were proposed in the past years. Below we give a short overview of such techniques tailored for convex optimization; we do not attempt to give a comprehensive list.

One core idea underlying several classical optimization algorithms, and also strongly related to the technique proposed below, is the use of subspace-searches. Among them, conjugate gradient methods (see e.g., hestenes1952methods ; wright1999numerical ), which can be seen as methods performing minimization steps on increasingly larger subspaces, have a prominent place.

Related to that, the original optimal methods for smooth convex minimization, developed by Nemirovski and Yudin nemirovski1982orth ; nemirovski1983information (see e.g., the review in narkiss2005sequential ), requires two and three-dimensional subspace minimization at each iteration and is therefore reminiscent of subspace-search methods. For smooth convex minimization, those methods can be seen as predecessors to the celebrated Nesterov’s fast gradient method Nesterov:1983wy , which achieves the same optimal convergence rate without relying on those exact subspace minimizations steps. Motivated by similarities between the subspace-search methods of Nemirovski and Yudin nemirovski1982orth ; nemirovski1983information and Nesterov’s fast gradient method Nesterov:1983wy , we propose a generic technique which transforms subspace-search Conjugate Gradient-like methods to fixed-step methods that have equal or better worst-case performances. This technique was also premised in two previous works by the authors:

In (drori2016exact, , Remark 3.1), Drori remarked that the lower bound for smooth convex unconstrained minimization was achieved by a greedy method (referenced to as the ideal first-order method),

In (de2016worst, , Section 4.1), de Klerk et al. study the worst-case complexity of steepest descent with exact line search applied to strongly convex functions. As suggested by an anonymous referee in de2016worst , the worst-case certificates were also valid for the gradient method with an appropriate fixed-step size.

Links between fast gradient methods and conjugate gradient methods were also recently analyzed in karimi2016unified .

1.2 Links with fast gradient methods

Fast gradient schemes for minimizing smooth convex and smooth strongly convex functions originated in the seminal works of Nesterov Nesterov:1983wy ; Book:Nesterov (fast gradient methods), Polyak polyak1964some ; Book:polyak1987 (heavy-ball method) and Nemirovski and Yudin nemirovski1982orth ; nemirovski1983information . Despite its fundamental nature, acceleration remained an obscure phenomenon relying on an algebraic trick for years, and many authors have recently developed new explanations for this behavior. For smooth strongly convex minimization, recent popular works include geometrical approaches such as a shrinking ball scheme bubeck2015geometric , a new method based on lower quadratic approximations drusvyatskiy2016optimal , analyses relying on stability theory for discrete-time and/or continuous-time dynamical systems fazlyab2017analysis ; lessard2014analysis ; wilson2016lyapunov (specifically for fast gradient in hu2017dissipativity ), or even as a specific integration scheme of the gradient flow scieur2017integration . In the context of smooth convex minimization, another recent trend include parallels with differential equations su2014differential — some of the previous approaches for the smooth strongly convex case also apply without strong convexity.

1.3 Links with systematic and computer-assisted approaches to worst-case analyses

This work takes place within the current effort for the development of systematic/computer-guided analyses and design of optimization algorithms. Among them, a systematic approach to lower bounds (which focuses on quadratic cases) is presented in by Arjevani et al. in arjevani2016lower , a systematic use of control theory (via integral quadratic constraints) for developing upper bounds is presented by Lessard et al. in lessard2014analysis , and the performance estimation approach, which aims at finding worst-case bounds was originally developed in Article:Drori (see also surveys in drori2014contributions and taylor2017convex ).

Those methodologies are mostly presented as tools for performing worst-cases analyses (see the numerous examples in drori2014contributions ; hu2017dissipativity ; taylor2017convex ; taylor2015exact ; taylor2015smooth ; taylor2017pgm ), however, such techniques were also recently used to develop new methods with improved worst-case complexities. Among others, such an approach was used in Article:Drori ; kim2014optimized to devise a fixed-step method that attains the best possible worst-case performance for smooth convex minimization drori2016exact , and later in drori2014optimal to obtain a variant of Kelley’s cutting plane method with the best possible worst-case guarantee for non-smooth convex minimization. Also, the control-theoretic approach presented by Lessard et al. in lessard2014analysis was used in VanScoy2017 for developing a new accelerated method for smooth strongly convex minimization, called the triple momentum method.

2 Paper organization and main contributions

The paper is organized as follows. First, Section 2 introduces elementary facts and definitions that are used throughout this work. Then, Section 3 presents a specific variant of the conjugate gradient method, which we refer to as the Greedy First-Order Method (GFOM), along with the corresponding tools for analyzing it. Following that, Section 4 proposes a procedure for constructing fixed-step first-order methods that benefits from the same worst-case guarantees as that of GFOM. The procedure is applied on the class of non-smooth and smooth convex functions, and is shown to produce families of first-order methods achieving the best-possible worst-case bounds in both settings. Section 5 is devoted the strongly-convex case, where no analytical solution is known to the problem that arises from the design procedure. We show that the resulting numerically-defined algorithm attains both an efficient implementation and an improved worst-case bounds as compared to a standard fast gradient method of Nesterov (Book:Nesterov, , Section 2.2). Finally, we conclude and discuss extensions in Section 6.

3 Notations

resulting in the following useful identity: ${\langle x,y\rangle}_{A}={\operatorname{Tr}\left(A(x\odot y)\right)}$.

Basic definitions

This section briefly introduces some definitions that we use in the forthcoming analyses. We start by introducing, for the sake of convenience, a shorthand notation for the set of inputs expected by the algorithms under consideration. We continue by introducing a notation allowing us to implicitly define a function based on some local first-order information.

Let $\mathcal{F}$ be a class of c.c.p. functions. A set of triplets $S=\{(x_{i},g_{i},f_{i})\}_{i\in I}$ (for some index set $I$) is called $\mathcal{F}$-interpolable if there exists a function $f\in\mathcal{F}$ such that $g_{i}\in\partial f(x_{i})$ and $f_{i}=f(x_{i})$ for all $i\in I$.

For many classes of functions $\mathcal{F}$, the condition “$S$ is $\mathcal{F}$-interpolable” can be expressed as a finite set of constraints on the elements of $S$. In these cases, we refer to this set of constraints as interpolation conditions for the class $\mathcal{F}$. See taylor2015exact ; taylor2015smooth for a list of known interpolation conditions for different classes of functions, along with the corresponding proofs.

For the sake of completeness, we include below the interpolation conditions for the class of strongly-convex smooth functions and for the class of non-smooth convex functions. These classes are used in the examples presented in Sections 4 and 5.

Let $I$ be a finite index set and let $\operatorname{\mathcal{F}_{\mu,L}}$ denote the set of $L$-smooth and $\mu$-strongly convex functions for some $0\leq\mu<L\leq\infty$. A set $\{(x_{i},g_{i},f_{i})\}_{i\in I}$ is $\operatorname{\mathcal{F}_{\mu,L}}$-interpolable if and only if for all $i,j\in I$

Let $I$ be a finite index set and let $\mathcal{C}_{M}$ denote the set of Lipschitz c.c.p. functions whose gradient is bounded in norm by $M$ for some $0\leq M\leq\infty$. A set $\{(x_{i},g_{i},f_{i})\}_{i\in I}$ is $\mathcal{C}_{M}$-interpolable if and only if for all $i,j\in I$

Finally, we introduce the following technical property, which will be heavily used in establishing tightness results in the sequel.

we have that $\hat{S}=\{(\hat{x}_{i},g_{i},f_{i})\}_{i\in I}$ is $\mathcal{F}$-interpolable.

Two important examples of contraction preserving classes were discussed above, namely the class of smooth (possibly strongly) convex functions and the class of non-smooth convex functions.

The class of $L$-smooth, $\mu$-strongly convex functions $\mathcal{F}_{\mu,L}$ with $0\leq\mu<L\leq\infty$ is contraction preserving.

Let $I$ be some index set, let $S=\{(x_{i},g_{i},f_{i})\}_{i\in I}$ be a $\mathcal{F}_{\mu,L}$-interpolable set, and suppose $\hat{S}=\{(\hat{x}_{i},g_{i},f_{i})\}_{i\in I}$ with $\hat{x}_{i}$ satisfying (4). Then from Theorem 2.1, we have $\forall i,j\in I$:

hence $\hat{S}$ is $\mathcal{F}_{\mu,L}$-interpolable, as those inequalities are necessary and sufficient for smooth strongly convex interpolation (see Theorem 2.1). ∎

The class of c.c.p. functions with $M$-bounded gradients $\mathcal{C}_{M}$ with $0\leq M\leq\infty$ is contraction preserving.

Let $S=\{(x_{i},g_{i},f_{i})\}_{i\in I}$ be a $\mathcal{C}_{M}$-interpolable set and suppose $\hat{S}=\{(\hat{x}_{i},g_{i},f_{i})\}_{i\in I}$ with $\hat{x}_{i}$ satisfying (4). Since the interpolation conditions (3) hold for $S$, it immediately follows from the equality relations in (4) that these interpolation conditions also hold for $\hat{S}$, concluding the proof. ∎

Analysis of a greedy first-order method

The goal of this section is to introduce a framework for studying the worst-case performance of the following subspace-search based greedy method, reminiscent of conjugate gradient methods.

GFOM clearly becomes intractable after the first few iterations; nevertheless, a few fundamental theoretical properties render its analysis interesting independently of the focus of the following sections. One such property is that GFOM attains the best possible behavior that can be achieved by a first-order method on functions that have a form similar to the “worst function in the world” introduced by Nesterov Book:Nesterov (as a way of establishing lower-complexity bounds). GFOM is therefore a natural candidate when looking for “the best algorithm in the world”. Additionally, GFOM can be seen as a generalization of the Conjugate Gradient method hestenes1952methods which remains a very fruitful field of study to this day.

Note that the iteration rule (5) is not well-defined when the function $f$ does not attain its infimum on the provided subspace. In such cases, GFOM cannot proceed and we say that it does not yield an output. For cases where (5) is well-defined, note that by the first-order optimality conditions, a choice for $f^{\prime}(x_{i})$ that satisfies the (Conjugate Gradient like) conditions (6) necessarily exists, and in particular, when $f$ is differentiable at $x_{i}$ these requirements are fulfilled by the gradient of $f$ at $x_{i}$.

The analysis below is based on the performance estimation methodology which was first introduced in Article:Drori and has been successfully applied to analyze methods in a wide range of settings, including smooth and nonsmooth minimization drori2014optimal ; kim2014optimized ; kim2015convergence ; taylor2015smooth , proximal gradient methods taylor2015exact ; taylor2017pgm , saddle-point problems drori2014contributions and more recently to operator splitting methods ryu2018operator . Here we build upon an approach developed for the analysis of line-searching methods de2016worst , and improve it by providing a tightness proof under some mild conditions.

Clearly, a meaningful analysis can only be attained by making some assumptions on the structure of the problem: namely, that $f$ belongs to some given class of functions $\mathcal{F}$ and that the initial point $x_{0}$ satisfies some conditions. In the sequel we restrict our attention to the standard initial condition on ${\left\lVert x_{0}-x_{*}\right\rVert}$, which we assume to be bounded by some constant $R_{x}>0$ (see Definition 1). In addition, we evaluate the performance of a method in terms of its worst-case absolute inaccuracy $f(x_{N})-f_{*}$. In other words, we are looking for worst-case guarantees of type

with $\tau\geq 0$ being as small as possible. Note that the presented analysis allows for more general initial conditions and performance measures (see discussions in (nemirovsky1992information, , Section 4), and more specifically in (taylor2017pgm, , Section 4) in the context of performance estimation), however, for the sake of simplicity we do not pursue this direction in this work.

We start the analysis of GFOM with the observation that, under the assumptions discussed above, the worst-case performance of GFOM is by definition the optimal value to the following performance estimation problem (PEP):

As an immediate consequence of the definition of (PEP), if $(f,x_{0})$ is such that $f\in\mathcal{F}$ and ${\left\lVert x_{0}-x_{*}\right\rVert}\leq R_{x}$ (for some $x_{*}\in\operatorname*{argmin}_{x}f(x)$) then the following bound hold:

Although the form (PEP) appears at first to be a purely theoretical notational reformulation, it provides a convenient framework for manipulating the problem in a way that will eventually yield a tractable bound on the worst-case performance of GFOM.

As a first step for obtaining tractable bounds we formulate (PEP) as a finite-dimensional optimization problem.

Furthermore, if $\mathcal{F}$ is contraction-preserving (see Definition 3) then the bound (8) is tight, i.e., for any $\varepsilon>0$ there exists an $(\mathcal{F},R_{x})$-input $(\hat{f},\hat{x}_{0})$, such that

In surprisingly many situations, the constraint ‘$\{(x_{i},g_{i},f_{i})\}_{i\in I^{*}_{N}}\text{ is }\mathcal{F}\text{-interpolable}$’ in (PEP-GFOM) can be expressed as a finite set of inequalities that depend on the $\{(x_{i},g_{i},f_{i})\}_{i\in I^{*}_{N}}$ variables via linear combinations of $\{f_{i}\}_{i\in I^{*}_{N}}$ and inner products of the vectors $\{(x_{i},g_{i})\}_{i\in I^{*}_{N}}$ (for example, see (2) and (3) for the $\operatorname{\mathcal{F}_{\mu,L}}$ and $\mathcal{C}_{M}$ classes, respectively). In these cases, (PEP-GFOM) becomes a quadratically constrained quadratic program (QCQP), which has efficient SDP relaxations beck2007quadratic ; beck2012new . We now consider such cases, and provide sufficient conditions under which these relaxations are exact.

2 A tractable bound on the worst-case performance of GFOM

which are defined such that $x_{i}-x_{0}=P(\mathbf{x}_{i}-\mathbf{x}_{0})$, $g_{i}=P\mathbf{g}_{i}$ and $f_{i}=F\mathbf{f}_{i}$. Using these notations together with the notations defined in Section 1.3, the following reformulations hold:

(The notation ic above is an abbreviation of interpolation conditions.)

for all $(i,j)\in K_{N}$ (see Theorem 2.1).

We can now formulate a tractable performance estimation problem for GFOM.

Furthermore, if $d\geq 2N+2$ then (12) holds with equality.

Since any feasible solution $\{(x_{i},g_{i},f_{i})\}_{i\in I^{*}_{N}}$ to (PEP-GFOM) can be transformed to a feasible solution to (sdp-PEP-GFOM), by setting $G=P^{\top\!}P$, where $P$ is defined as in (9), then (12) immediately follows.

Now, suppose $d\geq 2N+2$ and let $(F,G)$ be feasible to (sdp-PEP-GFOM). Since $G$ is a $(2N+2)\times(2N+2)$ positive-semidefinite matrix, there exits some $d\times(2N+2)$ matrix $P$ such that $G=P^{\top\!}P$, and thus $(F,G)$ can be transformed to a feasible solution for (PEP-GFOM) by assigning values for $\{(x_{i},g_{i},f_{i})\}_{i\in I^{*}_{N}}$ according to (9). We have obtained

We now describe the final form of the bound on the performance of GFOM, which is the standard Lagrangian dual of (sdp-PEP-GFOM). This bound provides the basic building block for SSEP.

The first part of the claim follows directly by establishing weak duality between (dual-PEP-GFOM) and (sdp-PEP-GFOM). Indeed, one can use the following association between the constraints and dual variables along with the definition of Lagrange duality:

The proof for the tightness claim is presented in Appendix B. ∎

Since (dual-PEP-GFOM) is an infimum problem, it has the useful property that any feasible solution to this problem corresponds to an upper bound on the worst-case accuracy of GFOM. We take advantage of this property in the following, where bounds on the performance of GFOM for different classes of problems are established by providing a (dual-PEP-GFOM)-feasible solution.

with $x_{0}=0$ (where $e_{i}$ are the canonical unit vectors). For more details, see (drori2014optimal, , Appendix A).

To conclude this section, we note that although the analysis above was performed under Assumption 3.2, for classes of functions for which a set of interpolation conditions is either unknown or complex, the analysis can still proceed using a set of necessary conditions for interpolability, with the only change being that tightness claims no longer apply.

The subspace-search elimination procedure

In this section, we introduce a technique for constructing first-order methods with a worst-case absolute inaccuracy that is guaranteed to be not worse than that of GFOM. We begin by stating the main technical result, we then outline the SSEP technique, and finally demonstrate the application of the technique on several cases.

The proof, presented in Appendix C, is based on the observation that by carefully aggregating the constraints in (dual-PEP-GFOM), it is possible to reach a PEP for methods satisfying (25) without adversely affecting the optimal value of the PEP.

Based on this result, the design procedure can be summarized as follows.

Subspace-search elimination procedure (SSEP)

Theorem 4.1 states that any point feasible to (dual-PEP-GFOM) can be used as a basis for constructing new methods with worst-case performances that are bounded by the value of the objective at that feasible point. In particular, this applies to an optimal solution of (dual-PEP-GFOM), hence in cases where (dual-PEP-GFOM) attains the worst-case performance of GFOM (e.g., under the tightness conditions in Theorem 3.1), the worst-case performance of any method constructed according to (25) from an optimal solution is guaranteed to be equal to or better than the worst-case performance of GFOM.

Equality (25) can be enforced in different ways. Perhaps the most straightforward one by an appropriate fixed-step size policy as detailed below.

In addition to the fixed-step method defined in Corollary 1, there are additional strategies for enforcing (25), where, in particular, the iterates of GFOM satisfy these equalities. As described in the examples below, this flexibility allows the construction of methods that have additional properties, such as independence on problem parameters (e.g., Lipschitz constants or initial distance to optimality $R_{x}$).

Consider the problem of minimizing a non-smooth convex function

We start the SSEP by establishing a worst-case bound on GFOM in this case. As discussed above, for this purpose it is sufficient to find a dual feasible solution to (PEP-GFOM) when the interpolation conditions used matches the class of functions under consideration.

The following assignment is feasible to (dual-PEP-GFOM) under the interpolation conditions for $\mathcal{C}_{M}$ defined in Example 2, and attain the objective value of $\frac{MR_{x}}{\sqrt{N+1}}$:

where all the other optimization variables in (dual-PEP-GFOM) are set to zero.

For the sake of coherence, the following proof relies on the SDP formalism developed above. One can note, though, that it is possible to reformulate the proof below using equivalent sum-of-squares arguments.

Since the inequality constraint in (dual-PEP-GFOM) clearly holds for (27), it is enough to verify the positive-semidefinite constraint and the equality constraint, i.e.:

The first condition can be verified by showing that it is equal to the following positive-semidefinite rank-one matrix (this may require some work to obtain directly, but can easily be verified by developing both expressions):

The equality is straightforward to verify. Finally, the objective value is given by

The following is now immediate from Theorem 3.1, Proposition 2 and Theorem 4.1.

Let $(f,x_{0})$ be a $(\mathcal{C}_{M},R_{x})$-input for some $M,R_{x}\geq 0$.

Furthermore, this bound is tight when $d\geq 2N+2$.

For any sequence $x_{1},\dots,x_{N}$ that satisfies

As noted above, sequences satisfying (28) can be generated in several ways. We start by describing an efficient implementation of the fixed-step scheme described in Corollary 1.

The claim then follows directly from the second part of Corollary 2.∎

Note though that the SSEP-based subgradient method has a guarantee on its last iterate, whereas the guarantees on standard subgradient methods are usually either on the averaged iterate $f\left(\frac{1}{N+1}\sum_{i=0}^{N}x_{i}\right)-f_{*}$ or in terms of the best iterate $\min_{0\leq i\leq N}f(x_{i})-f_{*}$. Interestingly, the SSEP-based subgradient method appears to be similar to the so-called quasi-monotone subgradient methods nesterov2015quasi .

As noted above, there are additional ways of enforcing equality (25), allowing the introduction of methods with different properties. As an example, one can subsume prior knowledge of the constants $R_{x}$, $M$ and $N$ by using an exact line search procedure, as demonstrated by the following optimal subgradient method.

SSEP-based subgradient method with an exact line search

Let $(f,x_{0})$ be an $(\mathcal{C}_{M},R_{x})$-input for some $M,R_{x}\geq 0$. For any sequence $\{x_{i}\}$ generated by SSEP-based subgradient method with an exact line search given $f$ and $x_{0}$

First, note that from the first-order optimality conditions on the exact line search procedure, for all $i$ there exist $f^{\prime}(x_{i})\in\partial f(x_{i})$ that satisfies the requirement ${\langle f^{\prime}(x_{i}),d_{i}\rangle}=0$. Now, from definition of $x_{i}$ and $y_{i}$, we have

which concludes the proof, since this establishes (28) as required by Corollary 2. ∎

In the setting considered in this section, it is known that no first-order method can have a worst-case absolute inaccuracy behavior that better than

after $N$ iterations when $d\geq N+2$ (drori2014optimal, , Theorem 2), hence the subgradient algorithms described above are optimal and the corresponding bounds are tight.

Note that the methods developed above are not the first subgradient schemes that attains the optimal worst-case complexity for non-smooth minimization, as it is achieved, for example by the optimal step-size policy $\frac{R_{x}}{M\sqrt{N+1}}$ proposed in (Book:Nesterov, , Section 3.2.3) and by the Kelley-like cutting plane method developed in drori2014optimal .

2 Example: smooth convex minimization

In this section we demonstrate the application of SSEP on the problem of minimizing a smooth convex function. We show that GFOM attains the best possible worst-case bound on this problem, and that the resulting fixed-step method is the optimized gradient method (OGM) developed in Article:Drori ; kim2014optimized . Finally, we construct a method that has the same worst-case performance, but does not require prior knowledge on the problem parameters, at the cost of performing a one-dimensional line search at each iteration.

The following assignment is feasible to (dual-PEP-GFOM) under the interpolation conditions for $\mathcal{F}_{0,L}$ defined in Example 1, and attains the objective value of $\frac{LR_{x}^{2}}{2\theta_{N,N}^{2}}$:

where all the other optimization variables in (dual-PEP-GFOM) are set to zero.

As in the non-smooth case, it is enough to show that the following constraints hold:

With some effort, one can show that the first expression above can be written as:

which is clearly a PSD matrix. As the second equality above also holds, it follows that the selected values define a feasible point. Finally, the objective value that corresponds to that point is given by

From Theorem 3.1 Proposition 1 and Theorem 4.1 we get the following result.

Let $(f,x_{0})$ be an $(\operatorname{\mathcal{F}_{0,L}},R_{x})$-input for some $L,R_{x}\geq 0$.

Furthermore, this bound is tight when $d\geq 2N+2$.

For any sequence $x_{1},\dots,x_{N}$ that satisfies

As an immediate application of Corollary 1, we recover the optimized gradient method (OGM), which was developed in Article:Drori ; kim2014optimized .

Optimized gradient method (OGM) kim2014optimized

As in the non-smooth case, one can trade the knowledge of the problem parameters with an exact line search procedure, resulting in an optimized gradient method with exact line search.

Optimized gradient method with exact line search (OGM-LS)

We omit the rate of convergence proofs, as they are identical to the proofs presented in the previous section. As in the non-smooth case, tightness of the worst-case bounds can be established by observing that they coincide with the lower complexity bound for the problem (drori2016exact, , Corollary 4) and therefore they cannot be improved in the large-scale setting ($d\geq N+2$).

Before proceeding, let us note that the results above are reminiscent to the historical developments premising accelerated methods. Indeed, acceleration was first discovered in the work of Nemirovski and Yudin nemirovski1982orth ; nemirovski1983information , who needed two or three-dimensional subspace-searches for obtaining the optimal convergence rate for smooth convex minimization. This rather strong requirement was removed later on in the work of Nesterov, resulting in the first version of the celebrated fast gradient method Nesterov:1983wy not requiring any line (or space) search.

3 Example: a universal method for non-smooth and smooth convex minimization

In this short section, we build upon the results of Section 4.1 and Section 4.2 to develop a universal method for both smooth and non-smooth minimization, i.e., a method that does not require any knowledge on which of the two classes the function belongs to, nor does it require knowledge on the specific parameters of the classes. The knowledge is replaced by the capability of performing exact three-dimensional subspace minimizations.

A universal method for non-smooth and smooth minimization (UM)

If $(f,x_{0})$ is an $({\mathcal{C}_{M}},R_{x})$-input for some $M\geq 0$, then

If $(f,x_{0})$ is an $(\operatorname{\mathcal{F}_{0,L}},R_{x})$-input for some $L\geq 0$, then

For the first part of the claim, it is enough to establish that the sequence generated by UM satisfies (28). Indeed, for $i=1,\dots,N$

where the last equality follows from the optimality conditions of the exact subspace minimization step:

The second part of the claim follows in an analogous way using (30).∎

Numerical construction of efficient methods

In this section we focus our attention to situations where either (dual-PEP-GFOM) does not have a known analytical solution, or the analytical solution is too complex for practical purposes. In particular, we examine the performance of the methods generated by SSEP in the case where $f\in\mathcal{F}_{\mu,L}$ (an $L$-smooth, $\mu$-strongly convex function). Note that since $f\in\operatorname{\mathcal{F}_{\mu,L}}$ implies $\frac{1}{L}f\in\mathcal{F}_{\frac{\mu}{L},1}$, the worst-case analyses can be limited to the case $L=1$, where simple homogeneity arguments allow extending the results to the case of arbitrary $L>0$. For a short discussion on this topic, we refer to (taylor2017convex, , Section 4.2.5).

As discussed above, one can observe that optimal solutions to (dual-PEP-GFOM) often enjoys certain advantageous structural properties. In particular, in the case of smooth strongly convex optimization, instances of the SSEP method fit the form (LABEL:eq:algo_eff_form2) below within high accuracy levels. Note that the form (LABEL:eq:algo_eff_form2) is a straightforward generalization of OGM, which is the SSEP method derived for the non-strongly convex case, $\mu=0$, established in Section 4.2 (see e.g. (kim2014optimized, , Section 7.1)).

SSEP-based gradient method for smooth strongly convex minimization

Now, assuming that both implementations (31) and (LABEL:eq:algo_eff_form2) describe the same algorithm, we have, in particular, $h_{i,i-1}=h_{i,i-1}^{\prime}$ and $h_{i,i-2}=h_{i,i-2}^{\prime}$. As a result, one can identify candidate values for $\eta_{i}$ and $\zeta_{i}$ as follows:

where we also arbitrarily set $\zeta_{0}=0$. Finally, one can numerically verify that $h_{i,j}\approx h_{i,j}^{\prime}$ indeed holds for all $i,j$ by generating the full set $\{h_{i,j}^{\prime}\}$ using (33) and the candidate values $\{(\eta_{i},\zeta_{i})\}$.

The numerical values of $\{(\eta_{i},\zeta_{i})\}$ derived in the case of $N=10$ for a few values of $\kappa$’s are reported in Table 1. Since the approach is limited by our capability to accurately solve SDPs, it is important to note that PEPs can be used again for validating the performances of the final method (shown in the one before last row in Table 1).

Figure 1 presents a comparison of the worst-case bounds in the case $\kappa=100$ for GFOM, for an SSEP-based method performing no line searches, the celebrated fast (or accelerated) gradient method (FGM) for smooth strongly convex minimization (Book:Nesterov, , Theorem 2.1.12), and the very recent triple momentum method (TMM) VanScoy2017 . These worst-case bounds were derived numerically by solving the corresponding PEPs using the interpolation conditions presented in Example 1 (see Article:Drori ; taylor2015smooth for details on the derivation of PEPs for fixed-step methods). Note that the bound for the SSEP method was generated for the form (31); bounds for the efficient form (LABEL:eq:algo_eff_form2) behave almost exactly like the bounds for the form (31)—the difference could not be observed from this plot—and were therefore omitted from the comparison.

Finally, the numerical results presented above support the conjectures that the subspace-searching GFOM enjoys an $O((1-\sqrt{2}\sqrt{\kappa^{-1}})^{N}R_{x}^{2})$ rate of convergence while the SSEP-based method that does not perform any line searches, converges at the faster rate $O((1-2\sqrt{\kappa^{-1}})^{N}R_{x}^{2})$ (matching the rate of convergence bounds on TMM (VanScoy2017, , Theorem 1)). This is not in contraction with the theory, as noted in Remark 3, however, we are currently unable to find an intuitive explanation to this phenomenon besides the algebraic observation that the PEPs corresponding to the methods (31) and (LABEL:eq:algo_eff_form2) have less degrees of freedom than the PEP for GFOM.

Conclusion

The main goal of this work is to provide a systematic and efficient approach for designing first-order optimization algorithms. The contribution is essentially threefold: first, we extend the performance estimation framework for obtaining worst-case guarantees for a greedy method that performs arbitrary subspace searches, and show that the generated guarantees are tight in the large-scale setting under some weak assumptions. Then, we describe a methodology for systematically designing fixed-step methods that share the same worst-case guarantees as the subspace searching greedy method. Finally, based on the new methodology, we derive optimal methods for non-smooth and smooth convex minimization and versions of these methods that do not require prior knowledge of the problem parameters.

As illustrated in Section 5, the methodology can also serve in cases where numerical results cannot easily be converted to practical analytical optimization schemes. For example, for real-time embedded optimization diehl2009efficient , where it is acceptable to spend some time performing pre-computations in order to more efficiently perform simple repetitive routines.

Direct extensions of the approach include considering additional families of functions and oracles, such as composite functions involving proximal terms and projections beck2009fast ; nesterov2007gradient , inexactness de2016worst ; devolder2013intermediate ; devolder2014first ; schmidt2011convergence , stochastic oracles arising in finite sums defazio2014saga ; johnson2013accelerating ; roux2012stochastic , or block-coordinate descent nesterov2012efficiency ; wright2015coordinate . Even further extensions include considering additional variants of the greedy method, e.g., using alternative optimality criteria, as the distance to an optimal point.

All the worst-case performance analyses presented above were numerically validated using the pesto toolbox taylorperformance . The code for reproducing the worst-case guarantees is available at

https://github.com/AdrienTaylor/GreedyMethods

Numerical experiments were produced using cvx and yalmip grant2008cvx ; Article:Yalmip along with MOSEK Article:Mosek .

Appendix A Proof of Lemma 1

We start the proof of Lemma 1 with the following a technical lemma.

Let $\mathcal{F}$ be a class of contraction-preserving c.c.p. functions (see Definition 3), and let $S=\{(x_{i},g_{i},f_{i})\}_{i\in I^{*}_{N}}$ be an $\mathcal{F}$-interpolable set satisfying

By (34) and (35) it then follows that for all $k\geq i$

hence, together with the definition of $v_{i}$, we get

Let us now choose $\{\hat{x}_{i}\}_{i\in I^{*}_{N}}$ as follows:

It follows immediately from this definition that (37) holds, it thus remains to show that $\hat{S}$ is $\mathcal{F}$-interpolable and that (36) holds.

In order to establish that $\hat{S}$ is $\mathcal{F}$-interpolable, from Definition 3 it is enough to show that the conditions in (4) are satisfied. This is indeed the case, as ${\langle g_{j},\hat{x}_{i}-\hat{x}_{0}\rangle}={\langle g_{j},x_{i}-x_{0}\rangle}$ follows directly from definition of $\{\hat{x}_{i}\}$ and (38), whereas ${\left\lVert\hat{x}_{i}-\hat{x}_{j}\right\rVert}\leq{\left\lVert x_{i}-x_{j}\right\rVert}$ in the case $i,j\neq*$ follows from

where for the second equality we used ${\langle v_{i},r_{*}\rangle}=0$. The last inequality also establishes (36), which completes the proof. ∎

hence the problem (PEP) can be equivalently expressed as follows:

Now, since all constraints in (39) depend only on the first-order information of $f$ at $\{x_{i}\}_{i\in I^{*}_{N}}$, by taking advantage of Definition 2 we can denote $f_{i}:=f(x_{i})$ and $g_{i}:=f^{\prime}(x_{i})$ and treat these and as optimization variables, thereby reaching the following equivalent formulation

Since (PEP-GFOM) is a relaxation of (40), we get

Indeed, by the definition of (PEP-GFOM), there exists a set $S=\{(x_{i},g_{i},f_{i})\}_{i\in I^{*}_{N}}$ that satisfies the constraints in (PEP-GFOM) and reaches an objective value $f_{N}-f_{*}\geq\operatorname{val}\eqref{gfom_dPEP}-\varepsilon$. Since $S$ satisfies the requirements of Lemma 5 (as these requirements are constraints in (PEP-GFOM)), there exists a set of vectors $\{\hat{x}_{i}\}_{i\in I^{*}_{N}}$ for which

Furthermore, since $g_{*}=0$ we have that $\hat{x}_{*}$ is an optimal solution of $\hat{f}$.

We conclude that the sequence $\hat{x}_{0},\dots,\hat{x}_{N}$ forms a valid execution of GFOM on the input $(\hat{f},\hat{x}_{0})$, that the requirement ${\left\lVert\hat{x}_{0}-\hat{x}_{*}\right\rVert}\leq R_{x}$ is satisfied, and that the output of the method, $\hat{x}_{N}$, attains the absolute inaccuracy value of $\hat{f}(\hat{x}_{N})-\hat{f}(\hat{x}_{*})=f_{N}-f_{*}\geq\operatorname{val}\eqref{gfom_dPEP}-\varepsilon$.

Appendix B Proof of Theorem 3.1

Let $(f,x_{0})$ be a pair satisfying the premise of the lemma and denote by $\{x_{i}\}_{i\geq 0}$ the sequence generated according to GFOM and by $\{f^{\prime}(x_{i})\}_{i\geq 0}$ the subgradients chosen at each iteration of the method, respectively. By the assumption that the optimal value is not obtained after $2N+1$ iterations, we have $f(x_{2N+1})>f_{*}$.

corresponds to a Slater point for (sdp-PEP-GFOM).

established by Lemmas 1 and 2. The tightness claim follows from the tightness claims of Lemmas 1, 2 and 6. ∎

Appendix C Proof of Theorem 4.1

We begin the proof of Theorem 4.1 by recalling a well-known lemma on constraint aggregation, showing that it is possible to aggregate the constraints of a minimization problem while keeping the optimal value of the resulting program bounded from below.

Before proceeding with the proof of the main results, let us first formulate a performance estimation problem for the class of methods described by (25).

for some $f^{\prime}(x_{i})\in\partial f(x_{i})$, the following bound holds:

We omit the proof since it follows the exact same lines as for (sdp-PEP-GFOM) (c.f. the derivations in Article:Drori ; taylor2015smooth ).

The key observation underlying the proof is that by taking the PEP for GFOM (sdp-PEP-GFOM) and aggregating the constraints that define its iterates, we can reach a PEP for the class of methods (25). Furthermore, by Lemma 7, this aggregation can be done in a way that maintains the optimal value of the program, thereby reaching a specific method in this class whose corresponding PEP attains an optimal value that is at least as good as that of the PEP for GFOM.

References