\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{Gradient descent on Ordinary Least Squares}

\begin{document}

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


\begin{frame}
  \frametitle{GD on OLS: Ordinary Least Squares}
  Let \(n, m \geq 1\), \(A \in \mathbb{R}^{n \times p}\) and \(y \in \mathbb{R}^{n}\).

  \textbf{Ordinary Least Squares (OLS)}
  \begin{equation}
    x^{\star} \in \arg\min_{x \in \mathbb{R}^{p}} f(x) = \frac{1}{2n} \| Ax - y \|_{2}^{2} .
  \end{equation}

  \textbf{Gradient}
  \[ \nabla f(x) = \frac{1}{n}A^{\top}(Ax - y) \in \mathbb{R}^{p} , \]
  \textbf{Hessian matrix} {\tiny (constant)} $\rightarrow$ covariance matrix
  \[ \nabla^{2} f(x) = H = \frac{1}{n} A^{\top} A \in \mathbb{R}^{p \times p} . \]

  \textbf{First order condition}: $H x^{\star} = \frac{1}{n} A^{T} y$
\end{frame}

\begin{frame}
  \frametitle{GD on OLS: Convergence in value and in iterates}

  \begin{columns}[T]
    \begin{column}{0.4\linewidth}
      \textbf{Gradient descent}
      \begin{equation*}
        x^{(t+1)} = x^{(t)} - \eta \nabla f(x^{(t)})
      \end{equation*}
    \end{column}
    \begin{column}{0.48\linewidth}
      \begin{minipage}{\linewidth}
        \scriptsize
        \begin{tabular}{ll}
          \textbf{(OLS)} &
          $\arg\min_{x \in \mathbb{R}^{p}} f(x) = \frac{1}{2n} \| Ax - y \|_{2}^{2}$ \\
          Gradient & $\nabla f(x) = \frac{1}{n}A^{\top}(Ax - y) \in \mathbb{R}^{p}$ \\
          Hessian matrix & $\nabla^{2} f(x) = H = \frac{1}{n} A^{\top} A \in \mathbb{R}^{p \times p}$ \\
          Minimizers & $H x^{\star} = \frac{1}{n} A^{T} y$
        \end{tabular}
      \end{minipage}
    \end{column}
  \end{columns}

  \textbf{Convergence in norms of the iterates.}
  Distance to \alert{a} minimizer:
  \[
    r^{(t)} = \norm{x^{(t)} - x^{\star}} \leq \epsilon
  \]
  \textbf{Convergence in value.}
  Infimum value $f^{*} = \inf_{x \in \RR^{n}} f(x)$
  \[
    r^{(t)} = f(x^{(t)}) - f^{*} \leq \epsilon
  \]

\end{frame}

\begin{frame}
  \frametitle{GD on OLS: Explicit expression}

  \begin{columns}[T]
    \begin{column}{0.4\linewidth}
      \textbf{Gradient descent}
      \begin{equation*}
        x^{(t+1)} = x^{(t)} - \eta \nabla f(x^{(t)})
      \end{equation*}
    \end{column}
    \begin{column}{0.48\linewidth}
      \begin{minipage}{\linewidth}
        \scriptsize
        \begin{tabular}{ll}
          \textbf{(OLS)} &
          $\arg\min_{x \in \mathbb{R}^{p}} f(x) = \frac{1}{2n} \| Ax - y \|_{2}^{2}$ \\
          Gradient & $\nabla f(x) = \frac{1}{n}A^{\top}(Ax - y) \in \mathbb{R}^{p}$ \\
          Hessian matrix & $\nabla^{2} f(x) = H = \frac{1}{n} A^{\top} A \in \mathbb{R}^{p \times p}$ \\
          Minimizers & $H x^{\star} = \frac{1}{n} A^{T} y$
        \end{tabular}
      \end{minipage}
    \end{column}
  \end{columns}

  \begin{proposition}
    For all $t \in \NN$, we have
    \begin{equation}\label{eq:linear-unrolled}
      x^{(t)} - x^{\star} = (I - \eta H)^{t} (x^{(0)} - x^{\star}) .
    \end{equation}
  \end{proposition}
  \textbf{Proof idea:} show that $x^{(t)} - x^{\star} = (I - \eta H) (x^{(t-1)} - x^{\star})$
\end{frame}

