Beyond GAP screening for Lasso by exploiting new dual cutting half-spaces
- Resource Type
- Conference
- Authors
- Tran, Thu-Le; Elvira, Clement; Dang, Hong-Phuong; Herzet, Cedric
- Source
- 2022 30th European Signal Processing Conference (EUSIPCO) European Signal Processing Conference (EUSIPCO), 2022 30th. :2056-2060 Aug, 2022
- Subject
- Bioengineering
Communication, Networking and Broadcast Technologies
Components, Circuits, Devices and Systems
Computing and Processing
Robotics and Control Systems
Signal Processing and Analysis
Geometry
Europe
Life estimation
Signal processing
Lasso
convex optimization
safe screening
- Language
- ISSN
- 2076-1465
In this paper, we propose a novel safe screening test for Lasso. Our procedure is based on a safe region with a dome geometry and exploits a canonical representation of the set of half-spaces (referred to as “dual cutting half-spaces” in this paper) containing the dual feasible set. The proposed safe region is shown to be always included in the state-of-the-art “GAP Sphere” and “GAP Dome” proposed by Fercoq et al. (and strictly so under very mild conditions) while involving the same computational burden. Numerical experiments confirm that our new dome enables to devise more powerful screening tests than GAP regions and lead to significant acceleration to solve Lasso.