\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{35 --- Nov 29, 2021}{Fall 2021}{Sebastien Roch, UW-Madison}{Susan Glenn, Sebastien Roch}

\section{Overview}

In the last lecture we focused on a constrained version of
the least square estimator that is particularly applicable in the sparse setting.

In this lecture we continue with the proof of Theorem 2.6 in \cite{fks} which controls the MSE of $\hat \theta^{LS}_{K}$ when $K = \mathcal{B}_{0}(k)$


\section{Sparse linear regression: Known $k$}

We begin by describing the problem of sparse linear regression from last time.

\subsection{Reminder}

Recall from last time: 
\begin{itemize}
    \item Sparsity is defined as $\text{supp}(\pmb{\theta}) = \{j: \pmb{\theta}_j \neq 0 \}$
    $$\|\pmb{\theta}\|_0 = |\text{supp}(\pmb{\theta})| $$
    $$\mathcal{B}_0 (k) = \{\pmb{\theta} \in \mathcal{R}^p : \|\pmb{\theta} \|_0 \leq k \} $$
    \item $(\mathbb{X}, Y) \in \mathbb{R}^{n \times p} \times \mathbb{R}^{n}$ 
    $$\pmb{\hat \theta} := \text{ argmin} \{ \|Y - \mathbb{X} \pmb{\theta} \|^2 : \pmb{\theta} \in \mathcal{B}_0 (k) \}$$
\end{itemize}



\begin{theorem}[Thm 2.6 in \cite{fks}]\label{thm:1} 
Assume $2k \leq p$ and $\pmb{\theta}^* \in \mathcal{B}_{0}(k)$ and $\|\pmb{\varepsilon}\|_{\psi_2} \leq \sigma$ w.p. $1-\delta$
$$\frac{1}{n} \|\mathbb{X} \pmb{\hat \theta} - \mathbb{X} \pmb{\theta^*}\| \lesssim \frac{\sigma^2}{n} \left\{k \log \left(\frac{p}{k} \right) + \log \left(\frac{1}{\delta} \right) \right\}$$

\end{theorem}

\subsection{Proof of Theorem~\ref{thm:1}}

Recall that, for a subset $s$ of $[p]$, the matrix $\mathbb{X}_s$ contains the columns of $\mathbb{X}$ in $s$. We let $r_s$ be the rank of $\mathbb{X}_s$. Also let 
$\Phi_s$ be a matrix whose columns form an orthonormal basis of $\mathbb{X}_s$.

\paragraph{Lemma A:} $$\| \mathbb{X} \pmb{\hat \theta} - \mathbb{X} \pmb{\theta^*} \| \leq 4 \max_{s: |s| = 2k} \sup_{\pmb{u} \in \mathcal{B}_{2}^{r_s}} (\pmb{\widetilde\varepsilon}_s^T \pmb{u})^2$$ where $\pmb{\widetilde\varepsilon}_s = \Phi_s^T \pmb{ \varepsilon}$ with $\|\pmb{\varepsilon}\|_{\psi_2} \leq \sigma$.

The vectors $\pmb{\hat \theta}$ and $\pmb{\theta^*}$ are sparse, the first one by construction and the second one by assumption. We proved this lemma in the last lecture but we need it for the proof of Theorem~\ref{thm:1}.

\paragraph{Lemma B:} $P \left( \sup_{\pmb{u} \in \mathcal{B}_{2}^{r_s}} (\pmb{\widetilde\varepsilon}_s^T \pmb{u})^2 > t \right) \leq 2 \cdot 5^{2k} \exp \left( \frac{-t}{4C\sigma^2} \right)$
\begin{proof}

Let $N$ be a $\frac{1}{2}$-net of $\mathcal{B}_{2}^{r_s}$. By a previous bound (see Lecture 19) $$|N| \leq \left(\frac{2}{\frac{1}{2} +1} \right)^{r_s} \leq 5^{2k}.$$

For any $\pmb{u} \in \mathcal{B}_{2}^{r_s}$, there exists $\pmb{z} \in N,\ \pmb{x} \in \frac{1}{2}\mathcal{B}_{2}^{r_s}$ such that $\pmb{u} = \pmb{z} + \pmb{x}$. By definition of an $\varepsilon$-net
$$\sup_{\pmb{u} \in \mathcal{B}_{2}^{r_s} } |\pmb{\widetilde \varepsilon}_s^T \pmb{u}| \leq \max_{\pmb{z} \in N} |\pmb{\widetilde \varepsilon}_s^T \pmb{z}| + \sup_{\pmb{x} \in \frac{1}{2}\mathcal{B}_{2}^{r_s}} |\pmb{\widetilde \varepsilon}_s^T \pmb{x}| $$

$$\sup_{\pmb{u} \in \mathcal{B}_{2}^{r_s} } |\pmb{\widetilde \varepsilon}_s^T \pmb{u}| \leq \max_{\pmb{z} \in N} |\pmb{\widetilde \varepsilon}_s^T \pmb{z}| + \frac{1}{2} \sup_{\pmb{u} \in \mathcal{B}_{2}^{r_s} } |\pmb{\widetilde \varepsilon}_s^T \pmb{u}| \text{ (by homogeneity) }$$

