Efficient Mixed-Norm Regularization: Algorithms and Safe Screening Methods

摘要: Sparse learning has recently received increasing attention in many areas including machine learning, statistics, and applied mathematics. The mixed-norm regularization based on the l1/lq norm with q > 1 is attractive applications of regression classification that it facilitates group sparsity model. resulting optimization problem is, however, challenging to solve due inherent structure l1/lq-regularization. Existing work deals special cases = 2,∞, they can not be easily extended general case. In this paper, we propose an efficient algorithm accelerated gradient method for solving l1/lq-regularized problem, which applicable all values larger than 1, thus significantly extending existing work. One key building block proposed Euclidean projection (EP1q). Our theoretical analysis reveals properties EP1q illustrates why more cases. Based our analysis, develop by two zero finding problems. To further improve efficiency large dimensional regularized problems, effective “screening” able quickly identify inactive groups, i.e., groups have 0 components solution. This may lead substantial reduction number entered optimization. An appealing feature screening data set needs scanned only once run screening. Compared computational cost test negligible. accurate sensitivity dual optimal solution when parameter varies. Experimental results demonstrate algorithm.