Screening Rules and its Complexity for Active Set Identification

2020/09/06 by Eugène Ndiaye, Ndiaye, Eugene, Olivier Fercoq +3 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Neural Networks and Applications #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2009.02709

openalex publication_date 2020/09/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• A Sparse-Group Lasso
• Rejoinder to "Least angle regression" by Efron et al
• Fast projection onto the simplex and the \pmb l_\mathbf 1 l 1 ball
• GAP Safe Screening Rules for Sparse-Group-Lasso
• Dual Extrapolation for Sparse Generalized Linear Models

Cited by

• El0ps: An Exact L0-regularized Problems Solver

Related

• Active set complexity of the Away-step Frank-Wolfe Algorithm
• Screening for Sparse Online Learning
• Active learning to optimise time-expensive algorithm selection
• Safe Screening Rules for Generalized Double Sparsity Learning
• Optimality, identifiability, and sensitivity