Screening Rules and its Complexity for Active Set Identification
arXiv:2009.02709
Abstract
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.
References in corpus (17)
- Discussion of "Least angle regression" by Efron et al
- Rejoinder to "Least angle regression" by Efron et al
- Least Angle Regression
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Safe Feature Elimination in Sparse Supervised Learning
- A Safe Screening Rule for Sparse Logistic Regression
- GAP Safe Screening Rules for Sparse-Group-Lasso
- GAP Safe screening rules for sparse multi-task and multi-class models
- Simultaneous Safe Screening of Features and Samples in Doubly Sparse Modeling
- Screening Rules for Lasso with Non-Convex Sparse Regularizers
- Dual Extrapolation for Sparse Generalized Linear Models