Optimal Attack Strategies Against Predictors - Learning from Expert Advice

Anh Truong, S. Rasoul Etesami, Jalal Etesami, Negar Kiyavash

Research output: Contribution to journalArticle

Abstract

Motivated by many real-world examples, such as recommendation systems or sensor fusion, and aiming to capture the influence of malicious experts who intentionally degrade the performance of learning systems, we analyze optimal adversarial strategies against the weighted average prediction algorithm in the learning with expert advice framework. All but one expert is honest and the malicious expert's goal is to sabotage the performance of the algorithm by strategically providing dishonest recommendations. We formulate the problem as a Markov decision process and analyze it under various settings. For the logarithmic loss, somewhat surprisingly, we prove that the optimal strategy for the adversary is the greedy policy, i.e., lying at every step. For the absolute loss, in the 2-experts, discounted cost setting, we prove that the optimal strategy is a threshold policy, where the malicious expert tells the truth until he earns enough weight and then lies afterwards. We extend the results to the infinite horizon problem and find the exact thresholds for the stationary optimal policy. Finally, we use a mean field approach in the N-experts setting to find the optimal strategy when the predictions of the honest experts are independent and identically distributed. We justify our results using simulations throughout this paper.

Original languageEnglish (US)
Article number7954673
Pages (from-to)6-19
Number of pages14
JournalIEEE Transactions on Information Forensics and Security
Volume13
Issue number1
DOIs
StatePublished - Jan 2018

Fingerprint

Recommender systems
Learning systems
Fusion reactions
Sensors
Costs

Keywords

  • Learning algorithm
  • Markov decision process
  • dynamic programming
  • expert advice
  • malicious experts
  • threshold policy
  • weighted average prediction

ASJC Scopus subject areas

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

Cite this

Optimal Attack Strategies Against Predictors - Learning from Expert Advice. / Truong, Anh; Etesami, S. Rasoul; Etesami, Jalal; Kiyavash, Negar.

In: IEEE Transactions on Information Forensics and Security, Vol. 13, No. 1, 7954673, 01.2018, p. 6-19.

Research output: Contribution to journalArticle

@article{a98b3a32bac74096a8d67e4fb9df0e38,
title = "Optimal Attack Strategies Against Predictors - Learning from Expert Advice",
abstract = "Motivated by many real-world examples, such as recommendation systems or sensor fusion, and aiming to capture the influence of malicious experts who intentionally degrade the performance of learning systems, we analyze optimal adversarial strategies against the weighted average prediction algorithm in the learning with expert advice framework. All but one expert is honest and the malicious expert's goal is to sabotage the performance of the algorithm by strategically providing dishonest recommendations. We formulate the problem as a Markov decision process and analyze it under various settings. For the logarithmic loss, somewhat surprisingly, we prove that the optimal strategy for the adversary is the greedy policy, i.e., lying at every step. For the absolute loss, in the 2-experts, discounted cost setting, we prove that the optimal strategy is a threshold policy, where the malicious expert tells the truth until he earns enough weight and then lies afterwards. We extend the results to the infinite horizon problem and find the exact thresholds for the stationary optimal policy. Finally, we use a mean field approach in the N-experts setting to find the optimal strategy when the predictions of the honest experts are independent and identically distributed. We justify our results using simulations throughout this paper.",
keywords = "Learning algorithm, Markov decision process, dynamic programming, expert advice, malicious experts, threshold policy, weighted average prediction",
author = "Anh Truong and Etesami, {S. Rasoul} and Jalal Etesami and Negar Kiyavash",
year = "2018",
month = "1",
doi = "10.1109/TIFS.2017.2718488",
language = "English (US)",
volume = "13",
pages = "6--19",
journal = "IEEE Transactions on Information Forensics and Security",
issn = "1556-6013",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "1",

}

TY - JOUR

T1 - Optimal Attack Strategies Against Predictors - Learning from Expert Advice

AU - Truong, Anh

AU - Etesami, S. Rasoul

AU - Etesami, Jalal

AU - Kiyavash, Negar

PY - 2018/1

Y1 - 2018/1

N2 - Motivated by many real-world examples, such as recommendation systems or sensor fusion, and aiming to capture the influence of malicious experts who intentionally degrade the performance of learning systems, we analyze optimal adversarial strategies against the weighted average prediction algorithm in the learning with expert advice framework. All but one expert is honest and the malicious expert's goal is to sabotage the performance of the algorithm by strategically providing dishonest recommendations. We formulate the problem as a Markov decision process and analyze it under various settings. For the logarithmic loss, somewhat surprisingly, we prove that the optimal strategy for the adversary is the greedy policy, i.e., lying at every step. For the absolute loss, in the 2-experts, discounted cost setting, we prove that the optimal strategy is a threshold policy, where the malicious expert tells the truth until he earns enough weight and then lies afterwards. We extend the results to the infinite horizon problem and find the exact thresholds for the stationary optimal policy. Finally, we use a mean field approach in the N-experts setting to find the optimal strategy when the predictions of the honest experts are independent and identically distributed. We justify our results using simulations throughout this paper.

AB - Motivated by many real-world examples, such as recommendation systems or sensor fusion, and aiming to capture the influence of malicious experts who intentionally degrade the performance of learning systems, we analyze optimal adversarial strategies against the weighted average prediction algorithm in the learning with expert advice framework. All but one expert is honest and the malicious expert's goal is to sabotage the performance of the algorithm by strategically providing dishonest recommendations. We formulate the problem as a Markov decision process and analyze it under various settings. For the logarithmic loss, somewhat surprisingly, we prove that the optimal strategy for the adversary is the greedy policy, i.e., lying at every step. For the absolute loss, in the 2-experts, discounted cost setting, we prove that the optimal strategy is a threshold policy, where the malicious expert tells the truth until he earns enough weight and then lies afterwards. We extend the results to the infinite horizon problem and find the exact thresholds for the stationary optimal policy. Finally, we use a mean field approach in the N-experts setting to find the optimal strategy when the predictions of the honest experts are independent and identically distributed. We justify our results using simulations throughout this paper.

KW - Learning algorithm

KW - Markov decision process

KW - dynamic programming

KW - expert advice

KW - malicious experts

KW - threshold policy

KW - weighted average prediction

UR - http://www.scopus.com/inward/record.url?scp=85021809302&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85021809302&partnerID=8YFLogxK

U2 - 10.1109/TIFS.2017.2718488

DO - 10.1109/TIFS.2017.2718488

M3 - Article

AN - SCOPUS:85021809302

VL - 13

SP - 6

EP - 19

JO - IEEE Transactions on Information Forensics and Security

JF - IEEE Transactions on Information Forensics and Security

SN - 1556-6013

IS - 1

M1 - 7954673

ER -