\documentstyle[11pt,epsf]{article}
%
\renewcommand{\baselinestretch}{1}
\topmargin=-0.5truein
\textheight=10.0truein
\oddsidemargin=0.0truein
\textwidth=6.5truein
%
\pagestyle{empty}
\begin{document}

\begin{center} {\Large
{\bf ECE 901} \\
{\bf Homework 0: Balancing Estimation and Approximation Errors}}
\end{center}

\noindent Consider a one-dimensional classification problem in which it is
known that the Bayes optimal classifier is a simple threshold
function.  Specifically, assume that the input (feature) space is
${\cal X} = [0,1]$ (e.g., the normalized range of human heights) and
the output space is binary, ${\cal Y} = \{0,1\}$ (e.g.,
$0=\mbox{normal person}, $1=\mbox{professional basketball player}).
Furthermore, assume that the Bayes optimal classifier has the form
$f^*(x) = {\bf 1}_{\{x\geq t\}$ for some (unknown) $t \in (0,1)$.  This is
  reasonable for the example of classifying basketball players, since
  being taller is uniformly better in basketball.

Suppose that we have a collection of data $\{X_i,Y_i\}_{i=1}^n$ of
labeled examples and we wish to design a classifier based on these data.
Consider the following collections of classification rules:
$${\cal F}_k \ = \ \left\{ \, {\bf 1}_{\{x \geq j/k\}}, \ j = 0,\dots,k \, \right\} \ \ \ \mbox{for $k =1,2,\dots$}$$
Define the empirical risk for a classifier $f$ as
$$\widehat{R}_n(f) \ = \ \frac{1}{n} \sum_{i=1}^n {\bf 1}{\{f(X_i)\neq Y_i\}}$$
and the empirical risk minimizers
$$\widehat{f}_n^{(k)} \ = \ \arg \min_{f \in {\cal F}_k} \widehat{R}_n(f)$$
The true risk of a classifier $f$ is given by
$$R(f) \ = \ E_{XY}\left[{\bf 1}_{\{f(X)\neq Y\}}\right] \ = \ P(f(X)\neq Y)$$
The excess risk of $\widehat{f}_n^{(k)}$ is given by
$$R(\widehat{f}_n^{(k)}) - R(f^*) \ = \ \left\{R(\widehat{f}_n^{(k)})-\min_{f \in {\cal F}_k} R(f)\right\} \ + \ \left\{\min_{f \in {\cal F}_k} R(f)-R(f^*)\right\}$$
the sum of the estimation and approximation errors, respectively.
\begin{description}
\item[a.] Apply Hoeffding's inequality to derive a PAC bound for the
  estimation error in each ${\cal F}_k$ (see Lecture 0).  The upper
  bound should be of the following form: with probability at least
  $1-\delta$ (with respect to a random draw of training data)
  $$R(\widehat{f}_n^{(k)})-\min_{f \in {\cal F}_k} R(f) \ \leq \ 
  \epsilon(n,\delta,{\cal F}_k})$$
\item[b.] Show that the expectation of the estimation error can be
bounded as
  $$E\left[R(\widehat{f}_n^{(k)})\right]-\min_{f \in {\cal F}_k} R(f) \ \leq \ 
  \epsilon(n,\delta,{\cal F}_k})+\delta$$
where the expectation is over random draws of the training data.
Based on this upper bound, suggest a reasonable choice for $\delta$.
\item[c.] Assume that the marginal probability of $X$ has a density
  function $p(x)$ that is bounded above by a constant $B>0$.  Derive
  an upper bound on the approximation error $\min_{f \in {\cal F}_k}
  R(f)-R(f^*)$. 
\item[d.] Combine the bounds in (b) and (c) above to obtain an upper
  bound on the expected excess risk
  $$E\left[R(\widehat{f}_n^{(k)})\right] - R(f^*)$$
  Propose a choice
  of $k$ (as a function of $n$) that minimizes the overall upper
  bound.  How does the expected excess risk decay as a function of $n$
with $k$ chosen in this manner?
\end{description}

\end{document}

