\documentclass[11pt]{article}
\usepackage[letterpaper,margin=1in]{geometry}
\usepackage{amsmath,amsbsy,amsfonts,amssymb,amsthm,commath}
\usepackage[round]{natbib}
\usepackage{hyperref}

% math font macros

\def\ddefloop#1{\ifx\ddefloop#1\else\ddef{#1}\expandafter\ddefloop\fi}
% Blackboard fonts: \bbA, \bbB, ...
\def\ddef#1{\expandafter\def\csname bb#1\endcsname{\ensuremath{\mathbb{#1}}}}
\ddefloop ABCDEFGHIJKLMNOPQRSTUVWXYZ\ddefloop
% Calligraphic fonts: \cA, \cB, ...
\def\ddef#1{\expandafter\def\csname c#1\endcsname{\ensuremath{\mathcal{#1}}}}
\ddefloop ABCDEFGHIJKLMNOPQRSTUVWXYZ\ddefloop
% Bold fonts (for vectors, matrices, etc.): \vA, \vB, ..., \va, \vb, ...
\def\ddef#1{\expandafter\def\csname v#1\endcsname{\ensuremath{\boldsymbol{#1}}}}
\ddefloop ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz\ddefloop
% Bold fonts (for vectors, matrices, etc.): \valpha, \vbeta, ...,  \vGamma, \vDelta, ...,
\def\ddef#1{\expandafter\def\csname v#1\endcsname{\ensuremath{\boldsymbol{\csname #1\endcsname}}}}
\ddefloop {alpha}{beta}{gamma}{delta}{epsilon}{varepsilon}{zeta}{eta}{theta}{vartheta}{iota}{kappa}{lambda}{mu}{nu}{xi}{pi}{varpi}{rho}{varrho}{sigma}{varsigma}{tau}{upsilon}{phi}{varphi}{chi}{psi}{omega}{Gamma}{Delta}{Theta}{Lambda}{Xi}{Pi}{Sigma}{varSigma}{Upsilon}{Phi}{Psi}{Omega}{ell}\ddefloop

% other macros

