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
Authors: Yoel Drori 
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 (26)
- On the properties of convex functions over open sets
- Potential Function-Based Framework for Minimizing Gradients in Convex and Min-Max Optimization
- On the oracle complexity of smooth strongly convex minimization
- On lower and upper bounds in smooth and strongly convex optimization
- Oracle complexity of second-order methods for smooth convex optimization
- Bilevel Methods for Image Reconstruction
- Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)
- Generalizing the optimized gradient method for smooth convex minimization
- Operator splitting performance estimation: tight contraction factors and optimal parameter selection
- On the minimal cost of approximating linear problems based on information with deterministic noise
- Exact worst-case performance of first-order methods for composite convex optimization
- 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
- On lower complexity bounds for large-scale smooth convex optimization
- 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 parallel complexity of nonsmooth convex optimization
- 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
- Branch-and-bound performance estimation programming: a unified methodology for constructing optimal optimization methods
- Information complexity of mixed-integer convex optimization
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)
