\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{epsfig}
\usepackage{bbm}
\usepackage{amsmath}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}

\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{37 --- December 3, 2021}{Fall 2021}{Sebastien Roch, UW-Madison}{Kwangmoon Park, Sebastien Roch}

\section{Overview}


At the end of the Lecture 36, we introduced LASSO estimator for sparse linear regression set up, which also employs thresholding method. In this lecture, we examine the Mean Squared Error(MSE) upper bound of LASSO estimator. Specifically, we will first prove a weak MSE bound of the LASSO estimator, and will show that LASSO achieves the rate $\frac{\sigma^2}{n}\log\left(d\right)$ with additional assumption: Incoherence.

\section{LASSO estimator}

\subsection{Model Definition}
The LASSO estimator of $\theta^*$ is defined by any $\hat{\theta}^{\mathcal{L}}$ such that 

\begin{align}\label{LASSO}
\hat{\theta^{\mathcal{L}}}\in \argmin_{\theta\in \mathbb{R}^d}\left\{
\frac{1}{n}\|Y-\mathbb{X}\theta\|_2^2+2\tau\|\theta\|_1
\right\} ,
\end{align}
where $Y=\mathbb{X}\theta^*+\epsilon$, for $Y\in \mathbb{R}^n$, $\mathbb{X}\in \mathbb{R}^{n\times d}$ and some random $\epsilon$. Note that $\|\cdot\|_2$ and $\|\cdot\|_1$ are $L_1$ and $L_2$ norm respectively, and $\tau$ is a thresholding parameter. The LASSO estimator penalizes the size of the choice of $\theta$ in addition to the MSE, and thus it is sometimes referred to as $L_1$ penalized linear regression model.

\subsection{Weak rate of the LASSO}
Here, we suggest a MSE bound for \eqref{LASSO} with relatively weak assumptions: Sub-Gaussainity and normalized $\mathbb{X}$. Observe that the bound obtained from the theorem below is weaker than the one we saw in the last lecture.

\begin{theorem}[Weak rate of the LASSO]\label{thm1}
Assume that the linear model $Y=\mathbb{X}\theta^*+\epsilon$ holds, where $\epsilon\sim \mbox{subG}_n(\sigma^2)$. Additionally, assume that each j-th column of $\mathbb{X}$ $\mathbb{X}_j$ satisfies $\max_j \|\mathbb{X}_j\|_2\leq \sqrt{n}$. Then, with probability at least $1-\delta$, the LASSO estimator in \eqref{LASSO} with regularization parameter\\

\begin{equation}
2\tau=2\sigma\sqrt{\frac{2\log(2d)}{n}}+2\sigma\sqrt{\frac{2\log(1/\delta)}{n}} \end{equation}

satisfies the MSE bound 
\begin{equation*}
    \mbox{MSE}(\mathbb{X}\hat{\theta}^{\mathcal{L}})=\frac{1}{n}\|\mathbb{X}\hat{\theta}^{\mathcal{L}}-\mathbb{X}\hat{\theta}^*\|_2^2\leq 4\|\theta^*\|_1\sigma\sqrt{\frac{2\log(2d)}{n}}+4\|\theta^*\|_1\sigma\sqrt{\frac{2\log(1/\delta)}{n}}.
\end{equation*}
\end{theorem}


Note that we have $\sigma\sqrt{\frac{\log(2d)}{n}}$ in the bound, which is slower than the bound $\sigma^2\frac{\log(2d)}{n}$ for Hard/Soft Thresholding estimator from the last lecture. Let us first prove this Theorem \ref{thm1} and show that we can obtain same rate for the LASSO estimator with additional assumptions.


\begin{proof}
By the definition of the LASSO estimator $\hat{\theta^{\mathcal{L}}}$, we have \begin{equation}\label{pr1eq1}
\|Y-\mathbb{X}\hat{\theta}^{\mathcal{L}}\|_2^2+2n\tau\|\hat{\theta}^{\mathcal{L}}\|_1\leq  \|Y-\mathbb{X}\hat{\theta}^*\|_2^2+2n\tau\|\hat{\theta}^*\|_1,    
\end{equation} 

since the LASSO estimator is the minimizer of the objective function in \eqref{LASSO}.

