\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}
\newtheorem{defn}{Definition}
\newtheorem{example}{Example}

% 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

\usepackage{mathtools}

\newcommand{\of}[1]{\left(#1\right)}
\newcommand{\off}[1]{\left[#1\right]}
\newcommand{\offf}[1]{\left\{#1\right\}}
\newcommand{\aabs}[1]{\left|#1\right|}
\newcommand{\onorm}[1]{\left\lVert#1\right\rVert}
\newcommand{\ang}[1]{\left\langle#1\right\rangle}
\DeclareMathOperator*{\argmin}{arg\,min}

\def\bbX{\mathbb X}
\def\bbR{\mathbb R}
\def\bbS{\mathbb S}
\def\mA{\mathbf A}
\def\mQ{\mathbf Q}
\def\mB{\mathbf B}
\def\mX{\mathbf X}
\def\mY{\mathbf Y}
\def\mx{\mathbf x}
\def\mv{\mathbf v}
\def\mq{\mathbf q}
\def\my{\mathbf y}
\def\mzero{\mathbf 0}
\def\mtheta{\boldsymbol{\theta}}
\def\mepsilon{\boldsymbol{\epsilon}}
\def\tR{\mathcal R}
\def\tH{\mathcal H}

\mathtoolsset{showonlyrefs}
\parindent 0in
\parskip 1.5ex
%\renewcommand{\baselinestretch}{1.25}

\begin{document}

\lecture{16 --- Oct 13, 2021}{Fall 2021}{Sebastien Roch, UW-Madison}{Jiaxin Hu}

\section{Overview}

In the last lecture we studied the linear regression model with sub-Gaussian noise and proved the upper bound of the mean squared error (MSE) of the predicted values with least squared estimate. 

In this lecture we derive the upper bound for the least squared estimate itself and relax the linear assumption on the predictor $\mX$ by considering $\varphi(\mX)$ with non-linear functions $\varphi$.

\section{Review of Matrix Perturbation theory}

We review the matrix perturbation theory before going to the linear regression.

\begin{defn}[Induced Norm] The 2-norm of a matrix $\mA \in \bbR^{n \times m}$ is 
\begin{equation}
    \onorm{\mA}_2 = \max_{\mzero \neq \mx \in \bbR^m} \frac{\onorm{ \mA \mx}}{\onorm{\mx}} = \max_{\mx \in \bbS^{m-1}} \onorm{\mA \mx}.
\end{equation}
\end{defn}

\begin{theorem}[Spectral Theorem] Let $\mA \in \bbR^{d \times d}$ be a symmetric matrix, that is, $\mA^T = \mA$. Then $\mA$ has $d$ orthonormal eigenvectors $\mq_1,...,\mq_d$ with corresponding (not necessarily distinct) real eigenvalues $\lambda_1 \geq \lambda_2 \geq \cdots \geq\lambda_d$. In matrix form, this is written as the matrix factorization 
\begin{equation}
    \mA = \mQ \Lambda \mQ^T  = \sum_{i = 1}^d \lambda_i \mq_i \mq_i^T,
\end{equation}
where $\mQ$ has columns $\mq_1,...,\mq_d$ and $\Lambda = \text{diag}(\lambda_1,...,\lambda_d)$. We refer to this factorization as a spectral decomposition of $\mA$.
\end{theorem}

\begin{defn}[Rayleigh Quotient] Let $\mA \in \bbR^{d \times d}$ be a symmetric matrix. The Rayleigh quotient is defined as 
\begin{equation}
    \tR_{\mA}(\mathbf{u}) = \frac{\ang{\mathbf{u}, \mA \mathbf{u} }}{\ang{\mathbf{u}, \mathbf{u} }},
\end{equation}
which is defined for any $\mzero \neq  \mathbf{u} \in \bbR^d$.
\end{defn}

\begin{theorem}[Courant-Fischer] Let $\mA \in \bbR^{d \times d}$ be a symmetric matrix with spectral decomposition $\mA = \sum_{i=1}^d \lambda_i \mv_i \mv_i^T$ where $\lambda_1 \geq \cdots \geq \lambda_d$. For each $k = 1, ..., d$, define the subspace 
\begin{align}
    \mathcal{V}_k = \text{span}(\mv_1,...,\mv_k) \text{ and } \mathcal{W}_{d - k+1} = \text{span}(\mv_k,...,\mv_d).
\end{align}
Then, for all $k = 1,...,d$, 
\begin{equation}
    \lambda_k = \min_{\mathbf{u} \in \mathcal{V}_k} \tR_{\mA}(\mathbf{u}) = \max_{\mathbf{u} \in \mathcal{W}_{d - k+1}} \tR_{\mA}(\mathbf{u}).
\end{equation}
Furthermore we have the following min-max formulas, which do not depend on the choice of spectral decomposition, for all $k = 1,...,d$,
\begin{equation}
    \lambda_k = \max_{\text{dim}(\mathcal{V}) = k}  \min_{\mathbf{u} \in \mathcal{V}} \tR_{\mA}(\mathbf{u}) =  \min_{\text{dim}(\mathcal{W}) = d - k+1}  \max_{\mathbf{u} \in \mathcal{W}} \tR_{\mA}(\mathbf{u}).
\end{equation}
\end{theorem}

\begin{lemma}[Weyl]  Let $\mA \in \bbR^{d \times d}$ and $\mB \in \bbR^{d \times d}$  be symmetric matrices. Then, for all $j = 1,...,d$ 
\begin{equation}
    \max_{j \in [d]} \aabs{\lambda_j(\mB) - \lambda_j (\mA) } \leq \onorm{\mB - \mA}_2,
\end{equation}
where $\onorm{\mX}_2$ is the induced 2-norm of $\mX$.
\end{lemma}

\begin{theorem}[Davis-Kahan]  Let $\mA \in \bbR^{d \times d}$ and $\mB \in \bbR^{d \times d}$  be symmetric matrices. For an $i \in [d]$, assume that 
\begin{equation}
    \delta \coloneqq \min_{j \neq i} \aabs{ \lambda_i(\mA) - \lambda_j(A)} > 0.
\end{equation}
Then, 
\begin{equation}
    \min_{s \in \{+1,-1\}} \onorm{\mv_i(\mA) - s\mv_i(\mB)}^2 \leq \frac{8 \onorm{\mA -\mB}^2_2}{\delta^2}.
\end{equation}
\end{theorem}
See the slide on the course website for more details.

\section{Error bound for the least square estimator}

Consider $n$ observations $\{(\mx_i, y_i)\}_{i=1}^n$ where $\mx_i \in \bbR^p$ and 
\begin{equation}
    y_i = \mx_i^T \mtheta^* + \epsilon_i,
\end{equation}
where $\mtheta^* \in \bbR^p$ is the unknown coefficient and $\mepsilon = (\epsilon_1,\ldots, \epsilon_n) \in \bbR^n$ is a  mean-zero random vector. Rewrite the linear regression model in the matrix form 
\begin{equation}
    \my = \mX \mtheta^* + \mepsilon,
\end{equation}
where $\my = (y_1,\ldots, y_n) \in \bbR^n$ and $\mX \in \bbR^{n \times p}$ is a matrix with $\mx_i^T$ on the row $i$. The least squared estimator of $\mtheta^*$ is 
\begin{equation}
    \hat \mtheta^{LS} \in \argmin_{\hat \mtheta \in \bbR^p} \frac{1}{n} \onorm{ \my - \mX \hat \mtheta }_2^2.
\end{equation}
We can choose $\hat \mtheta^{LS} = \mX^{+} \my$, where $\mX^{+}$ is the persudo inverse of $\mX$. Note that $\hat \mtheta^{LS}$ is the minimal norm solution and is not necessarily unique.

First, we recall the upper bound for the predicted values with least squared estimate. 
\begin{theorem}[Upper bound of MSE for predicted values]\label{thm:pre} Suppose $\mepsilon$ is a sub-Gaussian vector with $\onorm{\mepsilon}_{\psi_2} \leq K$. Then, with probability $ 1- \delta$, we have 
\begin{equation}
    \text{MSE} (\mX \hat \mtheta^{LS}) = \frac{1}{n} \onorm{ \mX \hat \mtheta^{LS} - \mX \mtheta^*}_2^2 \lesssim \frac{K^2}{n} \of{ \text{rank}(\mX) + \log \frac{1}{\delta} }.
\end{equation}
\end{theorem}


Next, we derive a corollary of Theorem~\ref{thm:pre} to find the upper bound for $\hat \mtheta^{LS}$ itself rather than the predicted values.

\begin{corollary}[Upper bound of MSE for least squared estimate] \label{cor:ls} Suppose $\mepsilon$ is a sub-Gaussian vector with $\onorm{\mepsilon}_{\psi_2} \leq K$.  Assume $p \leq n$ and $\mB = \frac{\mX^T \mX}{n}$ has rank $p$. Then, with probability $ 1- \delta$, we have 
\begin{equation}
    \onorm{ \hat \mtheta^{LS} - \mtheta^*}_2^2 \lesssim \frac{1}{\lambda_{\min}(\mB)} \frac{K^2}{n} \of{ p + \log \frac{1}{\delta}}, 
\end{equation}
where $\lambda_{\min}(\mB)$ is the smallest eigenvalue of $\mB$.
\end{corollary}

\begin{proof}[Proof of Corollary~\ref{cor:ls}] By  Courant-Fischer characterization, we have
\begin{equation}
    \lambda_{\min}(\mB) = \min_{ \mzero \neq \mathbf{u} \in \bbR^p} \frac{\ang{ \mathbf{u} , \mB  \mathbf{u} }}{\ang{ \mathbf{u} , \mathbf{u} }}.
\end{equation}
Note that 
\begin{equation}
     \frac{1}{n} \onorm{ \mX \hat \mtheta^{LS} - \mX \mtheta^*}_2^2 = \of{ \hat \mtheta^{LS} - \mtheta^* }^T  \frac{\mX^T \mX}{n} \of{ \hat \mtheta^{LS} - \mtheta^* } = \of{ \hat \mtheta^{LS} - \mtheta^* }^T \mB \of{ \hat \mtheta^{LS} - \mtheta^* },
\end{equation}
where the second equation follows by the definition of $\mB$. Therefore, we have 
\begin{equation}
      \onorm{ \hat \mtheta^{LS} - \mtheta^*}_2^2  \leq \frac{1}{\lambda_{\min} (\mB)}  \text{MSE} (\mX \hat \mtheta^{LS}),
\end{equation}
which completes the proof by Theorem~\ref{thm:pre}.
\end{proof}

\section{Non-linear regression and oracle bounds}

The linear assumption on $\mX$ is to restrictive for practical application. We model the non-linearity in this section. 

Consider the dictionary $\tH = \{ \varphi_1, \ldots, \varphi_M \}$ where $\varphi_i : \bbR^p \mapsto \bbR$ for all $i \in [M]$. Assume the response $y(\mx) \sim \sum_{i = 1}^M \theta_i \varphi_i(\mx)$. Given $n$ observations $\{(\mx_i, y_i)\}_{i=1}^n$, we can obtain the least squared estimator via 
\begin{equation}
    \hat \mtheta^{LS} \in \argmin_{\hat \mtheta \in \bbR^M} \onorm{\my - \Phi \hat \mtheta}_2^2,
\end{equation}
where the $i$-th row of $\Phi$ is $\Phi_i^T = (\varphi_1(\mx_i),\ldots, \varphi_M(\mx_i))$.

\begin{example}[Polynomial regression] Consider the polynomial regression with $\varphi_1(x) = 1, \varphi_2(x) = x, \varphi_3(x) = x^2$. Then, with observations $\{x_i, y_i\}_{i=1}^n$we have least squared estimator
\begin{equation}
    \hat \mtheta^{LS} \in \argmin_{\hat \mtheta \in \bbR^3} \frac{1}{n} \sum_{i=1}^n \off{  y_i - \of{ \theta_1 + \theta_2 x_i + \theta_3 x_i^2 } }^2.  
\end{equation}
\end{example}

Assume the data is generated from the class of function you assumed. We describe such assumption using the word ``oracle". Next, we establish the oracle bounds for the predicted values of non-linear regression. 
\begin{theorem}[Upper bound of MSE for predicted values in non-linear regression] Suppose the data is of form $y_i = f(\mx_i) + \epsilon_i$ for $i \in [n]$ with $\onorm{\mepsilon}_{\psi_2} = K$. Fix the dictionary $\tH$. Then, with probability $1 - \delta$, we havev
\begin{equation}
    \text{MSE}(\Phi \hat \mtheta^{LS}) \leq \inf_{ \hat \mtheta} \text{MSE}(\Phi \hat \mtheta) + \frac{CK^2}{n} \of{ M + \log \frac{1}{\delta}},
\end{equation}
where $\text{MSE}(\Phi \hat \mtheta)  = \frac{1}{n} \onorm{ \Phi \hat \mtheta  - \mathbf{f}}_2^2$ and $\mathbf{f} = \of{ f(\mx_1),\ldots,f(\mx_n) }$. Note that the $\inf$ chooses the best $\mtheta$ in the class. If the data is indeed generated from this class (realizable), then the term $\inf_{ \hat \mtheta} \text{MSE}(\Phi \hat \mtheta)$ degenerates to 0.
\end{theorem}



\end{document}