# convex

*Entry of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org) (course edition), by Alexander Jung, Aalto University. CC BY 4.0. Updated 2026-11-04. [HTML](https://dictionaryofml.org/terms/convex.html) · [typeset PDF](https://dictionaryofml.org/terms/convex.pdf) · [LaTeX](https://dictionaryofml.org/terms/convex.tex) · [Python demo](https://dictionaryofml.org/terms/convex.py) · [notebook](https://dictionaryofml.org/terms/convex.ipynb)*

Math is LaTeX with the book's macros expanded, so no notation package is needed to read it.

## Abstract

A subset of the Euclidean space is convex if it contains the line segment between any two of its points. A function is convex if its epigraph is a convex set. A convex optimization problem is the minimization of a convex function over a convex set. Empirical risk minimization is a convex optimization problem whenever the hypothesis space is parameterized by a convex set of model parameters and the loss function is convex in those model parameters. Any local minimizer of a convex objective function is necessarily also a global minimizer, so a method that reaches a local minimum has solved the optimization problem.

## Definition

Learning a linear model by gradient descent moves the model parameters step by step, each iteration reducing the objective function within a neighborhood of the current model parameters. Many machine learning methods learn model parameters by such an iterative optimization method, with gradient descent and its variants the most widely used.

These optimization methods are guaranteed to converge to a global minimum when the objective function is a differentiable convex function of the model parameters and the step size is chosen suitably (Boyd and Vandenberghe, 2004, Sect. 9.3). For a convex function every local minimum is necessarily a global minimum: any choice of model parameters at which no small change reduces the objective function already attains the smallest value that the objective function takes anywhere. The average squared error loss of linear regression is a convex function of the model parameters, and so is the objective function of the support vector machine. Empirical risk minimization over a hypothesis space parameterized by a convex set of model parameters, with a loss function that is convex in them, is a convex optimization problem: the minimization of a convex function over a convex set.

Convexity is defined both for sets and for functions. For sets, the definition is geometric. A subset $\mathcal{C} \subseteq \mathbb{R}^{d}$ of the Euclidean space $\mathbb{R}^{d}$ is referred to as convex if it contains the line segment between any two of its points (Boyd and Vandenberghe, 2004, Sect. 2.1.4). For ${\mathbf w}, {\mathbf w}' \in \mathcal{C}$, that is

$$
\beta {\mathbf w} + (1-\beta) {\mathbf w}' \in \mathcal{C}
\quad \text{for all } \beta \in [0,1] \text{.}
$$

Similarly, a function $f: \mathbb{R}^{d} \rightarrow \mathbb{R}$ is convex if its epigraph $\big\{ \big( {\mathbf w}^{\top},t \big)^{\top} \in \mathbb{R}^{d+1} : t \geq f({\mathbf w}) \big\}$ is a convex set (Boyd and Vandenberghe, 2004, Sect. 3.1.7), the epigraph being the set of points on or above the graph of $f$. Examples of a convex set and of a convex function are illustrated in Fig. 1.

![Figure 1 of the entry convex](https://dictionaryofml.org/terms/fig/convex-fig1.svg)

*Figure 1: (a) Convex set $\mathcal{C} \subseteq \mathbb{R}^{d}$: the line segment between any two points of $\mathcal{C}$ stays in $\mathcal{C}$. (b) Convex function $f: \mathbb{R}^{d} \rightarrow \mathbb{R}$: the shaded epigraph is a convex set, and the line segment connecting any two points on the graph of $f$ lies above the graph*

Two families of convex sets appear throughout machine learning. The first is the halfspace $\{ {\mathbf w} \in \mathbb{R}^{d} : {\mathbf a}^{\top} {\mathbf w} \leq b \}$. It is determined by a nonzero normal vector ${\mathbf a} \in \mathbb{R}^{d} \setminus \{\mathbf{0}\}$, which fixes the direction of the bounding hyperplane, and an offset $b \in \mathbb{R}$, which fixes its position. If two points satisfy the inequality, so does every point of the segment between them (Boyd and Vandenberghe, 2004, Sect. 2.2.1). The second is the convex hull of finitely many vectors ${\mathbf x}^{(1)}, \ldots, {\mathbf x}^{(m)}$. It is defined as the set of all their convex combinations,

$$
\operatorname{conv}\big\{ {\mathbf x}^{(1)}, \ldots, {\mathbf x}^{(m)} \big\}
:= \Big\{ \sum_{r=1}^{m} \beta_{r} {\mathbf x}^{(r)}
\; : \; \beta_{r} \geq 0 \text{ for } r = 1, \ldots, m,
\; \sum_{r=1}^{m} \beta_{r} = 1 \Big\} \text{.}
$$

It is the smallest convex set that contains these vectors (Boyd and Vandenberghe, 2004, Sect. 2.1.4).

Every closed convex set is given by the intersection of all halfspaces that contain it (Boyd and Vandenberghe, 2004, Sect. 2.3.1; Rockafellar, 1970, Thm. 11.5)

\begin{equation}
\tag{1}
\mathcal{C} = \bigcap \big\{ H \subseteq \mathbb{R}^{d}
\;:\; H \text{ is a halfspace}, \; \mathcal{C} \subseteq H \big\}
\text{.}
\end{equation}

In general, intersecting a subset of the halfspaces containing a convex set yields a convex set that contains the original one, i.e., an outer approximation (see Fig. 2).

![Figure 2 of the entry convex](https://dictionaryofml.org/terms/fig/convex-fig2.svg)

*Figure 2: A convex set $\mathcal{C}$ and two halfspaces $H_{1}, H_{2}$ that contain it, in three shades of gray: lightest where only one halfspace covers the plane, mid-gray for their intersection $H_{1} \cap H_{2}$, darkest for $\mathcal{C}$ itself. Neither halfspace is tight: its bounding hyperplane does not touch $\mathcal{C}$, leaving the gaps marked by the double arrows. The intersection is therefore a strictly larger convex set than $\mathcal{C}$ – an outer approximation*

The halfspace intersection Eq. (1) can be narrowed: it needs to consider only those halfspaces that are bounded by a supporting hyperplane. Every boundary point of a non-empty convex set carries such a hyperplane (Boyd and Vandenberghe, 2004, Sect. 2.5.2), and each point outside the set is already excluded by one of the halfspaces that these supporting hyperplanes bound: for a point ${\mathbf x} \notin \mathcal{C}$ and $\mathcal{C}$ closed, there is a unique nearest point ${\mathbf p} \in \mathcal{C}$ to ${\mathbf x}$ (Boyd and Vandenberghe, 2004, Sect. 8.1). That nearest point is a boundary point of $\mathcal{C}$, and therefore one of the points that carry a supporting hyperplane: a point of the interior could be moved a little toward ${\mathbf x}$ and would still lie in $\mathcal{C}$, so it would not be the nearest one. The hyperplane through ${\mathbf p}$ with normal vector ${\mathbf x} - {\mathbf p}$, i.e., orthogonal to ${\mathbf x} - {\mathbf p}$, supports $\mathcal{C}$ at ${\mathbf p}$, and the halfspace it bounds contains $\mathcal{C}$ but not ${\mathbf x}$ (Boyd and Vandenberghe, 2004, Sects. 2.5.1 and 2.5.2; see Fig. 3). Fig. 4 shows eight supporting hyperplanes of an ellipse.

![Figure 3 of the entry convex](https://dictionaryofml.org/terms/fig/convex-fig3.svg)

*Figure 3: Why the supporting hyperplanes already suffice to recover a closed convex set $\mathcal{C}$, here a disk (darker shading). For a point ${\mathbf x}$ outside $\mathcal{C}$, let ${\mathbf p}$ be the point of $\mathcal{C}$ nearest to ${\mathbf x}$. The hyperplane through ${\mathbf p}$ orthogonal to ${\mathbf x} - {\mathbf p}$ (solid line) touches $\mathcal{C}$ at ${\mathbf p}$, so it is a supporting hyperplane, and the halfspace it bounds (lighter shading) contains $\mathcal{C}$ but not ${\mathbf x}$. Every point outside $\mathcal{C}$ is excluded by one such halfspace, so intersecting these halfspaces recovers $\mathcal{C}$*

![Figure 4 of the entry convex](https://dictionaryofml.org/terms/fig/convex-fig4.svg)

*Figure 4: A convex set $\mathcal{C}$ (shaded ellipse) and eight hyperplanes that touch it (gray lines). Each of them bounds a halfspace that contains $\mathcal{C}$, and the intersection of all halfspaces containing $\mathcal{C}$ is $\mathcal{C}$ itself*

For the epigraph of a differentiable convex function $f$, the supporting hyperplane is determined by the gradient. At the boundary point $\big({\mathbf w}^{\top}, f({\mathbf w})\big)^{\top}$, its normal vector is $\big(\nabla f({\mathbf w})^{\top}, -1\big)^{\top}$, since

$$
\big(\nabla f({\mathbf w})^{\top}, -1\big)
\left[ \begin{pmatrix} {\mathbf w}' \\ t \end{pmatrix}
- \begin{pmatrix} {\mathbf w} \\ f({\mathbf w}) \end{pmatrix} \right]
\leq 0
\quad \text{for every } \big({\mathbf w}'^{\top}, t\big)^{\top} \in \operatorname{epi} f
\text{.}
$$

This is the first-order condition $f({\mathbf w}') \geq f({\mathbf w}) + \nabla f({\mathbf w})^{\top} ({\mathbf w}' - {\mathbf w})$ written as a statement about the epigraph (Boyd and Vandenberghe, 2004, Sect. 3.1.7). At a point where the gradient vanishes, the condition gives $f({\mathbf w}') \geq
f({\mathbf w})$ for every ${\mathbf w}'$, which is the claim above that a local minimum of a convex function is a global one.

The outer approximation of Fig. 2 is also used by approximate inference in probabilistic models defined over a graph. The set of achievable marginal distributions is a convex set described by a large number of linear inequalities. Message-passing methods optimize over an outer approximation of it obtained from a subset of those inequalities (Wainwright and Jordan, 2008, Sect. 3.4.1; Sontag and Jaakkola, 2007).

Of the two families of convex sets introduced above, the convex hull is the one that characterizes the linear separability of data points with binary label values. Consider $m$ data points with feature vectors ${\mathbf x}^{(r)} \in \mathbb{R}^{d}$ and labels $y^{(r)} \in \{-1,+1\}$, for $r = 1, \ldots, m$. These data points are linearly separable if some linear classifier predicts every label correctly, i.e., there are ${\mathbf w} \in \mathbb{R}^{d} \setminus \{\mathbf{0}\}$ and $b \in \mathbb{R}$ with $y^{(r)} \big( {\mathbf w}^{\top} {\mathbf x}^{(r)} + b \big) > 0$ for $r = 1, \ldots, m$. This holds precisely when the convex hull of the feature vectors labeled $+1$ and the convex hull of those labeled $-1$ do not intersect (Boyd and Vandenberghe, 2004, Sects. 2.5.1 and 8.6.1). Separability is therefore a property of two convex sets built from the data points.

Convexity also appears in a widely used family of probabilistic models. An exponential family is constituted by the probability distributions whose probability density function has the form

$$
p({\mathbf x}; {\mathbf w}) = h({\mathbf x})
\exp\big({\mathbf w}^{\top} \mathbf{t}({\mathbf x}) - A({\mathbf w})\big)
\text{.}
$$

This probability density function is parameterized by the vector ${\mathbf w}$ and the sufficient statistics $\mathbf{t}(\cdot)$. The log-partition function $A$ is fully determined by requiring $p({\mathbf x}; {\mathbf w})$ to integrate to one. Its Hessian is the covariance matrix of the sufficient statistics $\mathbf{t}({\mathbf x})$ under $p({\mathbf x}; {\mathbf w})$,

$$
\nabla^{2} A({\mathbf w})
= {\mathbb{E}} \big\{ \mathbf{t}({\mathbf x}) \mathbf{t}({\mathbf x})^{\top} \big\}
- {\mathbb{E}} \big\{ \mathbf{t}({\mathbf x}) \big\}
{\mathbb{E}} \big\{ \mathbf{t}({\mathbf x}) \big\}^{\top}
\text{,}
$$

which is positive semi-definite. A twice-differentiable function whose Hessian is positive semi-definite is convex (Boyd and Vandenberghe, 2004, Sect. 3.1.4), so $A$ is a convex function on its domain (Wainwright and Jordan, 2008, Prop. 3.1). The convexity of $A$ implies that the negative log-likelihood function of a training set, up to an additive constant that does not depend on ${\mathbf w}$,

$$
- \sum_{r=1}^{m} {\mathbf w}^{\top}
\mathbf{t}\big({\mathbf x}^{(r)}\big) + m A({\mathbf w})
\text{,}
$$

is a convex function of ${\mathbf w}$. Thus, for an exponential family, maximum likelihood estimation is a convex optimization problem.

**See also:** epigraph, halfspace, supporting hyperplane, convex optimization, Hessian.

## References

- Boyd and Vandenberghe (2004). Convex Optimization. *Cambridge Univ. Press*. <https://doi.org/10.1017/CBO9780511804441>
- Rockafellar (1970). Convex Analysis. *Princeton Univ. Press*. <https://doi.org/10.1515/9781400873173>
- Wainwright and Jordan (2008). Graphical Models, Exponential Families, and Variational Inference. *Found. Trends Mach. Learn.*. <https://doi.org/10.1561/2200000001>
- Sontag and Jaakkola (2007). New Outer Bounds on the Marginal Polytope. *Adv. Neural Inf. Process. Syst. (NeurIPS)*. <https://proceedings.neurips.cc/paper_files/paper/2007/hash/2b323d6eb28422cef49b266557dd31ad-Abstract.html>

## Cite this entry

```bibtex
@incollection{dictml_convex,
  author = {Jung, Alexander},
  editor = {Olioumtsevits, Konstantina and Schnoor, Ekkehard},
  title = {convex},
  booktitle = {Dictionary of Applied Machine Learning},
  publisher = {Springer Nature Singapore},
  year = {2026},
  doi = {10.1007/978-981-92-2012-0_18-1},
  isbn = {978-981-92-2012-0},
  url = {https://doi.org/10.1007/978-981-92-2012-0_18-1}
}
```