A min-rule distributed learning algorithm for hypothesis testing achieves network-independent exponential convergence rates and Byzantine resilience, outperforming belief-averaging methods.
Matrix Representation of Iterative Approximate Byzantine Consensus in Directed Graphs
6 Pith papers cite this work. Polarity classification is still indexing.
6
Pith papers citing it
abstract
This paper presents a proof of correctness of an iterative approximate Byzantine consensus (IABC) algorithm for directed graphs. The iterative algorithm allows fault- free nodes to reach approximate conensus despite the presence of up to f Byzantine faults. Necessary conditions on the underlying network graph for the existence of a correct IABC algorithm were shown in our recent work [15, 16]. [15] also analyzed a specific IABC algorithm and showed that it performs correctly in any network graph that satisfies the necessary condition, proving that the necessary condition is also sufficient. In this paper, we present an alternate proof of correctness of the IABC algorithm, using a familiar technique based on transition matrices [9, 3, 17, 19]. The key contribution of this paper is to exploit the following observation: for a given evolution of the state vector corresponding to the state of the fault-free nodes, many alternate state transition matrices may be chosen to model that evolution cor- rectly. For a given state evolution, we identify one approach to suitably "design" the transition matrices so that the standard tools for proving convergence can be applied to the Byzantine fault-tolerant algorithm as well. In particular, the transition matrix for each iteration is designed such that each row of the matrix contains a large enough number of elements that are bounded away from 0.
citation-role summary
method 1
citation-polarity summary
roles
method 1polarities
use method 1representative citing papers
Under strong monotonicity, a standard connectivity condition, and a slowly drifting equilibrium, the proposed DBROSA algorithm with trimmed-mean filtering and variance-reduced gradients keeps expected regret and constraint violation sublinear in online stochastic multi-cluster games with Byzantine…
A trimmed-mean decentralized TD(λ) algorithm is shown to converge near the ideal value function under Byzantine attacks, with finite-time rates and asymptotic error bounds depending on network and reward heterogeneity.
BRIDGE combines coordinate-wise trimmed mean with decentralized gradient descent to achieve Byzantine-resilient consensus and sublinear convergence to the statistical risk minimizer under strong convexity.
A structured review of Byzantine-robust distributed and decentralized inference and learning, with tables of guarantees and experimental comparisons of screening-based aggregation methods.
citing papers explorer
-
A New Approach to Distributed Hypothesis Testing and Non-Bayesian Learning: Improved Learning Rate and Byzantine-Resilience
A min-rule distributed learning algorithm for hypothesis testing achieves network-independent exponential convergence rates and Byzantine resilience, outperforming belief-averaging methods.
-
Decentralized online stochastic generalized Nash Equilibrium seeking for multi-cluster games: A Byzantine-resilient algorithm
Under strong monotonicity, a standard connectivity condition, and a slowly drifting equilibrium, the proposed DBROSA algorithm with trimmed-mean filtering and variance-reduced gradients keeps expected regret and constraint violation sublinear in online stochastic multi-cluster games with Byzantine…
-
Byzantine-Resilient Decentralized TD Learning with Linear Function Approximation
A trimmed-mean decentralized TD(λ) algorithm is shown to converge near the ideal value function under Byzantine attacks, with finite-time rates and asymptotic error bounds depending on network and reward heterogeneity.
-
BRIDGE: Byzantine-resilient Decentralized Gradient Descent
BRIDGE combines coordinate-wise trimmed mean with decentralized gradient descent to achieve Byzantine-resilient consensus and sublinear convergence to the statistical risk minimizer under strong convexity.
-
Adversary-resilient Distributed and Decentralized Statistical Inference and Machine Learning: An Overview of Recent Advances Under the Byzantine Threat Model
A structured review of Byzantine-robust distributed and decentralized inference and learning, with tables of guarantees and experimental comparisons of screening-based aggregation methods.
- RESIST: Resilient Decentralized Learning Using Consensus Gradient Descent