Statistica Sinica 16(2006), 441-457

OPTIMIZING $\mbox{\boldmath $\psi$}$-LEARNING VIA MIXED INTEGER

PROGRAMMING

Yufeng Liu and Yichao Wu

University of North Carolina at Chapel Hill

Abstract: As a new margin-based classifier, $\psi$-learning shows great potential for high accuracy. However, the optimization of $\psi$-learning involves non-convex minimization and is very challenging to implement. In this article, we convert the optimization of $\psi$-learning into a mixed integer programming (MIP) problem. This enables us to utilize the state-of-art algorithm of MIP to solve $\psi$-learning. Moreover, the new algorithm can solve $\psi$-learning with a general piecewise linear $\psi$ loss and does not require continuity of the loss function. We also examine the variable selection property of 1-norm $\psi$-learning and make comparisons with the SVM.

Key words and phrases: Classification, norm, regularization, SVM, variable selection.