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

% https://tex.stackexchange.com/a/42728/9019
\newcommand{\tagthis}[1]{\stepcounter{equation}\tag{\theequation}\label{#1}}

\definecolor{question}{rgb}{0,0,1}
\newlist{qlist}{enumerate}{1}
\setlist[qlist,1]{leftmargin=*, label=\textbf{(\alph*)}, ref={(\alph*)}}
\crefname{qlisti}{part}{parts}
\AtBeginEnvironment{qlist}{\color{question}}
\newcommand{\ask}[1]{\textcolor{question}{#1}}
\newenvironment{asking}{\begingroup\color{question}}{\endgroup}

\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}
\newcommand{\bepsilon}{\boldsymbol{\epsilon}}
\DeclareMathOperator{\bigO}{\mathcal{O}}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cI}{\mathcal{I}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cQ}{\mathcal{Q}}
\newcommand{\cR}{\mathcal{R}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cY}{\mathcal{Y}}
\newcommand{\cZ}{\mathcal{Z}}
\DeclareMathOperator*{\E}{\mathbb{E}}
\DeclareMathOperator{\ERM}{ERM}
\newcommand{\dist}{\mathcal{D}}
\newcommand{\eps}{\varepsilon}
\newcommand{\Lip}{\mathrm{Lip}}
\DeclareMathOperator{\MMD}{MMD}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\op}{\mathit{op}}
\newcommand{\R}{\mathbb{R}}
\let\RR\R
\DeclareMathOperator{\Rad}{Rad}
\DeclareMathOperator{\RLM}{RLM}
\newcommand{\SG}{\mathcal{SG}}
\DeclareMathOperator{\sign}{sign}
\DeclareMathOperator{\spn}{span}
\newcommand{\tp}{^\mathsf{T}}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Unif}{Unif}
\DeclareMathOperator{\VCdim}{VCdim}
\newcommand{\xdist}{\mathcal{D}_x}
\newcommand{\ZZ}{\mathbb{Z}}

