\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{remark}[theorem]{Remark}
\newtheorem{assumption}[theorem]{Assumption}
\usepackage{amssymb}
\newcommand{\E}{{\mathbb E}}
\DeclareMathOperator{\var}{Var}

\begin{document}

\lecture{17: Newton's method}{Mar 31,
    2020}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Haixu Liu}}

\section{Reminder: Gradient Descent}

 If a function f is "nice", we can use the following Taylor expansion on it:
 
 \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, y \in [x, x+\delta]
 \end{align*}
 
 The gradient descent step can be described as: 
 \begin{align*}
    \delta = -\eta \nabla^2f(x)
 \end{align*}
 
 We also mentioned two assumptions that can help us find the better bound:
 
 \begin{enumerate}
    \item $\beta$-smooth: 
    
    $$\lambda_{max}(\nabla^2f(x))\leq\beta$$
    
    which means the maximum eigenvalue of the Hessian matrix is upper bounded by $\beta$, and we have proved that $\delta = -\frac{1}{\beta}\nabla f(x)$ is the optimal if $\frac{1}{2}\delta^T\nabla^2f(x)\delta\leq\frac{\beta}{2}{||\delta||}^2$. This is still not enough, therefore, we introduced a new progress or step: $\delta = -\frac{1}{2\beta}{||\nabla f(x)||}^2$.
    
    \item convex: 
    
    $$\lambda_{min}(\nabla^2f(x))\geq0$$
    which means the minimum eigenvalue of the Hessian matrix is at least 0. This allows us to use three more properties:
    
     \begin{enumerate}
     \item if $\nabla f(x)=0$, then we can say x is the global minimum.
     \item we have proved in the last class that $||\nabla f(x)||\geq\frac{f(x)\cdot f(x^*)}{||x - x^*||}$, where $x^* = \arg\min {f(x)}$.
     \item we can achieve $\epsilon$ additive approximation, meaning that we can get $f(x^T) - f(x^*)\leq\epsilon$ using $T = O(\frac{\beta D^2}{\epsilon})$ steps, where $D \approx max||x - x^*||$.
     \end{enumerate}
     
\end{enumerate}

Using the two assumptions we can say that we can find an optimal solution for a given function if it is$\beta$-smooth as well as convex. However, this is not good enough, because we still have $\epsilon$ in time complexity which means it is pseudo-polynomial, and we do not have a good control on vector $D$.





\section{$\alpha$-Strong Convexity}   
\begin{definition}
  If function f satisfies $\lambda_{min}(\nabla^2f(x))\geq\alpha$, where  $\alpha > 0$, we say that f is a $\alpha$-strong convex function, note that here we assume the minimum eigenvalue of the Hessian matrix is strict positive.
