Feature selection, L1 vs. L2 regularization, and rotational invariance

By Andrew Y. Ng. 2004

2,105 citations recorded by the source corpus.

We consider supervised learning in the presence of very many irrelevant features, and study two different regularization methods for preventing overfitting. Focusing on logistic regression, we show that using L1 regularization of the parameters, the sample complexity (i.e., the number of training examples required to learn "well,") grows only logarithmically in the number of irrelevant features. This logarithmic rate matches the best known bounds for feature selection, and indicates that L1 regularized logistic regression can be effective even if there are exponentially many irrelevant features as there are training examples. We also give a lower-bound showing that any rotationally invariant algorithm---including logistic regression with L2 regularization, SVMs, and neural networks trained by backpropagation---has a worst case sample complexity that grows at least linearly in the number of irrelevant features.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Hyper-Parameter Optimization: A Review of Algorithms and Applications (2020, background): “The general expression of the regularization term is as follows (Ng, 2004): cost = lossfunction+ regularizationterm The L1 term uses the sum of absolute values of weights.”
MorphNet: Fast & Simple Resource-Constrained Structure Learning of Deep Networks (2017, methodology): “Later work [30] proposed to use an L1 regularization, which is known to induce sparsity [27, 23], thus alleviating the need for sophisticated estimates of a parameter’s contribution to the loss.”
Learning from Physical Human Corrections, One Feature at a Time (2018, background): “A natural solution for restricting the number of learned features might be to switch the regularization term in (5) to the L1 norm [13, 15], which encourages sparsity of the weight update.”
Parallel Coordinate Descent for L1-Regularized Loss Minimization (2011, methodology): “the number of irrelevant features (Ng, 2004).”
Tree-Guided Group Lasso for Multi-Task Regression with Structured Sparsity (2009, methodology): “, a gene expression measurement for a single gene), techniques such as lasso (Tibshirani, 1996) or L1-regularized logistic regression (Ng, 2004; Wainwright et al., 2006) have been developed to identify a parsimonious subset of covariates that determine the outputs.”
Regularization Techniques for Learning with Matrices (2009, background): “In the context of batch learning, it was studied by several authors (e.g. Ng [2004]).”
Multi-Label Prediction via Compressed Sensing (2009, background): “g.[23, 22]) which are concerned with sparsity in the weight vec tor, rather than in the output.”
A Survey of Deep Learning Applications to Autonomous Vehicle Control (2019, background): “e network reduce the effect of individual inputs on its behaviour, which means that the effect of local noise is reduced and the network is more likely to learn trends across the whole data set [49], [187]. Similarly, imposing constraints on the network weights through weight clipping has also been ”
Why do tree-based models still outperform deep learning on typical tabular data? (2022, methodology): “One answer is that this learner is rotationally invariant in the sense of Ng [2004]: the learning procedure which learns an MLP on a training set and evaluate it on a testing set is unchanged when applying a rotation (unitary matrix) to the features on both the training and testing set.”
A cloud detection algorithm for satellite imagery based on deep learning (2019, background): “L2-regularization L2-regularization adds the squared sums of the weights to the loss function, thereby preventing individual neurons to dominate (Ng, 2004), and is used in all convolutional layers.”
Compressive light-field microscopy for 3D neural activity recording (2016, methodology): “We implement a sparsity constraint known as l1 “Lasso” regularization [24,25] on the temporal components: min Si;k>0;Tk;j>0 ∥I − ST∥ 2 λ1 X”
High-Dimensional Graphical Model Selection Using $\ell_1$-Regularized Logistic Regression (2008, background): “A surge of recent work has shown that ℓ 1 -regularization can lead to practical algorithms with strong theoretical guarantees (e.g., Candes and Tao (2006), Donoho and Elad (2003), Meinshausen and B¨uhlmann (2006), Ng (2004), Tropp (2006), Wainwright (2006), Zhao and Yu (2007)).”