0
$\begingroup$

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?

$\endgroup$

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.