\documentclass[landscape]{slides}
\usepackage[total={9in,7.5in},top=0.5in,left=1in]{geometry}
\usepackage[dvips]{color}
\usepackage{graphicx}
\usepackage{fancybox}
\usepackage{tweaklist}
\usepackage{amsmath,amsfonts}

\graphicspath{{Figures}}
\renewcommand{\itemhook}{\setlength{\topsep}{0pt}%
  \setlength{\itemsep}{3pt}}

\newcommand{\heading}[1]{\begin{center}\color[rgb]{0.2, 0.2, 0.2}
    \large\bf\shadowbox{#1}\end{center}\vspace{1ex minus 1ex}}
\newcommand{\subheading}[1]{\underline{\large\bf{#1}}\vspace{1ex minus 1ex}}
\newcommand{\mytitle}[1]{\pagestyle{empty}\begin{center}
    {\large \underline{STAT 526}\\ \vspace{.5in} \Large\bf{#1}}\\ \vspace{.75in}    Dr. Qifan Song \end{center}}


% Dabao: The slides for Chapter 3 should be rewritten to follow the materials in the textbook and also get the materials in a better order...

%--------------------------------------------------------------------

\begin{document}



\begin{slide}
\mytitle{Topic X\\Statistical Learning Thoery}
\end{slide}

%
%

\begin{note}

\begin{center}
\Large
{\bf Learning Theory}
\end{center}

\normalsize
Learning theory is a broad topic, which aims to explain general behavior of estimation and prediction accuary. I will go through some popular concepts and results

Distance/Divergence measure between two measures $P$ and $Q$
\begin{itemize}
\item Total variation distance $TV = \sup_A|P(A)-Q(A)|=\int |p-q|dx / 2 = \sup_{\|f\|_\infty\leq 1} E_P f-E_Q f$
\item KL divergence $KL(P,Q)= \int \log(p/q) p dx$
\item Hellinger distance $H=\sqrt{\int(\sqrt p-\sqrt q)^2dx}$
\item $f$ divergence $D_f(P,Q)=\int f(p/q) qdx$; KL is $f$ div with $f=x\log x$
\item $H^2/2\leq TV\leq H\leq \sqrt{KL}$.
\end{itemize}


\end{note}

\begin{note}

\begin{center}
\Large
{\bf Testing}
\end{center}

\normalsize
\begin{itemize}
\item $X\sim P_0$ (null distribution) or $P_1$ (alternative distribution), equivalently, $X\sim P_\theta$ with $\theta\in\{0,1\}$
\item A test/estimator $\phi(X)\rightarrow\{0,1\}$
\item We want to assess: Type I/II error probabilities $P_0(\phi(X)=1)$ and $P_1(\phi(X)=0)$, or estimation accuracy $P_{\theta}(\phi(X)\neq\theta)$. Especially, the lower bounds of these quantities
\item Suppose that $\theta$ follow a uniform prior over $\{0,1\}$, let $A = \phi^{-1}(1)$
\[
\begin{split}
&P(\phi(X)\neq \theta) = \pi(\theta=0)P_0(\phi(X)=1)+ \pi(\theta=1)P_1(\phi(X)=0)\\
&=[P_0(X\in A)+P_1(X\in A^c)]/2=[1+P_0(X\in A)-P_1(X\in A)]/2\\
&\geq [1-TV(P_0,P_1)]/2
\end{split}
\]

\end{itemize}


%https://www.stat.cmu.edu/~siva/teaching/709/lec15.pdf
%Assouad, Fano, and Le Cam Bin Yu
%https://www.stat.cmu.edu/~larry/=stat705/Lecture27.pdf
%https://www.stat.cmu.edu/~larry/=sml/minimax.pdf
%https://www.cs.columbia.edu/~djhsu/coms4773-s24/lectures/minimax.pdf
%https://www.cs.columbia.edu/~djhsu/coms4773-s24/lectures/minimax.pdf
%https://ocw.mit.edu/courses/18-s997-high-dimensional-statistics-spring-2015/501374d1714bfd55ff6345189b9c2e26_MIT18_S997S15_Chapter5.pdf
\end{note}

\begin{note}
\begin{center}
\Large
{\bf Mini-Max}
\end{center}

\normalsize
\begin{itemize}
\item More precisouly, $\inf_\phi P(\phi(X)\neq \theta)=[1-TV(P_0,P_1)]/2$
\item Back to frequentist setting, we can get
\[
\inf_\phi \sup_{\theta\in\{0,1\}}  P(\phi(X)\neq \theta)\geq [1-TV(P_0,P_1)]/2,
\]
where the inf is taken over all possible test (or selector)
\item The equality holds if using LRT
\item Our Goal: Best accuracy under worst scenario (minimax risk)
\[
R_n = \inf_{\hat\theta}\sup_{P\in\mathcal P}E_P[L(\hat\theta,\theta(P))],
\]
where $\mathcal = \{P_\theta,\theta\in\Theta\}$, and $\theta(P_\theta)=\theta$, $L$ is distance-based measure.
\item Statistical optimality
\item Gap: $\phi$ vs $\hat\theta$, $\{\theta_0,\theta_1\}$ vs $\Theta$, one sample vs a data set
\end{itemize}
\end{note}


\begin{note}
\begin{center}
\Large
{\bf Mini-Max Rate}
\end{center}

\normalsize
\begin{itemize}
\item General strategy to obtain minimax rate 
\item Find an upper bound by defining a ``good estimator'' $\tilde\theta$, then
$R_n\leq \sup_{P\in\mathcal P}E_P[L(\tilde\theta,\theta(P))]$
\item Find a lower bound as in Le Cam's method (a challenging task)
\item If upper and lower bounds match in order, mission accomplished.
\end{itemize}
\end{note}



\begin{note}
\begin{center}
\Large
{\bf Le Cam's method}
\end{center}

\normalsize
\begin{itemize}
\item $X_1,\dots,X_n\sim P_{\theta_1}$ or $\sim P_{\theta_2}$, for $\theta_1,\theta_2\in\Theta$
\item $P_{\theta_i}^n$ denote product distribution
\item Then
\[
\inf_{\phi} \sup_{\theta\in\{\theta_1,\theta_2\}} P(\phi(X_1,\dots,X_n)\neq\theta)\geq  \frac{1-TV(P_{\theta_1}^n,P_{\theta_2}^n)}{2},
\]
\item $TV(P_{\theta_1}^n,P_{\theta_2}^n)\leq \sqrt{KL(P_{\theta_1}^n,P_{\theta_2}^n)}=\sqrt{nKL(P_{\theta_1},P_{\theta_2})}$ for iid case
\item $TV(P_{\theta_1}^n,P_{\theta_2}^n)\leq H(P_{\theta_1}^n,P_{\theta_2}^n)$
\item[] with $H^2(P_{\theta_1}^n,P_{\theta_2}^n)=2(1-\int \prod_{i}^n p_{\theta_1}(x_i)p_{\theta_2}(x_i))$
$=2(1- (1-H^2(P_{\theta_1},P_{\theta_2})/2)^n)$
$\leq nH^2(P_{\theta_1},P_{\theta_2})$
\end{itemize}
\end{note}

\begin{note}

\begin{center}
\Large
{\bf Test function}
\end{center}

\normalsize
Upper bound on testibility\\
Asymptotic Methods in Statistical Decision Theory (Le Cam, 1986, Lemma 4 on page 478)

Given two convex sets $\mathcal P_0$ and  $\mathcal P_1$ of probability measures, there exist tests $\phi_n$, such that 
\[
\begin{split}
\sup_{P\in\mathcal P_0} E_P\phi_n(X_1,\dots,X_n)&\leq \exp(n\log \rho(\mathcal P_0,\mathcal P_1))\\
\sup_{P\in\mathcal P_1} E_P[1-\phi_n(X_1,\dots,X_n)]&\leq \exp(n\log \rho(\mathcal P_0,\mathcal P_1))\\
\end{split}
\]
where $\rho = 1 - h^2(\mathcal P_0,\mathcal P_1)/2$, and $H(\mathcal P_0,\mathcal P_1)$ is the Hellinger distance. Note that $\log \rho \leq -H^2/2$

This theorem leads to 
\[
\inf_{\hat\theta} \sup_{\theta\in\{\theta_1,\theta_2\}} P(\phi\neq\theta)\leq  \exp(-nH^2( P_0,P_1)/2),
\]
\end{note}

\begin{note}
\begin{center}
\Large
{\bf Le Cam's method}
\end{center}

\normalsize
\begin{itemize}
\item Let $\hat\theta$ be any estimator
\
\[
\begin{split}
&\inf_{\hat\theta} \sup_{\theta\in\{\theta_1,\theta_2\}} E\|\hat\theta-\theta\|^2\\
\geq&  \inf_{\hat\theta} \sup_{\theta\in\{\theta_1,\theta_2\}} [\|\theta_1-\theta_2\|^2/4] P(\|\hat\theta-\theta\|\geq \|\theta_1-\theta_2\|/2)
\end{split}
\]
\item For any $\hat\theta$, we can define a test $\phi = \arg\min_{\{\theta\in\theta_1,\theta_2\}}\|\hat\theta-\theta\|$
\item $\phi\neq \theta_j$ implies that $\|\hat\theta-\theta_j\|\geq \|\theta_1-\theta_2\|/2$, that is 
$P(\|\hat\theta-\theta_j\|\geq \|\theta_1-\theta_2\|/2)\geq P(\phi\neq \theta_j)$, thus
\[
\begin{split}
&\inf_{\hat\theta} \sup_{\theta\in\{\theta_1,\theta_2\}} E\|\hat\theta-\theta\|^2\\
\geq&  \inf_{\hat\theta} \sup_{\theta\in\{\theta_1,\theta_2\}} [\|\theta_1-\theta_2\|^2/4] P(\phi\neq \theta)\\
\geq&   [\|\theta_1-\theta_2\|^2/4] \frac{1-TV(P_{\theta_1}^n,P_{\theta_2}^n)}{2},
\end{split}
\]
\end{itemize}
\end{note}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{note}
\begin{center}
\Large
{\bf Apply Le Cam's method}
\end{center}

\normalsize
\begin{itemize}
\item For any two $\theta_1$ and $\theta_2\in\Theta$, then
\[
\inf_{\hat\theta} \sup_{\theta\in\Theta} E\|\hat\theta-\theta\|^2\geq
\inf_{\hat\theta} \sup_{\theta\in\{\theta_1,\theta_2\}} E\|\hat\theta-\theta\|^2\geq \|\theta_1-\theta_2\|^2 F(n,P_{\theta_1},P_{\theta_2}),
\]
where $F=\frac{1}{8}(1-\sqrt{nKL(P_{\theta_1},P_{\theta_2})})$ or $\frac{1}{8}(1-\sqrt{n}H(P_{\theta_1},P_{\theta_2}))$
\item
\[
\inf_{\hat\theta} \sup_{\theta\in\Theta} E\|\hat\theta-\theta\|^2\geq \max_{\theta_1,\theta_2}\|\theta_1-\theta_2\|^2 F(n,P_{\theta_1},P_{\theta_2}),
\]
\item Quadratic approximation (2-order Taylor) $KL(P_{\theta_1},P_{\theta_2}) \approx c \|\theta_1-\theta_2\|^2$ and $H^2(P_{\theta_1},P_{\theta_2}) \approx c \|\theta_1-\theta_2\|^2$ holds for most parametric families
\item 
\[
\inf_{\hat\theta} \sup_{\theta\in\Theta} E\|\hat\theta-\theta\|^2\geq \max_{\Delta\theta}(\Delta\theta)^2 (1-c\sqrt n\Delta\theta)/8\asymp \frac{1}{ n},
\]
\end{itemize}

\end{note}

\begin{note}
\Large
\begin{center}
{\bf Try some examples}
\end{center}

\normalsize
\begin{itemize}
\item[1.] Estimating the  mean of normal distribution
\item[]
\item[]
\item[2.] Estimating parameter of uniform distribution $U(\theta,\theta+1)$
\item[]
\item[]
\end{itemize}
Le Cam's results are usually independent to dimension of the parameter space. 
Assouad introduced a hyper-rectangle trick to resolve it.

\end{note}


\begin{note}
\begin{center}
\Large
{\bf Parallel 2-hypothesis Test}
\end{center}

\normalsize
\begin{itemize}
\item A family of $2^m$ hypothesis $P_v$, indexed by $v\in\{-1,+1\}^m$



\item We need to connect the index space and the parameter space
\item Given $\theta_1$, $\theta_2$, assume that $d(\theta_1,\theta_2)=\sum_j d_j(\theta_1,\theta_2)$ (e.g., $L^1$ loss)
\item For any $u,v$ differ only at $j$th entry, assume $d_j(\theta(P_u),\theta(P_v))\geq \delta$ for all $j$
\item Follow Le Cam's idea (assign a uniform prior over $v$)
\item 
\[
\begin{split}
&\sup_{\theta\in\Theta} E d(\hat\theta,\theta)=\sup_{\theta\in\Theta} \sum_jE d_j(\hat\theta,\theta(P_v))\geq
\sup_{P_v} \sum_jE d_j(\hat\theta,\theta)\\
\geq& E_{P_v, v\sim\rm{Unif}} \sum_jE d_j(\hat\theta,\theta(P_v))\geq\sum_j E_{v_{-j}\sim\rm{Unif}}[E_{v_{j}\sim\rm{Unif}}d_j(\hat\theta,\theta(P_v))]
\end{split}
\]


\end{itemize}
\end{note}




\begin{note}
\begin{center}
\Large
{\bf Parallel 2-hypothesis Test}
\end{center}

\normalsize
\begin{itemize}
\item Now we can directly apply Le Cam's result  
\[
\begin{split}
E_{v_{j}\sim\rm{Unif}}d_j(\hat\theta,\theta(P_v))\geq &\frac{\delta}{2}\frac{1-TV(P_{v_j=1,v_{-j}}||P_{v_j=-1,v{-j}})}{2}\\
\geq&  \frac{\delta}{2}\frac{1-\Delta_j}{2}
\end{split}\]
where $\Delta_j=\max_{\{u,v \text{ diffs only at jth entry}\}} TV(P_u||P_v)$
\item Then 
\[
\begin{split}
&\sup_{\theta\in\Theta} E d(\hat\theta,\theta)\geq\sum_j E_{v_{-j}\sim\rm{Unif}}\frac{\delta}{2}\frac{1-\Delta_j}{2}
\geq \frac{m\delta}{2}\frac{1-\Delta}{2}
\end{split}
\]
where $\Delta=\max\Delta_j=\max_{\{u,v \text{ diffs only by one entry}\}} TV(P_u||P_v)$
\item If $n$ samples, then 
\[
\Delta=\max_{\{u,v \text{ diffs only by one entry}\}} TV(P_u^n||P_v^n)
\]
which is further bounded by $\sqrt{nKL}$ or $\sqrt n H$
\end{itemize}
\end{note}

\begin{note}
\begin{center}
\Large
{\bf Assouad's Method for non-metric or non-decomposable $\tilde d(\cdot,\cdot)$}
\end{center}

\normalsize
\begin{itemize}
\item related $\tilde d$ with another decomposable metric $d$: ($L_2$ norm $\geq$ $(1/\sqrt{d})$ $L_1$ norm)
\item $\tilde d \geq C\sum_j d_j$ where $d_j$ is a metric
\item $\tilde d = \sum_j \tilde d_j$ where $\tilde d_j$ is not a metric, but satisfies 
if $d_j(\theta_0,\theta_1)<d_j(theta_0,\theta_2)$, then $d_j(theta_0,\theta_2)\geq Cd_j(\theta_1,\theta_2)$
\item[] Under weak triangle inequality, $d_j(\theta_0,\theta_2)\geq [d_j(\theta_0,\theta_2)+d_j(\theta_0,\theta_1)]/2\geq Cd_j(\theta_1,\theta_2)/2$
\end{itemize}
\end{note}

\begin{note}
\begin{center}
\Large
{\bf Apply Assouad's method}
\end{center}

\normalsize
\begin{itemize}
\item $\Theta =\mathbb R^d$
\item Routine choice of $P_v$: $P_\theta$ with $\theta_i$'s $=(\pm \delta,\pm \delta, \dots,\pm\delta)=\delta*v$
\item By continuity of KL, $KL(P_{u}||P_{v}), H^2(P_{u}||P_{v})\approx c\delta^2$ for $u$ and $v$ differing by one entry.
\item 
\[
\inf_{\hat\theta}\sup_{\theta\in\Theta} E\|\hat\theta-\theta\|_1\geq m\delta\frac{1-\sqrt{cn}\delta}{2}\]
\item Maximizing RHS w.r.t. $\delta$ leads to an order of $d/\sqrt n$
\item We can also derive lower bounds for $L_2$ and $L_2^2$ ($\sqrt{d/n}$ and $d/n$) respectively
\end{itemize}

\end{note}

%\begin{note}
%\begin{center}
%\Large
%{\bf Parallel 2-hypothsis Test}
%\end{center}

%\normalsize
%\begin{itemize}
%\item Let $\phi$ be a test on $v_j=-1$ vs $v_j=+1$, by LeCam's method
%\[
%\begin{split}
%& \inf_{\phi} E_{v\sim \rm{Unif}} P(\phi(X)\neq v_j)\geq[1-TV(P_{v_j=1}||P_{v_j=-1})]/2
%\end{split}
%\]
%where $P_{v_j=1}$ is the mixture distribution of $P_v$ with $v_j=1$. So the problem reduces to 
%testing between $P_{v_j=1}$ and $P_{v_j=-1}$


%\item Lemma to handle $TV(P_{v_j=1}||P_{v_j=-1})$:\[
%\begin{split}
%&TV((P_1+P_2)/2||(P_3+P_4)/2) = (1/2)\int |p_1+p_2-p_3-p_4|/2 dx\\
%\leq& (1/4)(\int |p_1-p_3|dx+ \int |p_2-p_4|dx)=\frac{TV(P_1||P_3)+TV(P_2||P_4)}{2}
%\end{split}
%\]
%\item $TV(P_{v_j=1}||P_{v_j=-1})\leq \max_{\{u,v \text{ diffs only at jth entry}\}} TV(P_u||P_v)$
%\end{itemize}
%\end{note}

%\begin{note}
%\begin{center}
%\Large
%{\bf Parallel 2-hypothsis Test}
%\end{center}

%\normalsize
%\begin{itemize}
%\item Note that $\sum_{v_j=\pm 1}E_{v_{-j}\sim\rm{Unif}}d_j(\hat\theta,\theta(P_v))\geq \delta$.
%\item $E_{v_{-j}\sim\rm{Unif}}d_j(\hat\theta,\theta(P_v))$ can be used as a test for $v_j=-1$ vs $v_j=+1$, then
%\[\begin{split}
%&E_{v_{j}\sim\rm{Unif}}[E_{v_{-j}\sim\rm{Unif}}d_j(\hat\theta,\theta(P_v))]\\
%\geq& E_{v_{j}\sim\rm{Unif}}\frac{\delta}{2}P[E_{v_{-j}\sim\rm{Unif}}d_j(\hat\theta,\theta(P_v))\geq \delta/2]\\
%\geq& E_{v_{j}\sim\rm{Unif}}\frac{\delta}{2}P[\phi \neq v_j]
%\end{split}
%\]
%where $\phi_j\in\{-1,+1\}$ is determined by $d_j$ 

%\end{itemize}
%\end{note}


\begin{note}
\Large
\begin{center}
{\bf Multiple testing problem}
\end{center}
\normalsize
\begin{itemize}
\item $X$ is a discrete r.v. whose sample space is of size $M\geq 2$, $Y$ is another r.v.
\item $\tilde X = f(Y)$ for some function $f$, $E=1(\tilde X \neq X)$, i.e., using $Y$ to test $X$
\item $H(X|Y)=-\sum_{ij}P(x_i,y_i)\log P(x_i|y_j)$ denotes the conditional entropy, $H(X)=-\sum_i P(x_i)\log P(x_i)$ denotes the entropy.
\item By definition $H(E,X|\tilde X)=H(X|\tilde X)+H(E|X,\tilde X)=H(E|\tilde X)+H(X|E,\tilde X)$, which implies
$H(X|\tilde X)=H(E|\tilde X)+H(X|E,\tilde X)$
\item By definition $H(X|E,\tilde X)=H(X|E=0,\tilde X)P(E=0)+H(X|E=1,\tilde X)P(E=1)=H(X|E=1,\tilde X)P(E=1)$ 
\item[]
\end{itemize}
\end{note}

\begin{note}
\Large
\begin{center}
{\bf Fano's Lemma}
\end{center}

\normalsize
\begin{itemize}
\item $H(X|E=1,\tilde X)\leq \log (M-1)$ (a r.v. with $a$ possible values has max entropy $\log a$)
\item $H(E|\tilde X)\leq H(E)$ (HW: conditional entropy always is smaller than entropy)
\item $H(X|Y)\leq H(X|\tilde X)$ ($H(X|Y)=H(X,Y)-H(X)$, $H(X,\tilde X)=H(X,\tilde X)-H(X)$)
\item \[ H(X|Y)\leq H(E)+P(E=1)\log(M-1)\]
\end{itemize}

\end{note}

\begin{note}
\Large
\begin{center}
{\bf Fano's Method}
\end{center}

\normalsize
\begin{itemize}
\item $\theta$ has a uniform prior over $\{\theta_1,\dots,\theta_M\}$
\item By Fano's Lemma, for any estimator $\phi(X)$, let $E=1(\phi(X)\neq \theta)$
   \[\begin{split}
   H(\theta|X)&\leq H(E)+P(E=1)\log(M-1); H(E)\leq\log 2\\
   P(E=1)&\geq \frac{H(\theta|X)-\log 2}{\log(M-1)}
   \end{split}\]
   \item Using similar argument in Le Cam's method
  \[ \inf_{\hat\theta}\sup_{\theta\in\{\theta_1,\dots,\theta_M\}}E \|\hat\theta-\theta\|^2\geq
   \frac{\min_{\theta_i,\theta_j}\|\theta_i-\theta_j\|^2}{4}P(E=1)\]
\end{itemize}


\end{note}

\begin{note}
\Large
\begin{center}
{\bf Handle $H(\theta|X)$}
\end{center}

\normalsize
\begin{itemize}
\item
   \[\begin{split}
   &H(\theta|X)=E-\log\frac{P(\theta,X)}{P(X)P(\theta)}-E\log P(\theta)\\
   =&-KL(P(\theta,X)||P(\theta)P(Y))+\log M\\
   =&-\frac{1}{M}\sum_i KL(P_{\theta_i}||\bar P)+\log M
   \end{split}\]
   where $\bar P =\sum P_{\theta_i}/M$
\item By convexity of KL
  \[ \begin{split}
  &H(\theta|X)=-\frac{1}{M}\sum_i KL(P_{\theta_i}||\bar P)+\log M\\
  \geq &-\frac{1}{M^2}\sum_{i,j} KL(P_{\theta_i}||P_{\theta_j})+\log M
   \end{split}\]

   \item Finally
   \[\begin{split}
    &\inf_{\hat\theta}\sup_{\theta\in\{\theta_1,\dots,\theta_M\}} E\|\hat\theta-\theta\|^2\\
    \geq&
    \frac{\min_{\theta_i,\theta_j}\|\theta_i-\theta_j\|^2}{4}\frac{\log M-\log 2-\frac{1}{M^2}\sum_{i,j} KL(P_{\theta_i}||P_{\theta_j})}{\log(M-1)}\\
    \geq&
     \frac{\min_{\theta_i,\theta_j}\|\theta_i-\theta_j\|^2}{4}\left(1-\frac{\log 2+\frac{1}{M^2}\sum_{i,j} KL(P_{\theta_i}||P_{\theta_j})}{\log (M-1)}\right)
  \end{split}\]
  \item If we observe $n$ data point $X_1,\dots, X_n$
   \[\begin{split}
    &\inf_{\hat\theta}\sup_{\theta\in\{\theta_1,\dots,\theta_M\}} E\|\hat\theta-\theta\|^2\\
    \geq&
   \frac{\min_{\theta_i,\theta_j}\|\theta_i-\theta_j\|^2}{4}\left(1-\frac{\log 2+\frac{1}{M^2}\sum_{i,j}n KL(P_{\theta_i}||P_{\theta_j})}{\log (M-1)}\right)
  \end{split}\]
\end{itemize}



\end{note}


\begin{note}
\Large
\begin{center}
{\bf Apply Fano's method}
\end{center}


\normalsize
\begin{itemize}
\item Find multiple $\theta_i$'s $\in\Theta$
\item $\|\theta_i-\theta_j\|\geq 2\delta$, while $KL(P_{\theta_i}||P_{\theta_j})\leq \epsilon$ for all $i,j$
\item Then $\inf_{\hat\theta}\sup_{\theta\in\Theta} E\|\hat\theta-\theta\|^2\geq \delta^2\left(1-\frac{\log 2+n\epsilon}{\log (M-1)}\right)$
\item To obtain a sharper bound (i.e., larger bound), we need a big $M$ (the concept of packing number)
\item Fano vs Le Cam vs Assouad: Le Cam's method reduces $\Theta$ to one-dim case, thus the derived rate is usually dimension-indep. 
Assouad's method usually applies to that case where $\Theta\subset \mathbb{R}^d$ with $dim(\Theta)=d$. 
Fano's method may improve, and applies to nonreqular shaped $\Theta$. 
\end{itemize}


\end{note}

\begin{note}
\begin{center}
\Large
{\bf Apply Fano's method}
\end{center}

\normalsize
\begin{itemize}
\item Routine choice of $\theta_i$'s $=(\pm \delta,\pm \delta, \dots,\pm\delta)$, totally $M=2^d$
\item Unfortunately, it fails to obtain a good dim-dependent bound: $KL(P_{\theta_i}||P_{\theta_j})\leq cd\delta^2$
\item []
\item Instead, find $M$ $\theta_i$'s within $B(0,\epsilon)$, such that pairwise distance is greater than $\epsilon/3$.
\item Then $KL(P_{\theta_i}||P_{\theta_j})\leq c\epsilon^2$, $\|\theta_j-\theta_i\|\geq \epsilon/3$
\[
\inf_{\hat\theta}\sup_{\theta\in\Theta} E\|\hat\theta-\theta\|^2\geq \frac{\epsilon^2}{36}\left(1-\frac{\log 2+nc\epsilon^2}{\log (M-1)}\right)\]
\item Maximizing RHS w.r.t. $\delta$ leads to an order of $\log M/n$
\item How large can $M$ be?
\end{itemize}

\end{note}

\begin{note}
\begin{center}
\Large
{\bf Packing Number and Covering Number}
\end{center}

\normalsize
\begin{itemize}
\item $\epsilon$-covering: a set of $\theta_i$'s such that for any $\theta\in\Theta$, there exists $j$, such that $\|\theta-\theta_j\|\leq\epsilon$
\item $\epsilon$-packing: a set of $\theta_i$'s such that for $\|\theta_i-\theta_j\|>\epsilon$
\item []
\item Maximal $\epsilon$-packing is a $\epsilon$-covering, hence its size is greater than or equal to the minimal $\epsilon$-covering size.
\item Size of maximal  $2\epsilon$-packing is smaller than or equal to the minimal $\epsilon$-covering size. (if not, centers of two packing balls must be inside one covering ball)

\item The minimal $\epsilon$-covering size $\geq$ volume of $\Theta$ divided by volume of $\epsilon$-radius ball
\item Back to our question: the largest possible $M\geq $ volume of $B(0,\epsilon)$ divided by volume of $\epsilon/3$-radius ball. Thus $\log M$ at least of $O(d)$
\end{itemize}

\end{note}

\begin{note}
\begin{center}
\Large
{\bf Apply Fano's method}
\end{center}

\normalsize
\begin{itemize}
\item Let us try one example $X\sim\rm{N}(\theta, \sigma^2I)$, where $\theta\in\mathbb{R}^n$
and $\|\theta\|_0\leq s$, i.e., sparse mean regression
\item We need to find as many $\theta_i$'s as possible inside $\Theta=\{\|\theta\|_2\leq \epsilon, \|\theta\|_2\leq s\}$ with
$\|\theta_i-\theta_j\|\geq \delta$ for some $\epsilon$ and $\delta$
\item Let all these $\theta_i$'s be of sparsity $2s/3$, all of its nonzero entry be $\pm a$.For every pair of $\theta_i$ and $\theta_j$, they share at most $s/3$ nonzero entry index
\item Then for all $\|\theta_i-\theta_j\|\leq 2\sqrt{2s/3}a$, $KL(P_{\theta_i}||P_{\theta_j})\leq 4sa^2/3$
\item Then for all $\|\theta_i-\theta_j\|\geq \sqrt{2s/3}a$
\item $L^2_2$ rate low bound reduce to $\log M$
\end{itemize}

\end{note}

\begin{note}
\begin{center}
\Large
{\bf Apply Fano's method}
\end{center}

\normalsize
\begin{itemize}
\item The problem reduces to a combinatorial problem for  $n$-dim binary vectors.
\item There are totally $n\choose k$ $k$-sparse $n$-dim binary vector (here $k=2s/3$)
\item For every $k$-sparse vector, there are  ${k\choose k/2} {n-k \choose k/2} + \dots +{k\choose k} {n-k \choose 0}$ $k$-sparse vectors that shares more than $d/2$ nonzero entry index
\item So at least $M \geq {n\choose k} /({k\choose k/2} {n-k \choose k/2} + \dots +{k\choose k} {n-k \choose 0}) $
\item ${k\choose k/2} {n-k \choose k/2} + \dots +{k\choose k} {n-k \choose 0}\leq 2^k{n \choose k/2}$
\item $\log M \geq \log {n\choose k} -k\log 2 - \log {n\choose k/2}$
\item When $n/k$ is sufficient large, by Sterling approximation $(n!\sim n^{n+0.5}e^{-n})$, we have $\log M $ at least of order $k\log (n/k)\asymp s\log(n/s)$
\end{itemize}

\end{note}

\begin{note}
\begin{center}
\Large
{\bf Minimax Rate of Density estimation}
\end{center}

\normalsize
\begin{itemize}
\item $\Theta=\{\mbox{pdf } f \mbox{ on }[0,1] \}$.
\item $x_j=(j-(1/2))/m$, $j=1,\dots,m$, $g_j(x)=c\sin(m(x-x_j))/m^2$ for a fixed small $c$
\item Define $f_{v}=1+\sum_{j=1}^m v_jg_j$ with $v\in\{-1,+1\}^m$
\item $d_j$ satisfies weak triangle inequality
\item Assouad's method and Fano method both apply; then we take maximum over $m$
\[\inf\sup H^2(\hat f,f)\geq n^{-4/5}\]
\end{itemize}

\end{note}

\end{document}
