\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{epsfig}
\usepackage{stackengine}
\stackMath
\newcommand\tenq[2][1]{%
 \def\useanchorwidth{T}%
  \ifnum#1>1%
    \stackunder[0pt]{\tenq[\numexpr#1-1\relax]{#2}}{\scriptscriptstyle\sim}%
  \else%
    \stackunder[1pt]{#2}{\scriptscriptstyle\sim}%
  \fi%
}

\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{32 --- 19th November, 2021}{Fall 2021}{Sebastien Roch, UW-Madison}{Gokcan Tatli}

\section{Overview} \label{overview}

In the last lecture, we lower bounded the minimax risk $\mathfrak M$ using Proposition 15.12 from W \cite{Wainwright}. Then, we used the relation between mutual information and  Kullback Leibler divergence (15.34 in W \cite{Wainwright}), to find the following result:
\paragraph{Recall:}

If $(\tenq{\theta}^1),\ldots,\tenq{\theta}^M)$ are $2\delta$ separated under P, then

$$\mathfrak M \geq \phi (\delta)\left(1-\frac{\frac{1}{\mu^2}\sum \limits_{i\neq j}KL(P_{\tenq{\theta}^i}||P_{\tenq{\theta}^j})+1}{\log_2 M}\right)$$.


In this lecture, we continue to linear regression example and prove the lower bound for minimax MSE for that example. After that, we cover some basics of information theory.

\section{Example: Linear Regression (continued)}
\begin{itemize}
    \item[--] Suppose $\tenq{\mathbb{Y}}\sim N(\mathbb{X}\tenq{\theta}^*), \sigma^2I_n)$ when $(\tenq{\mathbb{Y}}, \mathbb{X})$ are observed and $\tenq{\theta}^*$ is unknown.

    \item[--] We want a lower bound on minimax MSE $(\mathbb{X}\tenq{\theta}^*))$, where
    $$\text{MSE}(\mathbb{X}\tenq{\theta}^*))=\frac{1}{n}||\mathbb{X}\tenq{\theta}^*)-\mathbb{X}\tenq{\hat{\theta}})||_2^2.$$ That is why we need following claims.
    \item{$\textbf{Claim 1.}$}
    If $\tenq{\gamma}^1,\ldots,\tenq{\gamma}^M\in range\mathbb{(X)}$ are such that $$||\tenq{\gamma}^i-\tenq{\gamma}^j||>2\delta \sqrt{n} \hspace{4mm} \forall i\neq j,$$ then $\exists \tenq{\theta}^1,\ldots,\tenq{\theta}^M$ such that 
    $$\rho(\tenq{\theta}^i, \tenq{\theta}^j)\frac{1}{\sqrt{n}}||\mathbb{X}\tenq{\theta}^i-\mathbb{X}\tenq{\theta}^j||_2>2\delta$$

    \item{$\textbf{Claim 2.}$}
    If $\tenq{\gamma}^1,\ldots,\tenq{\gamma}^M\in range\mathbb{(X)}$ are such that $$||\tenq{\gamma}^i||\leq 4\delta\sqrt{n} \hspace{4mm} \forall i,$$ then 
    $$KL(P_{\tenq{\theta}^i}||P_{\tenq{\theta}^j})\leq \frac{32n\delta^2}{\sigma^2}$$
\end{itemize}
\paragraph{\underline{Proof of Claim 2:}} We know that $P_{\tenq{\theta}^j}= N(\mathbb{X}\tenq{\theta}^j,\sigma^2I_n)$. That is why, 
\begin{eqnarray}
KL(P_{\tenq{\theta}^i}||P_{\tenq{\theta}^j})&=&\frac{1}{2\sigma^2}||\mathbb{X}\tenq{\theta}^i)-\mathbb{X}\tenq{\theta}^j)|| \hspace{4mm}(\text{by explicit calculation}) \\
&\leq& \frac{1}{2\sigma^2}\left [||\tenq{\gamma}^i||+||\tenq{\gamma}^j||\right]^2 \hspace{4mm}(\text{by triangle inequality})
\end{eqnarray}
Then, we use the norm bound, i.e., $4\delta\sqrt{n}$, in Claim 2 to get the desired KL-divergence bound $\frac{32n\delta^2}{\sigma^2}$.
\paragraph{Recall:}The largest cardinality of an $\epsilon-$separated set in a subset K of a metric space (T,d) is called the $\underline{\text{packing number of K}}$, i.e., $\mathcal{P(K, \epsilon)}$, which is a function of $\epsilon$.

