Mathematical Infrastructure

Convex Duality

Fenchel conjugates, the Fenchel-Moreau theorem, weak and strong duality, KKT conditions, and why duality gives the kernel trick for SVMs, connects regularization to constraints, and enables adversarial formulations in DRO.

CoreTier 1Stable~75 min

Prerequisites

Convex Optimization Basics

Quiz (3)

Why This Matters

Duality is the tool that converts hard optimization problems into equivalent (or approximately equivalent) problems that are easier to solve, analyze, or interpret. In machine learning, duality is not an abstract luxury --- it is the engine behind some of the most important algorithms and insights:

SVMs: the dual of the SVM problem reveals the kernel trick, transforming an optimization in parameter space into one in the space of inner products between data points
Regularization: constrained ERM (minimize loss subject to a norm constraint) and regularized ERM (minimize loss plus a penalty) are dual to each other. The Lagrange multiplier is the regularization parameter
DRO: distributionally robust optimization uses duality to convert a minimax problem (worst-case over distributions) into a tractable regularized problem

If you do not understand duality, you cannot understand why the kernel trick works, why regularization is equivalent to constraining, or how adversarial formulations lead to tractable algorithms.

Mental Model

Every convex minimization problem has a "shadow" problem --- its dual --- which is a maximization problem. The dual always provides a lower bound on the primal optimum (weak duality). Under mild conditions (strong duality), the two optima are equal. At the optimal point, the primal and dual variables satisfy complementary conditions (KKT).

The Fenchel conjugate $f^*$ is the fundamental building block: it converts a function into its "dual representation." For background on convex sets and functions, see convex optimization basics. The conjugate of the conjugate gives back the original function (for closed convex functions), which is the Fenchel-Moreau theorem.

Formal Setup

Definition

Fenchel Conjugate (Convex Conjugate)

The Fenchel conjugate (or convex conjugate) of a function $f: \mathbb{R}^d \to \mathbb{R} \cup \{+\infty\}$ is:

$f^*(y) = \sup_{x \in \mathbb{R}^d} \left\{ y^\top x - f(x) \right\}$

The conjugate $f^*: \mathbb{R}^d \to \mathbb{R} \cup \{+\infty\}$ is always convex (as a supremum of affine functions in $y$ ), even if $f$ is not convex.

Interpretation: $f^*(y)$ measures the maximum "gap" between the linear function $x \mapsto y^\top x$ and $f(x)$ . Geometrically, $f^*(y)$ is related to the supporting hyperplane of the epigraph of $f$ with slope $y$ .

Definition

Young-Fenchel Inequality

For any $f$ and its conjugate $f^*$ , and for all $x, y$ :

$x^\top y \leq f(x) + f^*(y)$

This is immediate from the definition: $f^*(y) \geq y^\top x - f(x)$ . Equality holds if and only if $y \in \partial f(x)$ (the subdifferential of $f$ at $x$ ).

Key conjugate pairs (you should know these):

$f(x)$	$f^*(y)$
$\frac{1}{2}\\|x\\|^2$	$\frac{1}{2}\\|y\\|^2$
$\\|x\\|$ (any norm)	$\delta_{\\|y\\|_* \leq 1}$ (indicator of dual norm ball)
$\frac{1}{2}x^\top Ax$ ( $A \succ 0$ )	$\frac{1}{2}y^\top A^{-1}y$
$e^x$	$y\log y - y$ for $y > 0$ , $0$ for $y = 0$ , $+\infty$ for $y < 0$
$\delta_C(x)$ (indicator of convex set)	$\sup_{x \in C} y^\top x$ (support function)

Main Theorems

Theorem

Fenchel-Moreau Biconjugation Theorem

Statement

If $f: \mathbb{R}^d \to \mathbb{R} \cup \{+\infty\}$ is proper (not identically $+\infty$ and never $-\infty$ ), lower-semicontinuous, and convex, then:

$f^{**} = f$

That is, the conjugate of the conjugate recovers the original function.

Intuition

A closed convex function is completely determined by its supporting hyperplanes. The Fenchel conjugate encodes these hyperplanes. Conjugating twice reconstructs the function from its hyperplane representation. This is analogous to the Fourier transform: applying it twice (with appropriate normalization) gives back the original function.

If $f$ is not convex or not lower-semicontinuous, then $f^{**}$ is the closed convex envelope of $f$ --- the largest closed convex function that is pointwise $\leq f$ .

