\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 kartik sreenivasan
\newcommand{\eg}{{\it e.g.}, }
\newcommand{\ie}{{\it i.e.}, }

\begin{document}

\lecture{8 --- September 24, 2021}{Fall 2021}{Sebastien Roch, UW-Madison}{Jeremy Johnson}

\section{Overview}

In the last lecture we expand our understanding of sub-exponential distributions and prove useful concentration inequalities for the sum of sub-exponential random variables and for the norm of random vectors with sub-gaussian coordinates.

\section{Sub-Exponential Random Variables}

We recall the class of sub-exponential random variables; a class of random variables whose tails decay slightly slower than those of sub-gaussian random variables. Similar to sub-gaussian random variables, this class of random variable can be understood through the following norm:

\begin{definition}
The  \textbf{sub-exponential norm} of $X\in \mathbb{R}$ is 
\[
\Vert X\Vert_{\psi_1} = \inf\left\{ t > 0 : \mathbb{E} \exp(\vert X \vert /t) \leq 2\right\}.
\]
If $\Vert X\Vert_{\psi_1}$ is finite, we say that $X$ is \textbf{sub-exponential}.
\end{definition}

\begin{fact}[See 2.7.1 in V for greater detail]
The above is equivalent (up to some absolute constant) to $\mathbb{P}(\vert X\vert \geq t)\leq 2 \exp(-ct/\Vert X\Vert_{\psi_1})$ for all $t\geq 0$. Moreover, the MGF of $\vert X\vert$ is bounded at some point, namely
\[
\mathbb{E} \exp(\vert X\vert/ K_4) \leq 2.
\]
\end{fact}

We will see that sub-exponential distributions and sub-gaussian distributions are closely related. First, note that any sub-gaussian distribution is sub-exponential. Second, the square of a sub-gaussian random variable is sub-exponential:

\begin{lemma}[2.7.6 in V]
A random variable $X$ is sub-gaussian if and only if $X^2$ is sub-exponential. Moreover,
\[
\Vert X^2\Vert_{\psi_1} = \Vert X \Vert^2_{\psi_2}.
\]
\end{lemma}
\emph{Idea of Proof. }\\
We have that
\[
\Vert X^2\Vert_{\psi_1} = \inf\left\{ t > 0 : \mathbb{E} \exp(\vert X^2 \vert /t) \leq 2\right\}.
\]
For any $t$ for which this is true, take $(\sqrt{t})^2$ in the definition of the sub-gaussian norm.

With the above, we can now state a concentration inequality for sums of independent sub-exponential random variables.

