2020/03/18 by Erhan Bayraktar, H. Vincent Poor, Bayraktar, Erhan +3 · 1 citation
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Optimization and Search Problems #Probability (math.PR) #cs.LG #math.OC #math.PR
paper · pdf · doi:10.48550/arxiv.2003.08457
Keywords: Adversarial online learning, multiplicative weights algorithm, dynamic programming, partial differential equation approach, viscosity solutions
arxiv created 2020/03/18 · openalex publication_date 2020/03/18 · arxiv updated 2020/03/20 · openalex created_date 2020/03/23 · openalex updated_date 2026/07/28
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 μ 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.