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

\bibitem[Ambartzumian(1990)]{ambartzumian}
R.V. Ambartzumian.
\newblock {\em Factorization Calculus and Geometric Probability}.
\newblock Cambridge University Press, Cambridge, 1990.

\bibitem[Ash(1972)]{ash}
R.B. Ash.
\newblock {\em Real Analysis and Probability}.
\newblock Academic Press, New York, 1972.

\bibitem[Bartlett et~al.(2000)Bartlett, Boucheron, and Lugosi]{ba-bo-lu}
P.L. Bartlett, S.~Boucheron, and G.~Lugosi.
\newblock Model selection and error estimation.
\newblock {\em preprint}, 2000.
\newblock (A shorter version of this paper was apparently presented at COLT
  2000.).

\bibitem[Boucheron et~al.(2000)Boucheron, Lugosi, and Massart]{bo-lu-ma}
S.~Boucheron, G.~Lugosi, and P.~Massart.
\newblock A sharp inequality with applications.
\newblock {\em Random Structures and Algorithms}, 16:\penalty0 277--292, 2000.

\bibitem[Buescher and Kumar(1996)]{bu-ku}
K.~Buescher and P.~Kumar.
\newblock Learning by canonical smooth estimation, part ii: Learning and choice
  of model complexity.
\newblock {\em IEEE Transactions on Automatic Control}, 41:\penalty0 557--569,
  1996.

\bibitem[Cannon and Cowen(2000)]{ca-co}
A.H. Cannon and L.J. Cowen.
\newblock Approximation algorithms for the class cover problem.
\newblock In {\em Proceedings of the 6th International Symposium on Mathematics
  and Artificial Intelligence}, 2000.

\bibitem[Cortes and Vapnik(1995)]{Cortes95}
C.~Cortes and V.~Vapnik.
\newblock Support-vector networks.
\newblock {\em Machine Learning}, 20:\penalty0 273--297, 1995.

\bibitem[Cover(1965)]{cover}
T.~Cover.
\newblock Geometrical and statistical properties of systems of linear
  inequalities with applications in pattern recognition.
\newblock {\em IEEE Transactions on Electronic Computers}, 14:\penalty0
  326--334, 1965.

\bibitem[Cristianini and Shawe-Taylor(2000)]{Crist00}
N.~Cristianini and J.~Shawe-Taylor.
\newblock {\em An Introduction to Support Vector Machines and Other
  Kernel-based Learning Methods}.
\newblock Cambridge University Press, Cambridge, 2000.

\bibitem[Devroye(1988)]{devroye}
L.~Devroye.
\newblock Automatic pattern recognition: A study of the probability of error.
\newblock {\em IEEE Transactions on Pattern Recognition and Machine
  Intelligence}, 10\penalty0 (4):\penalty0 530--543, 1988.

