The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle

Abstract

This paper considers a general class of iterative optimization algorithms, referred to as linear-optimization-based convex programming (LCP) methods, for solving large-scale convex programming (CP) problems. The LCP methods, covering the classic conditional gradient (CG) method (a.k.a., Frank-Wolfe method) as a special case, can only solve a linear optimization subproblem at each iteration. In this paper, we first establish a series of lower complexity bounds for the LCP methods to solve different classes of CP problems, including smooth, nonsmooth and certain saddle-point problems. We then formally establish the theoretical optimality or nearly optimality, in the large-scale case, for the CG method and its variants to solve different classes of CP problems. We also introduce several new optimal LCP methods, obtained by properly modifying Nesterov's accelerated gradient method, and demonstrate their possible advantages over the classic CG for solving certain classes of large-scale CP problems.

The paper first appeared in optimization-online.org in May 2013

References in corpus (2)

• Large-Scale Convex Minimization with a Low-Rank Constraint
• On the Equivalence between Herding and Conditional Gradient Algorithms

Cited by in corpus (39)

• On the Global Linear Convergence of Frank-Wolfe Optimization Variants
• Convergence Rate of Frank-Wolfe for Non-Convex Objectives
• Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
• An Affine Invariant Linear Convergence Analysis for Frank-Wolfe Algorithms
• Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory
• Conditional Accelerated Lazy Stochastic Gradient Descent
• Generalized Uniformly Optimal Methods for Nonlinear Programming
• Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
• Projection-Free Optimization on Uniformly Convex Sets
• A Conditional Gradient-Based Augmented Lagrangian Framework
• Convergence of Value Aggregation for Imitation Learning
• Distributionally Robust Submodular Maximization
• Frank-Wolfe Method is Automatically Adaptive to Error Bound Condition
• Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method
• Boosting Frank-Wolfe by Chasing Gradients
• On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization
• Local and Global Uniform Convexity Conditions
• Self-Concordant Analysis of Frank-Wolfe Algorithms
• How Does Momentum Help Frank Wolfe?
• Faster Projection-free Online Learning
• Semi-proximal Mirror-Prox for Nonsmooth Composite Minimization
• Frank-Wolfe Methods with an Unbounded Feasible Region and Applications to Structured Learning
• Parameter-free Locally Accelerated Conditional Gradients
• Heavy Ball Momentum for Conditional Gradient
• Efficient Projection-Free Algorithms for Saddle Point Problems
• Locally Accelerated Conditional Gradients
• Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraints
• Backtracking linesearch for conditional gradient sliding
• Projection-Free Algorithms in Statistical Estimation
• Frank-Wolfe with a Nearest Extreme Point Oracle
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Semi-Stochastic Frank-Wolfe Algorithms with Away-Steps for Block-Coordinate Structure Problems
• On the Frank-Wolfe algorithm for non-compact constrained optimization problems
• Fast and Scalable Lasso via Stochastic Frank-Wolfe Methods with a Convergence Guarantee
• Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization
• Safe Convex Learning under Uncertain Constraints
• Safe non-smooth black-box optimization with application to policy search
• Consistent Classification Algorithms for Multi-class Non-Decomposable Performance Metrics
• Frank-Wolfe variants for minimization of a sum of functions