An optimal gradient method for smooth strongly convex minimization

Autor:	Taylor, Adrien, Drori, Yoel
Rok vydání:	2021
Předmět:	Mathematics - Optimization and Control Mathematics - Numerical Analysis
Druh dokumentu:	Working Paper
Popis:	We present an optimal gradient method for smooth strongly convex optimization. The method is optimal in the sense that its worst-case bound on the distance to an optimal point exactly matches the lower bound on the oracle complexity for the class of problems, meaning that no black-box first-order method can have a better worst-case guarantee without further assumptions on the class of problems at hand. In addition, we provide a constructive recipe for obtaining the algorithmic parameters of the method and illustrate that it can be used for deriving methods for other optimality criteria as well. Comment: Accepted for publication in Mathematical Programming. Codes available at https://github.com/AdrienTaylor/Optimal-Gradient-Method (symbolic verifications and numerical experiments)
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2101.09741 Zobrazit plný text záznamu View this record from Arxiv