Concentration Bounds for High Sensitivity Functions Through Differential Privacy

A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations

Herman Chernoff · 1952

Earlier work this paper cites.

Probability inequalities for sums of bounded random variables

Wassily Hoeffding · 1963

Earlier work this paper cites.

Concentration of non-lipschitz functions and applications

Van H. Vu · 2002

Earlier work this paper cites.

Divide and conquer martingales and the number of triangles in a random graph

J. H. Kim and V. H. Vu · 2004

Earlier work this paper cites.

Our data, ourselves: Privacy via distributed noise generation

Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor · 2006

Earlier work this paper cites.

Calibrating noise to sensitivity in private data analysis

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith · 2006

Earlier work this paper cites.

Mechanism design via differential privacy

Frank McSherry and Kunal Talwar · 2007

Cited alongside, same era.

Preventing false discovery in interactive data analysis is hard

Moritz Hardt and Jonathan Ullman · 2014

Cited alongside, same era.

Concentration in unbounded metric spaces and algorithmic stability

Aryeh Kontorovich · 2014

Cited alongside, same era.

Generalization in adaptive data analysis and holdout reuse

Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth · 2015

Cited alongside, same era.

Preserving statistical validity in adaptive data analysis

Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth · 2015

Cited alongside, same era.

On the number of iterations for dantzig-wolfe optimization and packing-covering approximation algorithms

Philip N. Klein and Neal E. Young · 2015

Interactive fingerprinting codes and the hardness of preventing false discovery

Thomas Steinke and Jonathan Ullman · 2015

Later among the works it cites.

Typicality-based stability and privacy

Original

Raef Bassily and Yoav Freund · 2016

Later among the works it cites.

Algorithmic stability for adaptive data analysis

Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman · 2016

Later among the works it cites.

Adaptive learning with robust generalization guarantees

Rachel Cummings, Katrina Ligett, Kobbi Nissim, Aaron Roth, and Zhiwei Steven Wu · 2016

Later among the works it cites.

Subgaussian tail bounds via stability arguments

Original

Thomas Steinke and Jonathan Ullman · 2017

Closest in time.