PCG Reading Group: Abhimanyu Choudhary

About this event

On Bentkus' Inequalities, part IIAbstract: The classical and celebrated inequalities of Chernoff and Hoeffding are the gold-standard for tail bounds for sums of bounded, independent random variables. Despite this, these inequalities fail to reproduce central-limit type behavior in the limit, yielding tails of the form exp(-t^2/2) as opposed to the true Gaussian bound exp(-t^2/2) * t^(-1). This discrepancy was addressed by Talagrand in 1995, whose work was followed by Bentkus and Pinelis in a series of papers where they developed nearly optimal bounds. By nearly optimal, we mean that matching and upper and lower bounds exist. We continue last week's discussion: the form of these bounds, and the role that convexity plays in proving them.rt II

Abstract:

The classical and celebrated inequalities of Chernoff and Hoeffding are the gold-standard for tail bounds for sums of bounded, independent random variables. Despite this, these inequalities fail to reproduce central-limit type behavior in the limit, yielding tails of the form exp(-t^2/2) as opposed to the true Gaussian bound exp(-t^2/2) * t^(-1). This discrepancy was addressed by Talagrand in 1995, whose work was followed by Bentkus and Pinelis in a series of papers where they developed nearly optimal bounds. By nearly optimal, we mean that matching and upper and lower bounds exist. We continue last week's discussion: the form of these bounds, and the role that convexity plays in proving them.