A vector $v \in \mathbb{R}^d$ is a subgradient of a function $f\colon \mathbb{R}^d \to \mathbb{R}$ in a point $x \in \mathbb{R}^d$ if, for every $y \in \mathbb{R}^d$,

$$f(y) \ge f(x) + \langle x - y, v \rangle. $$

It can be proved that every convex function has subgradients in every point of its domain. The subgradient descent method is a method for minimizing non differentiable convex functions that consists in, staring in $x_0 \in \mathbb{R}^d$, for each $t$, taking a subgradient $v$ of $f$ at $x_t$ , and updating $x$ by the rule $x_{t+1} = x_t - \eta v$.

I want to prove that for $\eta$ small enough, the subgradient update decreases the value of $f$. I don't want to prove anything about convergence or convergence rates, I just want to see that if $0$ is not a subgradient of $f$ at $x$ and $v$ is a subgradient at the same point, then exists $\varepsilon > 0$ so that $f(x - \eta v) < f(x)$ for every $0 < \eta < \varepsilon$ (always considering $f$ is convex).

First of all, I thinked how can this be proved for the gradient descent method for differentiable functions in the general case. This can be done by taking the first order taylor approximation of $f$, in the points $x$ and $x - \eta \nabla f(x)$. From this is possible to bound the Lagrange remainder, for $\eta$ small enough, by the gradient norm, and finally obtaining that $f(x - \eta\nabla f(x)) - f(x) < 0$, obtaining the result.

After that I tried thinking about convex differentiable functions. In this case, we have that $f(x) \ge f(y) + \langle x - y, \nabla f(y) \rangle$, for every $x,y$ (in fact, in this case the gradient is the only subgradient of $f$ at every point). I was trying to prove the result I want from this hypothesis, to see then that it doesn't depend on the gradient, and any vector verifying the hypothesis (that is, the subgradients) would produce the result I want. But the only thing I could get from that expression is that $$- \eta \|\nabla f(x)\|^2\le f(x - \eta \nabla f(x)) - f(x) \le \eta \|\nabla f(x)\|^2, $$ which doesn't provide information enough to achieve the result. Any ideas?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.