\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{epsfig}

\usepackage{bm}
\usepackage[breaklinks=true,bookmarks=false]{hyperref}
\usepackage{cleveref}
\usepackage{autonum}
\usepackage{url}

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

% macros
% Random variables
\def\reta{{\textnormal{$\eta$}}}
\def\ra{{\textnormal{a}}}
\def\rb{{\textnormal{b}}}
\def\rc{{\textnormal{c}}}
\def\rd{{\textnormal{d}}}
\def\re{{\textnormal{e}}}
\def\rf{{\textnormal{f}}}
\def\rg{{\textnormal{g}}}
\def\rh{{\textnormal{h}}}
\def\ri{{\textnormal{i}}}
\def\rj{{\textnormal{j}}}
\def\rk{{\textnormal{k}}}
\def\rl{{\textnormal{l}}}
\def\rn{{\textnormal{n}}}
\def\ro{{\textnormal{o}}}
\def\rp{{\textnormal{p}}}
\def\rq{{\textnormal{q}}}
\def\rr{{\textnormal{r}}}
\def\rs{{\textnormal{s}}}
\def\rt{{\textnormal{t}}}
\def\ru{{\textnormal{u}}}
\def\rv{{\textnormal{v}}}
\def\rw{{\textnormal{w}}}
\def\rx{{\textnormal{x}}}
\def\ry{{\textnormal{y}}}
\def\rz{{\textnormal{z}}}

% Vectors
\def\vzero{{\bm{0}}}
\def\vone{{\bm{1}}}
\def\vmu{{\bm{\mu}}}
\def\vtheta{{\bm{\theta}}}
\def\va{{\bm{a}}}
\def\vb{{\bm{b}}}
\def\vc{{\bm{c}}}
\def\vd{{\bm{d}}}
\def\ve{{\bm{e}}}
\def\vf{{\bm{f}}}
\def\vg{{\bm{g}}}
\def\vh{{\bm{h}}}
\def\vi{{\bm{i}}}
\def\vj{{\bm{j}}}
\def\vk{{\bm{k}}}
\def\vl{{\bm{l}}}
\def\vm{{\bm{m}}}
\def\vn{{\bm{n}}}
\def\vo{{\bm{o}}}
\def\vp{{\bm{p}}}
\def\vq{{\bm{q}}}
\def\vr{{\bm{r}}}
\def\vs{{\bm{s}}}
\def\vt{{\bm{t}}}
\def\vu{{\bm{u}}}
\def\vv{{\bm{v}}}
\def\vw{{\bm{w}}}
\def\vx{{\bm{x}}}
\def\vy{{\bm{y}}}
\def\vz{{\bm{z}}}

% Random vectors
\def\rva{{\mathbf{a}}}
\def\rvb{{\mathbf{b}}}
\def\rvc{{\mathbf{c}}}
\def\rvd{{\mathbf{d}}}
\def\rve{{\mathbf{e}}}
\def\rvf{{\mathbf{f}}}
\def\rvg{{\mathbf{g}}}
\def\rvh{{\mathbf{h}}}
\def\rvi{{\mathbf{i}}}
\def\rvj{{\mathbf{j}}}
\def\rvk{{\mathbf{k}}}
\def\rvl{{\mathbf{l}}}
\def\rvm{{\mathbf{m}}}
\def\rvn{{\mathbf{n}}}
\def\rvo{{\mathbf{o}}}
\def\rvp{{\mathbf{p}}}
\def\rvq{{\mathbf{q}}}
\def\rvr{{\mathbf{r}}}
\def\rvs{{\mathbf{s}}}
\def\rvt{{\mathbf{t}}}
\def\rvu{{\mathbf{u}}}
\def\rvv{{\mathbf{v}}}
\def\rvw{{\mathbf{w}}}
\def\rvx{{\mathbf{x}}}
\def\rvy{{\mathbf{y}}}
\def\rvz{{\mathbf{z}}}

% Matrix
\def\mA{{\bm{A}}}
\def\mB{{\bm{B}}}
\def\mC{{\bm{C}}}
\def\mD{{\bm{D}}}
\def\mE{{\bm{E}}}
\def\mF{{\bm{F}}}
\def\mG{{\bm{G}}}
\def\mH{{\bm{H}}}
\def\mI{{\bm{I}}}
\def\mJ{{\bm{J}}}
\def\mK{{\bm{K}}}
\def\mL{{\bm{L}}}
\def\mM{{\bm{M}}}
\def\mN{{\bm{N}}}
\def\mO{{\bm{O}}}
\def\mP{{\bm{P}}}
\def\mQ{{\bm{Q}}}
\def\mR{{\bm{R}}}
\def\mS{{\bm{S}}}
\def\mT{{\bm{T}}}
\def\mU{{\bm{U}}}
\def\mV{{\bm{V}}}
\def\mW{{\bm{W}}}
\def\mX{{\bm{X}}}
\def\mY{{\bm{Y}}}
\def\mZ{{\bm{Z}}}

