Practical Frank-Wolfe algorithms
share
In the last decade there has been a resurgence of interest in Frank-Wolfe (FW) style methods for optimizing a smooth convex function over a polytope. Examples of recently developed techniques include Decomposition-invariant Conditional Gradient (DiCG), Blended Condition Gradient (BCG), and Frank-Wolfe with in-face directions (IF-FW) methods. We introduce two extensions of these techniques. First, we augment DiCG with the working set strategy, and show how to optimize over the working set using shadow simplex steps. Second, we generalize in-face Frank-Wolfe directions to polytopes in which faces cannot be efficiently computed, and also describe a generic recursive procedure that can be used in conjunction with several FW-style techniques. Experimental results indicate that these extensions are capable of speeding up original algorithms by orders of magnitude for certain applications.
READ FULL TEXT