\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{Descent direction}

\begin{document}

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


\begin{frame}
  \frametitle{Descent direction}

  \textbf{Iterative algorithm}
  \[
    x^{(t+1)} = x^{(t)} + \eta^{(t)} u^{(t+1)}
  \]

  \begin{columns}[c]
    \begin{column}{0.7\linewidth}
      \includegraphics[width=\linewidth]{figures/random_directions}
    \end{column}
    \begin{column}{0.3\linewidth}
      \begin{align*}
        u^{(t+1)} &\sim \Uu(-1,1) \\
        \eta^{(t)} &= 0.6  \\
      \end{align*}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Descent direction}

  \begin{columns}
    \begin{column}{0.5\linewidth}
      \textbf{Iterative algorithm}
      \[
        x^{(t+1)} = x^{(t)} + \eta^{(t)} u^{(t+1)}
      \]

      \textbf{Choice of direction?}
      how to ``optimaly choose'' the direction $u^{(t+1)}$ such that $x^{(t+1)}$ is closer to a minimum of $f$?
      \pause
      \begin{definition}
        A \emph{descent direction} $u \in \RR^{d}$ of $f$ at $x \in \RR^{d}$ is vector such that
        \[
          \exists \epsilon > 0,
          \forall \eta \in (0, \epsilon),
          \quad
          f(x + \eta u) < f(x) .
        \]
      \end{definition}
    \end{column}
    \begin{column}{0.5\linewidth}
      \begin{center}
        \includegraphics[width=\linewidth]{figures/descent_cone}
      \end{center}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Descent direction: differentiable case}

  \textbf{Descent direction}: $\exists \epsilon > 0, \forall \eta \in (0, \epsilon), \quad f(x + \eta u) < f(x)$

  \textbf{Characterization}: $\dotp{\nabla f(x)}{u} < 0$ \hfill{(\footnotesize for $f$ differentiable)}
  \begin{center}
    Why?
  \end{center}
  \pause
  \begin{proposition}[Antigradient is the steepest direction]
    Let $f: \RR^{d} \to \RR$ be a differentiable function at $\bar x \in \RR^{d}$.
    Then, the problem
    \[
      \min_{\norm{u} = 1} \dotp{\nabla f(\bar x)}{u}
    \]
    has a unique solution $u^{\star} = - \frac{\nabla f(\bar x)}{\norm{\nabla f(\bar x)}}$ .
  \end{proposition}
  \textbf{Proof idea}: study $\phi_{u}(t) = f(\bar x + \eta u)$.
\end{frame}

\end{document}