{"ID":2824132,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.24483","arxiv_id":"2512.24483","title":"Decentralized Optimization over Time-Varying Row-Stochastic Digraphs","abstract":"Decentralized optimization over directed graphs is essential for applications such as robotic swarms, sensor networks, and distributed learning. In many practical scenarios, the underlying network takes the form of a Time-Varying Broadcast Network (TVBN), where only row-stochastic mixing matrices can be constructed due to the unavailability of out-degree information. Achieving exact convergence for decentralized optimization over TVBNs has remained a long-standing open problem, as the limiting distribution of time-varying row-stochastic mixing matrices depends on unpredictable future graph realizations, rendering standard bias-correction techniques infeasible. This paper develops the first decentralized optimization algorithm that achieves exact convergence using only time-varying row-stochastic matrices. We first propose PULM (Pull-with-Memory), a gossip protocol that achieves average consensus with exponential convergence by alternating between row-stochastic mixing and local adjustment steps. Building on PULM, we develop PULM-DGD, which converges to a stationary solution at a rate of $\\mathcal{O}(\\ln(T)/T)$ for smooth nonconvex objectives, where $T$ denotes the communication round. Our results significantly broaden the applicability of decentralized optimization to highly dynamic communication environments.","short_abstract":"Decentralized optimization over directed graphs is essential for applications such as robotic swarms, sensor networks, and distributed learning. In many practical scenarios, the underlying network takes the form of a Time-Varying Broadcast Network (TVBN), where only row-stochastic mixing matrices can be constructed due...","url_abs":"https://arxiv.org/abs/2512.24483","url_pdf":"https://arxiv.org/pdf/2512.24483v3","authors":"[\"Liyuan Liang\",\"Yilong Song\",\"Kun Yuan\"]","published":"2025-12-30T22:08:04Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}