@article{Stemmer_Nissim_2019, title={Concentration Bounds for High Sensitivity Functions Through Differential Privacy}, volume={9}, url={https://journalprivacyconfidentiality.org/index.php/jpc/article/view/658}, DOI={10.29012/jpc.658}, abstractNote={<p>A new line of work demonstrates how differential privacy can be used as a mathematical tool for guaranteeing generalization in adaptive data analysis. Specifically, if a differentially private analysis is applied on a sample S of i.i.d. examples to select a low-sensitivity function f, then w.h.p. f(S) is close to its expectation, even though f is being chosen adaptively, i.e., based on the data.</p> <p>Very recently, Steinke and Ullman observed that these generalization guarantees can be used for proving concentration bounds in the non-adaptive setting, where the low-sensitivity function is fixed beforehand. In particular, they obtain alternative proofs for classical concentration bounds for low-sensitivity functions, such as the Chernoff bound and McDiarmidâ€™s Inequality.&nbsp;In this work, we extend this connection between differential privacy and concentration bounds, and show that differential privacy can be used to prove concentration of high-sensitivity functions.</p>}, number={1}, journal={Journal of Privacy and Confidentiality}, author={Stemmer, Uri and Nissim, Kobbi}, year={2019}, month={Mar.} }