MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 3 improved the writeup a bit.

Almost all optimization algorithms work

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

That said, there are a few different when analyzing optimization algorithms, several approaches exist:

  • Number

  • Counting the number of floating point operations
  • Information based complexity (so-called oracle model)

    • Now(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 mindis the information based complexity model, pioneered by 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 will provide just one example illustrate below the simplest upper-bound on the (information based) complexity of gradient descent. The 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

    Concrete example
    show/hide this revision's text 2 edited sentence about lower bounds etc.

    Almost all optimization algorithms work with real numbers, so we cannot use the traditional Turing machine model of complexity. There is always some $\epsilon$ lurking in there.

    That said, there are a few different approaches:

    1. Number of floating point operations
    2. Information based complexity
    3. Asymptotic local analysis

    Now, the closest to what you have in mind is the information based complexity model, pioneered by Nemirovksii and Yudin. I will provide just one example below. The references will help you study this subject in much greater detail.

    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).

    Concrete example

    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).
    show/hide this revision's text 1

    Almost all optimization algorithms work with real numbers, so we cannot use the traditional Turing machine model of complexity. There is always some $\epsilon$ lurking in there.

    That said, there are a few different approaches:

    1. Number of floating point operations
    2. Information based complexity
    3. Asymptotic local analysis

    Now, the closest to what you have in mind is the information based complexity model, pioneered by Nemirovksii and Yudin. I will provide just one example below. The references will help you study this subject in much greater detail.

    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).

    Concrete example

    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 on number of oracle calls, and 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.).

    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).