We derive an extension of McDiarmid’s inequality for functions f with bounded differences on a high probability set Y (instead of almost surely). The behavior of f outside Y may be arbitrary. The proof is short and elementary, and relies on an extension argument similar to Kirszbraun’s theorem [4].
On the other hand, concentration inequalities for general functions whose differences are bounded with high probability were provided in @cite_5 , @cite_1 , @cite_9 . The authors assume that there exists vectors @math and @math , with @math for all @math such that function @math has @math -bounded differences on @math and @math -bounded differences on @math . The provided concentration inequalities usually give a strong improvement over McDiarmid's inequality, but are not informative if @math is too large. Theorem shows that this is an artefact, since all the required "information" about the behaviour of @math outside of @math is contained in @math . A toy example of this phenomenon is @math , @math Ber( @math ), @math , @math and f(X) = . For all @math , Theorem guarantees that @math while previously known inequalities become uninformative for @math arbitrarily large.
@cite_5 @cite_9 @cite_1
2167969281 2247326188 2037982184 1615542443
Concentration inequalities are fundamental tools in probabilistic combinatorics and theoretical computer science for proving that random functions are near their means. Of particular importance is the case where f(X) is a function of independent random variables X=(X_1, ..., X_n). Here the well known bounded differences inequality (also called McDiarmid's or Hoeffding-Azuma inequality) establishes sharp concentration if the function f does not depend too much on any of the variables. One attractive feature is that it relies on a very simple Lipschitz condition (L): it suffices to show that |f(X)-f(X')| c_k whenever X,X' differ only in X_k. While this is easy to check, the main disadvantage is that it considers worst-case changes c_k, which often makes the resulting bounds too weak to be useful. In this paper we prove a variant of the bounded differences inequality which can be used to establish concentration of functions f(X) where (i) the typical changes are small although (ii) the worst case changes might be very large. One key aspect of this inequality is that it relies on a simple condition that (a) is easy to check and (b) coincides with heuristic considerations why concentration should hold. Indeed, given an event that holds with very high probability, we essentially relax the Lipschitz condition (L) to situations where occurs. The point is that the resulting typical changes c_k are often much smaller than the worst case ones. To illustrate its application we consider the reverse H-free process, where H is 2-balanced. We prove that the final number of edges in this process is concentrated, and also determine its likely value up to constant factors. This answers a question of Bollob 'as and Erd o s. We derive an extension of McDiarmid’s inequality for functions f with bounded differences on a high probability set Y (instead of almost surely). The behavior of f outside Y may be arbitrary. The proof is short and elementary, and relies on an extension argument similar to Kirszbraun’s theorem [4]. In a celebrated work by Hoeffding [J. Amer. Statist. Assoc. 58 (1963) 13-30], several inequalities for tail probabilities of sums M n = X 1 + ... + X n of bounded independent random variables X j were proved. These inequalities had a considerable impact on the development of probability and statistics, and remained unimproved until 1995 when Talagrand [Inst. Hautes Etudes Sci. Publ. Math. 81 (1995a) 73-205] inserted certain missing factors in the bounds of two theorems. By similar factors, a third theorem was refined by Pinelis [Progress in Probability 43 (1998) 257-314] and refined (and extended) by me. In this article, I introduce a new type of inequality. Namely, I show that P M n ≥ x ≤ cP S n ≥ x , where c is an absolute constant and S n = e 1 + ... + e n is a sum of independent identically distributed Bernoulli random variables (a random variable is called Bernoulli if it assumes at most two values). The inequality holds for those x ∈ Ρ where the survival function x → P S n ≥ x has a jump down. For the remaining x the inequality still holds provided that the function between the adjacent jump points is interpolated linearly or log-linearly. If it is necessary, to estimate P S n ≥ x special bounds can be used for binomial probabilities. The results extend to martingales with bounded differences. It is apparent that Theorem 1.1 of this article is the most important. The inequalities have applications to measure concentration, leading to results of the type where, up to an absolute constant, the measure concentration is dominated by the concentration in a simplest appropriate model, such results will be considered elsewhere. We prove an extension of McDiarmid's inequality for metric spaces with unbounded diameter. To this end, we introduce the notion of the subgaussian diameter, which is a distribution-dependent refinement of the metric diameter. Our technique provides an alternative approach to that of Kutin and Niyogi's method of weakly difference-bounded functions, and yields nontrivial, dimension-free results in some interesting cases where the former does not. As an application, we give apparently the first generalization bound in the algorithmic stability setting that holds for unbounded loss functions. This yields a novel risk bound for some regularized metric regression algorithms. We give two extensions of the basic concentration result. The first enables one to replace the independence assumption by appropriate strong mixing. The second generalizes the subgaussian technique to other Orlicz norms.