Differentially Private Release and Learning of Threshold Functions

We prove new upper and lower bounds on the sample complexity of $(ε, δ)$ differentially private algorithms for releasing approximate answers to threshold functions. A threshold function $c_x$ over a totally ordered domain $X$ evaluates to $c_x(y) = 1$ if $y \le x$, and evaluates to $0$ otherwise. We give the first nontrivial lower bound for releasing thresholds with $(ε,δ)$ differential privacy…