\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{tikz}
\usetikzlibrary{arrows}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{epsfig, xcolor}
\usepackage[right=0.8in, top=1in, bottom=1.2in, left=0.8in]{geometry}
\usepackage{setspace, changepage, dsfont}
\usepackage[ruled,vlined]{algorithm2e}
\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}{\hspace{0.08cm}#4}{Lecture 22 : $\alpha-$Strong Convexity, Newton's Method}}

\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}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{prove}[theorem]{To Prove}

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

\begin{document}

\lecture{Scribe : Newton's Method}{April 1, 2021}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Scribes: Siddharth Bhutoria, Nihar Maheshwari}}

\section{Gradient Descent : Recap}
For $f : \mathds{R}^{n} \rightarrow \mathds{R}$ having continuous first and second derivatives and a local improvement $\delta$, we have the following Taylor approximation:
$$
f(x+\delta) = f(x) + \nabla f(x)^T \cdot \delta + \frac{1}{2} \delta^T \cdot \nabla^2 f(y) \cdot \delta
$$
$$
\delta = - \eta \cdot \nabla f(x)
$$
\textbf{Note:} Since this is an approximation ignoring higher order terms, we have $y \in [x, x+\delta]$\\
Further, we made the following assumptions on $f$ to get a better bound:
\subsection{Assumption 1 : $f$ is $\beta$-smooth}
If $f$ is $\beta$-smooth, we have $\lambda_{max} (\nabla^2 f(y)) \leq \beta$. Upon using this to get an upper bound on  $f(x + \delta)$ we have
$$
\eta = \frac{1}{2\beta}
$$
This gives us a guarantee that we are progressing in each iteration of the descent as long as the gradient is not zero ($ \nabla f(x) \neq 0 $) as we will always then have $f(x + \delta) < f(x)$
\subsection{Assumption 2 : $f$ is Convex}
If $f$ is convex, we have that the minimum eigen value of the Hessian is at least 0 ($\lambda_{min} (\nabla^2 f(y)) \geq 0$). We further proved the following bound on the number of iterations $T$ for $\epsilon$ approximate solution:
$$
    T = \mathcal{O}\left( \frac{\beta \cdot D^2}{\epsilon} \right)
$$
\textbf{Where:} 
$$
f(x) - f(x^{*}) \leq \epsilon \text{ where } x^{*} = \arg\min f(x)
$$
$$
D = \max_{x} \|x - x^{*}\|
$$
\textbf{Note:} Drawbacks of this bound:
\begin{enumerate}
    \item Dependence over $1/\epsilon$: This could be improved
    \item $D = \max_{x} \|x - x^{*}\|$: This dependency is on the
      domain. The value of $D$ is proportional to the value of
      $\|x^{*}\|$, which may not be polynomial in input size.
\end{enumerate}

\section{Assumption 3 : $\alpha$-Strong Convexity}
\begin{definition}
A function $f$ is $\alpha$-strictly convex if it satisfies
$$
\lambda_{min}(\nabla^{2}f(y)) \geq \alpha > 0
$$
\end{definition}
The minimum eigen value of the Hessian is strictly positive in this case. To get a better bound on $T$, we are looking to remove the $\|x - x^{*}\|$ dependency with this assumption.\\[0.1in]
For $\delta = x - x^{*}$, from the Taylor approximation at $x^{*}$ and the $f : \alpha-$strictly convex assumption we have:
\begin{align}
    f(x) = f(x^{*} + (x - x^{*})) \geq f(x^{*}) + \nabla f(x) \cdot \delta + \frac{1}{2}\delta^T \cdot \alpha \cdot \delta\\
    \Rightarrow f(x) = f(x^{*} + (x - x^{*})) \geq f(x^{*}) + \nabla f(x) \cdot \delta + \frac{\alpha}{2}\|x - x^{*}\|^2
\end{align}
Since $x^{*}$ is the optimal value we have $\nabla f(x^{*}) = 0$. Therefore
\begin{align}
    f(x) - f(x^{*}) \geq  \frac{\alpha}{2}\|x - x^{*}\|^2
\end{align}
We will use this result ahead to remove the dependency of $T$ on $\|x -x^{*}\|^2$
\subsection{Progress in each Gradient Descent step}
\textbf{Goal:} In each iteration as we move from $x^{t} \rightarrow x^{t+1}$, our aim is to quantify the progress made towards the optimal in each iteration.\\[0.1in]
From previous lecture, since we decrease $f(x)$ by $(1/2\beta) \cdot \|\nabla f(x)\|^2$ in each iteration, using the inequality from before we have that:
$$
    f(x^{t+1}) - f(x^{*}) \leq f(x^t) - f(x^{*}) - \frac{1}{2\beta} \|\nabla f(x^t)\|^2\\
$$
$$
    \Rightarrow f(x^{t+1}) - f(x^{*}) \leq f(x^t) - f(x^{*}) - \frac{1}{2\beta} \cdot \frac{\left[ f(x^t) - f(x^{*}) \right]^2}{\|x^t - x^{*}\|^2}
$$
Using \textbf{(3)} from above, we have
$$
    \Rightarrow f(x^{t+1}) - f(x^{*}) \leq f(x^t) - f(x^{*}) - \frac{1}{2\beta} \cdot \frac{\left[ f(x^t) - f(x^{*}) \right]^2}{ (2/\alpha) \cdot \left[ f(x^t) - f(x^{*}) \right] }
$$
$$
    \Rightarrow f(x^{t+1}) - f(x^{*}) = \left[ f(x^t) - f(x^{*}) \right]\cdot \left[1 - \frac{\alpha}{4\beta}\right]
$$
\textbf{Note:} The distance to the optimal value of the function drops by a factor of $\left[1 - (\alpha/4\beta)\right]$ in each iteration\\[0.1in]
$\therefore$ starting from $x = x^0$, we have in $T$ steps (applying inequality inductively):
$$
    f(x^T) - f(x^{*}) \leq \left[ (x^0) - f(x^{*}) \right]\cdot[1 - \frac{\alpha}{4\beta} ]^T
$$
For 
$$
    T = \frac{4\beta}{\alpha} \cdot \ln{\left( \frac{f(x^0) - f(x^{*})}{\epsilon} \right)}
$$
We have 
$$
    \left(1 - \frac{\alpha}{4\beta}\right)^T \leq \frac{\epsilon}{f(x^0) - f(x^{*})}
$$
$$
    \Rightarrow f(x^T) - f(x^{*}) \leq \left(f(x^0) - f(x^{*})\right)\cdot\left(1 - \frac{\alpha}{4\beta}\right)^T \leq \epsilon
$$
Hence we have:
\begin{theorem}
For any $\alpha-$strongly convex and $\beta-$smooth function f:
$$
    T = \mathcal{O}\left(\frac{\beta}{\alpha}\cdot\ln\left(\frac{f(x^0) - f(x^{*})}{\epsilon}\right)\right)
$$
\end{theorem}
\textbf{Remarks:}
\begin{enumerate}
    \item Here, the number of steps / iterations do not depend on $\|x - x^{*}\|$. Rather $T$ has a logarithmic dependence on the function values $(f(x^{0}) - f(x^{*}))$. This greatly improves over the dependence we had over $D^2$ initially.
    \item Here, $T$ has a logarithmic dependence over $1/\epsilon$ which is again an improvement from the result using Assumption 2.
    \item $T$ is further proportional to $\beta/\alpha$ - The Condition Number
\end{enumerate}

\begin{definition}
We define the condition number $\kappa(\nabla^2 f(y))$ as:
$$
    \kappa(\nabla^2 f(y)) = \frac{\beta}{\alpha} = \frac{\lambda_{max}(\nabla^2 f(y))}{\lambda_{min}(\nabla^2 f(y))}
$$
\end{definition}

\section{Newton Method}
To understand Newton's Method, we will go back to 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
$$
\textbf{Note:} So far in Gradient Descent, we found bounds of the term $ \frac{1}{2} \delta^T \cdot \nabla^2 f(y) \cdot \delta $, where the $\alpha$-strong convexity lower bounds this term and $\beta$-smooth upper bounds this term. Unlike Gradient Descent, Newton's method try to optimize this quadratic form directly instead of finding the bounds. That's why Newton Method is also known as $2nd$ order method.
 
\subsection{Change of Variables}
\textbf{Goal:} Optimize $f(x+\delta)$ as a function of $\delta$.\\
\textbf{Intuition:} Changing variables shouldn't change the correctness.\\

We define $\Delta = A \cdot \delta$, where A is a full rank matrix, which means $\delta = A^{-1} \cdot \Delta$ \\

Plugging this $\delta$ value into Taylor expansion, we get: 
$$
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
$$   

Remember, in gradient descent, the number of iteration $T$ depends on the condition number of the hessian term where we divided maximum eigenvalue $\lambda_{max}$ with minimum eigenvalue $\lambda_{min}$. \\
Further, carefully analysing this strongly convex case we can say that $T$ is proportional to condition number of the matrix $(A^{-1})^T\cdot \nabla^2f(y)\cdot A^{-1}$. Ideally, we want to make the condition number as small as possible and the smallest value a condition number can take is 1, which implies that this matrix $(A^{-1})^T\cdot \nabla^2f(y)\cdot A^{-1}$ is equal to the identity matrix I i.e.
$$(A^{-1})^T\cdot \nabla^2f(y)\cdot A^{-1} = I$$
In this case, we have changed variable $\delta$ to $\Delta$, which implies that we have changed the Hessian as well, and therefore, we can get a much better condition number using the matrix A. \\
Now, let's see how we can generate $A$:
$$(A^{-1})^T\cdot \nabla^2f(y)\cdot A^{-1} = I$$
$$\nabla^2 f(y) = A^TA$$
$$\implies A = (\nabla^2 f(y))^\frac{1}{2}$$  
where $A$ is defined as long as $\lambda_{min} (\nabla^2 f(y)) \geq 0$. \\
\paragraph{} This signify $A$ is the best "change of variables". Next, we will redo the "best local $\delta$ step" analysis to find the best step under this change of variable:
$$
\delta = \mathop{\arg\min}_{ \delta: \Delta = A\delta} \nabla {f(x)}^T \cdot A^{-1}\Delta + \frac{1}{2}\Delta^T \cdot \Delta
$$
Fixing the norm of $\Delta$, we realize that the direction of $\Delta$ is aligned against $\nabla {f(x)}^T \cdot A^{-1}$. This implies that: 
$$
\Delta = - \eta \Big[ \nabla {f(x)}^TA^{-1} \Big]^T = - \eta (A^{-1})^T \nabla f(x)
$$
Under the nice function assumption $\Delta$ is symmetric which implies $A$ is symmetric  
$$ \Delta = - \eta (A^{-1})^T \nabla f(x) $$
$$ \Delta = -\eta \cdot \Big[ \nabla^2 f(y) \Big]^{-\frac{1}{2}} \cdot \nabla f(x)
$$
\begin{claim}
The above quadratic form gets optimized when $\eta = 1$.
\end{claim}

We know $\delta = A^{-1} \cdot \Delta$ so plugging the value $\Delta$, we will have: 
$$ \delta = -\eta \cdot \Big[ \nabla^2 f(y) \Big]^{-1} \cdot \nabla f(x)
$$  
\textbf{Issue:} There exists 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 and we don't know y. Therefore, we cannot use the solution directly.

    
\begin{remark}
Assuming that $\nabla^2 f(y) \approx \nabla^2 f(x)$ i.e. y is close to x, then
    
$$
\delta = \mathop{\arg\min}_{\delta: \Delta = A\delta} \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 \Big[ \nabla^2 f(x) \Big]^{-1} \nabla f(x) $$
    
Here, instead of using Hessian of y, we are using Hessian of x. In this case the optimal A to be used is $\Big[ \nabla^2 f(x) \Big]^{\frac{1}{2}}$
\end{remark}
    
\begin{remark}
Computing $\delta$ is harder because when we compute 
$$\delta = - \eta [\nabla^2 f(x)]^{-1} \cdot \nabla f(x) $$
we have to compute matrix inverse, and that can take $O(n^3)$.
\end{remark}

\section{Theorems for Newton's Method}
$$n(x) \triangleq [\nabla^2 f(x)]^{-1} \cdot \nabla f(x) $$
 
\begin{theorem}
Suppose $\exists r > 0$ s.t, $\forall x$ the distance from $x^*$ is $\leq r$:
 
\begin{enumerate}
\item $\lambda_{min} (\nabla^2 f(x)) \geq \alpha $, implies 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}

Then $\forall x^0$ at distance $\leq r$ from $x^*$, we have     
$$x^1 \triangleq x^0 + n(x)$$ 
$$ ||x^1 - x^*|| \leq \frac{L}{2 \alpha} \cdot {||x^0 - x^*||}^2 $$
\end{theorem}
 
This theorem suggests that if we update $x$ with Newton step, the distance between the updated point and the optimal point will drop quadratically. \\
 
To show the significance, let's define a new variable $ \gamma = \frac{2\alpha}{L}$, then we can re-write the above inequality as follows:
 
$$ ||\frac{x^1 - x^*}{\gamma}|| \leq \frac{L^2}{(2\alpha)^2} {||x^0 - x^*||}^2 = {||\frac{x^0 - x^*}{\gamma}||}^2 $$
$$ \implies ||\frac{x^T - x^*}{\gamma}|| \leq ||\frac{x^0 - x^*}{\gamma}||^{2^T} $$

Since $2^T$ is a very large number, if we set $||\frac{x^0 - x^*}{\gamma}||$ to some large number, we actually do not have any bound, therefore, we define $||\frac{x^0 - x^*}{\gamma}|| \leq 0.9$, which implies:

$$ T = O(\log \log \frac{1}{\epsilon}) $$
is enough for $||\frac{x^T - x^*}{\gamma}|| \leq 
\epsilon$.

\begin{remark}
A big caveat of Newton's method is that we need that $||x^0 - x^*||
\leq \frac{9\gamma}{10} = \frac{18\alpha}{10L}$, which means that
$x^0$ our starting position is close to the optimal point $x^*$. 
I.e., Newton's method works for "warm start" $x^0$.
\end{remark}

\section{Interior Point Method}
Consider a linear program of the form,

\begin{equation}
    \underset{x \in K}{\min} f(x)
\end{equation}

Example:-
\begin{equation}
\begin{aligned}
    K=\{ x: A x \leq b \} \\
    f(x) = c^Tx
\end{aligned}
\end{equation}

where $A \in \mathbb{R}^{m \times n}$, $c \in \R^n$ and $b \in \R^m$. 

We want to relax the minimization by defining a new function such that we have an unconstraint optimization framework similar to what we had in Gradient Descent. \\

\textbf{Idea:} 
We have already seen one way to turn this into an unconstrained problem, by replacing the objective
function with one that evaluates to $f(x)$ for $x \in K$ and to $+\infty$ otherwise.
 \[
    Define  F(x) = \left\{
	\begin{array}{ll}
		f(x)  & \mbox{if $x \in K$ } \\
		+\infty & \mbox{if $x \not\in K$}
	\end{array}
\right.
\]

But there is an issue with such a function, as function isn’t smooth/continuous and so it does not work well with the gradient descent method or Newton’s method. The boundaries for the function acts as some repellant force and so we should penalize if the $x$ comes too close to boundary or it goes in opposite direction. \\

We require a smoother function and next time we will see how to make the function smoother and solve this linear program using Interior Point Method.
\end{document}
