Concentration inequalities

1 Concentration inequalitiesA nonasymptotic theory of independenceSt ephane BoucheronParis 7G abor LugosiICREA and Universitat Pompeu FabraPascal MassartOrsayCLARENDON Concentration ideas developed during the last century in various partsof mathematics, including functional analysis, probability theory and statisticalmechanics, areas typically dealing with models involving an infinite number ofvariables. After early observations, and in particular a geometric interpretationof the law of large numbers by E. Borel, the real birth of measure concentrationtook place in the early seventies with the new proof by V. Milman, relying onL evy s inequality (of isoperimetric nature), of Dvoretzky s theorem on sphericalsections of convex bodies in high dimension. The inherent concept of measureconcentration emphasized by V.

2 Milman through this proof turned out as oneof the main achievements of analysis of the second part of the last century. Itopened a posteriori completely new perspectives and developments with appli-cations to various fields of mathematics. In particular, prompted by the conceptand results, M. Talagrand undertook in the 80 s and 90 s a deep investigationof Concentration inequalities for product measures, emphasizing a revolution-ary new look at independence. Viewing namely random variables depending (ina smooth way) on the influence of many independent random variables (butnot too much on any of them) as essentially constant led him to groundbreak-ing achievements and striking applications. With the tool in particular of thecelebrated convex distance inequality, M. Talagrand developed applications tocombinatorial probability, statistical mechanics and empirical processes.

3 Simul-taneously, the entropic method, relying on an early observation by I. Herbst inthe context of logarithmic Sobolev inequalities and developing information theo-retic ideas, became a powerful additional and flexible method in the investigationof new Concentration then, the Concentration -of-measure phenomenon spread out to an im-pressively wide range of illustrations and applications, and became a central tooland viewpoint in the quantitative analysis of a number of asymptotic propertiesin numerous topics of interest including geometric analysis, probability theory,statistical mechanics, mathematical statistics and learning theory, random ma-trix theory or quantum information theory, stochastic dynamics, randomizedalgorithms, complexity book by S. Boucheron, G. Lugosi and P. Massart is a most welcomeand complete account on the modern developments of Concentration inequalitiesin the context of the probabilistic method.

4 The monograph covers most of theimportant and recent developments, with a constant care on illustrations and ap-plications which make the theory so fruitful and attractive. The emphasis put oninformation theoretic methods is one main features of the exposition, with con-siderable benefit in the approach to a number of fundamental results and tools,such as for example the convex distance inequality or sharp bounds on empiricalviPrefaceprocesses of fundamental importance in statistical applications. The monographcovers further basic and most illustrative examples of the current research, in-cluding dimension reduction, random matrices, Boolean analysis, transportationinequalities or isoperimetric-type bounds. The style adopted by the authors is aperfect balance from basic and classical material up to the most sophisticatedand powerful results, always accessible and clearly reachable.

5 Young and con-firmed scientists, independently of their background, will find with this book theideal path to the powerful ideas and tools of Concentration inequalities , suggestedand illustrated with the most relevant applications and is an honour and a pleasure to write this preface to this wonderful book,sure to be a huge LedouxUniversit e de ToulouseCONTENTSP reface by Michel Ledouxv1 of independent random variables and the Concentration -of-measure entropy transportation Basic moments to Cram er-Chernoff random random maximal s s s projections and the Johnson-Lindenstrauss Association Minkowski s Bibliographical Exercises463 Bounding the Efron-Stein with bounded examples and convex Poincar e tail bounds via the Efron-Stein Gaussian Poincar e proof of the Efron-Stein inequality based on Exercises774 Basic information entropy and relative on product spaces and the chain s isoperimetric inequality on the binary s inequality for relative of the of general random and variational A transportation Pinsker