%%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}{\@floor}}
\newcommand{\@floor}[1]{\lfloor #1 \rfloor}
\newcommand{\@Floor}[1]{\left\lfloor #1 \right\rfloor}

\newcommand{\inner}{\@ifstar{\@Inner}{\@inner}}
\newcommand{\@inner}[2]{\langle #1, #2 \rangle}
\newcommand{\@Inner}[2]{\left\langle #1, #2 \right\rangle}
\makeatother
%%end novalidate  % overleaf code check false-positives here

\declaretheorem[name=Theorem,numberwithin=section]{thm}
\declaretheorem[name=Proposition,sibling=thm]{prop}
\declaretheorem[name=Lemma,sibling=thm]{lemma}
\declaretheorem[name=Corollary,sibling=thm]{corollary}

\begin{document}
\begin{center}
\Large
CPSC 532D: Assignment 5 --
due Saturday, 10 Dec 2022, \textbf{11:59pm}
\end{center}


As before:
use \LaTeX{}, either with the template I give or your own document if you prefer.

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.
If you accidentally come across a solution while looking for something related,
still write the argument up in your own words, link to wherever you found it, and be clear about what happened.


\clearpage
\section{Validation sets and expectation bounds \pts{20}} \label{q:pac}


\meta{%
Stability and SGD analyses mostly bound only the expected risk;
let's relate that a little more thoroughly to PAC learning now.
}

Let $A$ be a proper learning algorithm (one returning hypotheses in $\cH$) that guarantees: if $n \ge n_\cH(\varepsilon)$,
then for every distribution $\dist$, it holds that
\[
  \E_{S \sim \dist^n} L_{\dist}(A(S)) \le \inf_{h \in \cH} L_\dist(h) + \varepsilon
.\]
Here $L_\dist(h) = \E_{z \sim \dist} \ell(h, z)$ for a loss $\ell(h, z)$ bounded in $[0, 1]$.

In assignment 2 question 1b,
we essentially showed (not quite in these words) via Markov's inequality that
\begin{equation} \label{eq:pac-via-markov}
\forall\, \eps, \delta \in (0, 1),
\text{if $n \ge n_\cH(\varepsilon \delta)$, }
\forall\, \dist,\quad
\Pr\left(L_\dist(A(S)) \le \inf_{h \in \cH} L_\dist(h) + \varepsilon\right) \ge 1 - \delta
\tag{*}
.\end{equation}
\meta{(See \href{https://www.cs.ubc.ca/~dsuth/532D/22w1/assignments/a2sol.pdf\#page=3}{the solutions for a2} if you want a reminder.)}

\meta{%
\eqref{eq:pac-via-markov} implies PAC learning,
but the dependence on $\delta$ is quite bad.
For instance, the stability bound for regularized loss minimization (SSBD corollary 13.9) gives $n_\cH(\eps \delta) = \frac{8 \rho^2 B^2}{\eps^2 \delta^2}$,
so going from a failure probability $\delta$ of $0.1$ to $0.001$ for a fixed $\eps$ requires 10,000 times as many samples,
whereas for the bound we'll show below it's only three times as many samples.
}


Here's a ``meta-algorithm'' that will PAC-learn with a better sample complexity:
\begin{itemize}
\item
    Divide the training data up into $k + 1$ chunks,
    $S = S_1 \cup \dots \cup S_k \cup V$,
    where each of the $S_i$ have $m$ data points and $V$ has $n - m k$.
\item Run $A$ independently on each of the first $k$ chunks, getting $\hat h_i = A(S_i)$.
\item Let $\hat\i = \argmin_{i \in [k]} L_V(\hat h_i)$, and return the hypothesis $h_{\hat\i}$. (That is, choose the ``retry'' that looks best on the validation set $V$.)
\end{itemize}

\ask{Give a way to choose the parameters $m$ and $k$
    (that is, an expression for each variable depending only on on $n_\cH$, $\eps$, and $\delta$)
    such that the procedure agnostically PAC-learns the problem,
    and give the final sample complexity.}
Your sample complexity should be $\bigO\left( \left[ n_\cH(a \eps) + 1/\eps^2 \right] \log(1/\delta) \right)$ for some constant $a > 0$;
please give a finite-sample expression,
i.e.\ a function with explicit constants.


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



\clearpage
\section{Logistic regression \pts{30}} \label{q:logreg}

Let $\cX = \{ x \in \R^d : \norm x \le R \}$.
%and $\cH = \{ w \in \R^d : \norm w \le B \}$.
We'll learn a linear predictor based on logistic loss,
\[
  \ell^{\log}(w, (x, y))
  = \lambda_y^{\log}(w\tp x)
  = \log(1 + \exp(- y w\tp x))
.\]
Let $S$ be a sample $((x_1, y_1), \dots, (x_n, y_n)) \in \left(\cX \times \{-1, 1\}\right)^n$,
and let $X \in \R^{n \times d}$, $y \in \{-1, 1\}^n$ stack up the features and labels accordingly.

\begin{qlist}
  \item \pts{10} Show that $\lambda^{\log}_y(\hat y)$ is 1-Lipschitz and convex for $y \in \{-1, 1\}$.
  \begin{answer}\textcolor{red}{TODO}\end{answer}

  \item \pts{10} Show that for any 1-Lipschitz convex set of functions $\lambda_y$, the corresponding $L_S(w)$ is a convex, $R$-Lipschitz function of $w$.

  \hint{$\norm{g \circ h}_\Lip \le \norm{g}_\Lip \norm{h}_\Lip$, since
        $\norm{g(h(x)) - g(h(y))} \le \norm{g}_\Lip \norm{h(x) - h(y)} \le \norm{g}_\Lip \norm{h}_\Lip \norm{x - y}$.}
  \begin{answer}\textcolor{red}{TODO}\end{answer}

\end{qlist}

Let $A_\lambda(S) = \argmin_{w \in \R^d} L_S(w) + \lambda \norm{w}^2$.
We then have the bounds, from corollaries 13.8-13.9 of SSBD:
\begin{align}
    \text{for any $w^* \in \R^d$,}
    &&
    \E_S L_\dist(A_\lambda(S))
    &\le L_\dist(w^*) + \lambda \norm{w^*} + \frac{2 R^2}{\lambda n}
    ; \nonumber \\
    \text{if we use $\lambda = \frac{R}{B} \sqrt{\frac2n}$,}
    &&
    \E_S L_\dist(A_\lambda(S))
    &\le \inf_{w : \norm w \le B} L_\dist(w) + B R \sqrt{\frac 8 n}
    \tag{$\dagger$} \label{eq:logreg-stability}
%     \\
%     \E_S L_\dist(A(S))
%     &\le \left(1 + \frac{48 \beta}{\lambda n}\right) \left( L_\dist(w^*) + \lambda \norm{w^*}^2 \right)
%     &&\text{ for any $w^*$}
.\end{align}
\meta{It turns out the problem is also Convex-Smooth-Bounded, but the resulting bound is usually worse and also more annoying to work with.}


% Now, we're going to kernelize.
% 
% \begin{corollary}[Kernel version of SSBD Corollary 13.6 and 13.8]
%     Let $\cF$ be an RKHS.
%     Let $\ell : \cF \times \cZ \to \R$ be $\rho$-Lipschitz and convex for each $\cZ$,
%     i.e.\ for all $f, g \in \cF$, $t \in [0, 1]$, and $z \in \cZ$,
%     \begin{equation} \label{eq:convex-lipschitz}
%     \abs{\ell(f, z) - \ell(g, z)} \le \rho \norm{f - g}_{\cF}
%     \qquad\text{and}\qquad
%     \ell(t f + (1-t) g, z) \le t \ell(f, z) + (1-t) \ell(g, z)
%     \tag{$\dagger$}
%     .\end{equation}
%     Then the learning algorithm $A(S) = \argmin_{h \in \cF} L_S(f) + \lambda \norm{h}_{\cF}^2$
%     is on-average replace-one stable with rate $\frac{2 \rho^2}{\lambda n}$,
%     and hence for any $h^* \in \cF$,
%     \[
%         \E_{S \sim \dist^n} L_\dist(A(S))
%         \le \E_{S \sim \dist^n} \left[ L_S(A(S)) \right] + \frac{2 \rho^2}{\lambda n}
%         \le L_\dist(h^*) + \lambda \norm{h^*} + \frac{2 \rho^2}{\lambda n}
%     .\]
% \end{corollary}
% The proof is the same as those SSBD corollaries:
% nothing there depended at all on the norm in question being the Euclidean norm.


\begin{qlist}[resume]
% \item
% Consider a loss of the form $\ell(h, (x, y)) = \lambda_y(h(x))$
% for convex, 1-Lipschitz functions $\lambda_y : \R \to \R$.
% Prove that \eqref{eq:convex-lipschitz} holds for $\ell$.
% \meta{Hence the previous bounds also apply to kernelized logistic regression.}
% Consider a general loss of the form $\ell(w, (x, y)) : \R^d \times (\cX \times \cY) \to \R$
% such that $\ell(\cdot, (x, y))$ is a convex function for each $(x, y) \in \cX \times \cY$.
% Prove that $\ell_\cF(h, (x, y)) = $
% (and hence $L_S$ and $L_\dist$ are convex).
% Suppose that $\ell(w, (x, y)) = \lambda(w\tp x, y)$ for some function $\lambda : \hat Y \times \cY \to \R$.

\item \pts{10} \label{part:logreg:rad}
Let $A'_B(S) \in \argmin_{w \in \R^d : \norm w \le B} L_S(w)$ (constrained ERM).
Use Rademacher complexity to find a bound of the form
\[ \E L_\dist(A'_B(S)) \le \inf_{w : \norm w \le B} L_\dist(w) + Q \]
where $Q$ is some term depending only on $B$, $R$, and $n$.
Compare the resulting bound to \eqref{eq:logreg-stability}.

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


For \textcolor{points}{[no points (but hopefully a sense of personal satisfaction)]}, convince yourself that everything in this problem works for kernel logistic regression,
i.e.\
$\cX = \{ x : \sqrt{k(x, x)} \le R \}$,
$\ell^{\log}(h, (x, y)) = \lambda^{\log}_y(h(x))$,
$A_\lambda(S) = \argmin_{h \in \cF} L_S^{\log}(h) + \lambda \norm{h}_\cF^2$,
and $A'_B(S) = \argmin_{h \in \cF : \norm{h}_{\cF} \le B} L_S^{\log}(h)$.
\meta{Don't hand anything in for this, but if you want, it's nice to verify for yourself that
the loss is still convex and $R$-Lipschitz, that $A_\lambda(S)$ is still stable,
and $A'_B(S)$ still has the same Rademacher bound.}



\clearpage
\section{A really hard Convex-Lipschitz-Bounded problem \pts{15}}

Convex-Lipschitz-Bounded problems are solvable by regularized loss minimization,
which we showed gradient descent can approximately solve in polynomially many gradient steps.
But this \emph{doesn't} guarantee that Convex-Lipschitz-Bounded problems can be efficiently learned.

Let $\cH = [0, 1]$ -- nice and simple -- but let the example domain $\cZ$ be the set of all pairs of Turing machines $T$ with input strings $s$.
Define
\[
    \ell(h, (T, s)) = \begin{cases}
        \mathds{1}(\text{$T$ halts on the input $s$})  & \text{if } h = 0 \\
        \mathds{1}(\text{$T$ does not halt on the input $s$})  & \text{if } h = 1 \\
        h \ell(1, (T, s)) + (1 - h) \ell(0, (T, s)) & \text{if } 0 < h < 1
    .\end{cases}
\]
\ask{Prove that this problem is Convex-Lipschitz-Bounded, but no computable algorithm can learn this problem.}

\hint{If you have no idea what I'm talking about: look up the ``halting problem.''}

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



\clearpage
\section{Learning without concentration \pts{25}}
We're going to do an unsupervised learning task,
where we try to estimate the mean of a distribution,
but we do it with some \emph{missing} observations.
Specifically,
let $\cB$ be the unit ball $\cB = \{ w \in \R^d : \norm w \le 1 \}$,
and let the samples be in
$\cZ = \cB \times \{0, 1\}^d$,
where an entry $z = (x, \alpha)$ with $\alpha$ is a binary ``mask'' vector indicating whether the given entry is missing.
We want to estimate the mean ignoring the missing entries,
i.e.\ $\cH = \cB$ and
\[
    \ell(w, (x, \alpha)) = \sum_{i=1}^d \begin{cases}
        0 & \text{if } \alpha_i = 1 \\
        (x_i - w_i)^2 & \text{if } \alpha_i = 0
    .\end{cases}
\]

\begin{qlist}
\item \pts{10} Show that regularized loss minimization can PAC-learn this problem  with a sample complexity independent of $d$.

\hint{Appeal to \eqref{eq:pac-via-markov} to show PAC learning.}
\begin{answer}\textcolor{red}{TODO}\end{answer}

\item \pts{10}
    \textcolor{black}{Let $\dist$ be a distribution where $x$ is always the fixed vector $0$, and $\alpha$ has its entries i.i.d.\ $\Unif(\{0, 1\}) = \operatorname{Bernoulli}(1/2)$.
    }\textcolor{red}{
    Let $n_\dist(\eps, \delta)$ denote the sample complexity of uniform convergence for this $\dist$,
    so that if $n \ge n_\dist(\eps, \delta)$, then
    \[
        \Pr_{S \sim \dist^n}\left( \sup_{w \in \cH} L_\dist(w) - L_S(w) \le \eps \right) \ge 1 - \delta
    .\]
    Show that, for some (small) fixed $\eps > 0$ and $\delta > 0$, $n_\dist(\eps, \delta)$ increases with $d$.
    }
    % Show that for any $n$,
    % \[ \lim_{d \to \infty} \E_{S \sim \dist^n} \sup_{h \in \cH} L_\dist(h) - L_S(h) = \frac12 .\]

\hint{Show that if $d$ is large enough relative to $n$, you're likely to get at least one dimension $j$ where $(\alpha_i)_j = 1$ for \emph{all} your observed samples $i \in [n]$.}

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

\item \pts{5} Use these two results to describe a problem where RLM is a PAC learner, but uniform convergence doesn't hold. Describe why this doesn't contradict the fundamental theorem of statistical learning.

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


\clearpage
\section{Challenge: Lasso and stability \pts{10}}
On-average replace-one stability is not the only notion of stability
(nor even the most common).
Another useful version of stability is \emph{uniform stability},
which guarantees that
\[
    \forall S, S' \text{ of size $n$ differing for only one point}, \quad
    \sup_{z \in \cZ} \abs{\ell(A(S'), z) - \ell(A(S), z)} \le \gamma(n)
\]
\textcolor{red}{for some $\gamma(n)$ that goes to $0$ as $n \to \infty$}.

One advantage of uniform stability is that you can get high-probability bounds on $L_\dist(A(S))$,
not just expectation bounds.
(There's a simple route via McDiarmid, or over the past few years there have been some breakthroughs that give potentially much better bounds based on more complex analyses.)

For $\norm\cdot_2$-regularized linear models (including kernels),
the proof we did to show a bound on the on-average replace-one stability
in fact shows the same bound on the uniform stability,
$\gamma(n) \le \frac{2 \rho^2}{\lambda n}$.

The Lasso algorithm is based on the square loss and a $\norm w_1 = \sum_{j=1}^d \abs{w_j}$ regularizer:
\[
    A_\lambda(S) \in \argmin_{w \in \R^d} L_S(w) + \lambda \norm w_1
.\]
(If there are multiple minimizers, let's have $A_\lambda$ return an arbitrary one.)
The Lasso algorithm is nice because it often returns sparse solutions,
i.e.\ $w$ with many $w_j = 0$.

Let's use $\cZ = \cX \times \cY = \{ x \in \R^d : \norm x \le R \} \times [-M, M]$ for simplicity.

\begin{qlist}
\item \pts{5} Show that the Lasso algorithm is not uniformly stable.

\hint{There's a reason I mentioned multiple minimizers above.}
\begin{answer}\textcolor{red}{TODO}\end{answer}

\item \pts{5} Show that the Lasso algorithm for any $\lambda > 0$ \emph{is} on-average replace-one stable.

\hint{This is probably easiest to show with an ``indirect'' route via Rademacher complexity, as in \cref{q:logreg} \cref{part:logreg:rad}. You'll also have to go through Lagrange duality and bound the Rademacher complexity of an appropriate set.}

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



\end{document}
