Screening Rules for Lasso with Non-Convex Sparse Regularizers

Feb 19, 2019

Alain Rakotomamonjy, Gilles Gasso, Joseph Salmon

Leveraging on the convexity of the Lasso problem , screening rules help in accelerating solvers by discarding irrelevant variables, during the optimization process. However, because they provide better theoretical guarantees in identifying relevant variables, several non-convex regularizers for the Lasso have been proposed in the literature. This work is the first that introduces a screening rule strategy into a non-convex Lasso solver. The approach we propose is based on a iterative majorization-minimization (MM) strategy that includes a screening rule in the inner solver and a condition for propagating screened variables between iterations of MM. In addition to improve efficiency of solvers, we also provide guarantees that the inner solver is able to identify the zeros components of its critical point in finite time. Our experimental analysis illustrates the significant computational gain brought by the new screening rule compared to classical coordinate-descent or proximal gradient descent methods.
Feb 19, 2019

Alain Rakotomamonjy, Gilles Gasso, Joseph Salmon

**Click to Read Paper and Get Code**

Celer: a Fast Solver for the Lasso with Dual Extrapolation

Jun 06, 2018

Mathurin Massias, Alexandre Gramfort, Joseph Salmon

Jun 06, 2018

Mathurin Massias, Alexandre Gramfort, Joseph Salmon

**Click to Read Paper and Get Code**

From safe screening rules to working sets for faster Lasso-type solvers

May 01, 2017

Mathurin Massias, Alexandre Gramfort, Joseph Salmon

May 01, 2017

Mathurin Massias, Alexandre Gramfort, Joseph Salmon

**Click to Read Paper and Get Code**

Mind the duality gap: safer rules for the Lasso

Dec 03, 2015

Olivier Fercoq, Alexandre Gramfort, Joseph Salmon

Screening rules allow to early discard irrelevant variables from the optimization in Lasso problems, or its derivatives, making solvers faster. In this paper, we propose new versions of the so-called $\textit{safe rules}$ for the Lasso. Based on duality gap considerations, our new rules create safe test regions whose diameters converge to zero, provided that one relies on a converging solver. This property helps screening out more variables, for a wider range of regularization parameter values. In addition to faster convergence, we prove that we correctly identify the active sets (supports) of the solutions in finite time. While our proposed strategy can cope with any solver, its performance is demonstrated using a coordinate descent algorithm particularly adapted to machine learning use cases. Significant computing time reductions are obtained with respect to previous safe rules.
Dec 03, 2015

Olivier Fercoq, Alexandre Gramfort, Joseph Salmon

* erratum to ICML 2015, "The authors would like to thanks Jalal Fadili and Jingwei Liang for helping clarifying some misleading statements on the equicorrelation set"

**Click to Read Paper and Get Code**

Optimal mini-batch and step sizes for SAGA

Jan 31, 2019

Nidham Gazagnadou, Robert M. Gower, Joseph Salmon

Recently it has been shown that the step sizes of a family of variance reduced gradient methods called the JacSketch methods depend on the expected smoothness constant. In particular, if this expected smoothness constant could be calculated a priori, then one could safely set much larger step sizes which would result in a much faster convergence rate. We fill in this gap, and provide simple closed form expressions for the expected smoothness constant and careful numerical experiments verifying these bounds. Using these bounds, and since the SAGA algorithm is part of this JacSketch family, we suggest a new standard practice for setting the step sizes and mini-batch size for SAGA that are competitive with a numerical grid search. Furthermore, we can now show that the total complexity of the SAGA algorithm decreases linearly in the mini-batch size up to a pre-defined value: the optimal mini-batch size. This is a rare result in the stochastic variance reduced literature, only previously shown for the Katyusha algorithm. Finally we conjecture that this is the case for many other stochastic variance reduced methods and that our bounds and analysis of the expected smoothness constant is key to extending these results.
Jan 31, 2019

Nidham Gazagnadou, Robert M. Gower, Joseph Salmon

* 34 pages, 27 figures

**Click to Read Paper and Get Code**

A two-stage denoising filter: the preprocessed Yaroslavsky filter

Aug 31, 2012

Joseph Salmon, Rebecca Willett, Ery Arias-Castro

Aug 31, 2012

Joseph Salmon, Rebecca Willett, Ery Arias-Castro

**Click to Read Paper and Get Code**

Oracle inequalities and minimax rates for non-local means and related adaptive kernel-based methods

Apr 26, 2012

Ery Arias-Castro, Joseph Salmon, Rebecca Willett

This paper describes a novel theoretical characterization of the performance of non-local means (NLM) for noise removal. NLM has proven effective in a variety of empirical studies, but little is understood fundamentally about how it performs relative to classical methods based on wavelets or how various parameters (e.g., patch size) should be chosen. For cartoon images and images which may contain thin features and regular textures, the error decay rates of NLM are derived and compared with those of linear filtering, oracle estimators, variable-bandwidth kernel methods, Yaroslavsky's filter and wavelet thresholding estimators. The trade-off between global and local search for matching patches is examined, and the bias reduction associated with the local polynomial regression version of NLM is analyzed. The theoretical results are validated via simulations for 2D images corrupted by additive white Gaussian noise.
Apr 26, 2012

