\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}
\newcommand{\bsigma}{\boldsymbol{\sigma}}
\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{\conv}{conv}
\DeclareMathOperator*{\E}{\mathbb{E}}
\newcommand{\eps}{\varepsilon}
\newcommand{\indic}{\mathds{1}}
\newcommand{\op}{\mathit{op}}
\newcommand{\R}{\mathbb{R}}
\DeclareMathOperator{\Rad}{Rad}
\newcommand{\SG}{\mathcal{SG}}
\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}
\declaretheorem[name=Lemma,sibling=thm]{lemma}

\begin{document}
\begin{center}
\Large
CPSC 532D, Fall 2023: Assignment 2
\\
due Wednesday, 11 October 2023, \textbf{11:59 pm}
\end{center}


\meta{%
Use \LaTeX, like usual.
}

You can do this with a partner if you'd like (there's a ``find a group'' post on Piazza).
If so, \textbf{do not just split the questions up};
if you hand in an assignment with your name on it,
you're pledging that you participated in and understand all of the solutions.
(If you work with a partner on some problems and then end up doing some of them separately,
hand in separate answers and put a note in each question saying whether you did it with a partner or not.)

\meta{%
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 outside your group about general strategies -- if so, just say who and for which questions --
but \textbf{not} to sit down and do the assignment together.
}

\meta{%
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.
\meta{%
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 a surprising amount of grading time).
}

