\documentclass{article}

\usepackage{amsmath,amssymb,amsthm}
\usepackage{csquotes}
\usepackage{dsfont}
\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{\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}

%%begin novalidate  % overleaf code check gives false positives here
\makeatletter
% \abs{} uses auto-sized bars, \abs*{} uses regular-sized ones
\newcommand{\abs}{\@ifstar{\@abs}{\@Abs}}
\newcommand{\@abs}[1]{\lvert #1 \rvert}
\newcommand{\@Abs}[1]{\left\lvert #1 \right\rvert}

\newcommand{\norm}{\@ifstar{\@norm}{\@Norm}}
\newcommand{\@norm}[1]{\lVert #1 \rVert}
\newcommand{\@Norm}[1]{\left\lVert #1 \right\rVert}

\newcommand{\ceil}{\@ifstar{\@ceil}{\@Ceil}}
\newcommand{\@ceil}[1]{\lceil #1 \rceil}
\newcommand{\@Ceil}[1]{\left\lceil #1 \right\rceil}

\newcommand{\floor}{\@ifstar{\@floor}{\@Floor}}
\newcommand{\@floor}[1]{\lfloor #1 \rfloor}
\newcommand{\@Floor}[1]{\left\lfloor #1 \right\rfloor}
\makeatother
%%end novalidate

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

\begin{document}
\begin{center}
\Large
CPSC 532D, Fall 2024: Assignment 1
\\
due Monday, 16 September 2024, \textbf{12:00 noon}
\end{center}

\vspace{2cm}


% You can do this with a partner if you'd like (there's a ``find a group'' post on Piazza).
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/24w1/#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.
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.

Submit your answers as a single PDF on Gradescope:
\href{https://canvas.ubc.ca/courses/156968/external_tools/46711?display=borderless}{here's the link}.
% Make sure to use the Gradescope group feature if you're working in a group.
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).

Please \textbf{put your name on the first page} as a backup, just in case.
If something goes wrong, you can also email your assignment to me directly (\texttt{dsuth@cs.ubc.ca}).



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\clearpage
\section{Loss functions \pts{40}} \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{5}
\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 intuitive argument.)
\begin{answer}\TODO\end{answer}



\item \pts{5}
\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 (where $\cY = \{0, 1\}$) with 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.01 & \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{Priors? In my frequentist analysis? \pts{10}}

Suppose we have a countable (maybe finite, maybe infinite) hypothesis set $\cH$,
and we assign some ``prior probability'' $p_h$ to each $h \in \cH$
such that each $p_h > 0$ and $\sum_{h \in \cH} p_h \le 1$.
Assume a loss bounded in $[a, b]$.

\textcolor{question}{Use Hoeffding's inequality to prove the ``Bayesian-ish'' bound
\[
    \Pr_{S \sim \dist^m}\left(
        \forall h \in \cH.\quad
        L_\dist(h) - L_S(h)
        \le (b - a) \sqrt{\frac{1}{2m} \left[ \log \frac{1}{p_h} + \log\frac1\delta \right] }
    \right) \ge 1 - \delta
.\]
}%
\hint{It'll be pretty similar to the analogous step in the proof from lecture 2!}

We could then use this to show a bound on ERM in the same way as always: by separately bounding the probability of $L_S(h^*)$ being very small, and adding the two together.

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\clearpage
\section{Optimistic rates \pts{10 challenge}}
\meta{Assignments in this course will generally have \emph{challenge questions}. These questions are harder than the other ones, and worth at most 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.}

In this problem, assume that $\ell$ is an arbitrary loss bounded in $[0, 1]$,
and $\cH$ is finite.

In the second lecture, we showed/will show \meta{(depending on when you're reading this\dots)}
the following bound on the statistical error of any ERM $\hat h_S$:
\[
    \Pr\left(
        L_\dist(\hat h_S) - \min_{h \in \cH} L_\dist(\cH)
        \le \sqrt{ \frac2m \log\frac{\abs\cH + 1}{\delta} }
    \,\right) \ge 1 - \delta
.\]
This $1/\sqrt m$ dependence is what's known as a ``slow rate.''
In some settings, you can show a ``fast rate'' with $1/m$ dependence.
(This gap is pretty big: if you observe 100 times as many samples,
a $1/m$ rate will reduce the error by a factor of 100,
while $1 / \sqrt m$ would only reduce by 10.)

In previous years, I actually first proved a fast rate for finite hypothesis classes
if you assume \emph{realizability}:
that there is some $h^* \in \cH$ with $L_\dist(h^*) = 0$.
In that case, you can show a $\frac1m \log \frac{\abs\cH}{\delta}$ gap.
(You can see the argument in Section 2.3.1 of the [SSBD] book, linked from the course site.)

One drawback of having this is that we have two totally separate analyses.
If we know the problem is realizable, we get the nice $1/m$ rate.
But as soon as $\min_{h \in \cH} L_\dist(h) > 0$, we immediately jump up to the much worse rate.

We're going to prove an ``optimistic'' bound,
one that smoothly interpolates between the two rates
depending on the value of $L^* = \min_{h \in \cH} L_\dist(h)$.
This is going to take some more powerful machinery,
and get a nastier bound with probably a worse constant,
but the rate will be what we want.

One way to do this is based on \emph{Bernstein's inequality}:
\begin{prop}[Bernstein, bounded variables] \label{prop:bernstein}
    Let $X_1, \dots, X_m$ be independent random variables with means $\mu_i \in \R$, variances $\sigma^2_i$, and almost surely bounded in $[a, b]$. Then
    \begin{equation} \label{eq:bern}
        \Pr\left( \frac{1}{m} \sum_{i=1}^m (X_i - \mu_i) \ge \eps \right)
        \le \exp\left( - \frac{m \eps^2}{2 \left( \frac 1 m \sum_{i=1}^m \sigma^2_i \right) + \frac{2}{3} (b - a) \eps } \right)
        \tag{Bernstein}
    .\end{equation}
\end{prop}


\begin{qlist}
\item \pts{4} \label{q:bern:loss-ub}
    Use \cref{prop:bernstein} to show that for a fixed $h$, it holds with probability at least $1 - \delta$ over the choice of $S \sim \dist^m$ that
    \begin{equation} \label{eq:bern-ub}
        L_S(h) \le L_\dist(h) + \frac{C_1 \log \frac1\delta}{m} + \sqrt{ \frac{C_2 \log\frac1\delta}{m} L_\dist(h) }
        \tag{*}
    .\end{equation}
    for some (simple) universal constants $C_1, C_2$; give values for those constants.

    Use this bound (don't prove it again) to show that with probability at least $1 - \delta$,
    \begin{equation} \label{eq:bern-lb}
        L_S(h) \ge L_\dist(h) - \frac{C_1 \log \frac1\delta}{m} - \sqrt{ \frac{C_2 \log\frac1\delta}{m} L_\dist(h) }
        \tag{**}
    .\end{equation}

    \meta{You don't need to do this part to do the next one; you can just write that in terms of $C_1$ and $C_2$.}

    \hint{This is \emph{not} an exact inverse of the Bernstein probability bound; we're being a little loose here to get a simpler form.}

    \hint{After setting everything up, you can massage it so that $\Pr\left(L_S(h) \ge L_\dist(h) + \eps\right) \le \delta$ if a certain quadratic function of $\eps$ is nonnegative. Make your middle school/high school Algebra 1 teacher proud.}

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

Now on to the bound.
Let $\hat h_S$ denote an ERM,
and let $h^* \in \argmin_{h \in \cH} L_\dist(h)$,
with loss $L^* = L_\dist(h^*)$.\footnote{A minimizer is guaranteed to exist, since $\cH$ is finite, but at least in my proof it doesn't actually matter that $h^*$ be minimal; you could plug any hypothesis you like into the bound.}

\begin{qlist}[resume]
\item \pts{6} Prove a bound on $L_\dist(\hat h_S)- L^*$ in terms of $L^*$, $\abs{\cH}$, and $m$ of the form
    \[
        L_\dist(\hat h_S)
        \le L^* + \bigO\left( \frac1m \log \frac{\abs{\cH} + 1}{\delta} + \sqrt{\frac{L^*}{m} \log \frac{\abs{\cH} + 1}{\delta}} \right)
    .\]
    For full credit, use explicit constants in your answer, not $\bigO$.

    You can assume that $\frac1m \log\frac{\abs\cH + 1}{\delta} = o(1)$,
    which as a reminder means that it has a limit of zero.

    \hint{In my solution, $\cH$ and $\delta$ only appear in the form $\log \frac{\abs{\cH} + 1}{\delta}$; the $1$ isn't some constant hidden by $\bigO$, it's just a $1$.}

    \hint{Recall that since $\hat h_S$ is an ERM, $L_S(\hat h_S) \le L_S(h^*)$.}

    \hint{After doing the things in the hints above, you'll probably get something of the form $L_\dist(\hat h_S) \le \beta \sqrt{L_\dist(\hat h_S)} + \gamma$, where $\beta$ and $\gamma$ depend on all the other parameters of the problem. Think about what that equation tells us about $L_\dist(\hat h_S)$, and make your middle school algebra teacher proud again.}

\begin{answer}\TODO\end{answer}
\end{qlist}
\end{document}
