EUVIMEDEUVIMED entdecken
Crossref

On Graphs with Finite-Time Consensus and Their Use in Gradient Tracking

Edward Duc Hien Nguyen, Xin Jiang, Bicheng Ying, César A. Uribe

SIAM Journal on Optimization · 30.06.2025 · 35 (2) · 872-898

DOI: 10.1137/24m1661455 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Optimization, online erschienen am 28.04.2025. Verfasst von Edward Duc Hien Nguyen und 3 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 31 Literaturangaben. Gefördert von: NSF, Google Research Award.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

This paper studies sequences of graphs satisfying the finite-time consensus property (i.e., iterating through such a finite sequence is equivalent to performing global or exact averaging) and their use in the decentralized optimization algorithm Gradient Tracking. For each of the studied graph sequences, we provide an explicit weight matrix representation and prove their finite-time consensus property. Moreover, we incorporate such topology sequences into Gradient Tracking and present a new algorithmic scheme called Gradient Tracking for Finite-Time Consensus Topologies (GT-FT). We analyze the new scheme for nonconvex problems with stochastic gradient estimates. Our analysis shows that the convergence rate of GT-FT does not depend on the heterogeneity of the agents’ functions or the connectivity of any individual graph in the topology sequence. Furthermore, owing to the sparsity of the graphs, GT-FT requires lower communication costs than Gradient Tracking using the static counterpart of the topology sequence.

Förderung

  • NSF
  • Google Research Award

Zitieren

APA

Nguyen, E. D. H., Jiang, X., Ying, B., & Uribe, C. A. (2025). On Graphs with Finite-Time Consensus and Their Use in Gradient Tracking. SIAM Journal on Optimization, 35(2), 872-898. https://doi.org/10.1137/24m1661455

Vancouver

Nguyen EDH, Jiang X, Ying B, Uribe CA. On Graphs with Finite-Time Consensus and Their Use in Gradient Tracking. SIAM Journal on Optimization. 2025;35(2):872-898. doi:10.1137/24m1661455

BibTeX
@article{Nguyen2025,
  author = {Nguyen, Edward Duc Hien and Jiang, Xin and Ying, Bicheng and Uribe, César A.},
  title = {On Graphs with Finite-Time Consensus and Their Use in Gradient Tracking},
  journal = {SIAM Journal on Optimization},
  year = {2025},
  volume = {35},
  number = {2},
  pages = {872--898},
  doi = {10.1137/24m1661455}
}
Kostenlos starten →