= Fenchel–Young gap
{c}
{title2=$G_f(x,p)=f(x)+f^*(p)-p\cdot x$}
The <Fenchel–Young gap> is the nonnegative discrepancy
$$
G_f(x,p)=f(x)+f^*(p)-p\cdot x\geq0
$$
for a <proper convex function> and its <convex conjugate>. It can be $+\infty$. When $f^*(p)$ is finite, it is the vertical distance between $f(x)$ and its <affine minorant> $\ell_p(x)=p\cdot x-f^*(p)$. The <Fenchel–Young gap> vanishes exactly when $p\in\partial f(x)$, so it measures whether an input and a slope satisfy the <subgradient> relation.
For the <convex quadratic function> $f(x)=x^2/2$, completing the square gives
$$
G_f(x,p)=\frac{x^2}{2}+\frac{p^2}{2}-px=\frac{(x-p)^2}{2}.
$$
At $x=-1$ and $p=2$, the function value is $1/2$ and the <tangent line> $2x-2$ has value $-4$, giving a <Fenchel–Young gap> of $9/2$. In $\mathbb R^n$, the same calculation for $f(x)=\|x\|_2^2/2$ gives $f^*(p)=\|p\|_2^2/2$ and $G_f(x,p)=\|x-p\|_2^2/2$, half the squared <Euclidean norm> of the mismatch.
\Image[/fenchel-young-quadratic-gap.png]
{title=The <Fenchel–Young gap> for a <convex quadratic function> is the vertical distance above a <tangent line>}
{description=The left panel fixes $p=2$ and marks the distance $G_f(-1,2)=9/2$ between the <convex quadratic function> $x^2/2$ and its <tangent line> $2x-2$. The right panel plots the <Fenchel–Young gap> $(x-2)^2/2$, which vanishes at the matching input $x=p=2$.}
\b[An exact optimization error certificate.] Fix a slope $p$ with $f^*(p)<+\infty$ and minimize the linearly tilted <objective function> $h_p(z)=f(z)-p\cdot z$. By the definition of the <convex conjugate>, $\inf_z h_p(z)=-f^*(p)$, so
$$
h_p(x)-\inf_z h_p(z)=G_f(x,p).
$$
This identity holds even when the <infimum> is not attained. Thus a computed finite <Fenchel–Young gap> is exactly the error in objective value for this <minimization problem>. For the <convex quadratic function>, $G_f(x,p)\leq\varepsilon$ implies $|x-p|\leq\sqrt{2\varepsilon}$. A general <proper convex function> need not convert a small gap into a small distance: the <absolute value> has zero gap at $p=1$ for every $x\geq0$.
The <Fenchel–Young gap> also connects <convex analysis> to <optimal transport>. For a <proper convex function> $\Phi$, define <Kantorovich potentials> $u(x)=\|x\|_2^2/2-\Phi(x)$ and $v(y)=\|y\|_2^2/2-\Phi^*(y)$. The half-squared <Euclidean distance> cost satisfies $\|x-y\|_2^2/2-u(x)-v(y)=G_\Phi(x,y)$. For a <transport plan> with finite integrated cost and integrable <Kantorovich potentials>, integrating this identity gives the difference between transport cost and the potentials' bound. This is the same local <subgradient> mismatch summed over transported pairs.
Back to article page
