\mathsf{VISTA}: Decentralized Machine Learning in Adversary Dominated Environments
For decentralized learning systems vulnerable to majority adversaries, this work provides a practical and theoretically grounded approach to maintain convergence despite adversarial dominance.
This paper addresses decentralized machine learning under adversary-dominated settings where malicious workers outnumber honest ones. It proposes VISTA, an adaptive algorithm that tunes acceptance thresholds based on optimization history, achieving improved convergence over static thresholds and retaining asymptotic convergence behavior of standard SGD without an honest majority.
Decentralized machine learning often relies on outsourcing computations, such as gradient evaluations, to untrusted worker nodes. Existing robust aggregation methods can mitigate malicious behavior under honest-majority assumptions, but may fail when adversaries control a majority of the workers. We study this adversary-dominated setting through an incentive-oriented framework in which reports are accepted and rewarded only when they are mutually consistent up to a threshold. This turns the adversary from a pure saboteur into a rational agent that trades off increasing estimation error against the risk of rejection and loss of reward. We consider iterative optimization under this model. Unlike one-shot computation, iterative learning requires long-horizon decisions: permissive acceptance rules enable faster early progress but admit more adversarial corruption, while strict rules improve estimation accuracy but cause frequent rejections. We propose \mathsf{VISTA}, an adaptive algorithm that tunes the acceptance threshold using the optimization history. Numerical results show that \mathsf{VISTA} improves convergence over static thresholds. We also provide a rigorous convergence analysis showing that, with suitable incentive-aware adaptation, adversary-dominated decentralized learning can retain the asymptotic convergence behavior of standard SGD without relying on an honest majority.