\newcommand\ip[1]{\langle #1 \rangle} % inner product
\newcommand{\E}{\ensuremath{\mathbb{E}}} % expectation
\renewcommand{\P}{\ensuremath{\mathbb{P}}} % probability
\newcommand{\var}{\ensuremath{\operatorname{var}}} % variance
\newcommand{\vol}{\ensuremath{\operatorname{vol}}} % volume
\newcommand{\unitball}[1][d]{\ensuremath{B^{#1}}} % unit ball
\newcommand{\unitsphere}[1][d-1]{\ensuremath{S^{#1}}} % unit sphere
\newcommand{\logmgf}[1]{\ensuremath{\psi_{#1}}} % log mgf
\newcommand{\Normal}{\ensuremath{\operatorname{N}}} % normal distribution

% environments

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newenvironment{solution}{\noindent\emph{Solution.}}{\hfill$\square$}

%-------------------------------------------------------------------------------

\title{COMS 4772 Fall 2016 Homework 1 \\ Due Friday, September 30}
\author{% TODO put your Full Name and UNI here
  }
\date{%
  }

%-------------------------------------------------------------------------------

\begin{document}
\maketitle

\noindent\textbf{Instructions}:
\begin{itemize}
  \item
    Pick four of the following five problems to be graded.
    (If you do not designate which problems should be graded, we will pick arbitrarily for you.)

  \item
    The usual homework policies (\url{http://www.cs.columbia.edu/~djhsu/coms4772-f16/about.html}) are, of course, in effect.

  \item
    Using this \LaTeX\ template will be helpful for grading purposes.

\end{itemize}

\newpage

%-------------------------------------------------------------------------------

\begin{problem}[25 points]
  In this problem, ``volume'' refers to $(d-1)$-dimensional volume (or ``surface area'' in $d$-dimensions).
  \begin{enumerate}
    \item[(a)]
      Prove that there is a constant $C>0$ (not depending on $d$) such that, for any set $T \subset \unitsphere$ of $|T|=d^{100}$ unit vectors, the set
      \begin{equation*}
        \bigcap_{\vu \in T}
        \cbr{
          \vx \in \unitsphere : \abs{\ip{\vu,\vx}} \leq C\sqrt{\frac{\ln d}{d}}
        }
      \end{equation*}
      accounts for $99\%$ of the volume of $\unitsphere$.
      (Assume $d\geq2$ so $\ln(d) > 0$.)

    \item[(b)]
      Prove that there is a constant $c>0$ (not depending on $d$) such that, for any $\vu \in \unitsphere$, the set
      \begin{equation*}
        \cbr{
          \vx \in \unitsphere : \abs{\ip{\vu,\vx}} > \frac{c}{\sqrt{d}}
        }
      \end{equation*}
      accounts for $99\%$ of the volume of $\unitsphere$.

  \end{enumerate}
\end{problem}

\begin{solution}
% TODO Put solution here.
\end{solution}

\newpage

%-------------------------------------------------------------------------------

\begin{problem}[25 points]
  Let $B_1^d := \cbr[0]{ \vx \in \bbR^d : \sum_{i=1}^d |x_i| \leq 1 }$ denote the $d$-dimensional \emph{cross polytope} (as explained in Ball's lecture notes).
  \begin{enumerate}
    \item[(a)]
      Prove that $\unitball \subseteq \sqrt{d} B_1^d$.

    \item[(b)]
      Use the fact $\unitball \subseteq \sqrt{d} B_1^d$ to derive a bound on the volume of $\unitball$ of the form
      \[
        \vol(\unitball)
        \ \leq \
        c \cdot \del{ \frac{c'}{d} }^{d/2}
      \]
      for some positive constants $c, c' >0$.
      Explain each step in your derivation.

      \emph{Hint}: Stirling's approximation implies $\sqrt{2\pi} n^{n+1/2}e^{-n} \leq n! \leq n^{n+1/2}e^{1-n}$ for all $n \in \bbN$.
  \end{enumerate}
\end{problem}

\begin{solution}
% TODO Put solution here.
\end{solution}

\newpage

%-------------------------------------------------------------------------------

\begin{problem}[25 points]
  Let $X$ be an $[a,b]$-valued random variable (i.e., $\P(X\in\intcc{a,b})=1$) with $\E(X) = 0$.
  For simplicity, assume $X$ has a probability density function $f$.
  In this problem, you will prove $\logmgf{X}(\lambda) \leq \lambda^2(b-a)^2/8$ using a technique due to \citet{McAllesterO03}.
  \begin{enumerate}
    \item[(a)]
      Consider the family of density functions $\{ g_\lambda : \lambda \in \bbR \}$, where
      \begin{align*}
        g_\lambda(x) & \ := \ \frac{e^{\lambda x}}{\E e^{\lambda X}} f(x)
        \quad \text{for all $x \in \bbR$} \,.
      \end{align*}
      Briefly verify that if $Y_\lambda \sim g_\lambda$, then
      \begin{align*}
        \E(Y_\lambda) & \ = \ \logmgf{X}'(\lambda)
        \,,
        \\
        \var(Y_\lambda) & \ = \ \logmgf{X}''(\lambda)
        \,,
      \end{align*}
      where $\logmgf{X}'$ is the first-derivative of $\logmgf{X}$, and $\logmgf{X}''$ is the second-derivative of $\logmgf{X}$.
      (You don't need to write much at all for this part.)

    \item[(b)]
      Prove that any $[a,b]$-valued random variable has variance at most $(b-a)^2/4$.

    \item[(c)]
      The fundamental theorem of calculus implies
      \begin{align*}
        \logmgf{X}(\lambda)
        & \ = \
        \int_0^\lambda \int_0^\mu \logmgf{X}''(\gamma) \dif\gamma \dif\mu
        \,.
      \end{align*}
      Use this identity and the results of parts (a) and (b) to prove that
      $\logmgf{X}(\lambda) \leq \lambda^2 (b-a)^2/8$.

  \end{enumerate}
\end{problem}

\begin{solution}
% TODO Put solution here.
\end{solution}

\newpage

%-------------------------------------------------------------------------------

\begin{problem}[25 points]
  Let $\vU$ be a random unit vector with the uniform density on $\unitsphere$, and let $X := \ip{\vv,\vU}$, where $\vv$ is a fixed unit vector in
  $\unitsphere$.
  \begin{enumerate}
    \item[(a)]
      Prove that $\logmgf{X^2-\E(X^2)}(\lambda) \leq \logmgf{Z^2-1}(\lambda/d)$
      for all $\lambda \in \bbR$, where $Z \sim \Normal(0,1)$.

      \emph{Hint}: You may use the fact that if $Y_d \sim \chi^2(d)$ and $\vU$ are independent, then $\sqrt{Y_d}\vU \sim \Normal(\boldsymbol0,\vI)$ (standard multivariate Gaussian in $\bbR^d$).
      Jensen's inequality may also be useful.

    \item[(b)]
      Use the result of part (a) to derive a tail bound for $\abs{X^2-\E(X^2)}$.
      Explain each step in your derivation.

  \end{enumerate}
\end{problem}

\begin{solution}
% Put solution here.
\end{solution}

\newpage

%-------------------------------------------------------------------------------

\begin{problem}[25 points]
  Let $\Phi \colon \bbR \to [0,1]$ denote the cumulative distribution function for $\Normal(0,1)$, i.e., $\Phi(t) = \P(Z \leq t)$ where $Z \sim \Normal(0,1)$.
  Prove that for any $d \in \bbN$, if
  \begin{enumerate}
    \item $X_1, X_2, \dotsc, X_d$ are independent random variables;

    \item $\E X_i = 0$ and $\E X_i^2 = 1$ for all $i\in[d]$;

  \end{enumerate}
  then for a $1-o(1)$ fraction of unit vectors $\vu \in \unitsphere$, the random vector $\vX = (X_1,X_2,\dotsc,X_d)$ satisfies
  \begin{equation*}
    \sup_{t \in \bbR}
    \abs{ \P\del{ \ip{\vu,\vX} \leq t } - \Phi(t) }
    \ \leq \
    O\del{ \frac{\rho}{d^{0.49}} }
    \,,
  \end{equation*}
  where $\rho := \max_{i\in[d]} \E |X_i|^3$.

  You can use the following theorem (which you do not need to prove):
  \begin{center}
    \framebox[0.9\textwidth]{%
      \begin{minipage}{0.88\textwidth}
        \begin{theorem}[Berry-Ess\'een theorem]
          \label{thm:clt}
          There is an absolute positive constant $C>0$ such that the
          following holds.
          Let $Y_1, Y_2, \dotsc, Y_n$ be independent random variables
          with $\E Y_i = 0$, $\sigma_i^2 := \E Y_i^2 < \infty$.
          Define $v_n := \sum_{i=1}^n \sigma_i^2$ and $\rho_n :=
          \sum_{i=1}^n \E|Y_i|^3$.
          Then
          \begin{equation*}
            \sup_{t \in \bbR}
            \abs{
              \P\del{
                \frac{Y_1 + Y_2 + \dotsb + Y_n}{\sqrt{v_n}} \leq t
              }
              - \Phi(t)
            }
            \ \leq \
            \frac{C\rho_n}{v_n^{3/2}}
            \,.
          \end{equation*}
        \end{theorem}
      \end{minipage}%
    }
  \end{center}
\end{problem}

\begin{solution}
% TODO Put solution here.
\end{solution}

\newpage

%-------------------------------------------------------------------------------

\begin{thebibliography}{1}
  \bibitem[McAllester and Ortiz(2003)]{McAllesterO03}
  D.~McAllester and L.~Ortiz.
  \newblock Concentration inequalities for the missing mass and for histogram rule error.
  \newblock \emph{Journal of Machine Learning Research}, 4(Oct):895--911, 2003.
\end{thebibliography}

\end{document}
