EUVIMEDEUVIMED entdecken
Crossref

Understanding the Influence of Digraphs on Decentralized Optimization: Effective Metrics, Lower Bound, and Optimal Algorithm

Liyuan Liang, Xinmeng Huang, Ran Xin, Kun Yuan

SIAM Journal on Optimization · 30.09.2025 · 35 (3) · 1570-1600

DOI: 10.1137/24m1657341 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Optimization, online erschienen am 15.07.2025. Verfasst von Liyuan Liang und 3 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 45 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

This paper investigates the influence of directed networks on decentralized stochastic nonconvex optimization associated with column-stochastic mixing matrices. Surprisingly, we find that the canonical spectral gap, a widely used metric in undirected networks, is insufficient to characterize the impact of directed topology on decentralized algorithms. To overcome this limitation, we introduce a novel metric termed equilibrium skewness. This metric, together with the spectral gap, accurately and comprehensively captures the influence of column-stochastic mixing matrices on decentralized stochastic algorithms. With these two metrics, we clarify, for the first time, how the directed network topology influences the performance of prevalent algorithms such as Push-Sum and Push-DIGing. Furthermore, we establish the first lower bound of the convergence rate for decentralized stochastic nonconvex algorithms over directed networks. Since existing algorithms cannot match our lower bound, we further propose the MG-Push-DIGing algorithm, which integrates Push-DIGing with a multiround gossip technique. MG-Push-DIGing attains our lower bound up to logarithmic factors, demonstrating its near-optimal performance and the tightness of the lower bound. Numerical experiments verify our theoretical results.

Zitieren

APA

Liang, L., Huang, X., Xin, R., & Yuan, K. (2025). Understanding the Influence of Digraphs on Decentralized Optimization: Effective Metrics, Lower Bound, and Optimal Algorithm. SIAM Journal on Optimization, 35(3), 1570-1600. https://doi.org/10.1137/24m1657341

Vancouver

Liang L, Huang X, Xin R, Yuan K. Understanding the Influence of Digraphs on Decentralized Optimization: Effective Metrics, Lower Bound, and Optimal Algorithm. SIAM Journal on Optimization. 2025;35(3):1570-1600. doi:10.1137/24m1657341

BibTeX
@article{Liang2025,
  author = {Liang, Liyuan and Huang, Xinmeng and Xin, Ran and Yuan, Kun},
  title = {Understanding the Influence of Digraphs on Decentralized Optimization: Effective Metrics, Lower Bound, and Optimal Algorithm},
  journal = {SIAM Journal on Optimization},
  year = {2025},
  volume = {35},
  number = {3},
  pages = {1570--1600},
  doi = {10.1137/24m1657341}
}
Infokarte | EUVIMED

Artikeldaten derzeit nicht verfügbar.

Recherche