Frank-Wolfe Method is Automatically Adaptive to Error Bound Condition

By Yi Xu, Tianbao Yang. 2018

13 citations recorded by the source corpus.

Error bound condition has recently gained revived interest in optimization. It has been leveraged to derive faster convergence for many popular algorithms, including subgradient methods, proximal gradient method and accelerated proximal gradient method. However, it is still unclear whether the Frank-Wolfe (FW) method can enjoy faster convergence under error bound condition. In this short note, we give an affirmative answer to this question. We show that the FW method (with a line search for the step size) for optimization over a strongly convex set is automatically adaptive to the error bound condition of the problem. In particular, the iteration complexity of FW can be characterized by $O(\max(1/\epsilon^{1-\theta}, \log(1/\epsilon)))$ where $\theta\in[0,1]$ is a constant that characterizes the error bound condition. Our results imply that if the constrained set is characterized by a strongly convex function and the objective function can achieve a smaller value outside the considered domain, then the FW method enjoys a fast rate of $O(1/t^2)$.

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

Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, background): “H¨olderian Error Bounds on f [Kerdreux et al. 2018a; Xu et al. 2018; Rinaldi et al. 2020] or local uniform convexity of C [Kerdreux et al. 2020].”
A unifying framework for the analysis of projection-free first-order methods under a sufficient slope condition (2020, background): “, [29], [45]) under Hölderian error bound conditions, to interpolate between the well known O(1/k) rate for general convex objectives and the faster rates for strongly convex ones proved in [19] and [30].”
Projection-Free Optimization on Uniformly Convex Sets (2020, background): “A quantitative statement is, for instance, given in (Xu and Yang, 2018, proof of Theorem 1.) that we reproduce here.”