Computational Learning Theory

Herbrich(MicrosoftResearch),MarkHerbster(UniversityCollegeLondon), G¿aborLugosi(PompeuFabraUniversity),RonMeir(Technion),ShaharMend- son(AustralianNationalUniv. ),MichaelSchmitt(Ruhr-Universit¿atBochum), RoccoServedio(Harvard),andSantoshVempala(MIT). WealsoacknowledgethecreatorsoftheCyberChairsoftwareformakinga softwarepackagethathelpedthecommitteedoitswork. Local Arrangements, Co-located Conferences Support SpecialthanksgotoourconferencechairArunSharmaandlocalarrangements chairEricMartin(bothatUniv. ofNewSouthWales)forsettingupCOLT2002 inSydney. RochelleMcDonaldandSueLewisprovidedadministrativesupport. ClaudeSammutinhisroleasconferencechairofICMLandprogramco-chair ofILPensuredsmoothcoordinationwiththetwoco-locatedconferences. COLT Community ForkeepingtheCOLTseriesgoing,wethanktheCOLTsteeringcommittee, andespeciallyChairJohnShawe-TaylorandTreasurerJohnCaseforalltheir hardwork. WealsothankStephenKwekformaintainingtheCOLTwebsiteat http://www. learningtheory. org. Sponsoring Institution SchoolofComputerScienceandEngineering,UniversityofNewSouthWales, Australia VIII Thanks and Acknowledgments Referees PeterAuer LisaHellerstein AlainPajor AndrewBarto DanielHerrmann GunnarR¿atsch StephaneBoucheron ColindelaHiguera RobertSchapire OlivierBousquet SeanHolden JohnShawe-Taylor Nicol`oCesa-Bianchi MarcusHutter TakeshiShinohara TapioElomaa SanjayJain DavidShmoys RanEl-Yaniv YuriKalnishkan YoramSinger AllanErskine MakotoKanazawa CarlSmith HenningFernau SatoshiKobayashi FrankStephan J¿urgenForster VladimirKoltchinskii Gy¿orgyTur¿an DeanFoster MattiKä ¿ariai ¿nen PaulVitan ¿yi ClaudioGentile WeeSunLee ManfredWarmuth JudyGoldsmith ShieMannor JonA. Wellner ThoreGraepel RyanO¿Donnell RobertC. Williamson Table of Contents Statistical Learning Theory AgnosticLearningNonconvexFunctionClasses. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Shahar Mendelson andRobertC. Williamson Entropy,CombinatorialDimensionsandRandomAverages. . . . . . . . . . . . . . . . . 14 Shahar