\begin{thebibliography}{25}
\expandafter\ifx\csname natexlab\endcsname\relax\def\natexlab#1{#1}\fi
\expandafter\ifx\csname url\endcsname\relax
  \def\url#1{{\tt #1}}\fi

\bibitem[Bartlett et~al.(2004)Bartlett, Bousquet, and Mendelson]{BBM}
P.~L. Bartlett, O.~Bousquet, and S.~Mendelson.
\newblock Local rademacher complexities.
\newblock {\em Annals of Statistics}, 2004.

\bibitem[Blum et~al.(1999)Blum, Kalai, and Langford]{Progressive}
A.~Blum, A.~Kalai, and J.~Langford.
\newblock Beating the holdout: Bounds for k-fold and progressive
  cross-validation.
\newblock In {\em Computational Learning Theory (COLT)}, 1999.

\bibitem[Blumer et~al.(1987)Blumer, Ehrenfueucht, Haussler, and Warmuth]{BEHW}
A.~Blumer, A.~Ehrenfueucht, D.~Haussler, and M.~Warmuth.
\newblock Occam's razor.
\newblock {\em Information Processing Letters}, 24:\penalty0 377--380, 1987.

\bibitem[Chernoff(1952)]{chernoff}
H.~Chernoff.
\newblock A measure of asymptotic efficiency of tests of a hypothesis based
  upon the sum of the observations.
\newblock {\em Annals of Mathematical Statistics}, 24:\penalty0 493--507, 1952.

\bibitem[Clopper and Pearson(1934)]{CnP}
C.~J. Clopper and E.~S. Pearson.
\newblock The use of confidence intervals for fiducial limits illustrated in
  the case of the binomial.
\newblock {\em Biometrika}, 26:\penalty0 404--413, 1934.

\bibitem[Devroye et~al.(1996)Devroye, Gyorfi, and Lugosi]{Devroye}
L.~Devroye, L.~Gyorfi, and G.~Lugosi.
\newblock {\em A Probabilistic Theory of Pattern Recognition}.
\newblock Springer-Verlag, New York, 1996.

\bibitem[Floyd and Warmuth(1995)]{FW}
S.~Floyd and M.~Warmuth.
\newblock Sample compression, learnability, and the vapnik-chervonenkis
  dimension.
\newblock {\em Machine Learning}, 21:\penalty0 269--304, 1995.

\bibitem[Herbrich and Graepel(2001)]{kernelize}
R.~Herbrich and T.~Graepel.
\newblock Large scale bayes point machines.
\newblock In {\em Advances in Neural Information System Processing 13 (NIPS)},
  pages 528--534, 2001.

\bibitem[Hoeffding(1963)]{Hoeffding}
W.~Hoeffding.
\newblock Probability inequalities for sums of bounded random variables.
\newblock {\em Journal of the American Statistical Association}, 58:\penalty0
  13--30, 1963.

\bibitem[Joachims()]{svmlight}
T.~Joachims.
\newblock program SVMlight.

\bibitem[Kivinen and Warmuth(1997)]{Online}
J.~Kivinen and M.~Warmuth.
\newblock Additive versus exponentiated gradient updates for linear prediction.
\newblock {\em Information and Computation}, 132(1):\penalty0 1--64, 1997.

\bibitem[Langford()]{bound}
J.~Langford.
\newblock Program {\bf bound}.

\bibitem[Langford(2002)]{TnT}
J.~Langford.
\newblock Combining train set and test set bounds.
\newblock In {\em International Conference on Machine Learning}, 2002.

\bibitem[Langford and Blum(1999)]{MC_journal}
J.~Langford and A.~Blum.
\newblock Microchoice bounds and self bounding learning algorithms.
\newblock {\em Machine Learning}, 1999.

\bibitem[Langford and McAllester(2000)]{Shell}
J.~Langford and D.~McAllester.
\newblock Computable shell decomposition bounds.
\newblock In {\em Computational Learning Theory (COLT)}, 2000.

\bibitem[Langford and Seeger(2001)]{averaging}
J.~Langford and M.~Seeger.
\newblock Bounds for averaging classifiers.
\newblock Technical report, Carnegie Mellon, Department of Computer Science,
  2001.

\bibitem[Langford and Shawe-Taylor(2002)]{PB-margin}
J.~Langford and J.~Shawe-Taylor.
\newblock Pac-bayes \& margins.
\newblock In {\em Neural Information Processing Systems (NIPS)}, 2002.

\bibitem[Littlestone and Warmuth()]{LW}
N.~Littlestone and M.~Warmuth.
\newblock Relating data compression and learnability.

\bibitem[Marchand and Shawe-Taylor(2001)]{SCM}
M.~Marchand and J.~Shawe-Taylor.
\newblock The set covering machine.
\newblock In {\em International Conference on Machine Learning (ICML)}, 2001.

\bibitem[McAllester(1999)]{PB}
D.~McAllester.
\newblock Pac-bayesian model averaging.
\newblock In {\em Computational Learning Theory (COLT)}, 1999.

\bibitem[Seeger(2002)]{Matthias}
M.~Seeger.
\newblock Pac-bayesian generalization error bounds for gaussian process
  classification.
\newblock {\em Journal of Machine Learning Research}, 3:\penalty0 233--269,
  2002.

\bibitem[Seung()]{Seung}
S.~Seung.
\newblock Unpublished notes.

\bibitem[Shawe-Taylor et~al.(1998)Shawe-Taylor, Bartlett, Williamson, and
  Anthory]{SBWA}
J.~Shawe-Taylor, P.~Bartlett, R.~Williamson, and M.~Anthory.
\newblock Structural risk minimization over data-dependent hierarchies.
\newblock {\em IEEE Transactions on Information Theory}, 44(5):\penalty0
  1926--1940, 1998.

\bibitem[Valiant(1984)]{Valiant}
L.G. Valiant.
\newblock A theory of the leuarnable.
\newblock {\em Communications of the ACM}, 27(11):\penalty0 1134--1142, 1984.

\bibitem[Vapnik and Chervonenkis(1971)]{Vapnik}
V.~N. Vapnik and A.~Y. Chervonenkis.
\newblock On the uniform convergence of relative frequencies of events to their
  probabilities.
\newblock {\em Theory of Probability and its Applications}, 16(2):\penalty0
  264--280, 1971.

\end{thebibliography}
