\documentclass[]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
\else % if luatex or xelatex
  \ifxetex
    \usepackage{mathspec}
  \else
    \usepackage{fontspec}
  \fi
  \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage[]{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\PassOptionsToPackage{hyphens}{url} % url is loaded by hyperref
\usepackage[unicode=true]{hyperref}
\hypersetup{
            pdftitle={COMS 6998-4 F17 Homework 2 (due Monday October 30)},
            pdfauthor={Daniel Hsu (djh2164)},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace font for urls
\usepackage[margin=1in]{geometry}
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\setlength{\emergencystretch}{3em}  % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{0}
% Redefines (sub)paragraphs to behave more like sections
\ifx\paragraph\undefined\else
\let\oldparagraph\paragraph
\renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}}
\fi
\ifx\subparagraph\undefined\else
\let\oldsubparagraph\subparagraph
\renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}}
\fi

% set default figure placement to htbp
\makeatletter
\def\fps@figure{htbp}
\makeatother


\title{COMS 6998-4 F17 Homework 2 (due Monday October 30)}
\author{Daniel Hsu (djh2164)}
\date{}

\begin{document}
\maketitle

\newcommand\cA{\mathcal{A}}
\newcommand\cX{\mathcal{X}}
\newcommand\cZ{\mathcal{Z}}
\newcommand\E{\mathbb{E}}
\renewcommand\P{\mathbb{P}}
\newcommand\R{\mathbb{R}}
\newcommand\Rad{\operatorname{Rad}}
\newcommand\Var{\operatorname{Var}}
\newcommand\err{\operatorname{err}}

\section{Instructions}\label{instructions}

Solve \textbf{one} of the assigned problems. If you solve both problems
\emph{perfectly}, then you will receive some ``extra credit''. But only
if both solutions are \emph{perfect}. Also remember homework is only
10\% of the total grade. So don't fret too much.

Submit the assignment on Gradescope as a PDF document by 11:59 PM of the
due date.

Make sure the following appears at the top of the first page of your
write-up:

\begin{itemize}
\tightlist
\item
  your name,
\item
  your UNI, and
\item
  the names and UNIs of any students with whom you discussed the
  assignment.
\end{itemize}

You are welcome to use the Markdown or LaTeX source for the assignment
as a template for your write-up. I use Pandoc \url{http://pandoc.org} to
translate the Markdown to \LaTeX~and ultimately to PDF.

\newpage

\section{Problem 1}\label{problem-1}

Assume you are given: (i) an algorithm for the online classification
problem with mistake bound \(M\), (ii) target error rate \(\epsilon\),
and (iii) confidence parameter \(\delta\).

Consider the following ``online-to-batch'' conversion procedure.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\tightlist
\item
  Simulate the online learner on the first \(n_1(M,\epsilon,\delta)\)
  rounds, and save the collection of hypotheses produced by the online
  learner. You can assume that if the learner doesn't make a mistake in
  some round, then it uses the same hypothesis in the following round.
\item
  Evaluate each of the hypotheses saved from the first step in the next
  \(n_2(M,\epsilon,\delta)\) rounds, and return the hypothesis that
  makes the fewest mistakes.
\end{enumerate}

Determine the sample sizes \(n_1(M,\epsilon,\delta)\) and
\(n_2(M,\epsilon,\delta)\) so that with probability at least
\(1-\delta\), a hypothesis of error rate at most \(\epsilon\) is
returned. Give a detailed analysis that proves your claim. The total
sample size should be an improvement over that of the online-to-batch
procedure we discussed in lecture at least for large enough \(M\) and
small enough \(\epsilon\) and \(\delta\).

\bigskip

\emph{Your solution}:

\newpage

\section{Problem 2}\label{problem-2}

Recall the ``selective ERM'' algorithm from lecture on October 4,
reproduced below.

\(S_0 := \emptyset\), \(h_0 := \cA(S_0)\), \(\beta_0 := \infty\).

For \(n=1,2,\dotsc\):

\begin{itemize}
\tightlist
\item
  Get \(x_n\).
\item
  Predict \(a_n := h_{n-1}(x_n)\).
\item
  Get \(h_{n-1}' := \cA(S_{n-1},(x_n,a_n))\).
\item
  If
  \(\err_{S_{n-1}}(h_{n-1}') \leq \err_{S_{n-1}}(h_{n-1}) + \beta_{n-1}\),
  then:

  \begin{itemize}
  \tightlist
  \item
    Get \(y_n\).
  \item
    Let \(S_n := S_{n-1} \cup \{ (x_n,y_n) \}\).
  \end{itemize}
\item
  Else: Let \(S_n := S_{n-1} \cup \{ (x_n,a_n) \}\).
\item
  Let \(h_n := \cA(S_n)\),
  \(\beta_n := \Rad_{n,P}(H \cup -H) + \sqrt{\frac{2\log(n(n+1)/\delta)}{n}}\).
\end{itemize}

Let \(h^* \in H\) be a fixed hypothesis of minimum error rate with
respect to \(P\). Also define: \[ \begin{aligned}
  \rho(h,h') & := \Pr_{(x,y) \sim P}(h(x) \neq h'(x)) , & \tilde\rho(h^*,h) & := \err_P(h) - \err_P(h^*) , \\
  B(h,r) & := \{ h' \in H : \rho(h,h') \leq r \} , & \tilde{B}(h^*,r) & := \{ h \in H : \tilde\rho(h^*,h) \leq r \} , \\
  D(h^*,r) & := \{ x \in \cX : \exists h \in B(h^*,r) \centerdot h(x) \neq h^*(x) \} , &
  \tilde{D}(h^*,r) & := \{ x \in \cX : \exists h \in \tilde{B}(h^*,r) \centerdot h(x) \neq h^*(x) \} .
\end{aligned} \]

Let \(\cX := \{ x \in \R^d : \|x\|_2 = 1 \}\) be the unit sphere in
\(\R^d\), and let \(H\) be the class of homogeneous linear separators in
\(\R^d\). Furthermore, assume the marginal of \(P\) over \(\cX\) is the
uniform distribution on \(\cX\).

\begin{itemize}
\tightlist
\item
  Part 1. Prove that
  \(\tilde{D}(h^*,r) \subseteq D(h^*,2\err_P(h^*) + r)\).
\item
  Part 2. Prove a bound on the expected number of labels queried by a
  learner using this algorithm after \(n\) rounds. The bound should be
  given only in terms of \(d\), \(n\), and \(\err_P(h^*)\).
\item
  Part 3. Suppose a random draw \((x,y) \sim P\) is produced using the
  following generative process. First, draw \(x\) from the uniform
  distribution on \(\cX\). Then, a coin with heads probability \(\eta\)
  is tossed; if heads, set \(y := -h^*(x)\), and if tails, set
  \(y := h^*(x)\). Here, \(\eta \in (0,1/2)\) is a fixed constant. Prove
  a bound on the expected number of labels queried by a learner using
  this algorithm after \(n\) rounds. The bound should be given only in
  terms of \(d\), \(n\), and \(\eta\). Presumably it should be much
  better than the bound you get in Part 2.
\end{itemize}

\bigskip

\emph{Your solution}:

\end{document}