Learning from sleeping experts: Rewarding informative, available, and accurate experts

A. Truong, S. R. Etesami, N. Kiyavash

Research output: Contribution to journalArticle

Abstract

We consider a generalized model of learning from expert advice in which experts could abstain from participating at some rounds. Our proposed online algorithm falls into the class of weighted average predictors and uses a time-varying multiplicative weight update rule. This update rule changes the weight of an expert based on his or her relative performance compared to the average performance of available experts at the current round. This makes the algorithm suitable for recommendation systems in the presence of an adversary with many potential applications in the new emerging area of the Internet of Things. We prove the convergence of our algorithm to the best expert, defined in terms of both availability and accuracy, in the stochastic setting. In particular, we show the applicability of our definition of best expert through convergence analysis of another well-known algorithm in this setting. Finally, through simulation results on synthetic and real datasets, we justify the out-performance of our proposed algorithms compared to the existing ones in the literature.

Original languageEnglish (US)
Article number77
JournalACM Transactions on Design Automation of Electronic Systems
Volume23
Issue number6
DOIs
StatePublished - Nov 2018

Keywords

  • Accuracy
  • Availability
  • Convergence analysis
  • Internet of Things
  • Learning
  • Performance based
  • Sleeping expert
  • Stochastic approximation
  • Weighted average predictor

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Learning from sleeping experts: Rewarding informative, available, and accurate experts'. Together they form a unique fingerprint.

  • Cite this