skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Collaborative PAC Learning
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
Award ID(s):
1525971 1331175 1733556 1714140
PAR ID:
10057475
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
NIPS 2017
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, 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. ; ; ; (, 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. ; ; ; (, 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. ; ; (, 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
  5. ; ; ; ; ; ; ; ; ; (, Inorganic Chemistry)
    Four groups of rare-earth complexes, comprising 11 new compounds, with fluorinated O-donor ligands ([K(THF)6][Ln(OC4F9)4(THF)2] (1-Ln; Ln = Ce, Nd), [K](THF)x[Ln(OC4F9)4(THF)y] (2-Ln; Ln = Eu, Gd, Dy), [K(THF)2][Ln(pinF)2(THF)3] (3-Ln; Ln = Ce, Nd), and [K(THF)2][Ln(pinF)2(THF)2] (4-Ln; Ln = Eu, Gd, Dy, Y) have been synthesized and characterized. Single-crystal X-ray diffraction data were collected for all compounds except 2-Ln. Species 1-Ln, 3-Ln, and 4-Ln are uncommon examples of six-coordinate (Eu, Gd, Dy, and Y) and seven-coordinate (Ce and Nd) LnIII centers in all-O-donor environments. Species 1-Ln, 2-Ln, 3-Ln, and 4-Ln are all luminescent (except where Ln = Gd and Y), with the solid-state emission of 1-Ce being exceptionally blue-shifted for a Ce complex. The emission spectra of the six Nd, Eu, and Dy complexes do not show large differences based on the ligand and are generally consistent with the well-known free-ion spectra. Time-dependent density functional theory results show that 1-Ce and 3-Ce undergo allowed 5f → 4d excitations, consistent with luminescence lifetime measurements in the nanosecond range. Eu-containing 2-Eu and 4-Eu, however, were found to have luminescence lifetimes in the millisecond range, indicating phosphorescence rather than fluorescence. The performance of a pair of multireference models for prediction of the Ln = Nd, Eu, and Dy absorption spectra was assessed. It was found that spectroscopy-oriented configuration interaction as applied to a simplified model in which the free-ion lanthanide was embedded in ligand-centered Löwdin point charges performed as well (Nd) or better (Eu and Dy) than canonical NEVPT2 calculations, when the ligand orbitals were included in the treatment. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email