An Incremental Gradient Method for Large-scale Distributed Nonlinearly Constrained Optimization
An Incremental Gradient Method for Large-scale Distributed Nonlinearly Constrained Optimization
复制标题
DOI：
10.23919/acc50511.2021.9483035
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Harshal D. Kaushik;Farzad Yousefian
中科院分区：
文献类型：
--
作者：
Harshal D. Kaushik;Farzad Yousefian
从传感器网络和机器学习的应用所产生的动机，我们考虑的问题，最小化的不可微凸函数的每个组件功能与代理和一个难以投影的约束集的有限和。在众所周知的途径，以解决有限和问题是一类增量梯度（IG）的方法，其中一个单一的组件功能选择在每次迭代在一个循环或随机的方式。当问题有约束时，现有的IG方法（包括投影IG，邻近IAG和佐贺）需要在每次迭代时投影到可行集上。因此，当问题包括：（1）非线性约束，或（2）大量的线性约束时，这些方案的性能受到昂贵的预测的影响。本文的重点在于解决这两个挑战。我们开发了一种算法称为平均迭代正则化增量梯度（aIR-IG），不涉及任何难以预测的计算。在温和的假设下，我们得到的次优性和不可行性度量的非渐近收敛速度。数值上，我们表明，该方案优于标准的投影IG方法的分布式软利润支持向量机问题。
Motivated by applications arising from sensor networks and machine learning, we consider the problem of minimizing a finite sum of nondifferentiable convex functions where each component function is associated with an agent and a hard-to-project constraint set. Among well-known avenues to address finite sum problems is the class of incremental gradient (IG) methods where a single component function is selected at each iteration in a cyclic or randomized manner. When the problem is constrained, the existing IG schemes (including projected IG, proximal IAG, and SAGA) require a projection step onto the feasible set at each iteration. Consequently, the performance of these schemes is afflicted with costly projections when the problem includes: (1) nonlinear constraints, or (2) a large number of linear constraints. Our focus in this paper lies in addressing both of these challenges. We develop an algorithm called averaged iteratively regularized incremental gradient (aIR-IG) that does not involve any hard-to-project computation. Under mild assumptions, we derive non-asymptotic rates of convergence for both suboptimality and infeasibility metrics. Numerically, we show that the proposed scheme outperforms the standard projected IG methods on distributed soft-margin support vector machine problems.