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 give a computationally efficient algorithm for learning decision lists with minimal sample overhead over the best non-private algorithms. In the online model, we give a private analog of the influential Winnow algorithm for learning halfspaces with mistake bound polylogarithmic in the dimension and inverse polynomial in the margin. As an application, we describe how to privately learn decision lists in the online model, qualitatively matching state-of-the art non-private guarantees.

Inparticular,forany function in a classC of bounded VC dimension, we guarantee a low test error rate and a low rejection ratewith respect toP. Our algorithm is efficient given an Empirical Risk Minimizer (ERM) forC.

We show that the perturbation set and perturbation function models are equivalent. U ( x): = { g ( x): g 2G }, which completes the proof of this direction. B.1 Proper -Probabilistically Robust PAC Learning for finite G We show that if G is finite then VC classes are -probabilistically robustly learnable. Since A ( S) 2H, by construction of H, there are at least m points in C where A is not probabilistically robustly correct. Using a variant of Markov's inequality, gives We now use the same reasoning in Montasser et al. [2019], to show that no proper learning rule works.