No description available.

In 1943, Littlewood and Offord proved the first anti-concentration result for sums of independent random variables. Their result has since then been strengthened and generalised by generations of researchers, with applications in several areas of mathematics. In this paper, we present the first non-abelian analogue of the Littlewood Offord result, a sharp anti-concentration inequality for products of independent random variables. (C) 2016 Elsevier Inc. All rights reserved.

In this thesis we consider concentration inequalities and the concentration of measure phenomenon from a variety of angles. Sharp tail bounds on the deviation of Lipschitz functions of independent random variables about their mean are well known. We consider variations on this theme for dependent variables on the Boolean cube. In recent years negatively associated probability distributions have been studied as potential generalizations of independent random variables. Results on this class of distributions have been sparse at best, even when restricting to the Boolean cube. We consider the class of negatively associated distributions topologically, as a subset of the general class of probability measures. Both the weak (distributional) topology and the total variation topology are considered, and the simpler notion of negative correlation is investigated. The concentration of measure phenomenon began with Milman's proof of Dvoretzky's theorem, and is therefore intimately connected to the field of high-dimensional convex geometry. Recently this field has found application in the area of compressed sensing. We consider these applications and in particular analyze the use of Gordon's min-max inequality in various compressed sensing frameworks, including the Dantzig selector and the matrix uncertainty selector. Finally we consider the use of concentration inequalities in developing a theoretically sound anomaly detection algorithm. Our method uses a ranking procedure based on KNN graphs of given data. We develop a max-margin learning-to-rank framework to train limited complexity models to imitate these KNN scores. The resulting anomaly detector is shown to be asymptotically optimal in that for any false alarm rate α, its decision region converges to the α-percentile minimum volume level set of the unknown underlying density.

Cette thèse s'inscrit dans le domaine des matrices aléatoires et des techniques de grandes déviations. On s'attachera dans un premier temps à donner des inégalités de déviations pour différentes fonctionnelles du spectre qui reflètent leurs comportement de grandes déviations, pour des matrices de Wigner vérifiant une propriété de concentration indexée par un paramètre alpha ∈ (0,2]. Nous présenterons ensuite le principe de grandes déviations obtenu pour la plus grande valeur propre des matrices de Wigner sans queues Gaussiennes, dans la lignée du travail de Bordenave et Caputo, puis l'étude des grandes déviations des traces de matrices aléatoires que l'on aborde dans trois cas : le cas des beta-ensembles, celui des matrices de Wigner Gaussiennes, et enfin des matrices de Wigner sans queues Gaussiennes. Le cas Gaussien a été l'occasion de revisiter la preuve de Borell et Ledoux des grandes déviations des chaos de Wiener, que l'on prolonge en proposant un énoncé général de grandes déviations qui nous permet donner une autre preuve des principes de grandes déviations des matrices de Wigner sans queues Gaussiennes. Enfin, nous donnons une nouvelle preuve des grandes déviations de la mesure spectrale empirique des beta-ensembles associés à un potentiel quadratique, qui ne repose que sur leur représentation tridiagonale. / This thesis falls within the theory of random matrices and large deviations techniques. We mainly consider large deviations problems which involve a heavy-tail phenomenon. In a first phase, we will focus on finding concentration inequalities for different spectral functionals which reflect their large deviations behavior, for random Hermitian matrices satisfying a concentration property indexed by some alpha ∈ (0,2]. Then we will present the large deviations principle we obtained for the largest eigenvalue of Wigner matrices without Gaussian tails, in line with the work of Bordenave and Caputo. Another example of heavy-tail phenomenon is given by the large deviations of traces of random matrices which we investigate in three cases: the case of beta-ensembles, of Gaussian Wigner matrices, and the case of Wigner matrices without Gaussian tails. The Gaussian case was the opportunity to revisit Borell and Ledoux's proof of the large deviations of Wiener chaoses, which we investigate further by proposing a general large deviations statement, allowing us to give another proof of the large deviations principles known for the Wigner matrices without Gaussian tail. Finally, we give a new proof of the large deviations principles for the beta-ensembles with a quadratic potential, which relies only on the tridiagonal representation of these models. In particular, this result gives a proof of the large deviations of the GUE and GOE which does not rely on the knowledge of the law of the spectrum.

