Privately Learning Thresholds: Closing the Exponential Gap

Occam’s razor

A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth · 1987

Earlier work this paper cites.

Our data, ourselves: Privacy via distributed noise generation

C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor · 2006

Earlier work this paper cites.

Calibrating noise to sensitivity in private data analysis

C. Dwork, F. McSherry, K. Nissim, and A. D. Smith · 2006

Earlier work this paper cites.

Mechanism design via differential privacy

F. McSherry and K. Talwar · 2007

Earlier work this paper cites.

On the complexity of differentially private data release: efficient algorithms and hardness results

C. Dwork, M. Naor, O. Reingold, G. N. Rothblum, and S. P. Vadhan · 2009

Earlier work this paper cites.

Boosting and differential privacy

C. Dwork, G. N. Rothblum, and S. P. Vadhan · 2010

Cited alongside, same era.

What can we learn privately?

S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith · 2011

Cited alongside, same era.

Private learning and sanitization: Pure vs. approximate differential privacy

A. Beimel, K. Nissim, and U. Stemmer · 2013

Cited alongside, same era.

The algorithmic foundations of differential privacy

C. Dwork and A. Roth · 2014

Cited alongside, same era.

Differentially private release and learning of threshold functions

M. Bun, K. Nissim, U. Stemmer, and S. P. Vadhan · 2015

Cited alongside, same era.

Sample complexity bounds on differentially private learning via communication complexity

V. Feldman and D. Xiao · 2015

Later among the works it cites.

The Complexity of Differential Privacy

S. Vadhan · 2016

Later among the works it cites.

Composable and versatile privacy via truncated cdp

M. Bun, C. Dwork, G. N. Rothblum, and T. Steinke · 2018

Later among the works it cites.

Private PAC learning implies finite littlestone dimension

N. Alon, R. Livni, M. Malliaris, and S. Moran · 2019

Closest in time.