%% This LaTeX-file was created by <jl> Thu Oct 18 15:35:45 2001
%% LyX 1.0 (C) 1995-1999 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass{amsart}
\usepackage[T1]{fontenc}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\theoremstyle{plain}    
\newtheorem{thm}{Theorem}[section]
\numberwithin{equation}{section} %% Comment out for sequentially-numbered
\numberwithin{figure}{section} %% Comment out for sequentially-numbered

\makeatother

\begin{document}


\section{Technique}

Progressive validation is a technique which allows you to use almost \( \frac{1}{2} \)
of the data in a holdout set for training purposes while still providing the
same guarantee as the holdout bound. It first appeared in \cite{Progressive}
and is discussed in a more refined and detailed form here.

Suppose that you have a training set of size \( m_{\textrm{train}} \) and test
set of size \( m_{\textrm{pv}} \). Progressive validation starts by first learning
a hypothesis on the training set and then testing on the first example of the
test set. Then, we train on training set plus the first example of the test
set and test on the second example of the test set. The process continues \( m_{\textrm{test}} \)
iterations. Let \( m \) abbreviate \( m_{\textrm{pv}} \). Then, we have \( m \)
hypotheses, \( h_{1},...,h_{m} \) and \( m \) error observations, \( \hat{e}_{1},...,\hat{e}_{m} \).
The hypothesis output by progressive validation is the randomized hypothesis
which chooses uniformly from \( h_{1},...,h_{m} \) and evaluates to get an
estimated output. 

Since we are randomizing over hypotheses trained on \( m_{\textrm{train}} \)
to \( m_{\textrm{train}}+m_{\textrm{pv}}-1 \) examples, the expected number
of examples used by any hypothesis is \( m_{\textrm{train}}+\frac{m_{\textrm{pv}}-1}{2} \).
Given that training can exhibit phase transitions, the extra few examples can
greatly improve the accuracy of the trained example.

The true error rate of this randomized hypothesis will be: 
\[
e_{\textrm{pv}}=\frac{1}{m_{\textrm{pv}}}\sum _{i=1}^{m_{\textrm{pv}}}e(h_{i})\]
where \( e(h_{i})=\Pr _{D}(h_{i}(x)\neq y) \) and the empirical error estimate
of this randomized hypothesis will be: 
\[
\hat{e}_{\textrm{pv}}=\frac{1}{m_{\textrm{pv}}}\sum _{i=1}^{m_{\textrm{pv}}}\hat{e}_{i}\]



\section{Variance analysis}

Bounding the deviation of \( \hat{e}_{\textrm{pv}} \) is more difficult than
bounding the deviation of a holdout error. To understand this, we can think
of two games, the holdout game and the progressive validation game.

In the holdout game, your opponent chooses a bias and then nature flips \( m \)
coins with that bias. If the deviation of the average number of heads is larger
than \( \epsilon  \), then you lose. Otherwise, you win.

In the progressive validation game, the opponent chooses the bias of \emph{each}
coin just before it is flipped. The goal of the opponent remains the same, and
the opponent wins if a large deviation is observed. 

The progressive validation opponent is stronger than the holdout opponent since
the progressive validation opponent could choose the same bias for every coin.
Nonetheless, we will see that the progressive validation opponent is \emph{not}
much stronger. 

There are two ways in which we can show that the progressive validation opponent
is not much stronger. The first technique will show that the variance of the
progressive validation estimate is smaller than might be expected. 

\begin{thm}
Suppose we test the progressive validation hypothesis on \( m_{\textrm{test}}=m_{\textrm{pv}} \)
additional examples. Let \( \hat{e}_{\textrm{test}} \) be the empirical error
on these examples. Then, we have:
\[
E_{(x,y)^{m_{\textrm{pv}}+m_{\textrm{test}}}\sim D^{m_{\textrm{pv}}+m_{\textrm{test}}}}(\hat{e}_{\textrm{test}}-e_{\textrm{pv}})^{2}\]
\[
\geq E_{(x,y)^{m_{\textrm{pv}}}\sim D^{m_{\textrm{pv}}}}(\hat{e}_{\textrm{pv}}-e_{\textrm{pv}})^{2}\]

