\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-8:\hspace{0.12cm}Advanced
          Algorithms (Spring'21)} \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{21: Gradient descent: smoothness, convexity}{Mar 30,
  2021}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Wenjie Wang, Lingxiao Li}}

\section{Overview}
We will continue the context about \textbf{Gradient Descent}\\
The object function:
$$Let\ f: \mathbb{R}^n \rightarrow \mathbb{R}$$ 
$$\min\limits_{x\in \mathbb{R}^n} f(x)$$

\section{Smoothness, convexity}
\begin{theorem}
Taylor Expansion:
$$f(x+\delta) = f(x) + \nabla f(x)^T \cdot \delta + \frac{1}{2} \delta^T \cdot \nabla^2 f(y) \cdot \delta  $$
\end{theorem}
Notice y is some point nearby x.
\begin{definition}
$f$ is $\beta$-smooth: $\lambda_{max}\nabla^2 f(y) \leq \beta$
\end{definition}
Then we can use Taylor Expansion to get the folowing upper bound on $f(x+\delta)$:
$$f(x+\delta) \leq f(x) + \nabla f(x)^T \cdot \delta + \frac{1}{2} \beta ||\delta||^2$$
We want $\delta$ which minimizes the later quantity:
\begin{equation}
    \begin{aligned}
      \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{aligned}
\end{equation}

Now we can use $\delta = -\frac{1}{\beta}\nabla f(x)$ to get the upper bound on $f(x+\delta)$:
\begin{equation}
    \begin{aligned}
        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{aligned}
\end{equation}

if $\nabla f(x) \neq 0$, we can have $f(x+\delta) < f(x)$. It means that we are making progress and we can quantify how much progress we are making.\\

When $\nabla f(x) = 0$(we are not making any progress), we have following situations:
\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 increases, in some other
  directions it decreases, or may stay at constant. Can be usually solved by some random perturbations.
