LassoNet: A Neural Network with Feature
Sparsity
Ismael Lemhadri
AI at SLAC Seminar

April 2, 2021

Talk Materials at: https://tinyurl.com/lassonet

Joint work withFeng Ruan

Rob Tibshirani

Modern Machine Learning

I Large, complex models
I Massive amounts of data

The ILSVRC Competition

deep learning: applications

healthcare

drug discovery

recommender systems

deep learning: applications

healthcare

drug discovery

recommender systems

Also: gene sequencing, advertisement, speech recognition ...

deep learning: applications

healthcare

drug discovery

recommender systems

Also: gene sequencing, advertisement, speech recognition ...
Deep learning pervades data-rich problems

The age-old problem

Benefits of feature selection

I reduces overfitting
I improves accuracy
I helps overcome the curse of dimensionality
I allows shorter training time
I aids with interpretability

Mice Protein Data
Find proteins that are discriminant between healthy and trisomic
mice. 1080 measurements, 77 proteins.[Higuera et al., 2015]

Best six proteins: AKT, NR2B,TIAM1,nNOS,RRP1,GluR3

Prior art

I Filter and wrapper methods
I Embedded methods

Prior art

I Filter and wrapper methods
I Individual scores [Fisher score, Laplacian Score, Trace Ratio]
I Kernel based methods
I Mutual information based methods [HSIC-Lasso (Yamada etal., 2014), Conditional covariance minimization (Jordan et al.,2018)]

I Embedded methods
I L1-regularization [Lasso (Tibshirani, 1996) and variants]

Desiderata

I Capture arbitrary nonlinearity [nonparametric approach]I Achieve adaptive feature selection

Desiderata

I Capture arbitrary nonlinearity [nonparametric approach]I Achieve adaptive feature selection
Today’s proposal:
I An embedded method
I Optimizes over a large function class
I Obeys a natural hierarchy principle

Appetizer: results on MNIST

Demonstrating LassoNet on MNIST. Simultaneously selecting informative pixels and classifiyng digit 5 vs. digit 6.
Top: The classification accuracy by number of selected features. Bottom: A sample from the model with 160, 220
and 300 active features out of the 784.

The hierarchy principle”Large component main effects
are more likely to lead to appreciable interactions than small components. Also, the interactions
corresponding to larger main effects may be in some sense of
more practical importance.”

David Cox, 1980
Photo: General Motors Cancer Research Foundation

The hierarchy principle”Large component main effects
are more likely to lead to appreciable interactions than small components. Also, the interactions
corresponding to larger main effects may be in some sense of
more practical importance.”

David Cox, 1980
Photo: General Motors Cancer Research Foundation

More recently: Lasso for hierarchical interactions (Bien et al.,2013), reluctant interaction modelling (R.J. Tibshirani, 2019)

Our approach
I An embedded method
I Large function class: residual feedforward neural networksnoF = f : f (x) = θT x + fW (x)LassoNet architectureLassoNet
I Objective function:
minimize L(θ, W ) + λkθk1
θ,Wsubject to kW (0) kj ∞ ≤ M|θj |, j = 1, . . . , d.
where W (0) denotes the network’s input layer.

LassoNet
I Objective function:
minimize L(θ, W ) + λkθk1
θ,Wsubject to kW (0) kj ∞ ≤ M|θj |, j = 1, . . . , d.
where W (0) denotes the network’s input layer.

In particular, Wj = 0 as soon as θj = 0.

LassoNet
I Objective function:
minimize L(θ, W ) + λkθk1
θ,Wsubject to kW (0) kj ∞ ≤ M|θj |, j = 1, . . . , d.
where W (0) denotes the network’s input layer.

