\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[ruled,vlined]{algorithm2e}
\spacing{1.06}
\newcommand{\R}{\mathbb{R}}

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

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

\begin{document}

\lecture{20: Ellipsoid Algorithm and Gradiant Descent}{March 25,
  2021}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Greg Marzo, Alex Yao}}


\section{Introduction}

In this lecture, we 1) conclude our discussion of the Ellipsoid Algorithm for tackling linear programming and 2) begin our exploration of gradient descent.

\section{Ellipsoid Algorithm}

To recap from the previous class, we left off discussing the feasibility problem which is defined as follows: Given $F \triangleq \{x \in \R^n : Ax \leq b \}$, return some $x \in F$ if the set is non-empty or report that $F= \varnothing$.

To address this problem using the Ellipsoid Algorithm, we first address the approximation version of the feasibility problem: Given $F$ from the feasibility problem as well as $\epsilon > 0$, return some $x \in F$ if the set is non-empty or report that $\text{vol}(F) < \epsilon$. If $\epsilon = \exp (-poly(n,m) B)$, essentially $\epsilon$ is exponentially small, this is enough to solve the non-approximate version.

We first define key terms used in the algorithm.

\begin{definition} [Ball]
Fix $r>0$, a ball $$B_r(y) = \{ x \in \R^n : ||x - y|| \leq r\}$$
\end{definition}

\begin{definition} [Axis-Aligned Ellipsoid]
Fix $\lambda_1, ..., \lambda_n, r > 0$, an axis-aligned ellipsoid $$E_{r, \lambda}(y) = \{ x : \sum_{i=1}^n(\frac{x_i - y_i}{\lambda_i})^2 \leq r^2 \}$$
\end{definition}

\begin{definition} [General Ellipsoid]
Fix $r>0, \text{rank n matrix } A \in \R^{n \times n}$, a general ellipsoid
\begin{align*}
    E_{r, A}(y) &= \{ x + y : x^T A^T A x \leq r^2 \} \\
    &= \{ x + y : ||Ax||_2^2 \leq r^2 \} 
\end{align*} 
Alternatively,
\begin{align*}
    E_{r, A}(y) = \{ x+y : || \underbrace{\Lambda}_{\text{diagonal matrix}} \overbrace{R}^{\text{unitary rotation matrix}} x ||_2^2 \leq r^2 \}
\end{align*} 
\end{definition}

\subsection{Algorithm Idea}
\begin{enumerate}
    \item Start with a starting ellipsoid $E^0$ such that $F \subseteq E^0$.
    \item Iterate and compute $E^t$ for timestep $t$ such that
    \begin{enumerate}
        \item $F \subseteq E^t$
        \item $\text{vol}(E^t) < \text{vol}(E^{t-1})$
    \end{enumerate}
    \item Terminate when the center $y$ is in the target region $F$ or when $\text{vol}(E^t) < \epsilon$.
\end{enumerate}

\subsection{Exact Algorithm}

\begin{algorithm}[H]
\SetAlgoLined
\KwResult{Report $x \in F$, or that $\text{vol}(F) < \epsilon$}
 Start with $E^0 \supseteq F$, where $E^0 = \text{(ball) } B_r(y_0)$ of sufficient radius $r$ and center $y_0$. \\
 \For{$t = 0,...,T$}{
  \eIf{$y^t \in F$}{
   we are done: report $x = y^t$ \\
   }{
   $\exists$ some violated constraint $i$: $A_i y^t > b_i$ \\
   Define $E^{t+1}, y^{t+1} = \text{smallest ellipsoid containing } E^t \cap \{ A_ix \leq b_i \}$\\
   \If {$\text{vol}(E^{t+1}) < \epsilon$} {
      we are done: report $\text{vol}(F) < \epsilon$
      }
  }
 }
 \caption{Ellipsoid Algorithm}
\end{algorithm}

\begin{figure}[h]
\caption{$F \subseteq E^{t} \cap \{ A_i x \leq b_i \} \subset E^t$}
\centering
\includegraphics[width=0.5\textwidth]{ellipsoid.png}
\end{figure}

\subsection{Analysis}
We note that correctness of this algorithm follows by definition. If the algorithm terminates, it is correct. Now, we turn to the runtime analysis. Specifically, how many iterations ($T$) will this algorithm take?