By using Holder's inequality after plugging in $Y=\mathbb{X}\theta^*+\epsilon $ on the left hand side of \eqref{pr1eq1}, we have 
\begin{align}\label{pf1eq2}
\|\mathbb{X}\hat{\theta}^{\mathcal{L}}-\mathbb{X}\hat{\theta}^*\|_2^2&\leq 
2\epsilon^T\mathbb{X}(\hat{\theta}^{\mathcal{L}}-\theta^*)^2+2n\tau (
\|\hat{\theta}^{\mathbb{L}}\|_1-\|\theta^*\|_1)\notag\\
&\leq 2\|\mathbb{X}^T\epsilon\|_{\infty}\|\hat{\theta}^{\mathcal{L}}\|_1-2n\tau \|\hat{\theta}^{\mathcal{L}}\|_1+
2\|\mathbb{X}^T\epsilon\|_{\infty}\|\theta^*\|_1-2n\tau \|
\theta^*\|_1 \notag\\ 
&=2(\|\mathbb{X}^T\epsilon\|_{\infty}-n\tau)\|\hat{\theta}^{\mathcal{L}}\|_1+
2(\|\mathbb{X}^T\epsilon\|_{\infty}+n\tau)\|\theta^*\|_1.
\end{align}

We will show that the first part of \eqref{pf1eq2} is at most $0$ and the second part of \eqref{pf1eq2} is at most $4n\tau\|\theta*\|_1$ with probability at least $1-\delta$ with appropriate choice of $t$ below.

By Sub-Gaussianity of $\epsilon$, we have the tail probability bound 
\begin{align*}
\mathbb{P}(\|\mathbb{X}^T\epsilon\|_{\infty}\geq t)&=\mathbb{P}(\max_j|\mathbb{X}_j^T\epsilon|\geq t)\\
&\leq 2d\exp\left(-\frac{t^2}{2n\sigma^2}\right).
\end{align*}

Therefore, by taking $t=\sqrt{2n\log(2d)}+\sigma\sqrt{2n\log(1/\delta)}=n\tau$, we get with probability at least $1-\delta$, $\eqref{pf1eq2}\leq 4n\tau\|\theta*\|_1$, which implies 
\begin{align*}
\|\mathbb{X}\hat{\theta}^{\mathcal{L}}-\mathbb{X}\hat{\theta}^*\|_2^2\leq  4n\tau\|\theta*\|_1,
\end{align*}
and it is the same as the bound in the theorem above with $\tau=\sigma\sqrt{\frac{2\log(2d)}{n}}+\sigma\sqrt{\frac{2\log(1/\delta)}{n}}$.

\end{proof}






\subsection{Fast rate for the LASSO}

In order to obtain faster MSE bound for the LASSO, we need an additional assumption called Incoherence defined as below.

\begin{assumption}[Incoherecne]
We say that the matrix $\mathbb{X}$ has incoherence $k$ or denote it as INC$(k)$ for some integer $k>0$ if 
\begin{equation*}
\left\|\frac{\mathbb{X}^T\mathbb{X}}{n}-I_d\right\|_{\infty}\leq \frac{1}{32k},
\end{equation*}
where the $\left\|\cdot\right\|_{\infty}$ denotes the largest element of $A$ in absolute sense.
\end{assumption}

Note that this INC$(k)$ is an approximate version of assumption ORT introduced in the last lecture, and in case $k\rightarrow \infty$, we can obtain ORT from INC$(k)$. Recall that we needed $d\leq n$ in ORT. However, INC allows $d\gg n$, which is more reasonable in high-dimensional situation. 

We use this INC assumption to employ a Lemma that will be introduced below, and we will use the Lemma to prove faster bound theorem for the LASSO. Let us take a look at the Lemma. 

For any $\Delta \in \mathbb{R}^d$, $S\subset\{1,\hdots, d \}$, define $\Delta_S$ to be the vector with coordinates 
\begin{equation*}
    \Delta_{S,j}=\begin{cases}
    \Delta_j \mbox{ if }j\in S\\
    0 \mbox{ otherwise }.
    \end{cases}
\end{equation*}
With this, we have $\|\Delta\|_1=\|\Delta_S\|_1+\|\Delta_{S^c}\|_1$, and the following Lemma holds.

\begin{lemma}\label{lem1}
Fix a positive integer $k\leq d$ and assume that $\mathbb{X}$ satisfies assumption \mbox{INC}(k). Then, for any $S\in \{1,\hdots,d\}$ such that $|S|\leq k$ and any $\Delta\in \mathbb{R}^d$ that satisfies the cone condition 
\begin{equation}\label{cone}
\|\Delta_{S^c}\|_1\leq 3\|\Delta_S\|_1,    
\end{equation}
it holds that 
\begin{equation*}
    \|\Delta\|_1\leq 2\frac{\|\mathbb{X}\Delta  \|_2^2}{n}.
