Communication-Efficient Distributed Machine Learning over Strategic Networks: A Two-Layer Game Approach

Shutian Liu, Tao Li, Quanyan Zhu

Introduction

In traditional distributed machine learning (DML), such as Federated Learning, the communication topology is typically assumed to be static and pre-defined. However, this assumption often fails in real-world scenarios where agents are self-interested, data is non-IID (not identically and independently distributed), and communication resources are constrained. Forcing a node with highly specific or biased data to reach a hard consensus with a global network can actually degrade its local performance.

This paper introduces a novel game-theoretic framework for Strategic Network Design. Instead of treating the network as a fixed constraint, the authors model it as a strategic outcome. In this setup, nodes act as rational players that optimize both their local learning parameters and their network connections to minimize a personal "disutility" function—a balance between local prediction accuracy and the cost of disagreement with chosen neighbors.

The Strategic Framework

The core of the proposed approach is a non-zero-sum infinite game where each node $i$ performs two interrelated actions:

  1. Learning Action ($u_i$): Optimizing model parameters (e.g., classifier weights) to minimize error on local datasets.
  2. Network Formation Action ($m^i$): Selecting link weights to other nodes. High weights indicate a high degree of trust or relevance, while low weights allow nodes to ignore unhelpful or noisy neighbors.
Overview of the two-layer game approach combining distributed learning and strategic network formation.

By coupling these actions, the network structure evolves alongside the learning process. The system eventually reaches a Nash Equilibrium, where no node can further reduce its disutility by unilaterally changing its parameters or its connections.

Algorithmic Approaches

The authors propose three distinct methods to solve this two-layer optimization problem:

  • Commutative Approach: An iterative two-layer process. Nodes first update their learning parameters for a fixed network, then refine the network structure using the Alternating Direction Method of Multipliers (ADMM) based on the updated parameters.
  • Concurrent Approach: Utilizing Online Mirror Descent (OMD), nodes update learning and network actions simultaneously. This method is particularly robust for directed networks and environments prone to communication noise.
  • Streaming Adaptation: For real-time applications with sequential data, the framework is adapted into a Distributed Kalman Filter version, allowing for continuous model and topology updates.

Theoretical analysis proves that for undirected networks, this framework constitutes a generalized potential game, guaranteeing convergence to a stable Nash Equilibrium.

Key Insights and Results

Soft Consensus and Strategic Sparsity

Unlike standard consensus algorithms that force all nodes toward a single global model, this framework enables "soft consensus." This allows for the emergence of clusters—subgroups of nodes with similar data distributions that agree with each other while maintaining distance from irrelevant groups. Furthermore, by incorporating communication costs (similar to $l_1$ regularization), the network naturally becomes sparse, as nodes stop wasting resources on neighbors that do not improve their local learning task.

Performance Gains

The researchers validated their framework using the Parkinson’s Disease Telemonitoring dataset, simulating a network of hospitals with varying degrees of data bias. The results demonstrated that strategic design is mathematically guaranteed to perform no worse than fixed-network learning. In practice, it often performs significantly better; when nodes are allowed to be "selfish" about their connections, the overall social welfare (the sum of all players' performance) increases because harmful or irrelevant data sources are strategically ignored.

Structural Emergence

The study observed the emergence of core-periphery structures. Nodes with sparse or low-quality data naturally gravitate toward the "core" to seek information from high-quality hubs, while nodes with robust local data remain more independent or act as central providers of information.

Future Directions

While the current model assumes honest participation, future work could explore Bayesian games to account for privacy-preserving strategies or deceptive nodes. Additionally, the use of Stackelberg games could model hierarchical networks where certain nodes (e.g., those with massive datasets) hold more influence over the network formation process than others.

Summary updated

Abstract

This paper considers a game-theoretic framework for distributed machine learning problems over networks where the information acquisition at a node is modeled as a rational choice of a player. In the proposed game, players decide both the learning parameters and the network structure. The Nash equilibrium characterizes the tradeoff between the local performance and the global agreement of the learned classifiers. We first introduce a commutative approach which features a joint learning process that integrates the iterative learning at each node and the network formation. We show that our game is equivalent to a generalized potential game in the setting of undirected networks. We study the convergence of the proposed commutative algorithm, analyze the network structures determined by our game, and show the improvement of the social welfare in comparison with standard distributed learning over fixed networks. To adapt our framework to streaming data, we derive a distributed Kalman filter. A concurrent algorithm based on the online mirror descent algorithm is also introduced for solving for Nash equilibria in a holistic manner. In the case study, we use telemonitoring of Parkinson's disease to corroborate the results.
BibTeX
@misc{liu2020communication,
  author = {Shutian Liu and Tao Li and Quanyan Zhu},
  title = {{Communication-Efficient Distributed Machine Learning over Strategic Networks: A Two-Layer Game Approach}},
  year = {2020},
  eprint = {2011.01455},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2011.01455},
}
Figure