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

\newlist{qlist}{enumerate}{1}
\setlist[qlist,1]{leftmargin=*, label=\textbf{(\alph*)}, ref={(\alph*)}}
\crefname{qlisti}{part}{parts}
\AtBeginEnvironment{qlist}{\color{blue}}

\crefname{section}{Question}{Questions}

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

\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator{\bigO}{\mathcal{O}}
\newcommand{\bsigma}{\boldsymbol{\sigma}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cY}{\mathcal{Y}}
\newcommand{\cZ}{\mathcal{Z}}
\newcommand{\dist}{\mathcal{D}}
\DeclareMathOperator{\E}{\mathbb{E}}
\newcommand{\eps}{\varepsilon}
\newcommand{\op}{\mathit{op}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\SG}{\mathcal{SG}}
\DeclareMathOperator{\spn}{span}
\newcommand{\tp}{^\mathsf{T}}
\DeclareMathOperator{\tr}{tr}
\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=Theorem]{thm}
\crefname{thm}{Theorem}{Theorems}
\declaretheorem[name=Proposition,sibling=thm]{prop}
\crefname{prop}{Proposition}{Propositions}
\declaretheorem[name=Definition,sibling=thm]{defn}
\crefname{defn}{Definition}{Definitions}
%\numberwithin{equation}{section}