\begin{claim}
\label{claim:volumes}
$\text{vol}(E^{t+1}) \leq \text{vol}(E^{t}) \cdot (1 - \frac{1}{2n})$
\end{claim}
\begin{proof}
The proof is omitted from lecture since we did not show how to compute the exact update for $E^{t+1}, y^{t+1}$. However, there are update methods that obtain the bound in this claim.
\end{proof}

As a result of Claim \ref{claim:volumes}, we know
\begin{align*}
    \text{vol}(E^T) &\leq \text{vol}(E^0) \cdot (1 - \frac{1}{2n})^T\\
    &\leq \underbrace{(2R)^n}_{\text{ball volume bound}} \cdot (1 - \frac{1}{2n})^T
\end{align*}
In the worst case where we run until the volume is less than $\epsilon$, 
\begin{align*}
    (2R)^n \cdot (1 - \frac{1}{2n})^T &\leq \epsilon \\
    -n \log{2R} + T \cdot \frac{\theta (1)}{2n} &\geq \log{\frac{1}{\epsilon}}
\end{align*}
\begin{align*}
    T &\geq \theta(n) [ \log{\frac{1}{\epsilon}} + n \cdot poly(n,m) \cdot B ] \\
    \text{\# of iterations} &\approx \theta(n \log{\frac{1}{\epsilon}} + poly(n,m)\cdot B)
\end{align*} 
Given our approximate algorithm, it is enough to take $\epsilon = \exp (-poly(n,m) B)$ to solve our original non-approximate feasibility problem. The resulting overall runtime is $poly(n, m, B)$.

\begin{remark}
The only "access" needed to the input constraints $Ax \leq b$ is through a "separation oracle".
\end{remark}
\begin{definition}[Separation Oracle]
$SO_F:$ Given $y \in \R^n$, report $y \in F$ or return some violated constraint hyperplane $Ax=b$ such that $F$ and $y$ are on opposite sides.
\end{definition}

The maximum number of calls we may need to make to $SO_F = \theta(n) \cdot [\log{\frac{1}{\epsilon}} + n \log{R} ]$. Note there is no dependency on the number of constraint equations. In some cases, we can write separation oracles that work on linear problems with exponential number of constraints in only polynomial time, resulting in an overall polynomial runtime.

\section{Gradient Descent}
Switching gears to address the optimization of finding the minimum of a function f(x), we define 2 variants of the optimization problem:

\textbullet{} Unconstrained optimization:
\begin{align*}
    min_{x \in {\R}^{n}} f(x)
\end{align*}

\textbullet{} Constrained optimization:
\begin{align*}
    min_{\substack {x \in {\R}^{n} \\ x \in F}} f(x)
\end{align*}

A constrained optimization can be reduced to unconstrained by defining a new function g as:
\begin{equation*}
    g(x) = \left\{
        \begin{array}{ll}
            f(x) & \quad x \in F \\
            + \infty & \quad x \notin F
        \end{array}
        \right.
\end{equation*}
where it is enough to solve for the minimum of $g(x)$ as an unconstrained optimization problem.

\subsection {Setting up Gradient Descent}
In our Gradient Descent process, the basic idea is that we start with a ${x}^0 \in {\R}^{n}$ and on each iteration from ${t} = 0 ... {T}$, compute some new ${x}^{t+1}$ based on the previous ${x}^{t}$ via some function $f$

Naturally, 2 key questions arise:
\begin{enumerate}  
\item How will we find a new ${x}^{t+1}$ from ${x}^{t}$?
\item How many iterations $T$ will it take to find the global minimization of $min_{x \in {\R}^{n}} f(x)$?
\end{enumerate}

If we assume that $f(x)$ is a "nice" function, meaning that if we move a slight amount $\delta \in \R^n$ from $x \in \R^n$, the function's gradient won't change too drastically, we can use the Taylor Expansion to expand function {f(x)} like so: 

\begin{equation*}
    f(x + \delta) \approx f(x) + \nabla f(x)^\intercal  \delta + \delta^\intercal \nabla^2 f(y) \delta
\end{equation*}
where $y \in [x, x+\delta]$

Here, was also define the gradient and the Hessian as follows:

\begin{definition}
$\nabla f(x) = ( \frac{\partial f}{\partial x_1} (x), \frac{\partial f}{\partial x_2} (x), ... ) \in \R^n$
\end{definition}

\begin{definition}
 $\nabla^2 f(x)$ is some matrix size $n\times n$ where 
 \begin{align*}
    entry_{i,j} = \frac{\partial^2 f}{\partial x_i \partial x_j} (x)
 \end{align*}
\end{definition}


\subsection {Finding $\delta$}
To recap what we have established, we update $x^{t+1}$ to be $x^t + \delta$. Here, suppose we establish $\|\delta\| \leq \epsilon$.  \\ We can find the best $\delta$ using the following form:

\begin{equation*}
   \delta =  argmin_{\|\delta\| \leq \epsilon} f(x) + \nabla f(x)^\intercal  \delta + \delta^\intercal \nabla^2 f(y) \delta
\end{equation*}

A question arises now on how do we estimate $\delta^\intercal \nabla^2 f(y) \delta$? There are two options we can do.

\subsubsection {Option 1}
\begin{equation*}
    f(x + \delta) \approx f(x) + \nabla f(x)^\intercal  \delta + O(\epsilon^2)
\end{equation*}
We can take advantage of the fact that $O(\epsilon^2) << \nabla f(x)^\intercal  \delta$ and effectively ignore the $O(\epsilon^2)$ term. Thus:
\begin{align*}
   \delta &=  argmin_{\|\delta\| \leq \epsilon} f(x) + \nabla f(x)^\intercal  \delta \\
   &= argmin_{\|\delta\| \leq \epsilon} \nabla f(x)^\intercal  \delta \\
   &= \eta (-\nabla f(x))
\end{align*}

where here, $\|\eta - \nabla f(x)\| = \epsilon $ and $\eta = \frac{\epsilon}{\|\nabla f(x)\|}$

In context of the Gradient Descent Algorithm, $x^{t+1} = x^t - \eta \nabla f(x)$

\subsubsection {Option 2}
\begin{definition}
\textbf{$\beta$-smooth:}
Set $\beta > 0$. We call $f$  $\beta$-smooth if:
\begin{align*}
&\forall x,y \in {\R}^{n}: \|\nabla f(x) - \nabla f(y)\| \leq \beta \|x-y\| \\
&\Leftrightarrow \forall \delta \in \R^n: \delta^\intercal \nabla ^2 f(x) \delta \leq \beta \|\delta\|^2 \\
&\Leftrightarrow \text{max eigenvalue of } \nabla^2 f(x) \leq \beta
\end{align*}
\end{definition}

We can derive the optimization of $\delta$ for Gradient Descent in the following way:

\begin{align*}
    f(x + \delta) &\approx f(x) + \nabla f(x)^\intercal  \delta + \delta^\intercal \nabla^2 f(y) \delta \\
    &\leq f(x) + \nabla f(x)^\intercal \delta + \beta \frac{\|\delta\|^2}{2}
\end{align*}

and $\delta$ now gets set as:
\begin{align*}
\delta &= argmin_{\delta} f(x) + \nabla f(x)^\intercal \delta + \beta \frac{\|\delta\|^2}{2} \\
&= argmin_{\delta} \nabla f(x)^\intercal \delta + \frac{\beta}{2} \|\delta\|^2 \\
&= argmin_{\eta: \delta = \eta \nabla f(x)} -\eta \|\nabla f(x)\|^2 + \frac{\beta}{2} \eta^2 \|\nabla f(x)\|^2 \\
&= argmin_{\eta: \delta = \eta \nabla f(x)} \eta (\frac{\beta}{2} \eta - 1)
\end{align*}

Thus, the optimal solution becomes $\eta = \frac{1}{\beta}$ and the optimal $\delta$ becomes $\delta = -\frac{1}{\beta} \nabla f(x)$

In context of the Gradient Descent algorithm, 
\begin{align*}
f(x+\delta) &\leq f(x) - \frac{1}{\beta}\|\nabla f(x)\| + \frac{\beta}{2} \frac{1}{\beta ^2} \|\nabla f(x)\|^2 \\
&= f(x) - \frac{1}{2 \beta} \|\nabla f(x)^2\|
\end{align*}

\end{document}