1
$\begingroup$

Let $f$ be a $\alpha$-strongly convex $L$-smooth function (i.e. $\nabla f$ is $L$-Lipschitz). Consider gradient descent update: $$x_{t+1} \gets x_t - \eta_t \nabla f(x_t),$$ where $\eta_t$ are sufficiently small step sizes (for the purpose of this question, you can assume that they are as small as you need them to be).

Question: Do we have a uniform bound on $\|\nabla f(x_t)\|$ for all $t$? I want to say that $\|\nabla f(x_t)\|$ decreases (intuitively, since since $\|x_t - x^*\|$ decreases, where $x^*$ is the optimum), and therefore is bounded by $\|\nabla f(x_0)\|$, but I couldn't prove it. I expect that the worst bound is maybe something like $\frac L\alpha \|\nabla f(x_0)\|$.

The problem is that strong convexity can be used to bound $\|\nabla f(x_t)\|$ from below (using that $|\langle \nabla f(x_t), x_t - x^* \rangle| \ge \alpha \|x_t - x^*\|^2$), but I couldn't bound it from above. I also could show this for functions of form $f(x) = x^\top A x$ (by considering each eigenvector separately), but not for general functions.

I actually need this for stochastic Gradient Descent, but I expect that it'll require minor changes for both the bound and the proof.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

When $f$ is $L$-smooth, you have

$$ \| \nabla f(x) - \nabla f(x_*)\|_2 \leq L \| x - x_* \|_2 \Rightarrow \| \nabla f(x)\|_2 \leq L \| x - x_* \|_2, $$

since $\nabla f(x_*) = 0$ at the minimizer.

$\endgroup$
1
  • $\begingroup$ Thanks. Shame on me for missing this. $\endgroup$
    – Dmitry
    Mar 26, 2021 at 18:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .