Efficient, Noise-Tolerant, and Private Learning via Boosting
This work addresses the challenge of efficient and robust private learning for machine learning practitioners, offering incremental improvements in sample complexity and noise tolerance for specific algorithms.
The paper tackles the problem of designing private and noise-tolerant PAC learners by introducing a framework for private boosting algorithms, which is applied to large-margin halfspaces, achieving sample complexity independent of dimension and matching best known bounds while tolerating label noise.
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.