\end{equation*}
\end{lemma}

Note that in our proof of the fast rate of convergence, we will regard the difference between $\theta^*$, and $\hat{\theta}^{\mathcal{L}}$ in our model as $\Delta$.

%An intuition behind the cone condition \eqref{cone} is that the solution space of $y=\mathbb{X}\theta+\epsilon$ should not go through the $L_1$-ball of $\theta$, $\|\theta\|_1\leq \theta^*$, in order for us to obtain the true value $\theta^*$ as a solution of the $L_1$ penalized optimization, where $\Delta$ in this case is in the null space of $\mathbb{X}$ that gives $y=\mathbb{X}(\theta+\Delta)+\epsilon$.

For some intuition behind the conditions in this lemma, 
see Figures 7.2 and 7.6 in~\cite{wainwright:2019}.
Let us now prove the lemma.
\begin{proof}
By the definition of $\Delta_S$, we have 
\begin{equation}\label{pr2eq1}
\frac{\|\mathbb{X}\Delta\|_2^2}{n}=\frac{\|\mathbb{X}\Delta_S\|_2^2}{n}+\frac{\|\mathbb{X}\Delta_{S^c}\|_2^2}{n}+2\Delta_S^T
\frac{\mathbb{X}^T\mathbb{X}}{n}
\Delta_S.    
\end{equation}
We bound each of the three terms in the RHS of \eqref{pr2eq1}.\\

\textbf{I}. Firstly, it follows from the incoherence condition that 


\begin{equation}
\frac{\|\mathbb{X}\Delta_S\|_2^2}{n}=  \Delta_S^T
\frac{\mathbb{X}^T\mathbb{X}}{n}
\Delta_S =\|\Delta_S\|_2^2+
\Delta_S^T\left(\frac{\mathbb{X}^T\mathbb{X}}{n}-I_d\right)
\Delta_S\geq \|\Delta_S\|_2^2 -\frac{ \|\Delta_S\|_1^2}{32k}.
\end{equation}

\textbf{II}. By the same arguent in \textbf{I} and the cone condition \eqref{cone}, we have
\begin{align}
\frac{\|\mathbb{X}\Delta_{S^c}\|_2^2}{n}\geq    \|\Delta_{S^c}\|_2^2 -\frac{ \|\Delta_{S^c}\|_1^2}{32k}\geq
    \|\Delta_{S^c}\|_2^2 -\frac{9 \|\Delta_{S}\|_1^2}{32k}.
\end{align}

\textbf{III}. Finally, for the cross product term, by the incoherence condition and Cauchy-Swartz inequality, we have
\begin{align}
 2\Delta_S^T
\frac{\mathbb{X}^T\mathbb{X}}{n}
\Delta_S&\leq \frac{2}{32k}\|\Delta_{S}\|_1\|\Delta_{S^c}\|_2   \\
&\leq \frac{6}{32k}\|\Delta_S\|_1^2,
\end{align}
where the last inequality holds by the cone condition \eqref{cone}.

Therefore, combining \textbf{I}, \textbf{II}, \textbf{III} and given the condition that $|S|\leq k$, we have

\begin{align*}
\frac{\|\mathbb{X}\Delta\|_2^2}{n}&\geq \|\Delta_S\|_2^2+\|\Delta_{S^c}\|_2^2-\frac{16|S|}{32k}\|\Delta_S\|_2^2 \\
&\geq \frac{1}{2}\|\Delta\|_2^2
\end{align*}
\end{proof}

One remark from this Lemma is that given the incoherence assumption, the cone condition implies the strong positive curvature, and it is related to how much the LASSO solution is close to the true parameter $\theta^*$.


Now that we have Lemma \ref{lem1}, we are ready to prove the fast rate for the LASSO stated as below.

