On the oracle complexity of smooth strongly convex minimization

Introduction

In this paper, we study the performance of deterministic first-order methods for approximating the solution of unconstrained strongly-convex minimization problems, i.e., problems of the form

This problem setting has the attractive property that first-order methods for solving it are simple, scalable and easy to implement, nevertheless they enjoy ‘fast’ rates of convergence [nest-book-04], making highly-accurate solutions relatively easy to attain. As a result, these problems are considered ‘tractable’ and play a key role in a wide range of applications, from machine learning, parameter estimation, computer vision and many more. These types of problems also appear as steps in methods for solving more complex problems, a property which makes efficient solutions of these problems even more important.

where here and through the rest of the paper $\|\cdot\|$ stands for the Euclidean norm. This rate of convergence has been improved by the celebrated Accelerated Gradient Methods [nest-book-04], which generates a sequence of iterates converging to an optimal point at rate in the order of $O((1-\sqrt{\mu/L})^{N/2})$. Recently, the Triple Momentum Method [van2017fastest] improved this rate even further: after $N$ iterations the method attains an approximate solution $x_{N}$ such that

An additional improvement is due to the very recent Information-Theoretic Exact Method [taylor2021optimal], which further improves the leading constant in the bound above. This progress naturally raises the question: can we do even better?

In this work, we consider two criteria for measuring the inaccuracy of an approximate solution: absolute inaccuracy, which quantifies the inaccuracy of an approximate solution $\xi$ for a problem instance $(\mathcal{O}_{f},x_{0})$ by the value of $f(\xi)-f^{*}$, and the distance to the solution set which measures the inaccuracy of approximate solution $\xi$ by $\inf_{x_{*}\in X_{*}(f)}\|\xi-x_{*}\|$, where $X_{*}$ denotes the set of optimal solutions. The efficiency estimate of a first-order method $A$ over a given set of problem instances $\mathcal{I}$ is then defined as the worst-case value of the chosen inaccuracy measure. For the absolute inaccuracy measure we denote

and for the distance to the solution set, we denote

We can now put the main concepts addressed in this paper in formal terms: denoting by $\mathcal{A}_{N}$ the set of all deterministic first-order methods that perform at most $N$ calls to their first-order oracle, the minimax risk [Guzman20151] associated with $\mathcal{I}$ is defined as the infimal efficiency estimate that a method in $\mathcal{A}_{N}$ can attain over $\mathcal{I}$ as a function of the computational effort $N$

Similarly, for the distance to the solution set inaccuracy measure, we define the minimax error by

The classical notion of oracle (or information-based) complexity of the set $\mathcal{I}$ can now be identified as the inverse to the functions defined above, i.e., the minimal computational effort needed by a first-order method in order to reach a given worst-case accuracy level. For example, under the absolute inaccuracy measure, the oracle complexity of $\mathcal{I}$ is given by

In the following, we express our results using the minimax risk and minimax error functions as they prove to be better suited for expressing the dependence of the results on the dimension of the domain.

In this paper we focus on the class of strongly convex functions with Lipschitz-continuous gradient, where the initial point is assumed to be at bounded distance from an optimal point:

Lower bounds on the minimax risk and minimax error for this class of problems were derived by Nemirovski [nemirovsky1991optimality, nemirovsky1992information] and Nesterov [nest-book-04, Theorem 2.1.13]

and were shown to be optimal in the sense that the number of steps required to reach a certain accuracy matches the upper bound up to a constant. Nevertheless, a gap yet remains between the convergence rates of the upper and lower bounds, which is the purpose of this paper to close. Note that the bounds above were constructed using quadratic functions, making them also applicable on the subclass of strongly convex quadratic functions, thus partially explaining this gap.

The main contribution of this work is as follows:

We present a general technique for establishing lower bounds on the oracle complexity of smooth minimization problems (i.e., problems where the gradient of the objective is Lipschitz-continuous, but the objective is not necessarily convex). The technique is based on a construction that allows to smoothly extend a set of function values and gradients over the entire domain in such a way that the resulting function possesses properties making it “hard” to optimize by first-order methods and allows standard lower-complexity proof schemes to be applied.

We present a shorter and easier to follow proof for establishing the exact minimax risk for non-strongly-convex smooth convex minimization problems, derived in [drori2017exact]. Notably, the proof is based on the standard set of arguments commonly used for establishing lower bounds and does not take advantage of special properties of the construction.

Preliminaries

Note that unless stated otherwise we allow $\mu$ to be negative (where $f$ is $\mu$-strongly convex, as in the $\mu\geq 0$ case, if $f(\cdot)-\frac{\mu}{2}\|\cdot\|^{2}$ is convex).

Necessary and sufficient conditions for the existence of functions $f$ satisfying the conditions above were presented by Taylor, Hendrickx and Glineur in [taylor2017smooth] for the case where $I$ and $d$ are finite, and independently by Azagra and Mudarra [azagra2017extension] for arbitrary sets in Hilbert spaces. In addition, several explicit constructions of extension functions were presented [daniilidis2018explicit, drori2017exact, taylor2017smooth]. In this section, we describe a different construction, which will form a main building block for this paper.

where $\Delta_{I}$ denotes the $|I|$-dimensional unit simplex

2 Zero-chain functions and lower bounds

In this section, we briefly review a standard technique for establishing lower complexity bounds. The technique was first introduced by Nemirovsky [nemirovsky1991optimality, nemirovsky1992information] and has been extensively used to derive lower complexity results, see [arjevani2019oracle, carmon2019lower, drori2017exact, nest-book-04, ouyang2019lower] to name a few. Here we follow the convenient presentation of the technique due to Carmon et al. [carmon2019lower]. The presentation, for the special case of deterministic first-order minimization, is based on the following definition.

Note that zero-chain functions are typically defined over the canonical unit vectors, however, in the context of this paper it is useful to consider an arbitrary set which will be chosen according to the iterates and gradient values produced by the algorithm.

Zero-chain functions are well-suited for establishing lower complexity bounds. The standard argument proceeds as follows. As a first step, we consider only the special class of first-order methods which make their first query to oracle at zero and choose the following query points only from the subspace spanned by the previous gradients seen by the method (this class of algorithms is referred to in [carmon2019lower] as zero-respecting algorithms). This assumption plays well with the zero-chain property, as together they constrain the location of each iterate to a known subspace. By showing that all points at the final subspace are ‘bad’ under the chosen inaccuracy measure, a bound on the performance of any algorithm in the class can be established.

The next step of the argument is to extend the bound to arbitrary deterministic first-order methods. This is done via the “resisting oracle” technique pioneered by Nemirovsky and Yudin in their seminal book [nemi-yudi-book83]. This procedure requires that the problem class satisfies the following properties (see [carmon2019lower, Proposition 2]):

The problem class and inaccuracy measure must be invariant under orthogonal transformations.

The domain of the function class must be embeddable in a domain whose dimension is arbitrarily larger.

Suppose the conditions above hold and assume a given algorithm queries a point $x_{k}$ ($k\geq 0$) outside the span of the previous gradients and denote the component of the query point orthogonal to the span by $v$. Then by applying an orthogonal transformation on the objective it is possible to find a transformed objective that has the same first-order information at the points already queried by algorithm while being non-informative in the direction $v$ (e.g., having a simple separable quadratic behavior along that direction). Since the algorithm cannot distinguish between the two functions, it must therefore choose the same query point $x_{k}$ when given the transformed function, thereby at the worst-case it gains no additional information by querying at the direction $v$.

Since the problem settings which are the focus of this paper satisfy the conditions above, we have the following result.