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

S. Rasoul Etesami, Negar Kiyavash, Vincent Léon, H. Vincent Poor

TL;DR

This paper investigates the robustness of the multiplicative weight (MW) learning algorithm against a malicious expert aiming to maximize the system's prediction error. The authors show that a simple "always lie" strategy is surprisingly close to optimal for an offline adversary, and they provide an efficient dynamic programming approach to find the optimal strategy for an online, adaptive adversary. This work is crucial for understanding and defending against internal threats in real-world machine learning systems.

What Problem Does This Paper Address?

Many real-world systems, like recommendation engines (Netflix, IMDB) or sensor networks, rely on combining advice from multiple "experts" to make predictions. The standard approach, often using the Multiplicative Weight (MW) algorithm, assumes these experts are honest and aim for accurate predictions. However, what happens when one of these experts is malicious and actively tries to maximize the system's prediction error? This paper tackles this critical vulnerability. The challenge lies in characterizing the optimal strategy for such a malicious expert and understanding how well the standard MW algorithm performs under this adversarial pressure, especially when the adversary can be either strategic from the outset (offline) or adaptively choose their moves based on past information (online).

Methods

The paper analyzes two scenarios for the malicious expert:

  • Offline Adversary: The malicious expert commits to a fixed sequence of predictions before the learning process begins. The authors surprisingly find that a simple greedy strategy – always predicting the opposite of the true outcome – is asymptotically optimal. They also propose a "ratio policy" that closely mimics the optimal offline strategy and provides a strong approximation guarantee.
  • Online Adversary: The malicious expert can adapt its predictions at each step, using all available information up to that point. The authors formulate this as a dynamic programming (DP) problem. They cleverly show that the state space of this DP grows polynomially (specifically, $O(N^2)$ states), allowing for an efficient computation of the optimal online policy in $O(N^3)$ time.

The core mathematical tools involve analyzing the multiplicative weight update rule, deriving expressions for expected loss under different adversarial policies, and leveraging probability distributions (Binomial, Normal CDF) and theorems like Berry-Esseen for bounding errors.

Datasets

Not discussed in the paper. The evaluation is done through numerical simulations presented in figures.

Key Insights and Ideas

  • "Always Lie" is Surprisingly Effective: The most striking finding is that for an offline adversary, a simple strategy of consistently predicting the opposite of the true outcome is nearly as good as any complex, pre-planned strategy. This suggests that the MW algorithm, while effective against honest experts, is inherently vulnerable to even basic adversarial behavior.
  • Offline vs. Online Adversary: While the offline adversary's optimal strategy is simple, the online adversary's optimal strategy can be more complex, requiring adaptive decision-making. However, the paper shows this complexity can be managed efficiently.
  • MW Algorithm's Vulnerability: The results strongly indicate that the standard MW algorithm is not robust to malicious internal threats. A malicious expert doesn't need sophisticated intelligence; a simple, consistent adversarial strategy can inflict significant damage.
  • Efficient Online Policy Computation: The paper provides a practical solution for the online setting by formulating it as a DP and demonstrating its efficient solvability, making it feasible to determine the optimal adversarial strategy in polynomial time.

Key Results

  • Offline Adversary: The "always lie" policy achieves an approximation ratio of $1+O(\sqrt{\frac{\ln N}{N}})$ compared to the optimal offline policy, where $N$ is the number of prediction stages. This means the simple strategy is almost as good as the best possible one.
  • Online Adversary: An efficient $O(N^3)$ algorithm is presented to compute the optimal online adversarial policy.
  • Generalization: The framework is extended to handle multiple honest experts with varying accuracies, showing that a 2-expert model can approximate the behavior of multiple homogeneous honest experts.

Limitations and Future Work

  • Focus on Absolute Loss: The analysis primarily focuses on the absolute loss function ($| \hat{y} - y |$). While this is common, other loss functions might yield different results.
  • Specific MW Rule: The study is centered on the multiplicative weight update rule. Future work could explore the robustness of other learning algorithms (e.g., Upper Confidence Bound).
  • Closed-Form Online Policy: While an efficient DP exists, a closed-form characterization of the optimal online policy is still an open question.
  • Game-Theoretic Extension: The authors suggest exploring a game-theoretic version where the learning system can actively detect and remove malicious experts, rather than just penalizing them.
  • Mean-Field Approximation: For systems with a very large number of experts, using mean-field approximations to study optimal policies is proposed as a future direction.

Summary updated

BibTeX
@article{etesami2021optimal,
  author = {S. Rasoul Etesami and Negar Kiyavash and Vincent Léon and H. Vincent Poor},
  title = {{Optimal Adversarial Policies in the Multiplicative Learning System With a Malicious Expert}},
  journal = {IEEE Trans. Inf. Forensics Secur.},
  year = {2021},
  url = {https://openreview.net/forum?id=v6S_3D9f8km},
}
Figure