The exact information-based complexity of smooth convex minimization

详细信息    查看全文

• 作者：Yoel Drori ^{dyoel@google.com}
• 关键词：Convex optimization ; Complexity ; Rate of convergence ; Information-based complexity
• 刊名：Journal of Complexity
• 出版年：2017
• 出版时间：April 2017
• 年：2017
• 卷：39
• 期：Complete
• 页码：1-16
• 全文大小：434 K
• 卷排序：39

文摘

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.