\documentclass{article}

\usepackage{amsmath,amssymb,amsthm}
\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}}}

\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}

\DeclareMathOperator{\bigO}{\mathcal{O}}

\DeclareMathOperator*{\E}{\mathbb{E}}
\newcommand{\dist}{\mathcal{D}}
\newcommand{\xdist}{\mathcal{D}_x}

\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\sign}{sign}
\DeclareMathOperator{\spn}{span}
\DeclareMathOperator{\tr}{tr}
\newcommand{\tp}{^\mathsf{T}}
\newcommand{\op}{\mathit{op}}

\newcommand{\cH}{\mathcal{H}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cY}{\mathcal{Y}}

\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathcal{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\ud}{\mathrm{d}}

\newcommand{\ERM}{\mathrm{ERM}}
\newcommand{\SRM}{\mathrm{SRM}}
\newcommand{\RLM}{\mathrm{RLM}}

\DeclareMathOperator{\VCdim}{VCdim}
\DeclareMathOperator{\emprad}{\hat{\mathfrak{R}}_S}
\DeclareMathOperator{\rad}{\mathfrak{R}_n}
\newcommand{\bsigma}{\boldsymbol{\sigma}}

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

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

\begin{document}
\begin{center}
\Large
CPSC 532S: Assignment 4 --
due Friday, 8 Apr 2022, 11:59pm
\end{center}


This late policy is \textcolor{red}{extra-extra-generous because of end-of-term: -1 point on the assignment per day you're late, \textbf{not including Saturday/Sunday} so that handing in Monday is only -1, up to a hard deadline of Friday April 15th} (and not accepted after that).
% If you have something significant going on / are sick / whatever,
% write to me, and I can be more flexible there.

This assignment is split into \textcolor{red}{four} questions (the parts with big section headers; most have sub-parts).
You can solve each question in groups of up to three.
Groups don't need to be consistent between problems;
you can do Q1 and Q2 alone, Q3 with Alice, and Q4 with Bob and Carlos if you want.

Please \textbf{do not} just split the questions up and do the parts separately.
\textbf{\color{red} If your name is on a solution, you are pledging that you contributed significantly to the solution and understand it fully.}

There is a separate Gradescope assignment for each problem;
use the Gradescope groups feature to submit once and associate with each of you,
but also put all of your names on the first page as a backup.

Prepare your answers to these questions \textbf{using \LaTeX}.
Hopefully you're reasonably familiar with it,
but if not, try using Overleaf and looking around for tutorials online.
(Note that free Overleaf accounts can only share with one ``named collaborator,''
but you can collaborate with more people by sending them an edit link.
Make sure you only share the parts of the homework you're handing in together!)

Feel free to ask questions if you get stuck on things on Piazza
(but remove any details about the actual answers\dots
feel free to make a private post if that's tough).
If you look stuff up anywhere other than in the slides, one of the two course textbooks, or the Telgarsky notes,
please \textbf{cite your sources}:
just say in the answer to that question where you looked.
(A link is fine, no need for a formal citation.)
Please do not look at solution manuals or so on.
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.

If you like, 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 not, I'm not printing them out).
Or answer in a fresh document;
just make it clear which question you're answering where.

If you're using a consistent group and want to write your answers in one document,
you could split the PDF with e.g.\ \texttt{qpdf a2.pdf --pages . 2-3 -- q1.pdf}
or through the GUI of a PDF viewer.
Or you can upload the full file four times and just make sure you assign pages appropriately.

Submit your answers as a PDF on Gradescope:
\href{https://piazza.com/class/ky0u4qahwdn2xj?cid=17}{instructions on Piazza}.
You'll be prompted to mark where each sub-part is in your PDF;
make sure you mark all relevant pages for each part.
(This saves me a surprising amount of time in grading.)
If something goes wrong, you can also email your assignment to me directly (\texttt{dsuth@cs.ubc.ca}).



\clearpage
\section{Proving kerneldom \pts{25 points + 5 bonus}}

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

\hint{Recall that 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 as in lecture 15 slides ``Building kernels from other kernels'' through ``Some more ways to build kernels.''
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.}


\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 + \tfrac12 \right) (x-y) \right)}{2 \pi \sin((x-y) / 2)}$ on $\R$ for any $n \ge 0$.

\textcolor{black}{(This is called the \emph{Dirichlet kernel}, because it is a continuous kernel which converges to the Dirichlet delta function $\delta(x - y)$ as $n \to \infty$.)}


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



\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$.


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

For \pts{5 bonus}, you can instead show $1 / \sqrt{1 - x\tp y}$ is psd 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}
.\]}




