\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{epsfig}
\usepackage{bbm}
\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}

\newcommand{\R}{\mathbb{R}}
\newcommand{\X}{\mathbb{X}}
\renewcommand{\vec}[1]{\boldsymbol{#1}}
% 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{34 --- Nov 24, 2021}{Fall 2021}{Sebastien Roch, UW-Madison}{Yifei Ming, Sebastien Roch}

\section{Overview}

In Lecture 15, we discussed the properties of the (unconstrained) least square estimator for linear regression with sub-Gaussian noises. In this lecture, we turn our focus to a constrained version of the least square estimator that is particularly applicable in the sparse setting. 

\section{Main Section}

We begin by formally introducing the setting of sparse linear regression, and then we consider two examples under different assumptions.

\subsection{Sparse Linear Regression}
\paragraph{Review of Linear Regression}
Recall that in the linear regression problem, we have $n$ data points: $(\X, y)$, where $\X\in\R^{n\times p}$, and $y\in\R^n$. We assume $y = \X\vec\theta^* + \epsilon$, where $\vec\theta^*\in\R^p$ is the unknown parameter. The noise $\epsilon$ is assumed to be sub-Gaussian with $\|\epsilon\|_{\psi^2} \leq \sigma$. The mean squared error (MSE) of an estimator $\X\hat\theta$ is defined as $MSE(\X\hat\theta) = {1\over n}\|\X\theta^* -\X\hat\theta\|^2_2$. In particular, the least square estimator is defined as:
\begin{equation*}
    \hat{\vec\theta}^{LS}\in\arg\min_{\vec{\theta}\in\R^p} \|y- \X\vec{\theta}\|_2^2
\end{equation*}

We proved in Lecture 15 that with probability at least $1 - \delta$:
\begin{equation*}
    MSE(\X\hat{\vec\theta}^{LS})\underset{\sim}{<}\dfrac{\sigma^2}{n}(rank(\X) +\log(1/\delta))
\end{equation*}

\paragraph{Sparsity}
Recall that the $\ell_0$ norm is defined as the number of non-zero entries of a vector: $$\|\vec\theta\|_0 = \sum_{j=1}^p \mathbbm{1}\{\vec\theta_j \neq 0\}$$
Intuitively, sparsity corresponds to a "small" $\ell_{0}$ norm. Specifically, $\vec\theta$ is a $k$-sparse vector if $\|\vec\theta\|_{0} \leq k$. The support of $\vec\theta$ is defined as:
$$
\operatorname{supp}(\vec\theta)=\left\{j: \vec\theta_{j} \neq 0\right\}
$$
Therefore we have $\|\vec\theta\|_{0}=|\operatorname{supp}(\vec\theta)|$.
Moreover, the $\ell_{0}$ ball $\mathcal{B}_{0}(k)$ of all $k$-sparse vectors is denoted as:
$$
\mathcal{B}_{0}(k)=\left\{\vec\theta \in \mathbb{R}^{p}:\|\vec\theta\|_{0} \leq k\right\}
$$
where $k$ is the sparsity level.
\subsection{Benchmarks: Special cases}

\paragraph{Case 1}
After introducing the notations, now let's consider a simple case where we assume the non-zero entries of $\vec\theta$ are given. We denote $S := \operatorname{supp}(\vec\theta^*)$ and $\Delta = |S|$. Let $\X_S$ denote the submatrix of $\X$ with columns $\X_j$ for $\forall j\in S$. The corresponding least square estimator is given by:
$$
    \hat{\vec\theta}^{LS}_S\in\arg\min_{\vec{\theta}\in\R^\Delta} \|y- \X_S\vec{\theta}\|_2^2
$$
Thus the full solution $\hat{\vec\theta}$ is:
$$
\hat{\vec\theta}_i = \begin{cases} \hat{\vec\theta}^{LS}_{S,i} &\qquad i\in S\\
0 &\qquad i \notin S
\end{cases}
$$
Then, by our previous results for linear regression, we have the following bound for MSE (w.p. at least $1 - \delta$):
\begin{equation*}
    MSE(\X\hat{\vec\theta})\underset{\sim}{<}\dfrac{\sigma^2}{n}(\|\theta^*\|_0 +\log(1/\delta))
\end{equation*}

\paragraph{Case 2} Suppose $\operatorname{supp}(\vec\theta^*)$  is unknown but we know the number of non-zero entries $k = \|\vec\theta^*\|_0$. A natural least square estimator for a fixed $k$ is:
$$
    \hat{\vec\theta}^{LS}_{\mathcal{B}_{0}(k)}\in\arg\min \{\|y- \X\vec{\theta}\|_2^2: \vec\theta \in \mathcal{B}_{0}(k)\}
$$
Then we take the best estimator among $\hat{\vec\theta}^{LS}_S$ for each subset $S$ with $|S| = k$. Note that this brute force approach is computationally expensive, as we need to compute $\left(\begin{array}{l}p \\ k\end{array}\right)$ estimators for each $k$---we will come back later in the course to a computationally efficient approach. But for now, despite the computational difficulty, we analyze the statistical properties of this estimator.

\begin{theorem}(Thm 2.6 in \cite{hds})\label{th:theorem1} Fix a positive integer $k \leq p / 2$. Let $K=\mathcal{B}_{0}(k)$ be set of $k$-sparse vectors of $\mathbb{R}^{p}$ and assume that $\vec\theta^{*} \in \mathcal{B}_{0}(k)$. Then, for any $\delta>0$, with probability $1-\delta$, it holds
$$
\operatorname{MSE}\left(\mathbb{X} \hat{\theta}_{\mathcal{B}_{0}(k)}^{LS}\right) \lesssim \frac{\sigma^{2}}{n} \log \left(\begin{array}{c}
p \\
2 k
\end{array}\right)+\frac{\sigma^{2} k}{n}+\frac{\sigma^{2}}{n} \log (1 / \delta)
$$
\end{theorem}

Before proving the theorem, we prove a lemma. First, some notation. For any subset $S \in \{1,\ldots,p\}$, denote $r_{S} = \operatorname{rank}(\X_{S})\leq |S|$. Further, let $\Phi_{S}=\left[\phi_{1}, \ldots, \phi_{r_{S}}\right] \in \mathbb{R}^{n \times r_{S}}$ be the collection of orthonormal basis of the column space of $\X_{S}$.
\begin{lemma}
Let $\Tilde{\vec\theta} = \hat{\vec\theta}^{\mathrm{LS}}_{\mathcal{B}_{0}(k)}$. 
We have
	$$
	\|\mathbb{X} \Tilde{\vec\theta}-\mathbb{X} \vec\theta^{*}\|_{2}^{2} \leq 4 \max _{|S|=2 k} \sup _{u \in \mathcal{B}_{2}^{r_S}}(\tilde{\epsilon}^\top_S u)^2
	$$
	where $\Tilde{\epsilon}_S =\epsilon^\top\Phi_{S} \sim\operatorname{subG}_{r_S}(\sigma^2)$.
\end{lemma}
\begin{proof} 
By definition,
$$
\|y-\mathbb{X} \Tilde{\vec\theta}\|_{2}^{2} \leq\|y-\mathbb{X} \vec\theta^{*}\|_{2}^{2}=\|\epsilon\|_{2}^{2}.
$$
Moreover,
$$
\|y-\mathbb{X} \Tilde{\vec\theta}\|_{2}^{2}=\|\mathbb{X} \vec\theta^{*}+\epsilon-\mathbb{X} \Tilde{\vec\theta}\|_{2}^{2}=\|\mathbb{X} \Tilde{\vec\theta}-\mathbb{X} \vec\theta^{*}\|_{2}^{2}-2 \epsilon^{\top} \mathbb{X}\left(\Tilde{\vec\theta}-\vec\theta^{*}\right)+\|\epsilon\|_{2}^{2}.
$$
Rearranging the terms, we have
$$
\|\mathbb{X} \Tilde{\vec\theta}-\mathbb{X} \vec\theta^{*}\|_{2}^{2} \leq 2 \epsilon^{\top} \mathbb{X}\left(\Tilde{\vec\theta}-\vec\theta^{*}\right)=
2\|\mathbb{X} \Tilde{\vec\theta}-\mathbb{X} \vec\theta^{*}\|_{2}\frac{\epsilon^{\top} \mathbb{X}\left(\Tilde{\vec\theta}-\vec\theta^{*}\right)}{\|\mathbb{X} \Tilde{\vec\theta}-\mathbb{X} \vec\theta^{*}\|_{2}}.
$$
Next we aim to bound
$$
\frac{\epsilon^{\top} \mathbb{X}\left(\Tilde{\vec\theta}-\vec\theta^{*}\right)}{\|\mathbb{X} \Tilde{\vec\theta}-\mathbb{X} \vec\theta^{*}\|_{2}}.
$$
Let $\hat S = \operatorname{supp}(\Tilde{\vec\theta} - \vec{\theta}^*)$. As both $\Tilde{\vec\theta}$ and $ \vec{\theta}^*$ have at most $k$ non-zero entries, we have $|\hat S| \leq 2k$. Then we know that there exists some vector $\nu \in \mathbb{R}^{r_{\hat{S}}}$ such that
$$
\mathbb{X}\left(\Tilde{\vec\theta}-\vec\theta^{*}\right) = \Phi_{\hat S}\nu.
$$
Let $\Tilde{\epsilon} =\epsilon^\top\Phi_{\hat S} $. Then we have
$$
r = \frac{\epsilon^{\top} \mathbb{X}\left(\Tilde{\vec\theta}-\vec\theta^{*}\right)}{\|\mathbb{X} \Tilde{\vec\theta}-\mathbb{X} \vec\theta^{*}\|_{2}} = { \epsilon^\top \Phi_{\hat S}\nu \over \|\nu\|_2} = \Tilde{\epsilon}^\top{\nu\over\|\nu\|_2}\leq \max _{|S|=2 k} \sup _{u \in \mathcal{B}_{2}^{r_S}}\left[\epsilon^{\top} \Phi_{S}\right] u,
$$
where $\mathcal{B}_{2}^{r_S}$ is the unit ball of $\R^{r_{S}}$. 
Here we need to ``sup out'' the support of $\Tilde{\vec\theta} - \vec{\theta}^*$ and the vector $\nu$ as they depend in a
subtle way on $\epsilon$ (and therefore would prevent us
form applying the sub-Gaussianity of $\epsilon$).
Therefore, we have: 
$$
\|\mathbb{X} \Tilde{\vec\theta}-\mathbb{X} \vec\theta^{*}\|_{2}^{2} \leq 4 \max _{|S|=2 k} \sup _{u \in \mathcal{B}_{2}^{r_S}}(\tilde{\epsilon}^\top_S u)^2,
$$
where $\Tilde{\epsilon}_S =\epsilon^\top\Phi_{S} \sim\operatorname{subG}_{r_S}(\sigma^2)$,
as claimed. This last claim on the sub-Gaussian norm
of  $\epsilon^\top\Phi_{S}$ follows from the fact that
the columns of $\Phi_{S}$ are orthonormal by construction
and from the defintion of the sub-Gaussian vectors. 
\end{proof}

We will conclude the proof of the theorem next time.

%By union bound, we have for any $t>0$,
%$$
%\mathbb{P}\left(\max _{|S|=2 k} \sup _{u \in \mathcal{B}_{2}^{r_{S}}}\left(\tilde{\varepsilon}^{\top} u\right)^{2}>t\right) \leq \sum_{|S|=2 k} \mathbb{P}\left(\sup _{u \in \mathcal{B}_{2}^{r_S}}\left(\tilde{\varepsilon}^{\top} u\right)^{2}>t\right)
%$$
%It follows from the proof of Thm $1.19$ in \cite{hds} that for any $|S| \leq 2 k$,
%$$
%\mathbb{P}\left(\sup _{u \in \mathcal{B}_{2}^{r_{S}}}\left(\tilde{\varepsilon}^{\top} u\right)^{2}>t\right) \leq 6^{|S|} e^{-\frac{t}{8 \sigma^{2}}} \leq 6^{2 k} e^{-\frac{t}{8 \sigma^{2}}}
%$$
%Together, the above three displays yield
%$$
%\mathbb{P}\left(\left|\mathbb{X}\tilde{\vec\theta}-\mathbb{X} \vec\theta^{*}\right|_{2}^{2}>4 t\right) \leq\left(\begin{array}{c}
%p \\
%2 k
%\end{array}\right) 6^{2 k} e^{-\frac{t}{8 \sigma^{2}}}
%$$
%lastly, to bound the bound, we require $t$ that satisfies:
%$$
%t \geq C \sigma^{2}\left\{\log \left(\begin{array}{c}
%p \\
%2 k
%\end{array}\right)+k \log (6)+\log (1 / \delta)\right\}
%$$
% As we assume that $\epsilon \sim \operatorname{subG}\left(\sigma^{2}\right)$, we have:
% $$
% \mathbb{E}\left[e^{s \tilde{\epsilon}^{\top} u}\right]=\mathbb{E}\left[e^{s \epsilon^{\top} \Phi u}\right] \leq \mathrm{e}^{\frac{s^{2} \sigma^{2}}{2}}
% $$
% Therefore, $\tilde{\epsilon} \sim \operatorname{subG}_{r_{\hat S}}\left(\sigma^{2}\right)$
%\end{proof}

\bibliographystyle{alpha}

\begin{thebibliography}{77}

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

\end{thebibliography}

\end{document}
