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

\newcommand\independent{\protect\mathpalette{\protect\independenT}{\perp}}

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

\begin{document}

\lecture{10 --- September 29, 2021}{Fall 2021}{Sebastien Roch, UW-Madison}{Liam Johnston}

\section{Overview}

In the last lecture we stated the Hanson-Wright inequality. 

In this lecture we explore some useful tricks that will be helpful in proving the Hanson-Wright inequality.

\begin{theorem}[Hanson-Wright inequality (Thm 6.2.1. in Vershynin)]
Let $X=(X_1,\dots,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\geq0$, we have
\begin{equation*}
\mathbb{P}\{|X^{T}AX-\mathbb{E}X^{T}AX|\geq t\}\leq 2\exp{\big{[}-c\min{\big{(}\frac{t^2}{K^4||A||_{F}^{2}},\frac{t}{K^2||A||}\big{)}}\big{]}},
\end{equation*}
where $K=\max_i||X_i||_{\psi_{2}}$.
\end{theorem}

Recall the following lemma, which we apply later today,

\begin{lemma}[Pulled from previous lecture]\label{prev-class-lemma}
Let $Y$ and $Z$ be independent random variables with $\mathbb{E}Z=0$. Then for every convex function $F$
\begin{equation*}
	\mathbb{E}\big{[}F(y)\big{]}\leq\mathbb{E}\big{[}F(Y+Z)\big{]}
\end{equation*}
\end{lemma}

\newpage

\section{Useful Tricks for Proving Hanson-Wright Inequality}

\paragraph{Setting:} Let $A$ be an $n\times n$ matrix and $\underset{\sim}X=(X_1,\dots,X_n)$ where coordinates are independent, zero-mean and sub-gaussian. Our objective is to prove a concentration inequality for $\underset{\sim}X^{T}A\underset{\sim}X$.

\subsection{Idea 1: Decoupling}

\begin{theorem}[Decoupling (Thm 6.1.1. in Vershynin)]
Let $A$ be an $n\times n$, diagonal-free matrix (i.e. the diagonal entries of $A$ equal zero). Let $\underset{\sim}{X}=(X_1,\dots,X_n)$ be a random vector with independent mean zero coordinates $X_i$. Then, for every convex function $F:\mathbb{R}\rightarrow\mathbb{R}$, one has
\begin{equation*}
	\mathbb{E}F(\underset{\sim}X^{T}A\underset{\sim}X)\leq\mathbb{E}F(4\underset{\sim}X^{T}A\underset{\sim}X')
\end{equation*}
where $\underset{\sim}X'$ is an independent copy of $\underset{\sim}X$.
\end{theorem}

\begin{proof}

{\bf{Note:}} For any subset of indices $I\subseteq[n]$
\begin{equation*}
	\sum_{(i,j)\in I\times I^C}a_{ij}X_iX_j\ {\buildrel\mathcal{D} \over =}\ \sum_{(i,j)\in I\times I^C}a_{ij}X_iX'_j 
\end{equation*}
because coordinates are independent.

Let

\begin{equation*}
	\delta_i=
	\begin{cases}
		0 & w.p.\ 0.5 \hspace{15pt}\forall i\in[n]\text{ independently} \\
		1 & w.p.\ 0.5
	\end{cases}
\end{equation*}
and $I=\{i:\delta_i=1\}$.

{\bf{Note:}} 
\begin{equation*}
	\begin{aligned}
		\mathbb{E}\bigg{[}\sum_{(i,j)\in I\times I^C}a_{ij}X_iX_j\big{|}\underset{\sim}X\bigg{]}=&\mathbb{E}\bigg{[}\sum_{i\neq j}\delta_i(1-\delta_j)a_{ij}X_iX_j\big{|}\underset{\sim}X\bigg{]} \\
		=&\sum_{i\neq j}a_{ij}X_iX_j\mathbb{E}\underbrace{\big{[}\delta_i(1-\delta_j)\big{]}}_{i\neq j\implies\delta_i\text{ independent of }\delta_j} \\
		=&\sum_{i\neq j}\frac{a_{ij}X_iX_j}{4}
	\end{aligned}
\end{equation*}

We now turn our attention to
\begin{equation*}
	\begin{aligned}
		\mathbb{E}\bigg{[}F(4\sum_{(i,j)\in I\times I^C}a_{ij}X_iX_j)\bigg{]}=&\mathbb{E}\bigg{[}\mathbb{E}\big{[}4\sum_{(i,j)\in I\times I^C}a_{ij}X_iX_j\big{|}\underset{\sim}X\big{]}\bigg{]}\hspace{25pt}\text{(tower property)} \\
		\leq&\mathbb{E}\bigg{[}F\big{(}\mathbb{E}\big{[}4\sum_{(i,j)\in I\times I^C}a_{ij}X_iX_j\big{|}\underset{\sim}X\big{]}\big{)}\bigg{]}\hspace{25pt}\text{(By Jensen's)} \\
		=&\mathbb{E}\bigg{[}F\big{(}\underset{\sim}X^{T}A\underset{\sim}X\big{)}\bigg{]}\hspace{55pt}(\star)
	\end{aligned}
\end{equation*}

{\bf{Note:}} There exists a \textit{deterministic} set $J\subseteq[n]$ such that $(\star)$ holds with $I=J$.

To complete the sum, write
\begin{equation*}
	\begin{aligned}
		\underset{\sim}X^{T}A\underset{\sim}X=&\underbrace{\sum_{(i,j)\in J\times J^C}a_{ij}X_iX'_j}_{=y}+\underbrace{\sum_{(i,j)\in J\times J}a_{ij}X_iX'_j}_{=z_1}+\underbrace{\sum_{(i,j)\in J^C\times[n]}a_{ij}X_iX'_j}_{=z_2}
	\end{aligned}
\end{equation*}
Let $g=\sigma\big{(}(X_i)_{i\in J},(X'_i)_{i\in J^C}$. Then $y\in g$ (i.e. $y$ is $g$-measurable) and

\begin{equation*}
	\mathbb{E}[z_1|g]=0=\mathbb{E}[z_2|g]
\end{equation*}

Applying the lemma from the previous lecture (see top of notes), we have

\begin{equation*}
	F(4y)\leq\mathbb{E}\big{[}F(4y+4z_1+4z_2)|g\big{]}
\end{equation*}
Taking the expectation of both sides yields the result.
\end{proof}

% Comparison
\subsection{Idea 2: Comparison}

{\bf{Note:}} We use this to bound the moment generating function.

\begin{theorem}[Comparison (Thm 6.2.3 in Vershynin)]
Assuming the general setting described above with the addition of $K=\max_i||X_i||_{\psi_{2}}<+\infty$. Let $g,g'\sim N(0,I_n)$ independent. Then
\begin{equation*}
	\mathbb{E}\bigg{[}\exp{(\lambda\underset{\sim}X^{T}A\underset{\sim}X')}\bigg{]}\leq\mathbb{E}\bigg{[}\exp{(c\lambda k^2g^{T}Ag')}\bigg{]}
\end{equation*}
\end{theorem}

\begin{proof}
Write $Y=A\underset{\sim}X'$.
\begin{equation*}
	\begin{aligned}
		\mathbb{E}\bigg{[}\exp{(\lambda\underset{\sim}X^{T}A\underset{\sim}X')}\big{|}\underset{\sim}X'\bigg{]}=&\mathbb{E}\bigg{[}\exp{\big{(}\lambda\sum_{i=1}^{n}X_iY_i\big{)}}\big{|}\underset{\sim}X'\bigg{]} \\
		=&\prod_{i=1}^{n}\mathbb{E}\bigg{[}\exp{\big{(}\lambda X_iY_i\big{)}}\big{|}\underset{\sim}X'\bigg{]} \\
		\leq&\prod_{i=1}^{n}\exp{\big{(}cK^2\lambda^2Y_{i}^2\big{)}} \\
		=&\exp{\big{(}cK^2\lambda^2||A\underset{\sim}X'||_{2}^{2}\big{)}}
	\end{aligned}
\end{equation*}

Now replacing $X$ by $g$ and using the moment generating function of normal random variables we get
\begin{equation*}
	\mathbb{E}\big{[}\exp{(\mu g^{T}AX')}|X'\big{]}=\exp{\big{(}\frac{1}{2}\mu^2||AX'||_{2}^{2}\big{)}}
\end{equation*}
and selecting $\mu=\sqrt{2c}K\lambda$ we get the desired result
\begin{equation*}
	\mathbb{E}\big{[}\exp{(\lambda X^{T}AX')}\big{]}\leq\mathbb{E}\big{[}\exp{(\sqrt{2c}K\lambda g^{T}AX')}\big{]}
\end{equation*}
\end{proof}

%\bibliography{mybib}
\bibliographystyle{alpha}

\begin{thebibliography}{77}

\bibitem{vershynin2019}
R. Vershynin,
\emph{High dimensional probability. An introduction with applications in Data Science},
Cambridge University Press, 2019.

\end{thebibliography}

\end{document}