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!


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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.