Some comments on Wolfe's ‘away step’

By Jacques Guélat, Patrice Marcotte. 1986

How researchers see this paper

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

In Optimization & Training

Citations in the corpus

Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, background): “When the optimum is in the relative interior of any compact set C , FW converges linearly when f is strongly convex [Gu´elat et al. 1986; Lacoste-Julien et al. 2013].”
Frank-Wolfe Algorithms for Saddle Point Problems (2016, methodology): “If we assume that X and Y are the convex hulls of two finite sets of pointsA and B, we can also extend the awaystep Frank-Wolfe (AFW) algorithm (Guélat and Marcotte, 1986; Lacoste-Julien and Jaggi, 2015) to saddle point problems.”
Barrier Frank-Wolfe for Marginal Inference (2015, methodology): “For a strongly convex objective (with Lipschitz continuous gradient), the MFW was known to have asymptotic linear convergence (Guélat and Marcotte, 1986) and its global linear convergence rate was shown recently (Lacoste-Julien and Jaggi, 2015), accelerating the slow general sublinear rate of Frank-”
Automated Scalable Bayesian Inference via Hilbert Coresets (2017, methodology): “Next, taking inspiration from the large-scale optimization literature Frank and Wolfe (1956); Gu´elat and Marcotte (1986); Jaggi (2013); Lacoste-Julien and Jaggi (2015); Clarkson (2010); Reddi et al. (2016); Balasubramanian and Ghadimi (2018); Hazan and Luo (2016), we solve the convex optimization…”
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”
The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle (2013, methodology): “22]. In addition, the linear convergence of the CndG method has been shown in [44] for the case when the feasible set X is round (strongly convex as a set), and similar result has been generalized in [25] for the case when the optimal solution resides in the interior of the feasible set. The Complex”
Fast Stochastic Frank-Wolfe Algorithms for Nonlinear SVMs (2010, methodology): “See the first part of Theorem 5’s proof in [31].”
Efficient Image and Video Co-localization with Frank-Wolfe Algorithm (2014, background): “This version of Frank-Wolfe has been shown to have better convergence rates [18, 25].”
Linearly Convergent Frank-Wolfe with Backtracking Line-Search. (2018, background): “Two of these variants, the Away-steps FW (Gu´elat and Marcotte, 1986) and Pairwise FW (Lacoste-Julien and Jaggi, 2015) enjoy a linear rate of convergence over polytopes (Lacoste-Julien and Jaggi, 2015).”
A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization (2013, background): “d in [15], however their algorithms require to solve a regularized linear problem on each iteration which is computationally equivalent to computing projections. In case the convex set is a polytope, [7] has shown that the algorithm of [6] converges in linear rate assuming that the optimal point in ”
Frank-Wolfe with Subsampling Oracle (2018, methodology): “A popular variant of the FW algorithm is the Away-steps FW variant of Gu´elat & Marcotte (1986).”