In particular, Wj = 0 as soon as θj = 0.
I Hyper-parameters:
I `1 penalty, λ. Higher values of λ encourage sparser models
I Hierarchy parameter, M. Controls the relative strength of the linear and nonlinear
components.

LassoNet Training LoopFeature Selection PathClassification accuracies for LassoNet on a hold-out test-set.
Results on the MICE protein dataset where n = 864, d = 77.

LassoNet Training LoopThe power of warm starts

The power of warm starts

I The sparse to dense
optimization along the pathefficiently explores thenonconvex landscape.

The power of warm starts

I The sparse to dense
optimization along the pathefficiently explores thenonconvex landscape.
I Training combines warm
starts and early stopping

The power of warm starts

I The sparse to dense
optimization along the pathefficiently explores thenonconvex landscape.
I Training combines warmstarts and early stopping
I The bulk of thecomputational cost goes totraining the dense model.
I This is effectively pruning

The Hier-Prox algorithm

I The hierarchy constraint is separable over the features.
I Objective can be optimized by constrained proximal GD

The Hier-Prox algorithm

I The hierarchy constraint is separable over the features.
I Objective can be optimized by constrained proximal GD
I At its core, LassoNet solves d problems of the form
minimizeβ∈R,W ∈RK 12 (v − β)2 + 12 ku − W k2 + λkβk1
subject to kW k∞ ≤ M · |β|I Hier-Prox: an efficient hierarchical proximal operator

The Hier-Prox operator
I At its core, LassoNet solves d problems of the form
minimizeβ∈R,W ∈RK 12 (v − β)2 + 12 ku − W k2 + λkβk1
subject to kW k∞ ≤ M · |β|I The Hier-Prox operator provides the global solution of thisnonconvex minimization problem

The Hier-Prox operator
I At its core, LassoNet solves d problems of the form
minimizeβ∈R,W ∈RK 12 (v − β)2 + 12 ku − W k2 + λkβk1
subject to kW k∞ ≤ M · |β|I The Hier-Prox operator provides the global solution of thisnonconvex minimization problem
I Integrates seamlessly with deep learning frameworks

The Hier-Prox operator
I At its core, LassoNet solves d problems of the form
minimizeβ∈R,W ∈RK 12 (v − β)2 + 12 ku − W k2 + λkβk1
subject to kW k∞ ≤ M · |β|I The Hier-Prox operator provides the global solution of thisnonconvex minimization problem
I Integrates seamlessly with deep learning frameworks
I The algorithm has complexity O(dK · log(dK )), where d isthe number of features and K the size of the input layer
I Negligible overhead compared to gradient computations

Experimental evaluation

I Most other feature selection methods are not embedded
I Plug the selected features into external downstream learners:
I A feedforward neural network
I A tree-based classifier

I Systematic evaluation on 6 datasets

Results on the ISOLET dataset
I Letter speech data
I Benchmark data set for feature selection
I n = 7797, d = 617

Classification accuracies for feature selection methods
Left: using a one-hidden-layer feedforward neural network. Right: using an extremely randomized tree classifier.Systematic evaluation

Compare the classification accuracies for a fixed number offeatures, k = 50:

Classification accuracies on a hold-out test set, using a one-hidden-layer feedforward neural network.

Summary
The Neural Network Resurrection
Feature Selection
Benefits
Desiderata
LassoNet
The hierarchy principle
Formulation
Optimization
Pruning a dense model
The hierarchical optimizer
Experimental evaluation

Extensions and applications
I Unsupervised learning
I Reconstruction loss as the objective
I Related work: Concrete auto-encoder (Abid et al., ICML 2019)

Reconstructing single digit classes of MNISTExtensions and applications
I Unsupervised Learning
I Reconstruction loss as the objective
I Related work: Concrete auto-encoder (Abid et al., ICML 2019)

Extensions and applications
I Unsupervised Learning
I Reconstruction loss as the objective
I Related work: Concrete auto-encoder (Abid et al., ICML 2019)

I Cox Proportional Hazards Model

Extensions and applications
I Unsupervised Learning
I Reconstruction loss as the objective
I Related work: Concrete auto-encoder (Abid et al., ICML 2019)

I Cox Proportional Hazards ModelI Matrix completion and imputation

Extensions and applications
I Unsupervised Learning
I Reconstruction loss as the objective
I Related work: Concrete auto-encoder (Abid et al., ICML 2019)

I Cox Proportional Hazards ModelI Matrix completion and imputation
I Filter selection for Computer vision/ ConvNets

Resources

I Talk Materials at: https://tinyurl.com/lassonet
I Code at: https://github.com/ilemhadri/lassonet
I Thanks:
I Rob Tibshirani
I Feng Ruan
I PyTorch help: Louis Abraham

I Thank you. Be well!

The Hier-Prox algorithm

Systematic evaluation
Compare the classification accuracies for a fixed number offeatures, k = 50:

Classification accuracies on a hold-out test set, using Extremely Randomized Tree Classifiers (a variant of randomforests).