\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{\cC}{\mathcal{C}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cI}{\mathcal{I}}
\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{\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}
\DeclareMathOperator{\Unif}{Unif}
\DeclareMathOperator{\VCdim}{VCdim}
\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

\newcommand{\lec}[2]{\href{https://cs.ubc.ca/~dsuth/532D/23w1/notes/#1.pdf}{#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 2023: Assignment 3
\\
due Friday November 10th, \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{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{Rademacher complexity of weirder linear classes \pts{20}}

Consider $\cH_{\norm{\cdot} \le B} = \{ x \mapsto w \cdot x : \norm{w} \le B \}$,
where throughout this question $\norm w$ denotes a \emph{generic} vector norm of $w$,
not necessarily the Euclidean norm $\norm{w}_2$.
For example, we could use
$\norm{w}_1 = \sum_{j \in [d]} \abs{w_j}$,
$\norm{w}_\infty = \max_{j \in [d]} \abs{w_j}$,
or $\norm{w}_S = \sqrt{w\tp S w}$.

The \emph{dual norm} of a norm $\norm{\cdot}$ is given by
\[
    \norm{v}^* = \sup_{\norm w \le 1} v \cdot w
.\]
For instance, for the Euclidean norm $\norm{w}_2$,
we have
\[
    \norm{v}_2^*
    = \sup_{\norm{w}_2 \le 1} v \cdot w
    \le \sup_{\norm{w}_2 \le 1} \norm{v}_2 \norm{w}_2
    = \norm{v}_2
,\]
using Cauchy-Schwarz;
the inequality is actually an equality,
achieved by picking $w = v / \norm{v}_2$.

More generally,
\href{https://en.wikipedia.org/wiki/H%C3%B6lder%27s_inequality#Counting_measure}{Hölder's inequality}
shows the dual norm of $\norm{w}_p = (\sum_{j=1}^d \abs{w_j}^p )^{1/p}$
is $\norm{\cdot}_q$,
where $\frac1p + \frac1q = 1$.
Thus the dual of $\norm\cdot_2$ is still $\norm\cdot_2$,
but also the dual of $\norm\cdot_1$ is $\norm\cdot_\infty$, and vice versa.

Consider for a general norm the function class
\[
    \cH_{\norm\cdot \le B} = \{ x \mapsto x \cdot w : \norm w \le B \}
.\]
Recall that we bounded the Rademacher complexity of $\cH_{\norm\cdot_2 \le B}$
in Section 3.2 of the \lec{5-rademacher}{Rademacher notes}.

\begin{qlist}
\item \pts{5} Follow the same strategy to show that
\[
    \Rad( \cH_{\norm\cdot \le B} \rvert_{S_x} )
    = \frac{B}{m} \E_{\bsigma} \norm*{\sum_{i=1}^m \sigma_i x_i}^*
.\]
\begin{answer}\TODO\end{answer}
\end{qlist}

\meta{
We can use this result, as in SSBD Lemma 26.11,
to see that for $\cH_{\norm\cdot_1 \le B}$ (corresponding to Lasso),
\begin{align*}
    \E_{\bsigma} \norm*{\sum_{i=1}^m \sigma_i x_i}_\infty
 &= \E_{\bsigma} \max\left( \abs*{\left(\sum_{i=1}^m \sigma_i x_i\right)_1}, \dots,  \abs*{\left(\sum_{i=1}^m \sigma_i x_i\right)_d} \right)
\\&= \E_{\bsigma} \max\left(
    \sum_i \sigma_i (x_i)_1, \sum_i \sigma_i (-x_i)_1,
    \dots,
    \sum_i \sigma_i (x_i)_d, \sum_i \sigma_i (-x_i)_d,
\right)
\\&= \Rad\left( \left\{
    \bigl((x_1)_1, \dots, (x_m)_1\bigr),
    \bigl((-x_1)_1, \dots, (-x_m)_1\bigr),
    \dots,
    \bigl( (x_1)_d, \dots, (x_m)_d \bigr),
    \bigl( (-x_1)_d, \dots, (-x_m)_d \bigr)
\right\} \right)
.\end{align*}
This last expression is the Rademacher complexity of a set of size $2 d$.
If $\abs{ (x_i)_j } \le C$ for all $i \in [m]$, $j \in [d]$,
then each vector in this set has Euclidean norm at most
$\sqrt{\sum_{i=1}^m C^2} = C \sqrt{m}$;
thus, applying Massart's finite class lemma (Lemma 1 from the \lec{6-vc}{VC notes})
gives that
$\Rad(\cH_{\norm\cdot_1 \le B}\rvert_{S_x}) \le B C \sqrt{2 \log(2d) / m}$.
}

\begin{qlist}[resume]
\item \pts{5}
    Bound $\Rad(\cH_{\norm\cdot_p \le B} \rvert_{S_x})$ in terms of $\frac1m \sum_{i=1}^m \norm{x_i}_2^2$ for general $p \ge 1$, with a bound that goes to zero as $m \to \infty$.

    \hint{If $0 < a < b$, then Hölder's inequality implies $\norm{x}_b \le \norm{x}_a \le d^{\frac1a - \frac1b} \norm{x}_b$ for $x \in \R^d$.}

    \meta{(This isn't the most natural bound; there should be one in terms of $\norm{x_i}_q$ with $\frac1p + \frac1q = 1$, but honestly I couldn't figure it out right away.)}

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

\item \pts{10}
    The \emph{Mahalanobis norm} is $\norm{x}_S = \sqrt{x\tp S x}$
    for a strictly positive-definite matrix $S$.
    Show that $\norm{x}_S^* = \norm{x}_{S^{-1}}$,
    and bound $\Rad(\cH_{\norm\cdot_S \le B}\rvert_{S_x})$ in terms of $\frac1m \sum_{i=1}^m \norm{x_i}_{S^{-1}}$,
    with a bound that goes to zero as $m \to \infty$.

    \hint{Recall that if $S$ is strictly positive definite, there is a symmetric matrix $S^{\frac12}$ such that $S = S^{\frac12} S^{\frac12}$.}

    \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 (\lec{6-vc}{VC notes}, section 4.1.1)
that the $\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 11 in the notes), and also the simpler Corollary 9, to give two upper bounds on the growth function $\Gamma_\cH(n)$.
\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 per distinct bound from the previous parts.}
\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{Piecewise-constant functions \pts{30 points + 4 challenge}}

Let $a = (a_1, a_2, \dots, a_k, 0, 0, \dots)$
be an eventually-zero sequence
with entries $a_i \in \{0, 1\}$.
Then define a hypothesis $h_a : \R_{> 0} \to \{0, 1\}$ by
\[
    h_a(x) = a_{\ceil{x}} = \begin{cases}
    a_1 & \text{if } 0 < x \le 1 \\
    a_2 & \text{if } 1 < x \le 2 \\
    &\vdots
\end{cases}
.\]
Consider the hypothesis class of all such functions:
$\cH = \{ h_a : \forall i \in \NN, a_i \in \{0, 1\} \text{ and } a \text{ is eventually zero} \}$.
We'll use the 0-1 loss in this question.

\begin{qlist}
\item \label{q:const:vc} \pts{5} Show $\VCdim(\cH) = \infty$.
\begin{answer}\TODO\end{answer}

\item \label{q:const:noshatter} \pts{10}
    Give an example of a continuous distribution $\xdist$ on (a subset of) $\R_{> 0}$ where,
    for some $m < \VCdim(\cH)$, samples $S_x \sim \xdist^m$ have probability zero of being shattered by $\cH$.
    Thus prove that, for any $\dist$ with this $x$ marginal $\xdist$,
    ERM over $\cH$ $(\eps,\delta)$-competes with the best hypothesis in $\cH$ for that $\dist$
    with some finite sample complexity,
    rather than the infinite sample complexity that would be implied by the VC bound.
\begin{answer}\TODO\end{answer}

\item \label{q:const:srm} \pts{10}
    Write $\cH = \cH_1 \cup \cH_2 \cup \cdots$, where each $\cH_k$ has a finite VC dimension,
    and write down an explicit SRM algorithm that nonuniformly learns $\cH$.
    \meta{By ``an explicit algorithm,'' I mean to expand out things like the uniform convergence bound for $\cH_k$; it's okay to write something as an argmin over $\cH$ (like in equation (2) of \lec{8-srm}{the SRM notes}, if you say what $k_h$ is for a given $h$ and give the value of the Rademacher complexity term), or to just appeal to the SRM algorithm pseudocode from the notes (as long as you say what's in each $\cH_k$, what the $\eps_k$ functions are, and how to compute the stopping condition).}
\begin{answer}\TODO\end{answer}


\item \label{q:const:hardsrm} \pts{2 challenge} \textbf{Challenge question:}
    Suppose that instead of eventually-zero sequences,
    we allowed all possible sequences $a$,
    e.g.\ the $a$ that infinitely alternates between 0 and 1 could be an option.
    Prove that this bigger $\cH'$ is \emph{not} nonuniformly learnable.
    \meta{This implies a sort of no-free-lunch theorem for nonuniform learnability.}

    \hint{Try a \href{https://en.wikipedia.org/wiki/Cantor's_diagonal_argument}{diagonalization argument}.}
\begin{answer}\TODO\end{answer}


\item \label{q:const:radsmall} \pts{2 challenge} \textbf{Challenge question:}
    Prove that, for \emph{any} $\xdist$,
    $\E_{S_x \sim \xdist^m} \Rad(\cH\rvert_{S_x}) \to 0$
    as $m \to \infty$.

    \hint{One way to do it (there's probably more than one): first, reduce to the ``ceiled'' distribution over $\NN$ instead of over $\R_{>0}$. Then, letting $Q_S$ denote the number of \emph{unique} integers you've seen in your sample, get a bound in terms of $\E Q_S / m$. Then prove that $\E Q_S = o(m)$ for any distribution over $\NN$.}
\begin{answer}\TODO\end{answer}

\item \label{q:const:oops} \pts{5}
    An absentminded professor made the following argument on the \emph{final exam} for a course:
    \begin{displayquote} \itshape
        If a hypothesis class has $\E_{S_x \sim \xdist^m} \Rad(\cH\rvert_{S_x}) \to 0$ for all $\xdist$,
        then for all realizable $\dist$,
        \[ L_\dist(\hat h_S) \le \E_{S_X \sim \xdist^m} \Rad(\cH\rvert_{S_x}) + \sqrt{\frac{1}{2m} \log\frac1\delta} \to 0 .\]
        Thus, by the ``fundamental theorem of statistical learning,'' $\cH$ must have finite VC dimension.
    \end{displayquote}
    Clearly this argument is wrong, since it puts \cref{q:const:vc,q:const:radsmall} in contradiction.
    What was her mistake?
\begin{answer}\TODO\end{answer}
\end{qlist}



\clearpage
\section{Challenge: Rademacher lower bounds \pts{6 challenge}}
Using the no-free-lunch theorem,
we proved a lower bound on the ability of any algorithm to learn a binary classifier from $\cH$ in 0-1 loss
based on $\VCdim(\cH)$
(Theorem 3 in \lec{7-nfl}{the no-free-lunch notes}).

We didn't say anything about Rademacher lower bounds, though.
In this challenge question, we'll explore what can and can't be said for lower bounds based on Rademacher complexity.

First, let $\cF$ be some class of functions $\cZ \to \R$.
We're going to prove that,
for any $\dist$ over $\cZ$,
\begin{multline} \label{eq:exp-rad-lb}
    \frac12 \left(
        \E_{S \sim \dist^m} \sup_{f \in \cF} \left( \frac1m \sum_{i=1}^m f(z_i) - \E_{z \sim \dist} f(z) \right)
      + \E_{S \sim \dist^m} \sup_{f \in \cF} \left( \E_{z \sim \dist} f(z) - \frac1m \sum_{i=1}^m f(z_i) \right)
    \right)
\\ \ge \frac12 \E_{S \sim \dist^m} \Rad(\cF\rvert_S) - \frac{1}{2 \sqrt m} \sup_{f \in \cF} \abs*{\E_{z \sim \dist} f(z)}
.\end{multline}
The left-hand side here is the average of the two directions of one-sided uniform convergence.
Recall that the left-hand side is upper-bounded by $2 \E_{S \sim \dist^m} \Rad(\cF\rvert_S)$:
we bounded the $\E_z f(z) - \frac1m \sum_i f(z_i)$ term by this
in \lec{5-rademacher}{the Rademacher notes},
and examining the symmetrization argument shows that the same bound holds for the $\frac1m \sum_i f(z_i) - \E f(z)$ one as well.

Let's start by proving \eqref{eq:exp-rad-lb}:
\begin{qlist}
\item \pts{1} \label{q:lb:shift}
  \textcolor{black}{Let $\cF' = \{ z \mapsto f(z) - c_f : f \in \cF \}$, where $c_f \in \R$ may differ for each $f$.}
  Prove that $\Rad(\cF' \rvert_S) \le \Rad(\cF \rvert_S) + \frac{1}{\sqrt m} \sup_{f \in \cF} \abs{c_f}$.

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

\item \pts{3} Prove \eqref{eq:exp-rad-lb}.

\hint{Start by defining the centred class $\tilde \cF_\dist = \{ z \mapsto f(z) - \E_{z \sim \dist}[f(z)] : f \in \cF \}$,
  and consider $\frac12 \E_S \Rad(\tilde \cF_\dist \rvert_S)$.
  An appropriate application of \cref{q:lb:shift} will show this is at least the right-hand side.
  To show it's at most the left-hand side,
  expand out the definition and follow essentially the same argument as the symmetrization proof
  from Section 2 of \lec{5-rademacher}{the Rademacher notes}.}

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

When $a \le f(z) \le b$ for all $f, z$,
we can bound $\sup_{f \in \cF} \abs{\E_{z \sim \dist} f(z)} \le \max(\abs{a}, \abs{b})$.
Now, while
the left-hand side of \eqref{eq:exp-rad-lb} doesn't change if we shift all of $\cF$ by a constant,
and recalling that $\Rad(V + \{w\}) = \Rad(V)$ the first-term of the right-hand side doesn't either,
$\max(\abs a, \abs b)$ does.
Thus, if we shift $\cF$ so that $\abs{f(z)} \le \frac12 (b - a)$ for all $f$ and $z$,
we get that the average of the two directions of expected worst-case one-sided uniform convergence
is at least
\[
    \frac12 \E_{S \sim \dist^m} \Rad(\cF\rvert_S) - \frac{b - a}{4 \sqrt m}
.\]




Many sources in the literature consider two-sided uniform convergence,
$\sup_{f \in \cF} \abs*{\frac1m \sum_{i=1}^m f(z_i) - \E_{z \sim \dist} f(z)}$,
rather than the one-sided convergence we've always used; the upper bound then looks like
\[
    \E_{S \sim \dist^m} \sup_{f \in \cF} \abs*{\frac1m \sum_{i=1}^m f(z_i) - \E_{z \sim \dist} f(z)}
    \le 2 \E_{S \sim \dist^m} \Rad( ( \cF \cup -\cF )\rvert_S )
,\]
where $-\cF = \{ z \mapsto -f(z) : f \in \cF \}$.\footnote{%
    Note that $\Rad((\cF \cup -\cF)\rvert_S) = \E_{\bsigma} \sup_{f \in \cF} \abs*{\frac1m \sum_{i=1}^m \sigma_i f(z_i)}$;
    the original definition of Rademacher complexity, which still appears in many sources, was
    $\Rad_{\abs\cdot}(V) = \E_{\bsigma} \sup_{v \in V} \abs{v \cdot \bsigma} / m$.
    The version we use, without the absolute value, has turned out to be preferable for a bunch of reasons.}
If $\cF = - \cF$, i.e.\ the function class is symmetric, this is the same bound as we got in the one-sided case,
because then indeed the one-sided and two-sided cases are the same.

Notice that the left-hand side of \eqref{eq:exp-rad-lb} is always at most
$\E_{S \sim \dist^m} \sup_{f \in \cF} \abs*{\frac1m \sum_{i=1}^m f(z_i) - \E_{z \sim \dist} f(z)}$.
Thus, if $a \le f(z) \le b$ for all $f$ and $z$,
the same McDiarmid argument as in
Theorem 8 of \lec{5-rademacher}{the Rademacher notes}
gives that
\begin{align}
\Pr_{S \sim \dist^m}\Biggl(
        \sup_{f \in \cF} \abs*{\frac1m \sum_{i=1}^m f(z_i) - \E_{z \sim \dist} f(z)}
        &\ge \frac12 \E_{S \sim \dist^m} \Rad(\cF \rvert_S) - \frac{b - a}{\sqrt m}\left( \frac14 + \sqrt{\frac{1}{2} \log\frac1\delta} \right)
        \Biggr) \ge 1 - \delta
\label{eq:twosided-lb}
\\
\Pr_{S \sim \dist^m}\Biggl(
        \sup_{f \in \cF} \abs*{\frac1m \sum_{i=1}^m f(z_i) - \E_{z \sim \dist} f(z)}
        &\le 2 \E_{S \sim \dist^m} \Rad( ( \cF \cup -\cF )\rvert_S ) + \frac{b - a}{\sqrt m} \sqrt{\frac{1}{2} \log\frac1\delta}
        \Biggr) \ge 1 - \delta
\notag
.\end{align}

So far we've only really looked at upper bounds on the Rademacher complexity.
It's possible to get lower bounds, though;
\cref{q:thresholds} has one example.
Another is given by equation (D.24) of [MRT], which implies\footnote{%
    This means that $\Rad( \cH_B \rvert_S ) / \left( \frac{B}{\sqrt m} \sqrt{\frac1m \sum_{i=1}^m \norm{x_i}^2} \right) \in \left[\frac{1}{\sqrt{2}}, 1\right] \subset [0.7, 1]$; that's pretty nice!}
\begin{equation}
    \text{for } \cH_B = \{ x \mapsto w \cdot x : \norm w \le B \},
    \quad
    \Rad( \cH_B\rvert_{S_x} ) \ge \frac{B}{\sqrt{2 m}} \cdot \sqrt{\frac1m \sum_{i=1}^m \norm{x_i}^2}
\label{eq:boundlin-rad-lb}
.\end{equation}
Jensen's inequality goes \href{https://x.com/ccanonne_/status/1093683656147628032}{the wrong way}
to lower-bound bound the expected Rademacher complexity,
but at least asymptotically we know
that $\E \sqrt{\frac1m \sum_{i=1}^m \norm{x_i}^2}$ converges to a nonzero constant as $m \to \infty$,
as long as $x$ is not almost surely zero.

The real problem, though, is that Talagrand's contraction lemma is only one way.
Using \eqref{eq:twosided-lb},
our lower bound on 
$\sup_{h \in \cH} L_\dist(h) - L_S(h)$
would depend on
$\E_S \Rad((\ell \circ \cH)\rvert_S)$,
and it's not obvious how to lower-bound that by something depending on $\Rad(\cH\rvert_{S_x})$.

(It's also not obvious how to use a lower bound on $\sup_{h \in \cH} L_\dist(h) - L_S(h)$
to get a lower bound on any learning algorithm, even the ERM:
maybe the $h$ with small $L_S(h)$ all have small $L_\dist(h) - L_S(h)$,
but there are hypotheses where $L_\dist(h)$ and $L_S(h)$ are both big and far away from each other.)

These problems are in fact not possible to fix in general:

\begin{qlist}[resume]
\item \pts{2}
    Give an example of a problem (an $\cH$, $\dist$, and $\ell$) where $\E_{S \sim \dist^m} \Rad(\cH \rvert_{S_x}) \not\to 0$ as $m \to \infty$, and yet ERM can achieve arbitrarily small excess error with enough samples.

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

\end{document}
