\documentclass[t,aspectratio=169]{beamer}
\usetheme{metropolis}
\metroset{block=fill}

\input{../../_assets/basicslide1}
\input{../../_assets/macros}

\author{Samuel Vaiter}
\date{}
\institute{
Created: 2023-11-07.\\
Last update: 2023-11-07.\\
Status: finished.}
\title{What is optimization ?}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
  \frametitle{Optimization?}

  \begin{block}{Optimization problem}
    \begin{equation*}
      \alt<1>{\inf}{\alert<2>{\min}}
      {\color{DarkestKelly}f({\color{DarkestRuby}x})}
      \quad \text{subject to} \quad {\color{DarkestRuby}x} \in {\color{DarkestDaisy}\Omega} ,
    \end{equation*}
  \end{block}

  \begin{itemize}
  \item Domain ${\color{DarkestDaisy}\Omega} \subseteq \Xx$.
  \item Optimization variable ${\color{DarkestRuby}x}$.
  \item Cost {\footnotesize (or objective, energy, loss)} function ${\color{DarkestKelly}f}: {\color{DarkestDaisy}\Omega} \to \RR$.
  \item<2-> Optimal solution\only<2>{\alert{(s)}}
    \[
      x^{\star} \alt<3>{\alert{=}}{\in} \argmin
      {\color{DarkestKelly}f({\color{DarkestRuby}x})}
      \quad \text{subject to} \quad {\color{DarkestRuby}x} \in {\color{DarkestDaisy}\Omega} ,
    \]
  \end{itemize}

  \begin{center}
    \alert<2>{Existence}? \alert<3>{Uniqueness}? \alert<4>{Algorithm}?
  \end{center}
\end{frame}

\subsection{Examples}

\begin{frame}
  \frametitle{Example: Toy examples}
  \begin{center}
    \includegraphics[height=0.8\pageheight]{figures/rosenbrock+quad.pdf}
  \end{center}
  \note{Rosenbrock on the left, Quadratic on the right}
\end{frame}

