标题： 具有同构相关结构的推送求和算法的低复杂度收敛速率界限 显示英文标题

标题： Low complexity convergence rate bounds for push-sum algorithms with homogeneous correlation structure

摘要： 本工作的目标是为一类push-sum算法建立几乎必然收敛速率的上界。 当前的工作扩展了作者在类似低复杂度bound on push-sum算法上的方法和结果，结合了一些特定的同步消息传递方案，并补充了Gerencsér和Gerencsér于2022年提出的通用方法，提供了一个精确但通常较难理解的描述。 此外，对“消息”的“权重”进行了参数分析，发现其是凸的，并给出了梯度的显式表达式。 这使得可以对算法进行微调以提高效率。 数值结果证实了在不降低性能的情况下评估可计算界限的速度提升，对于一个有120个顶点的图，运行时间减少了超过4个数量级。 显示英文摘要

摘要： 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\'er and Gerencs\'er 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.