Efficient, noise-tolerant, and private learning via boosting
Carmosino, Marco Leandro
MetadataShow full item record
Citation (published version)M. Bun, M. Carmosino, J. Sorrell. 2020. "Efficient, noise-tolerant, and private learning via boosting." Conference on Learning Theory (COLT) https://arxiv.org/abs/2002.01100
We introduce a simple framework for designing private boosting algorithms. We give natural conditions under which these algorithms are differentially private, efficient, and noise-tolerant PAC learners. To demonstrate our framework, we use it to construct noise-tolerant and private PAC learners for large-margin halfspaces whose sample complexity does not depend on the dimension. We give two sample complexity bounds for our large-margin halfspace learner. One bound is based only on differential privacy, and uses this guarantee as an asset for ensuring generalization. This first bound illustrates a general methodology for obtaining PAC learners from privacy, which may be of independent interest. The second bound uses standard techniques from the theory of large-margin classification (the fat-shattering dimension) to match the best known sample complexity for differentially private learning of large-margin halfspaces, while additionally tolerating random label noise.