论文标题
与恶意专家一起在乘法学习系统中实现最佳的对抗性政策
Toward Optimal Adversarial Policies in the Multiplicative Learning System with a Malicious Expert
论文作者
论文摘要
我们考虑了一个基于常规乘法权重（MW）规则的学习系统，该规则结合了专家的建议，以预测一系列真实结果。假定其中一位专家是恶意的，旨在对系统造成最大损失。系统的丢失自然被定义为预测结果和真实结果的序列之间的总体差异。我们考虑在离线和在线设置下的这个问题。 In the offline setting where the malicious expert must choose its entire sequence of decisions a priori, we show somewhat surprisingly that a simple greedy policy of always reporting false prediction is asymptotically optimal with an approximation ratio of $1+O(\sqrt{\frac{\ln N}{N}})$, where $N$ is the total number of prediction stages.特别是，我们描述了一项与最佳离线政策结构相似的政策。对于恶意专家可以自适应做出决策的在线环境，我们表明可以通过在$ O（n^3）$中求解动态程序来有效地计算最佳的在线政策。我们的结果为对对抗性攻击的常用学习算法评估脆弱性评估提供了新的方向，而威胁是系统不可或缺的一部分。
We consider a learning system based on the conventional multiplicative weight (MW) rule that combines experts' advice to predict a sequence of true outcomes. It is assumed that one of the experts is malicious and aims to impose the maximum loss on the system. The loss of the system is naturally defined to be the aggregate absolute difference between the sequence of predicted outcomes and the true outcomes. We consider this problem under both offline and online settings. In the offline setting where the malicious expert must choose its entire sequence of decisions a priori, we show somewhat surprisingly that a simple greedy policy of always reporting false prediction is asymptotically optimal with an approximation ratio of $1+O(\sqrt{\frac{\ln N}{N}})$, where $N$ is the total number of prediction stages. In particular, we describe a policy that closely resembles the structure of the optimal offline policy. For the online setting where the malicious expert can adaptively make its decisions, we show that the optimal online policy can be efficiently computed by solving a dynamic program in $O(N^3)$. Our results provide a new direction for vulnerability assessment of commonly used learning algorithms to adversarial attacks where the threat is an integral part of the system.
