The exact information-based complexity of smooth convex minimization

Autor:	Drori, Yoel
Rok vydání:	2016
Předmět:	Mathematics - Optimization and Control
Druh dokumentu:	Working Paper
Popis:	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, 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.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1606.01424 Zobrazit plný text záznamu View this record from Arxiv