% Mathcal
\def\cA{{\mathcal{A}}}
\def\cB{{\mathcal{B}}}
\def\cC{{\mathcal{C}}}
\def\cD{{\mathcal{D}}}
\def\cE{{\mathcal{E}}}
\def\cF{{\mathcal{F}}}
\def\cG{{\mathcal{G}}}
\def\cH{{\mathcal{H}}}
\def\cI{{\mathcal{I}}}
\def\cJ{{\mathcal{J}}}
\def\cK{{\mathcal{K}}}
\def\cL{{\mathcal{L}}}
\def\cM{{\mathcal{M}}}
\def\cN{{\mathcal{N}}}
\def\cO{{\mathcal{O}}}
\def\cP{{\mathcal{P}}}
\def\cQ{{\mathcal{Q}}}
\def\cR{{\mathcal{R}}}
\def\cS{{\mathcal{S}}}
\def\cT{{\mathcal{T}}}
\def\cU{{\mathcal{U}}}
\def\cV{{\mathcal{V}}}
\def\cW{{\mathcal{W}}}
\def\cX{{\mathcal{X}}}
\def\cY{{\mathcal{Y}}}
\def\cZ{{\mathcal{Z}}}

% mathbb
\def\bA{{\mathbb{A}}}
\def\bB{{\mathbb{B}}}
\def\bC{{\mathbb{C}}}
\def\bD{{\mathbb{D}}}
\def\bE{{\mathbb{E}}}
\def\bF{{\mathbb{F}}}
\def\bG{{\mathbb{G}}}
\def\bH{{\mathbb{H}}}
\def\bI{{\mathbb{I}}}
\def\bJ{{\mathbb{J}}}
\def\bK{{\mathbb{K}}}
\def\bL{{\mathbb{L}}}
\def\bM{{\mathbb{M}}}
\def\bN{{\mathbb{N}}}
\def\bO{{\mathbb{O}}}
\def\bP{{\mathbb{P}}}
\def\bQ{{\mathbb{Q}}}
\def\bR{{\mathbb{R}}}
\def\bS{{\mathbb{S}}}
\def\bT{{\mathbb{T}}}
\def\bU{{\mathbb{U}}}
\def\bV{{\mathbb{V}}}
\def\bW{{\mathbb{W}}}
\def\bX{{\mathbb{X}}}
\def\bY{{\mathbb{Y}}}
\def\bZ{{\mathbb{Z}}}

% Random matrices
\def\rmA{{\mathbf{A}}}
\def\rmB{{\mathbf{B}}}
\def\rmC{{\mathbf{C}}}
\def\rmD{{\mathbf{D}}}
\def\rmE{{\mathbf{E}}}
\def\rmF{{\mathbf{F}}}
\def\rmG{{\mathbf{G}}}
\def\rmH{{\mathbf{H}}}
\def\rmI{{\mathbf{I}}}
\def\rmJ{{\mathbf{J}}}
\def\rmK{{\mathbf{K}}}
\def\rmL{{\mathbf{L}}}
\def\rmM{{\mathbf{M}}}
\def\rmN{{\mathbf{N}}}
\def\rmO{{\mathbf{O}}}
\def\rmP{{\mathbf{P}}}
\def\rmQ{{\mathbf{Q}}}
\def\rmR{{\mathbf{R}}}
\def\rmS{{\mathbf{S}}}
\def\rmT{{\mathbf{T}}}
\def\rmU{{\mathbf{U}}}
\def\rmV{{\mathbf{V}}}
\def\rmW{{\mathbf{W}}}
\def\rmX{{\mathbf{X}}}
\def\rmY{{\mathbf{Y}}}
\def\rmZ{{\mathbf{Z}}}

\DeclareRobustCommand\onedot{}
\def\ie{\emph{i.e}\onedot}
\def\wrt{\emph{w.r.t }\onedot}
\def\eg{\emph{e.g}\onedot}
\def\ow{\emph{o.w}\onedot}
\newcommand{\st}{\mathrm{s.t\onedot}}
\def\iid{\emph{i.i.d}\onedot}
\def\wp{\emph{w.p.}\onedot}

