We introduce a framework for designing primal methods under the decentralized
optimization setting where local functions are smooth and strongly convex. Our
approach consists of approximately solving a sequence of sub-problems induced
by the accelerated augmented Lagrangian method, thereby providing a systematic
way for deriving several well-known decentralized algorithms including EXTRA
arXiv:1404.6264 and SSDA arXiv:1702.08704. When coupled with accelerated
gradient descent, our framework yields a novel primal algorithm whose
convergence rate is optimal and matched by recently derived lower bounds. We
provide experimental results that demonstrate the effectiveness of the proposed
algorithm on highly ill-conditioned problems.

提出了一个在分散优化设置下设计原始方法的框架，该框架适用于局部函数光滑且强凸。通过近似解决由加速增广拉格朗日方法引起的一系列子问题，从而提供了一种演导出几个著名的分散算法的系统方法。当与加速梯度下降相结合时，我们的框架会产生一种新的原始算法，其收敛速度是最优的，并且与最近确定的下限相匹配。我们提供实验结果，证明了拟议算法在高度病态问题上的有效性。

IDEAL：非精确分散加速增广拉格朗日算法

IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method

In this paper, we study the problem of distributed multi-agent optimization
over a network, where each agent possesses a local cost function that is smooth
and strongly convex. The global objective is to find a common solution that
minimizes the average of all cost functions. Assuming agents only have access
to unbiased estimates of the gradients of their local cost functions, we
consider a distributed stochastic gradient tracking method (DSGT) and a
gossip-like stochastic gradient tracking method (GSGT). We show that, in
expectation, the iterates generated by each agent are attracted to a
neighborhood of the optimal solution, where they accumulate exponentially fast
(under a constant stepsize choice). Under DSGT, the limiting (expected) error
bounds on the distance of the iterates from the optimal solution decrease with
the network size $n$, which is a comparable performance to a centralized
stochastic gradient algorithm. Moreover, we show that when the network is
well-connected, GSGT incurs lower communication cost than DSGT while
maintaining a similar computational cost. Numerical example further
demonstrates the effectiveness of the proposed methods.

本文研究了分布式多智能体优化问题，其中每个智能体拥有一个光滑和强凸的本地代价函数。在仅具有本地代价函数梯度的无偏估计时，我们提出了一种分布式随机梯度跟踪方法（DSGT）和一种类似于 Gossip 的随机梯度跟踪方法（GSGT），并展示了这些方法对大规模网络的可比性能和通信成本的差异。

分布式随机梯度追踪方法

Distributed Stochastic Gradient Tracking Methods

The problem of minimizing an objective that can be written as the sum of a
set of $n$ smooth and strongly convex functions is considered. The Incremental
Quasi-Newton (IQN) method proposed here belongs to the family of stochastic and
incremental methods that have a cost per iteration independent of $n$. IQN
iterations are a stochastic version of BFGS iterations that use memory to
reduce the variance of stochastic approximations. The convergence properties of
IQN bridge a gap between deterministic and stochastic quasi-Newton methods.
Deterministic quasi-Newton methods exploit the possibility of approximating the
Newton step using objective gradient differences. They are appealing because
they have a smaller computational cost per iteration relative to Newton's
method and achieve a superlinear convergence rate under customary regularity
assumptions. Stochastic quasi-Newton methods utilize stochastic gradient
differences in lieu of actual gradient differences. This makes their
computational cost per iteration independent of the number of objective
functions $n$. However, existing stochastic quasi-Newton methods have sublinear
or linear convergence at best. IQN is the first stochastic quasi-Newton method
proven to converge superlinearly in a local neighborhood of the optimal
solution. IQN differs from state-of-the-art incremental quasi-Newton methods in
three aspects: (i) The use of aggregated information of variables, gradients,
and quasi-Newton Hessian approximation matrices to reduce the noise of gradient
and Hessian approximations. (ii) The approximation of each individual function
by its Taylor's expansion in which the linear and quadratic terms are evaluated
with respect to the same iterate. (iii) The use of a cyclic scheme to update
the functions in lieu of a random selection routine. We use these fundamental
properties of IQN to establish its local superlinear convergence rate.

本文提出一种增量式拟牛顿方法来最小化一个可用 n 个平滑和强凸函数表示的目标函数，该方法是一种随机和增量方法，每次迭代的成本与 n 无关，其收敛特性介于确定性和随机拟牛顿方法之间，利用聚合信息和泰勒展开近似函数、周期性更新目标函数等特性实现了在最优解局部范围内的局部超线性收敛率。