\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 6th, 2021}{Fall 2021}{Sebastien Roch, UW-Madison}{Joseph Shenouda}

\section{Overview}

In the last lecture we proved both the weak and fast LASSO rates and introduced the \textit{inchorence} property to prove the fast LASSO rate. 

In this lecture we discuss when we can achieve this incoherence property and conclude by introducing a theorem on oracle inequalities, using a dictionary of functions as opposed to a simple linear model.

\section{Main Section}

Recall the Lasso estimator problem, we assume that our observed data $Y \in \mathbb{R}^{n}$ is generated according to the following model,

\begin{align}
    Y = \mathbb{X}\theta^{*} + \epsilon
\end{align}

Where $||\theta^{*}||_{0} \leq k$ (i.e. $\theta^{*}$ is sparse, having at most $k$ non-zero terms). Under this assumption the Lasso estimator is $\hat{\theta}^{\mathcal{L}}$ such that,
\begin{align}
    \hat{\theta}^{\mathcal{L}} \in \arg \min_{\theta \in \mathbb{R}^{p}} \left\{\frac{1}{n} ||Y - \mathbb{X}\theta||^{2}_{2} + 2\tau ||\theta||_{1}\right\}
\end{align}

We showed that if $\mathbb{X}$ satisfies the following,
\begin{align}
    \left|\frac{\mathbb{X}^{T}\mathbb{X}}{n} - I_{p} \right|_{\infty} \leq \frac{1}{32k}
\end{align}
then it has the incoherence property denoted as INC($k$) and using this INC($k$) condition for $\mathbb{X}$ we can prove the following theorem,

\begin{theorem}[Fast Rate for Lasso]
Fix $n \geq 2$. Assume the linear model $Y = \mathbb{X}\theta^{*}+\epsilon$ holds where $||\epsilon||_{\Psi_{2}} \leq \sigma$. Moreover assume that $||\theta^{*}||_{0} \leq k$ and that $\mathbb{X}$ satisfies INC($k$). Then the Lasso estimator with regularization parameter defined by
\begin{align*}
    \tau = C \sigma \left\{ \sqrt{\frac{\log p}{n}} + \sqrt{\frac{\log(1/\delta)}{n}}\right\}
\end{align*}
Then with probability $1-\delta$
\begin{align*}
    \frac{1}{n} ||\mathbb{X}\hat{\theta}^{\mathcal{L}} - \mathbb{X}\theta^{*}||^{2}_{2} \lesssim \frac{\sigma^{2}}{n} ||\theta^{*}||_{0} \log(p/\delta)
\end{align*}
\end{theorem}
We proved this theorem in the last lecture.

\paragraph{Remark:}
In practice the value for $\sigma$ is an unknown hyperparameter and can be adjusted using cross validation.


\subsection{Validity of Incoherence Assumption}
The fast rate for Lasso estimators depends on this incoherence assumption. It is natural to ask if this assumption makes sense for high dimensional problems when $p >> n$. For $p < n$ as $k\to\infty$ the incoherence assumption is equivalent to orthogonality of the matrix $\mathbb{X}$. So here we show that that there exists a matrix that satisfies INC($k$) even for $p > n$. 

We use a probabilistic method to prove this existence by finding a probability measure which assigns positive probability to objects satisfying this property, implying that there must exist object that satisfy said property. The proof is from Proposition 2.16 \cite{hds}.

\begin{proposition}[2.16]
Let $\mathbb{X} \in \mathbb{R}^{n \times p}$ be a random matrix with iid entries $X_{ij}$ taking values in $\{+1, -1\}$ uniformly. Then the incoherence of $\mathbb{X}$ is $k$ with probability $1-\delta$ as long as 
\begin{align*}
    n \gtrsim k^{2}\log(p/\delta)
\end{align*}


\end{proposition}

\begin{proof}
To show INC($k$) we need that,

\begin{align*}
    \left|\left|\frac{\mathbb{X}^{T}\mathbb{X}}{n} - I\right|\right|_{\infty} \leq \frac{1}{32k}
\end{align*}
To prove this statement we will show that the diagonals of $\frac{1}{n}[\mathbb{X}^{T}\mathbb{X}]_{jj}$ are close to 1 and that the off-diagonals $\frac{1}{n}[\mathbb{X}^{T}\mathbb{X}]_{i j}$ are all close to 0.

We start by showing that the diagonals of $\frac{\mathbb{X}^{T}\mathbb{X}}{n}$ are close to $0$ notice that the $j$th diagonal term is
\begin{align*}
    \frac{1}{n} \sum^{n}_{i=1} X_{ij}^{2}
\end{align*}
Since each $X_{ij} \in \{+1,-1\}$ we have that $\frac{1}{n} \sum^{n}_{i=1} X_{ij}^{2} = 1$. Therefore,

\begin{align*}
        \left|\left|\frac{(\mathbb{X}^{T}\mathbb{X})_{jj}}{n} - 1\right|\right|_{\infty} = 0 \leq \frac{1}{32k}
\end{align*}

For the off-diagonals where $i \neq j$,
\begin{align*}
    \left(\frac{\mathbb{X}^{T}\mathbb{X}}{n}\right)_{ij} = \frac{1}{n} \sum^{n}_{\ell = 1} X_{\ell i} X_{\ell j}
