Linearly convergent away-step conditional gradient for non-strongly convex functions

By Amir Beck, Shimrit Shtern. 2015

115 citations recorded by the source corpus.

We consider the problem of minimizing the sum of a linear function and a composition of a strongly convex function with a linear transformation over a compact polyhedral set. Jaggi and Lacoste-Julien (An affine invariant linear convergence analysis for Frank-Wolfe algorithms. NIPS 2013 Workshop on Greedy Algorithms, Frank-Wolfe and Friends, 2014) show that the conditional gradient method with away steps — employed on the aforementioned problem without the additional linear term — has a linear rate of convergence, depending on the so-called pyramidal width of the feasible set. We revisit this result and provide a variant of the algorithm and an analysis based on simple linear programming duality arguments, as well as corresponding error bounds. This new analysis (a) enables the incorporation of the additional linear term, and (b) depends on a new constant, that is explicitly expressed in terms of the problem’s parameters and the geometry of the feasible set. This constant replaces the pyramidal width, which is difficult to evaluate.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, 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 Numerical Analysis

In Optimization & Training

Citations in the corpus

Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs (2016, background): “However, the regularization path algorithm finds solutions for all values of λ without the need to predefine the grid.”
On the Global Linear Convergence of Frank-Wolfe Optimization Variants (2015, methodology): “Building on a preliminary version of our work [20], Beck and Shtern [4] also proved a linear rate for away-steps FW, but with a simpler lower bound for the LHS of (10) using linear duality arguments.”
Linear convergence of first order methods for non-strongly convex optimization (2015, background): “Several other papers on the linear convergence of ﬁrst order methods for non-strongly convex optimization have appeared recently (after this paper was ﬁnalized) [8,13–15].”
The restricted strong convexity revisited: analysis of equivalence to error bound and quadratic growth (2015, background): “To avoid such dependence, the authors of [3] derived the quadratic growth property f (y) ≥ f ∗ + κ4 · d2(y,X ), ∀y ∈ Q for f (x) = g(Ex)+qT x by assuming that Q is compact, where κ4 > 0 is a constant.”
Projection-Free Optimization on Uniformly Convex Sets (2020, background): “…mechanisms (Guélat and Marcotte, 1986; Hearn et al., 1987) that lead to linear convergence rates under appropriate structures of the objective function (Garber and Hazan, 2013a; Lacoste-Julien and Jaggi, 2013, 2015; Beck and Shtern, 2017; Gutman and Pena, 2018; Pena and Rodriguez, 2018).”
From error bounds to the complexity of first-order descent methods for convex functions (2015, methodology): “E-mail: jerome.bolte@tse-fr.eu, Effort partially sponsored by the Air Force Office of Scientific Research, Air Force Material Command, USAF, under grant number FA9550-14-1-0056, the FMJH Program Gaspard Monge in optimization and operations research and ANR GAGA †Toulouse School of Economics, Univers”
Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization (2020, background): “non-polyhedral sets like the `2-ball) such as the pyramidal width [10], vertex-facet distance [19], eccentricity of the polytope [10] or sparsity-dependent constants [3], which have been shown to be essentially equivalent3 [20].”
Linear-Memory and Decomposition-Invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes (2016, methodology): “#LOO calls runtime memory Frank & Wolfe [5] D2/✏ 1 n n Garber & Hazan [8] nD2 log(1/✏) 1 nmin(n, t) nmin(n, t) Lacoste-Julien & Jaggi [16] nD2 log(1/✏) 1 nmin(n, t) nmin(n, t) Beck & Shtern [2] n2D2 log(1/✏) 1 nmin(n, t) nmin(n, t) This paper card(x⇤)D2 log(1/✏) 2 n n Table 1: Comparison with pr”