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

\newtheorem{remark}{Remark}
\numberwithin{remark}{section} % counting in section, can also be changed by {subsection}

\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}{Yu Sun, Sebastien Roch}
	
	
		Recall from last time, under the hypothesis testing problem setting:
		\begin{itemize}
			\item $\underline{\theta}^1, \dots, \underline{\theta}^M $ are $2\delta$-separated under $\rho$ over the space $\Theta(\mathcal{P})$.
			\item Pick $J$ uniformly at random on $[M]$. Given $J = j$, pick $Z \sim \mathbb{P}_{\theta^j}$ where $\theta(\mathbb{P}_{\theta^j}) = \theta^j$.
			\item $\mathbb{Q}_{Z,J}$ is the joint distribution of $(Z,J)$.
		\end{itemize}
		Fano's method can be stated as (Proposition 15.12 and equation (15.34) in \cite{ref1}; we will give a proof in the next lectures)
		\begin{equation}
			\begin{aligned}
			\mathfrak M & \overset{\Delta}{=}	\mathfrak M (\theta(\mathcal P); \Phi \circ \rho) = 	 \inf_{\hat{\theta}} \sup_{\mathbb{P} \in \mathcal P} \mathbb{E}_{\mathbb{P}} [ \Phi(\rho(\hat{\theta}, \theta(\mathbb{P})]\\
			& \ge \Phi(\delta) \cdot \left\{ 1- \frac{\frac{1}{M^2} \sum\limits_{i\neq j}^M KL(\mathbb{P}_{\theta_i}\|\mathbb{P}_{\theta^j})+1}{\log_2M}\right\}.
			\end{aligned}
		\end{equation}
		Today we finish the linear regression example and show 
		that the least-squares estimate achieves the minimax
		risk (under the mean-squared error) up to constant.
	
	\section{Example: Linear Regression (15.14 in [1]): Continued}
	
	Recall the assumption: $\underline{Y}\sim \mathcal{N} (\mathbb{X}\underline{\theta}^*, \sigma^2 I_n)$, where $\underline{Y}$ and $\mathbb{X}$ are  observed, and $\underline{\theta}^*$ is unknown. We want a lower bound for minimax of MSE, i.e.
	
\begin{equation}
	\text{MSE}(\mathbb{X}\hat{\theta}) = \frac{1}{n} \lVert \mathbb{X}\underline{\theta}^* -\mathbb{X}\hat{\theta} \rVert_2^2,
\end{equation}
we have 2 claims as follow:

	\begin{itemize}
		\item \textbf{Claim 1.} (proved at the end of the last lecture): If $\underline{\gamma}^1, \dots, \underline{\gamma}^M \in range(\mathbb{X})$, s.t. 
		\begin{equation}
				\|\underline{\gamma}^i - \underline{\gamma}^j \|_2 > 2\delta \sqrt{n} \quad \forall i \ne j,
		\end{equation}
	then there $\exists \underline{\theta}^1, \dots, \underline{\theta}^M$, s.t.
	\begin{equation}
			\rho(\underline{\theta}^i, \underline{\theta}^j) \overset{\Delta}{=}\frac{1}{\sqrt{n}} \|\mathbb{X}\underline{\theta}^i - \mathbb{X}\underline{\theta}^j \|_2 > 2\delta \quad \forall i \ne j. 
	\end{equation}

		\item \textbf{Claim 2.} : If $\underline{\gamma}^1, \dots, \underline{\gamma}^M \in range(\mathbb{X})$, s.t. 
	\begin{equation}
		\|\underline{\gamma}^i \|_2 < 4\delta \sqrt{n} \quad \forall i, 
	\end{equation}
	then
	\begin{equation}
		KL(\mathbb{P}_{\underline{\theta}^i}\|\mathbb{P}_{\underline{\theta}^j}) \le 32 n \frac{\delta^2}{\sigma^2}.
	\end{equation}
	\end{itemize}

	\begin{proof} (\textbf{Claim 2.})\
		Since $\mathbb{P}_{\underline{\theta}} = \mathcal{N} (\mathbb{X}\underline{\theta}, \sigma^2 I_n)$,
		\begin{equation}
			\begin{aligned}
				KL(\mathbb{P}_{\underline{\theta}^i}\|\mathbb{P}_{\underline{\theta}^j}) &= \frac{1}{2\sigma^2}\|\mathbb{X}\underline{\theta}^i - \mathbb{X}\underline{\theta}^j \|_2^2\\
				&\le \frac{1}{2\sigma^2}\cdot \bigg(	\|\underline{\gamma}^i \|_2 +	\|\underline{\gamma}^j \|_2 	\bigg)^2(\text{triangular inequality of norm})\\
				&=32 n\frac{\delta^2}{\sigma^2}
			\end{aligned}
		\end{equation}
	\end{proof}
	
	Recall the \textit{packing number}: the largest cardinality of an $\epsilon$-separated set in a subset $K$ of a metric space$(\mathcal{T},d)$ is called the \textit{packing number} of $K$, i.e. $\mathcal{P}(K,\epsilon)$. We proved,
	\begin{equation}
		\frac{Vol(K)}{Vol(\epsilon B_2^r)}\le \mathcal{N}(K,\epsilon)\le  \mathcal{P}(K,\epsilon)
	\end{equation}
with $(\mathcal{T},d)$ as $\mathbb{R}^r$ with $l_2$-norm, and $B_2^r$ is the unit ball under Euclidian distance.

We adapt it into our linear regression problem, $K\subset \mathbb{R}^r$, with $r=rank(\mathbb{X})$, chose $\epsilon =2\delta \sqrt{n}$ and $K=4\delta \sqrt{n}B_2^r$ (technically, inside the range of $\mathbb{X}$), we have 
\begin{equation}
	M\ge \bigg(\frac{4\delta \sqrt{n}}{2\delta \sqrt{n}} \bigg)^r=2^r \iff  \log_2 M\ge r.
\end{equation}
Combine \textbf{Claim 2} and the result from Fano's method at the beginning, 

\begin{equation}
	\begin{aligned}
		\mathfrak M & \ge \delta^2 \bigg(1-\frac{\frac{32n\delta^2}{\sigma^2}+1}{r}\bigg)\qquad \left(\text{since all KL's are bounded by either 0 or }\frac{32n\delta^2}{\sigma^2}\right)\\
		&\approx \Omega(\delta^2)
	\end{aligned}
\end{equation}
by taking $\delta^2 =\frac{\sigma^2 r}{64n}$ (when $r$ is sufficiently large). 
	
	
	
\section{Quick Tour for Information Theory}	
\begin{remark}
	In the interest of keeping things simple, we will derive everything on discrete spaces.
\end{remark}

Most of contents are covered in Chapter 2 of \cite{ref2}. 
\begin{definition}
	If $X\in\mathcal{X}$ is a discrete r.v. with probability mass function $p(x)$, the textit{entropy} of $X$ is
	\begin{equation}
		H(X) =-\sum\limits_{x\in \mathcal{X}} p(x) \log p(x),
	\end{equation}
with the criteria that $0\log 0=0$, and $0 \log \frac{0}{0}=0$.
\end{definition}

\begin{claim}
	If $\mathcal{X}$ is finite, then
	\begin{equation}
		H(X)\le \log (|\mathcal{X}|)
	\end{equation}
with equality iff $X$ is uniform on $\mathcal{X}$.
\end{claim}
\begin{proof}\

\noindent$\Leftarrow$ Suppose $U$ is uniform on $\mathcal{X}$, then
\begin{equation}
	\begin{aligned}
		H(U)&=-\sum\limits_{u\in \mathcal{X}} p(u) \log p(u)\\
		&=\sum\limits_{u\in \mathcal{X}} \frac{1}{|\mathcal{X}|} \log |\mathcal{X}|\\
		&=\log |\mathcal{X}|
	\end{aligned}
\end{equation}

\noindent$\Rightarrow$ 
\begin{equation}
	\begin{aligned}
		0\le KL(X|U)&=\sum\limits_{u\in \mathcal{X}} p(x) \log \frac{p(x)}{1/|\mathcal{X}|}\\
		&=\sum\limits_{u\in \mathcal{X}} p(u) \log p(u)-\log |\mathcal{X}|\\
		&=-H(X)-\log |\mathcal{X}|\\
	\end{aligned}
\end{equation} 


\end{proof}



\begin{definition}
	For a pair of r.v.s $(X,Y)$, the \textit{conditional entropy} $X|Y$ is
	\begin{equation}
		H(X|Y)=-\sum\limits_{x\in \mathcal{X}, y\in \mathcal{Y}} p(x,y) \log p(x|y)\\
	\end{equation}
\end{definition}

\begin{remark}
	By using $p(x,y)=p(y)p(x|y)$, we know above conditional entropy is the entropy of $X$ given $y$, averaged over the distribution of $\mathcal{Y}$.
\end{remark}
	
	%\bibliography{mybib}
	\bibliographystyle{alpha}
	
	\begin{thebibliography}{99}
		
		\bibitem{ref1}
		Wainwright, Martin J.,
		\emph{High-Dimensional Statistics: A non-Asymptotic Viewpoint},
		Cambridge Series in Statistical and Probabilistic Mathematics, 2019
		
		\bibitem{ref2}
		Cover, Thomas M.,
		\emph{Elements of information theory},
		John Wiley $\&$ Sons, 1999. 
		
		
	\end{thebibliography}
	
\end{document}