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

arXiv: https://arxiv.org/abs/1309.5550 · HTML: https://mlsanity.com/paper/1309.5550/

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Sep 2013.

## Built on by (most cited first, 29 of 29)

- [A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem](https://mlsanity.com/paper/2206.08868/) (2022)
- [Optimizing generalized Gini indices for fairness in rankings](https://mlsanity.com/paper/2204.06521/) (2022)
- [FISMO: Fisher-Structured Momentum-Orthogonalized Optimizer](https://mlsanity.com/paper/2601.21750/) (2026)
- [Regularized Frank-Wolfe for Dense CRFs: Generalizing Mean Field and Beyond](https://mlsanity.com/paper/2110.14759/) (2021)
- [Frank-Wolfe with a Nearest Extreme Point Oracle](https://mlsanity.com/paper/2102.02029/) (2021)
- [Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization](https://mlsanity.com/paper/2203.12633/) (2022)
- [Convergence of Value Aggregation for Imitation Learning](https://mlsanity.com/paper/1801.07292/) (2018)
- [Heavy Ball Momentum for Conditional Gradient](https://mlsanity.com/paper/2110.04243/) (2021)
- [Parameter-free Locally Accelerated Conditional Gradients](https://mlsanity.com/paper/2102.06806/) (2021)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [Local and Global Uniform Convexity Conditions](https://mlsanity.com/paper/2102.05134/) (2021)
- [Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelization](https://mlsanity.com/paper/2205.12751/) (2022)
- [Reusing Combinatorial Structure: Faster Iterative Projections over Submodular Base Polytopes](https://mlsanity.com/paper/2106.11943/) (2021)
- [Contextual bandits with concave rewards, and an application to fair ranking](https://mlsanity.com/paper/2210.09957/) (2022)
- [Linearization Algorithms for Fully Composite Optimization](https://mlsanity.com/paper/2302.12808/) (2023)
- [End-to-End Learning for Fair Multiobjective Optimization Under Uncertainty](https://mlsanity.com/paper/2402.07772/) (2024)
- [Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization](https://mlsanity.com/paper/2202.13212/) (2022)
- [Learning Fair Ranking Policies via Differentiable Optimization of Ordered Weighted Averages](https://mlsanity.com/paper/2402.05252/) (2024)
- [Using Taylor-Approximated Gradients to Improve the Frank-Wolfe Method for Empirical Risk Minimization](https://mlsanity.com/paper/2208.13933/) (2022)
- [Nonsmooth Projection-Free Optimization with Functional Constraints](https://mlsanity.com/paper/2311.11180/) (2023)
- [Quantum Algorithms for Projection-Free Sparse Convex Optimization](https://mlsanity.com/paper/2507.08543/) (2025)
- [Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity](https://mlsanity.com/paper/2511.02821/) (2025)
- [Empirical evaluation of the Frank-Wolfe methods for constructing white-box adversarial attacks](https://mlsanity.com/paper/2512.10936/) (2025)
- [Broximal Gradient Descent: A Projection-Free Sister of Projected Gradient Descent](https://mlsanity.com/paper/2605.08850/) (2026)
- [Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization](https://mlsanity.com/paper/2609.24423/) (2026)
- [Local LMO is Secretly a Projection Method!](https://mlsanity.com/paper/2609.33383/) (2026)
- [Lower Bounds for Linear-Oracle Online Learning](https://mlsanity.com/paper/2609.38375/) (2026)
- [Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization](https://mlsanity.com/paper/2610.00254/) (2026)
- [Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets](https://mlsanity.com/paper/2610.13590/) (2026)

## Abstract (arXiv)

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.