Non convex Optimization with Frank Wolfe Algorithm and Its Variants
Recently, Frank Wolfe (a.k.a. conditional gradient) algorithm has become a popular tool for tackling machine learning problems as it avoids the costly projection computation in traditional first order optimization methods. While the Frank Wolfe (FW) algorithm has been extensively studied for convex optimization, little is known for the FW algorithm in non convex optimization. This paper presents a unified convergence analysis for FW algorithm and its variants under the setting of nonconvex but smooth objective with a convex, compact constraint set. Our results are based on a novel observation on the so called Frank Wolfe gap (FW gap) which measures the closeness of solution to a stationary point. With a diminishing step size, we show that the FW gap decays at a rate ofO( 1/t) and the same rate holds for variants of FW such as the online FW algorithm and decentralized FW algorithm. Numerical experiments are shown to support our findings.