\documentclass[11pt]{article}
\usepackage{iftex}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{svg}
\usepackage{url}
\usepackage{hyperref}

\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{rem}{Remark}
\newtheorem{exmp}{Example}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{prop}{Proposition}

\date{2024-02-07}
\title{A first look at convex analysis}
% \large Crash course in convexity to have just enough material to study the gradient descent.}
\author{\href{https://samuelvaiter.com}{Samuel Vaiter}}

\begin{document}

\maketitle

\tableofcontents

\begin{figure}[htbp]
\centering
\includegraphics[width=.9\linewidth]{a-first-look-at-convex-analysis-article-archimede.png}
\caption{Definition of concavity by Archimede}
\end{figure}

Despite the fact that many problems encountered in statistics and machine learning are not convex, convexity is an important to study in order to understand what is the generic behaviour of an optimization procedure.

\section{Convex set}\label{sec:convex-set}

A set \(C \subseteq \mathcal{X}\) is convex if every segment of \(C\) is contained in \(C\).
It can formalized as the following definition and illustrated in Figure~\ref{fig:convex-set}.

\begin{figure}[htbp]
\centering
\includesvg[width=.9\linewidth]{a-first-look-at-convex-analysis-convex_set.svg}
\caption{Left: convex set. Right: not a convex set.}\label{fig:convex-set}
\end{figure}

\begin{defn}
A set \(C \subseteq \mathcal{X}\) is \textbf{convex} if
$$
\forall (x,y) \in C^{2}, \forall \lambda \in [0,1],
\quad
\lambda x + (1-\lambda) y \in C .
$$
\end{defn}

In most of these lecture notes, the set \(\mathcal{X}\) will the Euclidean space \(\mathbb{R}^{p}\), but remark that this notion only requires that \(\mathcal{X}\) is a vector space over the real numbers \(\mathbb{R}\), possibly of infinite dimension.

\begin{exmp}
\begin{itemize}
\item The convex sets of \(\mathbb{R}\) are \emph{exactly} the intervals of \(\mathbb{R}\).
\item Any affine hyperplane \(H = \{x \in \mathcal{X} \mid \varphi(x) = \alpha\}\) where \(\mathcal{X}\) is a real vector space, \(\varphi\) a linear functional and \(\alpha \in \mathbb{R}\) is convex.
\item Any half-space \(H_{-} = \{x \in \mathcal{X} | \varphi(x) \leq \alpha\}\) is also convex.
\item The unit simplex of \(\mathbb{R}^{d}\) defined as
\end{itemize}
$$ \Delta^{d-1} = \{x \in \mathbb{R}^{d} \mid x_{i} \geq 0 \text{ and } \sum_{i} x_{i} = 1\} $$
is convex.
\begin{itemize}
\item The nonnegative orthant \(\mathbb{R}_{\geq 0}^{d} = \{x \in \mathbb{R}^{d} | x_{i} \geq 0\}\) is convex.
\end{itemize}
\end{exmp}

The following proposition reviews some important algebraic properties of convex sets.

\begin{prop}
\begin{itemize}
\item \emph{Arbitrary intersection}. Let \((C_{i})_{i \in I}\) convex sets where \(I\) is a set. Then \(\cap_{i \in I} C_{i}\) is convex.
\item \emph{Cartesian product}. Let \(C_{1},\dots,C_{n}\) be sets of \(\mathbb{R}^{n_{1}}, \dots, \mathbb{R}^{n_{n}}\). Then \(C_{1} \times \dots \times C_{n}\) is convex if, and only if, every \(C_{i}\) is convex.
\item \emph{Sum}. Let \(C_{1}\), \(C_{2}\) two convex sets. Then the (Minkowski) sum \(C_{1} + C_{2}\) is convex.
\item \emph{Affine map}. Let \(A: \mathbb{R}^{n} \to \mathbb{R}^{m}\) be an affine map and \(C \subseteq \mathbb{R}^{n}\) a convex set. Then the image \(A(C)\) is convex.
\end{itemize}
\end{prop}

\section{Convex functions}\label{sec:convex}

The intuitive definition of a convex function is a function such that ``the line joining \(f(x)\) and \(f(y)\) lies above the graph of \(f\) between \(x\) and \(y\)''.
Formally, this definition makes sense using the definition of the epigraph of \(f\).

\begin{defn}
Let \(f: \mathbb{R}^{n} \to \overline{\mathbb{R}}\) and \(f \neq +\infty\).
The \textbf{epigraph} of \(f\) is the subset of \(\mathbb{R}^{n} \times \mathbb{R}\) defined by
$$
    \mathrm{epi} f
    :=
    \{(x,t) \in \mathbb{R}^{n} \times \mathbb{R} \mid t \geq f(x)\} .
$$
\end{defn}

\begin{figure}[htbp]
\centering
\includesvg[width=.9\linewidth]{a-first-look-at-convex-analysis-epigraph.svg}
\caption{(Left) Epigraph of a concave function. (Right) Epigraph of a convex function.}
\end{figure}

Equipped with this notion, we can define convex functions using the definition of convex sets applied to the epigraph.

\begin{defn}
A function \(f: \mathbb{R}^{p} \to \overline{\mathbb{R}}\) such that \(f \neq +\infty\) is \textbf{\textbf{convex function}} iff its epigraph \(\text{epi} f\) is convex.
\end{defn}

It is possible to make explicit this definition as follow:
\begin{equation}
  \forall x,y \in \mathrm{dom} f,\, \forall \lambda \in [0,1],
  \qquad
  f(\lambda x + (1-\lambda) y) \leq \lambda f(x) + (1-\lambda) f(y) .
  \label{eq-convex-function}
\end{equation}
Following the convention introduced in (Hiriart-Urruty, Jean-Baptiste and Lemarechal, Claude, 1996), we will denote the set of all convex functions of \(\mathbb{R}^{p}\) as \(\operatorname{Conv} \mathbb{R}^{p}\), and the set of closed -- that is, with closed epigraph -- convex functions of \(\mathbb{R}^{p}\) as \(\overline{\operatorname{Conv}} \mathbb{R}^{p}\).

\subsection{Local and global minima of a convex function}\label{sec:local-global}

For a (un)constrained minimization problem on a convex set \(C \subseteq \mathrm{dom} f\) with a function \(f : C \to \mathbb{R}\),
\begin{equation}
  \min_{x \in C} f(x) ,
  \label{eq-minpb}
\end{equation}
we say that \(x^\star\) is

\begin{itemize}
\item a \emph{local solution} of~\eqref{eq-minpb}, if there exists a neighborhood \(\mathcal{O}\) of \(x^\star\) such that for all \(x \in C \cap \mathcal{O}\), \(f(x) \geq f(x^\star)\);

\item a \emph{(global) solution} if for all \(x \in C\), \(f(x) \geq f(x^\star)\).
\end{itemize}

A fundamental result is that, \textbf{when \(f\) is convex}, every local solution of \eqref{eq-minpb} is global solution, and the set of (global) solutions is a convex set.

\begin{thm} \label{thm-local-global-convex-solution}
Assume that \(f\) is a convex function and \(C\) is a convex \textbf{closed} set.
Then,

\begin{itemize}
\item Any local solution of \eqref{eq-minpb} is a global solution;
\item The set of global solutions of \eqref{eq-minpb} is convex.
\end{itemize}
\end{thm}

\begin{proof}
Part 1.
By contradiction.
Consider a local solution \(x^\star\) and assume that \(x^\star\) is not a global solution.
In particular, there exists \(z \in C\) such that \(f(z) < f(x^\star)\).
By convexity,
$$
f((1 - t) x^\star + t z) \leq (1-t) f(x^\star) + t f(z) < f(x^\star) \quad \forall t \in [0,1]
$$
Given any open neighborhood \(\mathcal{O}\) of \(x^\star\), there exists \(t > 0\) such that \((1-t) f(x^\star) + t f(z) < f(x^\star)\) (contradiction).

Part 2.
Take two global solutions, and study the segment joining it: let \(x^\star\) and \(z\) two solutions.
We have \(f(x^\star) = f(z)\), and in turn,
$$
f(x^\star) \leq f((1 - t) x^\star + t z) \leq (1-t) f(x^\star) + t f(z) = f(x^\star),
$$
where the first inequality comes from the equality of the function at \(x^\star\) and \(z\), and the second by convexity.
\end{proof}

\subsection{Differentiable properties of a convex function}\label{sec:differentiable}

A differentiable function is convex if, and only if, it is above all its tangents, see Figure \ref{fig-convex-tangent}.

\begin{figure}[htbp]
\centering
\includesvg[width=.9\linewidth]{a-first-look-at-convex-analysis-convex_tangent.svg}
\caption{\label{fig-convex-tangent}A differentiable convex function and its tangent. The curve is always above its tangent in red.}
\end{figure}

\begin{prop}\label{prop-convex-diff}
Let \(f\) be a differentiable function on an open set \(\Omega \subseteq \mathbb{R}^{p}\), and \(C \subseteq \Omega\) a convex subset of \(\Omega\).
Then \(f\) is convex on \(C\) if, and only if,
\begin{equation}
    \forall x, \bar x \in C,\quad
    f(x) \geq f(\bar x) + \langle{\nabla f(\bar x)},{x-\bar x}\rangle .
    \label{eq-convex-diff}
\end{equation}
\end{prop}
\begin{proof}
Assume \(f\) is convex on \(C\).
Let \(x, \bar x \in C\) and \(\lambda \in (0,1)\).
By definition of convexity, we have
$$ f(\lambda x + (1-\lambda)\bar x) - f(\bar x) \leq \lambda (f(x) - f(\bar x)) . $$
Dividing by \(\lambda\), and letting \(\lambda\) goes to 0, we obtain \eqref{eq-convex-diff}.

Reciprocally, let \(x,y \in C\), \(\lambda \in (0,1)\) and define \(z = \alpha x + (1-\alpha) y \in C\).
Applying \eqref{eq-convex-diff} twice, we have
\begin{align*}
    f(x) &\geq f(z) + \langle{\nabla f(z)},{x-z}\rangle \\
    f(y) &\geq f(z) + \langle{\nabla f(z)},{y-z}\rangle .
\end{align*}
Using a convex combination of these two lines, we get
$$
    \alpha f(x) + (1-\alpha) f(y)
    \geq
    f(z) + \langle{\nabla f(x)},{\alpha x + (1-\alpha)y - z}\rangle ,
$$
which is exactly \eqref{eq-convex-function}.
\end{proof}

A similar criterion can be derived for strictly convex function.
Remark that Theorem \ref{thm-local-global-convex-solution} is a direct consequence of Proposition \hyperref[prop-convex-diff]{prop-convex-diff} for the class of differentiable convex functions: a local minima \(x^{\star}\) satisfies \(\nabla f(x^{\star}) = 0\) and thus \eqref{eq-convex-diff} gives \(f(x) \geq f(x^{\star})\) for all \(x \in C\).

\section{Strongly convex functions}\label{sec:strongly}

A strongly convex function satisfies a stronger statement of the Jensen's inequality.

\begin{defn}
\label{def-strongly-convex-function}
A function \(f: \mathbb{R}^{n} \to \overline{\mathbb{R}}\) is \emph{strongly convex} of modulus \(\mu > 0\) if \(\mathrm{dom} f\) is convex and
\begin{equation*}
    f(\lambda x + (1-\lambda) y) \leq \lambda f(x) + (1-\lambda) f(y)
    - \frac12 \mu \lambda(1-\lambda) \|x-y\|^{2} ,
\end{equation*}
for all \(x,y \in \mathrm{dom} f\) and \(\lambda \in [0,1]\).
\end{defn}

Another way to define strongly convex function is to say that \(f\) is \(\mu\)-strongly convex if the function
$$
  x \mapsto f(x) - \frac{\mu}{2} \|x\|^{2}
$$
is a convex function.

A strongly convex function defined on the whole space \(\mathbb{R}^{d}\) has a \textbf{unique} minimizer.

\subsection{Differentiability, strong convexity and quadratic lower bound}\label{sec:strongly-differentiable}

A function \(f\) is strongly convex if, and only if, it is \emph{strictly above} its tangent, and you can ``fit'' a quadratic form between the tangent and the function itself.
This is a key property to defined lower bounds on \(f\).

\begin{figure}[htbp]
\centering
\includesvg[width=.9\linewidth]{a-first-look-at-convex-analysis-strongly_convex_tangent.svg}
\caption{\label{strongly_convex_tangent}Strong convexity and differentiability. There is space for a quadratic form between the curve \(y = f(x)\) and the tangent.}
\end{figure}

\begin{prop}\label{prp-lower-bound-strongly-convex-function}
Let \(f\) be a differentiable and \(\mu\)-strongly convex function. Then,
$$
\forall x, \bar x \in \mathrm{dom} f,\quad
f(x) \geq f(\bar x) + \langle {\nabla f(\bar x)},{x-\bar x}\rangle + \frac{\mu}{2}\|x - \bar x\|^{2} .
$$
\end{prop}

Note that if \(f\) is \(C^{2}\), \(f\) is \(\mu\)-strongly convex if, and only if, its Hessian \(\nabla^{2} f \geq \mu \mathrm{Id}\), i.e., is definite positive.

An easy consequence is that it is possible to establish a lower bound on the values based on a lower bound on the distance between points:
\begin{equation}
  f(x) \geq f(x^{\star}) + \frac{\mu}{2}\|x - x^{\star} \|^{2} ,
  \label{eq-lower-bound-min-strongly-convex}
\end{equation}
where \(x^{\star}\) is the minimizer of \(f\).

\section{Lipschitz continuity of the gradient}\label{sec:lipschitz}

\begin{defn}\label{def-grad-smooth}
A differentiable function \(f: \mathbb{R}^{n} \to \mathbb{R}\) is said to be \(L\)-smooth if \(\nabla f\) is \(L\)-Lipschitz, i.e.,
$$
    \forall x, y \in \mathrm{dom} f, \quad
    \| \nabla f(x) - \nabla f(y) \|_{*} \leq L \| x - y \| .
$$
Here \(\| \cdot \|_{*}\) is the dual norm of \(\|\cdot\|\).
\end{defn}

\subsection{Quadratic upper bound}\label{sec:quadratic-upper}
\(L\)-smoothness is important in optimization because it ensures a quadratic upper bound of the function.

\begin{prop}\label{prp-grad-smooth-upper-bound}
Let \(f\) a \(L\)-smooth function.
Then, for all \(x, y \in \mathrm{dom}f\),
\begin{equation}
    \langle \nabla f(x) - \nabla f(y), x-y \rangle \leq L \|x-y\|^{2} .
    \label{eq-lsmooth-cs}
\end{equation}
Moreover, if \(\mathrm{dom}f\) is convex, then \eqref{eq-lsmooth-cs} is equivalent to
\begin{equation}
f(y) \leq f(x) + \langle \nabla f(x), y-x \rangle + \frac{L}{2} \| x-y \|^{2},
\quad
\forall x, y \in \mathrm{dom}f .
\label{eq-lsmooth-upper}
\end{equation}
\end{prop}

\begin{proof}
The fact that \(L\)-smoothness implies \eqref{eq-lsmooth-cs} is a direct application of the (generalized) Cauchy-Schwarz inequality.
For the equivalence of \eqref{eq-lsmooth-cs} and \eqref{eq-lsmooth-upper}, let's prove the two direction.

Given \(x, y \in \mathrm{dom}f\), define the real function \(g(t) = f(x + t(y-x))\).
Assuming \eqref{eq-lsmooth-cs} holds, then
\begin{equation*}
  g'(t) - g'(0) = \langle
  \nabla f(x + t(y-x)) - \nabla f(x),
  y - x
  \rangle
  \leq
  t L \| x - y \|^{2} .
\end{equation*}

Now,
\begin{align*}
  f(y) = g(1) = g(0) + \int_{0}^{1} g'(t)
  &\leq g(0) + g'(0) + \frac{L}{2} \| x - y \|^{2} \\
  &= f(x) + \langle \nabla f(x), y-x \rangle + \frac{L}{2} \| x-y \|^{2} .
\end{align*}

Reciprocally, if \eqref{eq-lsmooth-cs} holds, it is sufficient to apply it twice (to \(x,y\) and \(y,x\)) and combine the two equations.
\end{proof}

This result has a strong implication on the minima of \(f\).

\begin{prop}\label{prp-grad-smooth-minima}
Let \(f\) be a \(L\)-smooth function with full domain, and assume \(x^{\star}\) is a minimizer of \(f\).
Then,
$$
    \frac{1}{2L} \| \nabla f(z) \|_{*}^{2}
    \leq f(z) - f(x^{\star}) \leq
    \frac{L}{2} \| z - x^{\star} \|^{2}
    \quad
    \forall z \in \mathbb{R}^{n} .
$$
\end{prop}

\begin{proof}
The two side are proved separately.

\textbf{rhs}: Apply \eqref{eq-lsmooth-cs} applied to \((x^{\star}, z)\).

\textbf{lhs}: Minimize the quadratic upper bound for \(x = z\):
\begin{align*}
    f(x^{\star}) = \min_{y \in \mathbb{R}^{n}} f(y)
    &\leq \inf_{y} \left( f(z) + \langle \nabla f(z), y - z \rangle + \frac{L}{2} \| y - z \|^{2} \right) \\
    &= \inf_{\|v\|=1} \inf_{t} \left( f(z) + t \langle \nabla f(z), v \rangle + \frac{Lt^{2}}{2} \right) ,
\end{align*}
where the last inequality is obtained by the change of variable \(v = \frac{w}{\|w\|}\), \(t = \|w\|\) and \(w = y-z\).
Factorizing the trinom in \(t\) leads to:
\begin{equation*}
    f(z) + t \langle \nabla f(z), v \rangle + \frac{Lt^{2}}{2} =
    \frac{L}{2} \left( t + \frac{1}{L} \langle \nabla f(z), v \rangle \right)^{2}
    - \frac{1}{2L} \langle \nabla f(z), v \rangle^{2} + f(z) .
\end{equation*}
Hence,
\begin{equation*}
    \min_{y \in \mathbb{R}^{n}} f(y) \leq
    \inf_{\|v\|=1} \left( f(z) - \frac{1}{2L} \langle \nabla f(z), v \rangle^{2} \right) .
\end{equation*}
Minimizing the infimum boils down to maximizing \(\langle \nabla f(z), v \rangle^{2}\), that is obtained with \(v = \nabla f(z)\), hence the result.
\end{proof}

\subsection{Co-coercivity of the gradient of a \(L\)-smooth function}\label{sec:cocoercivity}

Convex \(L\)-smooth functions are co-coercive.
This result is sometimes coined Baillon--Haddad theorem (Baillon, Jean-Bernard and Haddad, Georges, 1977), but one shall note that the original contributionis much more general than its application to the gradient.

\begin{prop}
\label{prp-grad-smooth-cocoercive}
Let \(f\) be a full-domain convex \(L\)-smooth function.
Then, \(\nabla f\) is \(1/L\)-co-coercive, i.e.,
$$
    \forall x, y \in \mathbb{R}^{n},\quad
    \langle \nabla f(x) - \nabla f(y), x-y \rangle
    \geq \frac{1}{L} \| \nabla f(x) - \nabla f(y) \|_{*}^{2} .
$$
\end{prop}

\begin{proof}
Let \(f_{x}(z) = f(z) - \langle \nabla f(x), z \rangle\) and \(f_{y}(z) = f(z) - \langle \nabla f(y), z \rangle\).
The two are convex.

Since \(f\) is \(L\)-smooth, \(f_{x}\) and \(f_{y}\) are also \(L\)-smooth.

Canceling the gradient of \(f_{x}\) shows that \(z = x\) minimizes \(f_{x}\).
Hence, using the quadratic upper bound, we have
\begin{align*}
    f(y) - f(x) - \langle \nabla f(x), x-y \rangle
    &= f_{x}(y) - f_{x}(x)\\
    &\geq \frac{1}{2L} \| \nabla f_{x}(y) \|_{*}^{2} \\
    &= \frac{1}{2L} \| \nabla f(y) - \nabla f(x) \|_{*}^{2} .
\end{align*}

Doing exactly the same thing for \(f_{y}\) leads a similar bound, and combining the two gives the result.
\end{proof}

It turns out that smoothness, co-coercivity and upper quadratic boundness are equivalent properties for full-domain convex function.

\begin{prop}\label{prp-grad-smooth-coco-upper}
Let \(f\) be a differentiable convex function with \(\mathrm{dom} f = \mathbb{R}^{n}\).
Then the three following properties are equivalent:

\begin{enumerate}
\item \(f\) is \(L\)-smooth.

\item The quadratic upper bound \eqref{eq-lsmooth-upper} holds.

\item \(\nabla f\) is \(1/L\)-co-coercive.
\end{enumerate}
\end{prop}

\begin{proof}
The only one to prove is 2. \(\implies\) 3. (by Cauchy-Schwarz).
\end{proof}

For the special case of the \(\ell^{2}\) norm, we have:

\begin{prop}\label{prp-grad-smooth-l2case}
Let \(f\) be a differentiable convex function with \(\mathrm{dom} f = \mathbb{R}^{n}\), and \(L\)-smooth with respect to the Euclidean norm.
Then,

\begin{enumerate}
\item \(L \mathrm{Id} - \nabla f\) is monotone, i.e.
\end{enumerate}
$$
    \forall x,y \in \mathbb{R}^{n}, \quad \langle \nabla f(x) - \nabla f(y), x - y \rangle \leq L \| x - y \|_{2}^{2} .
$$

\begin{enumerate}
\item \(\frac{L}{2} \| x \|_{2}^{2} - f(x)\) is convex.

\item If \(f\) is twice differentiable, then,
\end{enumerate}
$$
    \lambda_{\mathrm{max}}(\nabla^{2} f(x)) \leq L, \quad \forall x \in \mathbb{R}^{n} .
$$
\end{prop}

When \(f\) is both \(L\)-smooth and \(\mu\)-strongly convex, we have the following ``strenghened'' co-coercivity.

\begin{prop}\label{prp-smooth-strongly-coco}
Let \(f\) be a \(L\)-smooth and \(\mu\)-strongly convex function.
For any \(x, y \in \mathbb{R}^{n}\), we have
\begin{equation*}
    \langle{\nabla f(x) - \nabla f(y)},{x-y}\rangle \geq
    \frac{\mu L }{\mu + L} \|x-y\|^{2}
    + \frac{1}{\mu + L} \|\nabla f(x) - \nabla f(y)\|^{2} .
\end{equation*}
\end{prop}

\begin{proof}
Consider the convex function \(\phi(x) = f(x) - \frac{\mu}{2} \|{x}\|^{2}\).
Its gradient reads \(\nabla \phi(x) = \nabla f(x) - \mu x\).
Using the \(L\)-smoothness of \(f\), we have that
\begin{align*}
    \langle{\nabla \phi(x) - \nabla \phi(y)},{x-y}\rangle
    &= \langle{\nabla f(x) - \nabla f(y)},{x-y}\rangle - \mu\langle{x-y},{x-y}\rangle \\
    &\leq (L-\mu) \|{x-y}\|^{2} .
\end{align*}
Hence, \(\phi\) is \((L-\mu)\)-smooth.

If \(L=\mu\), then nothing is left to prove since \(f\) is \(\mu\)-strongly convex.
Otherwise, the \((L-\mu)\)-co-coercivity of \(\phi\) (Proposition \ref{prp-grad-smooth-cocoercive}) gives us
$$
    \langle{\nabla \phi(x) - \nabla \phi(y)},{x-y}\rangle \geq
    \frac{1}{L-\mu} \|{\nabla \phi(x) - \nabla \phi(y)}\|^{2} .
$$
Explicing the expression of \(\nabla \phi(x)\) allows us to conclude.
\end{proof}

\noindent
Baillon, Jean-Bernard and Haddad, Georges (1977). \emph{Quelques propriétés des opérateurs angle-bornés etn-cycliquement monotones}.

\noindent
Hiriart-Urruty, Jean-Baptiste and Lemarechal, Claude (1996). \emph{Convex {{Analysis}} and {{Minimization Algorithms I}}: {{Fundamentals}}}, {Springer}.
\end{document}
