EUVIMEDEUVIMED entdecken
Crossref

Provably Accelerated Decentralized Gradient Methods Over Unbalanced Directed Graphs

Zhuoqing Song, Lei Shi, Shi Pu, Ming Yan

SIAM Journal on Optimization · 31.03.2024 · 34 (1) · 1131-1156

DOI: 10.1137/22m148570x ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Optimization, online erschienen am 22.03.2024. Verfasst von Zhuoqing Song und 3 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 68 Literaturangaben. Gefördert von: Shanghai Science and Technology Development Foundation, National Natural Science Foundation of China, Guangdong Talent Program.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We consider the decentralized optimization problem, where a network of [Formula: see text] agents aims to collaboratively minimize the average of their individual smooth and convex objective functions through peer-to-peer communication in a directed graph. To tackle this problem, we propose two accelerated gradient tracking methods, namely Accelerated Push-DIGing (APD) and APD-SC, for non-strongly convex and strongly convex objective functions, respectively. We show that APD and APD-SC converge at the rates [Formula: see text] and [Formula: see text], respectively, up to constant factors depending only on the mixing matrix. APD and APD-SC are the first decentralized methods over unbalanced directed graphs that achieve the same provable acceleration as centralized methods. Numerical experiments demonstrate the effectiveness of both methods.

Förderung

  • Shanghai Science and Technology Development Foundation
  • National Natural Science Foundation of China
  • Guangdong Talent Program
  • Shenzhen Research Institute of Big Data
  • Shenzhen Science and Technology Innovation Commission
  • National Science Foundation

Zitieren

APA

Song, Z., Shi, L., Pu, S., & Yan, M. (2024). Provably Accelerated Decentralized Gradient Methods Over Unbalanced Directed Graphs. SIAM Journal on Optimization, 34(1), 1131-1156. https://doi.org/10.1137/22m148570x

Vancouver

Song Z, Shi L, Pu S, Yan M. Provably Accelerated Decentralized Gradient Methods Over Unbalanced Directed Graphs. SIAM Journal on Optimization. 2024;34(1):1131-1156. doi:10.1137/22m148570x

BibTeX
@article{Song2024,
  author = {Song, Zhuoqing and Shi, Lei and Pu, Shi and Yan, Ming},
  title = {Provably Accelerated Decentralized Gradient Methods Over Unbalanced Directed Graphs},
  journal = {SIAM Journal on Optimization},
  year = {2024},
  volume = {34},
  number = {1},
  pages = {1131--1156},
  doi = {10.1137/22m148570x}
}
Kostenlos starten →