\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{epsfig}
\usepackage[colorlinks=true,linkcolor=blue]{hyperref}
\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{remark}[theorem]{Remark}
\newtheorem{assumption}[theorem]{Assumption}


\newcommand{\R}{\mathbb{R}}
\newcommand{\X}{\mathbb{X}}
\renewcommand{\vec}[1]{\boldsymbol{#1}}
\newcommand{\vect}[1]{\mathbf{#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{15 --- Oct 11, 2021}{Fall 2021}{Sebastien Roch, UW-Madison}{Angeliki Giannou}

\section{Overview}

In the last lecture we derived bounds for mean estimation of sub-Gaussian vectors.

In this lecture we will focus on the linear regression problem with noisy observations. Our goal would be to estimate the true parameter of the problem and derive error bounds of the loss. In order to do so, we will leverage tools from the previous lecture. 

\section{Main Section}

\subsection{Linear regression}
The problem has the following components:
\begin{itemize}
    \item Let $\vec{\theta}^*\in\R^p$ be an unknown vector.
    \item Let $f(\vect{x}) = \vect{x}^T\vec{\theta}^*$, $\vect{x}\in\R^p$.
    \item We make $n$ noisy observations $(\vect{x}_i,y_i)$ , $y_i = f(\vect{x}_i) + \epsilon_i$. We consider $\epsilon_i\in\R$, $i=1,\hdots,n$ to be a random variable with mean zero.  
\end{itemize}
Our \emph{goal} is to find $\vect{\hat{\vec{\theta}}}\in\R^p$ that minimizes the MSE loss, i.e.,
\begin{equation}\label{eq:loss}
    MSE(\hat{f}) =\dfrac{1}{n}\sum_{i=1}^n \left(\hat{f}_n(\vect{x}_i)-{f}_n(\vect{x}_i)\right)^2
\end{equation}
where $\hat{f}_n(\vect{x})=\vect{x}^T\vect{\hat{\vec{\theta}}}$. This problem cannot be solved directly, since we don't have access to the values $f(\vect{x}_i)$.
\subsubsection{Least square solution}
Instead we will solve:
\begin{equation}\label{eq:eq1}\tag{*}
    \min_{\vec{\hat{\theta}}\in\R^p} \|\vect{y} - \X\vec{\hat{\theta}}\|_2^2
\end{equation}
where $\vect{y} = (y_1,\hdots,y_n)^T\in\R^n$,  $\X = (\vect{x}_1,\hdots,\vect{x}_n)^T\in\R^{n\times p}$.

\begin{theorem}\label{th:theorem1}
Let $\hat{\vec{\theta}}^{LS}$ be a solution to \eqref{eq:eq1}. Then 
\begin{equation}\label{eq:eq2}\tag{**}
    \X^T\X\hat{\vec{\theta}}^{LS} = \X^T\vect{y}
\end{equation} 
Furthermore, we can always choose $\hat{\vec{\theta}}^{LS} = \X^+\vect{y}$.
\end{theorem}
\paragraph{Recall.} If $A\in\R^{n\times p}$ with Singular Value Decomposition (SVD): $A = USV^T$, where $U\in\R^{n\times n}$, $V\in\R^{p\times p}$ are orthogonal matrices and $S\in\R^{n\times p}$ is a diagonal matrix with all of its elements non-negative; then
\begin{equation*}
    A^+ = VS^+U^T
\end{equation*}
where 
\begin{equation*}
    s_{ii}^+ = \left\{\begin{matrix}
 \dfrac{1}{s_{ii}}&,\text{ if }s_i >0 \\ 
 0&, \text{ otherwise} 
\end{matrix}\right.
\end{equation*}
We now proceed to the proof of theorem \ref{th:theorem1}.
\begin{proof}
Notice that \eqref{eq:eq1} is convex and its solution satisfies
\begin{equation*}
    \nabla_{\vec{\theta}}\|\vect{y} -\X\vec{\theta}\|^2_2 =0
\end{equation*}
By doing the calculations we can derive \eqref{eq:eq2}.\\
Considering now the second part of the theorem, if the solution of the problem is not unique, one choice is to minimize also the norm of the parameter. Thus, we will solve:
\begin{equation*}
    \min_{\vec{\theta}}\|\vec{\theta}\|_2^2\quad \text{ s.t. }\quad \X^T\X\vec{\theta}= \X^T\vect{y}
\end{equation*}
Using SVD we have:
\begin{align*}
    \X^T\X =VS^TU^TUSV^T = VS^2V^T
\end{align*}
So, \eqref{eq:eq2} becomes:
\begin{equation*}
    VS^2V^T\vec{\theta}=VSU^T\vect{y} \Rightarrow S^2V^T\vec{\theta}=SU^T\vect{y}
\end{equation*} 
Let $\vect{z} = V^T\vec{\theta}$ and $\vect{w} = U^T\vect{y}$ and \eqref{eq:eq2} becomes:
\begin{equation*}
    s_{ii}^2z_i = s_{ii}w_i \text{ for all } i=1,\hdots,n
\end{equation*}
Notice that since $V$ is orthogonal, $\|\vect{z}\|_2^2 = \|\vec{\theta}\|^2_2$. So, we now want to minimize the norm of $\vect{z}$ or equivalently the expression
\begin{equation*}
    z_1^2 +\hdots z_n^2 \quad\text{ subject to }\quad s_{ii}^2z_i = s_{ii}w_i 
\end{equation*}
In the case that $s_{ii} =0$ we will choose $z_i =0$, since we want to minimize the above expression. In any other case we will choose $z_i =\dfrac{
w_i}{s_{ii}}$. We finally get that $\vect{z} = S^+\vect{w}$ or 
\begin{equation*}
   \vec{\theta} = VS^+U^T\vect{y} = \X^+\vect{y}
\end{equation*}
\end{proof}
\begin{remark}
Of course if $\X$ is invertible, $\vec{\theta}= \X^{-1}\vect{y}$.
\end{remark}
\begin{remark}
We can also think of the minimization of the norm of $\vec{\theta}$ as the projection to the column space of the matrix $\X$.
\end{remark}
\subsection{The MSE loss}
We now want to focus on the MSE loss meaning $\dfrac{1}{n}\|\X\hat{\vec{\theta}}^{LS} -\X\vec{\theta}^*\|^2_2$ and see whether we can bound it. 
\begin{theorem}
Suppose that $\vec{\epsilon} = (\epsilon_1,\hdots,\epsilon_n)$ is sub-Gaussian with $\|\vec{\epsilon}\|_{\psi_2}\leq K$. Then, with probability at least $1-\delta$ 
\begin{equation*}
    MSE(\X\hat{\vec{\theta}}^{LS})\underset{\sim}{<}\dfrac{K^2}{n}(rank(\X) +\log(1/\delta))
\end{equation*}
\end{theorem}
\begin{remark}
If $p<<n$ then we get a small bound. However, if $p>>n$ then $rank(\X) \simeq n$ and we just get a big constant as a bound.
\end{remark}
\begin{proof}
We have
\begin{align*}
    \X\hat{\vec{\theta}}^{LS} -\X\vec{\theta}^* &= \X\X^+\vect{y} -\X\vec{\theta}^*\\
    &=\X\X^+(\X\vec{\theta}^* +\vec{\epsilon}) - \X\vec{\theta}^*\\
    &= \X\X^+\X\vec{\theta}^* + \X\X^+\vec{\epsilon} -\X\vec{\theta}^*\\
    &=USV^TVS^+U^TUSV^T\vec{\theta}^*+ \X\X^+\vec{\epsilon} -\X\vec{\theta}^*\\
    &=USV^T\vec{\theta}^* + \X\X^+\vec{\epsilon} -\X\vec{\theta}^*\\
    &= \X\vec{\theta}^* + \X\X^+\vec{\epsilon} -\X\vec{\theta}^*\\
    &= \X\X^+\vec{\epsilon}
\end{align*}
So,
\begin{equation*}
    \dfrac{1}{n}\|\X\hat{\vec{\theta}}^{LS} -\X\vec{\theta}^*\|^2_2 = \dfrac{1}{n}\|\\X\X^+\vec{\epsilon}\|^2_2
\end{equation*}
In the previous lecture we saw that if $B$ is a matrix and $\|X\|_{\psi_2}\leq K$, then for all $t\geq 0$
\begin{equation*}
    \mathbb{P}\left(\|BX\|_2^2\geq CK^2\|B\|^2_{F} +t\right)\leq \exp(-ct/K^2\|B\|_2^2)
\end{equation*}
Using the above inequality with $B=\dfrac{\X\X^+}{\sqrt{n}}$ and $X=\vec{\epsilon}$ we get
\begin{equation*}
    \mathbb{P}\left(\dfrac{1}{n}\|\X\X^T\vec{\epsilon}\|_2^2\geq \dfrac{CK^2}{n}\|\X\X^+\|_{F}^2 +t\right)\leq \exp\left(\dfrac{-ctn}{K^2\|\X\X^+\|_2^2}\right)
\end{equation*}
By choosing $t=\dfrac{K^2\|\X\X^+\|_2^2}{cn}\log(1/\delta)$ we get that with probability at least $1-\delta$
\begin{align*}
     MSE(\X\hat{\vec{\theta}}^{LS}) &\leq  \dfrac{CK^2}{n}rank{\X}+ \dfrac{K^2}{cn}\\
     &\underset{\sim}{<} \dfrac{K^2}{n}(rank(\X) +\log(1/\delta))
\end{align*}
Notice that $\|\X\X^+\|_{2}^2 $ is the maximum singular value of $\X\X^+$ which is equal to one and $\|\X\X^+\|_F^2$ is equal to the rank of $\X$.
\end{proof}
\end{document}