What is the relationship between $\mu$-smoothness and Lipschitz-continuous gradient?

A convex function $F : W \to \mathbb R$ is $\mu$-smooth with respect to some $w^*$ if for all $w\in W$: $$ F(w) - F(w^*) \le \frac{\mu}{2}||w-w^*||^2 $$

In https://icml.cc/Conferences/2012/papers/261.pdf the authors write: "Such [$\mu$-smooth] functions arise, for instance, in logistic and leastsquares regression, and in general for learning linear predictors where the loss function has a Lipschitz-continuous gradient"

Suppose I know the Lipschitz constant for $\nabla F$, how does this relate to $\mu$?

  • $\begingroup$ The definition is not correct: you have to include the term $-\nabla F(w^*)(w-w^*)$ on the left-hand side. In the paper they assume $w^*$ to be the minimum, hence $\nabla F(w^*)=0$. $\endgroup$ – daw Mar 23 '18 at 12:05

It holds $\mu=L$: $$ |f(x)-f(x^*)-\nabla f(x^*)(x-x^*)| \le\| \int_0^1 \nabla f(x+t(x-x^*))-\nabla f(x^*)dt\| \cdot \|x-x^*\|\\ \le \frac L2 \|x-x^*\|^2. $$


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.