Asynchronous Optimization Over Graphs: Linear Convergence Under Error Bound Conditions
Asynchronous Optimization Over Graphs: Linear Convergence Under Error Bound Conditions
复制标题
DOI：
10.1109/tac.2020.3033490
复制
发表时间：
2020-10
影响因子：
6.8
通讯作者：
Loris Cannelli;F. Facchinei;G. Scutari;V. Kungurtsev
中科院分区：
文献类型：
--
作者：
Loris Cannelli;F. Facchinei;G. Scutari;V. Kungurtsev
我们考虑具有部分可分离目标函数的凸和非凸约束优化：代理最小化局部目标函数的总和，每个目标函数仅由相关代理知道，并且取决于该代理和其他一些代理的变量。这种分区设置出现在一些具有实际意义的应用中。据我们所知，我们提出了第一个针对此类问题提供速率保证的分布式异步算法。当目标函数为非凸时，该算法可证明以次线性速率收敛到稳态解，而线性速率是在著名的 Luo-Tseng 误差界限条件（比强凸性更宽松）下实现的。矩阵补全和 LASSO 问题的数值结果表明了我们方法的有效性。
We consider convex and nonconvex constrained optimization with a partially separable objective function: Agents minimize the sum of local objective functions, each of which is known only by the associated agent and depends on the variables of that agent and those of a few others. This partitioned setting arises in several applications of practical interest. We propose what is, to the best of our knowledge, the first distributed, asynchronous algorithm with rate guarantees for this class of problems. When the objective function is nonconvex, the algorithm provably converges to a stationary solution at a sublinear rate whereas linear rate is achieved under the renowned Luo-Tseng error bound condition (which is less stringent than strong convexity). Numerical results on matrix completion and LASSO problems show the effectiveness of our method.