On lower complexity bounds for large-scale smooth convex optimization

DOI10.1016/j.jco.2014.08.003zbMath1304.65155arXiv1307.5001OpenAlexW2048841424WikidataQ57392879 ScholiaQ57392879MaRDI QIDQ478994

Cristóbal Guzmán, Arkadi Nemirovski

Publication date: 5 December 2014

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

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

zbMATH Keywords

information-based complexityoptimal algorithmssmooth convex optimizationconditional gradient algorithmlower complexity bounds

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Complexity and performance of numerical algorithms (65Y20)

Related Items

Projection-free accelerated method for convex optimization, Lower Bounds for Parallel and Randomized Convex Optimization, New results on subgradient methods for strongly convex optimization problems with a unified analysis, Optimal complexity and certification of Bregman first-order methods, Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization, Unnamed Item, Affine-invariant contracting-point methods for convex optimization, Optimal Affine-Invariant Smooth Minimization Algorithms, Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems, Universal method for stochastic composite optimization problems, The exact information-based complexity of smooth convex minimization, Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraints, Fast gradient descent for convex minimization problems with an oracle producing a \(( \delta, L)\)-model of function at the requested point, Some worst-case datasets of deterministic first-order methods for solving binary logistic regression, Accelerated directional search with non-Euclidean prox-structure, On the oracle complexity of smooth strongly convex minimization, Conditional Gradient Sliding for Convex Optimization, An adaptive proximal method for variational inequalities

Cites Work

• On optimality of Krylov's information when solving linear operator equations
• Information-based complexity of linear operator equations
• On parallel complexity of nonsmooth convex optimization
• Introductory lectures on convex optimization. A basic course.
• Optimal methods of smooth convex minimization
• Sparse Approximate Solutions to Semidefinite Programs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item