# Properties of the subgradient method

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

1. 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?
2. 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$?