Analysis of Multi-stage Convex Relaxation for Sparse Regularization

Tong Zhang

Analysis of Multi-stage Convex Relaxation for Sparse Regularization

Tong Zhang; 11(35):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:

Heuristic methods such as gradient descent that only find a local minimum. A drawback of this approach is the lack of theoretical guarantee showing that the local minimum gives a good solution.
Convex relaxation such as L₁-regularization that solves the problem under some conditions. However it often leads to a sub-optimal solution in reality.

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 L₁ convex relaxation for learning sparse targets.