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?



Computational complexity of unconstrained convex optimisation
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).


