\documentclass{article}

\usepackage{amsmath,amssymb,amsthm}
\usepackage{csquotes}
\usepackage{dsfont}
\usepackage{mathtools}
\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{\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}
\DeclareMathOperator{\bigO}{\mathcal{O}}
\newcommand{\bsigma}{\boldsymbol{\sigma}}
\newcommand{\bX}{\mathbf{X}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cN}{\mathcal{N}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cY}{\mathcal{Y}}
\newcommand{\cZ}{\mathcal{Z}}
\DeclareMathOperator*{\E}{\mathbb{E}}
\newcommand{\eps}{\varepsilon}
\newcommand{\indic}{\mathds{1}}
\newcommand{\Lip}{\mathrm{Lip}}
\newcommand{\op}{\mathit{op}}
\newcommand{\R}{\mathbb{R}}
\DeclareMathOperator{\Rad}{Rad}
\DeclareMathOperator{\SG}{\mathcal{SG}}
\DeclareMathOperator{\Sph}{Sph}
\DeclareMathOperator{\spn}{span}
\newcommand{\tp}{^\mathsf{T}}
\DeclareMathOperator{\tr}{tr}
\newcommand{\ud}{\mathrm{d}}
\DeclareMathOperator{\Unif}{Unif}
\newcommand{\id}{\mathop{}\!\mathrm{d}}
\newcommand{\dist}{\mathcal{D}}
\newcommand{\xdist}{\mathcal{D}_x}

