An Optimal First Order Method Based on Optimal Quadratic Averaging
An Optimal First Order Method Based on Optimal Quadratic Averaging
复制标题
DOI：
10.1137/16m1072528
复制
发表时间：
2016-04
期刊：
影响因子：
--
通讯作者：
D. Drusvyatskiy;Maryam Fazel;Scott Roy
中科院分区：
文献类型：
--
作者：
D. Drusvyatskiy;Maryam Fazel;Scott Roy
在最近的一篇论文中，Bubeck，Lee和Singh引入了一种新的一阶方法，以最大程度地降低光滑的强烈凸功能。它们的几何下降算法在很大程度上受椭圆形方法的启发，它具有最佳的线性收敛速率。在他们的工作中，我们提出了一个紧密的变体，它迭代地保持了目标函数的二次全球估计量，其最小价值以最佳的速度接近了真正的最低限度。最终的直观方案配备了自然停止标准，并且可以通过使用累积信息在数值上加速。
In a recent paper, Bubeck, Lee, and Singh introduced a new first order method for minimizing smooth strongly convex functions. Their geometric descent algorithm, largely inspired by the ellipsoid method, enjoys the optimal linear rate of convergence. Motivated by their work, we propose a close variant that iteratively maintains a quadratic global under-estimator of the objective function, whose minimal value approaches the true minimum at an optimal rate. The resulting intuitive scheme comes equipped with a natural stopping criterion and can be numerically accelerated by using accumulated information.