\end{enumerate}
\includegraphics[scale=0.7]{localmin.jpg}\\
Only the first situation is what we want, but it is usually easy to get out of situation 3 and 4 by some random perturbations.\\
In general, dealing with local minimum is a hard problem. It is non-convex optimization.\\
To avoid local minimum, we need another assumption: f(x) is convex.
\begin{definition}
$f$ is convex iff $\lambda_{min}\nabla^2 f(y) \geq 0$
\end{definition}
\begin{fact}
$f$ is convex iff $\forall x,y \in \mathbb{R}^n, \alpha \in [0,1]$, there's
$$ f(\alpha x + (1-\alpha) y) \leq \alpha f(x) + (1-\alpha) f(y)$$
\end{fact}
\begin{claim}
if f(x) is a convex function, then $\nabla f(x) = 0$ implies x is global minimum
\end{claim}
Proof: Fix x such that $\nabla f(x) = 0$, using Taylor Expansion, we can have
$$f(x+\delta) = f(x) + \nabla f(x)^T\delta + \frac{1}{2}\delta^T \nabla^2f(y) \delta\\
\geq f(x)$$
It means that at any other point $x+\delta$, $f$ is at least $f(x)$, which implies that x is a global minimum.
\begin{assumption}
If f is convex
$$\nabla f(x^t) = 0$$
$\implies x^t$ is global minimum
$$\nabla f(x^t) \neq 0 \implies f(x^{t+1}) \leq f(x^t) - \frac{1}{2\beta}\Vert\nabla f(x)\Vert^2$$
$\implies$ gradient descent is making progress
\end{assumption}
Next, we need to consider how far we are from the optimal solution.\\
Goal: find some $x'$ such that
$$f(x') - f(x^*) \leq \varepsilon$$ where $x^*$ is the global minimum and $x'$ is the $\varepsilon-approximate$ solution\\
We want to relate how far we are from the optimal solution to how many progress we are making.\\
That is relate $f(x') - f(x^*)$ to $\Vert\nabla f(x)\Vert$:
\begin{equation}
    \begin{aligned}
        f(x^*) &= f(x + x^* - x)\\
        &= f(x) + \nabla f(x)^T(x^* - x) + (x^* - x)^T \nabla^2 f(y) (x^* - x)\\
        &\geq f(x) + \nabla f(x)^T(x^* - x)
        \end{aligned}
\end{equation}

After rearranging, we have:
\begin{equation}
    \begin{aligned}
        \nabla f(x)^T(x - x^*) &\geq f(x) - f(x^*)\\
        f(x) - f(x^*) &\leq \Vert\nabla f(x)\Vert\cdot\Vert x -x^*\Vert\\
        \Vert\nabla f(x)\Vert &\geq \frac{f(x) - f(x^*)}{\Vert x -x^*\Vert}
    \end{aligned}
\end{equation}

For example: if $x^t$ s.t. $f(x^t)-f(x^*)>\epsilon \implies \Vert \nabla f(x) \Vert \geq \frac{\epsilon}{\Vert x-x^*\Vert}$


\begin{theorem}
$f(x^T)-f(x^*)\leq \epsilon$ after $T=O(\beta \cdot \frac{D^2}{\epsilon})$ iterations, where $D\triangleq \max \limits_{x:f(x)\leq f(x^0)} \Vert x-x^*\Vert$
\end{theorem}
\begin{proof}
Let $\triangle_t=f(x^t)-f(x^*)>\epsilon$
$$\Vert\nabla f(x^t)\Vert\geq \frac{\triangle_t}{\Vert x^t-x^* \Vert}\geq \frac{\triangle_t}{D}$$
Let $T_1=\# iterations$ until $\triangle_{T_1}\leq \frac{\triangle_0}{2}$\\
Before reaching $t=T_1$:
$$\Vert \nabla f(x^t) \Vert \geq \frac{\triangle_0/2}{D}$$
In each iteration, $f(x^t)-f(x^*)$ drops by $\geq \frac{1}{2\beta}\cdot \Vert \nabla f(x^t) \Vert^2\geq \frac{1}{2\beta} \cdot \frac{\triangle_0^2}{4D^2}=\frac{\triangle_0^2}{8D^2\beta}$
$$\implies T_1\leq \frac{\triangle_0/2}{\triangle_0^2/8D^2\beta}=\frac{4D^2\beta}{\triangle_0}$$
Let $T_2=\# iterations$ until $\triangle_{T_1+T_2} \leq \frac{\triangle_{T_1}}{2}$. Similarly, $T_2\leq \frac{4D^2\beta}{\triangle_{T_1}}=4D^2\beta \cdot \frac{2}{\triangle_0}$\\
$$T_3:T3 \leq 4d^2\beta \cdot \frac{4}{\triangle_0}$$
$$\vdots$$
$$T_k:T_k \leq 4D^2\beta \cdot \frac{2^k}{\triangle_0}\implies f(x^{T_1+T_2+\cdots +T_k})-f(x^*)\leq\frac{\triangle_0}{2^k}\leq \epsilon$$
We set $k$ so that at time $T=T_1+T_2+\cdots +T_k$, value:
$$f(x^T)-f(x^*)\leq \epsilon,$$
i.e., $\epsilon/2\le\Delta_0/2^k\le\epsilon$.
Total time:
\begin{equation}
    \begin{aligned}
        T &= T_1+T_2+\cdots +T_k\\
        &= 4D^2\beta \cdot \left[\frac{1}{\triangle_0}+\frac{2}{\triangle_0}+\cdots\frac{2^k}{\triangle_0}\right]\\
        &= 4D^2\beta \cdot \left[\frac{1}{\triangle_0}+\frac{2}{\triangle_0}+\cdots\frac{2}{\epsilon}\right]\\
        &\leq 4D^2\beta \cdot \frac{4}{\epsilon}
    \end{aligned}
\end{equation}
since the sum is geometrically increasing.
Now, we have proved that when $T\leq O(\beta \cdot \frac{D^2}{\epsilon})$, $f(x^T)-f(x^*)\leq \epsilon$
\end{proof}
Here is an example where lack of smoothness is bad:\\
\includegraphics[scale=0.7]{smoothness.jpg}
\begin{definition}
$\alpha-strongly$ convex for $\alpha >0$ iff $\lambda_{min}\left(\nabla^2f(y)\right)\geq \alpha$
\end{definition}
\end{document}