\end{thm}
\begin{proof}
Every example on the left hand side can be though of as a coin with bias \( e_{\textrm{pv}}. \)
The variance of the LHS is then \( m*e_{\textrm{pv}}(1-e_{\textrm{pv}}) \).
The right hand side is: 
\[
E_{(x,y)^{m}\sim D^{m}}(\hat{e}_{\textrm{pv}}-e_{\textrm{pv}})^{2}\]
\[
=E_{(x,y)^{m}\sim D^{m}}\left[ \sum _{i=1}^{m}\hat{e}_{i}-e_{i}\right] ^{2}\]
where \( e_{i}=e(h_{i}) \) 
\[
=E_{(x,y)^{m}\sim D^{m}}\left[ \sum _{i\neq j}(\hat{e}_{i}-e_{i})(\hat{e}_{j}-e_{j})+\sum _{i=1}^{m}(\hat{e}_{i}-e_{i})^{2}\right] \]
\[
=\sum _{i\neq j}E_{(x,y)^{m}\sim D^{m}}(\hat{e}_{i}-e_{i})(\hat{e}_{j}-e_{j})+\sum _{i=1}^{m}E_{(x,y)^{m}\sim D^{m}}(\hat{e}_{i}-e_{i})^{2}\]
The cross product term is: 
\[
E_{(x,y)^{m}\sim D^{m}}(\hat{e}_{i}-e_{i})(\hat{e}_{j}-e_{j})\]


Without loss of generality, assume that \( i<j \). What we wish to prove is
that the expected value of this quantity is \( 0 \) conditional on the values
of all random variables other than \( i \)th or \( j \)th example. Let \( S_{ij} \)
be the set of examples minus the \( i \)th and \( j \)th example. Also, let
\( z_{i} \) and \( z_{j} \) be the \( i \)th and \( j \)th labeled examples.
If we can show that: 
\[
\forall S_{ij}:\,\,E_{z_{i},z_{j}|S_{ij}}(\hat{e}_{i}-e_{i})(\hat{e}_{j}-e_{j})=0\]
 then linearity of expectation will imply that: 
\[
E_{(x,y)^{m}\sim D^{m}}(\hat{e}_{i}-e_{i})(\hat{e}_{j}-e_{j})=0\]


The value of \( e_{i} \) is fixed after conditioning on \( S_{ij} \) (and
assuming a deterministic learning algorithm) while the value of \( e_{j} \)
is not fixed: it is dependent on the random variable \( z_{i} \). Let \( e_{j}(z_{i}) \)
be the derived random variable. Then, the expectation is:
\[
E_{z_{i},z_{j}|S_{ij}}(\hat{e}_{i}-e_{i})(\hat{e}_{j}-e_{j})\]
(implicitly conditioning on \( S_{ij} \)) 
\[
=\sum _{z_{i},z_{j}}\Pr _{D}(z_{i})\Pr _{D}(z_{j})(\hat{e}_{i}(z_{i})-e_{i})(\hat{e}_{j}(z_{j},z_{i})-e_{j}(z_{i}))\]
\[
=\sum _{z_{i}}\Pr _{D}(z_{i})(\hat{e}_{i}(z_{i})-e_{i})\sum _{z_{j}}\Pr _{D}(z_{j})(\hat{e}_{j}(z_{j},z_{i})-e_{j}(z_{i}))\]
 