\bibitem[Devroye et~al.(1996)Devroye, Gy{\"{o}}rfi, and Lugosi]{de-gy-lu}
L.~Devroye, L.~Gy{\"{o}}rfi, and G.~Lugosi.
\newblock {\em A Probabilistic Theory of Pattern Recognition}.
\newblock Springer-Verlag, 1996.

\bibitem[Dudley(1999)]{dudley}
R.M. Dudley.
\newblock {\em Uniform Central Limit Theorems}.
\newblock Cambridge University Press, New York, 1999.

\bibitem[Freund(1998)]{freund}
Y.~Freund.
\newblock Self bounding learning algorithms.
\newblock In {\em COLT; Proceedings of the Workshop on Computational Learning
  Theory}. Morgan Kaufmann, 1998.

\bibitem[Gat(1999)]{gat}
Y.~Gat.
\newblock A bound concerning the generalization ability of a certain class of
  learning algorithms.
\newblock Technical Report 548, University of California, Berkeley, 1999.

\bibitem[Hochbaum(1997)]{Hoc97a}
Dorit~S. Hochbaum.
\newblock {\em Approximation Algorithms for NP-Hard Problems}.
\newblock PWS Publishing Company, 1997.

\bibitem[Hush and Scovel(2001)]{hu-sc}
D.~Hush and C.~Scovel.
\newblock On the vc dimension of bounded margin classifiers.
\newblock {\em Machine Learning}, 45:\penalty0 33--44, 2001.

\bibitem[Johnson and Preparata(1978)]{Joh78a}
D.S. Johnson and F.P. Preparata.
\newblock The densest hemisphere problem.
\newblock {\em Theoretical Computer Science}, 6:\penalty0 93--107, 1978.

\bibitem[Koltchinskii(2001)]{koltchinskii}
V.I. Koltchinskii.
\newblock Rademacher penalties and structural risk minimization.
\newblock {\em IEEE Transactions on Information Theory}, 47\penalty0
  (5):\penalty0 1902--1914, 2001.

\bibitem[Koltchinskii et~al.(2000)Koltchinskii, Abdallah, Ariola, Dorato, and
  Panchenko]{ko-ab-ar-do-pa}
V.I. Koltchinskii, C.T. Abdallah, M.~Ariola, P.~Dorato, and D.~Panchenko.
\newblock Improved sample complexity estimates for statistical learning control
  of uncertain systems.
\newblock {\em IEEE Transactions on Automatic Control}, 45\penalty0
  (12):\penalty0 2383--2388, 2000.

\bibitem[Marchette and Priebe()]{ma-pr}
D.J. Marchette and C.E. Priebe.
\newblock Characterizing the scale dimension of a high dimensional
  classification problem.
\newblock {\em Pattern Recognition}.
\newblock forthcoming.

\bibitem[Priebe et~al.(2001)Priebe, DeVinney, and Marchette]{pr-de-ma}
C.E. Priebe, J.G. DeVinney, and D.J. Marchette.
\newblock On the distribution of the domination number for random class cover
  catch digraphs.
\newblock {\em Statistics and Probability Letters}, 55\penalty0 (3):\penalty0
  239--246, 2001.

\bibitem[Rogers(1978)]{rogers}
L.C.G. Rogers.
\newblock The probability that two samples in the plane have disjoint convex
  hulls.
\newblock {\em Journal of Applied Probability}, 15:\penalty0 790--802, 1978.

\bibitem[Sch{\"o}lkopf(2001)]{Sch01}
B.~Sch{\"o}lkopf.
\newblock The kernel trick for distances.
\newblock {\em Advances in Neural Information Processing Systems}, 13:\penalty0
  301--307, 2001.
\newblock Editors: T.K. Leen, T.G. Dietterich, and V. Tresp.

\bibitem[Serfling(1974)]{serfling}
R.J. Serfling.
\newblock Probability inequalities for the sum in sampling without replacement.
\newblock {\em Annals of Statistics}, 2\penalty0 (1):\penalty0 39--48, 1974.

\bibitem[Shawe-Taylor et~al.(1998)Shawe-Taylor, Bartlett, Williamson, and
  Anthony]{sh-ba-wi-an}
J.~Shawe-Taylor, P.L. Bartlett, R.C. Williamson, and M.~Anthony.
\newblock Structural risk minimization over data-dependent hierarchies.
\newblock {\em IEEE Transactions on Information Theory}, 44\penalty0
  (5):\penalty0 1926--1940, 1998.
\newblock Also appeared in {\em NeuroCOLT Technical Report}, NC-TR-96-053,
  1996.

\bibitem[Shawe-Taylor and Cristianini(2000)]{Sha00a}
J.~Shawe-Taylor and N.~Cristianini.
\newblock On the generalization of soft margin algorithms.
\newblock Technical Report NC2-TR-2000-082, NeuroCOLT2 Technical Report Series,
  2000.

\bibitem[Shiryaev(1980)]{shiryaev}
A.N. Shiryaev.
\newblock {\em Probability}.
\newblock Springer-Verlag, New York, 1980.

\bibitem[Vapnik(1998)]{Vap98a}
V.N. Vapnik.
\newblock {\em Statistical Learning Theory}.
\newblock John Wiley and Sons, Inc., New York, 1998.

\bibitem[Young and Householder(1938)]{You38a}
G.~Young and A.S. Householder.
\newblock Discussion of a set of points in terms of their mutual distances.
\newblock {\em Psychometrika}, 3:\penalty0 19--22, 1938.

\end{thebibliography}