Analysis of Multi-stage Convex Relaxation for Sparse Regularization

Tong Zhang; 11(Mar):1081−1107, 2010.

Abstract

We consider learning formulations with non-convex objective functions that often occur in practical applications. There are two approaches to this problem: This paper tries to remedy the above gap between theory and practice. In particular, we present a multi-stage convex relaxation scheme for solving problems with non-convex objective functions. For learning formulations with sparse regularization, we analyze the behavior of a specific multi-stage relaxation scheme. Under appropriate conditions, we show that the local solution obtained by this procedure is superior to the global solution of the standard L1 convex relaxation for learning sparse targets.

[abs][pdf]




Home Page

Papers

Submissions

News

Editorial Board

Announcements

Proceedings

Open Source Software

Search

Statistics

Login

Contact Us



RSS Feed