\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}}
\DeclareMathOperator{\Cov}{Cov}
\newcommand{\cA}{\mathcal{A}}
\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{\cU}{\mathcal{U}}
\newcommand{\cV}{\mathcal{V}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cY}{\mathcal{Y}}
\newcommand{\cZ}{\mathcal{Z}}
\DeclareMathOperator*{\E}{\mathbb{E}}
\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}
\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 4 --
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{Proving kerneldom \pts{25 + 5 challenge + 2 bonus}} \label{q:kernels}

\textcolor{question}{Prove that the following functions are kernels, i.e.\ that they are positive definite functions.}

\hint{Recall that we proved you can do so by directly proving all kernel matrices are psd,
by writing an explicit feature mapping $k(x, x') = \langle \phi(x), \phi(x') \rangle$ where $\phi$ maps into any Hilbert space (including $\R^d$),
or by using steps known to produce new kernels out of old ones.}

\meta{You could also use Bochner's theorem, which we did not cover in class, if you're a Fourier buff: a kernel $k(x, y) = \psi(x - y)$ with $\psi(0) = 1$ is psd iff it is the Fourier transform of a probability measure.
}

\hint{Here are two Hilbert spaces that might be useful to you.
First, the space $\ell^2$ of square-summable sequences $(a_k)_{k=1}^\infty$ with inner product $\langle (a_k), (b_k) \rangle_{\ell^2} = \sum_k a_k b_k$.
Second, the space $L^2(\cX)$ of square-integrable functions\footnote{Really, this should be a space of equivalence classes of functions, since a function that's zero only almost everywhere will have norm zero. That won't matter for this question.} on $\cX$, with inner product $\langle f, g \rangle_{L^2} = \int_\cX f(x) g(x) \mathrm d x$.
}

\begin{qlist}
\item \pts{5} $k(x, y) = \cos(x - y)$ on $\R$.