Proof Sketch

One direction is easy: $f^{**}(x) = \sup_y \{x^\top y - f^*(y)\} \leq f(x)$ follows from the Young-Fenchel inequality (for each $y$ , $x^\top y - f^*(y) \leq f(x)$ ).

The other direction uses the supporting hyperplane theorem: for every $x_0$ and every $\alpha < f(x_0)$ , the point $(x_0, \alpha)$ lies below the epigraph of $f$ . Since $\text{epi}(f)$ is closed and convex, a separating hyperplane gives a $y$ with $y^\top x_0 - f^*(y) \geq \alpha$ . Since $\alpha < f(x_0)$ is arbitrary, $f^{**}(x_0) \geq f(x_0)$ .

Why It Matters

Fenchel-Moreau is the theoretical foundation of all convex duality. It says that every closed convex function has a perfect "dual representation" via its conjugate. This enables:

Converting between constrained and penalized formulations: the conjugate of an indicator function is a support function, and vice versa. This is exactly the duality between norm-constrained and norm-penalized optimization.
Deriving dual problems: the Lagrangian dual of a convex problem can be written in terms of Fenchel conjugates. Strong duality ( $f^{**} = f$ ) ensures no duality gap.
Variational representations: many quantities in information theory (KL divergence, entropy) have dual representations via Fenchel conjugates. The Donsker-Varadhan variational formula for KL divergence is a consequence.

Failure Mode

If $f$ is not closed (lower-semicontinuous) or not convex, then $f^{**} \neq f$ . The biconjugate $f^{**}$ will be the closed convex envelope, which can differ significantly. For example, if $f(x) = -|x|$ , then $f$ is concave, and $f^{**}(x) = -\infty$ for all $x$ . Always verify closedness and convexity before applying Fenchel-Moreau.

Lagrangian Duality

Definition

Lagrangian and Dual Problem

Consider the primal problem:

$\min_x f(x) \quad \text{subject to } g_i(x) \leq 0, \; i = 1, \ldots, m$

The Lagrangian is:

$L(x, \lambda) = f(x) + \sum_{i=1}^m \lambda_i g_i(x), \quad \lambda_i \geq 0$

The dual function is $q(\lambda) = \inf_x L(x, \lambda)$ . The dual problem is:

$\max_{\lambda \geq 0} q(\lambda)$

The dual function $q$ is always concave (as an infimum of affine functions in $\lambda$ ), regardless of whether the primal is convex.

Definition

Weak and Strong Duality

Let $p^*$ be the primal optimal value and $d^*$ the dual optimal value.

Weak duality (always holds): $d^* \leq p^*$ . The dual provides a lower bound on the primal.

Strong duality: $d^* = p^*$ . The duality gap is zero.

Strong duality holds for convex problems under Slater's condition: there exists a strictly feasible point $\bar{x}$ with $g_i(\bar{x}) < 0$ for all $i$ .

Theorem

Strong Duality via Slater's Condition

Statement

If $f$ and $g_1, \ldots, g_m$ are convex and there exists a strictly feasible point $\bar{x}$ with $g_i(\bar{x}) < 0$ for all $i$ , then strong duality holds: the primal and dual optimal values are equal, and the dual optimum is attained.

Intuition

Slater's condition says the feasible region has a non-empty interior (the constraints are not "barely" satisfied). This prevents pathological cases where the primal feasible set is "too thin" for duality to work. In practice, Slater's condition holds for almost every convex optimization problem you encounter in ML.

Proof Sketch

Consider the set $\mathcal{V} = \{(u, t) : \exists x, \; g_i(x) \leq u_i, \; f(x) \leq t\} \subseteq \mathbb{R}^{m+1}$ . This set is convex (because $f$ and $g_i$ are convex). The point $(0, p^*)$ is on the boundary of $\mathcal{V}$ . By the supporting hyperplane theorem, there exists a hyperplane separating $(0, p^*)$ from the interior of $\mathcal{V}$ . This hyperplane defines the optimal dual variables $\lambda^*$ . Slater's condition ensures the hyperplane has the right orientation (the $\lambda$ components are non-negative), which gives $q(\lambda^*) = p^*$ .

Why It Matters

Strong duality is what makes dual methods actually useful:

