  Decentralized Multi-agent Learning (DML) enables collaborative model training
while preserving data privacy. However, inherent heterogeneity in agents'
resources (computation, communication, and task size) may lead to substantial
variations in training time. This heterogeneity creates a bottleneck,
lengthening the overall training time due to straggler effects and potentially
wasting spare resources of faster agents. To minimize training time in
heterogeneous environments, we present a Communication-Efficient Training
Workload Balancing for Decentralized Multi-Agent Learning (ComDML), which
balances the workload among agents through a decentralized approach. Leveraging
local-loss split training, ComDML enables parallel updates, where slower agents
offload part of their workload to faster agents. To minimize the overall
training time, ComDML optimizes the workload balancing by jointly considering
the communication and computation capacities of agents, which hinges upon
integer programming. A dynamic decentralized pairing scheduler is developed to
efficiently pair agents and determine optimal offloading amounts. We prove that
in ComDML, both slower and faster agents' models converge, for convex and
non-convex functions. Furthermore, extensive experimental results on popular
datasets (CIFAR-10, CIFAR-100, and CINIC-10) and their non-I.I.D. variants,
with large models such as ResNet-56 and ResNet-110, demonstrate that ComDML can
significantly reduce the overall training time while maintaining model
accuracy, compared to state-of-the-art methods. ComDML demonstrates robustness
in heterogeneous environments, and privacy measures can be seamlessly
integrated for enhanced data protection.
