For example, say I have a simple twice-differentiable function $x^2 + 4$. Is there some way to formalize the rate of convergence and subsequently solve for the fixed step size that maximizes this? The claim is that objective quadratic functions have an optimal fixed step size and this can be shown analytically.
Fair enough. The way to determine the step size that would be optimal for quadratics in gradient descent is the same as the step size in Newton's method since for quadratic objectives, the search direction is the same. ie) $|\frac{f^{(1)}(x_i)}{ f^{(2)}(x_i)}|$ which for your function $f(x) = x^2 + 4$ gives $|x_0|$ – muzzlator Feb 27 '13 at 18:48