Towards Structural Sparsity: An Explicit l2/l0 Approach

In many cases of machine learning or data mining applications, we are not only aimed to establish accurate 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 ℓ₂/ℓ₁ norms. In this paper, we present the explicit ℓ₂/ℓ₀ norm to directly achieve structural sparsity. To tackle the problem of intractable ℓ₂/ℓ₀ 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.