\documentclass[11pt]{article}
\parindent 0in
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
%\usepackage{amsthm}
%\usepackage{epsfig}

\newcommand{\handout}[5]{
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in { {\bf 18.409 The Behavior of Algorithms in Practice} \hfill #2 }
       \vspace{4mm}
       \hbox to 5.78in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { {\it #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{Lecturer: #3}{Scribe: #4}{Lecture #1}}

\newcommand{\Kappa}{\kappa}
\newcommand{\norm}[1]{\|#1\|}

\newcommand{\dist}{\text{dist}}
\newcommand{\aff}{\text{dist}}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}

\newcommand{\qed}{\ensuremath{\blacksquare}}
\newenvironment{proof}{\noindent{\bf Proof}\hspace*{1em}}{\qed\bigskip}

\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\parskip 1.5ex

\renewcommand{\baselinestretch}{1.25}

\begin{document}

\lecture{19}{5/2/2002}{Dan Spielman}{Matthew Lepinski}
\section*{Where We Are in the Proof}
We are trying to bound the quantity:
$$
\Pr_{b_1,\ldots,b_d}[\dist(0,\partial(\triangle(b_1\ldots b_d)))<\epsilon]
$$
Where the probability is over the distribution with density
$$
(\prod_{i=1}^d \mu_i(b_i))[0 \in \triangle(b_1\ldots b_d)]vol(\triangle(b_1\ldots b_d))
$$
Also recall that the $\mu_i$ are Gaussian with variance $\sigma^2 \leq 1$ and
have centers of norm $\leq \Gamma \leq 1+4\sqrt{d\log(n)}$.

\subsection*{Last Time We Proved}
$$
\Pr_{b_1,\ldots,b_d}[\dist(b_1,\aff(b_2,\ldots, b_d))<\epsilon] \leq
  e^2\left(\frac{d(1+\Gamma)\epsilon}{\sigma^2}\right)
$$
Where $\aff(b_2,\ldots, b_d)$ denotes the affine span of $b_2,\ldots,b_d$.

\subsection*{Today We Will Prove}
\begin{equation}
\Pr_{b_1,\ldots,b_d}[\dist(0,\aff(b_2,\ldots, b_d))<
  \epsilon \dist(b_1,\aff(b_2,\ldots, b_d))] \leq
    \left(\frac{10 d \Gamma^2 \epsilon}{\sigma^2}\right)
\end{equation}

\section*{How Smooth are Gaussians}
We will now prove a utility lemma which will be useful later.

\begin{lemma}
Let $\mu$ is a Guassian distribution centered at 0 with variance $\sigma^2$.
If $X$ and $Y$ are points such that $\norm{X}\leq T$ and 
$\norm{X-Y} < \epsilon \leq T$, then 
$$
\frac{\mu(Y)}{\mu(X)} \geq e^{\frac{-3 \epsilon T}{2 \sigma^2}}
$$
\end{lemma}
\begin{proof}
The worst case is when $X = T$ and $Y = T+\epsilon$. In this case we
have:
$$
\frac{\mu(Y)}{\mu(X)} = \frac{e^{\frac{-(T+\epsilon^2)}{2 \sigma^2}}}{
                              e^{\frac{-T^2}{2 sigma^2}}}
     = e^{\frac{-2T\epsilon - \epsilon^2}{2 \sigma^2}}
$$
\end{proof}

\textbf{Note:} If $\epsilon < T/\sigma^2$, this Lemma gives us that
$$
\frac{\mu(Y)}{\mu(X)} \geq e^{\frac{-3}{2}}
$$

\section*{Proof of Today's Bound}
\textbf{Goal:} Prove the origin is not much closer to $\aff(b_1,\ldots,b_d)$ than
$b_1$ is.

\textbf{Note:} Since Gaussians are smooth, the chance of any nearby configuration
is about the same.

\textbf{Idea:} Fix the shape of the simplex and shift it a little towards $b_1$.
The resulting configuration is just as likely and has the origin farther from
$\aff(b_1,\ldots,b_d)$.

\subsection*{Change of Variables}
It will be easier to fix the shape of the simplex if we do another change of variables.

Our handle on the simplex will be its center of gravity:
$$
x = \frac{1}{d} \sum_{i=1}^d b_i
$$

The shape of the simplex will be determined by the values:
$$
\delta_i = x - b_i
$$
For $i = 2 \ldots d$.

Additionally, we set
$$
\sum_{i=1}^d \delta_i = 0
$$
which defines $\delta_1$.

Observe that
$$
\triangle(b_1\ldots b_d) = \triangle(x-\delta_1\ldots x-\delta_d) = x +
  \triangle(-\delta_1\ldots -\delta_d)
$$

Therefore,
$$
0 \in \triangle(b_1\ldots b_d) \Leftrightarrow x \in  \triangle(-\delta_1\ldots -\delta_d)
$$

Similarly,
$$
\dist(0,\aff(b_2,\ldots,b_d) = \dist(0,\aff(\delta_2,\ldots,\delta_d)
$$

\textbf{Note:} This change of variables is just a linear transformation and so the 
Jacobian of the transformation is constant.

\subsection*{Defining the Contraction Map}
We observe that:
\begin{multline*}
\Pr_{b_1,\ldots,b_d}[\dist(b_1,\aff(b_2,\ldots, b_d))<\epsilon] \leq \\
  \max_{\delta_1, \ldots, \delta_d} \Pr_x [\dist(x,\aff(\delta_2,\ldots,\delta_d)) <
    \epsilon \dist(\delta_1,\aff(\delta_2,\ldots,\delta_d))]
\end{multline*}
Subject to the condition that $\norm{\delta_1 - \delta_i} \leq 2\Gamma$ for all $i$
and where $x$ is has distribution:
$$
\nu(x) = (\prod_{i=1}^d \mu_i(b_i))[x \in \triangle(\delta_1\ldots \delta_d)]
$$

Let $S$ be $\triangle(\delta_1\ldots \delta_d)$. Let $S_\epsilon$ be obtained by
contracting $S$ at $\delta_1$ by a factor of $(1 - \epsilon)$. That is, $S_\epsilon$
is the set of points $y$ such that 
$$
\dist(y,\aff(\delta_2,\ldots,\delta_d)) \geq
    \epsilon \dist(\delta_1,\aff(\delta_2,\ldots,\delta_d))
$$

We observe that
$$
\Pr_x [\dist(x,\aff(\delta_2,\ldots,\delta_d)) <
    \epsilon \dist(\delta_1,\aff(\delta_2,\ldots,\delta_d))] = 
       \frac{\nu(S) - \nu(S_\epsilon)}{\nu(S)}
$$
To show this quantity is small, we just need to show that the probability 
measures don't change much.

Let $\rho_\epsilon$ be the contraction map specified above.

\subsection*{Bounding \ensuremath{\nu(S_\epsilon)/\nu(S)}}
We observe that $\rho_\epsilon$ moves points by at most a distance of $\epsilon 2 \Gamma$.
Also, we know that $x$ is at a distance of at most $3 \Gamma$ from the center of its
distribution. 

Therefore, from Lemma 1, we know that under the map, $\rho_\epsilon$, the product of the 
$\mu$'s changes my at most a factor of:
$$
e^{\frac{-3-6\epsilon \Gamma^2 d}{2 \sigma^2}}
$$
Which is at least:
$$
\left(1 - \frac{\epsilon 9 \Gamma^2 d}{\sigma^2}\right)
$$
Additionally, are contraction map has a Jacobian of $(1-\epsilon)^d$ at every
point.

\textbf{Note:} $(1-\epsilon)^d \leq (1 - \epsilon d)$

This implies that 
$$
\frac{\nu(S_\epsilon)}{\nu(S)} \leq  \left(1 - \frac{\epsilon 9 \Gamma^2 d}{\sigma^2}\right)
  (1 - \epsilon d) \leq \left(1 - \frac{10d \epsilon \Gamma^2}{\sigma^2} \right)
$$

Therefore,
$$
\frac{\nu(S) - \nu(S_{\epsilon})}{\nu(S)} \leq \frac{10d \epsilon \Gamma^2}{\sigma^2}
$$

\subsection*{Completing the Bound}
Using Combination Lemma 2 which we will prove in the next section, we get that:
$$
\Pr[\dist(0,\aff(b_2,\ldots,b_d)) < \epsilon] \leq \epsilon 
   \frac{10 e d^2 \Gamma^2(1 + \Gamma)}{\sigma^4}
$$

Therefore, since the simplex has $d$ symmetric faces, we get that:
$$
\Pr[\dist(0,\partial(b_1,\ldots,b_d)) < \epsilon] \leq \epsilon 
   \frac{10 e d^3 \Gamma^2(1 + \Gamma)}{\sigma^4}
$$

\section*{The Combination Lemma}
\begin{lemma}
Let $a,b$ have some distribution such that 
\begin{enumerate}
\item $\Pr[f(a) < \epsilon] \leq \alpha \epsilon$
\item $\forall a$, $\Pr[g(a,b) \leq \epsilon] \leq (\beta \epsilon)^2$
\end{enumerate}
Then $\Pr[f(a)g(a,b) < \epsilon] \leq 5 \alpha \beta \epsilon$
\end{lemma}

\textbf{Note:} To really apply this to the previous circumstances, we would need to 
do this in the $\delta$ world where
\begin{itemize}
\item $a = \{\delta_1, \ldots \delta_2\}$
\item $b = x$
\end{itemize}

\begin{proof}
\begin{multline*}
\Pr[f(a)g(a,b)<\epsilon] \leq \Pr[f(a) < \beta \epsilon] +
  \sum_{i \geq 1} \Pr[f(a) < \beta \epsilon 2^i \mbox{ and } g(a,b)<\frac{2^{i+1}}{\beta} \\
\leq \alpha \beta \epsilon + \sum_{i \geq 1}\alpha\beta\epsilon 2^i (2^{-i+1})^2 
= \alpha \beta \epsilon (1 + \sum_{i \geq 2} 2^{-i + 2}) 
\end{multline*}
\end{proof}

\section*{Back to the Original Problem}
Recall that the quantity which we were originally interested in was:
$$
\Pr_{\omega, r, b_{\pi_1},\ldots,b_{\pi_d}}\left[ \frac{
   \dist(z^{\omega,r},\partial\triangle(b_{\pi_1}\ldots b_{\pi_d})) <\omega,z>}{3\Gamma}
     <\epsilon \right]
$$
Where the distribution of $\omega$, $r$, and $b_i$ was:
\begin{multline*}
\left(\prod_{j \not\in \{\pi_1,\ldots,\pi_d\}} \int_{a_j} [<\omega,a_j> \leq r] \mu_i(a_j)\right)
\prod_{i=1}^d \mu_{\pi_i}(a_{\pi_i}) \\
[z^{\omega,r} \in \triangle(b_{\pi_1}\ldots b_{\pi_d})]
\text{Vol}(\triangle(b_{\pi_1}\ldots b_{\pi_d}))
\end{multline*}

We have succeeded in bounding the probability that $z^{\omega,r}$ is close to the
boundary of the triangle. Therefore, all that remains is to show it is unlikely that
the angle is small. (That is, it is unlikely that $<\omega,z>$ is small).

\textbf{Idea:} Rotate the plane specified by $\omega$ and $r$ while preserving the 
intersection of the plane with the ray $z$. 

\subsection*{Another Change of Variables}
Previously, we had been specifying the plane with the variables $\omega$ and $r$. 
Now we will instead specify the plane by the variables $\omega$ and $t$ where $tz$ is
the point where the ray $z$ intersects the plane.

\textbf{Note:} $r = t<\omega,z>$

\textbf{Jacobian} $\frac{\partial r}{\partial t} = <\omega, z>$

Also, for convenience we choose $tz = z^{\omega,r}$ to be the origin of the
plane containing the $b_{\pi_i}$'s.

We will now bound the quantity:
$$
\max_{b_{\pi_1},\ldots,b_{\pi_d},t} \Pr_\omega[<\omega,r> < \epsilon]
$$
Subject to the constraint that $\norm{b_{\pi_i}} \leq \Gamma$ and $|t| \leq \Gamma$.
Where the distribution for $\omega$ is:
$$
<\omega,z>\left(\prod_{j \not\in \{\pi_1,\ldots,\pi_d\}} \int_{a_j} 
 [<\omega,a_j> \leq t<\omega,z>] \mu_i(a_j)\right) \prod_{i=1}^d \mu_{\pi_i}(a_{\pi_i})
$$
Observe that in the above expression everything except the term $<\omega,z>$ is like a
constant for small changes in $\omega$. We will write this distribution function as
$<\omega,z>f(\omega)$.

\subsection*{``Longitude and Latitude''}
We will now change to ``Longitude and Latitude'' where we express the unit vector
$\omega$ as an angle, $\theta$ (latitude) and a point, $\phi$ on the unit sphere of 
$d-1$ dimensions. 

That is, $\omega \in S^{d}$ becomes $\theta \in [0,\pi/2]$ and $\phi \in S^{d-1}$. Where
$\cos(\theta) = <\omega,z>$.

The Jacobian of this transformation is $[\sin(\theta)]^{d-1}$ which is like a constant for
$\theta \rightarrow \pi/2$.

Therefore, we get that:
$$
\max_{b_{\pi_1},\ldots,b_{\pi_d},t} \Pr_\omega[<\omega,r> < \epsilon] \leq
\max_{b_{\pi_1},\ldots,b_{\pi_d},t,\phi} \Pr_\theta[\cos(\theta) < \epsilon]
$$
Where the density is the same as before except $<\omega,z>$ is replaced by $\cos(\theta)$.
That is, the density is $f(\theta)\cos(\theta)$.

\textbf{Note:} We could derive a $\theta_0$ such that $\theta_0 = \text{poly}(n,d,1/\sigma)$ and 
$0 \leq \theta \leq \theta' \leq \theta_0$ 
$$
\frac{f(\theta)}{f(\theta')} \leq e
$$
(This is what was meant earlier by the comment that $f$ is almost constant for small
changes in $\omega$)

Therefore, we could show that:
$$
\Pr_\theta[\cos(\theta) < \epsilon] < \text{poly}(n,d,\frac{1}{\sigma})\epsilon^2
$$

\subsection*{Putting it All Together}
We now have bounds showing it is unlikely the distance to the boundary is small and it 
is unlikely that the angle is small. Therefore, we can apply a Combination Lemma to get
the following bound:

$$
\Pr_{\omega, r, b_{\pi_1},\ldots,b_{\pi_d}}\left[ \frac{
   \dist(z^{\omega,r},\partial\triangle(b_{\pi_1}\ldots b_{\pi_d})) <\omega,z>}{3\Gamma}
     <\epsilon \right] < \epsilon \text{poly}(n,d,\frac{1}{\sigma})
$$

This bound implies that the expected size of the shadow of the polytope is polynomial.

\end{document}













