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

2013/09/22 by Guanghui Lan, Lan, Guanghui · 18 citations
Engineering · Computer Science · #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Complexity and Algorithms in Graphs

paper · pdf · doi:10.48550/arxiv.1309.5550

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.

Citations

• Large-Scale Convex Minimization with a Low-Rank Constraint
• Smooth minimization of non-smooth functions

Cited by

• Empirical evaluation of the Frank-Wolfe methods for constructing white-box adversarial attacks
• Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity
• Frank-Wolfe variants for minimization of a sum of functions
• Backtracking linesearch for conditional gradient sliding
• Frank-Wolfe Methods with an Unbounded Feasible Region and Applications to Structured Learning
• Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization
• Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method
• Self-Concordant Analysis of Frank-Wolfe Algorithms
• A Conditional Gradient-Based Augmented Lagrangian Framework
• Simplex Frank-Wolfe: Linear Convergence and Its Numerical Efficiency for Convex Optimization over Polytopes
• Fast and Scalable Lasso via Stochastic Frank-Wolfe Methods with a\n Convergence Guarantee
• Lower Bounds for Linear Minimization Oracle Methods Optimizing over Strongly Convex Sets
• Distributionally Robust Submodular Maximization
• Consistent Classification Algorithms for Multi-class Non-Decomposable Performance Metrics
• A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming
• Semi-proximal Mirror-Prox for Nonsmooth Composite Minimization
• On the Frank-Wolfe algorithm for non-compact constrained optimization problems
• Projection-Free Algorithms in Statistical Estimation

Related

• An optimal subgradient algorithm for large-scale convex optimization in simple domains
• On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization
• Accelerated first-order methods for large-scale convex minimization
• A Primal-Dual Type Algorithm with the O(1/t) Convergence Rate for Large Scale Constrained Convex Programs
• Lower bounds for conditional gradient type methods for minimizing smooth strongly convex functions