\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{38 --- December 6, 2021}{Fall 2021}{Sebastien Roch, UW-Madison}{Lisheng Ren, Sebastien Roch}
	
	\section{Overview}
	
	In the last lecture we gived the analysis of Lasso estimator for sparse linear regression. 
	In this lecture we will wrap up the analysis and then generalize the setting to sparse oracle inequality.
	
	\section{Main Section}
		
	\subsection{Lasso estimator on sparse linear regression}
	First recall our definition for Lasso estimator
	\begin{definition}
		Let $\mathbb{X}\in \mathbb{R}^{n\times p}$ be $n$ samples on $\mathbb{R}^p$ and $y\in \mathbb{R}^{n}$ be the labels. We define the Lasso estimator as
		$$\hat \theta^L\in \mathrm{argmin}_{\theta\in\mathbb{R}^p}\{\frac{1}{n}\|Y-\mathbb{X}\theta \|_2^2+2\tau\|\theta\|_1\}$$
	\end{definition}
	
	Then recall the definition for Incoherence 
	\begin{definition}
		We say the matrix $\mathbb{X}$ has incoherence $k$ and denote it as $\mathrm{INC}(k)$ for integer $k>0$ if
		$$\left \|\frac{\mathbb{X}^T\mathbb{X}}{n}-I_d\right\|_\infty\leq \frac{1}{32k}$$
	\end{definition}
	
	Note we need the incoherence assumption for Fast rate of Lasso estimator.
	\begin{theorem} \label{1}
		Under $\mathrm{INC}(k)$ assumption, with
		$$\tau=C\sigma\left (\sqrt{\frac{\log p}{n}}+\sqrt{\frac{\log(1/\delta)}{n}}\right)$$
		then with probability $1-\delta$
		$$\frac{1}{n}\|\mathbb{X}\hat\theta^L-\mathbb{X}\theta^*\|_2^2\lesssim\frac{\sigma^2\|\theta^*\|_0\log(p/\delta)}{n}$$
	\end{theorem}
	The proof has already been discussed in note for Lecture 37.
	\begin{proposition} [Proposition 2.16 in \cite{hds}]
		Let $\mathbb{X}\in \{\pm 1\}^{n \times p}$ be a random matrix such that entries are i.i.d Rademacher ($\pm 1$) random variables. The incoherence of $\mathbb{X}$ is $k$ w.p. $1-\delta$ as long as
		$$n\gtrsim k^2\log (p/\delta)$$
	\end{proposition}
	\begin{proof}
		For diagonal entries, 
		$$\left(\frac{\mathbb{X}^T\mathbb{X}}{n}\right)_{j,j}=\frac{1}{n}\sum_{i=1}^n \mathbb{X}^2_{i,j}=1$$
		Thus $\frac{\mathbb{X}^T\mathbb{X}}{n}-I_p$ is 0 on the diagonal.\\
		For non-diagonal entries, 
		$$\left(\frac{\mathbb{X}^T\mathbb{X}}{n}\right)_{i,j}=\frac{1}{n}\sum_{l=1}^n \mathbb{X}_{l,i}\mathbb{X}_{l,j}$$
		Note $\mathbb{X}_{l,i}\mathbb{X}_{l,j}$ is also Rademacher random variable which is subgaussian, thus $\|\sum_{l=1}^n \mathbb{X}_{l,i}\mathbb{X}_{l,j}\|_{\psi_2}\lesssim n$. Therefore concentration and an union bond on non-diagonal entries, we have 
		$$\mathbb{P}(\|\frac{\mathbb{X}^T\mathbb{X}}{n}-I_p\|_\infty >\frac{1}{32k})\leq \sum_{i\neq j\in [p]}\mathbb{P}(\frac{1}{n}\sum_{l=1}^n \mathbb{X}_{l,i}\mathbb{X}_{l,j}>\frac{1}{32k} )\leq p^2\exp(-\frac{Cn}{k^2})$$
		Take the value equal to $\delta$ gives the proposition.
	\end{proof}
		
	\subsubsection{Lasso estimator on sparse oracle equality}
	The setting of the problem is the following.
	Let $\phi_1,\cdots,\phi_m: \mathcal{X}\mapsto \mathbb{R}$ be a set of dictionary functions and $\theta\in \mathbb{R}^m$ be a $k$-sparse vector. We will use $\phi_\theta$ to denote $\phi_\theta=\sum_{i=1}^m \theta_i\phi_i$.
	We assume the true concept is $f=\phi_{\theta^*}$ and assume we observe $\mathbb{X}$ and $Y$ such that 
	$$Y_i=f(X_i)+\epsilon_i, \text{      $i=1,\cdots ,n$}$$
	where and $\epsilon$ is a subgaussian with variance proxy $\sigma^2$.
	
	For any estimator $\hat f$, we define the mean squared error as
	$$\mathrm{MSE}(\hat f)=\frac{1}{n}\sum_{i=1}^n (f(X_i)-\hat f(X_i))^2$$
	In this setting, we can reduce the problem to sparse linear regression by considering the matrix $\Phi$ with $i$-th row equal to $[\phi_1(X_i),\cdots,\phi_m(X_i)]$. 
	%Then $\phi_\theta(X_i)=\Phi \theta$, thus the problem reduces to sparse linear regression.
	We define the Lasso estimator $\hat\theta^L$ for $\theta^*$ as 
	$$\hat\theta^L\in \mathrm{argmin}_{\theta\in\mathbb{R}^m}\{
	\frac{1}{n}\|Y-\Phi\theta \|_2^2 +2\tau\|\theta\|_1\}$$
	
	 Therefore the same analysis for Lasso estimator can also be applied here.
	\begin{theorem} [Theorem 3.5 in \cite{hds}]
	Under $\mathrm{INC}(k)$ assumption ($\|\frac{\mathbb{X}'^T\mathbb{X}'}{n}-I_m\|_\infty\leq \frac{1}{32k}$), with
	$$\tau=C\sigma\left (\sqrt{\frac{\log m}{n}}+\sqrt{\frac{\log(1/\delta)}{n}}\right)$$
	Let $\hat f=\phi_{\hat \theta^L}$then with probability $1-\delta$
	$$\frac{1}{n}\sum_{i=1}^n (f(\mathbb{X}_i)-\hat f(\mathbb{X}_i))^2\lesssim\frac{\sigma^2\|\theta^*\|_0\log(m/\delta)}{n}$$
	and
	$$\mathrm{MSE}(\phi_{\hat \theta})\lesssim\inf_{\theta\in\mathbb{R}^m, \|\theta\|_0\leq k}(\mathrm{MSE}(\phi_\theta)+\frac{\sigma^2\|\theta\|_0\log (m/\delta)}{n})$$
	\end{theorem}
	The proof of the above 
	%by having  $\mathbb{X}_{i,j}'=\phi_j(\mathbb{X}_i)$ and apply 
	is similar to that of Theorem \ref{1} and is omitted. 
	%on $\mathbb{X}'$.
	
	%\bibliography{mybib}
	\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.
	
	\bibitem{wainwright:2019}
	Wainwright, M. J. (2019). \emph{High-Dimensional Statistics: A Non-Asymptotic Viewpoint}. CUP.
	
\end{thebibliography}	
\end{document}