Pascal Massart Concentration Inequalities and Mode

PascalMassartConcentrationInequalitiesandModelSelectionEcoled’Et´edeProbabilit´esdeSaint-FlourXXXIII–2003SpringerBerlinHeidelbergNewYorkHongKongLondonMilanParisTokyoForewordThreeseriesoflecturesweregivenatthe33rdProbabilitySummerSchoolinSaint-Flour(July6–23,2003),bytheProfessorsDembo,FunakiandMassart.ThisvolumecontainsthecourseofProfessorMassart.ThecoursesofProfes-sorsDemboandFunakihavealreadyappearedinvolume1869(seebelow).Wearegratefultotheauthorforhisimportantcontribution.64participantshaveattendedthisschool.31ofthemhavegivenashortlecture.Thelistsofparticipantsandofshortlecturesareenclosedattheendofthevolume.TheSaint-FlourProbabilitySummerSchoolwasfoundedin1971.HerearethereferencesofSpringervolumeswherelecturesofpreviousyearswerepub-lished.AllnumbersrefertotheLectureNotesinMathematicsseries,expectS-50whichreferstovolume50oftheLectureNotesinStatisticsseries.1971:vol3071980:vol9291990:vol15271997:vol17171973:vol3901981:vol9761991:vol15411998:vol17381974:vol4801982:vol10971992:vol15811999:vol17811975:vol5391983:vol11171993:vol16082000:vol18161976:vol5981984:vol11801994:vol16482001:vol1837&18511977:vol6781985/86/87:vol1362&S-502002:vol18401978:vol7741988:vol14271995:vol16902003:vol18691979:vol8761989:vol14641996:vol1665Furtherdetailscanbefoundonthesummerschoolwebsitefindmanyconsis-tencyresultsintheliteratureforsuchcriteria.Theseresultsareasymptoticinthesensethatonedealswithagivennumberofmodelsandthenumberofobservationstendstoinfinity.Weshallgiveanoverviewofanonasymtotictheoryformodelselectionwhichhasemergedduringtheselasttenyears.Invariouscontextsoffunctionestimationitispossibletodesignpenalizedlog-likelihoodtypecriteriawithpenaltytermsdependingnotonlyonthenumberofparametersdefiningeachmodel(asfortheclassicalcriteria)butalsoonthecomplexityofthewholecollectionofmodelstobeconsidered.Theperfor-manceofsuchacriterionisanalyzedvianonasymptoticriskboundsforthecorrespondingpenalizedestimatorwhichexpressthatitperformsalmostaswellasifthebestmodel(i.e.withminimalrisk)wereknown.Forpracticalrelevanceofthesemethods,itisdesirabletogetapreciseexpressionofthepenaltytermsinvolvedinthepenalizedcriteriaonwhichtheyarebased.Thisiswhythisapproachheavilyreliesonconcentrationinequalities,theproto-typebeingTalagrand’sinequalityforempiricalprocesses.Ourpurposewillbetogiveanaccountofthetheoryanddiscusssomeselectedapplicationssuchasvariableselectionorchangepointsdetection.Contents1Introduction...............................................11.1Modelselection.........................................11.1.1Minimumcontrastestimation.......................31.1.2Themodelchoiceparadigm.........................51.1.3Modelselectionviapenalization.....................71.2Concentrationinequalities................................101.2.1TheGaussianconcentrationinequality...............101.2.2Supremaofempiricalprocesses.....................111.2.3Theentropymethod...............................122Exponentialandinformationinequalities..................152.1TheCram´er-Chernoffmethod.............................152.2Sumsofindependentrandomvariables.....................212.2.1Hoeffding’sinequality..............................212.2.2Bennett’sinequality...............................232.2.3Bernstein’sinequality..............................242.3Basicinformationinequalities............................272.3.1Dualityandvariationalformulas....................272.3.2Somelinksbetweenthemomentgeneratingfunctionandentropy......................................292.3.3Pinsker’sinequality................................312.3.4Birg´e’slemma....................................322.4Entropyonproductspaces...............................352.4.1Marton’scoupling.................................362.4.2Tensorizationinequalityforentropy.................402.5φ-entropy...............................................422.5.1Necessaryconditionfortheconvexityofφ-entropy.....442.5.2Adualityformulaforφ-entropy.....................452.5.3Adirectproofofthetensorizationinequality..........482.5.4Efron-Stein’sinequality............................49XContents3Gaussianprocesses........................................533.1Introductionandbasicremarks...........................533.2ConcentrationoftheGaussianmeasureonRN..............563.2.1Theisoperimetricnatureoftheconcentrationphenomenon......................................573.2.2TheGaussianisoperimetrictheorem.................593.2.3Gross’logarithmicSobolevinequality................623.2.4ApplicationtosupremaofGaussianrandomvectors...643.3ComparisontheoremsforGaussianrandomvectors..........663.3.1Slepian’slemma...................................663.4MetricentropyandGaussianprocesses.....................703.4.1Metricentropy....................................7