The exact information-based complexity of smooth convex minimization
The exact information-based complexity of smooth convex minimization
复制标题
光滑凸最小化的精确的基于信息的复杂性
DOI：
10.1016/j.jco.2016.11.001
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Yoel Drori
中科院分区：
文献类型：
--
作者：
Yoel Drori
我们得到了光滑函数和凸函数一阶最小化的信息复杂度的一个新的下界。我们证明了边界与最近引入的优化梯度方法的最坏情况性能相匹配（Drori and Teboulle, 2013; Kim and Fessler, 2015），从而建立了边界是紧密的，可以通过有效的算法实现。该证明是基于一种新的光滑和凸函数构造技术。
We obtain a new lower bound on the information-based complexity of first-order minimization of smooth and convex functions. We show that the bound matches the worst-case performance of the recently introduced Optimized Gradient Method (Drori and Teboulle, 2013; Kim and Fessler, 2015), thereby establishing that the bound is tight and can be realized by an efficient algorithm. The proof is based on a novel construction technique of smooth and convex functions.