Strong Convexity

Definition

$f$ is $\mu$-strongly convex ($\mu >0$) if $f(y)\ge f(x)+\nabla f(x)(y-x)+\frac{\mu }{2}\Vert y-x{\Vert }^2$ for all $x,y$. In 1d: $f^{\prime \prime }\ge \mu$; in ${\mathbb{R}}^d$: smallest Hessian eigenvalue $\ge \mu$. A loss is $L$-Lipschitz in $w$ if $|\ell (w,z)-\ell (w^{\prime },z)|\le L\Vert w-w^{\prime }\Vert$.

Formula

$$\frac{\mu }{2}\Vert w-w^{\ast }{\Vert }^2\le g(w)-g(w^{\ast })(\text{minimizer }{w}^{\ast }),{\Delta }_{\sup }(\text{ERM})\le \frac{4L^2}{\mu n}$$

A strongly convex empirical risk has a unique global minimum that is not hidden in flat parts. The squared loss of a linear model is not strongly convex (Hessian $2x{x}^{\top }$ has rank 1); adding $\lambda \Vert w{\Vert }^2$ makes it $2\lambda$-strongly convex (ridge regression, Lecture 5).

Appears in

• Lecture 4, definition
• Lecture 4, Theorem 3 and proof
• Lecture 4, squared loss is not strongly convex
• Lecture 4, exam-style task

Related concepts

• Algorithmic Stability
• Smoothness