2017/03/06 by Kobbi Nissim, Uri Stemmer, Nissim, Kobbi +1
Computer Science · #Cryptography and Data Security #FOS: Computer and information sciences #Machine Learning (cs.LG) #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1703.01970
openalex publication_date 2017/03/06 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
A new line of work [Dwork et al. STOC 2015], [Hardt and Ullman FOCS 2014],\n[Steinke and Ullman COLT 2015], [Bassily et al. STOC 2016] demonstrates how\ndifferential privacy [Dwork et al. TCC 2006] can be used as a mathematical tool\nfor guaranteeing generalization in adaptive data analysis. Specifically, if a\ndifferentially private analysis is applied on a sample S of i.i.d. examples to\nselect a low-sensitivity function f, then w.h.p. f(S) is close to its\nexpectation, although f is being chosen based on the data.\n Very recently, Steinke and Ullman observed that these generalization\nguarantees can be used for proving concentration bounds in the non-adaptive\nsetting, where the low-sensitivity function is fixed beforehand. In particular,\nthey obtain alternative proofs for classical concentration bounds for\nlow-sensitivity functions, such as the Chernoff bound and McDiarmid's\nInequality.\n In this work, we set out to examine the situation for functions with\nhigh-sensitivity, for which differential privacy does not imply generalization\nguarantees under adaptive analysis. We show that differential privacy can be\nused to prove concentration bounds for such functions in the non-adaptive\nsetting.\n