Feature selection for high-dimensional sparse feature space is an open issue for machine learning research

prevalent 1-norm regularization approaches share some theoretical drawbacks

such as lack the ability to select out grouped features

and can not select more features than the sample size.This paper considers the sparse modeling problem from the stochastic complexity theory perspective

and derive an easy computable model from its Minimax bound approximation.The proposed approach is proved to be optimized

and can perform automatic feature selection similar to its 1-norm penalized alternatives

but overcome their drawbacks.Furthermore

it does not rely on any parametric assumptions about the true data-generating mechanism

which makes it broadly applicable.Various simulations performed with both synthetic and real biological data show that the proposed approach performs similarly to the popular 1-norm penalized counterparts in ordinary experimental setups

and outperforms the other methods in robustness and predictive accuracy for extremely sparse problems.