Õptimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization

Edith Cohen, Xin Lyu, Jelani Nelson +2

The problem of learning threshold functions is a fundamental one in machine learning. Classical learning theory implies sample complexity of $O({\xi }^{-1}\log (1/\beta ))$ (for generalizati…