\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{epsfig}
\usepackage[right=0.8in, top=1in, bottom=1.2in, left=0.8in]{geometry}
\usepackage{setspace}
\spacing{1.06}

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{\vspace{0.25cm}
      \hbox to 5.78in { {COMS 4995-2:\hspace{0.12cm}Advanced
          Algorithms (Spring'20)} \hfill #2 }
      \vspace{0.48cm}
      \hbox to 5.78in { {\Large \hfill #5  \hfill} }
      \vspace{0.42cm}
      \hbox to 5.78in { {#3 \hfill #4} }\vspace{0.25cm}
    }
  }
  \end{center}
  \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{#3}{Scribes:\hspace{0.08cm}#4}{Lecture #1}}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}

\newcommand{\E}{{\mathbb E}}
\DeclareMathOperator{\var}{Var}

\begin{document}

\lecture{16: Gradient Descent}{Mar 26,
  2020}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Emily Jin, Yihao Li, Jayant Madugula}}

\section{Gradient Descent}

Let $f: \mathbb{R}^n \rightarrow \mathbb{R}$ and the objective function be $\min_{x\in \mathbb{R}^n} f(x)$

We have $f(x + \delta) = f(x) + \nabla f(x)^T \cdot \delta + \delta^T\cdot \nabla^2 f(y) \cdot \delta$ for some $y \in [x, x+\delta]$

For small enough $\delta$, we make The ``first order approximation''
of $f(x)$ by ignoring terms quadratic in $\delta$:

$$f(x + \delta) \approx f(x) + \nabla f(x)^T \cdot \delta$$

The local ``greedy'' step for delta gives:

\begin{align*}
  \delta &= \text{argmin}_{||\delta|| \leq \epsilon} f(x) + \nabla f(x)^T \cdot \delta \\
  &= -\eta \cdot \nabla f(x)^T
\end{align*}

where $\eta$ is the step size and is defined as $\eta = \text{const}(\epsilon)$.

\subsection{Gradient Descent Algorithm}

The algorithm itself is quite simple:

\begin{enumerate}
  \item Fix $x^0 \in \mathbb{R}^n$.
  \item For every iteration $t$, we have $$x^t = x^{t-1} - \eta \cdot \nabla f^T(x^{t-1})$$ We perform $T$ total iterations.
\end{enumerate}

Given this algorithm, how do we set  $t$ and find a sufficient setting for $T$?

We make two major assumptions.

\begin{definition}
  Let $\beta > 0$, $y = x + \delta$. $f$ is $\beta$-smooth if $\forall
  x, y \in \mathbb{R}^n$, $$||\nabla f(y) - \nabla f(x)|| \leq \beta ||x - y||$$

  Equivalently, $\forall \delta \in \mathbb{R}^n$: $$\delta^T \cdot \nabla^2 f(x) \cdot \delta = \beta \cdot ||\delta||^2$$

  $\Leftrightarrow$ max eigenvalue of the Hessian is $\leq \beta$, where the Hessian is $\nabla^2 f(x) = \frac{\partial^2 f(x)}{\partial x_i \partial x_j}$
\end{definition}

We use the Taylor Expansion of $f(x)$ to get the following upper bound on $f(x+\delta)$:

\begin{align}
  f(x+\delta) &= f(x) + \nabla f(x)^T \cdot \delta + \frac{1}{2} \delta^T \cdot \nabla^2 f(y) \cdot \delta \\ 
  &\leq f(x) + \nabla f(x)^T \cdot \delta + \frac{1}{2} \beta ||\delta||^2
\end{align}

We now minimize the latter, without any further constraint on
$\delta$. 
The optimum will satisfy $\delta = -\eta \cdot \nabla f(x)$. We can then solve for the optimal $\delta$ in terms of $\beta$ and the gradient of $f(x)$.
\begin{align}
  \delta &\triangleq \text{argmin}_{\delta \in \mathbb{R}^n} f(x) + \nabla f(x)^T \cdot \delta + \frac{\beta}{2} ||\delta||^2 \\ 
  &= \text{argmin}_{\delta \in \mathbb{R}^n} \nabla f(x)^T(-\eta \cdot \nabla f(x)) + \frac{\beta}{2}\eta^2 ||\nabla f(x)||^2 \\ 
  &= \text{argmin}_{\delta \in \mathbb{R}^n} ||\nabla f(x)||^2(-\eta + \frac{\beta}{2}\eta^2) \\
  &= \text{argmin}_{\delta \in \mathbb{R}^n} \frac{\beta}{2} \eta^2 - \eta \\
  &= -\frac{1}{\beta} \cdot \nabla f(x)
\end{align}

Note that just as $-\frac{1}{\beta} \cdot \nabla f(x)$ is the optimal $\delta$, $\frac{1}{\beta}$ is the optimal $\eta$, or step size.


At iteration t: 
\begin{equation*}
x^t = x^{t-1} - \frac{1}{\beta}\nabla f(x^{t-1})
\end{equation*}
we have $\eta = \frac{1}{\beta}$. We can now plug in $\delta =
-\frac{1}{\beta}\nabla f(x)$ into the Taylor expansion to get the
upper bound on $f(x+\delta)$:
\begin{align*}
f(x+\delta) \leq& f(x) + \nabla f(x)^T\left(-\frac{1}{\beta}\nabla f(x)\right) + \frac{\beta}{2} \Vert-\frac{1}{\beta}\nabla f(x)\Vert^2\\
=& f(x) + \Vert\nabla f(x)\Vert^2\left[-\frac{1}{\beta}+\frac{1}{2\beta}\right]\\
=& f(x) - \frac{1}{2\beta}\Vert\nabla f(x)\Vert^2
\end{align*}
If $\nabla f(x) \neq 0$, we know $\Vert\nabla f(x)\Vert \neq 0$, therefore $f(x+\delta) < f(x)$, i.e. we are making progress.\\
If $\nabla f(x) = 0$, we have following cases:
\begin{enumerate}
\item Global min, which is our goal
\item Local min
\item Global/local max, can be usually solved (escaped) by some random perturbations
\item Saddle point, in some directions it increase, in some other
  directions it decreases, and may stay at constant. Can be usually solved by some random perturbations.
\end{enumerate}
To deal with the local minimum, we introduce another assumption: f(x) is convex. \\

\begin{definition}
$f$ is convex iff $\forall x,y \in \mathbb{R}^n, \lambda \in [0,1]$, there's
\begin{equation*}
f(\lambda x + (1-\lambda) y) \leq \lambda f(x) + (1-\lambda) f(y)
\end{equation*}
\end{definition}

\begin{claim}
if f(x) is a convex function, any minimum of f is global minimum.
\end{claim}
\begin{proof}
  if f(x) is convex, $\forall \delta \in \mathbb{R}^n, \delta^T\nabla^2f(x)\delta \geq 0$, i.e. $\nabla^2f(x)$ is positive semi-definite (and all eigenvalues are positive),
By taylor expansion
\begin{align*}
f(x+\delta) =& f(x) + \nabla f(x)\delta + \frac{1}{2}\delta^T \nabla^2f(y) \delta\\
\geq& f(x) + \nabla f(x)\delta
\end{align*}
if $\nabla f(x) = 0$, we still have 
\begin{align*}
f(x+ \delta) \geq f(x) 
\end{align*}
for any $\delta$, which means x is a global minimum.
\end{proof}

Thus for the G.D algorithm, $\delta = -\frac{1}{\beta}\nabla f(x)$
\begin{itemize}
\item if $\nabla f(x) \neq 0$, $f(x+\delta) \leq f(x) - \frac{1}{2\beta}\Vert\nabla f(x) \Vert^2$ from $\beta$-smooth
\item if $\nabla f(x) = 0$, x is global min by convexity
\end{itemize}

Time Efficiency: How fast can it be? How should $T$ be defined?

Goal: given $\epsilon > 0$, find x s.t. $f(x) - f(x^*) \leq \epsilon$, where $x^* = \arg\min_x f(x)$, i.e. the optimum.
Bounding $\nabla f(x)$?
\begin{align*}
f(x^*) =& f(x + x^* - x)\\
=& f(x) + \nabla f(x)^T(x^* - x) + (x^* - x)^T \nabla^2 f(y) (x^* - x)\\
\mbox{given $\nabla^2 f(y)$ positive semi-definite, } \geq& f(x) + \nabla f(x)^T(x^* - x)
\end{align*}
Rearrange the equation, we have
\begin{align*}
f(x) - f(x^*) \leq - \nabla f(x)^T(x^* - x) \leq \Vert\nabla f(x)\Vert\cdot\Vert x^* -x\Vert
\end{align*}
Thus if $f(x) - f(x^*) > \epsilon$, we have
\begin{align*}
\Vert\nabla f(x)\Vert\cdot\Vert x^* -x\Vert &> \epsilon\\
\Vert\nabla f(x)\Vert&>\frac{\epsilon}{\Vert x^* -x\Vert}
\end{align*}
\begin{theorem}
$f(x^T) - f(x^*) \leq \epsilon$ after $T = O(\beta \cdot \frac{D^2}{\epsilon})$ iterations, where $D = \max ||x-x^*||$ for x such that $f(x) \leq f(x^0)$
\end{theorem}

\begin{proof}
From $\beta$-smoothness, we showed that $f(x + \delta) \leq f(x) - \frac{1}{2\beta} ||\nabla f(x)||^2$ where $\delta = -\frac{1}{\beta} \nabla f(x)$. Suppose $\Delta = f(x) - f(x^*) > \epsilon$:
\begin{center}
    $||\nabla f(x)|| \geq \frac{\Delta}{||x-x^*||}  \geq \frac{\Delta}{D}$
\end{center}

Let $\Delta_t = f(x^t) - f(x^*)$. If we fix $\Delta_0$, how many steps $T_1$ until $\Delta_{T_1} < \frac{\Delta_0}{2}$? Before this happens, when $t < T_1$:

\begin{center}
$||\nabla f(x)|| \geq \frac{\Delta_0/2}{D}$
\end{center}

In each iteration, we decrease $f(x)$ by $-\frac{1}{2\beta} ||\nabla f(x)||^2$:

\begin{align*}
\Delta_{t} \leq& \Delta_{t-1} - \frac{1}{2\beta} (\frac{\Delta_0/2}{D})^2 \\
\leq& \Delta_{t-1} - \frac{1}{8\beta D^2} \cdot \Delta_0^2 \\
\text{\# steps } T_1 \text{ is} \leq& \frac{8\beta D^2}{\Delta_0}
\end{align*}

How many steps until...
\begin{align*}
\Delta_{T_2} \leq \frac{\Delta_0}{4} \rightarrow& T_2 \leq 8\beta D^2 \cdot \frac{2}{\Delta_0} \\
\Delta_{T_3} \leq \frac{\Delta_0}{8} \rightarrow& T_3 \leq 8\beta D^2 \cdot \frac{4}{\Delta_0}\\
\Delta_{T} \leq \epsilon \rightarrow& T \leq 8\beta D^2 \cdot \frac{1}{2\epsilon}\\
\end{align*}

Total number of steps is $\leq T_1 + T_2 + ... \leq 8\beta D^2 \cdot [\frac{1}{\Delta_0} + \frac{2}{\Delta_0} + ... + \frac{1}{2\epsilon}]$. Since these terms are geometrically increasing, the last epsilon term is the most important. Therefore, the total runtime is $O(\frac{\beta D^2}{\epsilon})$.
\end{proof}

If $f$ is $\beta$-smooth and convex, $T = O(\frac{\beta
  D^2}{\epsilon})$ steps is enough to achieve $f(x) - f(x^*) \leq
\epsilon$. Note that the runtime is proportional to $D = \max ||x -
x^*||$. This is undesirable: it's like maximum capacity $F$ from the
Ford-Fulkerson algorithm (analysis), making this a
``pseudo-polynomial time'' algorithm.

\end{document}
