Convex Sets, Convex Functions, Smoothness and Strong Convexity

The four properties that every convergence theorem quantifies over, with the equivalences and the counterexamples that show they are genuinely different.

OptimizationCore⏱ 3 hours11 min readconvexitystrong convexitysmoothnesslipschitzstationary point

5 problems →

AssumesMultivariable and Matrix Calculus

Every convergence theorem in the optimisation section has the shape: under assumptions A, B, C, algorithm X satisfies rate R. This page defines A, B and C precisely, proves the equivalences that let one be swapped for another, and gives the counterexamples that show none of them implies the others.

Convex sets and functions

DefinitionConvex set

$\mathcal{C}\subseteq\R^d$ is convex if $\theta x + (1-\theta)y \in \mathcal{C}$ for all $x,y\in\mathcal{C}$ and $\theta\in[0,1]$ .

DefinitionConvex function

$f:\mathcal{C}\to\R$ on a convex domain is convex if for all $x,y\in\mathcal{C}$ , $\theta\in[0,1]$ ,

f\big(\theta x + (1-\theta)y\big) \le \theta f(x) + (1-\theta)f(y),

strictly convex if the inequality is strict for $x \ne y$ and $\theta\in(0,1)$ , and $\mu$ -strongly convex ( $\mu>0$ ) if $x \mapsto f(x) - \tfrac\mu2\norm{x}_2^2$ is convex.

TheoremFirst-order characterisation

Let $f$ be differentiable on an open convex set. Then $f$ is convex if and only if

f(y) \ge f(x) + \ip{\nabla f(x)}{y-x} \qquad\text{for all } x,y,

and $\mu$ -strongly convex if and only if

f(y) \ge f(x) + \ip{\nabla f(x)}{y-x} + \frac\mu2\norm{y-x}_2^2 \qquad\text{for all }x,y .

Key idea

"A convex function lies above its tangent planes" is the single most useful form of convexity in proofs. It converts a global comparison between two points into a statement involving only the gradient at one of them, which is exactly what an algorithm has access to. Almost every proof in the optimisation section applies this inequality at $x = x_t$ and $y = x^\star$ .

TheoremSecond-order characterisation

Let $f$ be twice continuously differentiable on an open convex set. Then

$f$ is convex $\iff \nabla^2f(x)\succeq0$ for all $x$ ;
$f$ is $\mu$ -strongly convex $\iff \nabla^2f(x)\succeq\mu I$ for all $x$ ;
$f$ is $L$ -smooth $\iff -LI \preceq \nabla^2f(x)\preceq LI$ for all $x$ ; if $f$ is also convex this reads $\nabla^2 f(x) \preceq LI$ .

Strong convexity and its consequences

PropositionConsequences of strong convexity

Let $f$ be differentiable and $\mu$ -strongly convex, with minimiser set $\argmin f$ . Then

$f$ has a unique minimiser $x^\star$ ;
quadratic growth: $f(x) - f(x^\star) \ge \tfrac\mu2\norm{x-x^\star}_2^2$ ;
Polyak–Łojasiewicz (PL) inequality: $\norm{\nabla f(x)}_2^2 \ge 2\mu\big(f(x)-f(x^\star)\big)$ ;
coercivity: $f(x)\to\infty$ as $\norm{x}_2\to\infty$ .

Key idea

The PL inequality is the property that actually drives linear convergence, and it is weaker than strong convexity — there are non-convex functions satisfying it. Every proof on this site that obtains a geometric rate uses PL, not strong convexity directly, which is why some of those proofs extend to non-convex settings. This is the technical content behind the over-parameterised convergence results on the deep learning theory page.

PropositionThe sandwich

If $f$ is $L$ -smooth and $\mu$ -strongly convex then for all $x,y$ ,

f(x) + \ip{\nabla f(x)}{y-x} + \frac\mu2\norm{y-x}_2^2 \;\le\; f(y) \;\le\; f(x) + \ip{\nabla f(x)}{y-x} + \frac L2\norm{y-x}_2^2 ,

and necessarily $\mu\le L$ . The ratio $\kappa = L/\mu \ge 1$ is the condition number of $f$ .

Stationary points

DefinitionStationary point

$x$ is a stationary point of a differentiable $f$ if $\nabla f(x)=0$ . It is an $\eps$ -stationary point if $\norm{\nabla f(x)}_2\le\eps$ .

PropositionStationary points of convex functions are global minimisers

If $f$ is convex and differentiable and $\nabla f(x^\star)=0$ , then $x^\star\in\argmin f$ . For non-convex $f$ , a stationary point may be a local minimum, a local maximum, or a saddle point, and second-order information does not always decide which.

This is why every non-convex convergence result in this laboratory states its conclusion as "converges to an $\eps$ -stationary point" and not "converges to a minimum". The gap between the two statements is not a technical nicety; it is where essentially all of the difficulty of non-convex optimisation lives.

The four properties are independent

PropositionLogical independence

The following functions on $\R$ separate the properties:

Function	Convex	Strongly convex	$L$ -smooth	Lipschitz
$x^2$	yes	yes ( $\mu=2$ )	yes ( $L=2$ )	no
$x^4$	yes	no	no	no
$\abs{x}$	yes	no	no	yes ( $K=1$ )
$\sqrt{1+x^2}$	yes	no	yes ( $L=1$ )	yes ( $K=1$ )
$\sin x$	no	no	yes ( $L=1$ )	yes ( $K=1$ )
$x^2 + \sin(5x)/2$	no	no	yes	no

Problems

First-order characterisation of convexityProof · Beginner · 30 min Strong convexity implies the Polyak–Lojasiewicz inequalityProof · Intermediate · 30 min Existence and uniqueness of the minimiserProof · Beginner · 15 min Every norm is convex, and the operator norm is a supremum of linear functionsProof · Beginner · 15 min Separating convexity, strong convexity, smoothness and LipschitznessProof · Intermediate · 30 min

References

BookStephen Boyd and Lieven Vandenberghe (2004). Convex OptimizationChapters 2–3 are the standard reference for the material of this page.
BookYurii Nesterov (2018). Lectures on Convex OptimizationThe source of the modern complexity-theoretic framing used throughout the optimisation section.
SurveySébastien Bubeck (2015). Convex Optimization: Algorithms and Complexity

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

TheoremFirst-order characterisation of convexityproof includedA differentiable function is convex exactly when it lies above all of its tangent planes.
TheoremSecond-order characterisation of convexityproof includedA twice-differentiable function is convex exactly when its Hessian is positive semidefinite everywhere.
PropositionConsequences of strong convexityproof includedStrong convexity gives a unique minimiser, a quadratic growth lower bound and the Polyak–Lojasiewicz inequality.
PropositionThe sandwich between smoothness and strong convexityproof includedAn L-smooth and mu-strongly convex function is trapped between two quadratics, and the ratio L/mu is the condition number.
PropositionStationary points of convex functions are global minimisersproof includedFor convex functions the first-order condition is sufficient, not merely necessary.
PropositionThe four properties are logically independentproof includedExplicit functions separating convexity, strong convexity, smoothness and Lipschitz continuity.

Problems (5)

All problems