Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Optimal Adversarial Policies in the Multiplicative Learning System With a Malicious Expert
 
research article

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

Etesami, S. Rasoul
•
Kiyavash, Negar  
•
Leon, Vincent
Show more
January 1, 2021
Ieee Transactions On Information Forensics And Security

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(root 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). 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.

  • Details
  • Metrics
Type
research article
DOI
10.1109/TIFS.2021.3052360
Web of Science ID

WOS:000617315800008

Author(s)
Etesami, S. Rasoul
Kiyavash, Negar  
Leon, Vincent
Poor, H. Vincent
Date Issued

2021-01-01

Publisher

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC

Published in
Ieee Transactions On Information Forensics And Security
Volume

16

Start page

2276

End page

2287

Subjects

Computer Science, Theory & Methods

•

Engineering, Electrical & Electronic

•

Computer Science

•

Engineering

•

adversarial learning

•

expert advice

•

markov decision process

•

dynamic programming

•

approximation ratio

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
BAN  
Available on Infoscience
March 26, 2021
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/176571
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés