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

\title{CSCI 145 Problem 3: Three Gradients You'll Use All Semester}
\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 3: Three Gradients You'll Use All Semester}

Linear regression, logistic regression, a neural network, and a reinforcement-learning policy are all trained by the same loop: write down a loss, take its gradient, and step downhill.
Between them they use three gradient formulas, and this problem derives all three from the single definition we wrote in lecture.

For $f: \mathbb{R}^d \to \mathbb{R}$, the gradient $\nabla_{\mathbf{x}} f$ is the unique vector satisfying, for every direction $\mathbf{v} \in \mathbb{R}^d$,
\begin{align*}
    f(\mathbf{x} + \epsilon \mathbf{v}) = f(\mathbf{x}) + \epsilon \, \langle \nabla_{\mathbf{x}} f, \mathbf{v} \rangle + o(\epsilon),
\end{align*}
where $o(\epsilon)$ collects terms that shrink faster than $\epsilon$ (like $\epsilon^2$).
Every part below uses the same recipe: expand $f(\mathbf{x} + \epsilon \mathbf{v})$, and whatever vector ends up paired with $\mathbf{v}$ inside the inner product of the $\epsilon$ term \emph{is} the gradient.

\subsection*{Part A: The Linear Function}

Let $f(\mathbf{x}) = \mathbf{a}^\top \mathbf{x}$ for a fixed vector $\mathbf{a} \in \mathbb{R}^d$.
Expand $f(\mathbf{x} + \epsilon \mathbf{v})$ and conclude that
\begin{align*}
    \nabla_{\mathbf{x}} \, \mathbf{a}^\top \mathbf{x} = \mathbf{a}.
\end{align*}
(You should find that the $o(\epsilon)$ term is exactly zero, because a linear function is its own first-order approximation.)

\subsection*{Part B: The Quadratic Form}

Let $f(\mathbf{x}) = \mathbf{x}^\top \mathbf{A} \mathbf{x}$ for a fixed square matrix $\mathbf{A} \in \mathbb{R}^{d \times d}$.
Expand $f(\mathbf{x} + \epsilon \mathbf{v})$, collect the terms linear in $\epsilon$, and show that
\begin{align*}
    \nabla_{\mathbf{x}} \, \mathbf{x}^\top \mathbf{A} \mathbf{x} = (\mathbf{A} + \mathbf{A}^\top) \mathbf{x}.
\end{align*}
(Hint: $\mathbf{v}^\top \mathbf{A} \mathbf{x}$ is a scalar, and a scalar equals its own transpose.)
Check the formula when $d = 1$ and $\mathbf{A} = a$, then write down the special case we will use constantly, where $\mathbf{A}$ is symmetric, and say in one line why it is the matrix version of $\frac{d}{dx} a x^2 = 2ax$.

\subsection*{Part C: Least Squares}

Let $f(\mathbf{x}) = \|\mathbf{A}\mathbf{x} - \mathbf{b}\|_2^2$ for a fixed matrix $\mathbf{A} \in \mathbb{R}^{n \times d}$ and vector $\mathbf{b} \in \mathbb{R}^n$.
First, expand the squared norm to show
\begin{align*}
    f(\mathbf{x}) = \mathbf{x}^\top (\mathbf{A}^\top \mathbf{A}) \mathbf{x} - 2 \mathbf{b}^\top \mathbf{A} \mathbf{x} + \|\mathbf{b}\|_2^2.
\end{align*}
Along the way, use the outer-product form of matrix multiplication from lecture to write
\begin{align*}
    \mathbf{A}^\top \mathbf{A} = \sum_{i=1}^n \mathbf{a}_i \mathbf{a}_i^\top,
\end{align*}
where $\mathbf{a}_i \in \mathbb{R}^d$ is the $i$th \emph{row} of $\mathbf{A}$ written as a column, so that $\mathbf{a}_i^\top$ is that row; check that the two sides have the same $(j,k)$ entry.
Then apply Parts A and B, noting that $\mathbf{A}^\top \mathbf{A}$ is symmetric, to conclude
\begin{align*}
    \nabla_{\mathbf{x}} \|\mathbf{A}\mathbf{x} - \mathbf{b}\|_2^2 = 2 \mathbf{A}^\top (\mathbf{A}\mathbf{x} - \mathbf{b}).
\end{align*}
Finally, show that for \emph{every} direction $\mathbf{v} \in \mathbb{R}^d$,
\begin{align*}
    \mathbf{v}^\top (\mathbf{A}^\top \mathbf{A}) \mathbf{v} = \|\mathbf{A}\mathbf{v}\|_2^2 \geq 0,
\end{align*}
and conclude in one sentence what that sign says about the \emph{shape} of $f$ along every direction, and why an algorithm that repeatedly steps against the gradient should be expected to reach the bottom.

\vspace{1em}
\noindent
\textbf{Where this goes next.}
Setting $2\mathbf{A}^\top(\mathbf{A}\mathbf{x} - \mathbf{b}) = \mathbf{0}$ gives the \emph{normal equations} of the Linear Models unit in one line, and the ``expand, collect the $\epsilon$ term'' recipe is how we will differentiate through entire neural networks.
The matrix $\mathbf{A}^\top\mathbf{A}$ also opens the course's spectral thread: its eigenvalues are the squared singular values of $\mathbf{A}$ (next lecture), and their ratio is the condition number that decides how fast gradient descent converges (Problem 8).

%\input{solutions/solution03}

\end{document}
