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

By Guanghui Lan. 2013

144 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics, Optimization & Training

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

In Optimization & Training

Citations in the corpus

Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, positive): “The affine invariant analysis of (Jaggi, 2013) is better than any known other analysis is the sense that (see also (Lan, 2013)) Cf ≤ min w∈F L‖·‖D 2 ‖·‖, (12)”
Frank-Wolfe Algorithms for Saddle Point Problems (2016, background): “Lan (2013) proposes to solve the saddle point problem (1) by running FW on X on the smoothed version of the problem max y ∈Y L ( x , y ), thus requiring a projection oracle on Y .”
Breaking the Curse of Dimensionality with Convex Neural Networks (2014, neutral): “See also Lan (2013).”
On the Global Linear Convergence of Frank-Wolfe Optimization Variants (2015, background): “In a different recent line of work, [10, 22] have studied a variation of FW that repeatedly moves mass from the worst vertices to the standard FW vertex until a specific condition is satisfied, yielding a linear rate on strongly convex functions.”
Accelerated gradient methods for nonconvex nonlinear and stochastic programming (2013, methodology): “To establish the convergence of the above AG method, we need the following simple technical result (see Lemma 3 of [16] for a slightly more general result).”
An Affine Invariant Linear Convergence Analysis for Frank-Wolfe Algorithms (2013, background): “1This can be interpreted as a concrete instantiation of the stronger oracle proposed in [Lan13].”
Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets (2014, background): “We motivate the study of optimization over strongly convex sets by showing that various norms that serve as popular regularizes in machine learning problems, including `p norms, matrix Schatten norms and matrix group norms, give rise to strongly convex sets.”
Boosting Frank-Wolfe by Chasing Gradients (2020, background): “…x ∈ Rn 7→ ‖x‖22 is the squared `2-norm and C = ∆n is the standard simplex, then the primal gap at iteration t ∈ J1, nK is lower bounded by 1/t−1/n; see also Lan (2013) for a lower bound Ω(LD2/t) on an equivalent setup, exhibiting an explicit dependence on the smoothness constant L of f and the…”
Projection-Free Optimization on Uniformly Convex Sets (2020, background): “The Frank-Wolfe algorithm admits a tight (Canon and Cullum, 1968; Jaggi, 2013; Lan, 2013) general sublinear convergence rate of O (1 /T ) when C is a compact convex set and f is a convex L -smooth function.”
Convergence Rate of Frank-Wolfe for Non-Convex Objectives (2016, background): “See also Lan (2013) for a related survey.”
Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization (2020, background): “This algorithm however, can only guarantee a sub-linear rate of O(1/t) for smooth and strongly convex optimization on a compact domain [9, 2], moreover, this rate is tight [13, 14].”
New analysis and results for the Frank–Wolfe method (2013, methodology): “Our analysis retains the well-known optimal O( 1 k ) rate (optimal for linear optimization oracle-based methods [18], following also from [15]) when the step-size is either given by the rule ᾱk := 2 k+2 or is determined by a line-search.”
A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem (2022, background): “We also remark that our rate is tight at least within the family of projection-free methods, since it is known that their worstcase complexity is Θ(1/ f ) even for a single-level problem (Jaggi, 2013; Lan, 2013).”
Linear-Memory and Decomposition-Invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes (2016, methodology): “Then, in Subsection 3.2, we present our new method, a decomposition-invariant away-steps-based conditional gradient algorithm, and discuss how it addresses the major shortcomings of previous away-steps-based variants.”
Revisiting Projection-Free Optimization for Strongly Convex Constraint Sets (2018, methodology): “Denote the diameter D of Ω as PA has a similar guarantee for the sequence ( w t ) t =1 , 2 ,... (Lan 2013).”
Complexity bounds for primal-dual methods minimizing the model of objective function (2017, methodology): “Moreover, it appears that this rate of convergence is optimal for methods with linear optimization oracle [11].”
Convergence of Value Aggregation for Imitation Learning (2018, unknown): “(Lan, 2013, Lemma 1) Let γk ∈ (0, 1), k = 1, 2, . . . be given.”
Frank-Wolfe Method is Automatically Adaptive to Error Bound Condition (2018, methodology): “…of the FW method and its variants (Levitin and Polyak, 1966; Demyanov and Rubinov, 1970; Dunn, 1979; Gu´elat and Marcotte, 1986; Beck and Teboulle, 2004; Garber and Hazan, 2013; Lan, 2013; Lacoste-Julien and Jaggi, 2013; Garber and Hazan, 2015; Lacoste-Julien and Jaggi, 2015; Lan and Zhou, 2016).”