Gradient Flows and Accelerated Proximal Splitting Methods
Gradient Flows and Accelerated Proximal Splitting Methods
复制标题
梯度流和加速近端分裂方法
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
R. Vidal
中科院分区：
文献类型：
--
作者：
G. França;Daniel P. Robinson;R. Vidal
近端算法非常适合于非光滑和有约束的大规模优化问题，因此适合于许多科学领域的应用。目前已知的基于不动点迭代的近端算法基本上有四种：向前向后分裂、向前向后向前或Tseng分裂、Douglas-Rachford和Davis-Yin三算子分裂。此外，乘法器的交替方向法（ADMM）也与之密切相关。在本文中，我们证明了所有这些算法都可以导出为单个微分方程的不同离散化，即简单的梯度流。这是通过微分方程的分裂方法实现的。此外，对一个特定的二阶微分方程采用类似的离散化方案，我们称之为加速梯度流，导致每个各自的近端算法的加速变体；我们同时考虑两种类型的加速度，尽管其他选择也是可能的。例如，我们提出了Davis-Yin和Tseng分裂的加速变体，以及ADMM的加速扩展。有趣的是，我们发现ADMM及其加速变体对应于再平衡分裂，这是一种最新的技术，旨在保持潜在微分方程的稳定状态。在适当的假设下，我们证明了所有导出的算法都是有效的一阶积分器。我们的研究结果加强了优化与连续动力系统之间的联系，为加速算法提供了统一的视角，并提供了新的加速算法。
Proximal algorithms are well-suited for nonsmooth and constrained large-scale optimization problems and therefore suitable for applications in many areas of science. There are essentially four proximal algorithms based on fixed-point iterations currently known: forward-backward splitting, forward-backward-forward or Tseng splitting, Douglas-Rachford, and the Davis-Yin three operator splitting. In addition, the alternating direction method of multipliers (ADMM) is also closely related. In this paper we show that all of these algorithms can be derived as different discretizations of a single differential equation, namely the simple gradient flow. This is achieved through splitting methods for differential equations. Moreover, employing similar discretization schemes to a particular second-order differential equation, which we refer to as the accelerated gradient flow, results in accelerated variants of each respective proximal algorithm; we simultaneously consider two types of acceleration, although other choices are also possible. For instance, we propose accelerated variants of Davis-Yin and Tseng splitting, as well as accelerated extensions of ADMM. Interestingly, we show that ADMM and its accelerated variants correspond to rebalanced splittings, which is a recent technique designed to preserve steady states of the underlying differential equation. We show that all derived algorithms are valid first-order integrators under suitable assumptions. Our results strengthen the connections between optimization and continuous dynamical systems, offer a unified perspective on accelerated algorithms, and provide new accelerated algorithms.
DOI：
10.1088/1742-5468/abcaee
发表时间：
2019-03
期刊：
Journal of Statistical Mechanics: Theory and Experiment
影响因子：
--
作者：
G. Francca;Jeremias Sulam;Daniel P. Robinson;R. Vidal
通讯作者：
G. Francca;Jeremias Sulam;Daniel P. Robinson;R. Vidal