Rates of convergence for conditional gradient algorithms near singular and nonsingular extremals

By J. Dunn. 1979

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, methodology): “…c over the constraint set (i.e., the constraints are active), the Frank-Wolfe algorithm 1 converges linearly [Levitin et al. 1966; Demyanov et al. 1970; Dunn 1979], at rate (cid:0) (cid:1) Note that assuming the gradient to be lower bounded means the constraints are tight, i.e., the solution of…”
Frank-Wolfe Algorithms for Saddle Point Problems (2016, background): “Frank-Wolfe for convex optimization over strongly convex sets has been studied by Levitin and Polyak (1966); Demyanov and Rubinov (1970) and Dunn (1979), amongst others.”
On the Global Linear Convergence of Frank-Wolfe Optimization Variants (2015, neutral): “sublinear: f(x(t))−f(x∗) ≤ O ( 1/t ) , for x∗ being an optimal solution [9, 6, 8, 15].”
Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization (2020, background): “Paper Algorithm Steps to get -error Dunn (1979) [26] Geometric analysis for vanilla CG.”
A conditional gradient method with linear rate of convergence for solving convex linear systems (2004, methodology): “, [2, 3, 4, 7]), for convenience and the interested reader on general results for CGM, we have given in an appendix compact proofs.”
Linear Bandits on Uniformly Convex Sets (2021, unknown): “Such observations have already been made, e.g. , in constrained optimization [Pol66; DR70; Dun79; KdP21b; Ker+20], when the sets’ α -strong convexity leads to linear convergence rates of the Frank-Wolfe methods with a conditioning on the set that does not depend on the dimension.”
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).”
Curvature of Feasible Sets in Offline and Online Optimization (2020, background): “There has been much interest in the influence of curvature on computational and statistical efficiency in optimization and machine learning, with the use of notions of curvature such as strong convexity and gauge bodies in convex optimization [1, 12, 13, 18, 32], and uniform convexity/martingale-cot”
Convergence Rate of Frank-Wolfe for Non-Convex Objectives (2016, methodology): “Dunn (1979, Note 5.5) generalizes the standard rates for the FW method (in terms of global suboptimality) when running it on a class of quasi-convex functions of the form: f ( x ) := h ( G ( x )) where h : R → R is a strictly increasing real function with a continuous derivative, and G : R d → R is…”
Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets (2014, background): “The algorithm implicitly assumes that the convex set K is given in terms of a linear optimization oracle O K : E → K which given a linear objective c ∈ E returns a point x = O K ( c ) ∈ K such that x ∈ arg min y ∈K y · c .”
Projection-Free Optimization on Uniformly Convex Sets (2020, methodology): “…analyses of the simple Follow-The-Leader (FTL) for online linear optimization (Huang et al., 2016) is analogous to the oﬄine convergence analyses of the Frank-Wolfe algorithm when not assuming strong-convexity of the objective function as in (Polyak, 1966; Demyanov and Rubinov, 1970; Dunn, 1979).”
Revisiting Projection-Free Optimization for Strongly Convex Constraint Sets (2018, background): “Prior work (Levitin and Polyak 1966; Demyanov and Ru-binov 1970; Dunn 1979) shows that standard FW without line search for smooth functions can achieve an exponential convergence rate, by making a strict assumption that the gradient is lower-bounded everywhere in the feasible set.”
New analysis and results for the Frank–Wolfe method (2013, methodology): “And in prior work, Dunn [6] presents convergence and computational guarantees for the case when the step-size ᾱk is determined from the structure of the lower quadratic approximation of h(·) in (7), if the curvature constant Ch,Q is known or upper-bounded.”
Frank-Wolfe Method is Automatically Adaptive to Error Bound Condition (2018, background): “…special cases, a series of works tried 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…”