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

\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}}
\newcommand{\E}{\mathbb{E}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\R}{\mathbb{R}}


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

\begin{document}

\lecture{11 --- October 1, 2021}{Fall 2021}{Sebastien Roch, UW-Madison}{Vasilis Kontonis}

\section{Overview}
In the last lecture we presented the \emph{decoupling} and \emph{comparison} 
theorems which will be usefull in the proof of the main result of this lecture:
the Hanson-Wright inequality. We have the following decoupling inequality.  In the lecture
we assumed that the diagonal elements of $A$ are zero but the same argument actually proves 
a stronger version without this assumption, see Remark 6.13 in \cite{ver}.
\begin{lemma}[Decoupling, Theorem 6.1.1 in \cite{ver}]
Let $A$ be an $n\times n$ matrix.
Let $X=(X_{1},X_{2},\dots, X_{n})\in\mathbb{R}^{n}$ be a random vector with independent, mean-zero coordinates $X_i$. Then for every convex function $F$
$$
\E\Big[ F \Big( \sum_{i\neq j} a_{ij} X_i X_j \Big) \Big] \leq \E \Big[ F(4 X^{T}AX' ) \Big],
$$
where $X^{'}$ is an independent copy of $X$.
\end{lemma}

The following comparison lemma shows that we can essentially replace the 
sub-Gaussian random variables $X, X'$ in the MGF of the quadratic form $X^T A X'$ by Gaussians.  
\begin{lemma}[Comparison, Lemma 6.2.3 in \cite{ver}]
Let $A$ be an $n\times n$ matrix and $X=(X_{1},X_{2},\dots, X_{n})\in\mathbb{R}^{n}$ be a random vector with independent, sub-Gaussian, mean-zero coordinates $X_i$. Let independent vectors $g, g^{'} \sim N(0, I_n)$, and assume $K= \max_i \lVert {X_i} \rVert_{\Psi_2} < \infty$. Then there exists a constant $C$ such that
$$
\E \exp(\lambda X^T A X^{'})\leq \E \exp(CK^2 \lambda g^T A g'),
$$
for any $\lambda \in \mathbb{R}$, where $X'$ is independent copy of $X$ and independent of $g$ 
and $g'$.
\end{lemma}

\section{Review of Matrix Norms and Singular Value Decomposition}
We reviewed basic facts about matrix norms and the singular value decomposition.
For details see the slides on \url{https://people.math.wisc.edu/~roch/mmids/}.


\section{The Proof of the Hanson-Wright Inequality}

In this lecture, we will prove the Hanson-Wright Inequality.  We first restate its statement
and then proceed to its proof.
\begin{theorem}[Hanson-Wright]
Let $X=(X_{1},X_{2},...,X_{n})\in\mathbb{R}^{n}$ be a random vector with independent, mean-zero, sub-gaussian coordinates. Let $A$ be an $n\times n$ matrix. Then, for every $t\geq 0$, we have
\begin{align*}
    \mathbb{P}[|X^{T}AX-\mathbb{E}[X^{T}AX]|\geq t ] 
    \leq 2 \exp\left( -c \min\left(\frac{t^2}{K^4||A||^{2}_{F}},\frac{t}{K^{2}||A||}\right) \right)\,, 
\end{align*}
where $K = \max_{i}||X_{i}||_{\psi_{2}}$ and $c > 0$ is some universal constant.
\end{theorem}
\begin{proof}
In what follows we have that \(X=\left(X_1, \ldots, X_n\right)\) is a random vector 
with independent mean-zero coordinates and \(X'\) be an independent copy of \(X\).
We will use the decoupling and comparison lemmas stated above.
Moreover, we will use the following estimate on the MGF of quadratic forms of independent 
Gaussian random variables.
\begin{lemma}[Gaussian Chaos MGF]
  Let \(g, g^{\prime} \sim N\left(0, I_{n}\right)\) be independent and \(A\) be an \(n \times n\) matrix. Then for any \(\lambda \in \R,\; |\lambda| \le c / \|A\|_2\), we have
  \[
    \E[\exp\left(\lambda g^TAg'\right)] 
    \le \exp\left(C\lambda^2 \|A\|^2_F\right).
  \]
  \end{lemma}
  We can decompose $X^T A X$ into a term involving the diagonal elements of $A$ and one
  with the off-diagonal:
  \[
    X^TAX = \sum_{i,j} a_{ij} X_i X_j
    = \sum_{i} a_{ii} X_i^2 + \sum_{i \ne j} a_{ij} X_i X_j.
  \]
  Since the $X_i$'s are independent, mean-zero random variables it holds that 
  \(
    \E[X^TAX] = \sum_{i} a_{ii} \E X_i^2.
  \)
  Using the fact that for any two random variables $X, Z$ it holds that 
  $\P[X+ Z \geq t] \leq \P[X \geq t/2] + \P[Z \geq t/2]$ we obtain 
  the following upper bound on the tail probability of the quadratic form
  \[
    \P\left[\left|X^TAX - \E(X^TAX))\right| \ge t\right] 
    \le
    \P\left[\sum_{i=1}^n a_{ii} (X_i^2 - \E X_i^2) \ge t/2 \right]
    + \P\left[\sum_{i \ne j} a_{ij} X_i X_j \ge t/2 \right].
  \]
  
Step 1: diagonal sum. 
$X_i$'s are independent, sub-gaussian random variables, 
and therefore, the random variables $X_i^2 - \E X_i^2$
are centered (mean-zero), independent, and sub-exponential. 
Using the fact that centering a random variable can only reduce its sub-exponential norm 
  we obtain 
  \[
    \left\|a_{ii} (X_i^2 - \E X_i^2)\right\|_{\Psi_1}
    \lesssim |a_{ii}| \|X_i^2\|_{\Psi_1}
    \lesssim |a_{ii}| \|X_i\|_{\Psi_2}^2
    \lesssim |a_{ii}| K^2.
  \]
  Thus we can apply Bernstein's Inequality.
\begin{lemma}[Bernstein's inequality (Theorem 2.8.1 in \cite{ver})] 
	Let $X_1, \ldots, X_N$ be independent, mean zero, sub-exponential random variables. Then, for every $t \geq 0$, we have
	\begin{equation*}
		\P\left[\left|\sum_{i=1}^{N}X_i\right| \geq t \right] 
		\leq 2\exp\left( -c \min\left\{\frac{t^2}{\sum_{i=1}^{N}\|X_i\|_{\psi_1}^2}, 
		\frac{t}{\max_i \|X_i\|_{\psi_1}}\right\}\right),
	\end{equation*}
where $c > 0$ is an absolute constant.
\end{lemma}
We can now bound the tail probability of the diagonal terms 
\begin{align*}
    \P\Big[\sum_{i=1}^n a_{ii} (X_i^2 - \E X_i^2) \ge t/2 \Big]
    &\leq 2 \exp\left(-c \min \left(\frac{t^2}{K^4\sum_i a_{ii}^2}, \frac{t}{K^2\max_i |a_{ii}|}\right)\right)
    \\
    &\leq 2 \exp\left(-c \min \left(\frac{t^2}{K^4\|A\|^2_F}, \frac{t}{K^2\|A\|_2}\right)\right),
    \end{align*}
    where we used the fact that $\max_{i} |a_{ii}| \leq \|A\|_2$ and
    that $\sum_{i} a_{ii}^2 \leq \|A\|_F^2$.  We move on to the off-diagonal terms.  
    Let \(S = \sum_{i \ne j} a_{ij} X_i X_j\).  
  By Markov's Inequality, we have that for any \(\lambda > 0\) it holds that 
  \[
    P[S \ge t / 2]=
    P\left[e^{\lambda S}  \ge e^{\lambda t/2}\right]
    \le \exp(-\lambda t/2) \E[\exp(\lambda S)].
  \]
  Given that \(|\lambda| \leq c /\|A\|\), we can use 
  the Decoupling, the Comparison, and the MGF of Gaussian Chaos lemmas to obtain
  \[
      \mathbb{E}[ \exp(\lambda S)]
      \leq \mathbb{E}[\exp(4 \lambda X^{\top} A X^{\prime} )  ]
      \leq \mathbb{E}[\exp( C_1 K^2 \lambda g^{\top} A g^{\prime})]
      \leq \exp\left(C_2 K^4 \lambda^{2}\|A\|_{F}^{2}\right),
  \]
  where $C_1, C_2$ are universal constants.
  Therefore, we obtain that 
  $   P[S \ge t / 2]
  \leq \exp\left(-\lambda t / 2 + C_2 K^4 \lambda^{2}\|A\|_{F}^{2}\right). $
  We can now pick the value of $\lambda \in (0,  c /\|A\|_2) $, 
  that maximizes the expression  
  $ -\lambda t / 2 + C_2 K^4 \lambda^{2}\|A\|_{F}^{2} $
  and obtain that
  \[
    P[S \ge t / 2]
    \le 2 \exp\left(- c_1 \min \left(\frac{t^2}{K^4\|A\|^2_F}, \frac{t}{K^2\|A\|_2}\right)\right),
  \]
  for some other universal constant $c_1$.
  To complete the proof we put together the above estimates for the diagonal
  and off-diagonal tail probabilities and replace the corresponding
  universal constants by another one.
\end{proof}
As a corollary of the Hanson-Wright inequality we give the following theorem.
\begin{theorem} \emph{(Concentration for Random Vectors, Thm 6.3.2 in \cite{ver})}
  Let $X=(X_{1},X_{2},...X_{n})\in\mathbb{R}^{n}$ be a random vector with independent, mean-zero, sub-gaussian coordinates with  \(K = \max \|X_i\|_{\Psi_2} < \infty \).
  Let \(B\) be an \(n \times m\) matrix then it holds
  \(
    \left\|\|BX\|_2 - \|B\|_F\right\|_{\Psi_2} \le CK^2\|B\|.
  \)
\end{theorem}

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