Search

The Frank--Wolfe 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 l1 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, the unbounded Frank--Wolfe method and the unbounded away-step Frank--Wolfe method, 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 an O(1/k) sublinear convergence rate, and the 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. [ABSTRACT FROM AUTHOR]

The Gradient Boosting Machine (GBM) introduced by Friedman [J. H. Friedman, Ann. Statist., 29 (2001), pp. 1189-1232] is a powerful supervised learning algorithm that is very widely used in practice--it routinely features as a leading algorithm in machine learning competitions such as Kaggle and the KDDCup. In spite of the usefulness of GBM in practice, our current theoretical understanding of this method is rather limited. In this work, we propose the Randomized Gradient Boosting Machine (RGBM), which leads to substantial computational gains compared to GBM by using a randomization scheme to reduce search in the space of weak learners. We derive novel computational guarantees for RGBM. We also provide a principled guideline towards better step-size selection in RGBM that does not require a line search. Our proposed framework is inspired by a special variant of coordinate descent that combines the benefits of randomized coordinate descent and greedy coordinate descent, and may be of independent interest as an optimization algorithm. As a special case, our results for RGBM lead to superior computational guarantees for GBM. Our computational guarantees depend upon a curious geometric quantity that we call the Minimal Cosine Angle, which relates to the density of weak learners in the prediction space. On a series of numerical experiments on real datasets, we demonstrate the effectiveness of RGBM over GBM in terms of obtaining a model with good training and/or testing data fidelity with a fraction of the computational cost. [ABSTRACT FROM AUTHOR]

Motivated principally by the low-rank matrix completion problem, we present an extension of the Frank-Wolfe method that is designed to ind uce near-optimal solutions on lowdimensional faces of the feasible region. This is accomplished by a new approach to generating "in-face" directions at each iteration, as well as through new choice rules for selecting between inface and "regular" Frank-Wolfe steps. Our framework for generating in-face directions generalizes the notion of away steps introduced by Wolfe. In particular, the in-face directions always keep the next iterate within the minimal face containing the current iterate. We present computational guarantees for the new method that trade off efficiency in computing near-optimal solutions with upper bounds on the dimension of minimal faces of iterates. We apply the new method to the matrix completion problem, where low-dimensional faces correspond to low-rank matrices. We present computational results that demonstrate the effectiveness of our methodological a pproach at producing nearly optimal solutions of very low rank. On both artificial and real datasets, we demonstrate significant speedups in computing very low rank nearly optimal solutions as compared to the Frank-Wolfe method (as well as several of its significant variants). [ABSTRACT FROM AUTHOR]