December 31, 2019
This paper presents compact notations for concentration inequalities and convenient results to streamline probabilistic analysis. The new expressions describe the typical sizes and tails of random variables, allowing for simple operations without heavy use of inessential constants. They bridge classical asymptotic notations and modern non-asymptotic tail bounds together. Examples of different kinds demonstrate their efficacy.
August 21, 2022
Concentration inequalities for the sample mean, like those due to Bernstein and Hoeffding, are valid for any sample size but overly conservative, yielding confidence intervals that are unnecessarily wide. The central limit theorem (CLT) provides asymptotic confidence intervals with optimal width, but these are invalid for all sample sizes. To resolve this tension, we develop new computable concentration inequalities with asymptotically optimal size, finite-sample validity, an...
January 22, 2024
The sample correlation coefficient $R$ plays an important role in many statistical analyses. We study the moments of $R$ under the bivariate Gaussian model assumption, provide a novel approximation for its finite sample mean and connect it with known results for the variance. We exploit these approximations to present non-asymptotic concentration inequalities for $R$. Finally, we illustrate our results in a simulation experiment that further validates the approximations prese...
March 5, 2019
Concentration inequalities have become increasingly popular in machine learning, probability, and statistical research. Using concentration inequalities, one can construct confidence intervals (CIs) for many quantities of interest. Unfortunately, many of these CIs require the knowledge of population variances, which are generally unknown, making these CIs impractical for numerical application. However, recent results regarding the simultaneous bounding of the probabilities of...
July 19, 2016
Concentration inequalities are indispensable tools for studying the generalization capacity of learning models. Hoeffding's and McDiarmid's inequalities are commonly used, giving bounds independent of the data distribution. Although this makes them widely applicable, a drawback is that the bounds can be too loose in some specific cases. Although efforts have been devoted to improving the bounds, we find that the bounds can be further tightened in some distribution-dependent s...
March 23, 2022
We prove concentration inequalities for $f\left( X\right) $ about its median, where $X$ is a random vector in $\mathbb{R}^n$ with independent heavy tailed coordinates of Weibull or power type, and $f:\mathbb{R}^n\rightarrow\mathbb{R}$ is a locally Lipschitz function. This paper is part of a series of four papers, Part I, Part II and two supporting papers. It can be read independently of Part I.
May 21, 2018
The present work provides an original framework for random matrix analysis based on revisiting the concentration of measure theory from a probabilistic point of view. By providing various notions of vector concentration ($q$-exponential, linear, Lipschitz, convex), a set of elementary tools is laid out that allows for the immediate extension of classical results from random matrix theory involving random concentrated vectors in place of vectors with independent entries. These...
December 28, 2018
The classical Gaussian concentration inequality for Lipschitz functions is adapted to a setting where the classical assumptions (i.e. Lipschitz and Gaussian) are not met. The theory is more direct than much of the existing theory designed to handle related generalizations. An application is presented to linear combinations of heavy tailed random variables.
October 21, 2018
The non-asymptotic tail bounds of random variables play crucial roles in probability, statistics, and machine learning. Despite much success in developing upper bounds on tail probability in literature, the lower bounds on tail probabilities are relatively fewer. In this paper, we introduce systematic and user-friendly schemes for developing non-asymptotic lower bounds of tail probabilities. In addition, we develop sharp lower tail bounds for the sum of independent sub-Gaussi...
September 9, 2011
This survey article discusses the main concepts and techniques of Stein's method for distributional approximation by the normal, Poisson, exponential, and geometric distributions, and also its relation to concentration inequalities. The material is presented at a level accessible to beginning graduate students studying probability with the main emphasis on the themes that are common to these topics and also to much of the Stein's method literature.