Computational Learning Theory

ThisvolumecontainspaperspresentedattheFifteenthAnnualConferenceon ComputationalLearningTheory(COLT2002)heldonthemaincampusofthe UniversityofNewSouthWalesinSydney,AustraliafromJuly8to10,2002. Naturally,thesearepapersinthe?eldofcomputationallearningtheory,a- search?elddevotedtostudyingthedesignandanalysisofalgorithmsformaking predictionsaboutthefuturebasedonpastexperiences,withanemphasisonr- orousmathematicalanalysis. COLT2002wasco-locatedwiththeNineteenthInternationalConferenceon MachineLearning(ICML2002)andwiththeTwelfthInternationalConference onInductiveLogicProgramming(ILP2002). NotethatCOLT2002wasthe?rstconferencetotakeplaceafterthefull mergeroftheAnnualConferenceonComputationalLearningTheorywiththe EuropeanConferenceonComputationalLearningTheory. (In2001ajointc- ferenceconsistingofthe5thEuropeanConferenceonComputationalLearning Theoryandthe14thAnnualConferenceonComputationalLearningTheory washeld;thelastindependentEuropeanConferenceonComputationalLea- ingTheorywasheldin1999. ) ThetechnicalprogramofCOLT2002contained26papersselectedfrom 55submissions. Inaddition,ChristosPapadimitriou(UniversityofCaliforniaat Berkeley)wasinvitedtogiveakeynotelectureandtocontributeanabstractof hislecturetotheseproceedings. TheMarkFulkAwardispresentedannuallyforthebestpapercoauthored byastudent. Thisyear’sawardwaswonbySandraZillesforthepaper“Merging UniformInductiveLearners. ” April2002 JyrkiKivinen RobertH. Sloan Thanks and Acknowledgments Wegratefullythankalltheindividualsandorganizationsresponsibleforthe successoftheconference. ProgramCommittee Weespeciallywanttothanktheprogramcommittee:DanaAngluin(Yale), JavedAslam(Dartmouth),PeterBartlett(BIOwulfTechnologies),ShaiBen- David(Technion),JohnCase(Univ. ofDelaware),PeterGru¨nwald(CWI),Ralf 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. . . . .