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 Systematic Review of Data Collection and Analysis Methods in K–12 Educational Games

   https://doi.org/10.3102/2110403  

   Ma, Tianyu; Kahn, Jennifer; Hardy, Lisa; Radke, Sarah (April 2024, AERA Online Paper Repository)

   This paper reports on systematic literature review that examined learning theories and data collection and analysis methods used to study game-based learning in research on educational digital games for K-12 populations. Through electronic database, hand, and ancestral searches, we identified 25 empirical studies (29 educational games) published in peer-review journals that report evidence of how students learn through in-game and out-of-game data collection and analysis methods. Taking an approach to game-based learning as identity-driven and situated, we found that while games do not take such an approach to game-based learning, games tend to collect data on players’ social interactions and collaborative experiences. The review also highlighted the opportunity for providing real-time feedback and data to players during gameplay. 

   more » « less
3. Compression in a Distributed Setting

   Ghazi, Badih; Haramaty, Elad; Kamath, Pritish; Sudan, Madhu (January 2017, Innovations in Theoretical Computer Science (ITCS))

   Motivated by an attempt to understand the formation and development of (human) language, we introduce a "distributed compression" problem. In our problem a sequence of pairs of players from a set of K players are chosen and tasked to communicate messages drawn from an unknown distribution Q. Arguably languages are created and evolve to compress frequently occurring messages, and we focus on this aspect. The only knowledge that players have about the distribution Q is from previously drawn samples, but these samples differ from player to player. The only common knowledge between the players is restricted to a common prior distribution P and some constant number of bits of information (such as a learning algorithm). Letting T_eps denote the number of iterations it would take for a typical player to obtain an eps-approximation to Q in total variation distance, we ask whether T_eps iterations suffice to compress the messages down roughly to their entropy and give a partial positive answer. We show that a natural uniform algorithm can compress the communication down to an average cost per message of O(H(Q) + log (D(P || Q) + O(1)) in $$\tilde{O}(T_eps)$$ iterations while allowing for O(eps)-error, where D(. || .) denotes the KL-divergence between distributions. For large divergences this compares favorably with the static algorithm that ignores all samples and compresses down to H(Q) + D(P || Q) bits, while not requiring (T_eps . K) iterations that it would take players to develop optimal but separate compressions for each pair of players. Along the way we introduce a "data-structural" view of the task of communicating with a natural language and show that our natural algorithm can also be implemented by an efficient data structure, whose storage is comparable to the storage requirements of Q and whose query complexity is comparable to the lengths of the message to be compressed. Our results give a plausible mathematical analogy to the mechanisms by which human languages get created and evolve, and in particular highlights the possibility of coordination towards a joint task (agreeing on a language) while engaging in distributed learning. 

   more » « less
4. Adaptive data collection for robust learning across multiple distributions

   Zang, Chengbo; Turkcan, Mehme; Zussman, Gil; Kostic, Zoran; Ghaderi, Javad (May 2025, in Proc. ICML’25, 2025)

   We propose a framework for adaptive data collection aimed at robust learning in multi-distribution scenarios under a fixed data collection budget. In each round, the algorithm selects a distribution source to sample from for data collection and updates the model parameters accordingly. The objective is to find the model parameters that minimize the expected loss across all the data sources. Our approach integrates upper-confidence-bound (UCB) sampling with online gradient descent (OGD) to dynamically collect and annotate data from multiple sources. By bridging online optimization and multi-armed bandits, we provide theoretical guarantees for our UCB-OGD approach, demonstrating that it achieves a minimax regret of O(T 1 2 (K ln T) 1 2 ) over K data sources after T rounds. We further provide a lower bound showing that the result is optimal up to a ln T factor. Extensive evaluations on standard datasets and a real-world testbed for object detection in smartcity intersections validate the consistent performance improvements of our method compared to baselines such as random sampling and various active learning methods. 

   more » « less
5. Computably Continuous Reinforcement-Learning Objectives are PAC-learnable

   Cambridge Yang; Michael Littman; Michael Carbin (January 2023, arXivorg)

   In reinforcement learning, the classic objectives of maximizing discounted and finite-horizon cumulative rewards are PAC-learnable: There are algorithms that learn a near-optimal policy with high probability using a finite amount of samples and computation. In recent years, researchers have introduced objectives and corresponding reinforcement-learning algorithms beyond the classic cumulative rewards, such as objectives specified as linear temporal logic formulas. However, questions about the PAC-learnability of these new objectives have remained open. This work demonstrates the PAC-learnability of general reinforcement-learning objectives through sufficient conditions for PAC-learnability in two analysis settings. In particular, for the analysis that considers only sample complexity, we prove that if an objective given as an oracle is uniformly continuous, then it is PAC-learnable. Further, for the analysis that considers computational complexity, we prove that if an objective is computable, then it is PAC-learnable. In other words, if a procedure computes successive approximations of the objective's value, then the objective is PAC-learnable. We give three applications of our condition on objectives from the literature with previously unknown PAC-learnability and prove that these objectives are PAC-learnable. Overall, our result helps verify existing objectives' PAC-learnability. Also, as some studied objectives that are not uniformly continuous have been shown to be not PAC-learnable, our results could guide the design of new PAC-learnable objectives. 

   more » « less