Defending non-Bayesian learning against adversarial attacks

By Lili Su, Nitin H. Vaidya. 2016

54 citations recorded by the source corpus.

This paper addresses the problem of non-Bayesian learning over multi-agent networks, where agents repeatedly collect partially informative observations about an unknown state of the world, and try to collaboratively learn the true state out of m alternatives. We focus on the impact of adversarial agents on the performance of consensus-based non-Bayesian learning, where non-faulty agents combine local learning updates with consensus primitives. In particular, we consider the scenario where an unknown subset of agents suffer Byzantine faults—agents suffering Byzantine faults behave arbitrarily. We propose two learning rules. In our learning rules, each non-faulty agent keeps a local variable which is a stochastic vector over the m possible states. Entries of this stochastic vector can be viewed as the scores assigned to the corresponding states by that agent. We say a non-faulty agent learns the underlying truth if it assigns one to the true state and zeros to the wrong states asymptotically. In our first update rule, each agent updates its local score vector as (up to normalization) the product of (1) the likelihood of the cumulative private signals and (2) the weighted geometric average of the score vectors of its incoming neighbors and itself. Under reasonable assumptions on the underlying network structure and the global identifiability of the network, we show that all the non-faulty agents asymptotically learn the true state almost surely. We propose a modified variant of our first learning rule whose complexity per iteration per agent is O(m2nlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(m^2 n \log n)$$\end{document}, where n is the number of agents in the network. In addition, we show that this modified learning rule works under a less restrictive network identifiability condition. In our first update rule, each agent updates its local score vector as (up to normalization) the product of (1) the likelihood of the cumulative private signals and (2) the weighted geometric average of the score vectors of its incoming neighbors and itself. Under reasonable assumptions on the underlying network structure and the global identifiability of the network, we show that all the non-faulty agents asymptotically learn the true state almost surely. We propose a modified variant of our first learning rule whose complexity per iteration per agent is O(m2nlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(m^2 n \log n)$$\end{document}, where n is the number of agents in the network. In addition, we show that this modified learning rule works under a less restrictive network identifiability condition.

Subfields: Artificial Intelligence, Computer Networks and Communications, Control and Systems Engineering, Safety, Robustness & Interpretability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Control and Systems Engineering

In Safety, Robustness & Interpretability

Citations in the corpus

Zeno++: Robust Fully Asynchronous SGD (2019, background): “In particular, tolerance to Byzantine failures (Blanchard et al., 2017; Chen et al., 2017; Yin et al., 2018; Feng et al., 2014; Su & Vaidya, 2016; 2018; Xie et al., 2019b; Alistarh et al., 2018; Cao & Lai, 2018; Xie et al., 2019c) has become an important topic in the distributed machine learning…”
Zeno: Byzantine-suspicious stochastic gradient descent (2018, methodology): “For example, Chen et al. [4], Su and Vaidya [17, 18] use geometric median as the aggregation rule.”
Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation (2019, background): “Most of the existing Byzantine-tolerant machine-learning algorithms (Blanchard et al., 2017; Chen et al., 2017; Yin et al., 2018; Feng et al., 2014; Su & Vaidya, 2016a;b; Alistarh et al., 2018) focus on the protection of distributed Stochastic Gradient Descent (SGD).”
Zeno: Distributed Stochastic Gradient Descent with Suspicion-based Fault-tolerance (2018, methodology): “Despite their differences, the existing majority-based methods for synchronous SGD (Blanchard et al., 2017; Chen et al., 2017; Yin et al., 2018; Su & Vaidya, 2016a; Alistarh et al., 2018) assume that the non-faulty workers dominate the entire set of workers.”
Zeno++: robust asynchronous SGD with arbitrary number of Byzantine workers (2019, background): “For this reason, fault tolerance in distributed settings has attracted increasing attention in the machine-learning community [1, 2, 3, 5, 13, 14, 15, 16].”