On the oracle complexity of smooth strongly convex minimization

DOI10.1016/j.jco.2021.101590zbMath1481.90250arXiv2101.09740OpenAlexW3179524346MaRDI QIDQ2052164

Yoel Drori, Adrien B. Taylor

Publication date: 25 November 2021

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2101.09740

zbMATH Keywords

information-based complexitystrongly convex functionsoptimal methodsoracle complexity

Mathematics Subject Classification ID

Convex programming (90C25)

Related Items (5)

An optimal gradient method for smooth strongly convex minimization ⋮ Factor-\(\sqrt{2}\) acceleration of accelerated gradient methods ⋮ A robust control approach to asymptotic optimality of the heavy ball method for optimization of quadratic functions ⋮ Branch-and-bound performance estimation programming: a unified methodology for constructing optimal optimization methods ⋮ Convex Synthesis of Accelerated Gradient Algorithms

Uses Software

• PESTO

Cites Work

• Unnamed Item
• Unnamed Item
• An extension theorem for convex functions of class \(C^{1,1}\) on Hilbert spaces
• On lower complexity bounds for large-scale smooth convex optimization
• Smooth strongly convex interpolation and exact worst-case performance of first-order methods
• The exact information-based complexity of smooth convex minimization
• On optimality of Krylov's information when solving linear operator equations
• Information-based complexity of linear operator equations
• Introductory lectures on convex optimization. A basic course.
• Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
• Oracle complexity of second-order methods for smooth convex optimization
• Explicit formulas for 𝐶^{1,1} Glaeser-Whitney extensions of 1-Taylor fields in Hilbert spaces

This page was built for publication: On the oracle complexity of smooth strongly convex minimization