\end{definition}

 
 Now we consider how to remove dependency on $||x^* - x^0||$:
 
 \begin{align}
    f(x+\delta) \geq f(x) + \nabla {f(x)}^T\cdot\delta + \frac{\alpha}{2}{||\delta||}^2\\
    \implies f(x)\geq f(x^*) + \nabla {f(x^*)}^T\cdot\delta + \frac{\alpha}{2}\cdot{||x - x^*||}^2
 \end{align}

 By applying Taylor Expansion on $x^*$. Since $x^*$ is optimal, therefore we have: $\nabla f(x^*) = 0$, which implies that:
 
 \begin{align}
    {||x - x^*||}^2\leq\frac{2}{\alpha}[f(x) - f(x^*)]
 \end{align}
 
 
    \subsection{Progress Per Step}
    Now we consider how much progress can we make per step during gradient descent, in other word, we need to find an upper bound of the progress using the inequality we have proved before:
    
    \begin{align}
        f(x^{t+1}) - f(x^*)\leq f(x^t) - f(x^*) - \frac{1}{2\beta}{||\nabla f(x^t)||}^2\\
        \leq f(x^t) - f(x^*) - \frac{1}{2\beta}\cdot\frac{[f(x^t) - f(x^*)]^2}{{||x^t - x^*||}^2}\\
        \leq f(x^t) - f(x^*)-\frac{\alpha}{4\beta}\cdot\frac{[f(x^t) - f(x^*)]^2}{[f(x^t) - f(x^*)]}\\
        = (1 - \frac{\alpha}{4\beta})(f(x^t) - f(x^*))
    \end{align}
    
    Thus, we can say that after T steps
    
    \begin{align}
        f(x^T) - f(x^*)\leq[f(x^0) - f(x^*)]\cdot(1-\frac{\alpha}{4\beta})^T
    \end{align}
    
    Remember that our goal is to find an $x^T$ that satisfies $f(x^T) - f(x^*)\leq\epsilon$, it is enough to say that when we have such T: 
    
    \begin{align}
        T = \frac{4\beta}{\alpha}\cdot\ln(\frac{f(x^0) - f(x^*)}{\epsilon})
    \end{align}
    
    It can be proved that: 
    
    \begin{align}
        f(x^T) - f(x^*)\leq [f(x^0) - f(x^*)]\cdot e^{-\frac{\alpha}{4\beta}\cdot T} = \epsilon
    \end{align}
    
    by plug in T.
    
    \begin{remark}
    The progress is independent on $||x^0 - x^*||$. 
    \end{remark}
    
    \begin{remark}
    The dependence on $\epsilon$ is logarithmic.
    \end{remark}
    
    \begin{remark}
    T is proportional to $\frac{\beta}{\alpha} = \frac{\lambda_{max}}{\lambda_{min}}$ of $\nabla^2f(x)$, here we call $\frac{\beta}{\alpha}$ condition number.
    \end{remark}