\hint{The \href{https://en.wikipedia.org/wiki/List_of_trigonometric_identities}{list of trigonometric identities} makes for good bedtime reading.}
\begin{answer}\textcolor{red}{TODO}\end{answer}

\item \pts{5} $k_n(x, y) = \frac{1}{2\pi} \left[ 1 + 2 \sum_{k=1}^n \cos(k (x - y)) \right] = \frac{\sin\left( \left(n + \frac12 \right) (x-y) \right)}{2 \pi \sin\left( \frac12 (x-y) \right)}$ on $\R$ for any $n \ge 0$.

\meta{(This is called the \emph{Dirichlet kernel}; it's a continuous kernel which converges to the Dirac delta function $\delta(x - y)$ as $n \to \infty$.)}

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

\item \pts{5} $k(x, y) = \min(x, y)$ on $[0, 1]$.

\hint{You could consider the integral $\int_\R \mathds{1}(t \in [0, x]) \mathds{1}(t \in [0, y]) \mathrm d t$.}

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

\item \pts{5} $k(X, Y) = \sum_{x \in X} \sum_{y \in Y} k_0(x, y)$ on finite sets with elements in $\cX$, where $k_0$ is a kernel on $\cX$.
\begin{answer}\textcolor{red}{TODO}\end{answer}

\item \pts{5}
$k(x, y) = 1 / \sqrt{1 - x y}$ on $(-1, 1)$.

For \pts{2 bonus}, you can instead show $1 / \sqrt{1 - x\tp y}$  on $\{ x \in \R^d : \norm x < 1 \}$.

\hint{It might help to use the following expansion (see e.g.\ \href{https://math.stackexchange.com/a/2053154/19147}{here}), which converges for $\abs{z} < 1$:
\[
  \frac{1}{\sqrt{1 - z}} = \sum_{k=0}^\infty c_k z^k
  \quad\text{for}\quad
  c_k := \frac{1}{2^{2 k}} \binom{2k}{k}
.\]}

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

\item \pts{5 challenge} \label{part:kernels:distance}
    The distance kernel $k(x, y) = \norm{x} + \norm{y} - \norm{x - y}$,
    where $\norm\cdot$ is the norm of any Hilbert space.

\hint{For all $n \ge 1$, for all $x_1, \dots, x_n$ and $c_1, \dots, c_n$ such that $\sum_{i=1}^n c_i = 0$, it holds that \[ \sum_{i=1}^n \sum_{j=1}^n c_i \norm{x_i - x_j} c_j \le 0 .\]}
\begin{answer}\textcolor{red}{TODO}\end{answer}


\end{qlist}


\clearpage
\section{Maximizing differences \pts{25}} \label{q:max-diffs}

Let's consider learning a kernel classifier with the somewhat unusual \emph{linear loss},
$\ell(h, (x, y)) = -y h(x)$,
where $y \in \{-1, 1\}$.
Take the kernel $k : \cX \times \cX \to \R$ with associated RKHS $\cF$.

\begin{qlist}
\item \pts{10} Find the regularized loss minimizer
\begin{equation} \label{eq:min-lin}
  \hat h_\lambda = \argmin_{h \in \cF} L_S(h) + \tfrac12 \lambda \norm{h}_{\cF}^2
  \tag{RLM}
,\end{equation}
for a training sample $S = ( (x_1, y_1), \dots, (x_n, y_n) )$.

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

\item \pts{5} Show that $L_S(\hat h_\lambda) = - \frac{1}{\lambda} \norm*{ \frac1n \sum_{i : y_i = 1} k(x_i, \cdot) - \frac1n \sum_{i : y_i = -1} k(x_i, \cdot) }_{\cF}^2$.

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

\item \pts{5} Find a (data-dependent) value of $\lambda$, call it $\hat\lambda$, such that $\norm{\hat h_{\hat\lambda}}_{\cF} = 1$,
and simplify the expression for $L_S(\hat h_{\hat\lambda})$.
\begin{answer}\textcolor{red}{TODO}\end{answer}

\item \pts{5} Argue that $\hat h_{\hat\lambda}$ is a solution to
\begin{equation}
  \min_{h \in \cF : \norm h \le 1} L_S(h)
  \tag{ERM}
  \label{eq:norm-1-erm}
.\end{equation}
Further argue that solving \eqref{eq:norm-1-erm} is equivalent to solving
\begin{equation}
  \max_{h \in \cF : \norm h \le 1} \sum_{i : y_i = 1} h(x_i) - \sum_{i: y_i = -1} h(x_i)
  \tag{MAX}
  \label{eq:max-discrep}
,\end{equation}
i.e.\ finding a function high on the positively-labeled points and low on the negatively-labeled ones.

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

\end{qlist}



\clearpage
\section{Kernel metrics on distributions \pts{15 + 5 challenge}} \label{q:mmd}

Here's a slight tweak to the object we developed in \cref{q:max-diffs},
called the \emph{maximum mean discrepancy}:
\[
\MMD(\cP, \cQ)
= \sup_{f \in \cF : \norm{f}_\cF \le 1} \E_{X \sim \cP} f(X) - \E_{Y \sim \cQ} f(Y)
.\]

Assume for this question that the kernel $k$ of $\cF$ is continuous and
satisfies $\sup_{x \in \cX} k(x, x) \le \kappa^2$ for some $\kappa < \infty$.
Define the \emph{kernel mean embedding} of a (Borel) distribution $\cP$ as
$\mu_\cP = \E_{X \sim \cP} k(X, \cdot)$;
for bounded kernels, this is guaranteed to exist,
and you can move the expectation inside or outside of inner products:
for any $f \in \cF$,
\[
\inner{\mu_\cP}{f}_\cF
= \inner{\E_{X \sim \cP} k(X, \cdot)}{f}_\cF
= \E_{X \sim \cP} \inner{k(X, \cdot)}{f}_\cF
= \E_{X \sim \cP} f(X)
.\]

\begin{qlist}
\item \pts{10}
Prove that
\[
\MMD(\cP, \cQ) = \norm{\mu_\cP - \mu_\cQ}_\cF
\]
and
\[
\MMD^2(\cP, \cQ) = \E_{\substack{X, X' \sim \cP\\Y, Y' \sim \cQ}}\Big[ k(X, X') - 2 k(X, Y) + k(Y, Y') \Big]
.\]
\begin{answer}\textcolor{red}{TODO}\end{answer}
\end{qlist}

From the $\norm{\mu_\cP - \mu_\cQ}_\cF$ form,
we can see that $\MMD$ satisfies all the conditions of a metric on probability distributions
except that we might have $\MMD(\cP, \cQ) = 0$ for $\cP \ne \cQ$.
\meta{The \emph{energy distance} is equivalent to the MMD with the distance kernel from \cref{q:kernels} \cref{part:kernels:distance}.}

\begin{qlist}[resume]
\item \pts{5 challenge} \label{q:mmd:universal}
\begingroup\color{black}
Let $\cX$ be a compact metric space,
and $C(\cX)$ denote the set of continuous bounded functions on $\cX$.
A \emph{universal} kernel $k$ \textcolor{red}{has an RKHS $\cF$} such that
for any $g \in {\color{red} C(\cX)}$, for all $\eps > 0$ there exists an $f \in \cF$
with $\norm{f - g}_\infty = \sup_{x \in \cX} \abs{f(x) - g(x)} \le \eps$.
\endgroup
Prove that if $k$ is universal,
then $\MMD(\cP, \cQ) = 0$ implies $\cP = \cQ$.

\hint{The following result will probably be helpful:
\begin{lemma}
    Two Borel probability measures $\cP$ and $\cQ$ on a metric space $\cX$
    are equal if and only if
    for all $f \in C(\cX)$, $\E_{X \sim \cP} f(X) = \E_{Y \sim \cQ} f(Y)$.
\end{lemma}
}
\begin{answer}\textcolor{red}{TODO}\end{answer}
\end{qlist}

Let $U$ and $V$ be (potentially dependent) random variables with values in $\cU$ and $\cV$ respectively.
Let $k_U$ be a kernel over $\cU$,
$k_V$ a kernel over $\cV$,
and $k_{UV}( (u, v), (u', v')) = k_U(u, u') k_V(v, v')$ a kernel over $\cU \times \cV$.

Define $C_{UV} = \E[ k_U(U, \cdot) \otimes k_V(V, \cdot) ] - \E[k_U(U, \cdot)] \otimes \E[k_V(V, \cdot)]$;
recalling that the outer product of $a \in \cA$ and $b \in \cB$
is a linear operator from $\cB$ to $\cA$ defined by
$[a \otimes b] x = a \inner{b}{x}_\cB$ for all $x \in \cB$.

\begin{qlist}[resume]
\item \pts{5} Show that $\langle f, C_{UV} g \rangle_{\cF_U} = \Cov(f(U), g(V))$ for all $f \in \cF_U$, $g \in \cF_V$.
\begin{answer}\textcolor{red}{TODO}\end{answer}
\end{qlist}

\meta{%
Using a similar argument to \cref{q:mmd:universal},
one can show that if $k_{UV}$ is universal
(or various somewhat weaker conditions),
then $U$ and $V$ are independent if and only if $C_{UV} = 0$.
This can be checked using something called the \emph{Hilbert-Schmidt independence criterion} (HSIC),
which estimates the squared Hilbert-Schmidt norm of $C_{UV}$.
With the distance kernel of \cref{q:kernels} \cref{part:kernels:distance}, this becomes proportional to the \emph{distance covariance}.
}


\clearpage
\section{One way to do semi-supervised learning \pts{25}}
\emph{Semi-supervised learning} is when you're given not only a training set of $(x, y)$ pairs,
but also a set of unlabeled $x$ samples from the marginal distribution of $x$.
(For instance, maybe you have a really big dataset scraped from the web, and have only paid for human annotation of a small, random selection from it.)
Even though there aren't any labels, this can be useful for determining the optimal decision function under some reasonable assumptions:
for instance, if you have a clear cluster structure, it's perhaps more likely that the labeling function is constant on that cluster.

One way to try to implement this is to penalize the \emph{gradient norm} of the decision function, evaluated at the data points -- the decision function should be smooth where there's data.
(You might be familiar with this type of gradient penalty from GANs.)
It turns out that the special structure of RKHSes will allow for this.
Specifically, let's let $\cF$ be an RKHS for some continuously twice-differentiable kernel $k$ on $\R$,
i.e.\ $f \in \cF$ maps $\R$ to $\R$.
(Everything here will work for $\R^d$, the notation just gets a little messier.)

Our goal will be to minimize the following regularized loss over all of $\cF$,
where both $\nu$ and $\lambda$ are positive scalars:
\begin{equation}
  J(h) =
    \frac1n \sum_{i=1}^n \big( h(x_i) - y_i \big)^2
  + \frac \nu m \sum_{i=1}^m \big( h'(x_i) \big)^2
  + \lambda \norm{h}_{\cF}^2
  \tag{J}
.\end{equation}
Here we assume that we have our usual sample set $\big( (x_1, y_1), \dots, (x_n, y_n) \big)$,
but we \emph{also} have an unlabeled sequence $\big( x_{n+1}, \dots, x_m \big)$,
so that we have $m$ total samples for $x$ (of which the first $n$ are labeled).

Kernels are two-argument functions, so differentiation notation can be slightly awkward.
For brevity,
we will use $\partial_1$ to refer to differentiating with respect to the first argument
and $\partial_2$ the second,
so that $\partial_1 k(x, y)$ means $\frac{\partial}{\partial x} k(x, y)$,
$\partial_2^2 k(x, y)$ means $\frac{\partial^2}{\partial y^2} k(x, y)$,
and $\partial_1 \partial_2 k(x, x)$ means $\frac{\partial^2}{\partial z_1 \partial z_2} k(z_1, z_2) \rvert_{\substack{z_1 = x\\z_2 = x}}$ -- note that differentiation happens ``before'' passing the arguments in (this is \emph{not} $\frac{\partial^2}{\partial x^2} k(x, x)$).

The following result will be useful for us:
\begin{lemma}[Special case of Steinwart/Christmann Lemma 4.34]
  Let $k : \R \times \R \to \R$ be a kernel
  such that both
  $\partial_1 \partial_2 k(x, y)$
  and
  $\partial_1^2 \partial_2^2 k(x, y)$
  exist and are continuous.
  Then, for all $x \in \R$,
  $\partial_1 k(x, \cdot)$ and $\partial_1^2 k(x, \cdot)$ are functions in $\cF$
  such that for all $f \in \cF$ we have
  \[
    \langle \partial_1 k(x, \cdot), f \rangle_{\cF} = f'(x)
    \quad\text{ and }\quad
    \langle \partial_1^2 k(x, \cdot), f \rangle_{\cF} = f''(x)
  .\]
  For example, this also means that
  \[
    \langle \partial_1 k(x, \cdot), \partial_1 k(x', \cdot) \rangle_{\cF} = \partial_1 \partial_2 k(x, x')
    \quad\text{ and }\quad
    \langle \partial_1^2 k(x, \cdot), k(x', \cdot) \rangle_{\cF} = \partial_1^2 k(x, x')
  .\]
\end{lemma}

\begin{qlist}
\item \pts{13}
Show a representer theorem for $\argmin_{h \in \cH} J(h)$, i.e.\ that you can write the optimal $h$ as a linear combination of some set of vectors in $\cH$.

\hint{The representer theorem we showed in class \emph{won't} directly apply, because $J$ depends on the derivatives of $h$. You'll need to make an analogous argument, taking advantage of the lemma above.}

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

\end{qlist}

Define the following matrices:
\begin{gather*}
  K = \begin{bmatrix}
    k(x_1, x_1) & \dots & k(x_1, x_n) \\
    \vdots & \ddots & \vdots \\
    k(x_n, x_1) & \dots & k(x_n, x_n)
  \end{bmatrix} \in \R^{n \times n}
  \\
  G = \begin{bmatrix}
    \partial_1 k(x_1, x_1) & \dots & \partial_1 k(x_1, x_n) \\
    \vdots & \ddots & \vdots \\
    \partial_1 k(x_m, x_1) & \dots & \partial_1 k(x_m, x_n) \\
  \end{bmatrix} \in \R^{m \times n}
  \\
  H = \begin{bmatrix}
    \partial_1 \partial_2 k(x_1, x_1) & \dots & \partial_1 \partial_2 k(x_1, x_m) \\
    \vdots & \ddots & \vdots \\
    \partial_1 \partial_2 k(x_m, x_1) & \dots & \partial_1 \partial_2 k(x_m, x_m) \\
  \end{bmatrix} \in \R^{m \times m}
.\end{gather*}

\begin{qlist}[resume]
\item \pts{12}
Write an explicit form for $J(h)$ in terms of usual matrix and vector operations on the $K$, $G$, and $H$ matrices
and the vector $y \in \R^n$ of labels,
as well as the parameters of your linear combination
(and $\lambda$, $\nu$, $n$, and $m$).

\hint{It will probably help to start by writing out $h(x_i)$, $h'(x_i)$, and $\norm h_{\cF}^2$, then plugging those together. It might be helpful in intermediate steps to use the standard basis vectors $e_i$, which have a one in the $i$th entry and zero in all others. Be careful about shapes matching.}
\begin{answer}\textcolor{red}{TODO}\end{answer}
\end{qlist}
If you did it right, the final form for $J$ should be a quadratic form of your coefficients in terms of the matrices $K$, $G$, and $H$.
Thus, setting the gradient to zero will give an analytical solution written as the solution to a certain linear system.
(No need for you to write out that solution, since it's a little messy.)
\end{document}
