Conditional gradient algorithms with open loop step size rules

By J. Dunn, P. Lax. 1978

In Ref. [l], Demyanov and Rubinov analyze a general iterative process for minimizing a smooth convex functional f over a bounded convex set 52 in a Banach space. At each stage in this process, the original minimization problem is replaced by a (presumably) simpler problem in which the local linear approximation to f, specified by f’s derivative at the current iterate x, in 9, is minimized over 9. Every solution yn of the latter problem yields a descent direction vector P, =Yn-XXn’ and the next iterate x,+r is then gotten by moving a certain distance from x, in the direction p, , after which the whole cycle is repeated. Demyanov and Rubinov refer to this procedure as the conditional gradient method and it does indeed resemble the classical gradient method for minimizing f over the entire space X (in the latter case, p, is obtained by minimizing the local linear approximation to f at x, over the unit ball with center x, , as in Kantorovich [2]). Both methods are formally applicable to nonconvex functionals, however in such cases the resulting iterates may renderf “stationary” in a certain sense [I] without achieving a global minimum over 9. A precursor of the general conditional gradient method appears in a paper by Prank and Wolfe [3] on quadratic programming problems in finite dimensional spaces. Variants of this basic procedure have since been rediscovered and analyzed by many workers, mainly in the context of optimal control theory (cf. Kelley [4], Gilbert [5], Gilbert and Barr [6], Barr [7], Barnes [S], Meyer [9], Pecsvaradi [IO], Dunn [Ill, Dunn and Kumar [12], and Kumar [13]); the method is especially interesting in this setting because it is effective on problems

Subfields: 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 Optimization & Training

Citations in the corpus

Block-Coordinate Frank-Wolfe Optimization for Structural SVMs (2012, methodology): “We apply the known convergence results for the standard Frank-Wolfe Algorithm 1, as given e.g. in (Frank & Wolfe, 1956; Dunn & Harshbarger, 1978; Jaggi, 2013), or as given in the paragraph just after the proof of Theorem C.1: For each k ≥ 1, the iterate α(k) of Algorithm 1 (either using the…”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, background): “The first is to take ρt−1 = 2/(t + 1) [62, 108], while the second one is to perform a line search on the quadratic upper-bound on g obtained from the L-Lipschitz continuity of g (see §7.”
New analysis and results for the Frank–Wolfe method (2013, methodology): “The original Frank–Wolfe method, developed for smooth convex optimization on a polytope, dates back to Frank andWolfe [9], andwas generalized to the more general smooth convex objective function over a bounded convex feasible region thereafter, see for example Demyanov and Rubinov [3], Dunn and Hars”
Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization (2013, background): “In terms of conver- gence, it is known that the iterates of Algorithm 1 satisfy f (x (k) ) − f (x * ) ≤ O 1 k , for x * being an optimal solution to (1) (Frank & Wolfe, 1956; Dunn & Harshbarger , 1978).”
Solving variational inequalities with monotone operators on domains given by Linear Minimization Oracles (2013, background): “…in this line of research is on smooth/smooth norm-regularized convex minimization [11,13,14,16,17,31], where the main “working horse” is the classical Conditional Gradient (a.k.a. Frank-Wolfe) algorithm originating from [12] and intensively studied in 1970’s (see [9,10,28] and references therein).”
Linearly convergent away-step conditional gradient for non-strongly convex functions (2015, methodology): “The algorithm is guaranteed to have an O( 1 k ) rate of convergence for stepsize determined according to exact line search [8], adaptive stepsize [18], which has a closed form when the smoothness constant of the objective function is known, and predetermined stepsize [6].”
Convex Optimization: Algorithms and Complexity (2014, methodology): “The following result is extracted from Jaggi [2013] (see also Dunn and Harshbarger [1978]).”
On the Effectiveness of Richardson Extrapolation in Machine Learning (2020, unknown): “While some form of line search can be used to ﬁnd ρ k , we consider so-called “open loop” schemes where ρ k = 1 /k or ρ k = 2 / ( k + 1) (Dunn and Harshbarger, 1978; Jaggi, 2013).”
The Cyclic Block Conditional Gradient Method for Convex Optimization Problems (2015, methodology): “We provide a sublinear global convergence rate estimates for a the predeﬁned stepsize strategy [13, 17] and an adaptive stepsize strategy [21].”
Convergence Properties of Feasible Descent Methods for Solving Variational Inequalities in Banach Spaces (1998, methodology): “It is well known that the problem (71) is equivalent to the variational inequality problem 〈f ′(x∗), x− x∗〉 ≥ 0∀x ∈ C. (72) Descent methods for solving optimization problems in infinite dimensional spaces have been addressed by several researchers, including Auslender [1], Valadier [16] and Dunn [4]”
Decomposition Techniques for Bilinear Saddle Point Problems and Variational Inequalities with Affine Monotone Operators (2015, methodology): “…this activity was focused on smooth (or Lasso-type smooth regularized) Convex Minimization over LMO-represented domains, where the classical Conditional Gradient algorithm of Frank & Wolfe [7] and its modiﬁcations are applicable (see, e.g., [5, 6, 8, 9, 13, 14, 15, 16, 21] and references therein).”