\begin{frame}
  \frametitle{GD on OLS: Geometrical insight}

  $\mu$ smallest eigenvalue of $H$, $L$ biggest eigenvalue of $H = \frac{1}{n} A^{\top} A$, $0 \leq \mu \leq L$
  \vspace{-1cm}
  \begin{columns}
    \begin{column}{0.5\linewidth}
      \begin{center}
        \includegraphics<1>[height=5.5cm]{figures/quadratic_difficulty_0.pdf}%
        \includegraphics<2>[height=5.5cm]{figures/quadratic_difficulty_gd_0.pdf}
        \[ \kappa = \frac{L}{\mu} \approx 1 \]
      \end{center}
    \end{column}
    \begin{column}{0.5\linewidth}
      \begin{center}
        \includegraphics<1>[height=5.5cm]{figures/quadratic_difficulty_1.pdf}
        \includegraphics<2>[height=5.5cm]{figures/quadratic_difficulty_gd_1.pdf}
        \[ \kappa = \frac{L}{\mu} \gg 1 \]
      \end{center}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{GD on OLS: Convergence in norm}

  \begin{columns}[T]
    \begin{column}{0.4\linewidth}
      \textbf{Closed-form expression}
      \begin{equation*}
        x^{(t)} - x^{\star} = (\Id - \eta H)^{t} (x^{(0)} - x^{\star})
      \end{equation*}
    \end{column}
    \begin{column}{0.48\linewidth}
      \begin{minipage}{\linewidth}
        \scriptsize
        \begin{tabular}{ll}
          \textbf{(OLS)} &
          $\arg\min_{x \in \mathbb{R}^{p}} f(x) = \frac{1}{2n} \| Ax - y \|_{2}^{2}$ \\
          Gradient & $\nabla f(x) = \frac{1}{n}A^{\top}(Ax - y) \in \mathbb{R}^{p}$ \\
          Hessian matrix & $\nabla^{2} f(x) = H = \frac{1}{n} A^{\top} A \in \mathbb{R}^{p \times p}$ \\
          Minimizers & $H x^{\star} = \frac{1}{n} A^{T} y$
        \end{tabular}
      \end{minipage}
    \end{column}
  \end{columns}

  \textbf{Distance to a minimizer}
  \[ \| x^{(t)} - x^{\star} \|^{2} = \langle x^{(0)} - x^{\star} , (\Id - \eta H)^{2t} (x^{(0)} - x^{\star}) \rangle \]


  \textbf{Eigenvalues of $(\Id - \eta H)^{2t}$}
  \[
    \mathrm{eigen}(\Id - \eta H)^{2t} = \setcond{(1-\eta \lambda)^{2t}}{\lambda \in \mathrm{eigen}(H)}
  \]
  \[
    \Downarrow (\text{using the fact } \lambda \in [\mu,L])
  \]
  \[
    \rho \in \mathrm{eigen}(\Id - \eta H)^{2t} \implies |\rho| \leq \left( \max_{\lambda \in [\mu,L]} | 1 - \eta \lambda | \right)^{2t}
  \]
\end{frame}

\begin{frame}
  \frametitle{GD on OLS: Convergence in norm}

  \begin{columns}[T]
    \begin{column}{0.4\linewidth}
      \textbf{Closed-form expression}
      \begin{equation*}
        x^{(t)} - x^{\star} = (\Id - \eta H)^{t} (x^{(0)} - x^{\star})
      \end{equation*}
    \end{column}
    \begin{column}{0.48\linewidth}
      \begin{minipage}{\linewidth}
        \scriptsize
        \begin{tabular}{ll}
          \textbf{(OLS)} &
          $\arg\min_{x \in \mathbb{R}^{p}} f(x) = \frac{1}{2n} \| Ax - y \|_{2}^{2}$ \\
          Gradient & $\nabla f(x) = \frac{1}{n}A^{\top}(Ax - y) \in \mathbb{R}^{p}$ \\
          Hessian matrix & $\nabla^{2} f(x) = H = \frac{1}{n} A^{\top} A \in \mathbb{R}^{p \times p}$ \\
          Minimizers & $H x^{\star} = \frac{1}{n} A^{T} y$
        \end{tabular}
      \end{minipage}
    \end{column}
  \end{columns}

  \textbf{Upper bounds for the distance to a minimizer}
  \[ \| x^{(t)} - x^{\star} \|^{2} = \langle x^{(0)} - x^{\star} , (\Id - \eta H)^{2t} (x^{(0)} - x^{\star}) \rangle \]
  \[ + \]
  \[
    \rho \in \mathrm{eigen}(\Id - \eta H)^{2t} \implies |\rho| \leq \left( \max_{\lambda \in [\mu,L]} | 1 - \eta \lambda | \right)^{2t}
  \]
  \[ \Downarrow (\text{\tiny spectral bound})\]
  \[ \| x^{(t)} - x^{\star} \|^{2} \leq \left( \max_{\lambda \in [\mu,L]} | 1 - \eta \lambda | \right)^{2t} \| x^{(0)} - x^{\star} \|_{2}^{2} . \]
  \pause
  \alert{What if $\mu = 0$?}
\end{frame}

