Multi-Stage Convex Relaxation Methods for Machine Learning
Abstract
Many problems in machine learning can be naturally formulated as non-convex optimization problems. However, such direct nonconvex formulations have been largely replaced by convex relaxation methods (such as support vector machines for classification or L1 regularization for sparse learning) to avoid the usual local optima issues. Many significant theoretical results have been developed in recent years to show that the convex relaxation approach solves the original problem asymptotically. However in practice, the standard simple convex relaxation schemes can be sub-optimal. In the proposed work, we consider a more general framework of multi-stage convex relaxation methods, which remedies the above gap between theory and practice. The method is derived from concave duality, and involves solving a sequence of convex relaxation problems, leading to better and better approximations to the original nonconvex formulation. We will develop theoretical properties of this method and algorithmic consequences. Related convex and nonconvex machine learning methods will also be investigated.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 2013
- Accession Number
- ADA580533
Entities
People
- Tong Zhang
Organizations
- Rutgers University–New Brunswick