On lower complexity bounds for large-scale smooth convex optimization

By Crist'obal Guzm'an, Arkadi Nemirovski. 2013

87 citations recorded by the source corpus.

We derive lower bounds on the black-box oracle complexity of large-scale smooth convex minimization problems, with emphasis on minimizing smooth (with Holder continuous, with a given exponent and constant, gradient) convex functions over high-dimensional ? ? ? p -balls, 1 ? p ? ∞ . Our bounds turn out to be tight (up to logarithmic in the design dimension factors), and can be viewed as a substantial extension of the existing lower complexity bounds for large-scale convex minimization covering the nonsmooth case and the "Euclidean" smooth case (minimization of convex functions with Lipschitz continuous gradients over Euclidean balls). As a byproduct of our results, we demonstrate that the classical Conditional Gradient algorithm is near-optimal, in the sense of Information-Based Complexity Theory, when minimizing smooth convex functions over high-dimensional ? ? ? ∞ -balls and their matrix analogies-spectral norm balls in the spaces of square matrices.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computational Theory and Mathematics

Citations in the corpus

Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization (2018, methodology): “In the case of the gradient oracle, we “smooth out” a standard non-smooth lower bound construction [20, 26]; previous work has used a similar approach in slightly different settings [2, 12].”
An Optimal Affine Invariant Smooth Minimization Algorithm (2013, methodology): “The second range, p ∈ [2,∞], requires a more specific argument since the lower bounds in Guzmán and Nemirovski [2013] are written in a dimension-free form.”
Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization (2015, unknown): “[54, 13, 40]) with a lot of renewed interest due to applications in machine learning (e.”