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

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

\author{Samuel Vaiter}
\date{}
\institute{
Created: 2023-11-08.\\
Last update: 2023-11-08.\\
Status: inprogress.}
\title{Strongly convex function}

\begin{document}

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

\begin{frame}
  \frametitle{Strongly convex function}

  \begin{columns}[T]
    \begin{column}{0.75\linewidth}
      Convex function
      \[ f(\lambda x + (1-\lambda) y) \leq \lambda f(x) + (1-\lambda) f(y) \]
    \end{column}
    \begin{column}{0.25\linewidth}
      \begin{tikzpicture}
        \draw[->,very thin] (-1.5,0) -- (1.5,0) node[right] {$x$};
        \draw[->,very thin] (0,-0.5) -- (0,1.5) node[right] {$\exp(x)$};

        % Absolute value
        \draw[scale=0.3,domain=-3:1.5, smooth, variable=\x] plot ({\x}, {exp(\x)});
      \end{tikzpicture}
    \end{column}
  \end{columns}
  \begin{columns}[b]
    \begin{column}{0.75\linewidth}
      \begin{definition}
        $f$ is a strongly convex function \alert{of modulus $\mu > 0$} if
        \[
          f(\lambda x + (1-\lambda) y) \leq \lambda f(x) + (1-\lambda) f(y)
          \alert{- \frac12 \mu \lambda(1-\lambda) \norm{x-y}^{2}}
        \]
        for all $x,y \in \dom f$, $\lambda \in [0,1]$.
      \end{definition}

      $f$ $\mu$-strongly convex $\Leftrightarrow$ $f - \frac{\mu}{2} \norm{\cdot}_{2}^{2}$ convex.\\
      $f$ $\mu$-strongly convex $\Rightarrow$ $f$ has a unique minimizer.
    \end{column}
    \begin{column}{0.25\linewidth}
      \begin{tikzpicture}
        \draw[->,very thin] (-1.5,0) -- (1.5,0) node[right] {$x$};
        \draw[->,very thin] (0,-0.5) -- (0,1.5) node[right] {$x^{2}$};

        % Double curve
        \draw[scale=0.3,domain=-2:2, smooth, variable=\x] plot ({\x}, {\x*\x});
      \end{tikzpicture}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Strong convexity and differentiability}
  \begin{proposition}
    A differentiable function $f$ is $\mu$-strongly convex, with $\mu > 0$, iff
    \[
      \forall x, \bar x \in \dom f,\quad
      f(x) \geq f(\bar x) + \dotp{\nabla f(\bar x)}{x-\bar x} + \frac{\mu}{2}\norm{x - \bar x}^{2}
    \]
  \end{proposition}

  \begin{center}
    \begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-0.7,xscale=0.7]
      % that's cheating because it is cubic ...
      \coordinate (fx) at (171,163);
      \coordinate (x) at (171,241);
      % Axis
      \draw[->] (50,241) -- (389,241);
      \draw[->] (83.9,261.84) -- (83.9,56);
      % f(x)
      \draw (143,55.84) .. controls (131.72,93.08) and (139.9,143.22) .. (fx) .. controls (202.1,182.78) and (317.05,182.56) .. (342,163.84) node[right] {$f(x)$};
      % tangent
      \draw (90,115) -- (278.67,228.33) node[right] {$f(\bar x) + \dotp{\nabla f(\bar x)}{x - \bar x}$};
      % quadratic
      \draw[red,thick] (83.33,21.67) node[anchor=north west] {$f(\bar x) + \dotp{\nabla f(\bar x)}{x-\bar x} + \frac{\mu}{2}\norm{x - \bar x}^{2}$} .. controls (74,55) and (139.9,143.22) .. (171,163) .. controls (202.1,182.78) and (367.05,216.38) .. (392,197.67);
      % (bar x, f(bar x))
      \draw[dotted] (fx) -- (x) node[below] {$\bar x$};
      \fill (fx) circle (2pt) node[anchor=south west] {$f(\bar x)$};
    \end{tikzpicture}
  \end{center}
  \note{
    \begin{itemize}
    \item A function $f$ is strongly convex if, and only if, it is \emph{stricly above} its tangent, and you can ``fit'' a quadratic form between the tangent and the function itself.
    \item This is a key property to defined lower bounds on $F$.
    \end{itemize}
  }
\end{frame}

\begin{frame}
  \frametitle{Strong convexity $\implies$ lower bounds}
  \begin{proposition}
    If $f$ is $\mu$-strongly convex and differentiable, then the following lower bound holds
    \[
      \forall x \in \RR^{d}, \quad
      f(x) \geq f(x^{\star}) + \frac{\mu}{2}\norm{x - x^{\star}}^{2}
    \]
    where $x^{\star} = \argmin f$.
  \end{proposition}

  \begin{center}
    \begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-0.7,xscale=0.7]
      % Axis
      \draw[->] (50,241) -- (389,241);
      \draw[->] (83.9,261.84) -- (83.9,56);
    \end{tikzpicture}
    {\tiny (live)}
  \end{center}
\end{frame}


\end{document}