On concentration of self-bounding functions

By Stéphane Boucheron, Gábor Lugosi, Pascal Massart. 2009

57 citations recorded by the source corpus.

We prove some new concentration inequalities for self-bounding functions using the entropy method. As an application, we recover Talagrand's convex distance inequality. The new Bernstein-like inequalities for self-bounding functions are derived thanks to a careful analysis of the so-called Herbst argument. The latter involves comparison results between solutions of differential inequalities that may be interesting in their own right.

Subfields: Applied Mathematics

View Paper: https://www.semanticscholar.org/paper/cc07224d483b3bfbda474bbfed358ed9eb897079

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

1. Aaron Roth
2. Moritz Hardt
3. Jonathan Ullman
4. Bo'az Klartag

Citations in the corpus

• Privately releasing conjunctions and the statistical query barrier (2010, methodology): “We then take advantage of Vondrak’s observation in [Von10] that Lipschitz submodular functions are self-bounding , which allows us to apply recent dimension-free concentration bounds for self-bounding functions [BLM00, BLM09].”