In many cases of machine learning or data mining applications, we are not only aimed to establish accurate {\em black box} predictors, we are also interested in discovering predictive patterns in data which enhance our interpretation and understanding of underlying physical, biological and other natural processes. Sparse representation is one of the focuses in this direction. More recently, structural sparsity has attracted increasing attentions. The structural sparsity is often achieved by imposing l2/l1 norms. In this paper, we present the explicit l2/l0 norm to directly achieve structural sparsity. To tackle the problem of intractable l2/l0 optimization, we develop a general Lipschitz auxiliary function which leads to simple iterative algorithms. In each iteration, optimal solution is achieved for the induced sub-problem and a guarantee of convergence is provided. Further more, the local convergent rate is also theoretically bounded. We test our optimization techniques in the multi-task feature learning problem. Experimental results suggest that our approaches outperform other approaches in both synthetic and real world data sets.
['Dijun Luo', 'Chris H. Q. Ding', 'Heng Huang']
Towards Structural Sparsity: An Explicit l2/l0 Approach