State-of-the-art neural algorithmic reasoners make use of message passing in
graph neural networks (GNNs). But typical GNNs blur the distinction between the
definition and invocation of the message function, forcing a node to send
messages to its neighbours at every layer, synchronously. When applying GNNs to
learn to execute dynamic programming algorithms, however, on most steps only a
handful of the nodes would have meaningful updates to send. One, hence, runs
the risk of inefficiencies by sending too much irrelevant data across the graph
-- with many intermediate GNN steps having to learn identity functions. In this
work, we explicitly separate the concepts of node state update and message
function invocation. With this separation, we obtain a mathematical formulation
that allows us to reason about asynchronous computation in both algorithms and
neural networks.

本文中，我们分离了节点状态更新和消息函数调用的概念，并得到了一个数学公式，以此来推导算法和神经网络中异步计算的过程。

具同调的异步算法对准

Asynchronous Algorithmic Alignment with Cocycles

Vertical federated learning (VFL) is an effective paradigm of training the
emerging cross-organizational (e.g., different corporations, companies and
organizations) collaborative learning with privacy preserving. Stochastic
gradient descent (SGD) methods are the popular choices for training VFL models
because of the low per-iteration computation. However, existing SGD-based VFL
algorithms are communication-expensive due to a large number of communication
rounds. Meanwhile, most existing VFL algorithms use synchronous computation
which seriously hamper the computation resource utilization in real-world
applications. To address the challenges of communication and computation
resource utilization, we propose an asynchronous stochastic quasi-Newton
(AsySQN) framework for VFL, under which three algorithms, i.e. AsySQN-SGD,
-SVRG and -SAGA, are proposed. The proposed AsySQN-type algorithms making
descent steps scaled by approximate (without calculating the inverse Hessian
matrix explicitly) Hessian information convergence much faster than SGD-based
methods in practice and thus can dramatically reduce the number of
communication rounds. Moreover, the adopted asynchronous computation can make
better use of the computation resource. We theoretically prove the convergence
rates of our proposed algorithms for strongly convex problems. Extensive
numerical experiments on real-word datasets demonstrate the lower communication
costs and better computation resource utilization of our algorithms compared
with state-of-the-art VFL algorithms.

本文提出了一种异步的基于拟牛顿算法的竖直联邦学习框架 (AsySQN)，并在此基础上提出了 AsySQN-SGD、AsySQN-SVRG 和 AsySQN-SAGA 三个算法，通过在实践中收敛比 SGD 更快地 Hessian 所产生的形式来缩小下降步长，从而大大减少通信轮次，并可以更好地利用计算资源，同时理论上证明了算法对于强凸问题的收敛速度，实验结果表明我们提出的算法在真实数据集上比现有的算法具有更低的通信成本和更好的计算资源利用率。

AsySQN: 更快的垂直联邦学习算法，更好的计算资源利用

AsySQN: Faster Vertical Federated Learning Algorithms with Better  Computation Resource Utilization

Asynchronous computation and gradient compression have emerged as two key
techniques for achieving scalability in distributed optimization for
large-scale machine learning. This paper presents a unified analysis framework
for distributed gradient methods operating with staled and compressed
gradients. Non-asymptotic bounds on convergence rates and information exchange
are derived for several optimization algorithms. These bounds give explicit
expressions for step-sizes and characterize how the amount of asynchrony and
the compression accuracy affect iteration and communication complexity
guarantees. Numerical results highlight convergence properties of different
gradient compression algorithms and confirm that fast convergence under limited
information exchange is indeed possible.

该论文提出了一种针对大规模机器学习的分布式梯度方法的统一分析框架，通过非渐进界限来推导了几种优化算法的收敛速率和信息交换，并得到了步长的显式表达式，表征了异步度和压缩精度如何影响迭代和通信复杂性保证，数值结果证实了限制信息交换下不同梯度压缩算法的收敛性能，以及快速收敛确实是可能的。