A conditional gradient method with linear rate of convergence for solving convex linear systems

By Amir Beck, Marc Teboulle. 2004

88 citations recorded by the source corpus.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

In Mathematical Optimization

Citations in the corpus

On the Equivalence between Herding and Conditional Gradient Algorithms (2012, neutral): “For the version with line search, we actually obtain a linear convergence rate (Beck & Teboulle, 2004): For the version without line search ( ρ t = 1 / ( t + 1)), Chen et al. (2010) shows the slower convergence rate Concerning the assumption that µ is in the relative interior of M , we now show…”
On the Global Linear Convergence of Frank-Wolfe Optimization Variants (2015, methodology): “Our analysis does not depend on the location of the true optimum with respect to the domain, which was a disadvantage of earlier existing results such as [34, 12, 5], and the newer work of [28], as well as the line of work of [1, 19, 26] which rely on Robinson’s condition [30].”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, methodology): “be obtained. See more details in [9]. Note ﬁnally, that if Ψ∗ is also strongly convex (i.e., when Ψ is smooth) and the global optimum is in the interior of K, then the convergence rate is exponential [87, 19]. 83 7.7 Bundle and simplicial methods In §7.4, we have considered the minimization of a fun”
Frank-Wolfe Method is Automatically Adaptive to Error Bound Condition (2018, methodology): “…to get faster rates 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;…”
Linearly convergent away-step conditional gradient for non-strongly convex functions (2015, background): “1 Epelman and Freund [7], as well as Beck and Teboulle [1], show a linear rate of convergence of the conditional gradient with a special stepsize choice in the context of ﬁnding a point in the intersection of an afﬁne space and a closed and convex set under a Slater-type assumption.”
The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle (2013, methodology): “This method has recently regained some interests from both machine learning and optimization community (see, e.g., [1,3,5,11,10,21,27, 26,28,29,30,36,46,47]) mainly for the following reasons.”
Linear-Memory and Decomposition-Invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes (2016, result): “A similar result was presented by Beck and Teboulle [3] who considered a specific problem they refer to a the convex feasibility problem over an arbitrary convex set.”
Proximal Algorithms in Statistics and Machine Learning (2015, methodology): “The most common approach involves Nes-terov acceleration; see Nesterov [1983] and Beck and Teboulle [2004] who introduce a momentum term for gradient-descent algorithms applied to non-smooth composite problems.”
A novel Frank-Wolfe algorithm. Analysis and applications to large-scale SVM training (2013, methodology): “The convergence of the FW method specialized to a quadratic program (arising from a linear system) has been also studied in [4].”