We proved that $$\frac{vol(K)}{vol(\epsilon B_2^r)}\leq N(K, \epsilon)\leq \mathcal{P}(K, \epsilon),$$
where $N(K, \epsilon)$ is the covering number and $B_2^r$ is the unit norm-ball.

In our case (linear regression example), $K \subseteq \mathbb{R}^r$, rank($\mathbb{X}$)=r, $\epsilon=2\delta\sqrt{n}$, $K="4\delta\sqrt{n}B_2^r"$ (inside the range$\mathbb{(X)}$). Therefore, $$M\geq\left(\frac{4\delta\sqrt{n}}{2\delta\sqrt{n}}\right)^r=2^r \Rightarrow \log_2M\geq r$$

So, we can write
\begin{eqnarray}
\mathfrak M &\geq& \delta^2\left(1-\frac{\frac{32n\delta^2}{\sigma^2}+1}{r}\right) \label{11}\\
&\approx&\frac{\delta^2}{2} \label{22}
\end{eqnarray} 
where (\ref{11}) comes from combining above bound for r and the bound we got from Claim 2, and plugging them in the lower bound of minimax risk given in Section \ref{overview}. Then, we can write the lower bound in (\ref{22}) by taking $\delta^2=\frac{\sigma^2}{64}\frac{r}{n}$ when r is sufficiently large.

\section{Quick Tour of Information Theory}
- Note that in the interest of keeping things simple, we will do everything in discrete spaces

- Mostly from Chapter 2 of Cover-Thomas \cite{CovThm}

\paragraph{Definition 1.} If X$\in\mathcal{X}$ is a discrete random variable with pmf p(x), the entropy of X is $$H(X)=-\sum_{x\in\mathcal{X}}p(x)\log p(x),$$ with the convention that $0\log 0=0 \ \text{and}  \ 0\log \frac{0}{0}=0$.
\paragraph{Claim 2.} If $\mathcal{X}$ is finite, then $$H(X)\leq\log|\mathcal{X}|$$ with equality if and only if X is uniform over $\mathcal{X}$.

\paragraph{Proof:} Suppose U is uniform over $\mathcal{X}$, then
\begin{eqnarray}
H(U)&=&-\sum_{u\in\mathcal{X}}p(u)\log p(u) \\
&=&-\sum_{u\in\mathcal{X}}\frac{1}{|\mathcal{X}|}\log \frac{1}{|\mathcal{X}|} \\ 
&=&\log |\mathcal{X}|
\end{eqnarray}

On the other hand,
\begin{eqnarray}
0&\leq & KL(X||U) \\
&=&\sum_{x\in\mathcal{X}}p(x)\log \frac{p(x)}{1/|\mathcal{X}|} \\
&=&\log |\mathcal{X}|-(-\sum_{x\in\mathcal{X}}p(x)\log p(x)) \\
&=&\log |\mathcal{X}|-H(X)
\end{eqnarray}
which completes the proof.

\paragraph{Definition 3.} For a pair of random variables (X, Y), the conditional entropy of X$|$Y is $$H(X|Y)=-\sum_{x\in\mathcal{X}, y\in \mathcal{Y}}p(x,y)\log p(x,y),$$ where $p(x,y)$ can be also written as $p(y)p(x|y)$. This can be considered as expectation of conditional distribution x$|$y.



%\bibliography{mybib}
\bibliographystyle{alpha}

\begin{thebibliography}{77}

\bibitem{Wainwright}
Wainwright, Martin J.,
\emph{High-Dimensional Statistics: A Non-Asymptotic Viewpoint},
Cambridge Series in Statistical and Probabilistic Mathematics, 2019.

\bibitem{CovThm}
Cover, Thomas M.,
\emph{Elements of information theory},
John Wiley $\&$ Sons, 1999. 

\end{thebibliography}

\end{document}