Concentration Bounds for High Sensitivity Functions Through Differential Privacy
A new line of work [Dwork et al. STOC 2015], [Hardt and Ullman FOCS 2014], [Steinke and Ullman COLT 2015], [Bassily et al. STOC 2016] demonstrates how differential privacy [Dwork et al. TCC 2006] 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, although f is being chosen based on the data. 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. 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.
Code (0)
등록된 구현이 없습니다.
Tasks
SensitivityVocal Bursts Intensity PredictionSimilar Papers 제목 키워드 기반
Sharper convergence bounds of Monte Carlo Rademacher Averages through Self-Bounding functions
We derive sharper probabilistic concentration bounds for the Monte Carlo Empirical Rademacher Averages (MCERA), which are proved through recent results on the concentration of self-bounding functions. Our novel bounds ar…
Efron-Stein PAC-Bayesian Inequalities
We prove semi-empirical concentration inequalities for random variables which are given as possibly nonlinear functions of independent random variables. These inequalities describe concentration of random variable in ter…
Generalization BoundsOff-policy evaluationConcentration analysis of multivariate elliptic diffusion processes
We prove concentration inequalities and associated PAC bounds for continuous- and discrete-time additive functionals for possibly unbounded functions of multivariate, nonreversible diffusion processes. Our analysis relie…
Learning without Concentration
We obtain sharp bounds on the performance of Empirical Risk Minimization performed in a convex class and with respect to the squared loss, without assuming that class members and the target are bounded functions or have …
Distribution-dependent concentration inequalities for tighter generalization bounds
Concentration inequalities are indispensable tools for studying the generalization capacity of learning models. Hoeffding's and McDiarmid's inequalities are commonly used, giving bounds independent of the data distributi…
Generalization BoundsLearning Theory