An optimal gradient method for smooth strongly convex minimization

• 成果类型: Article
• 署名作者: Taylor, Adrien; Drori, Yoel
• 署名单位: Inria; Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01839-y
• 发表日期: 2023
• 页码: 557-594
• 关键词: performance

摘要

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.