\relax 
\bibstyle{plainnat}
\citation{CriST00}
\citation{FS97}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{527}}
\citation{Pol84}
\citation{Vap98}
\citation{Sau72}
\citation{VC71}
\citation{DGL96}
\citation{Pol84}
\citation{Vap98}
\newlabel{eq:reg}{{1}{528}}
\citation{Bar98}
\citation{SFBL98}
\citation{AnBar99}
\citation{GBSW99}
\citation{Gurvits97}
\citation{WSS99}
\citation{WSS00}
\citation{Vap98}
\citation{PonSch32}
\citation{Kol56}
\citation{KT61}
\@writefile{toc}{\contentsline {section}{\numberline {2}Covering Numbers}{530}}
\newlabel{sec:cover}{{2}{530}}
\newlabel{eq:estimation}{{2}{530}}
\citation{Pol84}
\citation{Pol84}
\citation{Dud84}
\citation{Hau89}
\citation{Vap98}
\citation{Bar98}
\citation{ABCH97}
\citation{Gurvits97}
\citation{Bar98}
\citation{Bar98}
\newlabel{thm:pol84}{{1}{531}}
\newlabel{thm:inf-norm}{{2}{531}}
\citation{TBWA96}
\citation{TBWA96}
\newlabel{eq:inf-norm-pac}{{3}{532}}
\newlabel{cor:gamma_uniform}{{1}{532}}
\citation{Bar98}
\citation{GBSW99}
\citation{Mend01-geom}
\citation{TBWA96}
\citation{WSS99}
\citation{WSS00}
\newlabel{cor:para_uniform}{{2}{533}}
\@writefile{toc}{\contentsline {section}{\numberline {3}Covering Number Bounds for Linear Function Classes}{533}}
\newlabel{sec:linear}{{3}{533}}
\newlabel{eq:lin_loss}{{4}{533}}
\citation{AnBar99}
\citation{Bar93}
\citation{Jon92}
\citation{Bar98}
\citation{LBW96}
\citation{SFBL98}
\newlabel{lem:maurey}{{1}{534}}
\newlabel{thm:p-q-norm}{{3}{534}}
\newlabel{cor:2-2-norm}{{3}{535}}
\citation{GLS01}
\citation{GW98}
\citation{KW97}
\citation{GLS01}
\citation{GLS01}
\citation{ABCH97}
\citation{Bar98}
\citation{Gurvits97}
\citation{TBWA96}
\citation{GLS01}
\newlabel{prop:mistake-bound-pq}{{1}{537}}
\newlabel{thm:pq_online}{{4}{537}}
\citation{WSS00}
\citation{WSS00}
\citation{WSS00}
\citation{GLS01}
\citation{GW98}
\citation{KW97}
\newlabel{lem:infty_mistake}{{2}{539}}
\newlabel{thm:infty_online}{{5}{540}}
\citation{Bar98}
\citation{Bar98}
\newlabel{cor:infty_online}{{4}{541}}
\citation{GLS01}
\citation{JaaMeiJeb00}
\citation{Lit88}
\citation{KW97}
\citation{Zhang00-dualth}
\citation{LeTa91}
\citation{Mend01-geom}
\citation{Gurvits97}
\citation{Zhang00-dualth}
\citation{Todd97}
\citation{AnBar99}
\citation{CriST00}
\citation{Vap98}
\citation{BarSha99}
\citation{CriST00}
\@writefile{toc}{\contentsline {section}{\numberline {4}Some Consequences of Covering Number Bounds}{543}}
\newlabel{sec:example}{{4}{543}}
\newlabel{thm:2norm_margin}{{6}{543}}
\citation{CriST00}
\citation{BarSha99}
\citation{Bar98}
\citation{AnBar99}
\citation{TBWA96}
\citation{LaSe01}
\citation{Mca99}
\citation{SFBL98}
\citation{SFBL98}
\newlabel{thm:entropy_margin}{{7}{544}}
\citation{AnBar99}
\citation{GLS01}
\citation{Mca99}
\citation{Zhang99-colt}
\newlabel{thm:boosting_margin}{{8}{545}}
\@writefile{toc}{\contentsline {section}{\numberline {5}Discussion}{545}}
\newlabel{sec:discussion}{{5}{545}}
\citation{Pol84}
\citation{VC71}
\@writefile{toc}{\contentsline {section}{\numberline {A}Proof of Theorem\nobreakspace  {}2\hbox {}}{546}}
\newlabel{apx:inf-norm}{{A}{546}}
\newlabel{eq:cheby}{{5}{546}}
\citation{Hoe63}
\bibdata{learning,pubc,pubj}
\bibcite{ABCH97}{{1}{1997}{{Alon et~al.}}{{Alon, Ben-David, Cesa-Bianchi, and Haussler}}}
\bibcite{AnBar99}{{2}{1999}{{Anthony and Bartlett}}{{}}}
\bibcite{Bar93}{{3}{1993}{{Barron}}{{}}}
\bibcite{BarSha99}{{4}{1999}{{Bartlett and Shawe-Taylor}}{{}}}
\bibcite{Bar98}{{5}{1998}{{Bartlett}}{{}}}
\bibcite{CriST00}{{6}{2000}{{Cristianini and Shawe-Taylor}}{{}}}
\bibcite{DGL96}{{7}{1996}{{Devroye et~al.}}{{Devroye, Gy{\"o}rfi, and Lugosi}}}
\bibcite{Dud84}{{8}{1984}{{Dudley}}{{}}}
\bibcite{FS97}{{9}{1997}{{Freund and Schapire}}{{}}}
\bibcite{GW98}{{10}{1998}{{Gentile and Warmuth}}{{}}}
\bibcite{GLS01}{{11}{2001}{{Grove et~al.}}{{Grove, Littlestone, and Schuurmans}}}
\bibcite{GBSW99}{{12}{1999}{{Guo et~al.}}{{Guo, Bartlett, Shawe-Taylor, and Williamson}}}
\bibcite{Gurvits97}{{13}{1997}{{Gurvits}}{{}}}
\bibcite{Hau89}{{14}{1989}{{Haussler}}{{}}}
\bibcite{Hoe63}{{15}{1963}{{Hoeffding}}{{}}}
\bibcite{JaaMeiJeb00}{{16}{2000}{{Jaakkola et~al.}}{{Jaakkola, Meila, and Jebara}}}
\bibcite{Jon92}{{17}{1992}{{Jones}}{{}}}
\bibcite{KW97}{{18}{1997}{{Kivinen and Warmuth}}{{}}}
\bibcite{Kol56}{{19}{1956}{{Kolmogorov}}{{}}}
\bibcite{KT61}{{20}{1961}{{Kolmogorov and Tihomirov}}{{}}}
\bibcite{LaSe01}{{21}{2001}{{Langford and Seeger}}{{}}}
\bibcite{LeTa91}{{22}{1991}{{Ledoux and Talagrand}}{{}}}
\bibcite{LBW96}{{23}{1996}{{Lee et~al.}}{{Lee, Bartlett, and Williamson}}}
\bibcite{Lit88}{{24}{1988}{{Littlestone}}{{}}}
\bibcite{Mca99}{{25}{1999}{{McAllester}}{{}}}
\bibcite{Mend01-geom}{{26}{2001}{{Mendelson}}{{}}}
\bibcite{Pol84}{{27}{1984}{{Pollard}}{{}}}
\bibcite{PonSch32}{{28}{1932}{{Pontriagin and Schnirelmann}}{{}}}
\bibcite{Sau72}{{29}{1972}{{Sauer}}{{}}}
\bibcite{SFBL98}{{30}{1998}{{Schapire et~al.}}{{Schapire, Freund, Bartlett, and Lee}}}
\bibcite{TBWA96}{{31}{1998}{{Shawe-Taylor et~al.}}{{Shawe-Taylor, Bartlett, Williamson, and Anthony}}}
\bibcite{Todd97}{{32}{1997}{{Todd}}{{}}}
\bibcite{Vap98}{{33}{1998}{{Vapnik}}{{}}}
\bibcite{VC71}{{34}{1971}{{Vapnik and Chervonenkis}}{{}}}
\bibcite{WSS99}{{35}{1999}{{Williamson et~al.}}{{Williamson, Smola, and Sch\"{o}lkopf}}}
\bibcite{WSS00}{{36}{2000}{{Williamson et~al.}}{{Williamson, Smola, and Sch\"{o}lkopf}}}
\bibcite{Zhang99-colt}{{37}{1999}{{Zhang}}{{}}}
\bibcite{Zhang00-dualth}{{38}{2002}{{Zhang}}{{}}}