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

\newif\iffirstq
\firstqfalse
\setlist[qlist,1]{%
    leftmargin=*,
    label=\textbf{\color{black}[\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{\pt}[1]{\textcolor{points}{[#1~point]}}

\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{\cB}{\mathcal{B}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cD}{\mathcal{D}}
\newcommand{\cE}{\mathcal{E}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cI}{\mathcal{I}}
\newcommand{\cJ}{\mathcal{J}}
\newcommand{\cK}{\mathcal{K}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cN}{\mathcal{N}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cQ}{\mathcal{Q}}
\newcommand{\cR}{\mathcal{R}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cU}{\mathcal{U}}
\newcommand{\cV}{\mathcal{V}}
\newcommand{\cW}{\mathcal{W}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cY}{\mathcal{Y}}
\newcommand{\cZ}{\mathcal{Z}}
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator*{\E}{\mathbb{E}}
\DeclareMathOperator{\ERM}{ERM}
\newcommand{\eps}{\varepsilon}
\newcommand{\indic}{\mathds{1}}
\newcommand{\Lip}{\mathrm{Lip}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\op}{\mathit{op}}
\newcommand{\R}{\mathbb{R}}
\DeclareMathOperator{\Rad}{Rad}
\newcommand{\SG}{\mathcal{SG}}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\spn}{span}
\newcommand{\tp}{^\mathsf{T}}
\DeclareMathOperator{\Tr}{Tr}
\newcommand{\ud}{\mathrm{d}}
\DeclareMathOperator{\Unif}{Unif}
\DeclareMathOperator{\VCdim}{VCdim}
\newcommand{\ZZ}{\mathbb{Z}}
\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

\numberwithin{equation}{section}
\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 2024: Assignment 3
\\
due Friday, October 25 at 11:59pm
\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/54329?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{Monotonicity and model selection \pts{20}}

\begin{qlist}
\item \pts{5} \label{q:vc-monotone}
Prove that if $\cH \subseteq \cH'$, then $\VCdim(\cH) \le \VCdim(\cH')$.

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

\item \pts{5} \label{q:rad-monotone}
Prove that if $\cH \subseteq \cH'$, then $\Rad(\cH\rvert_S) \le \Rad(\cH'\rvert_S)$.
\begin{answer}\TODO\end{answer}

\item \pts{5}
Comment on how we should expect \cref{q:vc-monotone,q:rad-monotone} to affect the generalization loss of running ERM in $\cH$ versus $\cH' \supseteq \cH$, that is, $L_\dist(\operatorname{ERM}_{\cH}(S))$ versus $L_\dist(\operatorname{ERM}_{\cH'}(S))$ for a fixed sample size $m$. What other factors are relevant to that comparison?
\begin{answer}\TODO\end{answer}


\item \pts{5}
For any $\cH$,
show that
\[
    \E_{S \sim \dist^m}[ L_S(\ERM_{\cH}(S)) ]
    \le \inf_{h \in \cH} L_\dist(h)
    \le \E_{S \sim \dist^m}[ L_\dist(\ERM_{\cH}(S)) ]
.\]

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




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\clearpage
\section{Threshold functions \pts{20}} \label{q:thresholds}

This question is about the class of threshold functions on $\R$:
\[
    \cH = \left\{
        x \mapsto \mathds 1(x \ge \theta)
        : \theta \in \R
    \right\}
.\]

We showed in class (notes section 6.4.1.1)
that $\VCdim(\cH) = 1$:
it can shatter a single point,
but it cannot shatter any set of size two (since it can't label the left point 1 and the right point 0).
\begin{qlist}

\item \label{q:thresh:sauer} \pts{5}
Use Sauer-Shelah (Lemma 6.12), and also the simpler Corollary 6.10, to give two upper bounds on the growth function $\Gamma_\cH(m)$.
\begin{answer}\TODO\end{answer}

\item \label{q:thresh:tau} \pts{5}
Directly derive the exact value of the growth function $\Pi_\cH$ from its definition.
How tight are the upper bounds from \cref{q:thresh:sauer}?
\begin{answer}\TODO\end{answer}

\item \label{q:thresh:rad-ub} \pts{5}
Plug the previous parts in to upper bound $\Rad(\cH\rvert_{S_x})$
for an $S$ containing $m$ distinct real numbers.
\meta{You should give multiple bounds here: one for each bound, and one for the exact value of the growth function.}
\begin{answer}\TODO\end{answer}

\item \label{q:thresh:asymp} \pts{5}
Give the asymptotic value of $\Rad(\cH \rvert_{S_x})$ for an $S_x$ containing $m$ distinct real numbers.
    \textcolor{black}{Your answer might look something like ``$\Rad(\cH \rvert_{S_x}) = 7m + \bigO(1)$,'' with a justification. To be clear, this means that $7m - a_n \le \Rad(\cH\rvert_{S_x}) \le 7m + a_n$ for some $a_m = \bigO(1)$.}
How does it compare to the bound from \cref{q:thresh:rad-ub}?

\hint{
    Imagine playing a (pretty boring) betting game where you bet \$1 whether a coin I'm flipping comes up heads or tails, with even odds.
    Since \href{http://www.stat.columbia.edu/~gelman/research/published/diceRev2.pdf}{all physical coin flips are unbiased},
    you have a 50-50 shot of getting it right.
    The distribution of how much money I owe you is known as a \emph{simple random walk}.
    Your expected winnings at any time $t$ are always 0 (it's the sum of a bunch of mean-zero variables).
    If we play for a while,
    and then you conveniently ``lose'' the records of what happened after some time $t$ that just so happens to be the best possible time for you to have forgotten,
    you'll probably be able to win some money:
    the expected \emph{maximum} value achieved at any point during a simple random walk of length $m$
    \href{https://arxiv.org/abs/cond-mat/0506195}{turns out to be}
    $\sqrt{\frac{2 m}{\pi}} - \frac12 + \bigO(m^{-\frac12})$.
    (This is from equations (4) and (7) of the linked paper.)
}

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\clearpage
\section{Rademacher complexity of deep networks \pts{50}}
We're now going to prove a Rademacher complexity bound for deep networks.
To do that,
we're going to build up our repertoire of Rademacher properties a bit first.

\begin{lemma} \label{thm:rad-union}
    Consider finitely many sets $V_i$
    such that for all $\bsigma \in \{-1, 1\}^m$,
    it holds that $\sup_{v \in V_i} v \cdot \bsigma \ge 0$;
    for instance, this holds if $0 \in V_i$,
    or if for all $v \in V_i$ we also have $-v \in V_i$.
    Then $\Rad(\cup_i V_i) \le \sum_i \Rad(V_i)$.
\end{lemma}

\begin{qlist}
\item \pts{10} Prove \cref{thm:rad-union}.
\begin{answer}\TODO\end{answer}
\end{qlist}


The \href{https://en.wikipedia.org/wiki/Convex_hull}{convex hull} of a set $V$
is the set of all convex combinations of points in $V$:
\[
    \conv(V) = \bigcup_{k \ge 1}
    \left\{ \sum_{i=1}^k \alpha_i v_i : \alpha_i \ge 0; \sum_{i=1}^k \alpha_i = 1; v_1, \dots, v_k \in V \right\}
.\]
\begin{lemma} \label{thm:rad-cvx}
    For any set $V$,
    $\Rad(\conv(V)) = \Rad(V)$.
\end{lemma}

\begin{qlist}[resume]
\item \pts{10} Prove \cref{thm:rad-cvx}.
\begin{answer}\TODO\end{answer}
\end{qlist}

\begin{lemma} \label{thm:rad-linmap}
    For any set $V$,
    $\Rad\left( \left\{ \sum_{i=1}^d w_i v_i : w_i \in \R, \sum_{i=1}^d \abs{w_i} \le B, v_i \in V \right\} \right) \le B \Rad(V \cup (-V))$.
\end{lemma}
\begin{qlist}[resume]
\item \pts{10} Prove \cref{thm:rad-linmap}.
\hint{You might want to apply \cref{thm:rad-union,thm:rad-cvx}.}
\begin{answer}\TODO\end{answer}
\end{qlist}

Now we're ready to
bound a class of multilayer perceptrons
(without bias terms because it makes things look a little cleaner -- in practice, you should use bias terms!).
Specifically,
\[
    \cH_D = \{ x \mapsto \sigma_D( W_D \sigma_{D-1}( \cdots \sigma_1(W_1 x) \cdots )) : W_1 \in \cW_1, \dots, W_D \in \cW_D \}
.\]
The $\sigma_i$ are $M_i$-Lipschitz elementwise activation functions
such that $\sigma_i(0) = 0$;
for example, $\operatorname{ReLU}(x) = [ \max( x_i, 0 ) ]$.
The $W_i$ are matrices 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 some arbitrary, fixed sequence.
The constraints are
\[ \cW_i = \left\{
    W \in \R^{d_i \times d_{i-1}}
    :
    \forall j \in [d_i], \,
    \sum_{k=1}^{d_{i-1}} \abs{W_{jk}} \le B_i
\right\} .\]

Since $\cH_D$ has a nice recursive form,
let's think about ``peeling off'' a layer at a time:
bounding $\Rad(\cH_D)$ in terms of $\Rad(\cH_{D-1})$.
To do this,
recall that since we're dealing with a real-valued network,
$W_D$ is of shape $1 \times d_{D-1}$,
and then notice that for $D \ge 2$,
\begin{equation}
    \cH_D \subseteq \left\{ x \mapsto \sigma_D\left( \sum_{j=1}^{d_{D-1}} (W_D)_j \, h_j(x) \right) : h_1, \dots, h_{d_{D-1}} \in \cH_{D-1}, W_D \in \cW_D \right\}
    \label{eq:mlp:recurse}
.\end{equation}

\begin{qlist}[resume]
    \item \pts{10}
    Prove that $\Rad(\cH_D \rvert_{S_x}) \le 2 M_D B_D \Rad(\cH_{D-1} \rvert_{S_x})$.

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

\end{qlist}

If we define $\cH_0$ in a way so that \eqref{eq:mlp:recurse} also makes sense for $D = 1$,
this leaves us with a bound of the form
$\Rad(\cH\rvert_{S_x}) \le \left( \prod_{i=1}^D (2 M_i B_i) \right) \Rad(\cH_0 \rvert_{S_x})$.

\begin{qlist}[resume]
    \item \pts{10}
    Give a definition of $\cH_0$ so that \eqref{eq:mlp:recurse} makes sense for $D = 1$.
    Bound $\Rad(\cH_0 \rvert_{S_x})$
    under the assumption that $\max_{x \in S_x} \norm{x}_p \le C$, for some $p \in [1, \infty]$ of your choice.
    \meta{Your bound should be $\bigO(1 / \sqrt{m})$, treating everything but $m$ as a constant.}
\begin{answer}\TODO\end{answer}
\end{qlist}

Armed with this bound,
we can show generalization bounds for scalar-output MLPs
in the same way as for anything else:
for example, we can immediately get an expectation bound on $L_\dist(\ERM_{\cH_D})$
for any Lipschitz loss,
and if the loss is also bounded
(either ``naturally'' or based on a bound of $\abs{h(x)}$ as for logistic regression)
then we can get a high-probability bound too.
\meta{(The bound won't be very good for very deep networks, though -- it's exponential in the depth! It's possible to improve on this somewhat with fancier techniques, but if the $\cW_i$ are all norm balls, a dependence on the product of those norms is unavoidable.)}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\clearpage
\section{Gaussian complexity \pts{10 challenge}}

We briefly mentioned the idea of Gaussian complexity in class:
\[
    \cG(V)
    = \E_{s_i \sim \cN(0, 1)} \sup_{v \in V} \frac{1}{m} \sum_{i=1}^m s_i v_i
    = \E_{s \sim \cN(0, I_m)} \sup_{v \in V} \frac{s \cdot v}{m}
.\]
We also mentioned that Rademacher and Gaussian complexity are close.
Let's prove that.
The following results will be helpful in doing that.

If $X \sim \cN(0, 1)$, then we say that $\abs X \sim \chi$.
(You may be more familiar with the $\chi^2$ distribution; this is its square root, with one degree of freedom.)

\begin{lemma} \label{lem:chi-mean}
    If $q \sim \chi$, $\E q = \sqrt{{2}/{\pi}}$.
    % If $X \sim \cN(0, 1)$, $\E \abs{X} = \sqrt{{2}/{\pi}}$.
\end{lemma}
\begingroup \color{black!50!white} \vspace*{-3ex}
\begin{proof} 
    Use
    $\displaystyle
        \E q
        = \int_{-\infty}^0 (-x) \frac{1}{\sqrt{2\pi}} e^{-\frac12 x^2} \ud x
        + \int_0^{\infty} x \frac{1}{\sqrt{2\pi}} e^{-\frac12 x^2} \ud x
        %= \frac{2}{\sqrt{2 \pi}} \int_0^\infty x e^{-\frac12 x^2} \ud x
        = \frac{2}{\sqrt{2 \pi}} \int_{-\infty}^0 \left(-x e^{-\frac12 x^2}\right) \ud x
    $.
    Noting that $\frac{\ud}{\ud x} \left(e^{-\frac12 x^2}\right) = -x e^{-\frac12 x^2}$,
    the integral is therefore $e^{-\frac12 0^2} - e^{-\frac12 (-\infty)^2} = 1 - 0 = 1$.
\end{proof}
\endgroup

It'll also help to write
$a \odot b$ for the elementwise product of two vectors,
$(a \odot b)_i = a_i b_i$.

\begin{qlist}
\item \pts{3 challenge} \label{q:gauss:e-rad}
    Prove that $\cG(V) = \E_{q \sim \chi^m} \Rad(q \odot V)$,
    where $q \odot V = \{ q \odot v : v \in V \}$.

    \meta{Here $\chi^m$ means a vector of $m$ independent $\chi$ variables;
    $q$ is the same as taking the elementwise absolute value of $s \sim \cN(0, I_m)$.}

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

\item \pts{3 challenge}
    Prove a bound of the form $\cG(V) \le f(m) \Rad(V)$,
    where $f(m)$ depends only on $m$.
    Specify an explicit closed form for $f(m)$.
    \begin{answer}\TODO\end{answer}

\item \pts{3 challenge}
    Prove that $\Rad(V) \le \sqrt{\frac\pi2} \cG(V)$.

    \hint{Try using Jensen's inequality and brushing up on \href{https://en.wikipedia.org/wiki/Convex_function\#Operations_that_preserve_convexity}{convex function properties}.}
    \begin{answer}\TODO\end{answer}

\item \pt{1 challenge}
    Give an example of a particular $V$ where the previous bound is tight,
    i.e.\ $\Rad(V) = \sqrt{\frac{\pi}{2}} \cG(V) > 0$.
    \begin{answer}\TODO\end{answer}
\end{qlist}


\end{document}