6 S Birg e s Sub-additivity of entropy: the general The Brunn-Minkowski Bibliographical Exercises1095 Logarithmic Sobolev Bernoulli s argument: Concentration on the Gaussian logarithmic Sobolev Concentration : the Tsirelson-Ibragimov-Sudakov Concentration inequality for suprema of Gaussian random performance bound for the : the Bonami-Beckner The largest eigenvalue of random Bibliographic Exercises1516 The entropy bounded differences on bounded logarithmic Sobolev bounded for the lower of convex Lipschitz inequalities for self-bounding modified logarithmic Sobolev Efron-Stein A modified logarithmic Sobolev inequality for the Poisson Weakly self-bounding Proof of Lemma Some Janson s Bibliographic Exercises2027 Concentration and evy s classical isoperimetric isoperimetric inequality in the distance Lipschitz functions The transportation bounded differences inequality differences in quadratic of Marton s conditional transportation convex distance inequality s Gaussian transportation.

7 A general induction Influences and threshold fundamental inequalities for Fourier analysis and a variance Isoperimetry on the hypercube and Gaussian Bobkov s inequality for functions on the An isoperimetric inequality on the binary Asymmetric Bernoulli distributions and threshold The Gaussian isoperimetric Lipschitz functions of Gaussian random Bibliographical Exercises29911 The variance of suprema of empirical General upper bounds for the Nemirovski s The symmetrization and contraction Weak and wimpy Unbounded Bibliographic Exercises32612 Suprema of empirical processes: exponential An extension of Hoeffding s A Bernstein-type inequality for bounded A symmetrization Bousquet s inequalityinequality!BousquetBousquet s inequal-ity for suprema of empirical Non-identically distributed summands and left-tail Chi-square statistics and quadratic Bibliographic Exercises34313 The expected value of suprema of empirical Classical Lower bounds for Gaussian Chaining and Gaussian and Rademacher averages of symmetric variations of Nemirovski s Random projections of sparse and large Normalized processes.

8 Slicing and Relative deviations Risk bounds in Bibliographic Exercises38414 -entropy and its From -entropies to -Sobolev -Sobolev inequalities for Bernoulli random Bibliographical Exercises41215 Moment Generalized Efron-Stein Moments of functions of independent random Some variants and Sums of random Suprema of empirical Conditional Rademacher Bibliographical Exercises431 References434 Subject Index461 Author Index4691 INTRODUCTIONThe topic of this book is the study of random fluctuations of functions of inde-pendent random inequalitiesquantify such statements,typically by bounding the probability that such a function differs from its ex-pected value (or from its median) by more than a certain search for Concentration inequalities has been a topic of intensive re-search in the last decades in a variety of areas because of their importance innumerous applications.

9 Among the areas of applications, without trying to beexhaustive, we mention statistics, learning theory, discrete mathematics, statisti-cal mechanics, random matrix theory, information theory, and Concentration properties for sums of independent random variableswere thoroughly studied and fairly well understood in classical probability theory,powerful tools to handle more general functions of independent random variableswere not introduced until the appearance of martingale methods in the 1970 s,see Yurinskii (1976), Maurey (1979), Milman and Schechtman (1986), Shamirand Spencer (1987), McDiarmid (1989).A remarkable series of papers in the mid-1990 s by Michel Talagrand pro-vided major new insight to the problem and opened many exciting new researchdirections. The main principle, as summarized by Talagrand (1995), is that arandom variable that smoothly depends on the influence of many independentrandom variables satisfies Chernoff type bounds.

10 This book provides answers tothe natural question hidden behind this citation: what kind of smoothness condi-tions should we put on a functionfof independent random variablesX1,..,Xnin order to get Concentration bounds forZ=f(X1,..,Xn) around its mean orits median?In this introductory chapter we briefly review the history of the subject andoutline the contents, as an appetizer for the rest of the getting started, we emphasize that one of the main driving forcesof the development of the theory was the need of understanding random fluc-tuations of suprema of empirical processes defined as follows. LetTbe a setthat for now we assume to be finite and letX1,..,Xnbe independent randomvectors taking values inRT. We are interested in Concentration properties ofsups T ni=1Xi,s(whereXi= (Xi,s)s T).