\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-10.\\
Last update: 2023-11-10.\\
Status: inprogress.}
\title{Constant stepsize gradient descent on smooth convex function}

\begin{document}

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


\begin{frame}
  \frametitle{Convex $L$-smooth function}

  \begin{proposition}
    Let $f: \RR^{d} \to \RR$ be a \alert{convex $L$-smooth} function.
    For any initial guess $x^{(0)}$, the GD iterates $x^{(t)}$ with step-size $\eta^{(t)} = \eta \in (0,\frac{2}{L})$ converge towards \alert{an optimal point} $x^{\star}$ of $f$, and moreover
    \[
      f(x^{(t)}) - f^{\star} \leq
      \frac{
        2(f(x^{0}) - f^{\star}) \norm{x^{(0)} - x^{\star}}^{2}
      }{
        t \eta (2 - L \eta) (f(x^{0}) - f^{\star}) + 2 \norm{x^{(0)} - x^{\star}}^{2}
      } .
    \]
    Moreover, if $\eta = \frac{1}{L}$, then
    \[
      f(x^{(t)}) - f^{\star} \leq
      \frac{2 L \norm{x^{(0)} - x^{\star}}^{2}}{t + 4} .
    \]
  \end{proposition}

  Proof based on the co-coercivity of the gradient.
\end{frame}

\begin{frame}
  \frametitle{Co-coercivity of $\nabla f$}

  This result is sometimes coined Baillon--Haddad theorem.
  \begin{proposition}
    Let $f$ be a full-domain convex \(L\)-smooth function.
    Then, $\nabla f$ is \(1/L\)-co-coercive, i.e.,
    \[\forall x, y \in \mathbb{R}^{n},\quad
      \langle \nabla f(x) - \nabla f(y), x-y \rangle
      \geq \frac{1}{L} \| \nabla f(x) - \nabla f(y) \|^{2} .
    \]
  \end{proposition}
\end{frame}

\end{document}