\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{epsfig}
\usepackage[colorlinks,citecolor=blue,linkcolor=magenta,bookmarks=true]{hyperref}
\usepackage{color}
\newcommand{\eqdef}{\coloneqq}





\newcommand{\density}{\gamma}
\newcommand{\W}{ {\cal W} }
\newcommand{\wperp}{(\vec w^*)^{\perp_\vec w}}
\newcommand{\lp}{\left}
\newcommand{\rp}{\right}
\newcommand\norm[1]{\left\| #1 \right\|}
\newcommand\snorm[2]{\left\| #2 \right\|_{#1}}
\renewcommand\vec[1]{\mathbf{#1}}
\DeclareMathOperator*{\pr}{\mathbf{Pr}}
\DeclareMathOperator*{\E}{\mathbf{E}}
\newcommand{\proj}{\mathrm{proj}}
\newcommand{\me}{\mathrm{e}}
\newcommand{\mrm}{\mathrm}
\def\d{\mathrm{d}}
\newcommand{\normal}{\mathcal{N}}

\DeclareMathOperator*{\argmin}{argmin}
\DeclareMathOperator*{\argmax}{argmax}
\DeclareMathOperator*{\influ}{Inf}
\DeclareMathOperator*{\he}{He}



\newcommand{\sample}[2]{#1^{(#2)}}
\newcommand{\tr}{\mathrm{tr}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\bw}{\mathbf{w}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bp}{\mathbf{p}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\e}{\mathbf{e}}
\newcommand{\Sp}{\mathbb{S}}


\newcommand{\err}{\mathrm{err}}
\newcommand{\LTF}{\mathcal{H}}
\newcommand{\B}{\mathbb{B}}




\newcommand{\p}{\mathbf{P}}
\newcommand{\q}{\mathbf{Q}}
\newcommand{\h}{\mathbf{H}}
% \newcommand{\R}{\mathbb{R}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\s}{\mathbb{S}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\eps}{\epsilon}
\newcommand{\dtv}{d_{\mathrm TV}}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\polylog}{\mathrm{polylog}}
\newcommand{\var}{\mathbf{Var}}
\newcommand{\cov}{\mathbf{Cov}}


\newcommand{\sgn}{\mathrm{sign}}
\newcommand{\sign}{\mathrm{sign}}
\newcommand{\calN}{{\cal N}}
\newcommand{\calL}{{\cal L}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\Ex}{\mathop{{\bf E}\/}}
\newcommand{\opt}{\mathrm{opt}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\LR}{\mathrm{LeakyRelu}}
\newcommand{\Ind}{\mathds{1}}
\newcommand{\1}{\Ind}
\newcommand{\matr[1]}{\boldsymbol{#1}}
\newcommand{\littleint}{\mathop{\textstyle \int}}
\newcommand{\littlesum}{\mathop{\textstyle \sum}}
\newcommand{\littleprod}{\mathop{\textstyle \prod}}
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bi}{\mathbf{i}}
\newcommand{\bj}{\mathbf{j}}
\newcommand{\wt}{\widetilde}
\newcommand{\wh}{\widehat}


\newcommand{\ltwo}[1]{\left\lVert#1\right\rVert_2}
\newcommand{\dotp}[2]{ #1 \cdot #2 }
\newcommand{\miscl}{\err_{0-1}^{\D}}
\newcommand{\wstar}{\bw^{\ast}}
\newcommand{\x}{\vec x}
\DeclareMathOperator\erf{erf}
\newcommand{\normald}[1]{\mathcal{N}_{#1}}
\newcommand{\norms}[1]{\|#1\|_{\psi_2}}
\newcommand{\norme}[1]{\|#1\|_{\psi_1}}
\newcommand{\new}[1]{\textcolor{red}{#1}}

\newcommand{\ith}{^{(i)}}
\newcommand{\tth}{^{(t)}}
\newcommand{\Exx}{\E_{\x\sim \D_\x}}
\newcommand{\Ey}{\E_{(\x,y)\sim \D}}
\newcommand{\vpar}[2]{\vec #1^{\|_{\vec #2}}}
\newcommand{\vperp}[2]{\vec #1^{\perp{\vec #2}}}
\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{7 --- September 22, 2021}{Fall 2021}{Sebastien Roch, UW-Madison}{Nikos Zarifis}

\section{Last time}

In the last lecture we talked about the sub-Gaussian Random variables. Recall that a random variable $X$ is sub-Gaussian variable if its sub-Gaussian norm is bounded, i.e.,
\[\|X\|_{\psi_2}<\infty\;,\]
where
\[\|X\|_{\psi_2}=\inf\{t\geq 0:\E[\exp(X^2/t^2)]\leq 2\}\;.\]
If $\norms{X}\leq K$, there exists an absolute constant $C>0$ such that the following properties are equivalent (see \cite{ver}) 
\begin{enumerate}
    \item $\pr[|X|\geq t]\leq 2 \exp(-t^2/(CK^2))$ for all $t>0$. \label{property:1}
    \item $\|X\|_p\leq C K\sqrt{p}$ for all $p\geq 1$ (recall that $\|X\|_p=(\E[X^p])^{1/p}$).\label{property:2}
    \item If  $\E[X]=0$, $\E[\exp(\lambda X)]\leq \exp(C\lambda^2 K^2)$ for all $\lambda$.\label{property:3}
\end{enumerate}

Moreover, the triangle inequality holds w.r.t. the $\norms{\cdot}$, i.e.,
\[
\norms{X+Y}\leq \norms{X}+\norms{Y}\;.
\]
We denote that $a\lesssim b$ for $a\leq C b$, for some absolute constant $C>0$.

\section{Hoeffding's Inequality}
In this lecture we are going to see the Hoeffding's Inequality for sub-Gaussian random variables. First, we prove the following lemma:
\begin{lemma}[Centering lemma 2.6.8 in \cite{ver}] It holds that 
\[\norms{X-\E[X]}\lesssim \norms{X}\;.\]
    
\end{lemma}
\begin{proof}
    From triangle inequality, it holds that
    \[
    \norms{X-\E[X]}\leq \norms{X} + \norms{\E[X]} \lesssim 
    \norms{X}+ |\E[X]|\;,
    \]
    where we used that $\norms{\E[X]}\leq C|\E[X]|$, for some $C>0$, from the definition of the sub-Gaussian norm (for $t=\E[X]/\sqrt{\ln2}$).
    Then using Jensen's inequality we have that
    $|\E[X]|\leq \|X\|_1$ and from Property~\ref{property:2}, we have that 
    $\|X\|_1\leq C \norms{X}$, for some $C>0$. Therefore, we have that 
   \[
    \norms{X-\E[X]} \lesssim 
    \norms{X}+ |\E[X]|\lesssim \norms{X}\;.
    \]
\end{proof}

Next, we prove the General Hoeffding’s inequality.
\begin{theorem}[Thm 2.6.2 in \cite{ver}] Let $X_1,X_2,\ldots, X_N$ be independent mean zero, sub-Gaussian random variables. Then there exists an absolute constant $c>0$, so that for all $t\geq 0$, it holds
\[
\pr\left[\left|\sum_{i=1}^N X_i\right|\geq t\right]\leq 2\exp\left(-\frac{c t^2}{\sum_{i=1}^N \norms{X_i}^2}\right)\;.
\]
    
\end{theorem}
This is called General Hoeffding’s inequality and generalizes the Hoeffding’s inequality which assumes that the random variables have bounded variance $\sigma^2$.
\begin{proof}
    First, from triangle inequality it holds that
    \[\norms{\sum_{i=1}^N X_i}\leq \sum_{i=1}^N \norms{X_i}\leq \infty\;,\]
therefore $\sum_{i=1}^N X_i$ is a sub-Gaussian random variable.
     It suffices to show that the \[\norms{\sum_{i=1}^N X_i}^2\lesssim \sum_{i=1}^N \norms{X_i}^2\;.\]

    One could try the triangle inequality, but this would give that $\norms{\sum_{i=1}^N X_i}^2\leq (\sum_{i=1}^N \norms{X_i})^2\sim N\sum_{i=1}^N \norms{X_i}^2$ which is very loose, therefore we need to find a different way to prove this.

     To prove this, we need to use the independence of the random variables $X_i$.
     From the assumption that the random variables are mean zero, the sum is also from linearity, hence, using Property~\ref{property:3}, we have that for some absolute constant $C>0$ that
     \[
     \E[\exp(\lambda \sum_{i=1}^N X_i)]=\prod_{i=1}^N\E[\exp(\lambda X_i)]\leq \prod_{i=1}^N\exp(C\lambda \norms{X_i})=\exp(C\lambda \sum_{i=1}^N \norms{X_i}^2) \;,
     \]
    where we used the independence to split the expectation into a product. The proof follows by applying the Property~\ref{property:1}.
\end{proof}

\section{Sub-Exponential Random Variables}
To understand the norm of a vector with sub-Gaussian ($X$) coordinates, we need to understand the square of a sub-Gaussian ($X^2$).
Observe that
\[
\pr[X^2\geq t]=\pr[|X|\geq \sqrt{t}]\leq 2\exp(-\frac{C(\sqrt{t})^2}{K^2})=2\exp(-\frac{Ct}{K^2})\;,
\]
where we used the Property~\ref{property:1}. Observe that the decay is smaller than before, these random variables are called sub-exponential.

\begin{definition}
    We call a random variable $X$, sub-exponential if
\[\|X\|_{\psi_1}<\infty\;,\]
where
\[\|X\|_{\psi_1}=\inf\{t\geq 0:\E[\exp(\new{|X|}/t)]\leq 2\}\;.\]
\end{definition}

Similar with the sub-Gaussian random variables, we have some equivalence properties for sub-exponential random variables. We mark with \new{red} the main differences with sub-Gaussian random variables.
\begin{proposition}
If $\|X\|_{\psi_1}\leq K$, i.e., $X$ is sub-exponential then there exists an absolute constant $C>0$ such that the following properties are equivalent,
\begin{enumerate}
    \item $\pr[|X|\geq t]\leq 2 \exp(-\new{t/(CK)})$ for all $t>0$. \label{exp:1}
    \item $\|X\|_p\leq C K \new{p}$ for all $p\geq 1$.\label{exp:2}
    \item If  $\E[X]=0$, then $\E[\exp(\lambda X)]\leq \exp(C\lambda^2 K^2)$ for all \new{$|\lambda|\leq \frac{1}{C K}$}.\label{exp:3}
\end{enumerate}
\end{proposition}
We have that triangle inequality holds w.r.t. the $\norme{\cdot}$.
We have the Bernstein’s inequality.
\begin{theorem}[Thm 2.8.1. in \cite{ver}] Let $X_1,X_2,\ldots, X_N$ be independent mean zero, sub-exponential random variables. Then there exists an absolute constant $c>0$, so that for all $t\geq 0$, it holds
\[
\pr\left[\left|\sum_{i=1}^N X_i\right|\geq t\right]\leq 2\exp\left(-c\min(\frac{ t^2}{\sum_{i=1}^N \|X_i\|_{\psi_1}^2},\frac{ t}{\max_i \|X_i\|_{\psi_1}})\right)\;.
\]
    
\end{theorem}
\begin{proof}
    The proof is similar to the Hoeffding’s inequality. To prove this, we need to use the independence of the random variables $X_i$.
     We use Property~\ref{exp:3}, we have that
     \[
     \E[\exp(\lambda \sum_{i=1}^N X_i)]=\prod_{i=1}^N\E[\exp(\lambda X_i)]\leq \prod_{i=1}^N\exp(C\lambda \norme{X_i})=\exp(C\lambda \sum_{i=1}^N \norme{X_i}^2) \;,
     \]
     for all $\lambda \leq \frac{1}{C\max_i \norme{X_i}}$,
     where we used the independence to split the expectation into a product.
    Let $\sigma^2=\sum_{i=1}^N \norme{X_i}^2$. From Markov's inequality we have that
    \[
    \pr\left[\sum_{i=1}^N X_i\geq t\right]= \pr\left[\exp\left(\lambda\sum_{i=1}^N X_i\right)\geq \exp(\lambda t)\right]\leq \exp(-\lambda t) \E[\exp(\lambda \sum_{i=1}^N X_i)]\leq \exp(-\lambda t+ C\lambda^2\sigma^2)\;,
    \]
    then optimizing with respect of $\lambda$ we have that $\lambda=\min\left(\frac{t}{2C\sigma^2}, \frac{1}{C\max_i \norme{X_i}}\right)$ which gives the result, to complete the proof apply Markov's inequality in the $-\sum_{i=1}^N X_i$.
\end{proof}
There is another form of Bernstein’s inequality, when the random variables are bounded.

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