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

A. Truong, Seyed Rasoul 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

Fingerprint

Recommender systems
Availability
Internet of things

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

Cite this

Learning from sleeping experts : Rewarding informative, available, and accurate experts. / Truong, A.; Etesami, Seyed Rasoul; Kiyavash, N.

In: ACM Transactions on Design Automation of Electronic Systems, Vol. 23, No. 6, 77, 11.2018.

Research output: Contribution to journalArticle

@article{06dabe80416a4f4da6f05e5584ea6d48,
title = "Learning from sleeping experts: Rewarding informative, available, and accurate experts",
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.",
keywords = "Accuracy, Availability, Convergence analysis, Internet of Things, Learning, Performance based, Sleeping expert, Stochastic approximation, Weighted average predictor",
author = "A. Truong and Etesami, {Seyed Rasoul} and N. Kiyavash",
year = "2018",
month = "11",
doi = "10.1145/3236617",
language = "English (US)",
volume = "23",
journal = "ACM Transactions on Design Automation of Electronic Systems",
issn = "1084-4309",
publisher = "Association for Computing Machinery (ACM)",
number = "6",

}

TY - JOUR

T1 - Learning from sleeping experts

T2 - Rewarding informative, available, and accurate experts

AU - Truong, A.

AU - Etesami, Seyed Rasoul

AU - Kiyavash, N.

PY - 2018/11

Y1 - 2018/11

N2 - 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.

AB - 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.

KW - Accuracy

KW - Availability

KW - Convergence analysis

KW - Internet of Things

KW - Learning

KW - Performance based

KW - Sleeping expert

KW - Stochastic approximation

KW - Weighted average predictor

UR - http://www.scopus.com/inward/record.url?scp=85056384435&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85056384435&partnerID=8YFLogxK

U2 - 10.1145/3236617

DO - 10.1145/3236617

M3 - Article

AN - SCOPUS:85056384435

VL - 23

JO - ACM Transactions on Design Automation of Electronic Systems

JF - ACM Transactions on Design Automation of Electronic Systems

SN - 1084-4309

IS - 6

M1 - 77

ER -