SVM dual: the primal SVM minimizes over $w$ (potentially high-dimensional). The dual minimizes over $\alpha_i$ (one per data point). Under strong duality, both give the same answer. The dual depends on data only through inner products $x_i^\top x_j$ , enabling the kernel trick: replace inner products with $k(x_i, x_j)$ .
Regularization duality: minimizing $f(x)$ subject to $\|x\| \leq r$ is equivalent (by strong duality) to minimizing $f(x) + \lambda\|x\|$ for some $\lambda \geq 0$ . The Lagrange multiplier $\lambda$ is the regularization parameter. This is why constraint-based and penalty-based regularization are interchangeable.
DRO: worst-case expected loss over a ball of distributions can be dualized into a regularized empirical risk problem. This converts an intractable minimax problem into a tractable convex program.

Failure Mode

Without Slater's condition, strong duality can fail. Example: minimize $x$ subject to $x^2 \leq 0$ . The only feasible point is $x = 0$ (primal value $p^* = 0$ ). But the Lagrangian $L(x, \lambda) = x + \lambda x^2$ gives $q(\lambda) = \inf_x (x + \lambda x^2)$ . For $\lambda > 0$ : $q(\lambda) = -1/(4\lambda)$ . So $d^* = \sup_{\lambda \geq 0} q(\lambda) = 0$ (approached but not attained). In this case strong duality technically holds, but consider modified examples where the constraint is an equality on a convex function: Slater's condition fails and a gap can appear.

KKT Conditions

Definition

Karush-Kuhn-Tucker (KKT) Conditions

For the convex problem $\min_x f(x)$ subject to $g_i(x) \leq 0$ , under strong duality, the primal-dual pair $(x^*, \lambda^*)$ is optimal if and only if:

Primal feasibility: $g_i(x^*) \leq 0$ for all $i$
Dual feasibility: $\lambda_i^* \geq 0$ for all $i$
Stationarity: $0 \in \partial f(x^*) + \sum_i \lambda_i^* \partial g_i(x^*)$
Complementary slackness: $\lambda_i^* g_i(x^*) = 0$ for all $i$

Complementary slackness says: either a constraint is tight ( $g_i(x^*) = 0$ ) or its multiplier is zero ( $\lambda_i^* = 0$ ). Active constraints "matter"; inactive constraints are irrelevant. In SVMs, the data points with $\lambda_i^* > 0$ are the support vectors.

Sion Minimax Theorem

Definition

Sion Minimax Theorem

If $\mathcal{X}$ is convex and compact, $\mathcal{Y}$ is convex, and $\phi(x, y)$ is convex-concave (convex in $x$ for each $y$ , concave in $y$ for each $x$ ) and lower-semicontinuous in $x$ , upper-semicontinuous in $y$ , then:

$\min_{x \in \mathcal{X}} \sup_{y \in \mathcal{Y}} \phi(x, y) = \sup_{y \in \mathcal{Y}} \min_{x \in \mathcal{X}} \phi(x, y)$

The min and sup can be interchanged. This is a generalization of von Neumann's minimax theorem for zero-sum games.

Why it matters for ML: The minimax theorem underlies adversarial formulations. In GANs, DRO, and robust optimization, you want to swap a min over model parameters with a max over adversarial perturbations. The Sion theorem tells you when this swap is valid.

Canonical Examples

Example

Conjugate of the squared norm

$f(x) = \frac{1}{2}\|x\|^2$ . Then:

$f^*(y) = \sup_x \{y^\top x - \frac{1}{2}\|x\|^2\}$

Taking the gradient and setting to zero: $y - x = 0$ , so $x^* = y$ . Substituting: $f^*(y) = y^\top y - \frac{1}{2}\|y\|^2 = \frac{1}{2}\|y\|^2$ .

The squared norm is its own conjugate. This self-duality is why $\ell_2$ regularization leads to particularly clean dual problems (e.g., ridge regression).

Example

Duality between constrained and penalized optimization

Primal (constrained): $\min_w f(w)$ subject to $\|w\| \leq r$

Lagrangian: $L(w, \lambda) = f(w) + \lambda(\|w\| - r)$

Dual: $\max_{\lambda \geq 0} \{\inf_w [f(w) + \lambda\|w\|] - \lambda r\}$

The inner minimization $\inf_w [f(w) + \lambda\|w\|]$ is exactly the penalized problem with regularization parameter $\lambda$ .