\def\bnull{{\boldsymbol{0}}}
\def\bth{\bm{\theta}}
\def\lse{\widehat{\bm{\theta}}^\mathrm{LS}}
\def\tth{\bth^\star}

\def\eps{\varepsilon}
\def\veps{\bm{\varepsilon}}

\newcommand{\norm}[1]{\left\lVert#1\right\rVert}
\newcommand{\set}[1]{\{#1\}}
\newcommand{\innerproduct}[2]{\langle #1, #2\rangle}

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

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

\begin{document}

\lecture{16 --- October 13, 2021}{Fall 2021}{Sebastien Roch, UW-Madison}{Yuchen Zeng, Sebastien Roch}

\section{Overview}
In the last lecture we (a) studied least square estimator of linear regression model, and (b) proved the upper bound of mean squared error of estimated predicted variables.

In this lecture we (a) derive the concentration bound of the least square estimator of linear regression model, and (b) investigate a more general case: non-linear models.

\section{Reveiw of eigenvalues}
We begin by reviewing a few basic factors about matrices.
\begin{definition}[Induced Norm]
The 2-norm of a matrix $\mA{} \in \bR^{n\times m}$ is 
$$
\norm{\mA}_2 = \max_{\bnull \neq \vx \in \bR^m} \frac{\norm{\mA \vx}}{\vx} = \max_{\vx \in \bS^{m-1}} \norm{\mA \vx}.
$$
\end{definition}

% For a symmetric matrix $\mC \in \bR^{d\times d}$, we let $\lambda_j(\mC)$, $j = 1, \dots, d$, be the eigenvalues of $\mC$ in non-increasing oreder with corresponding orthonormal eigenvectors $\vv_j(\mC)$, $j=1,\dots, d$. Define the subspaces
% $$
% \cV_k(\mC) = \operatorname{span}(\vv_1(\mC), \dots, \vv_k(\mC)) \text{ and } \cW_{d-k+1}(\mC) = \operatorname{span}(\vv_k(\mC), \dots, \vv_d(\mC)).
% $$

% When $\mA$ is symmetric, that is, $a_{ij} = a_{ji}$ for all $i,j$, a remarkable result is that $\mA$ is similar to a diagonal matrix by an orthogonal transformation. Put differently, there exists an orthonomal basis of $\bR^d$ made of eigenvectors of $\mA$.

\begin{theorem}[Spectral Theorem]
Let $\mA \in \bR^{d\times d}$ be a symmetric matrix, that is, $\mA^\top = \mA$. Then $\mA$ has $d$ orthonormal eigenvectors $\vq_1, \dots, \vq_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 
$$
\mA = \mQ \Lambda \mQ^\top = \sum_{i=1}^d \lambda_i \vq_i \vq_i^\top,
$$
where $\mQ$ has columns $\vq_1, \dots, \vq_d$ and $\Lambda = \operatorname{diag}(\lambda_1, \dots, \lambda_d)$. We refer to this factorization as a spectral decomposition of $\mA$. 
\end{theorem}

\begin{definition}[Rayleigh Quotient]
Let $\mA \in \bR^{d\times d}$ be a symmetric matrix. The Rayleigh quotient is defined as 
$$
\cR_{\mA} (\vu) = \frac{\innerproduct{\vu}{\mA \vu}}{\innerproduct{\vu}{\vu}},
$$
which is defined for any $\vu \neq \bnull$ in $\bR^d$.
\end{definition}

\begin{theorem}[Courant-Fischer]
Let $\mA \in \bR^{d\times d}$ be a symmetric matrix with spectral decomposition $\mA = \sum^{d}_{i=1} \lambda_i \vv_i \vv_i^\top$ where $\lambda_1 \geq \cdots \geq \lambda_d$. For each $k = 1, \dots, d$, define the subspace 
$$
\cV_k(\mC) = \operatorname{span}(\vv_1(\mC), \dots, \vv_k(\mC)) \text{ and } \cW_{d-k+1}(\mC) = \operatorname{span}(\vv_k(\mC), \dots, \vv_d(\mC)).
$$
Then, for all $k=1,\dots,d$,
$$
\lambda_k = \min_{\vu \in \cV_k} \cR_{\mA}(\vu) = \max_{\vu\in \cW_{d-k+1}} \cR_{\mA}(\vu).
$$
Furthermore we have the following min-max formulas, which do not depend on the choice of spectral decomposition, for all $k = 1,\dots, d$, 
$$
\lambda_k = \max_{\operatorname{dim}(\cV) = k} \min_{\vu \in \cV} \cR_{\mA} (\vu) = \min_{\operatorname{dim}(\cW) = d-k+1} \max_{\vu \in \cW} \cR_{\mA} (\vu). 
$$
\end{theorem}

% The following lemma is one version of what is known as \emph{Weyl's Inequality}.
\begin{lemma}[Weyl's Inequality]
Let $\mA \in \bR^{d\times d}$ and $\mB \in \bR^{d\times d}$ be symmetric matrices. Then, for all $j = 1,\dots, d$, 
$$
\max_{j\in[d]} |\lambda_j (\mB) - \lambda_j(\mA)| \leq \norm{\mB - \mA}_2,
$$
where $\norm{\mC}_2$ is the induced 2-norm of $\mC$.
\end{lemma}

% While Weyl's Inequality indicates that the eigenvalues of $\mA$ and $\mB$ are close when $\norm{\mA - \mB}_2$ is small, it says nothing about the eigenvectors. The following theorem gives a related bound for eigenvectors. It is usually stated in terms of the angle between the eigenvectors. Here we give a version that will be more suited to our applications. 
\begin{theorem}[Davis-Kahan]
Let $\mA \in \bR^{d\times d}$ and $\mB \in \bR^{d\times d}$ be symmetric matrices. For an $i \in \set{1,\dots, d}$, assume that 
$$
\delta := \min_{j\neq i} |\lambda_i(\mA) - \lambda_j (\mA)| >0,
$$
then 
$$
\min_{s\in\set{+1, -1}} \norm{\vv_i(\mA) - s\vv_i(\mB)}^2 \leq \frac{8 \norm{\mA - \mB}_2^2}{\delta^2}.
$$
\end{theorem}

\section{Controlling the coefficients}
Assume we have $n$ observation pairs $\set{(\rvx_i, \ry_i)}_{i=1}^n$, where $\rvx_i \in \bR^p$, $\ry_i = \rvx_i^\top \tth + \eps_i$, $\tth \in \bR^p$ is unknown, and $\veps = (\eps_1, \dots, \eps_n) \in \bR^n$ is of mean zero. Denote the $\rvy = (\ry_1, \dots, \ry_n)$, $\rmX$ as the matrix with $\rvx_i^\top$ on row $i$. Therefore, the linear regression model can be written as 
$$
\rvy = \rmX \tth + \veps.
$$
The least square estimator of $\tth$ is defined as $\lse \in \arg\min_{\bth \in \bR^p} \frac{1}{n} \norm{\rvy - \rmX \bth}_2^2 $. Then $\lse = \rmX \rvy$ is the minimum norm solution in the set of least square estimators, which is generally unique.

In last lecture, we proved the following theorem, which provides a upper bound for the mean square error of the estimations. 
\begin{theorem}\label{thm:mse_lg}
Suppose $\veps$ is subgaussian, \ie, $\norm{\veps}_{\psi_2} \leq K$. Then \wp $1-\delta$, we have 
$$
\operatorname{MSE}(\rmX \lse) \lesssim \frac{K^2}{n} (\operatorname{rank}(\rmX) + \log(\frac{1}{\delta})),
$$
where $\operatorname{MSE}(\rmX \lse) = \frac{1}{n} \norm{\rmX \lse - \rmX \tth}_2^2$.
\end{theorem}
We derive a corollary which provides an concentration bound for $\lse$, based on the theorem above. 
\begin{corollary}
Suppose $p \leq n$ and $\rmB = \frac{\rmX^\top \rmX}{ n}$ has rank $p$. Then \wp $1-\delta$,
$$
\norm{\lse - \bth}_2^2 \lesssim \frac{1}{\lambda_{\min} (\rmB)} \frac{K^2}{n} (p + \log (\frac{1}{\delta})).
$$
\end{corollary}
\begin{proof}
By Courant-Fischer characterization, we have 
\begin{equation}\label{thm1:e1}
    \lambda_{\min} (\rmB) = \min_{\vu\in \bR^p} \frac{\innerproduct{\vu}{\rmB\vu}}{\innerproduct{\vu}{\vu}}.
\end{equation}
Note that 
\begin{equation}\label{thm1:e2}
    \frac{1}{n} \norm{\rmX \lse -\rmX \tth}_2^2 = (\lse -\tth)^\top \frac{\rmX^\top \rmX}{n}(\lse -\tth) = (\lse -\tth)^\top \rmB (\lse - \tth).
\end{equation}
Combining \eqref{thm1:e1} and \eqref{thm1:e2} yields
$$\norm{\lse - \tth}_2^2 \leq \frac{1}{\lambda_{\min}(\rmB)} \operatorname{MSE}(\rmX \lse).$$
Plugging the upper bound of $\operatorname{MSE}(\rmX \lse)$ in Theorem \ref{thm:mse_lg} completes the proof.
\end{proof}

\section{Modeling non-linearities and an oracle bound}
In this section, we extend the results to some nonlinear models. Consider a dictionary $\cH = \set{\phi_1, \dots, \phi_M}$, where $\phi_i: \bR^p \rightarrow \bR$ is a map, for $i = 1,\dots, M$. Then we can consider functions of $\rvx$ which can be written as $\sum_{i=1}^M \theta_i \phi(\rvx)$. Given $n$ observation pairs $\set{(\rvx_i, \ry_i)}_{i=1}^M$, we minimize the mean square error and obtain the least square estimator $$
\lse = \arg\min_{\bth \in \bR^M} \norm{\rvy - \Phi \bth}_2^2,
$$
where the $i$th row of $\Phi$ is $\Phi_i^\top = (\phi_1(\rvx_i), \dots, \phi_M(\rvx_i))$. 

Next, we provide a quick example to motivate the analysis on nonlinear model. 
\begin{example}
Suppose we observe a quadratic pattern between $\vx$ and $\ry$. We select the features to be $\phi_1(x) = 1, \phi_2(x) = x, \phi_3(x) = x^2$. Then we have $\lse \in \arg\min_{\bth} \frac{1}{n} \sum_{i=1}^n \left(\ry_i - (\theta_1 + \theta_2 \vx_i + \theta_3 \vx_i^2)\right)^2$.

\end{example}
Lastly, we present a theorem, which provides an upper bound for mean square error of the estimation under non-linear models' cases---without assuming that the data
is generated by the class of models used to fit it. This type of
bound is called an \textit{oracle bound}, and we will
have more to say about them later in the course. 
\begin{theorem}[See Theorem 3.3 in~\cite{rig}]
Assume the data $\ry_i = f(\rvx_i) + \eps_i$ with $\norm{\veps}_{\psi_2} \leq K$, for all $i = 1, \dots, n$. Fix the dictionary $\cH$. Then \wp~$1-\delta$, 
$$
\operatorname{MSE}(\Phi \lse) \leq \inf_{\bth \in \bR^p} \operatorname{MSE} (\Phi \bth) + \frac{cK^2}{n}(M + \log (\frac{1}{\delta})),
$$
where $\operatorname{MSE}(\Phi \bth) = \frac{1}{n} \norm{\Phi \bth - \bm{f}}_2^2$, and $\bm{f} = (f(\rvx_1), \dots, f(\rvx_n))$.
\end{theorem}
\begin{proof}
A solution to $\inf_{\bth \in \bR^p} \operatorname{MSE} (\Phi \bth)$ is given by $\bar\bth = \Phi^+ \bm{f}$, which corresponds to projecting $\bm{f}$ onto the column
space of $\Phi$. By the properties of the orthogonal
projection, for any other vector $\Phi\bth$ in the span of the columns of $\Phi$, we have the orthogonality
$$
\langle \Phi \bth - \Phi \bar\bth, \bm{f} - \Phi \bar\bth\rangle = 0.
$$
That applies in particular to the choice $\bth = \lse$. Hence,
by Pythagoras, 
\begin{eqnarray*}
\frac{1}{n} \norm{\Phi \lse - \bm{f}}_2^2
&=& \frac{1}{n} \norm{\Phi \lse - \Phi \bar\bth + \Phi \bar\bth - \bm{f}}_2^2\\
&=& \frac{1}{n} \norm{\Phi \bar\bth - \bm{f}}_2^2
+ \frac{1}{n} \norm{\Phi \lse - \Phi \bar\bth}_2^2.
\end{eqnarray*}
The claim then follows from the definition of $\bar\bth$
and our previous bound on the MSE of linear regression.
\end{proof}

%%\bibliography{mybib}
\bibliographystyle{alpha}

\begin{thebibliography}{77}

\bibitem{rig}
Philippe Rigollet and Jan-Christian Hutter,
\emph{High Dimensional Statistics},
Lecture Notes, 2019.
\url{http://www-math.mit.edu/~rigollet/PDFs/RigNotes17.pdf}%

\end{thebibliography}

\end{document}