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

% command to write Cramer with accent
\newcommand{\cram}{Cram\'{e}r}
\newcommand{\eucnorm}[1]{\lVert #1 \rVert}
\newcommand{\varp}[1]{\mathrm{var}_{{\tiny P}}(#1)}
\newcommand{\var}[1]{\mathrm{var}(#1)}
\newcommand{\expec}[1]{\mathbb{E}[#1]}
\newcommand{\est}{\hat{\theta}}

% command to write ~iid
\usepackage{mathtools}
\newcommand\iid{\stackrel{\mathclap{\tiny \mbox{iid}}}{\sim}}

\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}
\newtheorem{remark}[theorem]{Remark}

% 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{4 --- September 15, 2021}{Fall 2021}{Sebastien Roch, UW-Madison}{Ajinkya Kokandakar}

\section{Overview}

The previous lecture reviewed important concepts in classical probability theory, % including Markov's and Chebyshev's inequalities, $\mathcal{L}^p$ spaces and notions of convergence for random variables. The lecture also %
and introduced the loss function and the risk function that constitute the basic framework for the comparison of estimators. Intuitively, the idea behind the loss function is to measure how close the estimator is to the true (but unknown) value of the target \emph{parameter} by endowing the parameter space with a semi-metric. 

The main topic of this lecture is the \cram-Rao Bound, which is a lower bound for the variance of unbiased estimators for a target parameter.

\section{Basic Framework and Notation : A review}
We suppose that there is a abstract probability space $(\Omega, \mathcal{F})$ which is the source of all randomness. However, we are only concerned with \emph{samples} $X_1, X_2, \ldots, X_n$ that take values in the \emph{sample space} denoted $\mathcal{X}$.  In measure theoretic terms, a \emph{sample} $X$ is a random variable $X : (\Omega, \mathcal{F}) \rightarrow (\mathcal{X}, \mathcal{B})$. For our purposes, $\mathcal{X} \subseteq \mathbb{R}^p$. The samples are drawn from a fixed but unknown distribution on the sample space, and our goal is to estimate functions of this distribution. With this as our objective, we use the following framework for the discussion in this lecture: 
\begin{itemize}
\item {\em Family of distributions} -- There is a family of distributions $\mathcal{P}$ over the sample space, which contains the true distribution $P$, i.e. $P \in \mathcal{P}$.
%
\item {\em Parameter} -- We are interested in estimating a function of the distribution $\theta : \mathcal{P} \rightarrow \Theta$ where $\Theta$ is the \emph{parameter space}. In parametric families, we are typically interested in estimating a parameter of the distribution. For example, we might consider the family of normal distributions parameterized by mean $\mu$ and variance $\sigma^2$ and we are interested in making inferences about the mean $\mu$. Notice that $\mu = \mathbb{E}_{(\mu, \sigma^2)}(X) = \int_\mathbb{R} x \ dP_{(\mu, \sigma^2)}(x) = \mu(P_{(\mu, \sigma^2)})$, and is thus a function of the underlying (true) probability measure. 
\item {\em Data} -- The data consists of a sequence of $n$ i.i.d samples, $\{X_i\}_{i=1}^{n} \iid P \in \mathcal{P}$
\item {\em Estimator} -- An estimator $\hat{\theta}^{(n)} = \hat{\theta}^{(n)}(X_1, X_2, \ldots, X_n)$ is a function that maps the data to the parameter space i.e. $\hat{\theta}^{(n)} : \mathcal{X}^{n} \rightarrow \Theta$. An estimator is understood to be a function of the sample and hence we only write $\hat{\theta}^{(n)}$. Moreover, we often drop the superscript in the estimator $\est^{(n)}$ and simply use $\est$ instead. 
\end{itemize}

\begin{remark}
The expectation and variance of a random variable $Z$ are denoted as $\expec{Z}$ and $\var{Z}$. If we need to specify the distribution of the samples from $P$, we use $\mathbb{P}_P(\cdot), \mathbb{E}_P(\cdot)$ and $\mathrm{var}_P(\cdot)$ for the probability, expected value and variance under the distribution $P$ respectively.
\end{remark}


\subsection{Mean squared error and the Bias-Variance tradeoff}
Recall the definition of the bias of an estimator from the previous lecture: 
\begin{definition}
The bias of an estimator is defined as: 
$$
    \mathrm{bias}_{P}(\hat{\theta}, \theta) = \mathbb{E}_P [ \hat{\theta} - \theta(P) ]. %\ \ \text{for all } P \in \mathcal{P}.
$$
\end{definition}
When the distribution $P$ and parameter $\theta$ are obvious from the context, we write $\mathrm{bias}(\hat{\theta})$ for ease of notation. Positive bias indicates that the estimator provides an over-estimate the target parameter \emph{on average}. All else equal, we typically prefer to have zero bias, which motivates the following definition. 

\begin{definition}[Unbiasedness]
An estimator $\hat{\theta}$ is said to be unbiased if $\mathrm{bias}(\hat{\theta}, \theta) = 0$ for all $P \in \mathcal{P}$. 
\end{definition}
It is important to note that an unbiased estimator must have zero bias for \emph{all} possible distributions, for the following reason:  for any given estimator we can usually find \emph{some} distribution under which the estimator has zero bias. For example, for some $c \in \mathbb{R}$, the constant estimator $\est = c$ has zero bias for any $P$ with $\theta(P) = c$, but this is hardly a useful estimator for any $P$ that leads to a different value of $\theta$.

\begin{definition}[MSE, Panaretos \cite{pan} Def 3.3] 
The mean squared error (MSE) is defined as:
$$
    \mathrm{MSE}_P(\hat{\theta}) = \mathbb{E}[\lVert \hat{\theta} - \theta(P)\rVert^2]
$$
where $\lVert \cdot \rVert$ is the $L^2$ norm.
\end{definition}
For brevity we use $\mathrm{MSE}(\hat{\theta})$ when the distribution and the parameter are unambiguous. It is clear that the MSE satisfies the definition of a risk function given in the previous lecture. 

The following lemma expresses the the MSE of an estimator in terms of its bias and variance. 
\begin{lemma}[\cite{pan}, Lemma 3.4] Let $\hat{\theta} \in \mathbb{R}^p$ be an estimator for a $p$-dimensional parameter $\theta$, and $\hat{\theta}_k \in \mathbb{R}$ denote the $k$-th component of $\theta$, i.e. $\hat{\theta} = (\hat{\theta}_1, \hat{\theta}_2, \ldots , \hat{\theta}_p)^\top$, then the following always holds: 
$$
    \mathrm{MSE}(\hat{\theta}) = \eucnorm{\mathrm{bias}(\hat{\theta})}^2 + \sum_{k=1}^{p} \varp{\hat{\theta}_k}. 
$$
\end{lemma}
This result is called the \emph{bias-variance decomposition}. 
\begin{proof} 
We only prove the bias-variance decomposition for the case $p = 1$. By the definition of MSE, 
\begin{align*}
     \mathrm{MSE}(\hat{\theta}) 
        &=  \expec{(\est - \theta)^2} \\
        &=  \expec{(\est - \expec{\est} + \expec{\est} - \theta)^2} \\
        &= \expec{(\est - \expec{\est})^2} +\expec{(\expec{\est} - \theta)^2} 
                + 2 \expec{(\est - \expec{\est})(\expec{\est} - \theta)}  \\
        &= \var{\est} + \expec{\mathrm{bias}(\est)^2} + 2 (\expec{\est} - \theta)\underbrace{\expec{(\est - \expec{\est})}}_{ = 0} \\ 
        &= \mathrm{bias}(\est)^2 + \var{\est}
\end{align*}
which concludes the proof. 

\end{proof}

We define another impotant notion in classical statistics in the following definition. 
\begin{definition}[Consistency]
A sequence of estimators $\{\est^{(n)}\}$ is \textbf{consistent} if $\est^{(n)} \xrightarrow{i.p.} \theta$ as $n \rightarrow \infty$ for all $P \in \mathcal{P}$.
\end{definition}

\begin{lemma} For any $\varepsilon > 0$, 
$$
    \mathbb{P} (\eucnorm{\est - \theta} > \varepsilon) \leq  \frac{\mathrm{MSE(\est)}}{\varepsilon^2}
$$
\end{lemma}
\begin{proof}
Let $Z = \eucnorm{\est - \theta}^2$, then using Markov's inequality with $Z$ and $c = \varepsilon^2$ we get: 
$$
     \mathbb{P} (\eucnorm{\est - \theta} > \varepsilon) = \mathbb{P} (\eucnorm{\est - \theta}^2 > \varepsilon^2) \leq \frac{\expec{Z}}{\varepsilon^2}
$$
which is the required inequality.
\end{proof}
The following corollary is a direct consequence of the above lemma.

\begin{corollary}
A sequence of estimators $\est^{(n)}$ is consistent if $\mathrm{MSE}(\est^{(n)}) \rightarrow 0$ as $n \rightarrow \infty$.
\end{corollary}

We can reduce the mean squared error by either reducing the bias, the variance or both. It is easy to see that the mean squared error of an unbiased estimator is the variance itself. Therefore, when comparing among the class of unbiased estimators we only need to care about the variance of the estimators. This motivates the \cram-Rao bound in the next section. 


\section{\cram-Rao Bound}
The \cram-Rao bound is a lower bound for the variance of any unbiased estimators of a parameter of interest under certain regularity conditions. A lower bound is useful because it provides a benchmark to compare estimators against. If an estimator achieves the lower bound, it is optimal in the sense that no other unbiased estimator can have a lower variance. An estimator that achieves the lower bound is therefore ``efficient'' in the sense that it has the least possible variance. 

In this section we consider the special case of the \cram-Rao bound for random variables that can take only finitely many (real) values. For a more general result that applies to random variables in $\mathbb{R}^p$, see \emph{Theorem 6.6} in Lehmann and Casella \cite{lehmcass}.

For the theorem that follows consider the following setup:
\begin{itemize}
    \item The \emph{sample space} $\mathcal{X}$ is finite, i.e. $|\mathcal{X}| < \infty$. 
    \item The \emph{parameter space} $\Theta \subseteq \mathbb{R}$ is an open set in the real line
    \item The family of distribution consists of discrete distributions indexed by $\theta$ such that
    $$
        \mathcal{P} = \{ \ p( \ \cdot \ ; \theta) \ : \ \theta \in \Theta \ \}
    $$
    where $p(x, \theta) > 0$ and $p(x, \theta)$ is continuously differentiable in $\theta$ for all $x \in \mathcal{X}$.
\end{itemize}

Suppose we have a sample $\{X_i\}_{i=1}^{n} \iid p(\cdot ; \theta)$ as described above, then we have the following theorem: 

\begin{theorem}
If $\hat{\vartheta}^{(n)}, \ n \in \mathbb{N}$ is a sequence of unbiased estimators for $g(\theta)$ i.e. $\expec{\hat{\vartheta}^{(n)}} = g(\theta)$ for all $n \in \mathbb{N}$, where $g : \mathbb{R} \rightarrow \mathbb{R}$ is a continuously differentiable function, then: 
$$
    \var{\hat{\vartheta}^{(n)}} 
        \geq 
    \frac{[g'(\theta)]^2}{n \mathbb{E}\left[ \frac{\partial}{\partial \theta} \log p(X_1 ; \theta) \right]^2}
$$
where $\mathbb{E}\left[ \frac{\partial}{\partial \theta} \log p(X_1 ; \theta) \right]^2 =: I(\theta)$ is called the Fisher Information for $\theta$. 
\end{theorem} 

To understand the lower bound, note that:
$$
    I(\theta) := \mathbb{E} \left[ \frac{\partial}{\partial \theta} \log p(x ; \theta) \right] = \mathbb{E} \left[ \frac{\frac{\partial p(x ; \theta)}{\partial \theta}}{p(x ; \theta)} \right]
$$
Thus the Fisher information quantifies the expected relative rate of change of the likelihood in response to a small change in $\theta$. If this quantity is larger, it is easier to distinguish the likelihood functions that induce different values of  $\theta$, i.e. it is easier to distinguish between different value of $\theta$. It is in this sense, that $I(\theta)$ captures ``information'' about the parameter $\theta$, and therefore the name ``information'' matrix. The larger the information matrix, the easier it is to discern between different parameter values and the more information we have about the parameter. Notice that a larger Fisher information value corresponds to a lower \cram-Rao bound. A note of caution is due at this point: the \cram-Rao bound is \emph{not} a sharp lower bound, which means that there may not exist any unbiased estimator that achieves this lower bound. 


% \subsection{Using Boldface}f
% Make sure to use lots of boldface.
% 
% \paragraph{Question:}
% How would you use boldface?
% 
% \paragraph{Example:}
% This is an example showing how to use boldface to 
% help organize your lectures.
% 
% 
% \paragraph{Some Formatting.}
% Here is some formatting that you can use in your notes:
% \begin{itemize}
% \item {\em Item One} -- This is the first item.
% \item {\em Item Two} -- This is the second item.
% \item \dots and here are other items.
% \end{itemize}
% 
% If you need to number things, you can use this style:
% \begin{enumerate}
% \item {\em Item One} -- Again, this is the first item.
% \item {\em Item Two} -- Again, this is the second item.
% \item \dots and here are other items.
% \end{enumerate}
% 
% \paragraph{Bibliography.}
% 
% 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{pan}
Panaretos, V. M. (2016). \emph{Statistics for Mathematicians: A Rigorous First Course.} Birkhauser/Springer.

\bibitem{lehmcass}
Lehmann, E. L. and Casella, G. (1998). \emph{Theory of point estimation.} Springer.

%\bibitem{fks}
%M. Fredman, J. Koml\'{o}s, E. Szemer\'{e}di,
%\emph{Storing a Sparse Table with $O(1)$ Worst Case Access Time},
%Journal of the ACM, 31(3):538-544, 1984.

\end{thebibliography}

\end{document}
