Privately Learning Decision Lists and a Differentially Private Winnow

Mark Bun, William Fang

We give new differentially private algorithms for the classic problems of learning decision lists and large-margin halfspaces in the PAC and online models. In the PAC model, we giv…