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

\begin{document}

\lecture{31 --- 17th November, 2021}{Fall 2021}{Sebastien Roch, UW-Madison}{Nicholas Chelales}

\section{Overview}

Recall in the previous lectures where we defined the minimax risk:

\begin{align}
 \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})] 
\end{align}
We showed the special case where $M =2$ where the minimax risk can be bounded as 
\begin{align}
\mathfrak M \geq \Phi(\delta) * \frac{1}{2} \{ 1 - ||\mathbb{P}_{\theta^1} - \mathbb{P}_{\theta}^2||_{TV})
\end{align}
In this lecture we will examine the case where $M > 2$ and develop and information theory based approach to bounding the mini-max risk using Fano's method. The proof of this method will be discussed in the upcoming lecture, with examples and results being shown today. 


\section{Mutual Information and the Minimax Risk}

The mutual information between two variables is an information theory technique which helps numerically describe the relationship between two random variables. If one were to observe variable A, the mutual information would describe the amount of information gained regarding variable B with this single observation of variable A. The higher the mutual information, the more knowledge one gains regarding the non-observed variable by observing a particular variable. It follows that zero mutual information indicates independent random variables. 

\subsection{Mutual Information and KL Divergence}

The mutual information can be described in terms of the Kullback Leibler divergence:

\begin{align}
I(Z,J) = KL(\mathbb{Q}_{Z,J} || \mathbb{Q}_{Z} \mathbb{Q}_J )
\end{align}

where $\mathbb{Q_{Z,J}}$ represent the joint distribution and $\mathbb{Q}_Z$ and $\mathbb{Q}_J$ represent the marginal distributions respectively.

\begin{theorem}{Proposition 15.12 in W \cite{Wainwright}}
\begin{align}
\mathfrak M \geq \Phi(\delta)[1 - \frac{I(Z,J) + 1}{log_2(M)}] \label{eq1}
\end{align}
\end{theorem}
It follows that the lower the mutual information (i.e. less information J reveals about Z, the larger $ [1 - \frac{I(Z,J) + 1}{log_2(M)}] $ becomes, thus increasing the lower bound for the minimax risk. \\

\begin{lemma}{15.34 in W \cite{Wainwright}}
\begin{align}
    I(Z;J) \leq \frac{1}{M^2} \sum_{i,j}^M KL(\mathbb{P}_{\theta^i} || \mathbb{P}_{\theta^j}) 
\end{align}
\end{lemma}

The above lemma is useful to reduce the problem to two different distributions, which can be plugged into equation \ref{eq1} to get a more descriptive bound. The proof of this theorem and lemma will be discussed in the next lecture.

\section{Linear Regression Example} 

Recall the linear regression problem, where we have an unknown parameter $\mathbb{\theta}^* \in \mathbb{R}^P$ of which we wish to estimate. We are given $n$ observations of $y_i = f(\underline{x}_i) + \epsilon_i$ where $\epsilon$ is some form of noise, and $f$ represents the true function, i.e. $f(\underline{x}) = {\theta^*}^{T} \underline{x}$

The Mean squared error (MSE) is defined as:

\begin{align}
    MSE(\hat{f_n}) = \frac{1}{n} \sum_{i=1}^n(\hat{f_n}(\underline{x}_i) - f(\underline{x}_i))^2
\end{align}

this can be simplified in terms of the matrix form of $\underline{x}$

where the rows of $ \mathbb{X} $ contain $\underline{x_i}$

\begin{align}
    MSE(\hat{f_n}) = \frac{1}{n} || \mathbb{X} \hat{\underline{\theta}} - \mathbb{X}\underline{\theta}^*||^2
\end{align}

and


\begin{align}
    \hat{\theta}^{LS} \in argMin_{\underline{\hat{\theta}}} || \underline{y} - \mathbb{X}\underline{\theta}||^2
\end{align}

where $\underline{y} = (y_1,....y_n)$.

Recall we previously showed w.p. $1- \delta$

\begin{align}
    MSE(\mathbb{X}{\hat{\theta}^{LS}})\leq \frac{\sigma^2}{n}(rank(\mathbb{X}) + log(1/\delta))
\end{align}

when $\epsilon$ has sub-guassian norm $||\underline{\epsilon}||_{\psi_2} \leq \sigma$


Suppose our $\epsilon_i$ are generated from a normal distribution $ N(\underline{0}, \sigma^2 I_n)$

We wish to find as many possible $\theta^1... \theta^m$ such that:

\begin{align}
    \frac{1}{\sqrt{n}} ||\mathbb{X}\underline{\theta}^i - \mathbb{X}\underline{\theta}^j ||_2 > 2\delta \  \forall i \neq j
\end{align}

We wish to find the largest M number of $\theta$ since earlier we showed that the upper bound on the mutual information $I(Z;J)$ is inversely proportional to M (see Lemma 2). Thus the larger M is, the tighter upper bound we can get on the mutual information. since X is fixed, the above expression is really a combination of the columns of X, and thus we can obtain the list of $\theta$'s by finding all vectors $\gamma^i$ in \textbf{the range of $\mathbb{X}$} that fit the criteria:

\begin{align}
    ||\underline{\gamma}^i - \underline{\gamma}^j||_2 \geq 2 \delta \sqrt{n} \ \forall i \neq j
\end{align}

then there must exist a set of $\theta^i$ such that:

\begin{align}
    \underline{\gamma}^i = \mathbb{X}{\underline{\theta}^i}
\end{align}

Note that all possible $\gamma$ values lie within the range of $\mathbb{X}$, and we wish the find the maximum possible set which fit the $\delta$ criteria as described above. 

what remains is a probability distribution of the form:

\begin{align}
    \mathbb{P}_{\theta^j} = N(\mathbb{X}\underline{\theta}^j, \sigma^2 I_n)
\end{align}

of which we wish to bound the KL divergence:

\begin{align}
    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 
\end{align}

to be continued in more detail the next lecture. 

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


\end{thebibliography}

\end{document}