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

3 improved the writeup a bit.

Almost all optimization algorithms work


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