A Linear Programming Inequality with Applications to Concentration of Measure

In this report, we aim to exemplify concentration inequalities and provide easy to understand proofs for it. Our focus is on the inequalities which are helpful in the design and analysis of machine learning algorithms.

For a sequence $\{X_{n}, \, n \geqslant 1 \}$ of random variables satisfying $\mathbb{E} \lvert X_{n} \rvert < \infty$ for all $n \geqslant 1$, a maximal inequality is established, and used to obtain strong law of large numbers for dependent random variables.

We give concentration bounds for martingales that are uniform over finite times and extend classical Hoeffding and Bernstein inequalities. We also demonstrate our concentration bounds to be optimal with a matching anti-concentration inequality, proved using the same method. Together these constitute a finite-time version of the law of the iterated logarithm, and shed light on the relationship between it and the central limit theorem.

This paper gives a review of concentration inequalities which are widely employed in non-asymptotical analyses of mathematical statistics in a wide range of settings, from distribution-free to distribution-dependent, from sub-Gaussian to sub-exponential, sub-Gamma, and sub-Weibull random variables, and from the mean to the maximum concentration. This review provides results in these settings with some fresh new results. Given the increasing popularity of high-dimensional data...

We show somewhat unexpectedly that whenever a general Bernstein-type maximal inequality holds for partial sums of a sequence of random variables, a maximal form of the inequality is also valid.

We introduce a version of Stein's method for proving concentration and moment inequalities in problems with dependence. Simple illustrative examples from combinatorics, physics, and mathematical statistics are provided.

We illustrate a process that constructs martingales from raw material that arises naturally from the theory of sampling without replacement.The usefulness of the new martingales is illustrated by the development of maximal inequalities for permuted sequences of real numbers. Some of these inequalities are new and some are variations of classical inequalities like those introduced by A. Garsia in the study of rearrangement of orthogonal series.

We consider the problem of bounding large deviations for non-i.i.d. random variables that are allowed to have arbitrary dependencies. Previous works typically assumed a specific dependence structure, namely the existence of independent components. Bounds that depend on the degree of dependence between the observations have only been studied in the theory of mixing processes, where variables are time-ordered. Here, we introduce a new way of measuring dependences within an unor...

The purpose of this paper is to give a survey of a class of maximal inequalities for purely discontinuous martingales, as well as for stochastic integral and convolutions with respect to Poisson measures, in infinite dimensional spaces. Such maximal inequalities are important in the study of stochastic partial differential equations with noise of jump type.

We give a simple inequality for the sum of independent bounded random variables. This inequality improves on the celebrated result of Hoeffding in a special case. It is optimal in the limit where the sum tends to a Poisson random variable.