\begin{theorem}[Fast rate of the LASSO]\label{thm2}
Fix $n\geq 2$, and assume the linear model $Y=\mathbb{X}\theta^*+\epsilon$, where $\epsilon\sim \mbox{subG}_n(\sigma^2)$. In addition, assume that $\|\theta^*\|_0\leq k$ and that $\mathbb{X}$ satisfies assumption INC$(k)$. Then the LASSO estimator $\hat{\theta}^{\mathcal{L}}$ with $\tau$ such that 
\begin{equation*}
2\tau=8\sigma \sqrt{\frac{\log(2d)}{n}}+8\sigma\sqrt{\frac{\log(1/\delta)}{n}},   
\end{equation*}
satisfies 
\begin{equation}\label{MSEbd}
    \mbox{MSE}(\mathbb{X}\hat{\theta}^{\mathcal{L}})=\frac{1}{n}\|\mathbb{X}\hat{\theta}^{\mathcal{L}}-\mathbb{X}\theta^*\|_2^2\lesssim k\sigma^2\frac{\log(2d/\delta)}{n}
\end{equation}
and 
\begin{equation}\label{thetabd}
    \|\hat{\theta}^{\mathcal{L}}-\theta^*\|_2^2\lesssim k\sigma^2\frac{\log(2d/\delta)}{n}
\end{equation}
with probability at least $1-\delta$.
\end{theorem}

\begin{proof}
Similar to the proof of Theorem\ref{thm1}, by the definition of the LASSO estimate, we have 
\begin{equation}\label{pf3eq1}
\|Y-\mathbb{X}\hat{\theta}^{\mathcal{L}}\|_2^2\leq \|Y-\mathbb{X}\theta^*\|_2^2+2n\tau \|\theta^*\|_1-2n\tau\|\hat{\theta}^{\mathcal{L}}\|_1. 
\end{equation}
By adding $n\tau\|\hat{\theta}^{\mathcal{L}}-\theta^*\|_1$ on both sides of \eqref{pf3eq1} and with some arranging of the equations after plugging in $Y=\mathbb{X}\theta^*+\epsilon$, we get

\begin{align}\label{pf3eq2}
\|\mathbb{X}\hat{\theta}^{\mathcal{L}}-\mathbb{X}\theta^*\|_2^2+n\tau\|\hat{\theta}^{\mathcal{L}}-\theta^*\|_1\leq 2\epsilon^T\mathbb{X}(\hat{\theta}^{\mathcal{L}}-\theta^*)+
 2n\tau\|\hat{\theta}^{\mathcal{L}}-\theta^*\|_1+2n\tau\|\theta^*\|_1-2n\tau\|\hat{\theta}^{\mathcal{L}}\|_1.
\end{align}

Let us remove the cross product term on the right hand side of \eqref{pf3eq2}. Once we apply Holder's inequality and use similar steps as in the proof of Theorem \ref{thm1}, with probability at least $1-\delta$, we get
\begin{align*}
\epsilon^T\mathbb{X}(\hat{\theta}^{\mathcal{L}}-\theta^*)&\leq \|\epsilon^T\mathbb{X}\|_{\infty}\|\hat{\theta}^{\mathcal{L}}-\theta^*\|_1 \\
&\leq\frac{n\tau}{2}\|\hat{\theta}^{\mathcal{L}}-\theta^*\|_1,
\end{align*}
where we used the fact that $\|\mathbb{X}_j\|_2^2\leq n+1/(32k)\leq 2n$. Thus, the cross product term cancels out with the second term of the LHS of \eqref{pf3eq2}. Taking $S=\mbox{supp}(\theta^*)$, we get 
\begin{align*}
\eqref{pf3eq2}&\leq 2n\tau \|\hat{\theta}^{\mathcal{L}}-\theta^*\|_1+2n\tau \|\theta^*\|_1-2n\tau\|\hat{\theta}^{\mathcal{L}}\|_1\\
&=2n\tau \|\hat{\theta}^{\mathcal{L}}_S-\theta^*\|_1+2n\tau \|\theta^*\|_1-2n\tau\|\hat{\theta}^{\mathcal{L}}_S\|_1\\
&\leq 4n\tau\|\hat{\theta}^{\mathcal{L}}_S-\theta^*\|_1,
\end{align*}
where the first equality is from the fact that $2n\tau \|\hat{\theta}^{\mathcal{L}}-\theta^*\|_1=2n\tau \|\hat{\theta}^{\mathcal{L}}_{S^c}\|_1$ on $S^c$ and the fact that $2n\tau \|\hat{\theta}^{\mathcal{L}}-\theta^*\|_1=2n\tau \|\hat{\theta}^{\mathcal{L}}_S-\theta^*\|_1$ on $S$ and that $2n\tau \|\hat{\theta}^{\mathcal{L}}\|_1=2n\tau \|\hat{\theta}^{\mathcal{L}}_S\|_1+2n\tau \|\hat{\theta}^{\mathcal{L}}_{S^c}\|_1$. The last inequality is from the triangle inequality.

