Noise-Robust Distributed Optimization Over Directed Graphs With Row Stochastic Matrices
Abstract
In the presence of information-sharing noise, row-stochastic distributed optimization over directed and unbalanced graphs can suffer not only from noise accumulation in gradient tracking, but also from distortion of the left eigenvector-based gradient scaling used for imbalance compensation. To address these issues, this paper proposes a noise-robust distributed optimization algorithm using only row-stochastic weights, termed Robust Xi-row (R-Xi-row). The optimization update is driven by the increment of an auxiliary cumulative variable to exclude historical tracking noise, while two decaying gains and a normalized scaling gain are used to suppress the effect of noisy eigenvector estimation and asymptotically recover the required gradient scaling almost surely. Under strongly convex and smooth objectives and appropriate decaying gains, we prove almost sure convergence to the optimal solution. For polynomially decaying gains, we further establish a near-𝒪(k−1/3) expected convergence rate. Numerical experiments validate the theoretical results.
Related
- Open Capacity Pooling in Agentic Supply Chains: Coordination-Directed LLM Discovery and Distributed Re-optimization
- Distributed Cross-Layer Optimization for Covert Multi-Hop, Multi-Modal Networks: Exponentially Fast Convergence and Robust Tracking
- Application of Optimal Inexact Second-Order Acceleration to Distributed Stochastic Optimization under Statistical Similarity
- A Note on the NP-Hardness on Quadratic Optimization over Doubly Stochastic Matrices and the Gromov-Wasserstein Problem
- Scalable Distributed Stochastic Optimization via Bidirectional Compression: Beyond Pessimistic Limits
BibTeX
@misc{wang2026noiserobust,
title = {{Noise-Robust Distributed Optimization Over Directed Graphs With Row Stochastic Matrices}},
author = {Yifan Wang and Mufeng Wang and Xianghui Cao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.29481},
eprint = {2609.29481},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29481},
}
RIS
TY - UNPB
TI - Noise-Robust Distributed Optimization Over Directed Graphs With Row Stochastic Matrices
AU - Yifan Wang
AU - Mufeng Wang
AU - Xianghui Cao
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.29481
UR - https://arxiv.org/abs/2609.29481
AB - In the presence of information-sharing noise, row-stochastic distributed optimization over directed and unbalanced graphs can suffer not only from noise accumulation in gradient tracking, but also from distortion of the left eigenvector-based gradient scaling used for imbalance compensation. To address these issues, this paper proposes a noise-robust distributed optimization algorithm using only row-stochastic weights, termed Robust Xi-row (R-Xi-row). The optimization update is driven by the increment of an auxiliary cumulative variable to exclude historical tracking noise, while two decaying gains and a normalized scaling gain are used to suppress the effect of noisy eigenvector estimation and asymptotically recover the required gradient scaling almost surely. Under strongly convex and smooth objectives and appropriate decaying gains, we prove almost sure convergence to the optimal solution. For polynomially decaying gains, we further establish a near-𝒪(k^−1/3) expected convergence rate. Numerical experiments validate the theoretical results.
ER -