concentration of measure inequality

《concentration of measure inequality》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Concentration-of-measureinequalitiesLecturenotesbyGáborLugosiJune25,2009AbstractThistextcontainssomeofthematerialpresentedattheSummerSchoolonMachineLearningattheAustralianNationalUniversity,Canberra,2003,attheWorkshoponCombinatorics,ProbabilityandAlgorithmsattheCentredeRe

2、cherchesMathématiques,UniversitédeMontréal,andattheWinterSchoolonProbabilisticMethodsinHighDimensionPhenomena,Toulouse,2005.DepartmentofEconomics,PompeuFabraUniversity,RamonTriasFargas25-27,08005Barcelona,Spain(email:lugosi@upf.es).Contents1.Introduction2.BasicsExercises3

3、.Sumsofindependentrandomvariables3.1Hoeding'sinequality3.2Bernstein'sinequalityExercises4.TheEfron-Steininequality4.1Functionswithboundeddierences4.2Self-boundingfunctions4.3CongurationfunctionsExercises5.Theentropymethod5.1Basicinformationtheory5.2Tensorizationoftheent

4、ropy5.3LogarithmicSobolevinequalities5.4Firstexample:boundeddierencesandmore5.5Exponentialinequalitiesforself-boundingfunctions5.6Combinatorialentropies5.7VariationsonthethemeExercises6.Concentrationofmeasure6.1Boundeddierencesinequalityrevisited6.2Convexdistanceinequali

5、ty6.3ExamplesExercisesReferences11IntroductionThelawsoflargenumbersofclassicalprobabilitytheorystatethatsumsofindependentrandomvariablesare,underverymildconditions,closetotheirexpectationwithalargeprobability.Suchsumsarethemostbasicexamplesofrandomvariablesconcentratedarou

6、ndtheirmean.Morerecentresultsrevealthatsuchabehaviorissharedbyalargeclassofgeneralfunctionsofindependentrandomvariables.Thepurposeofthesenotesistogiveanintroductiontosomeofthesegeneralconcentrationinequalities.Theinequalitiesdiscussedinthesenotesboundtailprobabilitiesofgen

7、-eralfunctionsofindependentrandomvariables.Severalmethodshavebeenknowntoprovesuchinequalities,includingmartingalemethodspioneeredinthe1970'sbyMilman,seeMilmanandSchechtman[61](seetheinu-entialsurveysofMcDiarmid[58],[59]andChungandLu[?]forsomenewdevelpments),information-th

8、eoreticmethods(seeAlhswede,Gács,andKörner[1],Marton[52],[53],[54],Dembo[24],Massart[55]an