Cette thèse se concentre sur certaines extensions de la théorie des processus empiriques lorsque les données sont Markoviennes. Plus spécifiquement, nous nous concentrons sur plusieurs développements de la théorie du bootstrap, de la robustesse et de l’apprentissage statistique dans un cadre Markovien Harris récurrent positif. Notre approche repose sur la méthode de régénération qui s’appuie sur la décomposition d’une trajectoire de la chaîne de Markov atomique régénérative en blocs d’observations indépendantes et identiquement distribuées (i.i.d.). Les blocs de régénération correspondent à des segments de la trajectoire entre des instants aléatoires de visites dans un ensemble bien choisi (l’atome) formant une séquence de renouvellement. Dans la premiére partie de la thèse nous proposons un théorème fonctionnel de la limite centrale de type bootstrap pour des chaînes de Markov Harris récurrentes, d’abord dans le cas de classes de fonctions uniformément bornées puis dans un cadre non borné. Ensuite, nous utilisons les résultats susmentionnés pour obtenir unthéorème de la limite centrale pour des fonctionnelles Fréchet différentiables dans un cadre Markovien. Motivés par diverses applications, nous discutons la manière d’étendre certains concepts de robustesse à partir du cadre i.i.d. à un cas Markovien. En particulier, nous considérons le cas où les données sont des processus Markoviens déterministes par morceaux. Puis, nous proposons des procédures d’échantillonnage résiduel et wild bootstrap pour les processus périodiquement autorégressifs et établissons leur validité. Dans la deuxième partie de la thèse, nous établissons des versions maximales d’inégalités de concentration de type Bernstein, Hoeffding et des inégalités de moments polynomiales en fonction des nombres de couverture et des moments des temps de retour et des blocs. Enfin, nous utilisons ces inégalités sur les queues de distributions pour calculer des bornes de généralisation pour une estimation d’ensemble de volumes minimum pour les chaînes de Markov régénératives. / This thesis concentrates on some extensions of empirical processes theory when the data are Markovian. More specifically, we focus on some developments of bootstrap, robustness and statistical learning theory in a Harris recurrent framework. Our approach relies on the regenerative methods that boil down to division of sample paths of the regenerative Markov chain under study into independent and identically distributed (i.i.d.) blocks of observations. These regeneration blocks correspond to path segments between random times of visits to a well-chosen set (the atom) forming a renewal sequence. In the first part of the thesis we derive uniform bootstrap central limit theorems for Harris recurrent Markov chains over uniformly bounded classes of functions. We show that the result can be generalized also to the unbounded case. We use the aforementioned results to obtain uniform bootstrap central limit theorems for Fr´echet differentiable functionals of Harris Markov chains. Propelledby vast applications, we discuss how to extend some concepts of robustness from the i.i.d. framework to a Markovian setting. In particular, we consider the case when the data are Piecewise-determinic Markov processes. Next, we propose the residual and wild bootstrap procedures for periodically autoregressive processes and show their consistency. In the second part of the thesis we establish maximal versions of Bernstein, Hoeffding and polynomial tail type concentration inequalities. We obtain the inequalities as a function of covering numbers and moments of time returns and blocks. Finally, we use those tail inequalities toderive generalization bounds for minimum volume set estimation for regenerative Markov chains.

Dans la première partie de cette thèse, on présente des inégalités de concentration convexe pour des intégrales stochastiques. Ces résultats sont obtenus par calcul stochastique e tpar calcul de Malliavin forward/backward. On présente également des inégalités de déviation pour les exponentielles martingales à saut.Dans une deuxième partie on présente des théorèmes limites pour le conditionnement du mouvement brownien. / In the first part of this thesis, we present some convex concentration inequalities for stochastic integrals. These results are obtained by forward/backward stochastic calculus combined with Malliavin calculus. We also present deviation inequalities for exponentialjump-diffusion.In the second part, we present some limit theorems for the conditionning of Brownian motion.

