\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}
\usepackage{algorithm}
\usepackage{algpseudocode}
\spacing{1.06}
\usepackage{graphicx}
\graphicspath{ {./images/} }
\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}

\setlength{\parindent}{0cm}
\begin{document}

\lecture{15: Ellipsoid Algorithm \& Gradient Descent}{March 12,
  2020}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Andrew Quijano, Isabel Ehrhardt}}

%Lecture starts at 12:30 in CVN video recording

\section{Project}
There will be 3 deliverables for the projects, which are two project reports (PR) and a final paper. The instructor will upload a document to Courseworks with more detailed information on both the expectations of the deliverables and potential project ideas.

\subsection{Progress Report 1 - due 3/26}
\begin{itemize}
    \item 1-2 pages
    \item Include team members, 2-4 people (1 person projects discouraged, talk to Professor)
    \item Specify area(s) of interest
    \item Specify type of project (see nest sub-section)
    \item Include some relevant literature for professor to help guide interest/give suggestions
    \item Identify some potential problem/goal for your final report
\end{itemize}

\subsection{Progress Report 2 - due 4/16}
\begin{itemize}
    \item 3 pages
    \item Expand on PR 1 by formally defining the problem, the goal of the project, and what related works you will be referencing
    \item Include current progress and remaining work
\end{itemize}


\subsection{Final Report - due 5/11}
\begin{itemize}
    \item Minimum 10 pages
    \item A complete report on the project you set for your team in the first 2 PRs.
\end{itemize}


\subsection{Types of Projects}
\subsubsection{Reading/Survey}
Read 2 - 3 papers or a very long paper e. g. a thesis. 
The goal is to synthesize the data from the sources into one concise paper.
For example, it can be reading about 2 approaches to same problem and or viewing both an old and more modern approach to a specific problem. 
The survey will discuss approaches and the main core ideas of the papers, and synthesize their ideas and how they are related. 
The final project report should be 10+ pages. Avoid re-writing the papers, you want to discuss the core ideas of the papers and be able to clearly explain it and compare/contrast both papers. The description should follow a lecture format that you would be able to explain it to your classmates.

\subsubsection{Implementation} 
Implement some algorithm that is theoretically backed, such as the algorithms seen in class. It would have a theorem both proving the algorithm works and has specified run-time. 

You should understand the core idea of the paper and run the algorithm on your a graph/dataset potentially. 
There should be some hypothesis you want to prove or disprove. An example would be you implement a standard algorithm and compare with a new algorithm and compare which runs faster. 
You should be able to explain your results e. g. an algorithm works better on certain kind of datasets than another algorithm. 

\subsubsection{Research-based}
You want to try push bounds of what we have learned in class to create some new theoretical work. It is connected to the reading/survey project as you will need to understand the current state of the problem you are investigating in algorithms to devise a new algorithm. If you struggle to complete your goal in time, you should have a plan to fall back to a reading/survey project. You can also narrow the scope, such as improving an algorithm's run-time for a very specific use case (e. g. making assumptions on a potential dataset your new algorithm would be analyzing).

\subsection{Last remarks}
You are free to e-mail/ask the instructor on Piazza about the project before PR1 deadline about the direction of your project. It is best to ask the instructor directly rather than the TAs with your project inquiries. PR1 will be returned with the instructor's comments about your project and a list of updated related works that may better fit your interests.

% Starts at 35:00
\section{Ellipsoid Algorithm - Khachiyan, 1979}
\subsection{Background}
\begin{itemize}
    \item Our 1st polynomial time algorithm for LP. \\
(We have talked about the Simplex algorithm that was smarter in enumerating the vertices as it would get closer and closer to the solution. While no bound can be proved for the Simplex algorithm, in practice it runs in polynomial time assuming your LP is not adversarial, etc.) 
    \item The Ellipsoid Algorithm isn't used practically for LP, but is more versatile for other problems beside LP. 
    \item It solves the Feasibility Problem: which is defined as finding
an x $\in$ F, where F is the feasible region e. g. Ax $\geq$ b. 
\end{itemize}
\subsection{Reducing LP to Feasibility}
\begin{fact}
You can reduce general LP into solving feasibility. 
\end{fact}

General Linear Program:
\begin{equation*}
\begin{array}{lr@{}c@{}r@{}l}
\text{minimize }   & c^{\top} x         \\
\text{subject to } & Ax \geq b
\end{array}
\end{equation*}

\begin{proof}
Suppose we have a guess $v$ for LP. Then, we can solve the following feasibility problem for x:
\begin{align*}
    Q_{v} = 
        \begin{cases}
            Ax \geq b \\
            c^{\top}x \leq v 
       \end{cases}