\begin{document}
\begin{center}
\Large
CPSC 532D, Fall 2022: Assignment 2
\\
due Wednesday, 12 October 2022, \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),
but please \textbf{make sure you understand everything you're submitting} --
don't just split an assignment in half.
If you do parts of the assignment with a partner and parts separately,
submit separate solutions, and say in each part you did together who you did it with.

If you look stuff up anywhere other than in \textbf{SSBD, MRT, Telgarsky, or Wainwright},
\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.

Submit your answers as a single PDF on Gradescope:
link and login instructions on \href{https://canvas.ubc.ca/courses/101911}{the Canvas site},
which you should now be able to get to even if you're not yet officially enrolled yet.
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 a surprising amount of grading time).

Please \textbf{put your names 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*{Some notes on concentration inequalities}
Here are some definitions and results from class which may be useful on this assignment.

\begin{defn}
    A random variable $X$ with mean $\mu = \E[X]$ is called \emph{sub-Gaussian with variance parameter $\sigma \ge 0$}, written $X \in \SG(\sigma)$, if $\E[ e^{\lambda (X - \mu)} ] \le e^{\frac12 \lambda^2 \sigma^2}$ for all $\lambda \in \R$.
\end{defn}
We motivated this definition by noting that a Gaussian $\mathcal N(\mu, \sigma^2)$ is $\SG(\sigma)$.

Notice that if $\sigma_1 < \sigma_2$, then anything that's $\SG(\sigma_1)$ is also $\SG(\sigma_2)$.

\begin{prop}[Hoeffding's lemma]
    A real-valued random variable bounded in $[a, b]$
    is $\SG\left( \frac{b - a}{2} \right)$.
\end{prop}

\begin{prop} \label{prop:sg-ind-sum}
    If $X_1 \in \SG(\sigma_1)$ and $X_2 \in \SG(\sigma_2)$ are independent,
    $X_1 + X_2 \in \SG(\sqrt{\sigma_1^2 + \sigma_2^2})$.
\end{prop}
\begin{proof}
    \hfill $ \displaystyle
        \E[e^{\lambda (X_1 + X_2 - \E[X_1 + X_2])}]
        = \E[e^{\lambda (X_1 - \E[X_1])}] \E[e^{\lambda (X_2 - \E[X_2])}]
        \le e^{\frac12 \lambda^2 \sigma_1^2} \, e^{\frac12 \lambda^2 \sigma_2^2}
        = e^{\frac12 \lambda^2 \left(\sqrt{\sigma_1^2 + \sigma_2^2}\right)^2}
    .$\hfill
\end{proof}

\begin{prop} \label{prop:sg-scale}
    If $X \in \SG(\sigma)$, then $a X \in \SG(\abs{a} \sigma)$ for any $a \in \R$.
\end{prop}
\begin{proof}
    \hfill $\displaystyle
        \E[e^{\lambda (a X - \E[a X])}]
        = \E[e^{(a \lambda) (X - \E X)}]
        \le e^{\frac12 (a \lambda)^2 \sigma^2}
        = e^{\frac12 \lambda^2 (\abs{a} \sigma)^2}
    .$\hfill
\end{proof}

\begin{prop}[Markov]
    If $X$ is a nonnegative-valued random variable,
    $\Pr(X \ge t) \le \tfrac1t \E X$.
\end{prop}
\begin{proof}
    Take expectations of both sides of $t \mathds{1}(X \ge t) \le X$.
\end{proof}


\begin{prop}[Chernoff, sub-Gaussians] \label{prop:sg-chernoff}
    If $X \in \SG(\sigma)$, then
    $
        \Pr(X \ge \E X + t) \le \exp\left( - \frac{t^2}{2 \sigma^2} \right)
    $ for $t \ge 0$.
\end{prop}
\begin{proof}
    Note that
    $\Pr(X \ge \E X + t) = \Pr(\exp(\lambda (X - \E X)) \ge \exp(\lambda t))$ for any $\lambda \in \R$.
    Applying Markov's inequality gives an upper bound of $\exp(-\lambda t) \E \exp(\lambda(X - \E X)) \le \exp(\tfrac12 \lambda^2 \sigma^2 - \lambda t)$.
    Plug in $\lambda = t / \sigma^2$.
\end{proof}

Since $-X$ is also $\SG(\sigma)$ by \cref{prop:sg-scale},
the same bound holds for a lower deviation $\Pr(X \le \E X - t)$.
A union bound then immediately gives
$\Pr(\abs{X - \mu} \ge t) \le 2\exp\left( - \frac{t^2}{2 \sigma^2} \right)$.

\begin{prop}[Hoeffding] \label{prop:hoeffding}
    If $X_1, \dots, X_n$ are independent and each $\SG(\sigma_i)$ with mean $\mu_i$,
    for all $\eps \ge 0$
    \[
        \Pr\left( \frac1n \sum_{i=1}^n X_i \ge \frac1n \sum_{i=1}^n \mu_i + \eps \right)
        \le \exp\left( - \frac{n^2 \eps^2}{2 \sum_{i=1}^n \sigma_i^2} \right)
    .\]
\end{prop}
\begin{proof}
    By \cref{prop:sg-ind-sum,prop:sg-scale},
    $\frac1n \sum_{i=1}^n X_i \in \SG\left( \frac{1}{n} \sqrt{ \sum_{i=1}^n \sigma_i^2 } \right)$.
    Then apply \cref{prop:sg-chernoff}.
\end{proof}
If the $X_i$ have the same mean $\mu_i = \mu$ and parameter $\sigma_i = \sigma$,
this becomes
\begin{equation} \label{eq:hoeff-iid}
    \Pr\left( \frac1n \sum_{i=1}^n X_i \ge \mu + \eps \right)
    \le \exp\left( - \frac{n \eps^2}{2 \sigma^2} \right)
    \tag{Hoeffding}
,\end{equation}
which can also be stated as that, with probability at least $1 - \delta$,
\begin{equation} \label{eq:hoeff-iid-ub}
    \frac1n \sum_{i=1}^n X_i \le \mu + \sigma \sqrt{\frac{2}{n} \log \frac1\delta}
    \tag{Hoeffding'}
.\end{equation}


\clearpage
\section{A question that's probably more or less about PAC learning \pts{30}}

\begin{qlist}

\item \pts{10}
    Show that if $A$ is an algorithm that agnostically PAC learns a hypothesis class $\cH$,
    it's also a (realizable) PAC learner for $\cH$.
\begin{answer}\textcolor{red}{TODO}\end{answer}

\item \pts{10}
    \textcolor{black}{Let $A$ be a learning algorithm, $\dist$ a probability distribution, and let $L$ denote the random variable $L_\dist(A(S))$ for some loss function bounded in $[0, 1]$.}
    Prove that the following two statements are equivalent:
    \begin{enumerate}
        \item For every $\eps, \delta > 0$, there is some $n(\eps, \delta)$ such that for all $n \ge n(\eps, \delta)$, $\Pr_{S \sim \dist^n}( L > \eps ) < \delta$. \meta{This is the kind of guarantee we've been using for PAC learning.}
        \item $\lim_{n \to \infty} \E_{S \sim \dist^n} L = 0$. \meta{The expected loss goes to zero asymptotically.}
    \end{enumerate}
\begin{answer}\textcolor{red}{TODO}\end{answer}

\item \pts{10}
    Say we have a \emph{countable} hypothesis set $\cH$,
    and we have a distribution $p$ assigning probability mass $p(h)$ to each hypothesis $h$ in $\cH$.
    \textcolor{red}{Assume a loss bounded in $[0, 1]$.}
    Use Hoeffding's inequality to prove that the ``Bayesian-ish'' bound
    \[
        L_\dist(h) \le L_S(h) + \sqrt{\frac{1}{2 n} \left[ \log \frac{1}{p(h)} + \log \frac1\delta \right]}
    \]
    holds uniformly over all $h \in \cH$ with probability at least $1 - \delta$.
    \meta{Because this is uniform, we could then plug it in to get a particular bound on our generalization error after training based on $L_S(\hat h)$ and $p(\hat h)$.}

    \hint{In the finite case, we effectively allotted an error probability of $\delta / \abs{\cH}$ to each hypothesis having high error and applied \eqref{eq:hoeff-iid-ub}. Do something slightly different here.}

    \begin{answer}\textcolor{red}{TODO}\end{answer}


\end{qlist}


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

\begin{qlist}

\item \label{q:sg:sum-dep-sqrt} \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(\sqrt{2} \sqrt{\sigma_1^2 + \sigma_2^2})$.

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

    \begin{answer}\textcolor{red}{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}\textcolor{red}{TODO}\end{answer}

\item \pts{15}
    Try constructing a version of \eqref{eq:hoeff-iid} that doesn't assume independence based on applying \cref{q:sg:sum-dep-sqrt} or \ref{q:sg:sum-dep} rather than \cref{prop:sg-ind-sum}.
    How much worse is what you just got than \eqref{eq:hoeff-iid}?
    How does what you got compare to the best such inequality you could possibly hope to get, with any approach?

    \begin{answer}\textcolor{red}{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_n$ 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,n} X_i \right] \le \sigma \sqrt{2 \log(n)}
    .\]

    \hint{Bound $\exp(\lambda \E \max_i X_i)$ in terms of something that only depends on $n$, $\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 $n$, $\sigma$, and $\lambda$. Then optimize $\lambda$ in that bound to get something only depending on $n$ 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}\textcolor{red}{TODO}\end{answer}

\end{qlist}





\clearpage
\section{Challenge problem: Bernstein-based rates \pts{10}}
\meta{I'm going to start introducing ``challenge problems'' on the homeworks.
These will be notably more difficult than the other problems,
but worth at most 10 points,
so that if you just totally ignore these but do well on everything else,
you can still absolutely get an A in the course (final average 85-89\%).
To have a good chance at an A+, however, you'll have to do at least some of the challenge problems.
(I might adjust this scheme over the course of the term if it seems necessary.)}

This problem will consider arbitrary loss functions bounded in $[0, 1]$,
and finite hypothesis classes $\cH$.

Recall in class that we showed two different kinds of rates for ERM:
given $n$ samples, with probability at least $1 - \delta$,
ERM achieves excess error, $L_\dist(\hat h_S) - \inf_{h \in \cH} L_\dist(\cH)$, of
\begin{itemize}
    \item $\frac{1}{n} \left[ \log \abs{\cH} + \log \frac1\delta \right]$ in the realizable setting, where there's an $h^*$ with $L_S(h^*) = 0$
    \item $\sqrt{\frac{2}{n} \left[ \log \abs{\cH} + \log \frac2\delta \right]}$ in the agnostic setting.
\end{itemize}
This difference between $1/n$ and $1/\sqrt{n}$ is a big deal (often called a ``fast rate'' versus a ``slow rate''),
and it's pretty annoying that we have to decide in advance whether we think the problem is realizable,
and if it's ``almost realizable'' then we don't get any ``partial credit.''
In this problem, you'll prove a version of this bound that unifies the two rates.

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_n$ be independent random variables with means $\mu_i \in \R$, variances $v_i$\footnote{We're not calling this $\sigma_i^2$ to avoid confusion with the sub-Gaussian parameter, which this is emphatically not; Bernstein's inequality is more closely connected to something called sub-exponential variables.}, and almost surely bounded in $[a, b]$. Then
    \begin{equation} \label{eq:bern}
        \Pr\left( \frac{1}{n} \sum_{i=1}^n (X_i - \mu_i) \ge \eps \right)
        \le \exp\left( - \frac{n \eps^2}{2 \left( \frac 1 n \sum_{i=1}^n v_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^n$ that
    \begin{equation} \label{eq:bern-ub}
        L_S(h) \le L_\dist(h) + \frac{C_1 \log \frac1\delta}{n} + \sqrt{ \frac{C_2 \log\frac1\delta}{n} L_\dist(h) }
        \tag{*}
    .\end{equation}
    for some (simple) universal constants $C_1, C_2$; give values for those constants.

    Also show that, separately, it holds with probability at least $1 - \delta$ that
    \begin{equation} \label{eq:bern-lb}
        L_S(h) \ge L_\dist(h) - \frac{C_1 \log \frac1\delta}{n} - \sqrt{ \frac{C_2 \log\frac1\delta}{n} L_\dist(h) }
        \tag{**}
    .\end{equation}
    \meta{The same argument can show both; you don't need to write it all out twice, but we'll need both directions.}

    \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, the way that \eqref{eq:hoeff-iid-ub} is for \eqref{eq:hoeff-iid}; we're being a little loose here to get a simpler form.}


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

Now on to the bound.
Let $\hat h_S$ denote an ERM,
and let $h^*$ be an optimal hypothesis from a finite $\cH$,
$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 $n$ of the form
    \[
        L_\dist(\hat h_S)
        \le L^* + \bigO\left( \frac1n \log \frac{\abs{\cH} + 1}{\delta} + \sqrt{\frac{L^*}{n} \log \frac{\abs{\cH} + 1}{\delta}} \right)
    .\]
    For full credit, use explicit constants in your answer, not $\bigO$.

    \textcolor{red}{You can assume that $\frac1n \log\frac{\abs\cH + 1}{\delta} = o(1)$,
    i.e.\ a term with that squared will be ``lower-order.''}

    \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}\textcolor{red}{TODO}\end{answer}
\end{qlist}

\end{document}
