Convergence Rates for Conditional Gradient Sequences Generated by Implicit Step Length Rules

By J. Dunn. 1980

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

Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering (2015, background): “…(also called conditional gradient) (Frank and Wolfe, 1956) is a simple ﬁrst-order iterative constrained optimization algorithm for optimizing smooth functions over closed bounded convex sets like M (see Dunn (1980) for its convergence analysis on general inﬁnite dimensional Banach spaces).”
On the Equivalence between Herding and Conditional Gradient Algorithms (2012, neutral): “Without further assumptions on the problem, then the two choices of step sizes lead to a convergence rate of the form (Dunn, 1980; Bach, 2011): where R is diameter of the marginal polytope.”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, background): “, conditional gradient without line search [108, 61], with similar convergence rates and behavior, but sometimes worse empirical peformance.”
A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization (2013, methodology): “1 Introduction First-order optimization methods, such as (sub)gradient-descent methods [35, 29, 30] and conditional-gradient methods [10, 8, 6, 15, 20], are often the method of choice for coping with very large scale optimization tasks.”
Efficient Image and Video Co-localization with Frank-Wolfe Algorithm (2014, background): “Given a convex cost function f and a convex set D, the Frank-Wolfe algorithm [17] finds the global minimum of f over D by solving a succession of linear problems [15, 20].”
The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle (2013, methodology): “The development of LCP methods dates back to the conditional gradient (CndG) method (a.k.a., Frank-Wolfe algorithm) developed by [20] (see also [17,18] for some earlier studies on this area).”
Linearly Convergent Frank-Wolfe with Backtracking Line-Search. (2018, methodology): “In this ﬁ gure we also show the performance of FW, Away-steps FW (AFW) and Pairwise FW (PFW), all of them using the step-size � � , as well as the back-tracking variants of Dunn (1980) and (Beck et al., 2015), which we denote D-FW and B-FW respectively.”
A class of gap functions for variational inequalities (1994, unknown): “See Dunn (1980).3.”
Complexity bounds for primal-dual methods minimizing the model of objective function (2017, background): “Motivation Inthelastyears,wecanseeanincreasinginteresttoFrank–Wolfealgorithm [2,3,12], which sometimes is called Conditional Gradient Method (CGM) [5,8–10].”
Frank-Wolfe Bayesian Quadrature: Probabilistic Integration with Theoretical Guarantees (2015, methodology): “In addition we highlight a robustness property: Even when the assumptions of this section do not hold, one still obtains atleast a rate OP (n−1/2) for the posterior mean using either FWBQ or FWLSBQ [8].”