\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 regular-sized bars, \abs*{} uses auto-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}{\@norm}}
\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 2023: Assignment 1
\\
due Monday, 18 September 2023, \textbf{12:00 noon}
\end{center}


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 if so;
feel free to delete whatever boilerplate you want.
Or answer in a fresh document.

% 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.
If you look stuff up anywhere other than in SSBD or MRT,
\textbf{cite your sources}:
just say in the answer to that question where you looked.
If you ask anyone else for help, \textbf{cite that too}.
Please do not look at solution manuals / search for people proving the things we're trying to prove / etc.
Also, please do \emph{not} ask ChatGPT or similar models.
It's okay to talk to others in the class about general strategies -- if so, just say who and for which questions --
but \textbf{not} to sit down and do the assignment together.

Submit your answers as a single PDF on Gradescope:
\href{https://canvas.ubc.ca/courses/123461/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 save 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{55}} \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_n) \sim \dist^m$.%
\footnote{The notation $\dist^m$ here refers to a \emph{product distribution}:
a distribution which gives $m$ independent and identically-distributed samples from $\dist$.}

\begin{qlist}
\item \pts{5}
Show that, for any given $h \in \cH$, $L_S$ is unbiased: $\E L_S(h) = L_\dist(h)$.
\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 accuracy: models can make 5 guesses at the label, and we count how often the correct label is one 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}$ 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 a nicer ``loss'') 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$ predicted as $c$ and/or with 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{10}
\begingroup\color{black}
Recall the 1-nearest neighbour classifier:
when trained on $S = ((x_1, y_1), \dots, (x_m, y_m))$,
the learned predictor $\hat h_S$
finds $\hat i \in \argmin_{i \in [m]} \norm{x - x_i}$
and then returns as its prediction $y_{\hat i}$.
\endgroup
Can you write this algorithm as ERM?
If so, give the loss function and hypothesis class and show it's an ERM;
if not, argue why not.
\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{5}
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?
\begin{answer}\TODO\end{answer}


\end{qlist}



\clearpage
\section{Bayes optimality \pts{35}}

A Bayes-optimal predictor is a predictor which achieves the lowest possible error for any function, regardless of a choice of hypothesis class or anything like that.\footnote{As usual in this course, I'm ignoring issues of measurability and so on; 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 loss functions of the form
$\ell(h, (x, y)) = l(h(x), y)$,
where $h : \cX \to \hat\cY$ and $l : \hat\cY \times \cY \to \R$.%
\footnote{This is often how loss functions are defined in the first place;
there are a few cases in the course where the more general $\ell$ form is more convenient (including in parts of \cref{q:losses}),
but for this question, the $l$ form is a little easier.}
(We often have $\hat\cY = \cY$, as in binary classification, but not necessarily, as you may have seen in the previous question.)

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.

\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(h(x), y) \le \E_{y \sim \mathcal F(x)} l(g(x), y)$,
    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(\hat y, y)
.\]

\begin{qlist}[resume]
    \item \pts{5}
    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 0-1 loss.
    \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(\hat y, 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 squared loss $l(\hat y, y) = (\hat y - y)^2$.
    \begin{answer}\TODO\end{answer}
\end{qlist}


\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 far worse. 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 ERM:
\[
    \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,
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.}


\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.}

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