Machine learning algorithms have exciting and wide-range potential. However, as the data frequently containsensitive personal information, there are real privacy concerns associated with the development and the deployment of this technology. Motivated by this observation, the line of work on differentially private learning (initiated by [23]) aims to construct learning algorithms that provide strong (mathematically proven) privacy protections for the training data. Both government agenciesand industrial companies have realized the importance of introducing strong privacy protection to statistical and machine learning tasks. A few recent examples include Google [20] and Apple [27] that are already using differentially private estimation algorithms that feed into machine learning algorithms, and the US Census Bureau announcement that they will use differentially privatedata publication techniques in the next decennial census [1]. Differential privacy is increasingly accepted as a standard for rigorous privacy. We refer the reader to the excellent surveys in [17] and [28]. The definition of differential privacy is, Definition 1.1 ([16]). Let A be a randomized algorithm whose input is a sample.