%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[oneside,english]{amsart}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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
 \theoremstyle{plain}

\usepackage{babel}
\makeatother
\begin{document}

\title{A Tight Transduction to Induction Reduction}

\maketitle

\section{First Attempt}

This attempt is inadequate because it has (essentially) been done
elsewhere.

The PAC-MDL bound on the test error rate of a chosen classifier is:
\[
\Pr_{S_{\textrm{test}},S_{\textrm{train}}}\left(\hat{c}_{\textrm{test}}\leq\overline{\textrm{Hyp}}(\hat{c}_{\textrm{train}},|S_{\textrm{test}}|,\delta)\right)\geq1-\delta\]
We also know that for every classifier: \[
\Pr_{S_{\textrm{test}},S_{\textrm{train}}}\left(\hat{c}_{\textrm{test}}\leq\textrm{Bin}(c_{D},|S_{\textrm{test}}|,1-\delta)\right)\geq1-\delta\]


\begin{thm}
\[
\Pr_{S_{\textrm{train}}}\left(c_{D}\leq\overline{\textrm{Bin}}\left(\overline{\textrm{Hyp}}\left(\hat{c}_{\textrm{train}},|S_{\textrm{test}}|,\frac{\delta}{2}\right),\frac{1}{2}\right)\right)\geq1-\delta\]

\end{thm}
\begin{proof}
\[
E_{X,Y}I(\Phi(X,Y))>1-\epsilon\]


\[
\Rightarrow\forall\alpha>1:\,\,\, E_{X}I(E_{Y}I(\Phi(X,Y))>1-\alpha\epsilon)>1-\frac{1}{\alpha}\]
so: \[
\Pr_{S_{\textrm{test}},S_{\textrm{train}}}\left(\hat{c}_{\textrm{test}}\leq\overline{\textrm{Hyp}}(\hat{c}_{\textrm{train}},|S_{\textrm{test}}|,\frac{\delta}{2})\right)\geq1-\frac{\delta}{2}\]
implies: \[
\Pr_{S_{\textrm{train}}}\left(\Pr_{S_{\textrm{test}}}\left(\hat{c}_{\textrm{test}}\leq\overline{\textrm{Hyp}}(\hat{c}_{\textrm{train}},|S_{\textrm{test}}|,\frac{\delta}{2})\right)>\frac{1}{2}\right)\geq1-\delta\]


\[
\Pr_{S_{\textrm{train}}}\left(\textrm{Bin}(c_{D},\frac{1}{2})\geq\overline{\textrm{Hyp}}(\hat{c}_{\textrm{train}},|S_{\textrm{test}}|,\frac{\delta}{2})\right)\geq1-\delta\]


\[
\Pr_{S_{\textrm{train}}}\left(c_{\textrm{D}}\leq\overline{\textrm{Bin}}(\overline{\textrm{Hyp}}(\hat{c}_{\textrm{train}},|S_{\textrm{test}}|,\frac{\delta}{2}),\frac{1}{2})\right)\geq1-\delta\]

\end{proof}

\section{Second Attempt?}
\end{document}
