Abstract
Many signal processing and machine learning problems can be formulated as consensus optimization problems which can be solved efficiently via a cooperative multi-agent system. However, the agents in the system can be unreliable due to a variety of reasons: noise, faults and attacks. Providing erroneous updates leads the optimization process in a wrong direction, and degrades the performance of distributed machine learning algorithms. This paper considers the problem of decentralized learning using ADMM in the presence of unreliable agents. First, we rigorously analyze the effect of erroneous updates (in ADMM learning iterations) on the convergence behavior of the multi-agent system. We show that the algorithm linearly converges to a neighborhood of the optimal solution under certain conditions and characterize the neighborhood size analytically. Next, we provide guidelines for network design to achieve a faster convergence to the neighborhood. We also provide conditions on the erroneous updates for exact convergence to the optimal solution. Finally, to mitigate the influence of unreliable agents, we propose ROAD, a robust variant of ADMM, and show its resilience to unreliable agents with an exact convergence to the optimum.
Introduction
Decentralized learning allows a network of agents to collaboratively solve a global optimization problem—such as training a machine learning model—without the need for a central server. The Alternating Direction Method of Multipliers (ADMM) is a popular choice for these tasks due to its speed and suitability for consensus-based problems. However, most existing research assumes an "ideal" world where every agent is reliable and communication is perfect.
In practice, decentralized systems are vulnerable: nodes might crash, communication links might be noisy, or malicious actors might inject "Byzantine" errors to steer the model toward a wrong solution. While previous work on "inexact ADMM" looked at small, vanishing errors, this research tackles the challenge of arbitrary and persistent errors, providing both a mathematical roadmap of how they degrade performance and a concrete algorithm to mitigate their impact.
Theoretical Analysis and the ROAD Algorithm
The authors first perform a comprehensive convergence analysis for both convex and strongly convex cost functions. They prove that under standard ADMM, the system doesn't necessarily fail but instead converges to a neighborhood of the optimal solution. The size of this neighborhood depends on the network topology and the magnitude of the errors.
To overcome this "noise floor," the paper introduces ROAD (Robust Decentralized ADMM). The key innovation is a local detection mechanism that allows agents to identify and filter out erroneous updates without disconnecting the network. Each agent tracks how much its neighbors' updates deviate from the local consensus over time. Using an analytically derived threshold ($U$), agents identify "unreliable" neighbors. If a neighbor is deemed unreliable, the agent ignores that neighbor's update and replaces it with its own local value for that iteration.
This approach maintains the underlying communication graph's connectivity, which is vital for the overall system's health. Unlike some robust algorithms that "cut" links to suspicious nodes (which can lead to network fragmentation), ROAD simply ignores the suspicious data for that specific step.
Experimental Evaluation and Results
The authors evaluated their approach using two main benchmarks: Decentralized Linear Regression (a synthetic setup with 10 agents) and MNIST Binary Classification (a real-world task classifying handwritten digits).
The analysis revealed a fascinating tension in network topology: highly connected networks converge faster in ideal conditions but also spread errors more effectively. A less connected network might be more resilient because it localizes the impact of a few bad actors. For strongly convex problems, standard ADMM still converges linearly but hits a plateau. This plateau (the neighborhood size) can be minimized by tuning the ADMM penalty parameter and designing the network structure.
As shown in the performance comparison, standard ADMM fluctuates wildly or converges to a high error state when noise is injected. In contrast, ROAD achieves the same convergence rate as an error-free system. In the MNIST classification experiment, ROAD successfully recovered a classifier nearly identical to the one produced by a perfectly reliable network, whereas standard ADMM learned an incorrect classifier.
Conclusion and Future Work
ROAD provides a robust framework for decentralized learning, though the authors acknowledge several areas for further exploration. The algorithm currently assumes that for any given agent, the majority of its neighbors are reliable. Additionally, calculating the optimal threshold requires knowledge of some global properties, such as the Lipschitz constant of the gradient, which might not always be available in a fully decentralized setting. Future work will look into extending this analysis to asynchronous settings and non-convex functions, such as those found in deep neural networks.
Summary updated