Screening Rules and its Complexity for Active Set Identification
Screening rules were recently introduced as a technique for explicitly identifying active structures such as sparsity, in optimization problem arising in machine learning. This has led to new methods of acceleration based on a substantial dimension reduction. We show that screening rules stem from a combination of natural properties of subdifferential sets and optimality conditions, and can hence be understood in a unified way. Under mild assumptions, we analyze the number of iterations needed to identify the optimal active set for any converging algorithm. We show that it only depends on its convergence rate.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningDimensionality ReductionSimilar Papers 제목 키워드 기반
Look-Ahead Screening Rules for the Lasso
The lasso is a popular method to induce shrinkage and sparsity in the solution vector (coefficients) of regression problems, particularly when there are many predictors relative to the number of observations. Solving the…
Lasso Screening Rules via Dual Polytope Projection
Lasso is a widely used regression technique to find sparse representations. When the dimension of the feature space and the number of samples are extremely large, solving the Lasso problem remains challenging. To improve…
GAP Safe Screening Rules for Sparse-Group Lasso
For statistical learning in high dimension, sparse regularizations have proven useful to boost both computational and statistical efficiency. In some contexts, it is natural to handle more refined structures than pure sp…
Identification and Estimation of Multidimensional Screening
We study the identification and estimation of a multidimensional screening model, where a monopolist sells a multi-attribute product to consumers with private information about their multidimensional preferences. Under o…
AttributeSafe RuleFit: Learning Optimal Sparse Rule Model by Meta Safe Screening
We consider the problem of learning a sparse rule model, a prediction model in the form of a sparse linear combination of rules, where a rule is an indicator function defined over a hyper-rectangle in the input space. Si…
AllPrediction