\begin{theorem}[Bernstein's inequality]
Let $X_1,\dots, X_N$ be independent, mean zero, sub-exponential random variables. Then, for every $t\geq 0$, we have
\[
\mathbb{P}\left\{\left\vert \sum_{i=1}^N X_i\right\vert \geq t\right\}\leq 2 \exp\left[-c\min\left(\frac{t^2}{\sum_{i=1}^N\Vert X_i\Vert^2_{\psi_1}}, \frac{t}{\max_i\Vert X_i \Vert_{\psi_1}}\right)\right],
\]
where $c>0$ is an absolute constant.
\end{theorem}
\begin{proof}
See 2.8.1 in Vershynin.
\end{proof}

Let us see what this says for random variables satisfying $\Vert X_i \Vert_{\psi_1} = 1$:
\[
\mathbb{P}\left\{\left\vert \sum_{i=1}^N X_i\right\vert \geq t\right\} \leq
	\begin{cases}
	\exp(-ct^2/N) & t<N \\
	\exp(-c t) & t\geq N.
	\end{cases}
\]
This says that, for sums of sub-exponential random variables, small deviations from the mean have sub-gaussian tails whereas large deviations have heavier sub-exponential tails.

\section{Concentration of the norm}
Given a random vector $X=(X_1,\dots, X_n)\in \mathbb{R}^n$, we may ask where its norm is likely to be located. This is answered by the following theorem:
\begin{theorem}[3.1.1 in V]
Let $X=(X_1,\dots, X_n)\in \mathbb{R}^n$ be a random vector with independent, sub-gaussian coordinates $X_i$ that satisfy $\mathbb{E}X_i^2=1$. Then
\[
\mathbb{P}\left(\Big\lvert \Vert X\Vert_2 - \sqrt{n}\Big\rvert  \geq t\right) \leq 2 \exp(-ct^2/K^4),
\]
where $K=\max_i\Vert X_i\Vert_{\psi_2}$.
\end{theorem}
\begin{proof}
%We first note that $\mathbb{E}\left[\Vert X\Vert_2^2\right]=\sum_{i=1}^n\mathbb{E}X_i^2=n$.

In the following, we assume $K\geq 1$ (this is justified below). We will apply Bernstein's inequality to $\frac{1}{n}\Vert X\Vert_2^2-1$ by first noting that this quantity is equivalent to $\frac{1}{n}\sum_{i=1}^n(X_i^2-1)$ and that this is indeed a sum of sub-exponential random variables:
\begin{align*}
\Vert X_i^2-1\Vert_{\psi_1} &\lesssim \Vert X_i^2\Vert_{\psi_1} \qquad \text{(by centering lemma)}\\
&= \Vert X_i \Vert^2_{\psi_2}\\
&\lesssim K^2.
\end{align*}
Apply Bernstein's inequality with $t=nu$:
\begin{align}
\mathbb{P}\left(\Big\lvert \frac{1}{n}\Vert X\Vert_2^2 - 1\Big\rvert \geq u \right) &\leq 2\exp\left(-c \min\left(\frac{n^2u^2}{nK^4},\frac{nu}{K^2}\right)\right) \nonumber \\
&\leq 2 \exp \left(\frac{-cn}{K^4}\min(u^2, u)\right) \quad (K\leq 1).\label{(3.1)}
\end{align}

This is a concentration inequality for $\Vert X\Vert_2^2$. To make the link towards a concentration inequality for $\Vert X \Vert_2$, observe (this is an exercise) that for $z\geq 0$:
\[
\vert z-1 \vert \geq \delta\quad \text{implies} \quad \vert z^2 - 1 \vert \geq \max(\delta, \delta^2).
\]

We obtain, for any $\delta \geq 0$, that
\begin{align*}
\mathbb{P}\left\{\bigg\vert \frac{1}{\sqrt{n}}\Vert X\Vert_2 - 1 \bigg\vert \geq \delta \right\} &\leq \mathbb{P}\left\{\bigg\vert \frac{1}{n}\Vert X \Vert_2^2 -1 \bigg\vert \geq \max(\delta,\delta^2)\right\}\\
& \leq 2 \exp \left(-\frac{cn}{K^4}\cdot \delta^2\right) \quad (\text{by (1) for }u=\max(\delta, \delta^2)).
\end{align*}

Changing variables to $t = \delta\sqrt{n}$, we obtain the desired concentration inequality
\[
\mathbb{P}\left(\Big\lvert \Vert X\Vert_2 - \sqrt{n}\Big\rvert  \geq t\right) \leq 2 \exp(-ct^2/K^4).
\]
\end{proof}

\textbf{Remark.}
Why may we assume $K\geq 1$? Note that $e^x\geq 1 + x$. Hence
\begin{align*}
2&\geq \mathbb{E}\left(\exp\left(\frac{\vert X_i\vert^2}{\Vert X_i\Vert_{\psi_2}^2}\right)\right)\\
&\geq \mathbb{E}\left(\frac{\vert X_i\vert^2}{\Vert X_i\Vert^2_{\psi_2}}\right) + 1
\end{align*}
Recalling that $\mathbb{E}X_i^2 =1$ and rearranging, we have
\[
\mathbb{E}\left(\frac{1}{\Vert X_i\Vert^2_{\psi_2}}\right)\leq 1.
\]
That is, $\Vert X_i \Vert_{\psi_2}$ is at least 1.



% \paragraph{Bibliography.}
% Please give real bibliographical citations for the papers that we
% mention in class. See below for how to include a bibliography section.
% If you use BibTeX, integrate the .bbl file into your .tex
% source. You should reference papers like this: ``The FKS
% dictionary originates in a paper by Fredman, Koml\'{o}s and
% Szemer\'{e}di \cite{fks}.'' In general, the name of the authors should
% appear in text at most once (for the first citation); further
% citations look like: ``Our proof follows that of \cite{fks}''.

% Take a look at previous lectures (TeX files are available) to see the
% details. A excellent source for bibliographical citations is
% DBLP. Just Google DBLP and an author's name.


%\bibliography{mybib}
\bibliographystyle{alpha}

\begin{thebibliography}{77}

\bibitem{vershynin}
Vershynin, Roman,
\emph{High-dimensional probability: An introduction with applications in data science}.
Vol. 47. Cambridge university press, 2018,

\end{thebibliography}

\end{document}
