From Gap safe rules to working sets for faster sparse solvers, Talk by Alexandre Gramfort
On November 15th Alexandre Gramfort, Researcher at INRIA, will give a talk entitled “From Gap safe rules to working sets for faster sparse solvers”. This will take place at 10am in Soda Hall, room 405.
Abstract. Convex sparsity-promoting regularizations are ubiquitous in modern statistical learning. By construction, they yield solutions with few non-zero coefficients, which correspond to saturated constraints in the dual optimization formulation. Working set (WS) strategies are generic optimization techniques that consist in solving simpler problems that only consider a subset of constraints, whose indices form the WS. Working set methods therefore involve two nested iterations: the outer loop corresponds to the definition of the WS and the inner loop calls a solver for the subproblems. For the Lasso estimator a WS is a set of features, while for a Group Lasso it refers to a set of groups. In practice, WS are generally small in this context so the associated feature Gram matrix can fit in memory. Here we show that the Gauss-Southwell rule (a greedy strategy for block coordinate descent techniques) leads to fast solvers in this case. Combined with a working set strategy based on an aggressive use of so-called Gap Safe screening rules, we propose a solver achieving state-of-the-art performance on sparse learning problems. In this talk I will present results on Lasso and multi-task Lasso estimators on both simulations and neuroscience data, namely on the problem of neural source localization using EEG and MEG data.
Short bio. Alexandre Gramfort is currently a researcher at Inria in the Parietal Team. His work is on statistical machine learning, signal and image processing, optimization, scientific computing and software engineering with primary applications in brain functional imaging (MEG, EEG, fMRI). Before joining Inria, Alexandre was during 5 years assistant professor at Telecom ParisTech in the signal processing and machine learning department and before he was at the Martinos Center for Biomedical Imaging at Harvard University in Boston. He am also an active member of the Center for Data Science at Université Paris-Saclay.
References
Massias, Mathurin, Alexandre Gramfort, and Joseph Salmon. “From safe screening rules to working sets for faster Lasso-type solvers.” arXiv preprint arXiv:1703.07285 (2017) [PDF]
Fercoq, Olivier, Alexandre Gramfort, and Joseph Salmon. “Mind the duality gap: safer rules for the Lasso.” International Conference on Machine Learning. 2015 [PDF]