$$\Rightarrow \sup_{\pmb{u} \in \mathcal{B}_{2}^{r_s} } |\pmb{\widetilde \varepsilon}_s^T \pmb{u}| \leq 2 \max_{\pmb{z} \in N} |\pmb{\widetilde \varepsilon}_s^T \pmb{z}|$$

Hence,
$$P \left( \sup_{\pmb{u} \in \mathcal{B}_{2}^{r_s}} |\pmb{\widetilde\varepsilon}_s^T \pmb{u}| > \sqrt{t} \right) \leq  P \left(  \max_{\pmb{z} \in N} |\pmb{\widetilde \varepsilon}_s^T \pmb{z}| > \frac{\sqrt{t}}{2} \right)$$

$$\leq  \sum_{\pmb{z} \in N} P \left(  |\pmb{\widetilde \varepsilon}_s^T \pmb{z}| > \frac{\sqrt{t}}{2} \right) \text{ (union bound) }$$

$$= 5^{2k} \cdot 2 \exp \left(\frac{-(\frac{\sqrt{t}}{2})^2}{C\sigma^2} \right)  \text{ (sub gaussian) }$$
which concludes the proof.
\end{proof}



We are ready to prove the main theorem.
\begin{proof}[Proof of Theorem~\ref{thm:1}]
$$P \left( \| \mathbb{X} \pmb{\hat \theta} - \mathbb{X} \pmb{\theta^*} \|_2^2 \leq 4 t  \right) \leq P \left(\max_{|S| = 2k} \sup_{\pmb{u} \in \mathcal{B}_{2}^{r_s}} (\pmb{\widetilde\varepsilon}_s^T \pmb{u})^2 \right)  \text{ (by lemma A) }$$
$$\leq \sum_{\max_{|S| = 2k}} P \left(\sup_{\pmb{u} \in \mathcal{B}_{2}^{r_s}} (\pmb{\widetilde\varepsilon}_s^T \pmb{u})^2 \right) \text{ since finite and using the union bound }$$
$$\leq \delta \text{ (by lemma B) }$$
for the choice  $t = \frac{1}{4} C\sigma^2 \{\log(\binom{p}{2k}\times 2 \times 5^{k}) + \log(\frac{1}{\delta}) \}$.

By Stirling's approximation, we get that $P \left( \| \mathbb{X} \pmb{\hat \theta} - \mathbb{X} \pmb{\theta^*} \|_2^2 \leq C \sigma^2 \{k \log(\frac{p}{k}) + \log(\frac{1}{\delta}) \} \right) \leq \delta $.
%
%$$ \frac{1}{n} \|\mathbb{X} \pmb{\hat \theta} - \mathbb{X} \pmb{\theta^*}\| \lesssim \frac{\sigma^2}{n} \left\{k \log \left(\frac{p}{k} \right) + \log \left(\frac{1}{\delta} \right) \right\}$$
\end{proof}


\subsection{Another Special Case: Sub-Gaussian Sequence Model}
We assume here all columns of $\mathbb{X}$ are orthogonal (which can only be satisfied when $p \leq n$). Formally:

\begin{itemize}
\item {\em Assumption ORT}: $\frac{\mathbb{X}^T \mathbb{X}}{n} = \pmb{I}_p$
\item from this consider $y := \frac{1}{n} \mathbb{X}^T Y = \frac{1}{n} \mathbb{X}^T [\mathbb{X} \pmb{\theta^*} + \pmb{\varepsilon }] =  \pmb{\theta^*} + \pmb{\xi }$ where $\xi = \frac{1}{n} \mathbb{X}^T \pmb{\varepsilon} \in \mathbb{R}^p$
\item if $\|\varepsilon\|_{\psi_2}\| \leq \sigma$ the $\|\xi\|_{\psi_2} \leq \frac{\sigma}{\sqrt{n}}$
\item {\em Normal Equations}: $\frac{1}{n} \mathbb{X}^T \mathbb{X} \pmb{\hat \theta}^{LS} = \frac{1}{n} \mathbb{X}^T Y $ then $\pmb{\hat \theta}^{LS} =y$
\item MSE$(\mathbb{X} \pmb{\hat \theta}) = \frac{1}{n} \|\mathbb{X} \pmb{\hat \theta} - \mathbb{X} \pmb{ \theta^*} \|_2^2 = \frac{1}{n} (\pmb{\hat \theta} - \pmb{ \theta^*}) \mathbb{X}^T \mathbb{X} (\pmb{\hat \theta} - \pmb{ \theta^*}) = \|\pmb{\hat \theta} - \pmb{ \theta^*} \|_2^2$ 

\end{itemize}

Next time: assume that $\pmb{\theta^*}$ is sparse. How can we improve over the least squares estimate (whose MSE we showed to be $\approx p \frac{\sigma^2}{n}$)? When there are lots of $0$s in $\pmb{\theta^*}$, we can hope to improve the MSE by taking small $y$ values and setting them equal to 0. We will give the details next time. 

%\bibliography{mybib}
\bibliographystyle{alpha}

\begin{thebibliography}{77}

\bibitem{fks}
Philippe Rigollet and Jan-Christian H{\"u}tter 18.657:
\emph{High Dimensional Statistics Lecture Notes},
MIT, 2017

\end{thebibliography}

\end{document}