The subgradient algorithm for minimizing a convex function $f(x)$ is the update rule $$ x(t+1) = x(t) - \alpha(t) d(t)$$ where $d(t)$ is any subgradient of $f(x)$ at $x(t)$ and $\alpha(t)$ is a decaying stepsize. Choosing $\alpha(t) = 1/\sqrt{t}$, one usually obtains the bound $$ f \left( \frac{\sum_{j=1}^t \alpha(j) x(j)}{\sum_{j=1}^t \alpha(j)}\right) - f^* \leq O \left( \frac{||x(0) - x^*||_2^2 + L \ln t}{ \sqrt{t}} \right)$$ where $L$ is an upper bound on the norm of all the subgradients that appear by time $t$, and we assume that the optimal value is $f^*$.
Some puzzling things about the subgradient method make sense to me after a little thought: for example, it is a little disconcerting that $L$ enters the bound, but considering functions such as $f(x) = 1000000|x|$ motivates why this is so - starting the subgradient method near the optimal point for this function leads to lots of "overshooting."
Other things about the subgradient method are mysterious to me.
Why is the bound for a convex combination for $x(1), \ldots, x(t)$ instead of for $f(x(t))$? Is it possible to derive a similar bound for $f(x(t))$? If not, is there a clear reason why this is unreasonable?
I think I understand why the bound is on $f(\cdot) - f^* $ rather than on the distance $||x(t)-x^*||_2^2$ - it has to do with functions that are nearly flat. For example, if $f(x)$ is a tiny perturbation of the zero function, it may take a while for the subgradient algorithm to find the optimal point. So, suppose we assume that every subgradient that enters the method has norm at least $l>0$. Does that allow us to derive a similar bound on $||x(t) - x^*||_2^2$?
