2017/01/12 by Thomas Steinke, Jonathan Ullman, Steinke, Thomas +1
Computer Science · Social Sciences · #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Privacy, Security, and Data Protection #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.1701.03493
openalex publication_date 2017/01/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Sums of independent, bounded random variables concentrate around their expectation approximately as well a Gaussian of the same variance. Well known results of this form include the Bernstein, Hoeffding, and Chernoff inequalities and many others. We present an alternative proof of these tail bounds based on what we call a stability argument, which avoids bounding the moment generating function or higher-order moments of the distribution. Our stability argument is inspired by recent work on the generalization properties of differential privacy and their connection to adaptive data analysis (Bassily et al., STOC 2016).