Gramian-Based Adaptive Combination Policies for Diffusion Learning over Networks

Y. Efe Erginbas, Stefan Vlaski, Ali H. Sayed

Abstract

This paper presents an adaptive combination strategy for distributed learning over diffusion networks. Since learning relies on the collaborative processing of the stochastic information at the dispersed agents, the overall performance can be improved by designing combination policies that adjust the weights according to the quality of the data. Such policies are important because they would add a new degree of freedom and endow multi-agent systems with the ability to control the flow of information over their edges for enhanced performance. Most adaptive and static policies available in the literature optimize certain performance metrics related to steady-state behavior, to the detriment of transient behavior. In contrast, we develop an adaptive combination rule that aims at optimizing the transient learning performance, while maintaining the enhanced steady-state performance obtained using policies previously developed in the literature.

Introduction

In distributed learning, a network of agents—such as sensors or autonomous robots—collaborates to solve a global optimization problem without the need for a central coordinator. A widely adopted framework for this is Adapt-then-Combine (ATC) diffusion. In this model, agents first update their local estimates based on private data and then refine these estimates by aggregating information from their immediate neighbors using weighted averages.

The effectiveness of ATC diffusion hinges on the choice of combination weights. While static weights (e.g., uniform averaging) are computationally simple, they fail to account for varying data quality across the network. Existing adaptive weighting strategies primarily target "steady-state" performance—the long-term accuracy after the system has converged. However, these strategies often suffer from sluggish "transient" performance, meaning they take longer to reach that steady state. This research introduces a Gramian-based adaptive policy designed to bridge this gap, offering rapid initial learning without sacrificing long-term precision.

Methodology

The authors frame the selection of combination weights as a constrained optimization problem, aiming to minimize the Square Deviation (SD)—the distance between an agent's estimate and the true optimal value—at every time step.

The Gramian Matrix ($Q$)

The optimal weights are derived from the correlation between the estimation errors of neighboring nodes. To capture these relationships, the authors utilize a Gramian matrix (a matrix of inner products of error vectors). Since the "true" optimal value is unknown in real-time, the error statistics are estimated on the fly using an exponential moving average based on the differences between successive local estimates.

Decentralization and Simplification

To ensure the approach is scalable for large networks, the global optimization problem is decoupled into $N$ independent sub-problems, allowing each node to compute its weights locally. Furthermore, a Simplified Gramian-Based Policy is proposed. By focusing only on the diagonal elements of the Gramian matrix, this version significantly reduces computational overhead while maintaining most of the performance gains of the full approach.

Experimental Evaluation

The proposed algorithms were tested using a decentralized logistic regression simulation on a strongly connected network of 20 nodes. The nodes processed streaming synthetic data with varying noise levels to simulate heterogeneous data quality.

Comparison of Mean Square Deviation (MSD) over iterations for various combination policies.

As shown in the figure above, the Gramian-based policies (both full and simplified) demonstrate a clear advantage. They reach lower Mean Square Deviation (MSD) levels significantly faster than established rules such as Metropolis, Hastings, or Uniform averaging. Notably, the proposed method eventually matches the performance of the Relative-Variance rule—the theoretical "gold standard" for steady-state accuracy—but achieves this state much earlier in the learning process.

Key Insights and Discussion

  • Optimizing the Learning Curve: By minimizing error at each step rather than just at infinity, the Gramian-based approach naturally optimizes both transient and steady-state performance.
  • Information Flow Control: The adaptive weights function as a dynamic flow control mechanism. During the transient phase, the network can effectively ignore noisy neighbors, gradually increasing trust as estimates become more refined.
  • Theoretical Convergence: A key theoretical result confirms that as the system reaches steady state, the Gramian-based weights converge to the optimal Relative-Variance rule.

Limitations and Future Work

While promising, the current analysis assumes "small step-sizes," which is standard for diffusion learning but may not apply to more aggressive learning rates. Additionally, the current formulation does not strictly enforce non-negativity of weights, which might be required in specific physical network applications. Future research could also investigate how these adaptive policies interact with communication-efficient techniques like gradient sparsification or quantization.

Summary updated

Abstract

This paper presents an adaptive combination strategy for distributed learning over diffusion networks. Since learning relies on the collaborative processing of the stochastic information at the dispersed agents, the overall performance can be improved by designing combination policies that adjust the weights according to the quality of the data. Such policies are important because they would add a new degree of freedom and endow multi-agent systems with the ability to control the flow of information over their edges for enhanced performance. Most adaptive and static policies available in the literature optimize certain performance metrics related to steady-state behavior, to the detriment of transient behavior. In contrast, we develop an adaptive combination rule that aims at optimizing the transient learning performance, while maintaining the enhanced steady-state performance obtained using policies previously developed in the literature.
BibTeX
@inproceedings{erginbas2020gramian,
  author = {Y. Efe Erginbas and Stefan Vlaski and Ali H. Sayed},
  title = {{Gramian-Based Adaptive Combination Policies for Diffusion Learning over Networks}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2020},
  doi = {10.1109/icassp39728.2021.9414449},
}
Figure