\end{align*}
If you don't have a guess, execute binary search to find $v$. \\
Start with $v^0$ = -R, where R is a really large number and is likely to be infeasible. \\
If $Q_{v^0}$ is infeasible $\rightarrow$ $v^{1}$ = $\frac{-R}{2}$. 
If $Q_{v^1}$ is infeasible $\rightarrow$ $v^{2}$ = $\frac{v^1}{2}$. If
\begin{align*}
    v^{*} = 
        \begin{cases}
            Ax \geq b \\
            c^{\top}x \leq v 
       \end{cases}
\end{align*}
Then we just do a binary search for $v^{*}$ starting from interval [-R, +R] for large enough R. 

\includegraphics{images/Fig1.jpg} 

If A, b are all integers then $log_2$(R) = $n^{O(1)}$ * b, where b is the bit complexity of the numbers. \\

$v^{*}$ = ratio of 2 numbers with bit-complexity b.\\

\# of iterations in the binary search is $n^{0(1)}$ * b.
\end{proof}




\subsection{Definitions}
\begin{definition}
\textbf{Ball} B, for r $>$ 0, is defined as 
$B_r$(y) = \{ x: $||$x - y$||$ $\leq$ r\}
\end{definition}

\begin{definition}
\textbf{Axis-Aligned Ellipsoid}
E for $\lambda_1$, $\lambda_2$, ..., $\lambda_n$ $> 0$ is defined as 
E(y) = $\{x: \frac{\Sigma_i(x_i-y_i)^2}{\lambda^2} \leq r\}$\\
Note: if all $\lambda=1$, this is a ball\\
\end{definition}

\begin{definition} 
\textbf{Generic Ellipsoid} E for full-rank n x n matrix A is defined as 
\begin{align*}
E(y) = \{ x: (y - x)^TA^TA(y - x) \leq r^2\}     
\end{align*}
y is the center and the rotation is determined by A.\\
Note: if A is the diagonal matrix composed of $\frac{1}{\lambda_i}$, then this is an axis aligned ellipsoid. \\
\end{definition}



A ball, an Axis-Aligned Ellipsoid, and a Generic Ellipsoid in 2D:

\includegraphics[width=3cm, height=3cm]{images/BallFig.jpg}
\includegraphics[width=6cm, height=6cm]{images/AxisAllign.jpg}
\includegraphics[width=6cm, height=6cm]{images/Ellipsoid.jpg}

\subsection{Ellipsoid Algorithm - Solving the Feasibility Problem}
\textbf{Feasibility problem:}
\begin{align*}
F = \{x: Dx \geq e \} = 
\begin{cases}
Ax \geq b \\
c^{\top}x \leq v\\     
\end{cases}
\end{align*}
 

\textbf{Goal:} Find x $\in$ F\\

\textbf{Algorithm idea:} We want to search for x $\in$ F, where F is the feasible region, keeping F as a subset of some larger ellipsoid that we make tighter. We proceed in iterations, where in iteration t, $y^{t}$ is center of ellipsoid $E^t$ such that F $\subseteq$ $E^t$, and try to make $E^{t+1}$ smaller than $E^t$\\
\newpage
\textbf{Algorithm:} \\
\begin{algorithm}[htb]
\begin{algorithmic}[1]
\State Start with $y_0=0$, $E_0 :=$ ball of radius r, such that if $x \in F$ exists, $||x|| \leq R$
\If{$y^{t}$ $\in$ F}
\State{Success!}
\Else
\State{$y^t$ violated some inequality constraint $A_ix \geq b_i$ where $A_iy^t<b_i$}
\State{Compute new $y^{t+1}$, $E^{t+1}$ s. t. F $\subseteq$ $E^{t+1}$ and $E^{t+1}$ is smaller than $E$}
\State{To compute this, use the fact that the constraint gives a hyperplane that cuts the ellipsoid, with $y^t$ on one side, and F on the other}
\State{Find $E^{t+1}$ that contains $E^t \cap \{x_i; Ax_i\geq b\}$}
\State{If not yet done, continue unless $E^t$ is so small that we need to stop and say it is infeasible.}
\EndIf
\end{algorithmic}
\end{algorithm}
\\
\textbf{2D Visuals: }\\
\includegraphics[width=8cm, height=6cm]{images/Start.jpg}
\includegraphics[width=8cm, height=6cm]{images/StepT.jpg}\\


\textbf{Main Analysis Claim:} There is a method to define $E^{t+1}$ such that vol($E^{t+1}$) $\leq$ vol($E^{t}$)(1 - $\frac{1}{2n}$). (where vol is the traditional volume of ellipsoid). \\

