@article {1027961,
	title = {Concentration Bounds for High Sensitivity Functions Through Differential Privacy},
	journal = {Journal of Privacy and Confidentiality},
	volume = {9},
	number = {1},
	year = {2019},
	abstract = {
	A new line of work [6, 9, 15, 2] demonstrates how differential privacy [8] 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 lowsensitivity function f , then w.h.p. f (S) is close to its expectation, although f is being chosen based on the data. Very recently, Steinke and Ullman [16] 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{\textquoteright}s Inequality. In this work, we set out to examine the situation for functions with high-sensitivity, for which differential privacy does not imply generalization guarantees under adaptive analysis. We show that differential privacy can be used to prove concentration bounds for such functions in the non-adaptive setting.

},
	url = {https://journalprivacyconfidentiality.org/index.php/jpc/article/view/658},
	author = {Kobbi Nissim and Uri Stemmer}
}