\section{Newton Method}
 Go back to our Taylor expansion:
 
 \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
 \end{align}
 
 Note that what we have done so far is find bounds of the term $\frac{1}{2} \delta^T \cdot \nabla^2 f(y) \cdot \delta$, $\beta$-smooth upper bounds this term, and the convexity lower bounds this term. Newton method, however, tries to optimize this quadratic form directly instead of finding bounds.
 
    \subsection{Change of Variables}
    Assume $\Delta = A \cdot \delta$, where A is a linear matrix, and it is full rank, which means $\delta = A^{-1} \cdot \Delta$.\\
    
    Plug this equation into Taylor expansion: 
    
    \begin{align}
        f(x + \delta) = f(x) + \nabla {f(x)}^TA^{-1}\Delta + \frac{1}{2}\Delta^T(A^{-1})^T\cdot\nabla^2f(y)\cdot A^{-1}\cdot\Delta
    \end{align}
    
    The strongly convex case analysis says that T is proportional to condition number of matrix $(A^{-1})^T\cdot\nabla^2f(y)\cdot A^{-1}$. Therefore, ideally we want this matrix to have condition number 1, this implies that this matrix $(A^{-1})^T\cdot\nabla^2f(y)\cdot A^{-1}$ is equal to identity matrix I. In this case, we change variable $\delta$ to $\Delta$, which means we change the Hessian as well, and therefore, we can get a much better condition number using matrix A. \\
    Now we need to consider how to generate A:

    \begin{align}
        \nabla^2 f(y) = A^TA\\
        \implies A = (\nabla^2 f(y))^\frac{1}{2}
    \end{align}
    
    This means A is the best "change of variables". Redo the "best local $\delta$ step" analysis and find the best step:
    
    \begin{align}
        \delta = \mathop{\arg\min}_{\delta: \Delta = A\delta}\nabla {f(x)}^T\cdot A^{-1}\Delta + \frac{1}{2}\Delta^T\cdot \Delta
    \end{align}

    if we fixed the norm of $\Delta$, the direction of $\Delta$ is aligned against $\nabla {f(x)}^T \cdot A^{-1}$. Therefore, we consider: 
    
    \begin{align}
        \Delta = - \eta [\nabla {f(x)}^TA^{-1}]^T = - \eta (A^{-1})^T \nabla f(x)
    \end{align}

    Since $\delta = A^{-1}\Delta$, we have: 
    
    \begin{align}
        \Delta = - \eta [\nabla {f(x)}^TA^{-1}]^T = - \eta (A^{-1})^T \nabla f(x)\\
        = -\eta [\nabla^2 f(y)]^{-1} \cdot \nabla f(x)
    \end{align}
    
    \begin{claim}
        When $\eta = 1$ is the optimizer of the whole quadratic form, but there is still a problem that when we compute the best $\delta$, it depends on the gradient of point x but Hessian of point y, where the point y depends on $\delta$ as well. Therefore, the solution above cannot be used directly.
    \end{claim}
    
    \begin{remark}
    Assume that $\nabla^2 f(y) \approx \nabla^2 f(x)$ when y is close to x, then
    
    \begin{align}
        \delta = \mathop{\arg\min}_{\delta: \Delta = A\delta, ||A|| \leq \epsilon}\nabla {f(x)}^T\cdot A^{-1}\Delta + \frac{1}{2}\Delta^T\cdot(A^{-1})^T \nabla^2 f(x) A^{-1} \Delta\\
        = - \eta [\nabla^2 f(x)]^{-1} \nabla f(x)
    \end{align}
    
    Instead of using Hessian of y, we are using Hessian of x. In this case the optimal A to be used is $[\nabla^2 f(x)]^{\frac{1}{2}}$
    \end{remark}
    
    \begin{remark}
    Gradient descent step depends on $\nabla^2 f(x)$, which is called second-order method, this means that we are not only using the assumption on the Hessian here, we are actually using the value of the Hessian.
    \end{remark}
    
    \begin{remark}
    Gradient descent step is computationally harder because when we compute 
    
    \begin{align}
        \delta = - \eta [\nabla^2 f(x)]^{-1} \cdot \nabla f(x)
    \end{align}
    we need to compute an inverse of a matrix, this can be $O(n^3)$.
    \end{remark}





 \section{Theorems for Newton's Method}
 
 \begin{theorem}
 Suppose $\exists r > 0$ s.t, $\forall x$ the distance from $x^*$ is at most $r$:
 
    \begin{enumerate}
        \item $\lambda_{min}(\nabla^2 f(x)) \geq \alpha$, means the function is $\alpha$-strong convex.
        \item $||\nabla^2 f(x) - \nabla^2 f(y)|| \leq L \cdot ||x - y||$, where $||A||$ is spectral norm as well as the max singular value.
    \end{enumerate}
    
    Set $x^1 \triangleq x^0 + n(x)$, where $n(x) = - \eta [\nabla^2 f(x)]^{-1} \nabla f(x)$ is Newton step, then we can have:
    
    \begin{align}
        ||x^1 - x^*|| \leq \frac{L}{2 \alpha} \cdot {||x^0 - x^*||}^2
    \end{align}
    
    where $x^0$ is at distance at most r from $x^*$.
 \end{theorem}
 
 This theorem means that if we update x with Newton step, the distance between the updated point and the optimal point will drop quadractically.\\
 
 To show why this is useful, we define a new variable $\gamma \triangleq \frac{2\alpha}{L}$, the above inequality is equal to:
 
 \begin{align}
    ||\frac{x^1 - x^*}{\gamma}|| \leq {||\frac{x^0 - x^*}{\gamma}||}^2\\
    \implies ||\frac{x^T - x^*}{\gamma}|| \leq ||\frac{x^0 - x^*}{\gamma}||^{2^T}
 \end{align}
 
 Since $2^T$ is a very large number, if we set $||\frac{x^0 - x^*}{\gamma}||$ to be a large number, we actually do not have any bound here, therefore, we need $||\frac{x^0 - x^*}{\gamma}|| \leq \frac{1}{2}$, which implies:
 
 \begin{align}
    T = O(\log \log \frac{1}{\epsilon}) 
 \end{align}
 
 is enough for $||\frac{x^T - x^*}{\gamma}|| \leq \epsilon$.
 
    \begin{observation}
    A big caveat of Newton's method is that $||x^0 - x^*|| \leq \frac{\gamma}{2} = \frac{\alpha}{2}$
    \end{observation}
 
    \begin{observation}
    Newton's method works for "warm start" $x^0$.
    \end{observation}
    
    
    
    
    
\section{Next Time}
Next time we will talk about Interior Point Method for linear programming.




\end{document}