% \abs{} uses regular-sized bars, \abs*{} uses auto-sized ones
\DeclarePairedDelimiter{\abs}{\lvert}{\rvert}
\DeclarePairedDelimiter{\norm}{\lVert}{\rVert}
\DeclarePairedDelimiterX{\inner}[2]{\langle}{\rangle}{#1,#2}

\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 2025: Assignment 2
\\
due Wednesday, 15 October 2025, \textbf{12:00 noon}
\end{center}

\vspace{2cm}


You can do this assignment, and future ones, with a partner.
\textbf{Read the website section on academic integrity}
\href{https://www.cs.ubc.ca/~dsuth/532D/25w1/#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 for anything content-related.
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 if you'd prefer.

Submit your answers as a single PDF on Gradescope:
\href{https://canvas.ubc.ca/courses/172832/external_tools/62337?display=borderless}{here's the link}.
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).

Make sure you submit using Gradescope's group feature if you're submitting a joint assignment,
and put both your names on the first page to be safe;
if you did the assignment partially together and partially separately,
hand in separate PDFs, and put a note on each question where you worked together like
\emph{I did this problem with Alice}
so we don't think you cheated. :)

On the off chance something goes wrong,
you can also email your assignment to me directly (\texttt{dsuth@cs.ubc.ca}).



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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{Sums, means, and maxes of subgaussians \pts{50}}

In this question, we're going to explore subgaussians and different versions of Hoeffding's inequality some more.

\begin{qlist}

\item \label{q:sg:sum-dep-sqrt} \pts{10}
    Let $X_1$ be $\SG(\sigma_1)$ and $X_2$ be $\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$ be $\SG(\sigma_1)$ and $X_2$ be $\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 3.6 (which assumed independence).}
    How much worse is what you just got than (Hoeffding') from the notes
    when the variables are actually independent,
    particularly in terms of its dependence on $m$?
    Could you have expected to get a better result,
    or can you construct a dependent example where this dependence on $m$ is necessary?

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

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

\item \pts{15} \label{q:subgauss:max}
    \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, unlike for the mean, 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 subgaussianity. 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.
    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{Complexity: it's simpler than you think \pts{30 points + 5 bonus}}
In class (or notes section 5), we defined the Rademacher complexity
\[
    \Rad(V)
    = \E_{\bsigma \sim \Unif(\pm 1)^m} \sup_{v \in V} \frac1m \sum_{i=1}^m \sigma_i v_i
    = \E_{\bsigma \sim \Unif(\pm 1)^m} \sup_{v \in V} \frac{\bsigma \cdot v}{m}
.\]
We also mentioned in class, for motivation, something that I called the ``spherical complexity.''
letting $\mathbb S = \{ w \in \R^m : \norm w = 1 \}$,
\[
    \Sph(V)
    = \E_{s \sim \Unif(\mathbb S)} \sup_{v \in V} s \cdot v
.\]
I mentioned these two are pretty close.
We'll show now that $\Sph(V)$ is roughly proportional to ${\sqrt m} \Rad(V)$.

\begin{qlist}
\item \pts{5} Argue directly from the definitions of $\Rad$ and $\Sph$ that the $\sqrt m$ scaling ``makes sense.'' \meta{This will probably be one or two lines.}
    \begin{answer}\TODO\end{answer}
\end{qlist}


Let's write
$a \odot b$ for the elementwise product of two vectors,
$(a \odot b)_i = a_i b_i$,
and $a \odot V = \{ a \odot v : v \in V \}$.

It also may be helpful to note that $s \sim \Unif(\mathbb S)$
is equivalent to taking $g \sim \cN(0, I_m)$,
meaning that each $g_i \sim \cN(0, 1)$ iid,
and then setting $s = g / \norm g$.

Define a random variable $q$ by
first taking a uniform vector $s \sim \Unif(\mathbb S)$,
then taking its elementwise absolute value:
$q_i = \abs{s_i}$.
The rest of the questions will all have $q$ follow this distribution.

\begin{qlist}[resume]
\item \pts{10}
    Prove that $\Sph(V) = m \E_{q} \Rad(q \odot V)$.

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

\item \pts{5}
    Show that $\Sph(V) \le m \left( \E_q \norm{q}_\infty \right) \Rad(V)$.
    \meta{Recall that $\norm{q}_\infty = \max_i \abs{q_i}$.}

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

\end{qlist}

Let $g \sim \cN(0, I_m)$ and $s = g / \norm g$,
so that $s \sim \Unif(\mathbb S)$.
Hence
$s_i = \frac{g_i}{\sqrt{g_i^2 + \sum_{j \ne i} g_j^2}}$.
For large $m$,
the denominator will be very very likely to be dominated by the sum,
meaning that
$s_i \approx \frac{g_i}{\sqrt{m}}$.
This suggests that, for large $m$, $s_i$ should be roughly $\SG(C/\sqrt{m})$.
In fact, this is correct (even for small $m$):
using ``concentration of Lipschitz functions on the sphere''\footnote{%
See, e.g., Theorem 5.1.3 (labeled with that quoted text) of the current draft of \href{https://www.math.uci.edu/~rvershyn/papers/HDP-book/HDP-2.pdf}{Vershynin, second edition}.},
there exists some global constant $C > 0$ such that $s_i$ is $\SG(C / \sqrt m)$.
(I found a paper claiming that $C < 560$, but didn't follow their references to check, and presumably that's extremely loose anyway.)

\begin{qlist}[resume]
\item \pts{5} Let $C$ be a constant such that $s_i$ is $\SG(C / \sqrt m)$ for each $i$.
    Prove that $\E_q \norm{q}_\infty \le C \sqrt{\frac2m \log(2m)}$. 

    \hint{That form sure does look reminiscent of \cref{q:subgauss:max}, doesn't it? You can use that result here.}

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


\item \pts{5 bonus}
    Show that $\Sph(V) \ge m (\E_q q_1) \Rad(V)$.
    \meta{Here $q_1$ means the first coordinate of $q$.}

    \hint{Try using \href{https://en.wikipedia.org/wiki/Jensen\%27s_inequality\#Probabilistic_form}{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 \pts{5}
    Show that $\displaystyle \E_q q_1 = \frac{\E_{x \sim \cN(0, 1)} \abs{x}}{\E_{g \sim \cN(0_m, I_m)} \norm{g}}$.

    \hint{Consider $\E \abs{g_1}$, and think about the ``opposite'' of the argument above about constructing $s = g / \norm g$.}
    \begin{answer}\TODO\end{answer}
\end{qlist}

We can just look up the mean of \href{https://en.wikipedia.org/wiki/Chi_distribution}{the chi distribution} to get an exact formula for this ratio.
The numerator is $\sqrt{2/\pi}$;
the denominator is a ratio of gamma functions
which is $\sqrt{m - 1} \, (1 - \bigO(1/m))$,
giving that $\E q_1 \approx \sqrt{2 / (\pi m)} \approx 0.8 / \sqrt{m}$.

Thus, there are constants $c, C$ such that $c \sqrt m \Rad(V) \le \Sph(V) \le C \sqrt m \log(2m) \Rad(V)$.





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\clearpage
\section{Limits of Learning Lipschitz Laws \pts{10 challenge}}

So far, we've only seen covering number bounds based on covering norm balls in $\R^d$.
Let's use an analogous argument with a different kind of result.

Let $\cH = \{ h : [0, C]^d \to \R : h(0) = 0, \norm{h}_\Lip \le B \}$ for some $B \ge 0$,
where the Lipschitz constant is with respect to the usual Euclidean norms.
This is a nonparametric class
that includes ``a \emph{lot}'' of functions.

Consider the ``sup-norm''/uniform norm defined as
$\norm{f}_\infty = \sup_{x} \abs{f(x)}$,
which induces a metric
$\rho_\cH(h, g) = \norm{h - g}_\infty$.
(Recall that $h - g$ is the function that maps $x$ to $h(x) - g(x)$.)
It can be shown\footnote{%
    Example 5.10 of \href{https://go.exlibris.link/9ZMcv9J6}{Wainwright's book}
    shows a lower bound for $d = 1$, $C = 1$
    and points towards how to do the upper bound.
    Just afterwards, he mentions the $d > 1$ case is analogous.
    \meta{(Unfortunately, he only states it in $\asymp$ notation and I'm not totally sure whether the constant there is allowed to depend on $d$ or not. The version of \eqref{eq:covering-lip} is definitely valid -- see e.g.\ \href{https://ieeexplore.ieee.org/document/7944658}{Lemma 6 here} which bounds a more general case with explicit constants -- but I'm not certain it's necessary.)}
    To generalize to $C \ne 1$,
    consider that if $h : [0, C]^d \to \R$
    is $B$-Lipschitz,
    then $x \mapsto h(C x)$ is a $[0, 1]^d \to \R$ function
    which is $BC$-Lipschitz.
}
that the covering number of $\cH$ with respect to this $\rho_\cH$
satisfies
\begin{equation} \label{eq:covering-lip}
    \log N(\cH, \eta) \le \left( \frac{a B C}{\eta} \right)^d
\end{equation}
for some constant $a > 0$
and all $\eta$ small enough that the right-hand side is at least $1$.
Compare this to the $d \log\frac{3 B}{\eta}$ bound we saw for Euclidean balls.

Consider the absolute-value loss $\ell(h, (x, y)) = \abs{h(x) - y}$,
and suppose $\dist$ is such that $\Pr_{(x, y) \sim \dist}(\abs{y} \le Y) = 1$.
\textcolor{question}{Prove a high-probability bound on $\sup_{h \in \cH} L_\dist(\cH) - L_S(h)$}
with the best rate (in terms of $m$) you can find;
it should depend on $a$, $B$, $C$, $Y$, $d$, $m$, and the error probability $\delta$.
Prove this bound with explicit constants,
but then also \textcolor{question}{summarize it in a $\bigO_p$ statement}
treating everything but $m$ as a constant.
\textcolor{question}{Is the rate faster or slower than the logistic regression bound we saw in class?}

\hint{This proof ends up kind of long (at least mine did). Split it into appropriate sub-parts, and maybe define some helper variables along the way so your expressions don't get too unwieldy (but then expand out the final answer). Feel free to make simplifications that make things look nicer at the cost of making the constants worse, but try to get the $m$ dependence right.}

\hint{It's not possible to find the exactly optimal choice of $\eta$ here (when $d \ge 2$). You'll probably want to use $\sqrt{x + y} \le \sqrt x + \sqrt y$ before picking $\eta$, which gives a nicer bound anyway.}

\hint{The \href{https://en.wikipedia.org/wiki/Triangle_inequality\#Reverse_triangle_inequality}{reverse triangle inequality} is often useful.}

\meta{You don't have to repeat any portion of the argument which is verbatim identical to the notes, but you can. If you're not, be very clear about exactly what you've changed.}

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

\end{document}
