Given a function $f:\mathbb{R^n}\rightarrow \mathbb{R}$ and f is twice differentiable. We say $f$ is $l$-smooth if
$$||\nabla f(x)-\nabla f(y)|| \leq l||x-y||$$
for all $x,y \in \mathbb{R}^n$. And we say f is $\alpha$-strongly convex($\alpha >0$) if for all $x\in \mathbb{R}^n$, $$\lambda_{min}(\nabla^2 f(x)) \geq \alpha$$
Now we suppose the function $f$ satisfies both $l$-smooth and $\alpha$-strongly convex conditions. How can we get the $(\alpha,l)$– regularity condition, which says if for any $x\in \mathbb{R}^n$, we have
$$\langle \nabla f(x), x – x^*\rangle \geq \frac{\alpha}{2}||x – x^*||^2+\frac{1}{2\beta}||\nabla f(x)||^2$$ Here $x^*$ is the global minimum of the function $f$.
This is regularity condition is defined in Assumption 3b in this paper.
Thanks in advance!
Best Answer
Since your estimate only contains gradients and differences between points in $\mathbb{R}^n$, we can assume that $f(x^*)=0$ and hence $f(x)\ge 0$ everywhere (otherwise you add $-\min f$).
Given that $f$ is twice differentiable, you have the Taylor expansion around $x$: $$ f(x^*)=f(x)+\langle\nabla f(x),x^*-x\rangle+\frac{1}{2}(x^*-x)^T\nabla^2(\xi)(x^*-x) $$ Given your lower estimate on the Hessian matrix, you have $$ f(x^*)\ge f(x)+\langle\nabla f(x),x^*-x\rangle+\frac{\alpha}{2}\|x^*-x\|^2 $$ or $$ \frac{\alpha}{2}\|x^*-x\|^2-\langle\nabla f(x),x-x^*\rangle\le f(x^*)-f(x)=-f(x)\quad (*) $$ by our initial assumption.
Given that $f$ is $l$-smooth, you have the Taylor-type estimate $$ f(v)-f(w)\le \langle\nabla f(w),v-w\rangle+\frac{l}{2}\|v-w\|^2 $$ for any $v,w$. If you set $w=x$ and $v=x-\frac{1}{l}\nabla f(x)$ you get $$ f(v)-f(x)\le -\frac{1}{l}\|\nabla f(x)\|^2+\frac{l}{2l^2}\|\nabla f(x)\|^2=-\frac{1}{2l}\|\nabla f(x)\|^2. $$ Our function satisfies $f(v)\ge 0$ for every $v$ and the above inequality implies $$ -f(x)\le -\frac{1}{2l}\|\nabla f(x)\|^2, $$ which combined with the inequality $(*)$ gives the desired result.