\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{epsfig}

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{
      \hbox to 5.78in { {\bf MATH888: High-dimensional probability and statistics } \hfill #2 }
      \vspace{4mm}
      \hbox to 5.78in { {\Large \hfill #5  \hfill} }
      \vspace{2mm}
      \hbox to 5.78in { {\em #3 \hfill #4} }
    }
  }
  \end{center}
  \vspace*{4mm}
}

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

\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}

% 1-inch margins, from fullpage.sty by H.Partl, Version 2, Dec. 15, 1988.
\topmargin 0pt
\advance \topmargin by -\headheight
\advance \topmargin by -\headsep
\textheight 8.9in
\oddsidemargin 0pt
\evensidemargin \oddsidemargin
\marginparwidth 0.5in
\textwidth 6.5in

\parindent 0in
\parskip 1.5ex
%\renewcommand{\baselinestretch}{1.25}

%%%%% Added by me %%%%%%
%\usepackage{cancel}
\usepackage{bm}
%\usepackage[mathscr]{eucal}
\newtheorem{remark}[theorem]{Remark}
\DeclareMathOperator{\Cov}{Cov}
\DeclareMathOperator{\tr}{tr}
\def\cX{{\mathcal{X}}}
\def\cP{{\mathcal{P}}}
\def\bE{{\mathbb{E}}}
\def\bR{{\mathbb{R}}}
\def\bS{{\mathbb{S}}}
\def\mB{{\bm{B}}}
\def\mU{{\bm{U}}}
\def\mD{{\bm{D}}}
\def\mSig{{\bm{\Sigma}}}
\def\vX{{\bm{X}}}
\def\vz{{\bm{z}}}
\def\vu{{\bm{u}}}
\def\vw{{\bm{w}}}
\def\vmu{{\bm{\mu}}}
\def\vtheta{{\bm{\theta}}}
\def\<{\langle}
\def\>{\rangle}

\begin{document}

\lecture{14 --- October 8, 2021}{Fall 2021}{Sebastien Roch, UW-Madison}{Nayoung Lee}

\section{Overview}

In the last lecture we discussed tail inequalities for the norm of sub-Gaussian vectors and obtained an error bound for sub-Gaussian vector using the Hanson-Wright inequality.

In this lecture we will discuss mean estimation of i.i.d. sub-Gaussian random vectors and derive an error bound.

\section{Application to mean estimation}

\subsection{Review: Tail inequalities for quadratic forms of sub-Gaussian vectors}
We begin by reviewing relevant concepts.

\begin{itemize}
    \item For a symmetric matrix $\mSig$, it has eigenvalue decomposition: $\mSig=\mU \mD \mU^T$.
    \item $\mSig \succeq 0$ denotes that $\mSig$ is a positive semi-definite matrix, which means $D_{i,i}\geq 0$ for all i.
    \item $\|\mB\|_F^2 = \tr (\mB^T\mB)$
    \item $\|\mB\|_2^2 = \|\mB^T \mB\|_2$
    
    \item For sub-Gaussian random vector $\vz \in \bR^p$ with $\|\vz\|_{\psi_2}\leq K$, $\bE\vz=0$ and $\mSig \in \bR^{p\times p}\succeq 0$, we have $\forall t \geq 0$: 
    $$ \cP(\vz^T \mSig \vz \geq CK^2 \tr (\mSig) + t )\leq \exp (- \frac{ct}{K^2 \| \mSig \|_2}). $$

\end{itemize}

\subsection{Mean estimation of sub-Gaussian random vectors}
\begin{lemma}
Let $\vz^{(1)}, \cdots, \vz^{(n)} \in \bR^p$ be independent, mean zero, sub-Gaussian vectors. Then we have 
$$\|\sum_{i=1}^{n}\alpha_i \vz^{(i)}\|_{\psi_2}^{2} \lesssim \sum_{i=1}^{n} \alpha_i \| \vz^{(i)} \|_{\psi_2}^2.$$
\end{lemma}

\begin{proof} The key idea is to project $\vz$ on unit vectors.

For any $\vu \in S^{p-1}$, 
\begin{align*}
    \| \<\vu, \sum_{i=1}^n \alpha_i \vz^{(i)}\> \|_{\psi_2}^2 &= \| \sum_{i=1}^k \alpha_i \<\vu, \vz^{(i)} \> \|_{\psi_2}^2 \\ 
    &\lesssim \sum_{i=1}^n \alpha_i^2 \| \< \vu, \vz^{(i)} \> \|_{\psi_2}^2 \qquad (\text{by Prop 2.6.1 in \cite{ver}}).
    %\qquad (\bE\<\vu, \vz^{(i)}\> = \<u, \bE \vz^{(i)}\> = 0)
\end{align*}

By taking the supremum on the equation above, we have,

\begin{align*}
    \sup_{\vu \in S^{p-1}} \| \< \vu, \sum_{i=1}^n \alpha_i \vz^{(i)}\> \|_{\psi_2}^2 &= \sup_{\vu} \|\sum_{i=1}^n \alpha_i \< \vu, \vz^{(i)}\> \|_{\psi_2}^2 \\
    &\lesssim \sup_\vu \sum_{i=1}^n \alpha_i^2 \|\<\vu,\vz^{(i)}\>\|\\
    &\leq \sum \alpha_i^2 \sup_{\vu} \|\<\vu, \vz^{(i)}\>\|_{\psi_2}^{2}.
\end{align*}\
The last inequality uses the fact that the sum of supremum is equal or larger than the superemum of sum. Also note that the second line holds for universal constant. 

\end{proof}

\begin{theorem}
Let $\vX^{(1)},\cdots,\vX^{(n)} \in \bR^p$ be i.i.d random vectors with $\bE(\vX^{(i)})=\vmu$ and $\Cov(\vX^{(i)}) = \bE((\vX^{(i)}-\vmu)(\vX^{(i)}-\vmu)^T) = \mSig \succeq 0$. 
Assume further that for all $\vw \in \bR^p$, $$\| \< \vw, \vX^{(i)}-\vmu \>\|_{\psi_2} \leq K \sqrt{\bE(\<\vw, \vX^{(i)}-\vmu\>^2)}$$ holds. 
Let $\bar{\vX} = \frac{1}{n} \sum_{i=1}^{n}\vX^{(i)}$, the mean of $\vX^{(1)}, \cdots \vX^{(n)}$. Then, w.p $\geq 1-\delta$, we have 
$$\| \bar{\vX}-\vmu \|_2^2 \preceq \frac{K^2}{n} \| \mSig \|_2 \left\{ \frac{\tr \mSig}{\| \mSig \|_2} + \log \frac{1}{\delta} \right\}.$$

\end{theorem}

\begin{proof}
Let $\vz^{(i)} = \sqrt{\Sigma^\dagger}(\vX^{(i)}-\vmu)$

Recall, the eigenvalue decomposition $\mSig = \mU \mD \mU^T$. The pseudo inverse of $\mSig$, $\mSig^\dagger = \mU \mD^\dagger \mU^T$, where $D_{ii}^\dagger$ is $1/D_{i,i}$ for $D_{i,i}>0$ and 0 otherwise. Also, $\sqrt{\mSig^\dagger} = \mU \sqrt{\mD^\dagger} \mU^T$ and $\sqrt{\mSig} = \mU \sqrt{\mD} \mU$, where $\sqrt{\mD\dagger}$ and $\sqrt{\mD}$ takes a square root of diagonal entries of $\mD$ and $\mD^\dagger$. respectively. 

$\vX^{(i)}=\sqrt{\mSig} \vz^{(i)}+\vmu$ with probability 1. Therefore, $\|\bar{\vX}-\vmu\|_2^2 = \bar{\vz}^T \mSig \bar{\vz}$, where $\bar{\vz}$ is the average of $\vz^{(i)}$. 

Now it remains to bound $\|\vz^{(i)}\|_{\psi_2}$. For $\vw \in S^{p-1}$, 
\begin{align*}
    \|\<\vw, \vz^{(i)} \> \|_{\psi_2} &= \|\<\vw, \sqrt{\mSig^\dagger}(\vX^{(i)}-\vmu)\>\|_{\psi_2}\\
    &= \|\<\sqrt{\mSig^\dagger}\vw, (\vX^{(i)}-\vmu)\>\|_{\psi_2} \qquad (\sqrt{\mSig^\dagger}: \text{symmetric}) \\
    & \leq K \sqrt{\bE(\<\sqrt{\mSig^\dagger}\vw, \vX^{(i)}-\vmu\>^2)} \\
    & \leq \cdots \\
    & \leq K
\end{align*}

The rest of the proof uses Lemma to show $\|\bar{\vz}\|_{\psi_2}^2 \lesssim \frac{K^2}{n}$. Then plug into to $\cP(\vz^T \mSig \vz \geq CK^2 \tr(\mSig)) +t$

\end{proof}

\paragraph{Remark: }

\begin{itemize}
    \item Notice the resemblance of Theorem 2. to the mean estimation of sub-Gaussian random vectors discussed on the last lecture. The intuition is that similar to the fact that sub-Gaussian is closely related to $\sigma^2$, we now project $\vX^{(i)}-\vmu$ to $\vw$ and observe the standard deviation. 
    
    \item $\frac{\tr \mSig}{\| \mSig \|_2}$ can be interpreted as a \textit{stable rank}. The numerator $\tr \mSig$ is the sum of eigenvalues of $\mSig$ and the denominator $\| \mSig \|_2$ is the largest eigenvalue. If the eigenvalues of $\mSig$ are the same, the stable rank is equal to $p$ whereas if many eigenvalues of $\mSig$ are close to zero, stable rank is small. 

\end{itemize}


Next time, we will be looking at application to linear regression.


\bibliographystyle{alpha}


%\bibliography{mybib}
\bibliographystyle{alpha}

\begin{thebibliography}{77}

 \bibitem{ver}
R. Vershynin,
\emph{High-Dimensional Probability: An introduction with Applications in Data Science},
Cambridge University Press, 2008.

\end{thebibliography}

\end{document}