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

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

\usepackage[noend]{algpseudocode}
\usepackage{listings}
\lstdefinestyle{chack}{
  language=C,
  columns=fullflexible,
  keepspaces=true,
  numbers=left,
  basicstyle=\ttfamily\footnotesize\color{black},
  commentstyle=\ttfamily\footnotesize\color{gray},
  moredelim=**[is][\color{red}]{@}{@},
}

\author{Samuel Vaiter}
\date{}
\institute{
Created: 2023-11-09.\\
Last update: 2023-11-09.\\
Status: inprogress.}
\title{Oracle gradient descent on coercive non-convex function}

\begin{document}

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


\begin{frame}
  \frametitle{Gradient descent: oracle step-size}
  \begin{columns}[T]
    \begin{column}{0.6\linewidth}
      \begin{tcolorbox}[fonttitle=\bfseries, title={Gradient Descent algorithm}]
        \begin{algorithmic}[1]
          \Require{Initialization $x^{(0)} \in \RR^{d}$, $\quad\quad\quad$ step-size policy $\eta^{(t)} > 0$.}
          \For{$t = 1, \cdots$}
          \begin{equation}
            \label{eq:gradient-descent}\tag{GD}
            x^{(t+1)} = x^{(t)} - \alert{\eta^{(t)}} \nabla f(x^{(t)})
          \end{equation}
          \EndFor
        \end{algorithmic}
      \end{tcolorbox}
      \begin{itemize}
      \item Constant step-size $\eta^{(t)} = \eta$
      \item Predetermined function $\eta^{(t)} = f(t)$
      \alert{\item ``Oracle''}
      \item Backtracking
      \end{itemize}
    \end{column}
    \begin{column}{0.4\linewidth}
      \textbf{Oracle step-size} {\tiny $\equiv$ best choice}
      \[
        \eta^{(t)} = \uargmin{\eta \geq 0} \underbrace{f(x^{(t)} - \eta \nabla f(x^{(t)}))}_{\eqdef \phi(\eta)} .
      \]
      \begin{center}
        \begin{tikzpicture}
          \draw[->] (0,0) -- (3,0) node[right] {$\eta$};
          \draw[->] (0,0) -- (0,2) node[right] {$\phi(\eta)$};
          \draw[domain=0:3, smooth, variable=\x] plot ({\x}, {2.2-1.8*exp(-(\x-1)^2)});
          \draw[dotted] (1,2.2) -- (1,0) node[below] {$\eta^{(t)}$};
        \end{tikzpicture}
      \end{center}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Convergence of GD for coercive $C^1$ functions}

  \begin{proposition}
    Let $f: \RR^{d} \to \RR$ be a coercive function and assume moreover that it is continuously differentiable.
    For any initial guess $x^{(0)}$, the \alert{oracle} GD iterates $x^{(t)}$ converge \alert{up to a subsequence} towards a \alert{critical point} of $f$.
  \end{proposition}
  \textbf{Remarks}:
  \begin{itemize}
    \item \emph{no} rate!
    \item If $f$ has a unique critical point, then GD converges towards it (exercice).
  \end{itemize}
  \metroset{block=transparent}
  \begin{block}{Proof idea}
    \begin{enumerate}
      \item The value sequence is (strictly)decreasing (unless it reaches a critical point).
      \item The iterates sequence is converging (up to a subsequence).
      \item The limit of the iterates sequence is a critical point.
    \end{enumerate}
  \end{block}
  \metroset{block=fill}  
\end{frame}


\end{document}