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

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

<ol>
<li><p>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? </p></li>
<li><p>I <em>think</em> 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&gt;0$. Does that allow us to derive a similar bound on $||x(t) - x^*||_2^2$? </p></li>
</ol>

<p>Note: I <a href="https://mathoverflow.net/questions/119613/properties-of-the-subgradient-method">asked this question</a> on mathoverflow a week ago where it attracted no responses. </p>

CC BY-SA 3.0
2013-02-01T03:10:00.660Z
Your question is better suited for math.stackexchange.com, or maybe cs.stackexchange.com. Mathoverflow and this site are intended for research-level questions.
usul
CC BY-SA 3.0
2013-02-01T04:29:47.457Z
@usul - I believe my question is research-level.
robinson
<optimization><convex-optimization>
Properties of the subgradient method
robinson
# Properties of the subgradient method

(Asked by: username_0 on 2013-02-01)

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](https://mathoverflow.net/questions/119613/properties-of-the-subgradient-method) on mathoverflow a week ago where it attracted no responses.

**Tags:** optimization, convex-optimization

> **Comments:**
> **username_1**: Your question is better suited for math.stackexchange.com, or maybe cs.stackexchange.com. Mathoverflow and this site are intended for research-level questions.  
> **username_0**: @username_1 - I believe my question is research-level.  

---

## 0 answers

