论文标题
具有二次上限的凸功能的最佳一阶方法
Optimal first-order methods for convex functions with a quadratic upper bound
论文作者
论文摘要
我们分析了在函数类别上的一阶优化方法的最坏情况收敛的保证，从而扩展了光滑和凸功能的功能类别。该类包含凸功能，该函数允许一个简单的二次上限。它的研究是由于其在轻微扰动下的稳定性所激发的。我们对一阶方法进行了彻底的分析，包括多种算法的最差案例收敛保证，并证明其中一些可以实现整个类别的最佳最差保证。我们通过使用绩效估计问题对最差案例保证的数值验证来支持我们的分析。可以从该分析中得出一些观察，特别是关于重球方法的最优性（分别和适应性）（分别进行搜索的分别重力）。最后，我们展示了如何利用分析以获得更复杂类别的融合保证。总体而言，这项研究带来了对标准一阶方法具有最差保证的功能类别的见解。
We analyze worst-case convergence guarantees of first-order optimization methods over a function class extending that of smooth and convex functions. This class contains convex functions that admit a simple quadratic upper bound. Its study is motivated by its stability under minor perturbations. We provide a thorough analysis of first-order methods, including worst-case convergence guarantees for several algorithms, and demonstrate that some of them achieve the optimal worst-case guarantee over the class. We support our analysis by numerical validation of worst-case guarantees using performance estimation problems. A few observations can be drawn from this analysis, particularly regarding the optimality (resp. and adaptivity) of the heavy-ball method (resp. heavy-ball with line-search). Finally, we show how our analysis can be leveraged to obtain convergence guarantees over more complex classes of functions. Overall, this study brings insights on the choice of function classes over which standard first-order methods have working worst-case guarantees.
