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 MattiKa¨ ¨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 Mendelson andRoman Vershynin GeometricParametersofKernelMachines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Shahar Mendelson LocalizedRademacherComplexities. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 PeterL. Bartlett, Olivier Bousquet, and Shahar Mendelson SomeLocalMeasuresofComplexityofConvexHulls andGeneralizationBounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Olivier Bousquet, Vladimir Koltchinskii, and DmitriyPanchenko OnlineLearning PathKernelsandMultiplicativeUpdates. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 Eiji Takimoto andManfred K. Warmuth PredictiveComplexityandInformation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 Michael V. Vyugin andVladimir V. V'yugin MixabilityandtheExistenceofWeakComplexities. . . . . . . . . . . . . . . . . . . . . . . 105 YuriKalnishkan andMichael V. Vyugin ASecond-OrderPerceptronAlgorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 Nicolo ` Cesa-Bianchi, AlexConconi, and Claudio Gentile TrackingLinear-ThresholdConceptswithWinnow . . . . . . . . . . . . . . . . . . . . . . . . 138 Chris Mesterharm Inductive Inference LearningTreeLanguagesfromText. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 HenningFernau PolynomialTimeInductiveInferenceofOrderedTreePatterns withInternalStructuredVariablesfromPositiveData . . . . . . . . . . . . . . . . . . . . 169 YusukeSuzuki, RyutaAkanuma, Takayoshi Shoudai, TetsuhiroMiyahara, andTomoyuki Uchida X Table of Contents InferringDeterministicLinearLanguages. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 Colin dela HigueraandJoseOncina MergingUniformInductiveLearners. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 SandraZilles TheSpeedPrior:ANewSimplicityMeasure YieldingNear-OptimalComputablePredictions. . . . . . . . . . . . . . . . . . . . . . . . . . . 216 J¨ urgenSchmidhuber PAC Learning NewLowerBoundsforStatisticalQueryLearning. . . . . . . . . . . . . . . . . . . . . . . . 229 KeYang ExploringLearnabilitybetweenExactandPAC. . . . . . . . . . . . . . . . . . . . . . . . . . . 244 Nader H. Bshouty, Je?reyC. Jackson, andChristino Tamon PACBoundsforMulti-armedBanditandMarkovDecisionProcesses. . . . . | Computational Learning Theory by Jyrki Kivinen, Paperback | Indigo Chapters