Ery Arias-Castro, Joseph Salmon, Rebecca Willett

* 49 pages, 15 figures

**Click to Read Paper and Get Code**

Dual Extrapolation for Sparse Generalized Linear Models

Jul 12, 2019

Mathurin Massias, Samuel Vaiter, Alexandre Gramfort, Joseph Salmon

Jul 12, 2019

Mathurin Massias, Samuel Vaiter, Alexandre Gramfort, Joseph Salmon

**Click to Read Paper and Get Code**

Concomitant Lasso with Repetitions (CLaR): beyond averaging multiple realizations of heteroscedastic noise

Feb 07, 2019

Quentin Bertrand, Mathurin Massias, Alexandre Gramfort, Joseph Salmon

Feb 07, 2019

Quentin Bertrand, Mathurin Massias, Alexandre Gramfort, Joseph Salmon

**Click to Read Paper and Get Code**

Gap Safe screening rules for sparsity enforcing penalties

Dec 27, 2017

Eugene Ndiaye, Olivier Fercoq, Alexandre Gramfort, Joseph Salmon

Dec 27, 2017

Eugene Ndiaye, Olivier Fercoq, Alexandre Gramfort, Joseph Salmon

**Click to Read Paper and Get Code**

Generalized Concomitant Multi-Task Lasso for sparse multimodal regression

Oct 18, 2017

Mathurin Massias, Olivier Fercoq, Alexandre Gramfort, Joseph Salmon

Oct 18, 2017

Mathurin Massias, Olivier Fercoq, Alexandre Gramfort, Joseph Salmon

**Click to Read Paper and Get Code**

On the benefits of output sparsity for multi-label classification

Mar 14, 2017

Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Joseph Salmon

Mar 14, 2017

Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Joseph Salmon

**Click to Read Paper and Get Code**

Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions

Jun 08, 2016

Igor Colin, Aurélien Bellet, Joseph Salmon, Stéphan Clémençon

Jun 08, 2016

Igor Colin, Aurélien Bellet, Joseph Salmon, Stéphan Clémençon

**Click to Read Paper and Get Code**

GAP Safe Screening Rules for Sparse-Group-Lasso

Feb 19, 2016

Eugene Ndiaye, Olivier Fercoq, Alexandre Gramfort, Joseph Salmon

Feb 19, 2016

Eugene Ndiaye, Olivier Fercoq, Alexandre Gramfort, Joseph Salmon

**Click to Read Paper and Get Code**

GAP Safe screening rules for sparse multi-task and multi-class models

Nov 18, 2015

Eugene Ndiaye, Olivier Fercoq, Alexandre Gramfort, Joseph Salmon

Nov 18, 2015

Eugene Ndiaye, Olivier Fercoq, Alexandre Gramfort, Joseph Salmon

* in Proceedings of the 29-th Conference on Neural Information Processing Systems (NIPS), 2015

**Click to Read Paper and Get Code**

Extending Gossip Algorithms to Distributed Estimation of U-Statistics

Nov 17, 2015

Igor Colin, Aurélien Bellet, Joseph Salmon, Stéphan Clémençon

Nov 17, 2015

Igor Colin, Aurélien Bellet, Joseph Salmon, Stéphan Clémençon

* to be presented at NIPS 2015

**Click to Read Paper and Get Code**

Adaptive Multinomial Matrix Completion

Aug 26, 2014

Olga Klopp, Jean Lafond, Eric Moulines, Joseph Salmon

Aug 26, 2014

Olga Klopp, Jean Lafond, Eric Moulines, Joseph Salmon

**Click to Read Paper and Get Code**

Characterizing the maximum parameter of the total-variation denoising through the pseudo-inverse of the divergence

Dec 08, 2016

Charles-Alban Deledalle, Nicolas Papadakis, Joseph Salmon, Samuel Vaiter

Dec 08, 2016

Charles-Alban Deledalle, Nicolas Papadakis, Joseph Salmon, Samuel Vaiter

**Click to Read Paper and Get Code**

Poisson noise reduction with non-local PCA

Apr 28, 2014

Joseph Salmon, Zachary Harmany, Charles-Alban Deledalle, Rebecca Willett

Apr 28, 2014

Joseph Salmon, Zachary Harmany, Charles-Alban Deledalle, Rebecca Willett

* erratum: Image man is wrongly name pepper in the journal version

**Click to Read Paper and Get Code**

Learning Heteroscedastic Models by Convex Programming under Group Sparsity

Apr 16, 2013

Arnak S. Dalalyan, Mohamed Hebiri, Katia Méziani, Joseph Salmon

Apr 16, 2013

Arnak S. Dalalyan, Mohamed Hebiri, Katia Méziani, Joseph Salmon

* Proceedings of the 30 th International Conference on Machine Learning (2013) http://icml.cc/2013/?page_id=43

**Click to Read Paper and Get Code**