The exact information-based complexity of smooth convex minimization

2016/06/04 by Drori, Yoel · 9 citations
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1606.01424

Abstract

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.

Cited by

• Essential Convergence Rates of Continuous-Time Models for Optimization Methods
• Optimal Subgradient Methods for Lipschitz Convex Optimization with Error Bounds
• H-invariance theory: A complete characterization of minimax optimal fixed-point algorithms
• Subgame Perfect Methods in Nonsmooth Convex Optimization
• A Practical Adaptive Subgame Perfect Gradient Method
• Optimization in Theory and Practice
• Lower Bounds for Linear Minimization Oracle Methods Optimizing over Strongly Convex Sets
• AutoLyap: A Python package for computer-assisted Lyapunov analyses for first-order methods
• Optimized methods for composite optimization: a reduction perspective

Related

• On the oracle complexity of smooth strongly convex minimization
• On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization
• Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functions
• An optimal lower bound for smooth convex functions
• Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness