Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization

By Martin Jaggi. 2013

1,516 citations recorded by the source corpus.

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

End-to-End Learning of Visual Representations From Uncurated Instructional Videos (2019, methodology): “The Frank-Wolfe algorithm [11, 15] allows to minimize large convex problems over convex sets by solving a sequence of linear problems.”
Controlled Sparsity via Constrained Optimization or: How I Learned to Stop Tuning Penalties and Love Constraints (2022, methodology): “Commonly used methods for solving constrained convex optimization problems [1, 11, 21] make assumptions on the properties of the objective function, constraints or feasible set.”
Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, methodology): “In that setting, Clarkson 2010; Jaggi 2013 deﬁne a modulus of smoothness that leads to aﬃne invariant analysis of the Frank-Wolfe algo-rithm, matching with the aﬃne covariant behavior of the algorithm.”
Frank-Wolfe Splitting via Augmented Lagrangian Method (2018, methodology): “This property has been proved for the block-coordinate Frank-Wolfe method 3 (Lacoste-Julien et al., 2013), usual Frank-Wolfe (Jaggi, 2013) and Frank-Wolfe with away-step (Lacoste-Julien and Jaggi, 2015).”
Joint Discovery of Object States and Manipulation Actions (2017, background): “When dealing with a constrained optimization problem for which it is easy to solve linear programs but difficult to project on the feasible set, the Frank-Wolfe algorithm is an excellent choice [23, 29].”
Frank-Wolfe Algorithms for Saddle Point Problems (2016, methodology): “Next, we recall two lemmas, one from Lacoste-Julien and Jaggi (2013) and the other one from (Lacoste-Julien and Jaggi, 2015).”
Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs (2016, methodology): “Then similarly to Lemma 7 in Jaggi (2013), we have C (i) f ≤ Li ( diam‖·‖iM (i) )2. easy.”
Barrier Frank-Wolfe for Marginal Inference (2015, methodology): “The primal convergence of the Frank-Wolfe algorithm is given by Thm. 1 in Jaggi (2013), restated here for convenience: for k ≥ 1, the iterates x(k) satisfy: (4)f(x(k))− f(x∗) ≤ 2Cf k + 2 , where Cf is called the “curvature constant”.”
Unsupervised Learning from Narrated Instruction Videos (2015, background): “In contrast, we show in the appendix of the paper [2] that the multiple sequence alignment problem given by (1) can be reformulated as an integer quadratic program with combinatorial constraints, for which the FrankWolfe optimization algorithm has been used recently with increasing success [5, 14, 1”
Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering (2015, methodology): “A third alternative is to re-optimize J(g) over the convex hull of the previously visited vertices; this is called the fully corrective version (Jaggi, 2013) of the Frank-Wolfe algorithm (hereafter referred as FCFW).”
Block-Coordinate Frank-Wolfe Optimization for Structural SVMs (2012, methodology): “In terms of convergence, it is known that after O(1/ε) iterations, Algorithm 1 obtains an ε-approximate solution (Frank & Wolfe, 1956; Dunn & Harshbarger, 1978) as well as a guaranteed ε-small duality gap (Clarkson, 2010; Jaggi, 2013), along with a certificate to (5).”
Weakly Supervised Action Labeling in Videos under Ordering Constraints (2014, methodology): “It has recently received increased attention in the context of large-scale optimization [11,17].”
Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs (2019, methodology): “We propose a decentralized algorithm based on FrankWolfe (FW) (Frank and Wolfe, 1956; Jaggi, 2013), also known as conditional gradient descent.”
Filtering with State-Observation Examples via Kernel Monte Carlo Filter (2013, methodology): “ the fact (Bach et al., 2012) that Kernel Herding can be seen as the Frank-Wolfe optimization method with step size 1=(‘+ 1) for the ‘-th iteration. For details of the Frank-Wolfe method, we refer to Jaggi (2013); Freund and Grigas (2014) and references therein. Fix the samples Z 1;:::;Z N. Let M Nb”
Introduction to Online Convex Optimization (2016, methodology): “Due to the applicability of the FW algorithm to large-scale constrained problems, it has been a method of choice in recent machine learning applications, to name a few: (61; 69; 60; 39; 50; 58; 98; 16; 104; 46; 47; 18).”
Breaking the Curse of Dimensionality with Convex Neural Networks (2014, background): “Conditional gradient algorithms allow to incrementally build a set of elements of Fδ1 = {f ∈ F1, γ1(f) 6 δ}; see, e.g., Frank and Wolfe (1956); Dem’yanov and Rubinov (1967); Dudik et al. (2012); Harchaoui et al. (2013); Jaggi (2013); Bach (2014).”
On the Global Linear Convergence of Frank-Wolfe Optimization Variants (2015, methodology): “Here the linear dependence on d should not come as a surprise, in view of the known lower bound of 1/t for t ≤ d for Frank-Wolfe type methods [15].”
Towards Practical Differentially Private Convex Optimization (2019, methodology): “Following the advice of [26], we use a decreasing learning rate for better accuracy guarantees.”
On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport (2018, background): “This approach tackles a variant of (1) where the regularization term is replaced by an upper bound on the total variation norm; the associated constraint set is the convex hull of all Diracs and negatives of Diracs at elements of θ ∈ Θ, and thus adapted to conditional gradient algorithms [19].”
Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals (2018, background): “The computational complexity of rate constraints makes them generally unattractive to try to optimize with approaches that require projections, such as projected SGD, or optimization of constrained subproblems, such as Frank-Wolfe (Hazan and Kale, 2012; Jaggi, 2013; Garber and Hazan, 2013)).”