Inégalités de concentration

Master 2 Master Modélisation Aléatoire (6 ECTS) 2009-2011

On s”intéresse aux fonctions d”une collection de variables aléatoires indépendantes X1,X2,…,Xn. Ces fonctions généralisent les sommes de variables aléatoires indépendantes. Ces fonctions sont sujettes au phénomène de concentration de la mesure :
si la fonction F ne dépend pas trop de chacun de ces arguments, alors elle se concentre autour de son espérance ou de sa médiane (qui sont proches). Depuis une vingtaine d”année, notre compréhension de ce phénomène a fait de grands progrès. Les inégalités de concentration sont devenues un outil standard d”analyse en Statistique, notamment en apprentissage. Le phénomène de concentration de la mesure touche des questions mathématiques très variées : analyse, géométrie, phénomène de seuils …

Le cours est (largement) tiré de Concentration inequalities, a non-asymptotic theory of independence.

  • Sommaire

    Variance : Inégalités d’Efron-Stein et applications

    L’inégalité d”Efron-Stein affirme que l”estimateur Jackknife de la variance est pessimiste. C”est un outil simple, facile à mettre en oeuvre et remarquablement utile. Cet outil permet d”établir des versions faibles du phénomène de concentration de la mesure.

    Inégalités de théorie de l”information

    La variance est un cas particulier de fonctionnelle vérifiant une propriété de tensorisation. Cette propriété est aussi vérifiée par l”entropie, l”entropie relative et d”autres quantités issues de la théorie de l”information.

    Inégalités de Sobolev logarithmiques et concentration gaussienne

    La tensorisation de l”entropie relative permet, avec un peu de calcul, d”établir des inégalités fonctionnelles très fécondes, les inégalités de Sobolev logarithmiques. Celles ci permettent en retour de majorer les moments exponentielles de fonctions régulières de vecteurs gaussiens. Elles constituent une voie d”accès facile au phénomène de concentration de la mesure gaussienne et par extension au phénomène de concentration de la mesure dans les espaces produits.

    La méthode entropique et les fonctionnelles auto-majorées

    Starting from logarithmic Sobolev inequalities, it is possible to build exponential versions of the so-called Efron-Stein inequalities.

    Suprema de processus empiriques et applications

    Talagrand’s inequality provides a functional generalization of the (very useful) exponential inequalities due to Bernstein and Bennett.

  • Références

    Concentration Inequalities: S. Boucheron, G. Lugosi and P. Massart.
    Oxford University Press.

    S. Boucheron, O. Bousquet, and G. Lugosi. Machine Learning Summer School 2003, volume 3176 of LNAI, chapter Concentration inequalities, pages 169-207. Springer-Verlag, 2004.
    Massart, P. Concentration inequalities and model selection. Ecole d”été de Probabilités de Saint-Flour 2003. Lecture Notes in Mathematics, Springer

  • Motivations

    Pour comprendre l”intérêt des inégalités stochastiques lorsqu”on travaille dans le
    domaine des statistiques ou de l”informatique, envisageons le problème du routage aléatoire dans le cube
    (posé, il y vingt ans par Brebner et Valiant). Sur un hypercube de dimension n,
    on associe à chaque sommet un autre sommet tiré uniformément au hasard. Pour chaque
    paire de sommets construite de cette façon, on choisit un chemin de longueur minimale.
    Les chemins sont susceptibles de se croiser, et un excès de croisements en un point
    conduit à une congestion. On souhaite contrôler le nombre maximal de chemins qui passent
    par un sommet arbitraire. Il s”agit d”une variable aléatoire, fonction assez compliquée
    d””un grand nombre 2^n de variables aléatoires indépendantes (le choix des 2^n
    chemins). Comment l”étudier ? Une méthode éprouvée consiste à analyser séparemment
    l”espérance de cette congestion maximale et les fluctuations autour de cette espérance.

    L”espérance se contrôle le plus souvent à l”aide d”arguments ad hoc. Ici, il s”agit du maximum
    d”un grand nombre de variables binomiales au comportement presque Poissonien. En Statistiques,
    on invoque des techniques de chaînage pour traiter des situations comparables. En revanche,
    les fluctuations autour de l”espérance peuvent être traitées par des approches assez systématiques
    qui relèvent de ce que l”on nomme aujourd”hui la théorie de la concentration de la mesure.

  • Videos