\[
=\sum _{z_{i}}\Pr _{D}(z_{i})(\hat{e}_{i}(z_{i})-e_{i})[e_{j}(z_{i})(1-e_{j}(z_{i}))+(1-e_{j}(z_{i}))(-e_{j}(z_{i})]\]


(since \( \Pr (\hat{e}_{j}(z_{j})=1|e_{j})=e_{j} \))
\[
=\sum _{z_{i}}\Pr _{D}(z_{i})(\hat{e}_{i}(z_{i})-e_{i})*0\]


\[
=0\]
Since this sum is zero regardless of the values of all other random variables,
the cross product terms all have expectation zero. Note that we can extend this
proof to randomized algorithms by conditioning on the random bits of the algorithm
in the above argument. Consequently:
\[
=\sum _{i=1}^{m}E_{(x,y)^{m}\sim D^{m}}\left[ (\hat{e}_{i}-e_{i})^{2}\right] \]
\[
=\sum _{i=1}^{m}e_{i}(1-e_{i})\]
So, all that we must show is: 
\[
me_{\textrm{pv}}(1-e_{\textrm{pv}})\geq \sum _{i=1}^{m}e_{i}(1-e_{i})\]
which follows from Jensen's inequality and the convexity of \( x(1-x) \) on
the interval \( [0,1] \). 
\end{proof}

\section{Deviance analysis}

The second way in which we can show that the progressive validation opponent
is not so strong is by bounding the deviation directly. Surprisingly, we can
prove exactly the same bound as for Hoeffding inequality.

\begin{thm}
\[
\Pr _{(x,y)^{m}\sim D^{m}}(e_{\textrm{pv}}\geq \hat{e}_{\textrm{pv}}+\epsilon )\leq e^{-2m\epsilon ^{2}}\]

\end{thm}
\begin{proof}
(A variant of Chernoff)
\[
\Pr _{(x,y)^{m}\sim D^{m}}(e_{\textrm{pv}}\geq \hat{e}_{\textrm{pv}}+\epsilon )\]
\[
\Leftrightarrow \forall \lambda \, \, \Pr _{(x,y)^{m}\sim D^{m}}(e^{\lambda me_{\textrm{pv}}}\geq e^{\lambda m(\hat{e}_{\textrm{pv}}+\epsilon )})\]
 
\[
\Leftrightarrow \Pr _{(x,y)^{m}\sim D^{m}}(e^{\lambda m(e_{\textrm{pv}}-\hat{e}_{\textrm{pv}}-\epsilon )}\geq 1)\]
 
\[
\leq E_{(x,y)^{m}\sim D^{m}}e^{\lambda m(e_{\textrm{pv}}-\hat{e}_{\textrm{pv}}-\epsilon )}\]
\[
=E_{(x,y)^{m}\sim D^{m}}e^{\lambda (\sum _{i=1}^{m}e_{i}-\hat{e}_{i}-\epsilon )}\]
\[
=\prod _{i=1}^{m}E_{(x,y)\sim D}\left[ e^{\lambda (e_{i}-\hat{e}_{i}-\epsilon )}|\hat{e}_{1},...,\hat{e}_{i-1}\right] \]


The value of \( e^{\lambda (e_{i}-\hat{e}_{i}-\epsilon )} \) is only dependent
on \( \hat{e}_{1},...,\hat{e}_{i-1} \) through the value of \( e_{i} \). For
all possible hypotheses, \( h_{i} \), we know that \( \hat{e}_{i} \) is a
Bernoulli random variable with bias \( e_{i}=\Pr _{D}(h_{i}(x)\neq y) \). This
is true regardless of how we choose \( h_{i} \). Consequently, we have:
\begin{equation}
\label{opt}
=\prod _{i=1}^{m}E_{(x,y)\sim D}\left[ e^{\lambda (e_{i}-\hat{e}_{i}-\epsilon )}\right] 
\end{equation}
 Since this is true for all \( \lambda  \), we can choose the optimal \( \lambda  \).
In general, this is an optimization problem which can be worst-case simplified
with the inequality: 
\[
E_{(x,y)\sim D}e^{\lambda (e_{i}-\hat{e}_{i})}\leq e^{\frac{\lambda ^{2}}{8}}\]
which implies: 
\[
\forall \lambda \, \, \leq \prod _{i=1}^{m}e^{\frac{\lambda ^{2}}{8}-\lambda \epsilon )}\]
This is optimized for \( \frac{2\lambda }{8}=\epsilon  \) which implies \( \lambda =4\epsilon  \)
giving:
\[
\leq \prod _{i=1}^{m}e^{-2\epsilon ^{2}}\]
\[
=e^{-2m\epsilon ^{2}}\]

\end{proof}
Open Problem: Starting with \ref{opt}, derive a bound similar to the relative
entropy Chernoff bound which holds for progressive validation

\end{document}
