Convergence analysis and active set complexity for some FW variants

*The FW method, first introduced in 1956 by Marguerite Frank and Philip Wolfe, has recently been the subject of renewed interest thanks to its many applications in machine learning. In this thesis we prove convergence and active set identification properties for some popular variations of this method. While the classic FW method has a slow O(1/t)** convergence rate even for strongly convex objectives, i* *t has recently been proved that some FW variants on polytopes have faster convergence rates assuming an Holderian error bound condition which generalizes strong convexity. In this thesis we prove that for one of these variants this acceleration of the convergence rate can be extended also to a class of non polyhedral sets, including strictly convex smooth convex sets whose boundary satisfies some positive curvature property. We also prove that under suitable assumptions some FW variants on polytopes identify the active set in finite time. This result extends an analogous well known result proved for projected gradient methods. To prove our result however we use a fundamentally different technique, relating the identification property to active set identification strategies with Lagrange multipliers. Other minor results of the thesis include a proof of finite time active set identification for the pairwise step FW variant, a new proof for the projected gradient finite time active set identification property with explicit estimates, and a generalization of some of the convergence rate results to reflexive Banach spaces. *