\documentclass[fleqn]{article}

\usepackage{mydefs}
\usepackage{notes}
\usepackage{url}

\begin{document}
\lecture{Machine Learning}{HW09: Kernel methods}{CS 689, Spring 2015}

% IF YOU ARE USING THIS .TEX FILE AS A TEMPLATE, PLEASE REPLACE
% "CS 689, Spring 2015" WITH YOUR NAME AND UID.

Hand in via moodle at: \url{https://moodle.umass.edu/course/view.php?id=20836}.
Remember that only PDF submissions are accepted.  We encourage using
\LaTeX\ to produce your writeups.  See \verb+hw00.tex+ for an example
of how to do so.  You can make a \verb+.pdf+ out of the \verb+.tex+ by
running ``\verb+pdflatex hw00.tex+''. You'll need mydefs.sty and notes.sty which can be downloaded from the course page.

\bee
\i Suppose that you have N data points in D dimensions. Suppose you run perceptron for 1 pass over the
data set and it makes K updates. How long does this take? (Big-O notation, please: note, it should
not actually depend on K.) How long would it take to run if you preprocessed your data with the
quadratic feature map? How long for cubic feature map?


Now, suppose that you run kernelize perceptron over the same data with a linear kernel. How long
will this take (it should depend on K now, and note that under different feature maps, the numbers
K will not be comparable.) What about for quadratic or cubic kernels?

\ene
\end{document}
