A computational analysis of projection-free methods

Constrained optimization problems arise in many applications. From engineering to machine learning, from the study of biological system to the analysis of networks, many problems can be expressed as the minimization of a objective function on a feasible region. The feasible region can be quite hard to handle. Hence, finding the projection of a vector on it may not be practical. Projection-free methods are aimed at solving the minimization problem without the use of the projection on the feasible region. Because of this, projection-free methods are well suited to handle structured constraints and have recently become popular in machine learning applications.The most known projection-free method is the Frank-Wolfe algorithm, many variants of which have been proposed to ensure fast convergence rate towards a solution. A reason that slows down Frank-Wolfe variants is the presence of “short” steps during which the iterate stops at the frontier of the feasible region. Rinaldi and Zeffiro proposed a SSC framework for Frank-Wolfe’s variants that addresses this issue. We implement two Frank-Wolfe ariants(namely, the Away-step Frank-Wolfe and Pairwise Frank-Wolfe), in both a classic way and with the new framework. Thereafter, we benchmarked every variant against two cluster detection problems in networks: maximum clique problem and maximum s-defective clique problem Our goal is to perform a numerical analysisof the actual improvements brought by the SSC framework.