Malicious Experts Versus the Multiplicative Weights Algorithm in Online Prediction

Erhan Bayraktar, H. Vincent Poor, Xin Zhang

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

We consider a prediction problem with two experts and a forecaster. We assume that one of the experts is honest and makes correct prediction with probability $\mu $ at each round. The other one is malicious, who knows true outcomes at each round and makes predictions in order to maximize the loss of the forecaster. Assuming the forecaster adopts the classical multiplicative weights algorithm, we find an upper bound (5) for the value function of the malicious expert, and also a lower bound (19). Our results imply that the multiplicative weights algorithm cannot resist the corruption of malicious experts. We also show that an adaptive multiplicative weights algorithm is asymptotically optimal for the forecaster, and hence more resistant to the corruption of malicious experts.

Original languageEnglish (US)
Article number9203984
Pages (from-to)559-565
Number of pages7
JournalIEEE Transactions on Information Theory
Volume67
Issue number1
DOIs
StatePublished - Jan 2021
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Adversarial online learning
  • dynamic programming
  • multiplicative weights algorithm
  • partial differential equation approach
  • viscosity solutions

Fingerprint

Dive into the research topics of 'Malicious Experts Versus the Multiplicative Weights Algorithm in Online Prediction'. Together they form a unique fingerprint.

Cite this