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 (ERM) for a convex hypothesis space and
a convex loss function is a convex optimization problem. Such an
optimization problem can be solved efficiently by iterative methods
that use local approximations to update model parameters. The
theoretical underpinning of these methods is that any local minimizer
of a convex objective function is necessarily also a global minimizer.
Definition
A subset $\mathcal{C} \subseteq \reals^{\featuredim}$ of the
Euclidean space $\reals^{\featuredim}$ is referred to
as convex if it contains the line segment between any two points
$\weights, \weights' \in \mathcal{C}$ in that set, i.e.,
\[ \expcoeff \weights + (1-\expcoeff) \weights' \in \mathcal{C}
\quad \text{for all } \expcoeff \in [0,1] \text{.} \]
Similarly, a function
$f: \reals^{\featuredim} \rightarrow \reals$
is convex if its epigraph
$\big\{ \big( \weights^{\top},t \big)^{\top} \in \reals^{\featuredim+1} : t \geq f(\weights) \big\}$
is a convex set (Boyd and Vandenberghe, 2004). One example of a convex set
and a convex function is illustrated in Fig.\ 1.
Convexity is a central property for machine learning (ML) methods. For a convex objective function, such as
the average squared error loss of linear regression or the objective function of
the support vector machine (SVM), every local minimum is a global minimum;
for differentiable convex objective functions and suitable
step size choices, gradient descent (GD) converges to such a
minimum (Boyd and Vandenberghe, 2004).
Figure 1: (a) Convex set $\mathcal{C} \subseteq \reals^{\featuredim}$:
the line segment between any two points of $\mathcal{C}$ stays in
$\mathcal{C}$. (b) Convex function
$f: \reals^{\featuredim} \rightarrow \reals$: the shaded
epigraph is a convex set, and the line segment connecting
any two points on the graph of $f$ lies above the
graph
A closed convex set admits a representation by halfspaces: it
is the intersection of all closed halfspaces that contain it
(Boyd and Vandenberghe, 2004, Ch. 2). Not all of these halfspaces
are needed: those whose boundary hyperplane touches the
set suffice, in the following sense. A
supporting hyperplane of the set $\mathcal{C}$ is a
hyperplane $\{ \weights : \va^{\top} \weights = b \}$,
with normal vector $\va \neq \mathbf{0}$ and $b \in \reals$,
such that $\va^{\top} \weights \leq b$ holds for every
$\weights \in \mathcal{C}$, with equality for at least one
boundary point of $\mathcal{C}$
(see supporting hyperplane). The halfspace
$\{ \weights : \va^{\top} \weights \leq b \}$ then contains
$\mathcal{C}$ and is referred to as a supporting halfspace.
A closed convex set is already the intersection of its supporting
halfspaces (Rockafellar, 1970). Intersecting only
finitely many of them yields an outer approximation of the set
(see Fig. 2). For a bounded set and a
suitable choice of the halfspaces, e.g., supporting
halfspaces at equally spread boundary points, the
excess area (volume) of the approximation over the set shrinks
toward zero as the number of halfspaces increases. This representation
turns geometric statements about convex sets into systems of linear
inequalities (Rockafellar, 1970, Sect. 13).
Figure 2: A convex set $\mathcal{C}$ (shaded) and eight of its
supporting hyperplanes (gray lines). Each
supporting hyperplane defines a halfspace that
contains $\mathcal{C}$; intersecting the eight halfspaces
yields an outer approximation of $\mathcal{C}$, and the
intersection of all such halfspaces recovers
$\mathcal{C}$ exactly
See also: Euclidean space, function, epigraph,
convex optimization, minimum, objective function, halfspace,
supporting hyperplane.
References
Boyd and Vandenberghe (2004). Convex Optimization. Cambridge Univ. Press.