\begin{frame}
  \frametitle{Example: Risk minimization}

  \begin{itemize}
  \item Joint distribution $\PP$ on input $x \in \Xx$, output $y \in \Yy$.
  \item Loss function $\ell: \Yy \times \Yy \to \RR$ {\footnotesize (\eg $\ell^{2}$-norm $\ell(y, y') = (y - y)^{2}$)}.
  \end{itemize}

  \begin{block}{Statistical (or expected) risk}
    \begin{equation*}
      \inf_{\phi: \Xx \to \Yy}
      \Rr(\phi) = \EE_{(x,y) \sim \PP} [\ell(y, \phi(x))] .
    \end{equation*}
  \end{block}

  \begin{itemize}
  \item {\color{DarkestDaisy}Domain}: (Measurable) functions from inputs $\Xx$ to outputs $\Yy$.
  \item {\color{DarkestRuby}Variable}: prediction function $\phi: \Xx \to \Yy$.
  \item {\color{DarkestKelly}Cost}: expected statistical risk $\Rr$.
  \end{itemize}

  \begin{center}
    \footnotesize Check your statistical learning 101 class!
  \end{center}
\end{frame}

\begin{frame}
  \frametitle{Example: \alert{Empirical} Risk minimization}

  \begin{itemize}
  \item \alert{$n$ examples in a training set $(x_{i},y_{i}) \in \Xx \times \Yy$}.
  \item Loss function $\ell: \Yy \times \Yy \to \RR$ {\footnotesize (\eg $\ell^{2}$-norm $\ell(y, y') = (y - y)^{2}$)}.
  \end{itemize}

  \begin{block}{Empirical risk minimization (ERM)}
    \begin{equation*}
      \inf_{\phi: \Xx \to \Yy}
      \hat \Rr(\phi) = \frac{1}{n} \sum_{i=1}^{n} \ell(y_{i}, \phi(x_{i})) .
    \end{equation*}
  \end{block}

  \begin{itemize}
  \item {\color{DarkestDaisy}Domain}: (Measurable) functions from inputs $\Xx$ to outputs $\Yy$.
  \item {\color{DarkestRuby}Variable}: prediction function $\phi: \Xx \to \Yy$.
  \item {\color{DarkestKelly}Cost}: expected \alert{empirical} risk $\hat \Rr$.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Example: Portfolio optimization}

  \begin{itemize}
  \item Assets with returns $a = (a_{1},\dots,a_{n}) \in \RR^{n}$.
  \item \alert{Known} expected returns $\mu = (\mu_{1},\dots,\mu_{n})$.
  \item Risk in/between (covariance matrix positive definite) $\Sigma \in \RR^{n \times n}$.
  \end{itemize}

  \begin{block}{Portfolio with minimal variance}
    \[
      \inf_{x \in \RR^{n}} {\color{DarkestKelly}f({\color{DarkestRuby}x})} \eqdef \dotp{\Sigma {\color{DarkestRuby}x}}{{\color{DarkestRuby}x}}
      \quad \text{subject to} \quad
      {\color{DarkestDaisy}
      \begin{cases}
        \EE(\dotp{{\color{DarkestRuby}x}}{a}) = \dotp{{\color{DarkestRuby}x}}{\mu} = r \\
        \dotp{{\color{DarkestRuby}x}}{\mathbf{1}} = 1 .
      \end{cases}}
    \]
  \end{block}

  \begin{itemize}
  \item {\color{DarkestDaisy}Domain}: Portfolio with expected return $\mu$
  \item {\color{DarkestRuby}Variable}: Portfolio ${\color{DarkestRuby}x} \in \RR^{n}$
  \item {\color{DarkestKelly}Cost}: Variance of the portfolio $\dotp{\Sigma {\color{DarkestRuby}x}}{{\color{DarkestRuby}x}}$
  \end{itemize}

  \photoUp{pictures/Markowitz.jpg}{H. Markowitz (1927--)}
\end{frame}

\begin{frame}
  \frametitle{Example: Optimal transport}

  \begin{itemize}
  \item Probability measures $\mu$ on $X$ and $\nu$ on $Y$.
  \item Cost function $c: X \times Y \to \RRb$.
  \end{itemize}

  \begin{block}{Optimal transport (Monge formulation)}
    \begin{equation*}
      \inf_{{\color{DarkestRuby}T}: X \to Y} {\color{DarkestKelly}f({\color{DarkestRuby}T})}
      = \int_{X} c(x,{\color{DarkestRuby}T}(x)) d \mu(x)
      \quad \text{subject to} \quad
      {\color{DarkestDaisy} {\color{DarkestRuby}T}_{\sharp}\mu = \nu} .
    \end{equation*}
  \end{block}

  \begin{itemize}
  \item {\color{DarkestDaisy}Domain}: Set of admissible transport map ${\color{DarkestRuby}T}_{\sharp}\mu = \nu$.
  \item {\color{DarkestRuby}Variable}: Transport map ${\color{DarkestRuby}T}$.
  \item {\color{DarkestKelly}Cost}: Cost of transport from $\mu$ to $\nu$.
  \end{itemize}

  \photoUp{pictures/Monge.jpg}{G. Monge (1746--1818)}

  \note{
    Let $X,Y$ two metric spaces, $\mu$ a Borel measure on $X$ and $T: X \to Y$ a measurable map.
    We recall that the \emph{push-forward} of $\mu$ by $T$ is the measure $T_{\sharp}\mu$ defined by the change-of-variable formula
    \[
      \int_{Y} \phi(y) dT_{\sharp}\mu(y) = \int_{X} \phi(T(x)) d \mu(x) ,
    \]
    for all measurable and bounded $\phi: Y \to R$.
  }
\end{frame}

\end{document}