\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{Constant stepsize gradient descent on smooth non-convex function}

\begin{document}

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


\begin{frame}
  \frametitle{Rate for $L$-smooth functions}

  \begin{proposition}
    Let $f: \RR^{d} \to \RR$ be a \alert{$L$-smooth} function, \alert{bounded from below} by $\bar f \in \RR$.
    For any $x^{(0)}$, the GD iterates $x^{(t)}$ with $\eta^{(t)} = \eta < \frac{2}{L}$ converge towards a \alert{critical point} of $f$,
    \[
      \min_{0 \leq t \leq T} \norm{\nabla f(x^{(t)})}
      \leq
      \frac{1}{\sqrt{T+1}}
      \left(
        \omega^{-1} L (f(x^{(0)} - \bar f))
      \right)^{1/2} ,
    \]
    where $\omega = 2 \alpha (1-\alpha)$ and $\eta = \frac{2\alpha}{L}$.
  \end{proposition}

  \textbf{We cannot say \emph{anything} about the rate of convergence of $f(x^{(t)})$ or $(x^{(t)})_{t \geq 0}$!}

  \metroset{block=transparent}
  \begin{block}{Proof idea}
    \begin{enumerate}
      \item Bound on one step of gradient descent.
      \item Convergence of 1st-order optimality.
      \item Rate of convergence.
    \end{enumerate}
  \end{block}
  \metroset{block=fill}  
\end{frame}

\end{document}