\begin{frame}
  \frametitle{GD on OLS: Convergence in norm}

  \begin{columns}[T]
    \begin{column}{0.5\linewidth}
      \fbox{Case $\mu = 0$}

      $\Leftrightarrow $$H$ is non-invertible.

      \vspace{0.5cm}
      Eigenvector $v$ associated to $\mu=0$
      \[
        \exists v \in \RR^{p}, \quad (I - \eta H)v = v
      \]
      Choose \(x^{\star}\) a minimizer\\
      Initialization $x^{(0)} = v + x^{\star}$.
      \begin{align*}
        &\| x^{(t)} - x^{\star} \|^{2} \\
        =& \langle v + x^{\star} - x^{\star} , (I - \eta H)^{2t} (v + x^{\star} - x^{\star}) \rangle \\
        =& \langle v  , (I - \eta H)^{2t} v \rangle \\
        =& \| v \|_{2}^{2}
      \end{align*}
    \end{column}
    \begin{column}{0.5\linewidth}
      \includegraphics[width=\linewidth]{figures/gd_quadratic_noninvertible}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{GD on OLS: Convergence in norm}

  \fbox{Case $\mu \neq 0$}
  \[
    \| x^{(t)} - x^{\star} \|^{2} \leq \alert{\left( \max_{\lambda \in [\mu,L]} | 1 - \eta \lambda | \right)^{2t}} \| x^{(0)} - x^{\star} \|_{2}^{2} .
  \]

  \only<1>{
    \textbf{Optimal step-size}: solving
    \[
      \min_{\eta > 0} \max_{\lambda \in [\mu,L]} | 1 - \eta \lambda |
      \implies
      \eta^\star = \frac{2}{\mu + L}
      \quad \text{and} \quad
      \max_{\lambda \in [\mu,L]} | 1 - \eta^\star \lambda | = \frac{\kappa - 1}{\kappa + 1} \in (0,1)
    \]

    \begin{center}
      \begin{tikzpicture}
        \draw[->] (0,0) -- (5, 0) node[right] {$\eta$};
        \draw[->] (0,0) -- (0,2);

        \draw (0,1) -- (1,0)  node[below] {$\frac{1}{L}$}-- (3.5,2.5);
        \draw (0,1) -- (3,0) node[below] {$\frac{1}{\mu}$}-- (6, 1) node[above] {$|1 - \eta \mu|$};
        \draw[red,thick] (0,1) -- (1.5,0.5) -- (3.5,2.5) node[right] {$\max \{ |1-\eta L|, |1 - \eta \mu| \}$};
        \draw[red, dotted] (1.5,0.5) -- (1.5,0) node[below] {$\frac{2}{L+\mu}$};
      \end{tikzpicture}
    \end{center}}
  \only<2>{
    \textbf{Choice independant from $\mu$}: $\bar \eta = 1/L$
    \[
      \max_{\lambda \in [\mu,L]} | 1 - \bar \eta \lambda | = 1 - \frac{\mu}{L} = 1 - \frac{1}{\kappa} \in (0,1)
    \]
  }
\end{frame}