\end{align*}
Since $X_{\ell i}$ and $X_{\ell j}$ are independent and uniform we have that their product is also a uniform random variable taking values $\{+1,-1\}$ and thus it is a bounded random variable so it has subgaussian norm $||X_{\ell i} X_{\ell j}||_{\psi_{2}} \lesssim 1$

Therefore we just need to show that the probability that the off-diagonals are close to $0$ is high,

\begin{align*}
    \mathbb{P} \left(\left|\left|\frac{\mathbb{X}^{T}\mathbb{X}}{n} - I\right|\right|_{\infty} > t\right) \\
    &= \mathbb{P}\left(\max_{i \neq j} \left|\frac{1}{n} \sum^{n}_{\ell =1} X_{\ell i} X_{\ell j}\right| > t\right) \\
    &\leq \sum_{i \neq j}\mathbb{P}\left( \left|\frac{1}{n} \sum^{n}_{\ell =1} X_{\ell i} X_{\ell j} \right| > t\right) \quad (\text{Union Bound}) \\
\end{align*}

Now $\frac{1}{n}\sum^{n}_{\ell = 1} X_{\ell i}X_{\ell j}$ is a sum of independent subgaussain random variables with mean $0$ so we can apply Hoeffding's inequality to get,

\begin{align*}
    \sum_{i \neq j}\mathbb{P}\left( \left|\frac{1}{n} \sum^{n}_{\ell =1} X_{\ell i} X_{\ell j}\right| > t \right) &\leq \sum_{i \neq j} 2\exp\left(-\frac{(nt)^{2}}{2n}\right) \\
    &\leq 2 p^{2} \exp\left(-\frac{(nt)^{2}}{2n}\right)
\end{align*}

If we let $t= \frac{1}{32k}$ then,

\begin{align*}
    \mathbb{P} \left(\left|\left|\frac{\mathbb{X}^{T}\mathbb{X}}{n} - I\right|\right|_{\infty} > \frac{1}{32k} \right) \leq 2 p^{2} \exp\left(-\frac{(n/32k)^{2}}{2n}\right)
\end{align*}
And,
\begin{align*}
    2 p^{2} \exp\left(-\frac{(n/32k)^{2}}{2n}\right) \leq \delta
\end{align*}
For $n \gtrsim k^{2}\log (p/\delta)$
\end{proof}

\section{Oracle Inequalities}

Sometimes the assumption that your data comes from the linear model $y = \mathbb{X}\theta^{*} + \epsilon$ is to strong of an assumption. 

Instead let's assume the data is generated by some arbitrary function $f(x)$ so that the model becomes,

\begin{align}
    Y_i = f(X_i)+\epsilon_i
\end{align}

Now consider a dictionary of functions $\mathcal{H} = \{\varphi_{1},...,\varphi_{M}\}$ where $\varphi_{j}: \mathbb{R}^{p} \to \mathbb{R}$. And we want to estimate the unknown $f$ using a linear combination of the functions in the dictionary.

\begin{align}
    f \approx \varphi_{\theta} := \sum^{M}_{j=1} \theta_{j} \varphi_{j}
\end{align}

The vector $\varphi_{\theta} (X_i) \in \mathbb{R}^{n}$ is defined as,
\begin{align}
    \varphi_{\theta} (X_i) := \sum^{M}_{j=1} \theta_{j} \varphi_{j}(X_i)
\end{align}

So again we can use the same MSE to find our LASSO estimator,

\begin{align}
    \hat{\theta^{\mathcal{L}}} \in \arg \min_{\theta \in \mathbb{R}^{m}} \left\{\frac{1}{n} \sum^{n}_{i=1} (Y_i - \varphi_{\theta} (X_i))^{2} + 2\tau ||\theta||_{1} \right\}
\end{align}

We will present an oracle inequality for the Lasso estimator similar to what we showed earlier. Recall that to prove the fast Lasso estimator rate we needed the incoherence property. For this setting define the matrix $\Phi \in \mathbb{R}^{n \times M}$ with elements $\Phi_{ij} =\varphi_{j}(X_{i})$. The incoherence property is then,

\begin{align}
    INC(k): \left|\left| \frac{\Phi^{T}\Phi}{n} - I_{m} \right|\right|_{\infty} \leq \frac{1}{32k}
\end{align}

Under this condition we have the following theorem from \cite{hds}

\begin{theorem}
Assume that $||\epsilon||_{\psi_{2}} \leq \sigma$ and let $\Phi$ have INC($k$) then if,

\begin{align}
    \tau = C \sigma \left\{\sqrt{\frac{\log M}{n}} + \sqrt{\frac{\log{1/\delta}}{n}}\right\}
\end{align}
and $||\theta^{*}||_{0} \leq k$ then with probability $1-\delta$.

\begin{align}
    \frac{1}{n}||\varphi_{\hat{\theta}^{\mathcal{L}}} - f||^{2}_{2} \lesssim \inf_{\theta \in \mathbb{R}^{M} ,||\theta||_{0} \leq k}  \left\{\frac{1}{n} ||\varphi_{\theta} - f||^{2}_{2} + \frac{\sigma^{2}}{n} ||\theta||_{0} \log(M/\delta) \right\}
\end{align}

\end{theorem}




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