\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[a4paper, total={6in, 8in}]{geometry}
\usepackage{amsmath, amsfonts}
\usepackage{hyperref, graphicx}

\title{CSCI 145 Problem 9: The Exact Price of Reusing the Data}
\author{} % TODO: Put your name here
\date{\today}

\begin{document}

\maketitle

\subsection*{Submission Instructions}

Please upload your work to Gradescope by \textbf{11:59pm on DATE}. % TODO: date
\begin{itemize}
\item Turn in a single PDF of \textit{handwritten} solutions. Typed (including \LaTeX) solutions will not be accepted.
\item Problems are grouped into three-week \textbf{cycles}. Once per cycle, you will meet with the grader and present the solution to \emph{one} problem from that cycle, selected at random when you arrive --- so bring your work and be ready to explain any of them.
\end{itemize}

\newpage \section*{Problem 9: The Exact Price of Reusing the Data \hfill \textnormal{2 points}}

Fix a full-column-rank design matrix $\mathbf{X}\in\mathbb{R}^{n\times d}$. Suppose the linear model is correct and the training labels are
$$
\mathbf{y}=\mathbf{X}\mathbf{w}^\star+\boldsymbol{\eta},
\qquad
\mathbb{E}[\boldsymbol{\eta}]=\mathbf{0},
\qquad
\operatorname{Cov}(\boldsymbol{\eta})=\sigma^2\mathbf{I}.
$$
Least squares fits $\hat{\mathbf{y}}=\mathbf{H}\mathbf{y}$, where $\mathbf{H}$ is the projection matrix from Problem 7. To measure performance on the same feature vectors without reusing their noise, an independent replicate has labels $\mathbf{y}'=\mathbf{X}\mathbf{w}^\star+\boldsymbol{\eta}'$, with $\boldsymbol{\eta}'$ distributed like $\boldsymbol{\eta}$ and independent of it.

Quantify exactly how optimistic the training mean squared error is. Derive the expected training error $n^{-1}\|\mathbf{y}-\hat{\mathbf{y}}\|_2^2$ and the expected replicate error $n^{-1}\|\mathbf{y}'-\hat{\mathbf{y}}\|_2^2$ as functions of $n,d,$ and $\sigma^2$. Use your formulas to audit a report claiming that a nearly zero training error near $d=n$ proves that the noise level is nearly zero. Your explanation should identify where the missing error went and connect the resulting gap to the bias--variance account in the reading.

\paragraph{Results you may use.}
The projection satisfies $\mathbf{H}^\top=\mathbf{H}$, $\mathbf{H}^2=\mathbf{H}$, $\operatorname{tr}(\mathbf{H})=d$, and $\mathbf{H}\mathbf{X}=\mathbf{X}$. If a mean-zero random vector has covariance $\sigma^2\mathbf{I}$, then
$$
\mathbb{E}\|\mathbf{A}\boldsymbol{\eta}\|_2^2
=\sigma^2\operatorname{tr}(\mathbf{A}^\top\mathbf{A}).
$$

%\input{solutions/solution09}

\end{document}
