\documentclass{article}

\usepackage{amsmath,amssymb,amsthm}
\usepackage{csquotes}
\usepackage{dsfont}
\usepackage{mathtools}
\usepackage{thmtools}
\usepackage{etoolbox}
\usepackage{enumitem}
\usepackage{fullpage}
\usepackage{parskip}
\usepackage{xcolor}
\usepackage{verbatim}

\usepackage[colorlinks,linkcolor=red!80!black]{hyperref}
\usepackage[noabbrev,capitalize]{cleveref}

\definecolor{question}{rgb}{0,0,1}
\crefname{section}{Question}{Questions}
\newlist{qlist}{enumerate}{1}
\setlist[qlist,1]{leftmargin=*, label=\textbf{(\thesection.\arabic*)}, ref={(\thesection.\arabic*)}}
\crefname{qlisti}{Question}{Questions}
\AtBeginEnvironment{qlist}{\color{question}}

\definecolor{answer}{rgb}{0,.5,0}
\newcommand{\ans}[1]{\par\textcolor{answer}{Answer: #1}}
\newenvironment{answer}{\par\begingroup\color{answer}Answer: }{\endgroup}

\definecolor{points}{rgb}{0.6,0.3,0}
\newcommand{\pts}[1]{\textcolor{points}{[#1~points]}}

\newcommand{\hint}[1]{\textcolor{black!60!white}{\emph{Hint: #1}}}
\newcommand{\meta}[1]{\textcolor{black!60!white}{\emph{#1}}}

\newcommand{\TODO}{\color{red}{TODO}}

\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator{\bigO}{\mathcal{O}}
\newcommand{\bX}{\mathbf{X}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cY}{\mathcal{Y}}
\newcommand{\cZ}{\mathcal{Z}}
\DeclareMathOperator*{\E}{\mathbb{E}}
\newcommand{\eps}{\varepsilon}
\newcommand{\indic}{\mathds{1}}
\newcommand{\op}{\mathit{op}}
\newcommand{\R}{\mathbb{R}}
\DeclareMathOperator{\spn}{span}
\newcommand{\tp}{^\mathsf{T}}
\DeclareMathOperator{\tr}{tr}
\newcommand{\dist}{\mathcal{D}}
\newcommand{\xdist}{\mathcal{D}_x}

% \abs{} uses regular-sized bars, \abs*{} uses auto-sized ones
\DeclarePairedDelimiter{\abs}{\lvert}{\rvert}
\DeclarePairedDelimiter{\norm}{\lVert}{\rVert}
\DeclarePairedDelimiterX{\inner}[2]{\langle}{\rangle}{#1,#2}

\declaretheorem[name=Theorem,numberwithin=section]{thm}
\declaretheorem[name=Proposition,sibling=thm]{prop}

\begin{document}
\begin{center}
\Large
CPSC 532D, Fall 2025: Assignment 1
\\
due Monday, 15 September 2025, \textbf{11:59 pm}
\end{center}

\vspace{2cm}


Do assignment 1 alone; future ones will allow partners.
\textbf{Read the website section on academic integrity}
\href{https://www.cs.ubc.ca/~dsuth/532D/25w1/#policies}{here}
for what you're allowed to do and not do;
in particular, cite your sources (including people you talked to!)
and don't use ChatGPT/etc for anything content-related.
If you're not sure if something is okay, ask.

Prepare your answers to these questions using \LaTeX;
hopefully you're reasonably familiar with it,
but if not, try using Overleaf and looking around for tutorials online.
Feel free to ask questions if you get stuck on things on Piazza
(but remove any details about the actual answers to the questions\dots
make a private post if that's tough).
If you prefer, the \texttt{.tex} source for this file is available on the course website,
and you can put your answers in
\verb|\begin{answ|\verb|er} My answer here... \end{answer}|
% that weird formatting so my answer-stripping script doesn't catch it :p
environments to make them stand out;
feel free to delete whatever boilerplate you want.
Or answer in a fresh document if you'd prefer.

Submit your answers as a single PDF on Gradescope:
\href{https://canvas.ubc.ca/courses/172832/external_tools/62337?display=borderless}{here's the link}.
You'll be prompted to mark where each question is in your PDF;
make sure you mark all relevant pages for each part (which saves us a surprising amount of grading time).

On the off chance something goes wrong,
you can also email your assignment to me directly (\texttt{dsuth@cs.ubc.ca}).



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\clearpage
\section{Loss functions \pts{50}} \label{q:losses}

As a reminder,
the general form of learning problems we'll usually work with in this course is as follows:
$\dist$ is some distribution over a space $\cZ$,
and $\ell : \cH \times \cZ \to \R$ is a loss function.

For example,
classification problems are often framed with
$\cZ = \cX \times \cY$,
with the zero-one loss function $\ell(h, (x, y)) = \mathds{1}(h(x) \ne y)$.
The true risk is $L_\dist(h) = \E_{z \sim \dist} \ell(h, z)$,
and the empirical risk is $L_S(h) = \frac{1}{m} \sum_{i=1}^m \ell(h, z_i)$
for a sample $S = (z_1, \dots, z_m) \sim \dist^m$, i.e.\ the $z_i$ are iid following $\dist$.

\begin{qlist}
\item \pts{5}
Show the empirical risk is an unbiased estimator of the true risk: $\E L_S(h) = L_\dist(h)$ for all $h \in \cH$.
\begin{answer}\TODO\end{answer}

\item \pts{5}
Show that the expected zero-one loss for $k$-way classification ($\cY = [k] = \{1, \dots, k\}$) is equal to one minus the expected accuracy (the portion of correct answers on samples from $\dist$).
\begin{answer}\TODO\end{answer}

\item \pts{10}
\textcolor{black}{For the canonical ImageNet Large Scale Visual Recognition Challenge, images are given with one of a thousand possible labels, and one major way of evaluating those models is the top-5 error rate: models can make 5 guesses at the label, and we count how often the correct label is not any of those 5 guesses.} Frame this in the language above: what kind of object does $h(x)$ output, and what does $\ell(h, (x, y))$ look like?
\begin{answer}\TODO\end{answer}

\item \pts{10}
\textcolor{black}{
\emph{Semantic segmentation} is a computer vision problem where we try to label each pixel of an image as belonging to one of $k$ classes (``tree,'' ``street,'' ``dog,'' etc.).
Let $S = ((x_1, y_1), \dots, (x_n, y_n))$ where $x_i$ are the given input images in, say, $\R^{h \times w \times 3}$, and $y_i \in [k]^{h \times w}$ are their corresponding pixel labels.\footnote{$[k]$ is semi-common notation for $\{1, 2, \dots, k\}$; thus $y_i$ is an $h \times w$ array of integers between $1$ and $k$.}
One typical evaluation metric is called mIoU (``mean intersection over union'').
One minus the mIOU (to make it a nonnegative ``loss'' to minimize) is measured on a test set as follows:
\[
    Q_S = 1 -
    \frac{1}{k} \sum_{c=1}^{k}
    \frac{\text{\# of pixels from all images in $S$ that are \emph{correctly} predicted as $c$}}
         {\text{\# of pixels from all images in $S$ that are predicted as $c$ and/or have true label $c$}}
.\]
}

Argue that this metric \emph{cannot} be expressed using the form of loss function above on the given $S$.
(A formal proof isn't necessary on this question, just a good convincing intuitive argument --
but a formal proof is one way to be very convincing.)
\begin{answer}\TODO\end{answer}



\item \pts{10}
\begingroup\color{black}
Principal component analysis (PCA) is a common technique that can try to find an underlying low-dimensional structure by a linear mapping to a low-dimensional space:
a data point $x \in \R^d$ is mapped to a latent code $z = W x \in \R^k$,
where $W \in \R^{k \times d}$ is a matrix with orthonormal rows ($W W^\top = I$) that we want to learn.
To reconstruct a point from its latent code $z$, we take $W^\top z$.
To find $W$, we minimize the squared reconstruction error on a training set:
\begin{equation} \label{eq:pca}
    \argmin_{W : W W^\top = I} \sum_{i=1}^m \norm{W^\top W x_i - x_i}^2
    \tag{PCA}
.\end{equation}
\endgroup
Frame PCA as an empirical risk minimization problem:
what are the data domain $\cZ$, the sample $S$, the hypothesis class $\cH$, and the loss function $\ell : \cH \times \cZ \to \R$ such that the set of ERMs is exactly the set of solutions to \eqref{eq:pca}?
\begin{answer}\TODO\end{answer}

\item \pts{10}
Frame the problem of fitting a Gaussian distribution to a set of independent scalar observations as loss minimization, like above:
what are the data domain $\cZ$, the sample $S$, the hypothesis class $\cH$, and the loss function $\ell : \cH \times \cZ \to \R$ such that the ERM agrees with the maximum likelihood estimate?
\textcolor{black}{You can assume that the maximum-likelihood Gaussian is non-degenerate, i.e.\ has strictly positive variance.}
\begin{answer}\TODO\end{answer}


\end{qlist}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\clearpage
\section{Bayes optimality \pts{40}}

A Bayes-optimal predictor is a predictor which achieves the lowest possible error for \emph{any} function, regardless of a choice of hypothesis class.\footnote{As usual in this course, I'm ignoring issues of measurability; this should all be formalizable by being appropriately careful and using ``disintegrations'' of probability measures, etc, but for the purpose of this question you can just ignore such issues.}

We'll consider losses of the form
$\ell(h, (x, y)) = l_y(h(x))$,
where $h : \cX \to \hat\cY$ and $l_y : \hat\cY \to \R$ for each $y \in \cY$.

A Bayes-optimal predictor has no pesky constraints on the form of function it's going to be,
so it can just give an arbitrary different prediction for each $x$.
Let $\mathcal F(x)$ denote the conditional distribution of $y$ for a given $x$ under $\dist$:
if $\dist$ is deterministic, this won't be a very interesting distribution (a point mass), but in general it might be more complicated.
You might find it helpful to also use $\xdist$ to denote the marginal distribution of $x$ under $\dist$.

\begin{qlist}
    \item \pts{10}
    Argue that if $h$ and $g$ are predictors such that for every $x$, $\E_{y \sim \mathcal F(x)} l_y(h(x)) \le \E_{y \sim \mathcal F(x)} l_y(g(x))$,
    then we necessarily have that $L_\dist(h) \le L_\dist(g)$.
    \begin{answer}\TODO\end{answer}
\end{qlist}

Thus, we can find a generic Bayes-optimal predictor according to
\[
    f_{\dist,l}(x) \in \argmin_{\hat y \in \hat\cY} \E_{y \sim \mathcal F(x)} l_y(\hat y)
.\]

\begin{qlist}[resume]
    \item \pts{10}
    Use the above formulation to argue that
    \[
        f_{\dist,\text{0-1}}(x) = \begin{cases}
            1 & \text{if } \Pr_{y \sim \mathcal F(x)}(y = 1) \ge \frac12 \\
            0 & \text{otherwise}
        \end{cases}
    \]
    is Bayes-optimal for binary classification problems with $\cY = \{0, 1\}$ under 0-1 loss $l_y(\hat y) = \indic(y \ne \hat y)$.
    \begin{answer}\TODO\end{answer}

    \item \pts{10}
    Use the above formulation to
    derive the Bayes-optimal predictor for a binary classification problem with the loss of an ``is this mushroom edible'' classifier:
    \[
        l_y(\hat y) = \begin{cases}
            0    & \text{if } \hat y = y \\
            0.001 & \text{if } \hat y = 0, \; y = 1 \\
            1    & \text{if } \hat y = 1, \; y = 0.
        \end{cases}
    \]
    \begin{answer}\TODO\end{answer}

    \item \pts{10}
    Use the above formulation to argue that
    \[
        f_{\dist,\text{sq}}(x) = \E_{y \sim \mathcal F(x)} y
    \]
    is Bayes-optimal for scalar regression problems with square loss $l_y(\hat y) = (\hat y - y)^2$.
    \begin{answer}\TODO\end{answer}
\end{qlist}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\clearpage
\section{Interpolation learning \pts{10 challenge}}
\meta{Assignments in this course will generally have \emph{challenge questions}. These questions are harder than the other ones, and worth a total of 10 points, so the effort:points ratio is \emph{much} higher. If you never touch the challenge questions but get everything else right, you can still get a 90 (the lowest possible A+) in the course. But I think they're interesting questions, so if you have the time to spend, you might learn something.}

\meta{(This one is not \emph{that} hard, especially the first parts! Try giving it a shot.)}

Consider a supervised learning setup,
where $\cH$ contains functions $\cX \to \cY$,
and the training data is a subset of $\cZ = \cX \times \cY$.
Let's restrict ourselves to losses of the form
$\ell(h, (x, y)) = l_y(h(x))$
and further assume that $l_y(\hat y) \ge 0$ for all $y, \hat y$.

Say that a nonnegative loss of this form is \emph{strictly proper}
if a sequence of predictions $(\hat y_t)$ satisfies $l_y(\hat y_t) \to 0$
if and only if $\hat y_t \to y$.
The squared loss $l_y(\hat y) = (y - \hat y)^2$ is strictly proper;
something weird like $l_y(\hat y) = \bigl( (y - 1) - \hat y \bigr)^2$ is not,
and neither is
the logistic loss $l_y(\hat y) = \log(1 + \exp( - y \hat y))$.

\begin{qlist}
\item \pts{2}
Show that the set of \emph{interpolators}, $G_S = \{ h \in \cH : L_S(h) = 0 \}$, is the same for any strictly proper nonnegative loss.
\begin{answer}\TODO\end{answer}

\item \pts{2}
What does the previous part imply about the set of possible ERMs in $\cH$
across multiple strictly proper nonnegative losses?
\begin{answer}\TODO\end{answer}

\item \pts{3}
\begingroup\color{black}
Let $\cX = \R^d$, $\cY = \R$, and $\cH = \{ h_w = (x \mapsto w \cdot x) : w \in \R^d \}$.
Let $\ell$ be a strictly proper nonnegative loss
such that for each $y \in \R$, $l_y : \R \to \R$ is differentiable.

Gather the $x_i$ from $S$ into $\bX \in \R^{m \times d}$
and the $y_i$ into $\by \in \R^m$.
Suppose that $m < d$ and that $\bX$ is of rank $m$,
implying that there are multiple $w$ for which $L_S(h_w) = 0$.

\meta{Thus, there are many possible ERM rules;
some of them might generalize well
and some might not.
As we'll explore in more depth later in the course,
it's then interesting to ask which solution a particular algorithm will find,
so that we can then ask whether we expect that algorithm to work well in general.}

Consider the following learning algorithm, a simple version of gradient descent:
\begin{itemize}
    \item Take as input a starting guess $w_0$, a learning rate $\eta > 0$, and a dataset $S = ((x_1, y_1), \dots, (x_m, y_m))$.
    \item For $t = 0, 1, \dots$:
    \begin{itemize}
        \item Let $
        w_{t+1}
        %= w_{t} - \eta \nabla_w L_S(h_{w_{t}})
        = w_{t} - \eta \; \frac{1}{m} \sum_{i=1}^m l_{y_i}'(w_{t} \cdot x_i) \, x_i$.
    \end{itemize}
\end{itemize}

We'll prove later in class that under some conditions on $S$, $l$, and $\eta$,
this algorithm converges:
$w_t \to w_\infty$, where $w_\infty$ is an ERM.
Assume that this happens in this situation.
\endgroup

Give a closed-form expression for $w_\infty$ in terms of $\bX$, $\by$, and $w_0$.
\meta{This can include things like matrix multiplication and inversion, but no looping, $\argmin$, etc.}

\hint{Consider which directions it is possible for each step to move in, regardless of the particular choice of loss; it will \emph{not} be the whole space $\R^d$. This will let you characterize a subset of possible values that the $w_t$ could conceivably take. Reconcile that characterization with the set of $w$ for which $L_S(h_w) = 0$; that will leave you with a matrix expression for $w_\infty$.}

\begin{answer}\TODO\end{answer}

\item \pts{3}
Prove that your answer to the previous part implies
$w_\infty = \argmin_{w : L_S(h_w) = 0} \norm{w - w_0}$:
we converge to the closest interpolator to where we started.

\hint{This part is fairly ``geometric,'' assuming you got the right answer in the previous part. There are many good approaches, but my preferred one is usually to write things in terms of the \emph{singular value decomposition}; there's a brief overview of this, if you're not super familiar, on the course website.}
\begin{answer}\TODO\end{answer}

\end{qlist}

\end{document}
