2025/07/22 by Balázs Gerencsér, Gerencsér, Balázs, Miklós Kornyik +1
Computer Science · #37M25 (Primary) 93D50 #93D05 (Secondary} #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #FOS: Mathematics #G.3 #Multiagent Systems (cs.MA) #Probability (math.PR) #Quantum Computing Algorithms and Architecture #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2507.16601
openalex publication_date 2025/07/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The objective of this work is to establish an upper bound for the almost sure convergence rate for a class of push-sum algorithms. The current work extends the methods and results of the authors on a similar low-complexity bound on push-sum algorithms with some particular synchronous message passing schemes and complements the general approach of Gerencsér and Gerencsér from 2022 providing an exact, but often less accessible description. Furthermore, a parametric analysis is presented on the ``weight'' of the messages, which is found to be convex with an explicit expression for the gradient. This allows the fine-tuning of the algorithm used for improved efficiency. Numerical results confirm the speedup in evaluating the computable bounds without deteriorating their performance, for a graph on 120 vertices the runtime drops by more than 4 orders of magnitude.