\textbf{Corollary:} if v = vol($E^{0}$) = exp(n log(n)) $R^n$. Then after T = O(nlog($\frac{v}{\epsilon}$)) iterations. Then

val($E^{t}$) $\leq$ vol($E^{0}$)(1 - $\frac{1}{2n})^T$ $\leq$ $\epsilon$ \\

\textbf{Remark:} This algorithm is applicable to in programming/optimization problems beyond LP. 

e. g.: LPs where number of constraints is exp(n) and where for given y, find a constraint Ax $\geq$ b that is violated by y in polynomial time with respect to n. This is done by taking the normal given y. it is polynomial because you aren't iterating overall constraints. 

% Starts at 1:15 in lecture video
\section{Gradient Descent (GD)}
We so far talked about L. P. for a constrained optimization problem
\begin{equation*}
\begin{array}{lr@{}c@{}r@{}l}
\text{minimize }   & c^{\top} x         \\
\text{subject to } & Ax \geq b
\end{array}
\end{equation*}

GD is unconstrained optimization for minimizing some function f(x). Solve
\begin{align*}
    min_{x \in \mathbb{R}^{n}} f(x)
\end{align*}

\subsection {LP can be formatted as Unconstrained Optimization}

Define
\begin{align*}
g(x) =     
\begin{cases} 
      f(x) & x \in F, \: Ax \geq b\\
      +\infty & x \notin F
   \end{cases}
\end{align*}
Note: F is the feasible region. Now we have a new optimization problem: 
\begin{align*}
    min_{x \in \mathbb{R}^{n}} g(x)
\end{align*}

\textbf{Goal:} Find $min_{x}$ $f(x)$. \\

\textbf{General Approach for GD}:\\
Set $x_0$ as a starting point \\
Define $x^{t+1}$ = $f$($x^t$, values of f or $x^t$, ...) \\
Then hope that in each iteration of $x^{t}$ to $x^{t + 1}$ that f($x^{t+1}$) is improved over f($x^t$).\\

\textbf{Computational questions: }
\begin{enumerate}
    \item How to go from $x^{t}$ to $x^{t + 1}$?
    \item How many iterations?
\end{enumerate}
There are similar computational questions brought up when discussing max flow using the Ford-Fulkerson algorithm. The first point matches with selecting better augmenting paths for Ford-Fulkerson. Also, the second point matches with how picking a better alternating path reduces the number of iterations.

Gradient Descent as a natural greedy algorithm, means it moves a little bit $\delta$ = $x^{t+1}$ - $x^{t}$ such that to minimize f($x^{t+1}$)

\subsection{What should $\delta$ be?}
Suppose f is a "nice" function so that we can approximate f via a Taylor expansion in $\mathbb{R}^n$. Note that  $\nabla f(x)^{\top} \delta$ $\in$ $\mathbb{R}^{n}$ and
$\nabla^{2}f(x)$ is the Hessian Matrix, which can be described as $[\nabla^{2}f(x)]_{i, j}$ = $\dfrac{\partial^{2}f}{\partial x_i \partial x_j}$\\
\begin{align*}
f(x + \delta) \approx f(x) + \nabla f(x)^{\top} \delta + \delta^{\top}\nabla^{2}f(x)\delta
\end{align*}
Think of $\delta$ as very small, as if near infinitesimal small. Note $O(||\delta||^2)$ is negligible. Therefore:
\begin{align*}
f(x + \delta) \approx f(x) + \nabla f(x)^{\top}\delta + O(||\delta||^2) \\
f(x + \delta) \approx f(x) + \nabla f(x)^{\top}\delta\\
\end{align*}

Question: find $\delta$ such that:
\begin{enumerate}
\item $||\delta||$ $\leq$ $\epsilon$ 
\item minimize f(x) + $\nabla f(x)^{\top}\delta$    
\end{enumerate}

Note: You drop f(x) as it is not depending on $\delta$. \\
Note: For the optimization, the best thing to do is to take $\delta$ to be equal to the gradient but the opposite sign! \\
Note: $\eta^2 ||\nabla f(x)||^2$ = $\epsilon^2$ \\

\begin{align*}
\delta &= argmin_{\delta s. t. ||\delta|| \leq \epsilon} f(x) + \nabla f(x)^{\top}\delta \\
&= argmin_{\delta s. t. ||\delta|| \leq \epsilon}  \nabla f(x)^{\top}\delta \\
&= -\nabla f(x)^{\top} \eta \: s. t. \: ||\delta||^2 = \epsilon^{2} \\
\end{align*}

Finally, we get the result:
\begin{align*}
x^{t+1} = x^t + \delta = x^t - \nabla f(x)^{\top} \eta    
\end{align*}


\end{document}
