Back to Search
Start Over
Frank-Wolfe Methods with an Unbounded Feasible Region and Applications to Structured Learning
- Publication Year :
- 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 $\ell_1$ 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 $O(1/k)$ 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.<br />Comment: 31 pages, 6 figures
- Subjects :
- Mathematics - Optimization and Control
90C25, 90C06, 90C90
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2012.15361
- Document Type :
- Working Paper