Malicious Experts versus the multiplicative weights algorithm in online prediction
This addresses a security issue in online learning algorithms for scenarios involving adversarial experts, though it is incremental as it builds on known multiplicative weights methods.
The paper tackles the problem of online prediction with one honest and one malicious expert, where the malicious expert aims to maximize the forecaster's loss. It finds that the classical multiplicative weights algorithm is vulnerable to such corruption, but an adaptive version is asymptotically optimal and more resistant.
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.