By strong duality, there exists $\lambda^*$ such that the constrained problem with radius $r$ and the penalized problem with parameter $\lambda^*$ have the same solution. This is the rigorous justification for the equivalence between norm-constrained and norm-penalized regularization.

Common Confusions

Watch Out

Weak duality always holds; strong duality requires conditions

Students sometimes assume that the primal and dual always have the same optimal value. Weak duality ( $d^* \leq p^*$ ) is trivially true, but strong duality ( $d^* = p^*$ ) requires assumptions like convexity plus Slater's condition. For non-convex problems, the duality gap can be arbitrarily large. Always check the conditions before claiming strong duality.

Watch Out

The dual problem is always concave, even if the primal is non-convex

The dual function $q(\lambda) = \inf_x L(x, \lambda)$ is concave in $\lambda$ regardless of whether $f$ or the $g_i$ are convex. This is because $q$ is a pointwise infimum of affine functions in $\lambda$ . The dual is always a concave maximization problem, which is computationally tractable. The catch: for non-convex primal problems, $d^* < p^*$ and the dual only gives a lower bound.

Watch Out

KKT conditions are necessary and sufficient only under strong duality

For general non-convex problems, KKT is only necessary (assuming constraint qualification). For convex problems with strong duality, KKT is both necessary and sufficient. In ML, most problems of interest (SVMs, regularized linear models, DRO) are convex and satisfy Slater's condition, so KKT gives exact optimality conditions.

Summary

Fenchel conjugate: $f^*(y) = \sup_x \{y^\top x - f(x)\}$
Young-Fenchel inequality: $x^\top y \leq f(x) + f^*(y)$ , with equality iff $y \in \partial f(x)$
Fenchel-Moreau: $f^{**} = f$ for closed convex functions
Weak duality always holds ( $d^* \leq p^*$ ); strong duality requires convexity + Slater's condition
KKT conditions: primal feasibility, dual feasibility, stationarity, complementary slackness
Duality converts constrained problems into penalized problems (regularization = Lagrangian duality)
SVM dual reveals the kernel trick; DRO dual yields tractable regularization

Exercises

ExerciseCore

Problem

Compute the Fenchel conjugate of $f(x) = \|x\|_1$ (the $\ell_1$ norm on $\mathbb{R}^d$ ). What is the dual norm of $\ell_1$ ?

ExerciseAdvanced

Problem

Derive the dual of the soft-margin SVM problem:

$\min_{w, b, \xi} \frac{1}{2}\|w\|^2 + C\sum_i \xi_i \quad \text{s.t. } y_i(w^\top x_i + b) \geq 1 - \xi_i, \; \xi_i \geq 0$

Show that the dual depends on the data only through inner products $x_i^\top x_j$ , which enables the kernel trick.

Related Comparisons

Weak Duality vs. Strong Duality

References

Canonical:

Rockafellar, Convex Analysis (1970), Chapters 12, 26-28, 31
Boyd & Vandenberghe, Convex Optimization (2004), Chapter 5
Borwein & Lewis, Convex Analysis and Nonlinear Optimization (2nd ed., 2006)

Current:

Shalev-Shwartz & Ben-David, Understanding Machine Learning (2014), Chapter 15 (SVM duality)
Ben-Tal, El Ghaoui, Nemirovski, Robust Optimization (2009), Chapter 4

Next Topics

Building on convex duality:

Support vector machines: the canonical application of Lagrangian duality in ML
Regularization theory: constrained and penalized formulations as dual views
Kernels and RKHS: the kernel trick as a consequence of the SVM dual

Last reviewed: April 2026

Prerequisites

Foundations this topic depends on.

Convex Optimization BasicsLayer 1
Differentiation in RnLayer 0A
Sets, Functions, and RelationsLayer 0A
Basic Logic and Proof TechniquesLayer 0A
Matrix Operations and PropertiesLayer 0A

Builds on This

Augmented Lagrangian and ADMMLayer 2
Information GeometryLayer 3
Minimax and Saddle PointsLayer 2
Von Neumann Minimax TheoremLayer 2
Mirror Descent and Frank-WolfeLayer 3
Optimal Transport and Earth Mover's DistanceLayer 3

Next Topics

Support Vector MachinesContinue →Regularization TheoryContinue →Kernels and RkhsContinue →