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

This paper considers the problem of minimizing an expectation function over a
closed convex set, coupled with a {\color{black} functional or expectation}
constraint on either decision variables or problem parameters. We first present
a new stochastic approximation (SA) type algorithm, namely the cooperative SA
(CSA), to handle problems with the constraint on devision variables. We show
that this algorithm exhibits the optimal ${\cal O}(1/\epsilon^2)$ rate of
convergence, in terms of both optimality gap and constraint violation, when the
objective and constraint functions are generally convex, where $\epsilon$
denotes the optimality gap and infeasibility. Moreover, we show that this rate
of convergence can be improved to ${\cal O}(1/\epsilon)$ if the objective and
constraint functions are strongly convex. We then present a variant of CSA,
namely the cooperative stochastic parameter approximation (CSPA) algorithm, to
deal with the situation when the constraint is defined over problem parameters
and show that it exhibits similar optimal rate of convergence to CSA. It is
worth noting that CSA and CSPA are primal methods which do not require the
iterations on the dual space and/or the estimation on the size of the dual
variables. To the best of our knowledge, this is the first time that such
optimal SA methods for solving functional or expectation constrained stochastic
optimization are presented in the literature.

本文介绍了两种新型随机逼近算法 —— 协作随机逼近算法（CSA）和协作随机参数逼近算法（CSPA），分别用于处理决策变量约束和问题参数约束的期望函数最小化问题，证明了它们实现了最优收敛率以及不需要使用对偶变量迭代。