论文标题
在线预测中，恶意专家与乘法算法
Malicious Experts versus the multiplicative weights algorithm in online prediction
论文作者
论文摘要
我们考虑了两个专家和一个预报员的预测问题。我们假设其中一位专家是诚实的，并且在每回合时以概率$μ$进行正确的预测。另一个是恶意的，他在每轮比赛中都知道真实的结果，并做出预测，以最大程度地提高预报员的损失。假设预报员采用了经典的乘法算法，我们为恶意专家的价值函数找到上限和下限。我们的结果表明，乘法算法无法抵抗恶意专家的腐败。我们还表明，适应性乘法算法对预报员渐近最佳，因此对恶意专家的腐败具有更大的抵抗力。
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.
