The exact information-based complexity of smooth convex minimization

DOI10.1016/j.jco.2016.11.001zbMath1357.68072arXiv1606.01424OpenAlexW2963385703MaRDI QIDQ511109

Yoel Drori

Publication date: 14 February 2017

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

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

zbMATH Keywords

complexityrate of convergenceconvex optimizationinformation-based complexity

Mathematics Subject Classification ID

Convex programming (90C25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (19)

Optimal complexity and certification of Bregman first-order methods ⋮ On the Properties of Convex Functions over Open Sets ⋮ Generalizing the Optimized Gradient Method for Smooth Convex Minimization ⋮ Adaptive restart of the optimized gradient method for convex optimization ⋮ Exact worst-case convergence rates of the proximal gradient method for composite convex minimization ⋮ Potential Function-Based Framework for Minimizing Gradients in Convex and Min-Max Optimization ⋮ An optimal gradient method for smooth strongly convex minimization ⋮ Factor-\(\sqrt{2}\) acceleration of accelerated gradient methods ⋮ Branch-and-bound performance estimation programming: a unified methodology for constructing optimal optimization methods ⋮ Another Look at the Fast Iterative Shrinkage/Thresholding Algorithm (FISTA) ⋮ Efficient first-order methods for convex minimization: a constructive approach ⋮ Operator Splitting Performance Estimation: Tight Contraction Factors and Optimal Parameter Selection ⋮ On the convergence analysis of the optimized gradient method ⋮ Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions ⋮ Some worst-case datasets of deterministic first-order methods for solving binary logistic regression ⋮ On the oracle complexity of smooth strongly convex minimization ⋮ Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs ⋮ Bilevel Methods for Image Reconstruction ⋮ Exact Worst-Case Performance of First-Order Methods for Composite Convex Optimization

Uses Software

• PESTO

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimized first-order methods for smooth convex minimization
• An optimal variant of Kelley's cutting-plane method
• On lower complexity bounds for large-scale smooth convex optimization
• Information-based complexity of linear operator equations
• Introductory lectures on convex optimization. A basic course.
• Performance of first-order methods for smooth convex minimization: a novel approach
• Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization
• Information-Based Complexity, Feedback and Dynamics in Convex Programming

This page was built for publication: The exact information-based complexity of smooth convex minimization