This thesis studies the generalization ability of machine learning algorithms in a statistical setting. It focuses on the data-dependent analysis of the generalization performance of learning algorithms in order to make full use of the potential of the actual training sample from which these algorithms learn.¶ First, we propose an extension of the standard framework for the derivation of generalization bounds for algorithms taking their hypotheses from random classes of functions. This approach is motivated by the fact that the function produced by a learning algorithm based on a random sample of data depends on this sample and is therefore a random function. Such an approach avoids the detour of the worst-case uniform bounds as done in the standard approach. We show that the mechanism which allows one to obtain generalization bounds for random classes in our framework is based on a “small complexity” of certain random coordinate projections. We demonstrate how this notion of complexity relates to learnability and how one can explore geometric properties of these projections in order to derive estimates of rates of convergence and good confidence interval estimates for the expected risk. We then demonstrate the generality of our new approach by presenting a range of examples, among them the algorithm-dependent compression schemes and the data-dependent luckiness frameworks, which fall into our random subclass framework.¶ Second, we study in more detail generalization bounds for a specific algorithm which is of central importance in learning theory, namely the Empirical Risk Minimization algorithm (ERM). Recent results show that one can significantly improve the high-probability estimates for the convergence rates for empirical minimizers by a direct analysis of the ERM algorithm. These results are based on a new localized notion of complexity of subsets of hypothesis functions with identical expected errors and are therefore dependent on the underlying unknown distribution. We investigate the extent to which one can estimate these high-probability convergence rates in a data-dependent manner. We provide an algorithm which computes a data-dependent upper bound for the expected error of empirical minimizers in terms of the “complexity” of data-dependent local subsets. These subsets are sets of functions of empirical errors of a given range and can be determined based solely on empirical data. We then show that recent direct estimates, which are essentially sharp estimates on the high-probability convergence rate for the ERM algorithm, can not be recovered universally from empirical data.

Ce document rassemble les travaux effectués durant mes années de thèse. Je commence par une présentation concise des résultats principaux, puis viennent trois parties relativement indépendantes.Dans la première partie, je considère des problèmes d'inférence statistique sur un échantillon i.i.d. issu d'une loi inconnue à support dénombrable. Le premier chapitre est consacré aux propriétés de concentration du profil de l'échantillon et de la masse manquante. Il s'agit d'un travail commun avec Stéphane Boucheron et Mesrob Ohannessian. Après avoir obtenu des bornes sur les variances, nous établissons des inégalités de concentration de type Bernstein, et exhibons un vaste domaine de lois pour lesquelles le facteur de variance dans ces inégalités est tendu. Le deuxième chapitre présente un travail en cours avec Stéphane Boucheron et Elisabeth Gassiat, concernant le problème de la compression universelle adaptative d'un tel échantillon. Nous établissons des bornes sur la redondance minimax des classes enveloppes, et construisons un code quasi-adaptatif sur la collection des classes définies par une enveloppe à variation régulière. Dans la deuxième partie, je m'intéresse à des marches aléatoires sur des graphes aléatoires à degrés precrits. Je présente d'abord un résultat obtenu avec Justin Salez, établissant le phénomène de cutoff pour la marche sans rebroussement. Sous certaines hypothèses sur les degrés, nous déterminons précisément le temps de mélange, la fenêtre du cutoff, et montrons que le profil de la distance à l'équilibre converge vers la fonction de queue gaussienne. Puis je m'intéresse à la comparaison des temps de mélange de la marche simple et de la marche sans rebroussement. Enfin, la troisième partie est consacrée aux propriétés de concentration de tirages pondérés sans remise et correspond à un travail commun avec Yuval Peres et Justin Salez. / This document presents the problems I have been interested in during my PhD thesis. I begin with a concise presentation of the main results, followed by three relatively independent parts. In the first part, I consider statistical inference problems on an i.i.d. sample from an unknown distribution over a countable alphabet. The first chapter is devoted to the concentration properties of the sample's profile and of the missing mass. This is a joint work with Stéphane Boucheron and Mesrob Ohannessian. After obtaining bounds on variances, we establish Bernstein-type concentration inequalities and exhibit a vast domain of sampling distributions for which the variance factor in these inequalities is tight. The second chapter presents a work in progress with Stéphane Boucheron and Elisabeth Gassiat, on the problem of universal adaptive compression over countable alphabets. We give bounds on the minimax redundancy of envelope classes, and construct a quasi-adaptive code on the collection of classes defined by a regularly varying envelope. In the second part, I consider random walks on random graphs with prescribed degrees. I first present a result obtained with Justin Salez, establishing the cutoff phenomenon for non-backtracking random walks. Under certain degree assumptions, we precisely determine the mixing time, the cutoff window, and show that the profile of the distance to equilibrium converges to the Gaussian tail function. Then I consider the problem of comparing the mixing times of the simple and non-backtracking random walks. The third part is devoted to the concentration properties of weighted sampling without replacement and corresponds to a joint work with Yuval Peres and Justin Salez.

In this thesis, new methods for proving concentration inequalities for Poisson functionals are developed. The focus is on techniques that are based on logarithmic Sobolev inequalities, but also results that are based on the convex distance for Poisson processes are presented. The general methods are applied to a variety of functionals associated with random geometric graphs. In particular, concentration inequalities for subgraph and component counts are proved. Finally, the established concentration results are used to derive strong laws of large numbers for subgraph and component counts associated with random geometric graphs.

Thesis (PhD (Statistics and Actuarial Sciences))--Stellenbosch University, 2008. / We consider the problem of model assessment by risk estimation. Various approaches to risk estimation are considered in a uni ed framework. This a discussion of various complexity dimensions and approaches to obtaining bounds on covering numbers is also presented. The second type of training sample interval estimator discussed in the thesis is Rademacher bounds. These bounds use advanced concentration inequalities, so a chapter discussing such inequalities is provided. Our discussion of Rademacher bounds leads to the presentation of an alternative, slightly stronger, form of the core result used for deriving local Rademacher bounds, by avoiding a few unnecessary relaxations. Next, we turn to a discussion of PAC-Bayesian bounds. Using an approach developed by Olivier Catoni, we develop new PAC-Bayesian bounds based on results underlying Hoe ding's inequality. By utilizing Catoni's concept of \exchangeable priors", these results allowed the extension of a covering number-based result to averaging classi ers, as well as its corresponding algorithm- and data-dependent result. The last contribution of the thesis is the development of a more exible shell decomposition bound: by using Hoe ding's tail inequality rather than Hoe ding's relative entropy inequality, we extended the bound to general loss functions, allowed the use of an arbitrary number of bins, and introduced between-bin and within-bin \priors". Finally, to illustrate the calculation of these bounds, we applied some of them to the UCI spam classi cation problem, using decision trees and boosted stumps. framework is an extension of a decision-theoretic framework proposed by David Haussler. Point and interval estimation based on test samples and training samples is discussed, with interval estimators being classi ed based on the measure of deviation they attempt to bound. The main contribution of this thesis is in the realm of training sample interval estimators, particularly covering number-based and PAC-Bayesian interval estimators. The thesis discusses a number of approaches to obtaining such estimators. The rst type of training sample interval estimator to receive attention is estimators based on classical covering number arguments. A number of these estimators were generalized in various directions. Typical generalizations included: extension of results from misclassi cation loss to other loss functions; extending results to allow arbitrary ghost sample size; extending results to allow arbitrary scale in the relevant covering numbers; and extending results to allow arbitrary choice of in the use of symmetrization lemmas. These extensions were applied to covering number-based estimators for various measures of deviation, as well as for the special cases of misclassi - cation loss estimators, realizable case estimators, and margin bounds. Extended results were also provided for strati cation by (algorithm- and datadependent) complexity of the decision class. In order to facilitate application of these covering number-based bounds,