This work introduces DADAO: the first decentralized, accelerated,
asynchronous, primal, first-order algorithm to minimize a sum of $L$-smooth and
$\mu$-strongly convex functions distributed over a given network of size $n$.
Our key insight is based on modeling the local gradient updates and gossip
communication procedures with separate independent Poisson Point Processes.
This allows us to decouple the computation and communication steps, which can
be run in parallel, while making the whole approach completely asynchronous,
leading to communication acceleration compared to synchronous approaches. Our
new method employs primal gradients and does not use a multi-consensus inner
loop nor other ad-hoc mechanisms such as Error Feedback, Gradient Tracking, or
a Proximal operator. By relating the inverse of the smallest positive
eigenvalue of the Laplacian matrix $\chi_1$ and the maximal resistance
$\chi_2\leq \chi_1$ of the graph to a sufficient minimal communication rate
between the nodes of the network, we show that our algorithm requires
$\mathcal{O}(n\sqrt{\frac{L}{\mu}}\log(\frac{1}{\epsilon}))$ local gradients
and only
$\mathcal{O}(n\sqrt{\chi_1\chi_2}\sqrt{\frac{L}{\mu}}\log(\frac{1}{\epsilon}))$
communications to reach a precision $\epsilon$, up to logarithmic terms. Thus,
we simultaneously obtain an accelerated rate for both computations and
communications, leading to an improvement over state-of-the-art works, our
simulations further validating the strength of our relatively unconstrained
method. We also propose a SDP relaxation to find the optimal gossip rate of
each edge minimizing the total number of communications for a given graph,
resulting in faster convergence compared to standard approaches relying on
uniform communication weights. Our source code is released on a public
repository.

DADAO 是第一个分布式异步算法，可通过分别使用独立的泊松点过程模拟本地梯度更新和闲话通信过程进行并行计算和加速通信，而不需要使用内部循环或其他特定机制，例如误差反馈，梯度跟踪或近端算子。

DADAO: 分离的加速去中心化异步优化

DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization

In this paper we propose the first non-parametric Bayesian model using
Gaussian Processes to make inference on Poisson Point Processes without
resorting to gridding the domain or to introducing latent thinning points.
Unlike competing models that scale cubically and have a squared memory
requirement in the number of data points, our model has a linear complexity and
memory requirement. We propose an MCMC sampler and show that our model is
faster, more accurate and generates less correlated samples than competing
models on both synthetic and real-life data. Finally, we show that our model
easily handles data sizes not considered thus far by alternate approaches.

本文提出了第一个使用高斯过程的非参数贝叶斯模型，在不用网格化域或引入潜在稀化点的情况下对泊松点过程进行推断。我们设计了 MCMC 采样器，并展示了我们的模型在合成数据和实际数据上比竞争模型更快，更准确且生成的样本更少相关性。最后，我们证明我们的模型容易处理先前未考虑的数据规模。