The exact information-based complexity of smooth convex minimization

Keywords

Convex optimization; Complexity; Rate of convergence; Information-based complexity

Introduction

The problem of smooth and convex minimization plays a key role in a various range of applications, including signal and image processing, communications, machine learning, and many more. Some of the most successful approaches for solving these problems are first-order methods, i.e., algorithms that are only allowed to gain information on the objective by evaluating its value and gradient. The benefit of limiting the amount of accessible information is that these algorithms generally involve very cheap and simple computational iterations, making them suitable for tackling large scale problems. This benefit, however, comes with a price: first-order methods, in general, require considerable computational effort in order reach highly accurate solutions, making them practical when only moderate accuracy is sufficient.

As the scale of modern problems grows and finding efficient algorithms becomes increasingly important, a natural question that arises, and will be the main focus of this paper, is finding the level of accuracy that can be attained by first-order methods using a bounded computational effort. Note that there is some difficulty in answering this question that originates from the fact that the computational effort of a first-order method consists of two parts: the effort in choosing the points where the objective is to be evaluated (called the search points) and the effort in calculating the objective value and gradient at these points. Observing that the evaluation of the objective and its gradient often dominates the computational effort of the computation and following the theory of information-based complexity introduced in [nemirovsky1992information], we resolve this issue by measuring the computational effort of an algorithm by the number of times it evaluated the objective and its gradient, neglecting the effort required for choosing the search points.

To put these concepts in more precise terms, consider the following unconstrained problem

Within the setting considered above, a commonly used criterion for measuring the accuracy of an approximate solution is the absolute inaccuracy criterion, which quantifies the accuracy of an approximate solution $\xi$ for a problem instance $(\mathcal{O}_{f},x_{0})$ by the value of $f(\xi)-f^{*}$ (for alternative criteria see e.g., [nemirovski1999optimization, Section 3.3]). Under this criterion, the efficiency estimate of a first-order method $A$ over some given set of problem instances $\mathcal{I}$ is defined as the worst-case absolute inaccuracy of $A$, i.e.,

Note that the classical notion of information-based complexity of the set $\mathcal{I}$ can be identified as the inverse to the risk function,

i.e., the minimal computational effort needed by a first-order method in order to reach a given worst-case accuracy level, however, in the following we express our results using the minimax risk function as it proves to be more convenient.

Clearly, in order to establish an upper bound on the minimax risk of a class it is sufficient to find an upper bound on the efficiency estimate of a single first-order method (the main problem here being the identification of a good algorithm). On the other hand, establishing lower bounds on the minimax risk requires a more involved analysis, as the bound needs to hold for any first-order method. Several approaches appear in the literature for establishing lower-bounds, including resisting oracles [nemi-yudi-book83], construction of a “worst-case” function [Guzman20151, nest-book-04], and reduction to statistical problems [agarwal2012information, raginsky2011information, shapiro2005complexity].

Note that existing works on information-based complexity focus mainly on establishing order of magnitude bounds, where less attention is paid to absolute constants. Nevertheless, the exact minimax risk was established for several important classes of problem, some of which are detailed below.

Consider the problem of convex quadratic minimization:

It was established by Nemirovsky in [nemirovsky1992information, §2.3.B] that for $d\geq 2N+3$ exact minimax risk associated with this class is given by

Nemirovsky also shows in [nemirovsky1992information] that this bound is attained by the Tschebyshev Methods, and in a later work, that this bound is attained by the well-known and efficient Conjugate Gradient method (this is a somewhat forgotten result, see (5.4.22) in [nemirovski1999optimization], where unlike classical bounds on the Conjugate Gradient method, this bound does not depend on nontrivial spectral properties of $A$).

Another fundamental class of problems for which the exact minimax risk result is known is the class of non-smooth convex functions,

For this class, the exact minimax risk was recently established in [drori2014optimal], where it was shown that for $d\geq 2N+1$This bound can be improved to cover the case $d\geq N+1$, see Remark LABEL:R:nonsmoothex.

Note that this bound is obtained by several efficient methods, including the subgradient method [nest-book-04, §3.2.3] and also a family of methods recently studied in [drori2014optimal], which are similar to Kelley’s well-known Cutting-Plane Method.

In this paper we focus on the class of smooth convex functions with Lipschitz-continuous gradient:

which establishes the following upper bound on the minimax risk of smooth minimization:

Note that since $\sqrt{1+4\theta_{i-1}^{2}}=2\theta_{i-1}+o(1)$, then for $i<N$ we have $\theta_{i}=i/2+o(i)$ and

hence there exists a gap of about a factor of eight between the lower bound (1.1) and the upper bound (1.4). The main goal of this paper is to close this gap by showing that the bound (1.4) is in fact tight, i.e., the inequality (1.4) can be turned into an equality.

The approach taken by this paper is motivated by the “worst-case function” proof technique introduced in [nest-book-04] and the construction of smooth and convex functions developed in [Taylor2016].

Overview of the paper

The rest of this paper is organized as follows. We begin, in Section 2, by introducing a novel construction of smooth and convex functions that satisfy a given set of requirements on their value and gradient. We then use this construction, in Section LABEL:S:family, to define a function that possesses properties making it suitable for constructing lower bounds on the minimax risk function. Building on these results, in Section LABEL:S:lower, we establish the minimax risk associated with FL,R(Rd). Finally, in Section LABEL:S:concluding give some concluding remarks.

Notations

A smooth convex interpolation scheme

In this section, we describe a general construction of smooth and convex functions that satisfy a set of first-order requirements. This construction can be viewed as a generalized primal form of the interpolation scheme developed in [Taylor2016].

Note that the extra degree of freedom granted by the inclusion of the set $C$, although not necessary for the purpose of finding an interpolating function, will be crucial for establishing the properties of the worst-case function in the next section.

For later reference, we now state some immediate necessary and sufficient optimality conditions for the minimization problem $\hyperref@@ii[D:generalfamily]{W_{\mathcal{T}}^{C}}(y)$.

and for any $j,k\in I$ such that $\alpha^{*}_{j}>0$

Here $P_{C}$ denotes the projection onto the set $C$.

Condition (2.3) follows directly from the definition of the projection function, and condition (2.4) is the first-order optimality condition for $\alpha$. See for example [bertsekas1999nonlinear]. ∎

The main property of $\hyperref@@ii[D:generalfamily]{W_{\mathcal{T}}^{C}}(y)$ is summarized by the following theorem.

The function $\hyperref@@ii[D:generalfamily]{W_{\mathcal{T}}^{C}}(y)$ is convex and in $C^{1,1}_{L}$. Furthermore, $\hyperref@@ii[D:generalfamily]{W_{\mathcal{T}}^{C}}(x_{i})=f_{i}$ and $\nabla\hyperref@@ii[D:generalfamily]{W_{\mathcal{T}}^{C}}(x_{i})=g_{i}$ for any $i\in I$ that satisfies

Convexity. This follows from a well-known property of the infimum operator. See e.g., [rockafellar2009variational, Proposition 2.22].

Since $\hyperref@@ii[D:generalfamily]{W_{\mathcal{T}}^{C}}(y)$ is convex and defined over its entire domain, $\partial\hyperref@@ii[D:generalfamily]{W_{\mathcal{T}}^{C}}(y)$ is nonempty and we get that