More Like this

1. Communication-Aware Collaborative Learning

   Blum, A.; Heinecke, S.; Reyzin, L. (January 2021, Proceedings of the AAAI Conference on Artificial Intelligence)

   null (Ed.)

   Algorithms for noiseless collaborative PAC learning have been analyzed and optimized in recent years with respect to sample complexity. In this paper, we study collaborative PAC learning with the goal of reducing communication cost at essentially no penalty to the sample complexity. We develop communication efficient collaborative PAC learning algorithms using distributed boosting. We then consider the communication cost of collaborative learning in the presence of classification noise. As an intermediate step, we show how collaborative PAC learning algorithms can be adapted to handle classification noise. With this insight, we develop communication efficient algorithms for collaborative PAC learning robust to classification noise. 

   more » « less
2. A Computational Separation between Private Learning and Online Learning

   Bun, Mark (January 2020, 34th Conference on Neural Information Processing Systems)

   null (Ed.)

   A recent line of work has shown a qualitative equivalence between differentially private PAC learning and online learning: A concept class is privately learnable if and only if it is online learnable with a finite mistake bound. However, both directions of this equivalence incur significant losses in both sample and computational efficiency. Studying a special case of this connection, Gonen, Hazan, and Moran (NeurIPS 2019) showed that uniform or highly sample-efficient pure-private learners can be time-efficiently compiled into online learners. We show that, assuming the existence of one-way functions, such an efficient conversion is impossible even for general pure-private learners with polynomial sample complexity. This resolves a question of Neel, Roth, and Wu (FOCS 2019). 

   more » « less
3. Bounds and Complexity Results for Learning Coalition-Based Interaction Functions in Networked Social Systems

   https://doi.org/10.1609/aaai.v34i04.5710  

   Adiga, Abhijin; Kuhlman, Chris; Marathe, Madhav; Ravi, S.; Rosenkranz, Daniel; Stearns, Richard; Vullikanti, Anil (June 2020, Proceedings of the AAAI Conference on Artificial Intelligence)

   null (Ed.)

   Using a discrete dynamical system model for a networked social system, we consider the problem of learning a class of local interaction functions in such networks. Our focus is on learning local functions which are based on pairwise disjoint coalitions formed from the neighborhood of each node. Our work considers both active query and PAC learning models. We establish bounds on the number of queries needed to learn the local functions under both models. We also establish a complexity result regarding efficient consistent learners for such functions. Our experimental results on synthetic and real social networks demonstrate how the number of queries depends on the structure of the underlying network and number of coalitions. 

   more » « less
4. 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
5. Learning Coalition-Based Interactions in Networked Social Systems

   Adiga, Abhijin; Kuhlman, Chris J.; Marathe, Madhav V.; Ravi, S. S.; Rosenkrantz, Daniel J.; Stearns, Richard E.; Vullikanti, Anil (April 2020, Association for the Advancement of Artificial Intelligence Conference 2020)

   Using a discrete dynamical system model for a networked social system, we consider the problem of learning a class of local interaction functions in such networks. Our focus is on learning local functions which are based on pairwise disjoint coalitions formed from the neighborhood of each node. Our work considers both active query and PAC learning models. We establish bounds on the number of queries needed to learn the local functions under both models.We also establish a complexity result regarding efficient consistent learners for such functions. Our experimental results on synthetic and real social networks demonstrate how the number of queries depends on the structure of the underlying network and number of coalitions. 

   more » « less