Projection-free methods for data segmentation problems

Data segmentation represents a challenging task in modern machine learning. In many real-world applications, data are naturally structured as graphs and labeled data are often expensive to obtain, motivating the use of graph-based semi-supervised learning techniques. Existing methods inspired by fluid dynamics and materials science minimize a graph-based Ginzburg–Landau functional, but require expensive graph Laplacian eigendecompositions and repeated projections onto the unit simplex, making them impractical for very large datasets. A recent work proposed a new penalty-based reformulation, combined with an efficient eigendecomposition and projection-free optimization scheme, based on a tailored variant of the classic Frank-Wolfe method. In this thesis we propose block-coordinate variants of the Frank-Wolfe scheme to reduce the computational burden, while achieving a similar convergence rate. Additionally, we analyze an inference-based approach to the problem. We test the proposed methods on artificial and real-world networks, showing their effectiveness.