In particular, we have $\|\hat{\theta}^{\mathcal{L}}_{S^c}-\theta^*_{S^c}\|_1\leq 3\|\hat{\theta}^{\mathcal{L}}_{S}-\theta^*_{S }\|_1$, because we have
\begin{align*}
n\tau\{
\|\hat{\theta}^{\mathcal{L}}_{S}-\theta^*_{S}\|_1+\|\hat{\theta}^{\mathcal{L}}_{S^c}-\theta^*_{S^c}\|_1\}&=n\tau \|\hat{\theta}^{\mathcal{L}}-\theta^*\|_1\\
&\leq     \|\mathbb{X}\hat{\theta}^{\mathcal{L}}-\mathbb{X}\theta^*\|_2^2+n\tau\|\hat{\theta}^{\mathcal{L}}-\theta^*\|_1.\\
&\leq 4n\tau \|\mathbb{X}\hat{\theta}^{\mathcal{L}}_S-\mathbb{X}\theta^*\|_1\\
&=4n\tau \|\mathbb{X}\hat{\theta}^{\mathcal{L}}_S-\mathbb{X}\theta^*_S\|_1.
\end{align*}

Then, with $\Delta=\hat{\theta}^{\mathcal{L}}-\theta^*$, it satisfies the cone condition $\eqref{cone}$. Thus, using the Lemma \ref{lem1} and Cauchy-Swartz inequality, since $|S|\leq k$, we have
\begin{align}\label{pf3eq3}
\|\hat{\theta}^{\mathcal{L}}_S-\theta^*\|_1&\leq \sqrt{|S|}\|\hat{\theta}^{\mathcal{L}}_S-\theta^*\|_2\notag\\
&\leq \sqrt{|S|}\|\hat{\theta}^{\mathcal{L}}-\theta^*\|_2\notag\\
&\leq \sqrt{\frac{2k}{n}}\|\mathbb{X}\hat{\theta}^{\mathcal{L}}-\mathbb{X}\theta^*\|_2.
\end{align}


Combining the result \eqref{pf3eq3} with the fact that 
\begin{align*}
\|\mathbb{X}\hat{\theta}^{\mathcal{L}}-\mathbb{X}\theta^*\|_2^2\leq \|\mathbb{X}\hat{\theta}^{\mathcal{L}}-\mathbb{X}\theta^*\|_2^2+n\tau\|
\hat{\theta}^{\mathcal{L}}-\theta^*
\|_1\leq 4n\tau \|\hat{\theta}^{\mathcal{L}}_S-\theta^*\|_1\leq 4n\tau\sqrt{\frac{2k}{n}}\|\mathbb{X}\hat{\theta}^{\mathcal{L}}-\mathbb{X}\theta^*\|_2,
\end{align*}

we eventually get 
\begin{align*}
\|\mathbb{X}\hat{\theta}^{\mathcal{L}}-\mathbb{X}\theta^*\|_2^2&\leq \left(4n\tau \sqrt{\frac{2k}{n}}\right)^2\\
&\leq 32n\tau^2k,
\end{align*}
which concludes the bound on MSE.

For the coefficient's bound $\|\hat{\theta}^L-\theta^*\|_2^2$, we again Lemma \ref{lem1} and get
\begin{equation}
\|\hat{\theta}^{\mathcal{L}}-\theta^*\|_2^2\leq 2\mbox{MSE}(\mathbb{X}\hat{\theta}^{\mathcal{L}})\leq 64k\tau^2.
\end{equation}


\end{proof}

In fact, we do not even need incoherence condition INC$(k)$ for the bound in Theorem \ref{thm2}, but the conclusion of Lemma \ref{lem1},
\begin{equation*}
\inf_{|S|\leq k}\inf_{\theta \in C_s}\left\{
\frac{\|\mathbb{X}\theta\|_2^2}{n\|\theta\|_2^2}\geq \kappa
\right\},    
\end{equation*}
where $\kappa=\frac{1/}{2}$ and $C_s$ is defined as $C_S=\{
\|\theta_{S^c}\|_2\leq 3\|\theta_S\|_1\}$.\\

Eventually, the LASSO estimator \eqref{LASSO} gives equivalent bound up to a constant $C$ as the Hard/Soft Thresholding estimators that we introduced in the last lecture.












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