Technical Summary: Row-Stochastic Matrices Can Provably Outperform Doubly Stochastic Matrices in Decentralized Learning

Problem Statement

Decentralized learning is a central paradigm for large-scale optimization, yet most existing theoretical analyses assume uniform node weights and rely on symmetric, doubly stochastic mixing matrices. In practical systems, however, nodes often possess heterogeneous data volumes and distributions, necessitating a weighted global loss function:
$$\min_{\theta \in \mathbb{R}^d} F(\theta) = \frac{1}{n} \sum_{i=1}^n \lambda_i F_i(\theta)$$
where $\lambda = [\lambda_1, \dots, \lambda_n]^\top$ represents prescribed heterogeneous weights. Two natural strategies exist to solve this problem:

1. Strategy I (Weighted Loss): Absorb the weights $\lambda_i$ into the local losses (replacing $F_i$ with $\lambda_i F_i$) and retain a standard doubly stochastic mixing matrix.
2. Strategy II (Weighted Mixing): Keep the original local losses and incorporate $\lambda$ into a row-stochastic mixing matrix whose stationary distribution equals $\lambda/n$.

While prior work establishes that both strategies converge to the stationary points of the same weighted optimization problem, fundamental questions remain regarding the tightness of convergence rates under heterogeneous weights and the structural factors differentiating their behaviors. Specifically, it is unclear whether standard Euclidean analysis provides tight bounds and whether performance differences arise solely from spectral gaps or other geometric factors.

Methodology

The authors develop a new analytical framework based on a weighted Hilbert space $L_2(\lambda; \mathbb{R}^d)$, endowed with the inner product $\langle X, Y \rangle_{\lambda, d} = \sum_{i=1}^n \lambda_i \langle x_i, y_i \rangle$. This geometry naturally accommodates the error recursions induced by heterogeneous node weights.

Key methodological components include:

• Matrix Construction: A decentralized row-stochastic matrix $W$ is constructed using a modified Metropolis–Hastings rule such that its stationary distribution matches $\lambda/n$. This matrix satisfies the detailed balance condition $\lambda_i W_{ij} = \lambda_j W_{ji}$.
• Self-Adjointness Analysis: Within the $L_2(\lambda; \mathbb{R}^d)$ space, the $\lambda$-induced row-stochastic matrix $W$ becomes self-adjoint, admitting an orthogonal eigen-decomposition. In contrast, the doubly stochastic matrix $W^{ds}$ used in Strategy I is generally non-self-adjoint in this weighted space.
• Convergence Analysis: The authors derive convergence rates for decentralized stochastic gradient tracking (GT) under both strategies. They analyze the consensus error and show that the non-self-adjoint nature of $W^{ds}$ in the weighted space introduces additional penalty terms (specifically involving $\kappa_\lambda^2$ and $\lambda_{\max}^2$) that amplify consensus error and restrict the admissible step-size range.
• Topology Design: Using Rayleigh-quotient and Loewner-order eigenvalue comparisons, the paper derives sufficient conditions under which Strategy II converges faster than Strategy I, even if Strategy II's mixing matrix has a smaller spectral gap. This leads to a design guideline where node degrees should scale proportionally with their associated weights.

Key Contributions

The paper makes three primary contributions:

1. Tighter Convergence Bounds via Weighted Hilbert Space: The authors demonstrate that standard Euclidean analysis yields strictly looser bounds for decentralized learning with heterogeneous weights. By utilizing the $L_2(\lambda; \mathbb{R}^d)$ framework, they derive tight convergence rates that accurately reflect the dependence on heterogeneous weights.
2. Structural Explanation of Performance Gaps: The analysis reveals that the performance difference between the two strategies is not determined solely by spectral gaps. Crucially, the lack of self-adjointness in the doubly stochastic matrix (under the weighted geometry) generates multiplicative penalty terms that increase consensus error and tighten step-size constraints. Consequently, Strategy II (row-stochastic) can converge faster than Strategy I (doubly stochastic) even when its spectral gap is smaller.
3. Topology Design Guidelines: The paper provides sufficient spectral and topological conditions for Strategy II to outperform Strategy I. It proposes a practical algorithm (Algorithm 2) to construct connected graphs where node degrees are proportional to the prescribed weights, thereby maximizing the spectral gap in heterogeneous settings.

Experimental Results

The theoretical findings are validated through experiments on synthetic least-squares tasks and deep learning (ResNet-18 on CIFAR-10).

• Least-Squares: Strategy II consistently converges faster than Strategy I and reaches a tighter neighborhood of the optimum, resulting in a smaller steady-state gradient norm. The performance gap widens with increased weight heterogeneity.
• CIFAR-10: Strategy II achieves lower interval loss and higher test accuracy across various topologies (Ring, Grid, Exponential, Random Geometric, and tailored graphs). Notably, Strategy II remains superior even when the doubly stochastic matrix has a larger spectral gap, confirming that convergence is influenced by the self-adjointness structure and resulting constants, not just spectral gaps.
• Tailored Topologies: Graphs constructed via the proposed degree-weight proportionality algorithm (Algorithm 2) demonstrate improved performance, validating the theoretical design guidelines.

Significance and Claims

The paper claims to advance the understanding of decentralized learning with heterogeneous weights by resolving open questions regarding convergence tightness and the fundamental differences between weighting strategies.

• Revisiting Standard Assumptions: The work challenges the assumption that doubly stochastic mixing is optimal or equivalent to row-stochastic mixing in heterogeneous settings. It shows that the standard Euclidean framework fails to capture the geometric structure of weighted decentralized learning, leading to loose bounds.
• Beyond Spectral Gaps: A central claim is that convergence rates are not dictated solely by spectral gaps. The self-adjointness of the mixing matrix in the appropriate weighted space is a critical factor that can allow a strategy with a smaller spectral gap to outperform one with a larger gap.
• Practical Implications: The paper provides concrete, provable guidelines for topology design, suggesting that in systems with heterogeneous node importance (weights), the network connectivity (degree) should be matched to these weights to optimize convergence.

The authors note that their results are specific to the single-loop gradient tracking framework considered and do not constitute universal minimax lower bounds for all decentralized algorithms. Future work is suggested to extend these analyses to directed graphs and to develop lower-bound characterizations for broader algorithmic classes.