Optimal Adversarial Policies in the Multiplicative Learning System with a Malicious Expert

S. Rasoul Etesami, Negar Kiyavash, Vincent Leon, H. Vincent Poor

Research output: Contribution to journalArticlepeer-review

Abstract

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 system's loss 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\left({\sqrt {\frac {\ln N}{N}}}\right)$ , 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})$. We also discuss a generalization of our model to multi-expert settings. Our results provide a new direction for vulnerability assessment of commonly-used learning algorithms to internal adversarial attacks.

Original languageEnglish (US)
Article number9328196
Pages (from-to)2276-2287
Number of pages12
JournalIEEE Transactions on Information Forensics and Security
Volume16
DOIs
StatePublished - 2021
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Safety, Risk, Reliability and Quality
  • Computer Networks and Communications

Keywords

  • Adversarial learning
  • Markov decision process
  • approximation ratio
  • dynamic programming
  • expert advice

Fingerprint Dive into the research topics of 'Optimal Adversarial Policies in the Multiplicative Learning System with a Malicious Expert'. Together they form a unique fingerprint.

Cite this