More Like this

1. Efficient, Noise-Tolerant, and Private Learning via Boosting

   Bun, Mark; Carmosino, Marco L.; Sorrell, Jessica (January 2020, Proceedings of Thirty Third Conference on Learning Theory)

   null (Ed.)

   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. 

   more » « less
2. Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random

   Chandrasekaran, Gautam; Kontonis, Vasilis; Stavropoulos, Konstantinos; Tian, Kevin (January 2025, NeurIPS 2024 https://arxiv.org/abs/2501.09851)

   We study the problem of PAC learning γ-margin halfspaces with Massart noise. We propose a simple proper learning algorithm, the Perspectron, that has sample complexity O˜((ϵγ)−2) and achieves classification error at most η+ϵ where η is the Massart noise rate. Prior works [DGT19,CKMY20] came with worse sample complexity guarantees (in both ϵ and γ) or could only handle random classification noise [DDK+23,KIT+23] -- a much milder noise assumption. We also show that our results extend to the more challenging setting of learning generalized linear models with a known link function under Massart noise, achieving a similar sample complexity to the halfspace case. This significantly improves upon the prior state-of-the-art in this setting due to [CKMY20], who introduced this model. 

   more » « less
3. Collaborative PAC Learning

   Blum, Avrim; Haghtalab, Nika; Procaccia, Ariel D; Qiao, Mingda (December 2017, NIPS 2017)

   We consider a collaborative PAC learning model, in which k players attempt to learn the same underlying concept. We ask how much more information is required to learn an accurate classifier for all players simultaneously. We refer to the ratio between the sample complexity of collaborative PAC learning and its non-collaborative (single-player) counterpart as the overhead. We design learning algorithms with O(ln(k)) and O(ln2 (k)) overhead in the personalized and centralized variants our model. This gives an exponential improvement upon the naïve algorithm that does not share information among players. We complement our upper bounds with an Ω(ln(k)) overhead lower bound, showing that our results are tight up to a logarithmic factor. 

   more » « less
4. PAC Learnability of Node Functions in Networked Dynamical Systems

   Adiga, Abhijin; Kuhlman, Chris J; Marathe, Madhav V; Ravi, S S; Vulliikanti, Anil (January 2019, Proceedings of the International Conference on Machine Learning)

   null (Ed.)

   We consider the PAC learnability of the functions at the nodes of a discrete networked dynamical system, assuming that the underlying network is known. We provide tight bounds on the sample complexity of learning threshold functions. We establish a computational intractability result for efficient PAC learning of such functions. We develop efficient consistent learners when the number of negative examples is small. Using synthetic and real-world networks, we experimentally study how the network structure and sample complexity influence the quality of inference. 

   more » « less
5. Crowdsourced PAC Learning under Classification Noise

   Heinecke, Shelby; Reyzin, Lev (October 2019, Proceedings of the Seventh AAAI Conference on Human Computation and Crowdsourcing)

   Law, Edith; Vaughan, Jennifer W (Ed.)

   In this paper, we analyze PAC learnability from labels produced by crowdsourcing. In our setting, unlabeled examples are drawn from a distribution and labels are crowdsourced from workers who operate under classification noise, each with their own noise parameter. We develop an end-to-end crowdsourced PAC learning algorithm that takes unlabeled data points as input and outputs a trained classifier. Our threestep algorithm incorporates majority voting, pure-exploration bandits, and noisy-PAC learning. We prove several guarantees on the number of tasks labeled by workers for PAC learning in this setting and show that our algorithm improves upon the baseline by reducing the total number of tasks given to workers. We demonstrate the robustness of our algorithm by exploring its application to additional realistic crowdsourcing settings. 

   more » « less