Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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^*$.

There are a number of puzzling things about the subgradient method that I don't feel I have a good handle on.

  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))$? Specifically is it true that $f(x(t))-f^* = O( \log t/t)$ (taking $L$ and $||x(0)-x^*||^2$ as constants in the O-notation)?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$?

Note: I asked this question on mathoverflow a week ago where it attracted no responses.

share|cite|improve this question
Your question is better suited for, or maybe Mathoverflow and this site are intended for research-level questions. – usul Feb 1 '13 at 3:10
@usul - I believe my question is research-level. – robinson Feb 1 '13 at 4:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.