Please \textbf{put your name(s) 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{Concentrating on concentric circles \pts{40}} \label{q:circles}

\meta{Based in part on SSBD exercise 3.3.}

In this problem, we'll show that a particular infinite hypothesis class can be PAC-learned with a ``direct'' proof.
\meta{It's pretty annoying to show general bounds on this problem with covering numbers,
but once we cover VC dimension we'll return see a more direct way to show (agnostic) PAC learning.}

Let $\cX = \R^2$, $\cY = \{0, 1\}$,
and let $\cH$ be the class of indicator functions for circles around the origin
-- that is, $\cH = \{ h_r : r \in \R_{\ge 0} \}$,
where $h_r(x) = \mathds{1}_{[ \norm x \le r]}$
(a function which is 1 if $\norm x \le r$, 0 otherwise).
Use 0-1 loss.

For a given sample $S$,
let $r_S = \max_{i : y_i = 1} \norm{x_i}$,
and use $\hat h_S$ to denote $h_{r_S}$,
the indicator function of a circle with radius $r_S$,
the tightest circle containing all of the positive training points.

To start with, let's assume \emph{realizability}:
that there is an $h^* \in \cH$ such that $L_\dist(h^*) = 0$.

\begin{qlist}
\item \pts{5}
Show that $\hat h_S$ is an empirical risk minimizer for the hypothesis class $\cH$.

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

\item \pts{20} \label{q:circles:pac}
Prove that $\hat h_S$ PAC-learns this $\cH$,
with sample complexity $\frac1\eps \log\frac1\delta$.

\hint{Three steps: first, what makes a hypothesis have high error in this setting? Next, what would $S$ have to look like in order to get one of those ``bad'' hypotheses? Last, how likely is it to see an $S$ like that?}

\hint{A frequently useful inequality is that $1 - a \le \exp(- a)$.}

\hint{If you're stuck and want to see something similar-ish (but a little more complicated), check out Example 2.4 of MRT, which is also Exercise 2.3 of SSBD.}

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

Now let's make things a little harder on our learner,
by adding random noise.
Rather than perfect realizability,
let $\dist$ be such that
$\Pr(y = 1 \mid x) = \begin{cases}
    1 - \eta & \text{if } h^*(x) = 1 \\
    \eta     & \text{if } h^*(x) = 0
\end{cases}$
for some $h^* \in \cH$:
that is, labels are randomly flipped with probability $\eta \in (0, \tfrac12)$.
The learner knows the value of $\eta$, but not which points have been flipped.


\begin{qlist}[resume]
\item \pts{5}
Is $\hat h_S$ as described above still an ERM?
\begin{answer}\TODO\end{answer}

\item \pts{10}
\begingroup \color{black}
Ambitious Ambrose claims to have proven the following:
\begin{displayquote}
    For any $\eps, \delta \in (0, 1)$ and $0 \le \eta < \frac12$,
    there is a function $m(\eta, \eps, \delta)$ such that,
    for any $m \ge m(\eta, \eps, \delta)$ and any $\dist$ of the form above,
    \[ \Pr_{S \sim \dist^m}(L_\dist(\hat h_S) > \eta + \eps) \le \delta .\]
\end{displayquote}
This is followed by an unreadably long computer-assisted proof using both category theory and complicated partial differential equations. Without reading that proof,
\endgroup
argue that Ambrose must be wrong: no such function $m(\eta, \eps, \delta)$ can exist.

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


\clearpage
\section{Sums, means, and maxes of sub-Gaussians \pts{50}}
In this question, we're going to explore sub-Gaussians and different versions of Hoeffding's some more.

A reminder that you may want to refer back to \href{https://www.cs.ubc.ca/~dsuth/532D/23w1/notes/3-concentration.pdf}{the lecture notes}.

\begin{qlist}

\item \label{q:sg:sum-dep-sqrt} \pts{10}
    Let $X_1 \in \SG(\sigma_1)$ and $X_2 \in \SG(\sigma_2)$; \textbf{do not} assume independence. 
    Show that $X_1 + X_2$ is $\SG(\sqrt{2} \sqrt{\sigma_1^2 + \sigma_2^2})$.

    \hint{One form of the ever-useful Cauchy-Schwarz inequality is that $\E[X Y] \le \sqrt{\E[X^2] \E[Y^2]}$, even if $X$ and $Y$ are dependent.}

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

\item \label{q:sg:sum-dep} \pts{15}
    Let $X_1 \in \SG(\sigma_1)$ and $X_2 \in \SG(\sigma_2)$; \textbf{do not} assume independence. 
    Show that $X_1 + X_2$ is $\SG(\sigma_1 + \sigma_2)$.

    \hint{One way is to use H\"older's inequality: $\E[X Y] \le \E[X^p]^{1/p} \E[Y^q]^{1/q}$ for all $p, q \in [1, \infty]$ with $1/p + 1/q = 1$, i.e.\ $q = p / (p - 1)$. Do this for a general $p$, see what you get, then find the optimal $p$.}

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

\item \pts{10}
    \textcolor{black}{
    Let $X_1, \dots, X_m$ each be $\SG(\sigma)$ with mean $\mu$,
    but do \emph{not} assume independence.}
    Construct a high-probability bound on their mean,
    \textcolor{black}{
    $\Pr\left( \frac1m \sum_{i=1}^m X_i > \mu + \text{something} \right) \le \delta$,
    using either \cref{q:sg:sum-dep-sqrt} or \ref{q:sg:sum-dep}
    rather than the notes' Proposition 6.}
    How much worse is what you just got than (Hoeffding') from the notes if the variables are actually independent?
    Is your result tight?

    \hint{One of these results is \emph{much} easier to use than the other one.}

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

\item \pts{15}
    \meta{
    So far, we've only looked at means of a bunch of random variables.
    But for uniform convergence, we care about the \emph{worst-case} behaviour of errors.
    We're going to (or have already, depending on when you're reading this\dots{}) use the following result in a key way in class.
    }

    Let $X_1, \dots, X_m$ be zero-mean random variables that are each $\SG(\sigma)$;
    \textbf{do not} assume independence.\footnote{As far as I know, independence actually wouldn't help here.}
    Prove that
    \[
        \E\left[ \max_{i=1,\dots,m} X_i \right] \le \sigma \sqrt{2 \log(m)}
    .\]

    \hint{Bound $\exp(\lambda \E \max_i X_i)$ in terms of something that only depends on $m$, $\sigma$, and $\lambda$, by rearranging into a form that lets you plug in the definition of sub-Gaussianity. Then turn that into a bound on $\E \max_i X_i$ in terms of $m$, $\sigma$, and $\lambda$. Then optimize $\lambda$ in that bound to get something only depending on $m$ and $\sigma$.}

    \hint{By Jensen's inequality, $\exp(\E Y) \le \E \exp(Y)$.}

    \hint{One way to upper-bound the max of a bunch of nonnegative numbers is by their sum.\footnote{Although this might seem really loose, if the max is a lot bigger than the second-biggest number -- e.g.\ because they're on an exponential scale -- it's not too bad.}}

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

\clearpage
\section{Deep networks \pts{10 challenge}}
Consider a hypothesis class of deep networks of depth $D$, with inputs in $\R^d$:
\[
    \cH = \{ x \mapsto \sigma_D(W_D \sigma_{D-1}(\cdots \sigma_1(W_1 x)\cdots)) : W_1 \in \mathcal W_1, \dots, W_D \in \mathcal W_D \}
,\]
where the $\sigma_i$ are $r$-Lipschitz elementwise activation functions with $\sigma_i(0) = 0$.
That is, $\sigma_i(v) = ( \sigma_i(v_j) )_{j=1}^{\dim v}$,
where on the right-hand side $\sigma_i$ is taking a scalar argument.
The canonical example for $\sigma_i$ is $\operatorname{ReLU}(x) = \max(0, x)$.

Here the weight matrices $W_i$ are of shape $d_i \times d_{i-1}$,
where the input dimension is $d_0 = d$,
the output dimension is $d_D = 1$,
and the in-between dimensions are arbitrary.

The constraints $W_i \in \mathcal W_i$ are intentionally left unspecified;
you'll have to choose it in your proof.
Don't choose a ``trivial'' constraint like $\mathcal W_i = \{ 0 \}$;
let's say at least that $\mathcal W_i$ must have nonzero volume in $\R^{d_i \times d_{i-1}}$.
It should probably something like
a bound on the Frobenius norm of each $W_i$,
or on $\norm{w}_{4}^{6i+12}$ for each column $w$ of $W_i$,
or something like that.
(Most likely, you'll want to make the constraint the same for each layer.)

You can make a similar ``reasonable'' assumption on $\dist$.
Assuming $\norm x \le C$ is reasonable;
assuming $x$ is almost surely constant is not.
At a minimum, again, the support of $x$ should have nonzero volume in $\R^d$.
Assuming realizability is reasonable (if you'd like);
assuming $y = 0$ is not.

Choose a \emph{specific} loss function $\ell$.
Zero-one, logistic, and $l(\hat y, y) = \abs{\hat y - y}^p$ for any $p \in [1, \infty)$ are all reasonable;
if you'd like to use something else, that's potentially okay,
just justify it as ``reasonable.''

Make all of these assumptions extremely clear in your answer.

\textcolor{question}{Prove a bound on $L_\dist(\hat h_S)$ for the ERM $\hat h_S$} under the conditions you assumed.
It can be either an expectation or a high-probability bound,
but the excess error should go to zero as $m \to \infty$ with other parameters fixed.

\begingroup\color{black!60!white}\itshape
Reminder: don't just look up and ape an existing bound; prove it yourself based on the class material.

Hint: you may want to tackle this with covering numbers, or with Rademacher complexity (to be covered starting in lecture 5); I think they're about equal amounts of work here, but (like usual with ``basic'' covering arguments) the Rademacher result is somewhat better. In either case, you'll probably want to do induction on the layers.

~

If you're using covering numbers, you can use the following result without proof:

\begin{prop} \label{prop:banach-cover}
Let $\mathbb F$ be a \href{https://en.wikipedia.org/wiki/Banach_space}{Banach space}.
The size of a minimal $\eta$-cover of the radius-$R$ ball in $\mathbb F$,
$\{ f \in \mathbb F : \norm f_{\mathbb F} \le R \}$, 
with respect to the metric $\norm{f - f}_{\mathbb F}$,
satisfies
$N_{\mathbb F}(R, \eta) \le (4 R / \eta)^{\dim \mathbb F}$.
\end{prop}

Letting $\mathbb F$ be $\mathbb R^d$, you get a slightly worse version of the result proved in \href{https://www.cs.ubc.ca/~dsuth/532D/23w1/notes/4-pac-covering.pdf}{our covering number notes}. But maybe you could define a different $\mathbb F$ so that $\ell(h, z)$ is Lipschitz with respect to that metric\dots.
(You don't need to explicitly prove that $\mathbb F$ is complete, if it's clear that it's a vector space, the norm you define is clearly a norm, and it seems reasonable that the space would be complete.)

~

If you're using Rademacher complexity, please prove any properties you use that aren't in 
\href{https://www.cs.ubc.ca/~dsuth/532D/23w1/notes/5-rademacher.pdf}{the notes}.
But you might find it useful to prove these properties:
\begin{itemize}
\item $\Rad(\conv(V)) = \Rad(V)$, where $\conv(V)$ is the convex hull of $V$, $\{ \sum_{i=1}^{\abs V} \alpha_i v_i : \alpha_i \ge 0, \sum_i \alpha_i = 1 \}$.
\item Let $V_i$ be such that $\forall \bsigma \in \{-1, 1\}^m,\, \sup_{v \in V_i} v \cdot \bsigma \ge 0$; for instance, this is true if $0 \in V_i$, or if $\forall v \in V_i, \, -v \in V_i$. Then $\Rad\left(\cup_i V_i\right) \le \sum_i \Rad(V_i)$.
\end{itemize}
(If you're not sure how to prove them but use them in your result, you'll get only a small point penalty.)

\endgroup
\clearpage

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