\begin{frame}
  \frametitle{GD on OLS: Convergence in norm}

  \begin{proposition}
    Assume that $\min_x \norm{Ax - b}^2$ has a unique minimizer $x^{\star}$.
    Then, the gradient descent iterates $x^{(t)}$ with constant step-size $\eta^{(t)} = \eta = \frac{2}{\mu + L}$ (resp. $\eta = \frac{1}{L}$) converges \alert{linearly} in norm
    \[
      \norm{x^{(t)} - x^{\star}}^{2} \leq
      c^{2t} \norm{x^{(0)} - x^{\star}}^{2} ,
    \]
    where $c = \frac{\kappa - 1}{\kappa + 1}$ (resp. $c = 1 - \frac{1}{\kappa}$.
  \end{proposition}

  \faWarning $\,$ Linear $\equiv$ Exponential $\equiv$ Geometric!

  \textbf{Characteristic time} (case $\eta = 1/L$)
  \[
    \left(1 - \frac{1}{\kappa}\right)^{2t}
    \leq
    \exp\left(-\frac{2t}{\kappa}\right)
  \]
\end{frame}


\begin{frame}
  \frametitle{GD on OLS: Convergence in value}

  \[
    f(x) = \norm{Ax - b}^2
  \]

  \begin{proposition}
    Let $x^{\star}$ any solution of $\min_x f(x)$.
    The gradient descent iterates $x^{(t)}$ with constant step-size $\eta^{(t)} = \eta = \frac{1}{L}$ converges with a sublinear $O(1/t)$ rate
    \[
      f(x^{(t)}) - f(x^{\star}) \leq
      \frac{1}{4t\eta} \norm{x^{(0)} - x^{\star}}_{2}^{2} .
    \]
    If moreover, the solution is unique, the convergence is linear:
    \[
      f(x^{(t)}) - f(x^\star) \leq \left( 1 - \frac{1}{\kappa} \right)^{2t} (f(x^{(0)}) - f(x^\star)) .
    \]
  \end{proposition}
\end{frame}

\begin{frame}
  \frametitle{GD on OLS: Summary}

  \begin{columns}[T]
    \begin{column}{0.4\linewidth}
      \textbf{Closed-form expression}
      \begin{equation*}
        x^{(t)} - x^{\star} = (\Id - \eta H)^{t} (x^{(0)} - x^{\star})
      \end{equation*}
    \end{column}
    \begin{column}{0.48\linewidth}
      \begin{minipage}{\linewidth}
        \scriptsize
        \begin{tabular}{ll}
          \textbf{(OLS)} &
          $\arg\min_{x \in \mathbb{R}^{p}} f(x) = \frac{1}{2n} \| Ax - y \|_{2}^{2}$ \\
          Gradient & $\nabla f(x) = \frac{1}{n}A^{\top}(Ax - y) \in \mathbb{R}^{p}$ \\
          Hessian matrix & $\nabla^{2} f(x) = H = \frac{1}{n} A^{\top} A \in \mathbb{R}^{p \times p}$ \\
          Minimizers & $H x^{\star} = \frac{1}{n} A^{T} y$
        \end{tabular}
      \end{minipage}
    \end{column}
  \end{columns}

  \fbox{Case $\mu = 0 \Leftrightarrow H$ singular}
  \begin{itemize}
    \item \textbf{Norm} no convergence
    \item \textbf{Value} $f(x^{(t)}) - f(x^{\star}) \leq \frac{1}{4t\eta} \norm{x^{(0)} - x^{\star}}_{2}^{2}$
  \end{itemize}

  \fbox{Case $\mu > 0 \Leftrightarrow H$ invertible}
  \begin{itemize}
    \item \textbf{Norm} $\norm{x^{(t)} - x^{\star}}^{2} \leq c^{2t} \norm{x^{(0)} - x^{\star}}^{2}$
    \item \textbf{Value} $f(x^{(t)}) - f(x^\star) \leq \left( 1 - \frac{1}{\kappa} \right)^{2t} (f(x^{(0)}) - f(x^\star))$
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{GD on OLS: Puzzle}

  \begin{columns}[T]
    \begin{column}{0.4\linewidth}
      Ordinary Least Squares (OLS)
      \[ \arg\min_{x \in \mathbb{R}^{p}} f(x) = \frac{1}{2n} \| Ax - y \|_{2}^{2} \]
      Gaussian measurements
      \[ A_{ij} \sim \Nn(0,1), b = 1 \]
      Gradient descent (constant LR)
      \[ x^{(t+1)} = x^{(t)} - \eta \nabla f(x^{(t)}) \]
      Learning rate
      \[
        \eta = \frac{1}{L}
      \]
    \end{column}%
    \begin{column}{0.6\linewidth}
      \vspace{-0.4cm}
      \begin{center}
        \begin{tikzpicture}[baseline=(img.north),remember picture]
          \node (img) at (0,0) {\includegraphics[height=3.5cm]{figures/puzzle_gd_300.pdf}};
          \node at (1.2,1) {\begin{tabular}{l}$n=300, p=500$\\$H$ singular\\ linear (?)\end{tabular}};
        \end{tikzpicture}

        \begin{tikzpicture}[baseline=(img.north),remember picture]
          \node (img) at (0,0) {\includegraphics[height=3.5cm]{figures/puzzle_gd_500.pdf}};
          \node at (1.2,1) {\begin{tabular}{l}$n=500, p=500$\\$H$ invertible\\sublinear (?)\end{tabular}};
        \end{tikzpicture}
      \end{center}
    \end{column}
  \end{columns}
  \begin{tikzpicture}[remember picture,overlay,visible on=<2>]
    \node[anchor=west,inner sep=0pt] at (current page.west) {\includegraphics[height=5cm]{pictures/watmeme.png}};
  \end{tikzpicture}
\end{frame}

\begin{frame}
  \frametitle{GD on OLS}

  \begin{itemize}
    \item Can we do better than linear convergence for strongly convex problems? better than sublinear for convex problems?
    \begin{center}
      \small
      Yes. Conjugate gradient and Nesterov accceleration (later in this course)
    \end{center}
    \item Can we say something about nonquadratic problems? nonconvex problems?
    \begin{center}
      \small
      Yes. Convex problems enjoy a similar theory. Nonconvex problems have guarantees with respect to local minima.
    \end{center}
    \item Can we prove \alert{lower} bounds in contrast to upper bound?
    \begin{center}
      \small
      Yes. We are going to show that $O(1/t^2)$ is a lower bound for the convex world.
    \end{center}
  \end{itemize}
\end{frame}


\end{document}