An $\tilde{O}$ptimal Differentially Private Learner for Concept Classes with VC Dimension 1

Machine learning algorithms can access sensitive information from the training dataset. We research the privacy-preserving machine learning technique, introduced by Kasiviswanathan et al. [17], that targets to learn a hypothesis while preserving the privacy of individual entries in the dataset. Informally, the goal is to construct a learner that satisfies the requirements of probably approximately correct (PAC) learning [22] and, simultaneously, differential privacy [11].