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

\title{CSCI 145 Problem 7: Which Label Can Move the Fit?}
\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 7: Which Label Can Move the Fit? \hfill \textnormal{2 points}}

Let $\mathbf{X}\in\mathbb{R}^{n\times d}$ have linearly independent columns, and let least squares produce
$$
\hat{\mathbf{y}}=\mathbf{H}\mathbf{y},
\qquad
\mathbf{H}=\mathbf{X}(\mathbf{X}^\top\mathbf{X})^{-1}\mathbf{X}^\top.
$$
A lab later discovers that label $i$ was wrong by $\delta$, so the corrected label vector is $\mathbf{y}+\delta\mathbf{e}_i$, where $\mathbf{e}_i$ is the $i$th standard basis vector. The model is refit using the same design matrix.

Determine exactly how much this correction can move the full vector of fitted predictions. Your answer should show that one number $h_i=[\mathbf{H}]_{ii}$ measures both the change at the corrected training point and the total squared change across all training predictions. Establish the sharp bounds on $h_i$, show that the $n$ values satisfy
$$
\sum_{i=1}^n h_i=d,
$$
and use these facts to assess the claim that averaging the loss over the data makes all labels equally influential. Give a concrete full-column-rank design matrix for which two labels have different influence, and interpret what distinguishes the high-influence row geometrically.

\paragraph{Results you may use.}
The reading shows that least squares is orthogonal projection. You may use that the matrix $\mathbf{H}$ above is this projection, so $\mathbf{H}^\top=\mathbf{H}$ and $\mathbf{H}^2=\mathbf{H}$, and that the trace of a projection equals the dimension of its image.

%\input{solutions/solution07}

\end{document}