\end{qlist}


\clearpage
\section{Maximizing differences \pts{25}}

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 $\cH_k$.

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



\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) }_{\cH_k}^2$.



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


\item \pts{5} Argue that $\hat h_{\hat\lambda}$ is a solution to
\begin{equation}
  \min_{h \in \cH_k : \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 \cH_k : \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.


\end{qlist}




\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 $\cH_k$ be an RKHS for some twice-differentiable kernel $k$ on $\R$,
i.e.\ $f \in \cH_k$ 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 $\cH_k$,
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}_{\cH_k}^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
  $\frac{\partial}{\partial x} \frac{\partial}{\partial y} k(x, y)$
  and
  $\frac{\partial^2}{\partial x^2} \frac{\partial^2}{\partial y^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 $\cH_k$
  such that for all $f \in \cH_k$ we have
  \[
    \langle \partial_1 k(x, \cdot), f \rangle_{\cH_k} = f'(x)
    \quad\text{ and }\quad
    \langle \partial_1^2 k(x, \cdot), f \rangle_{\cH_k} = f''(x)
  .\]
  For example, this also means that
  \[
    \langle \partial_1 k(x, \cdot), \partial_1 k(x', \cdot) \rangle_{\cH_k} = \partial_1 \partial_2 k(x, x')
    \quad\text{ and }\quad
    \langle \partial_1^2 k(x, \cdot), k(x', \cdot) \rangle_{\cH_k} = \partial_1^2 k(x, x')
  .\]
\end{lemma}

\begin{qlist}
\item \pts{10}
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 (lecture 16, starting around page 18 -- sorry that slides aren't numbered in that lecture\dots) will \emph{not} directly apply, because $J$ depends on the derivatives of $h$. You'll need to make an analogous argument, taking advantage of the lemma above.}



\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{15}
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.

\hint{It will probably help to start by writing out $h(x_i)$, $h'(x_i)$, and $\norm h_{\cH_k}^2$, then plugging those together. It's 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.}

\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,
although I don't need you to write out that system since it's a little messy.




\clearpage
\section{Tangent kernels \pts{25}}

Recall that the empirical tangent kernel for a general model $h(x; w)$ is given by
\[
  k_w(x, x') = \big[ \nabla_w h(x; w) \big]\tp \big[ \nabla_w h(x'; w) \big]
,\]
\textcolor{red}{where here we're thinking of $\nabla_w h(x; w)$ as a \emph{column} vector, so that $k_w(x, x') \in \R$.}

For randomly initialized $w \sim \Q$,
in certain regimes $k_w$ will converge as the model gets bigger to its expectation
\[
  k_\Q(x, x') = \E_{w \sim \Q} k_w(x, x')
.\]

\begin{qlist}

\item \pts{10}
Explicitly write out the empirical tangent kernel $k_w$ for a linear model $h(x; w) = w\tp x$,
and its expected kernel $k_\Q$ when $w \sim \N(0, I)$, the standard normal distribution.
Does kernel regression with $k_\Q$ agree with ERM for $h$ under the square loss (linear regression)?



\item \pts{15}
Explicitly write out the empirical tangent kernel $k_w$ for a (not-very-)deep linear model $f(x; V, W) = v\tp W x$,
where $v \in \R^{m}$ and $W \in \R^{m \times d}$;
you can think of a vector $w \in \R^{m(d+1)}$ as stacking up all the entries of $W$ and $v$.
Assume that $\Q$ has $w \sim \N(0, I)$, and also write out $k_\Q$.
Does kernel regression with $k_\Q$ agree with the ERM of $f$ with square loss?

\hint{\url{http://matrixcalculus.org/} is handy to check that you're taking your derivatives of linear algebra expressions correctly, or \href{https://www.math.uwaterloo.ca/~hwolkowi/matrixcookbook.pdf}{The Matrix Cookbook} is what I used in grad school, back before computers could just solve all our problems for us. But make sure that you handle the shapes correctly -- in this case, $k_w$ should be scalar-valued.}

\hint{Gee, that \href{https://en.wikipedia.org/wiki/Wishart_distribution}{Wishart distribution} sure is neat, huh? Nothing to do with anything in particular, just thought I'd mention.}



\end{qlist}


\end{document}
