A note on concentration of submodular functions

Abstract

We survey a few concentration inequalities for submodular and fractionally subadditive functions of independent random variables, implied by the entropy method for self-bounding functions. The power of these concentration bounds is that they are dimension-free, in particular implying standard deviation O(\sqrt{\E[f]}) rather than O(\sqrt{n}) which can be obtained for any 1-Lipschitz function of n variables.

Cited by in corpus (8)

• Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
• Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas
• On Approximating Partial Set Cover and Generalizations
• Fast Non-Monotone Submodular Maximisation Subject to a Matroid Constraint
• Learning Coverage Functions and Private Release of Marginals
• Prophet Inequalities with Linear Correlations and Augmentations
• Maximizing Non-monotone Submodular Set Functions Subject to Different Constraints: Combined Algorithms
• Approximate ${\mathbb{F}}_2$-Sketching of Valuation Functions