Sparse Learning Via Relaxation And Rounding

Due to its simplicity and computational advantages,sparse learning is an essential topic in machine learning.Generally speaking,sparse learning problem can be regard as the best subset selection problem,which is a NP-Complete problem.Most of the existing works are based on heuristic rules or use regular terms to get approximation solution.However,those methods are lack of corresponding theoretical guarantee and can't effectively control the trade-off between the sparsity and the accuracy.The relax-ation and rounding method is a powerful algorithmic technique that has proved to be extremely useful for a wide variety of problems in the area of approximation algorithms designing for NP-hard problems.This paper extend the relaxation and rounding method to the setting of sparse learning problems,propose a new sparse learning method via re-laxation and rounding.The main contributions of this paper are as follows:1.Reformulating the sparse learning problem.Firstly we reformulate the sparse learning problem to a subset selection problem with to penalty.Then by intro-ducing Boolean variables,we rewrite it as a mixed integer program with l1 of Boolean variables exactly.2.Proposing a new approximation method of l₀ norm and show its applicability to linear models and deep models.3.Giving the theoretical analysis of the proposed method,consisting of the theo-retical error bound and time complexity analysis of the proposed method.The proposed method can get a sparse solution while learning.Comparing with the existing works,the proposed method has probable theoretical guarantee,can effectively control the trade-off between the sparsity and the accuracy and has strong scalability.