Computational complexity of unconstrained convex optimisation

Question

What is known about the relationship between unconstrained convex optimisation and computational complexity? For example, for which optimisation problems and which gradient descent algorithms is one guaranteed to get to the optima in a polynomial number of iterations? How about getting to within some $\epsilon>0$ of the optima?

Answer 1

Since we are dealing with real number computation, we cannot use the traditional Turing machine for complexity analysis. There will always be some $\epsilon$s lurking in there.

That said, when analyzing optimization algorithms, several approaches exist:

1. Counting the number of floating point operations
2. Information based complexity (so-called oracle model)
3. Asymptotic local analysis (analyzing rate of convergence near an optimum)

A very popular, and in fact very useful model is approach 2: information based complexity. This, is probably the closest to what you have in mind, and it starts with the pioneering work of Nemirovksii and Yudin.

The complexity depends on the structure of the convex function: Lipschitz continuous gradients help, strong convexity helps, a certain saddle point structure helps, and so on. Even if your convex function is not differentiable, then depending on its structure, different results exist, and some of these you can chase by starting from Nesterov's "Smooth minimization of nonsmooth functions" cited by Brian in his answer.

But for the sake of clarity, I illustrate below the simplest upper-bound on the (information based) complexity of gradient descent. This complexity is worse than the lower bound (optimal methods that attain this do exist). In any case, the references cited will help you study this subject in much greater detail.

Concrete example

In summary, in the informational complexity model, one assumes access to an oracle that given an input vector $x$, outputs the objective and gradient values $(f(x), \nabla f(x))$. Then, complexity of a convex optimization algorithm is measured in terms of how many calls to the oracle an algorithm makes to be able to obtain an $\epsilon$-accurate solution (e.g., in terms of objective value, norm of gradient, or distance to optimal).

Suppose $f$ is $C^1$ convex function defined over the reals, and we wish to solve the unconstrained optimization problem \begin{equation*} \min_x\quad f(x) \end{equation*}

Suppose we solve the above problem using the gradient-descent iteration

\begin{equation*} x^{k+1} = x^k - \alpha_k\nabla f(x^k),\quad k=0,1,\ldots. \end{equation*}

$\newcommand{\reals}{\mathbb{R}}$

Theorem. (Nesterov) Let $f$ be as above, and let it have a Lipschitz continuous gradient with constant $L > 0$. Let $\alpha_k = 1/L$. let $x^*$ be an optimal solution to the above problem. Define the diameter $D:=\|x_0-x^*\|$. Then, the iterates $(x^k)$ produced by gradient-descent satisfy

$$ f(x^k) - f(x^*) \le \frac{2LD^2}{k+4}. $$

As a corollary, we see that gradient-descent requires $O(1/\epsilon)$ calls to the oracle to obtain an $\epsilon$-accuracy solution (i.e., to ensure that $f(x^k)-f(x^*) \le \epsilon$).

There also exist lower-bounds (e.g., $O(1/\sqrt{\epsilon})$ for the above class) on number of oracle calls, and methods such as Nesterov's optimal gradient method that actually achieve the lower-bound.

More generally, several other specialized cases of information based complexity depending on different assumptions that one makes about the oracle (stochastic, deterministic, sparse), and the function (strongly convex, nonsmooth, etc.). Please have a look at the references cited below for more information.

References.

1. Nemirovsky, A. S., and Yudin, D. B. 1983. Problem complexity and method efficiency in optimization. Wiley-Interscience. Translated by: E.~R.~Dawson.

2. Nesterov, Yu. 2004. Introductory Lectures on Convex Optimization: A Basic Course Kluwer Academic (now Springer).

Answer 2

Some books to start with for background reading would include:

Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Springer, 2003.

Y. Nesterov and A. Nemirovsky, Interior Point Polynomial Methods in Convex Programming : Theory and Algorithms, SIAM, 1993. (Really just about the computational complexity of conic optimization problems, particularly LP, SOCP, and SDP.)

Stephen Vavasis, Nonlinear Optimization: Complexity Issues, Oxford University Press, 1991.

A seminal paper is

Y. Nesterov. Smooth Minimization of Non-Smooth Functions Mathematical Programming 103:127-152. 2005.

In the analysis of subgradient descent methods for convex optimization problems, the normal approach is to analyze the number of iterations to get the objective function value to within $\epsilon$ of the optimal value (this is not the same as finding a solution within $\epsilon$ of the optimal solution!) The key results are that for a smooth problem with Lipschitz continuous gradient with Lipschitz constant $L$, this can be done in $O(\sqrt{L/\epsilon})$ iterations (e.g. by using an algorithm published by Nesterov in a 1983 paper), and that for nonsmooth problems, $O(1/\epsilon^{2})$ iterations are required, and this is in general the best possible bound. There are explicit counterexamples that show you can't do better.

However, Nesterov shows how in many cases it is possible to smooth a nonsmooth problem and then apply an optimal method to the smoothed problem to get an $\epsilon$ optimal solution to the original nonsmooth problem in $O(1/\epsilon)$ time. Doing this requires that the problem have some specific structure that can be exploited so as to produce a smooth problem with a Lipschitz continuous gradient and Lipschitz constant such that the optimal method for the smoothed problem takes $O(1/\epsilon)$ iterations. Nesterov gives several examples of this process in the 2005 paper.

This theoretical work hit at just the moment that interest in compressive sensing problems (which are nonsmooth convex optimization problems with special structure) was growing. In particular, many people are interested in solving very large scale problems of the form

$ \min \| Ax - b \|^{2}\_{2} + \lambda \| x \|_{1} $

Nesterov's ideas are certainly applicable in this context, but practical methods for these problems don't all follow this approach.

It isn't clear why you're asking about this, and there's quite a lot of research going on in this area. Chances are that a more specific question would yield a much more informative answer.