A Simple Nearly Optimal Restart Scheme For Speeding Up First-Order Methods
A Simple Nearly Optimal Restart Scheme For Speeding Up First-Order Methods
复制标题
DOI：
10.1007/s10208-021-09502-2
复制
发表时间：
2018-03
影响因子：
3
通讯作者：
J. Renegar;Benjamin Grimmer
中科院分区：
文献类型：
--
作者：
J. Renegar;Benjamin Grimmer
我们提出了一个简单的计划重新启动一阶方法的凸优化问题。重新启动仅基于实现目标值的指定减少，对于所有优化问题，指定的量是相同的。与现有的重启方案不同，该方案不试图学习表征优化问题结构的参数值，也不需要任何在实践中不可用的特殊信息（除非选择在方案本身中使用的一阶方法需要特殊信息）。作为直接推论的主要定理，我们表明，当一些著名的一阶方法中采用的计划，所产生的复杂性界限是近最佳的特殊，但相当普遍的类问题。
We present a simple scheme for restarting first-order methods for convex optimization problems. Restarts are made based only on achieving specified decreases in objective values, the specified amounts being the same for all optimization problems. Unlike existing restart schemes, the scheme makes no attempt to learn parameter values characterizing the structure of an optimization problem, nor does it require any special information that would not be available in practice (unless the first-order method chosen to be employed in the scheme itself requires special information). As immediate corollaries to the main theorems, we show that when some well-known first-order methods are employed in the scheme, the resulting complexity bounds are nearly optimal for particular—yet quite general—classes of problems.