The exact information-based complexity of smooth convex minimization
From MaRDI portal
Publication:511109
DOI10.1016/J.JCO.2016.11.001zbMATH Open1357.68072arXiv1606.01424OpenAlexW2963385703MaRDI QIDQ511109FDOQ511109
Publication date: 14 February 2017
Published in: Journal of Complexity (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1606.01424
Recommendations
- scientific article; zbMATH DE number 3516928
- Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory
- Information complexity of mixed-integer convex optimization
- Information-Based Complexity, Feedback and Dynamics in Convex Programming
- Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization
- On the oracle complexity of smooth strongly convex minimization
- Information complexity of functional optimization problems and their approximation schemes
- On the minimal cost of approximating linear problems based on information with deterministic noise
- Informational inequalities in the problem of gradient stochastic optimization and optimal realizable algorithms
- Sequential convex programming for computing information-theoretic minimal partitions: nonconvex nonsmooth optimization
Convex programming (90C25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Introductory lectures on convex optimization. A basic course.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Performance of first-order methods for smooth convex minimization: a novel approach
- Optimized first-order methods for smooth convex minimization
- On lower complexity bounds for large-scale smooth convex optimization
- On complexity of stochastic programming problems
- An optimal variant of Kelley's cutting-plane method
- Information-based complexity of linear operator equations
- Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization
- Information-Based Complexity, Feedback and Dynamics in Convex Programming
Cited In (22)
- Exact Worst-Case Performance of First-Order Methods for Composite Convex Optimization
- Potential Function-Based Framework for Minimizing Gradients in Convex and Min-Max Optimization
- On the oracle complexity of smooth strongly convex minimization
- Bilevel Methods for Image Reconstruction
- On the minimal cost of approximating linear problems based on information with deterministic noise
- Some worst-case datasets of deterministic first-order methods for solving binary logistic regression
- Efficient first-order methods for convex minimization: a constructive approach
- Optimal complexity and certification of Bregman first-order methods
- Factor-\(\sqrt{2}\) acceleration of accelerated gradient methods
- Adaptive restart of the optimized gradient method for convex optimization
- Exact worst-case convergence rates of the proximal gradient method for composite convex minimization
- Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions
- An optimal gradient method for smooth strongly convex minimization
- On the Properties of Convex Functions over Open Sets
- On parallel complexity of nonsmooth convex optimization
- Generalizing the Optimized Gradient Method for Smooth Convex Minimization
- Another Look at the Fast Iterative Shrinkage/Thresholding Algorithm (FISTA)
- On the convergence analysis of the optimized gradient method
- Informational inequalities in the problem of gradient stochastic optimization and optimal realizable algorithms
- Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs
- Operator Splitting Performance Estimation: Tight Contraction Factors and Optimal Parameter Selection
- Branch-and-bound performance estimation programming: a unified methodology for constructing optimal optimization methods
Uses Software
This page was built for publication: The exact information-based complexity of smooth convex minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q511109)
