Frank-Wolfe Methods with an Unbounded Feasible Region and Applications to Structured Learning
From MaRDI portal
Publication:6357250
DOI10.1137/20M1387869arXiv2012.15361MaRDI QIDQ6357250FDOQ6357250
Authors: Haoyue Wang, Haihao Lu, Rahul Mazumder 
Publication date: 30 December 2020
Abstract: The Frank-Wolfe (FW) method is a popular algorithm for solving large-scale convex optimization problems appearing in structured statistical learning. However, the traditional Frank-Wolfe method can only be applied when the feasible region is bounded, which limits its applicability in practice. Motivated by two applications in statistical learning, the trend filtering problem and matrix optimization problems with generalized nuclear norm constraints, we study a family of convex optimization problems where the unbounded feasible region is the direct sum of an unbounded linear subspace and a bounded constraint set. We propose two new Frank-Wolfe methods: unbounded Frank-Wolfe method (uFW) and unbounded Away-Step Frank-Wolfe method (uAFW), for solving a family of convex optimization problems with this class of unbounded feasible regions. We show that under proper regularity conditions, the unbounded Frank-Wolfe method has a sublinear convergence rate, and unbounded Away-Step Frank-Wolfe method has a linear convergence rate, matching the best-known results for the Frank-Wolfe method when the feasible region is bounded. Furthermore, computational experiments indicate that our proposed methods appear to outperform alternative solvers.
Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Semidefinite programming (90C22) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
This page was built for publication: Frank-Wolfe Methods with an Unbounded Feasible Region and Applications to Structured Learning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6357250)
