\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{Means of convergence}

\begin{document}

\begin{frame}
  \maketitle
\end{frame}

\begin{frame}
  \frametitle{Mean of convergence}

  \FourQuad{%
    \textbf{Convergence in norms of the iterates.}
    Distance to \alert{a} minimizer:
    \[
      r^{(t)} = \norm{x^{(t)} - x^{\star}} \leq \epsilon .
    \]
  }{%
    \textbf{Convergence to the set of minimizers.}
    Distance to \alert{any} minimizer:
    \[
      r^{(t)} = d(x^{(t)}, \Ss) = \inf_{x^{\star} \in \Ss} \norm{x^{(t)} - x^{\star}} \leq \epsilon ,
    \]
    where $\Ss$ is the set of minimizer.
  }{%
    \textbf{Convergence in value (0-order).}
    Infimum value $f^{*} = \inf_{x \in \dom f} f(x)$
    \[
      r^{(t)} = f(x^{(t)}) - f^{*} \leq \epsilon,
    \]
  }{%
    \textbf{First-order convergence.}
    If $f$ is differentiable,
    \[
      r^{(t)} = \norm{\nabla f(x^{(t)})} \leq \epsilon .
    \]
  }
  \note{
    \begin{itemize}
    \item Convergence in norm: for a \emph{given} norm and a \emph{given} solution
    \item The idea is to use the first-order condition, and say that the more $\nabla f(x^{(t)})$, the closer we are from a local minima/saddle point of $f$ if $f$ is nonconvex, and closer from a global minima if $f$ is convex.
    \end{itemize}
  }
\end{frame}

\begin{frame}
  \frametitle{Rate vs Complexity}

  \begin{itemize}
    \item \textbf{Sublinear rates}
    \[
      r^{(t)} \leq c t^{-\alpha}, \quad c>0 \text{ and } \alpha > 0
    \]
    with complexity bound $(\frac{c}{\epsilon})^{1/\alpha}$
    \item \textbf{Linear rates}
    \[
      r^{(t)} \leq c e^{-qt}, \quad c>0 \text{ and } q \in [0,1)      
    \]
    with complexity bound $\frac{1}{q}(\log c + \log \frac{1}{\epsilon})$
    \item \textbf{Superlinear rates} (\eg quadratic)
    \[
      r^{(t)} \leq c (r^{(t)})^2, \quad c>0
    \]
    with complexity bound $\log c + \log \log \frac{1}{\epsilon}$ (1 iteration = double precision)
  \end{itemize}
\end{frame}

\end{document}