Malicious Experts Versus the Multiplicative Weights Algorithm in Online Prediction

DOI10.1109/TIT.2020.3025866MaRDI QIDQ5151731zbMATH OpenOpenAlexFDO

Authors Erhan Bayraktar, H. Vincent Poor, Xin Zhang

Publication date 22 February 2021

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.08457

zbMATH Keywords

malicious expertsmultiplicative weights algorithmprediction problemtwo experts and a forecaster

Mathematics Subject Classification ID

Viscosity solutions to Hamilton-Jacobi equations in optimal control and differential games (49L25) Statistical aspects of information-theoretic topics (62B10) Inference from stochastic processes and prediction (62M20) Optimal stochastic control (93E20)

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 upper and lower bounds for the value function of the malicious expert. 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.

Cited in

(4)

• scientific article; zbMATH DE number 7370589 (Why is no real title available?)
• Comparison for semi-continuous viscosity solutions for second order PDEs on the Wasserstein space
• Numerical solution of a PDE arising from prediction with expert advice
• Comparison of viscosity solutions for a class of second-order PDEs on the Wasserstein space

This page was built for publication: Malicious Experts Versus the Multiplicative Weights Algorithm in Online Prediction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5151731)