论文标题
一种通用自适应重新开始方案，并应用于鞍点算法的应用
A generic adaptive restart scheme with applications to saddle point algorithms
论文作者
论文摘要
我们为凸优化提供了一个简单且通用的自适应重新开始方案，该方案能够实现与需要了解特定问题常数知识的最佳重新启动方案匹配（最多达到恒定的乘法因子）。只要有足够的基于距离的电位函数，该方案就会触发。该潜在函数始终可计算。 我们应用该方案以获取第一个适应性重新启动算法，用于鞍点算法，包括原始偶发杂种梯度（PDHG）和外部算法。该方法改善了双线性游戏中PDHG最差的范围，以及有关二次分配问题和矩阵游戏的数值实验，为获得高准确解决方案提供了巨大的改进。此外，对于加速的梯度下降（AGD），该方案在需要高精度时获得了最佳的最佳重新启动时期的最差案例结合。实际上，该计划与O'Donoghue and Candes（2015）的启发式竞争力竞争。
We provide a simple and generic adaptive restart scheme for convex optimization that is able to achieve worst-case bounds matching (up to constant multiplicative factors) optimal restart schemes that require knowledge of problem specific constants. The scheme triggers restarts whenever there is sufficient reduction of a distance-based potential function. This potential function is always computable. We apply the scheme to obtain the first adaptive restart algorithm for saddle-point algorithms including primal-dual hybrid gradient (PDHG) and extragradient. The method improves the worst-case bounds of PDHG on bilinear games, and numerical experiments on quadratic assignment problems and matrix games demonstrate dramatic improvements for obtaining high-accuracy solutions. Additionally, for accelerated gradient descent (AGD), this scheme obtains a worst-case bound within 60% of the bound achieved by the (unknown) optimal restart period when high accuracy is desired. In practice, the scheme is competitive with the heuristic of O'Donoghue and Candes (2015).
