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

A. Ng

article2004ICML2,111 citations

Modern predictive modeling frequently encounters high-dimensional data containing numerous irrelevant variables alongside a small set of truly informative features. In these settings, learning algorithms are prone to overfitting, where models memorize noise rather than true patterns and subsequently perform poorly on new data. The primary operational bottleneck is sample complexity, which is the volume of training data required to achieve dependable classification. When the number of features vastly exceeds available samples, organizations face severe performance degradation and escalating data collection costs.

This article evaluates how different penalty methods—specifically first-power magnitude penalties (L1 regularization) versus squared magnitude penalties (L2 regularization)—impact the sample requirements of logistic regression in high-dimensional environments. It aims to theoretically establish and experimentally demonstrate why certain algorithms successfully identify relevant features while others fail when irrelevant dimensions are introduced.

To establish these properties, the article combines statistical learning theory with controlled numerical simulations. The mathematical analysis derives lower bounds on sample complexity using covering number bounds and the geometric concept of rotational invariance, which describes algorithms whose predictions remain identical regardless of coordinate system rotations. The theoretical findings were validated across three synthetic experimental scenarios using data drawn from normal distributions: a single relevant feature, three relevant features, and exponentially decaying feature relevance across multiple dimensions, with all results averaged over 100 trials using a 30 percent hold-out validation split.

The article establishes three key findings. First, logistic regression with L1 regularization achieves a sample complexity that grows only logarithmically with the total number of features. This ensures effective model training even when irrelevant features exponentially outnumber training examples. Second, L2-regularized logistic regression is mathematically proven to be rotationally invariant, causing its sample complexity to scale linearly with the number of input features. Third, this linear sample requirement applies broadly to all rotationally invariant methods, including standard support vector machines and spherically initialized neural networks, leading to rapid performance degradation when irrelevant features are present.

These findings have direct implications for project risk, timelines, and analytical costs. Deploying rotationally invariant models or L2 regularization on uncurated, high-dimensional data demands an impractically large volume of training data to prevent severe error rates. In contrast, utilizing L1 regularization automatically suppresses irrelevant variables, allowing organizations to achieve high predictive accuracy with significantly smaller datasets and lower data acquisition expenses.

Organizations handling high-dimensional data with sparse informative signals should prioritize L1-regularized models or incorporate explicit, non-rotationally invariant feature selection prior to training. Teams should avoid standard L2 regularization and kernel methods when the feature-to-sample ratio is high unless substantial feature pruning is performed beforehand. Future implementation initiatives should test these approaches on domain-specific empirical datasets to evaluate whether these theoretical sample efficiencies persist under non-normal data distributions and complex noise patterns.

The conclusions carry high theoretical confidence based on rigorous mathematical bounds, though practical caution is advised regarding specific boundary conditions. The theoretical guarantees rely strictly on log-loss error metrics within generalized linear frameworks, and the experimental validations utilized synthetic, normally distributed data. Practitioners should anticipate potential performance variations when applying these methods to real-world datasets with complex, non-linear dependencies or severe class imbalances.

classifiers feature selection genetic selection Regularization Rotational Invariance Logistic Regression

Ng (2004).pdf

Paper: Regression Shrinkage and Selection Via the Lasso, Robert Tibshirani (1996). Reading the introduction of the Lasso provides the foundational definition of L1-regularized regression that the source paper subsequently analyzes for high-dimensional sample complexity.
Paper: Stability and Generalization, Olivier Bousquet et al. (2002). Understanding algorithmic stability and generalization error bounds supplies the theoretical bedrock necessary to follow the source's derivation of sample complexity.
Paper: On Discriminative vs. Generative Classifiers: A comparison of logistic regression and naive Bayes, A. Ng et al. (2001). Reviewing the comparative behavior of logistic regression versus generative classifiers establishes vital background on classification convergence rates before examining high-dimensional feature penalties.

Paper: On Model Selection Consistency of Lasso, P. Zhao et al. (2006). This paper extends the source's evaluation of L1 regularization by explicitly establishing the exact conditions required for Lasso to achieve model selection consistency.
Paper: Pegasos: primal estimated sub-gradient solver for SVM, Shai Shalev-Shwartz et al. (2007). Building directly on the source's findings regarding linear models, this paper introduces scalable primal solvers to optimize high-dimensional SVM objectives efficiently.
Paper: Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, John Duchi et al. (2011). This work continues the investigation of high-dimensional learning by developing adaptive gradient methods that optimize sparse objectives more effectively than standard fixed-penalty schemes.

Abstract

This document is a presentation slide deck and does not contain an abstract.

Topics

classifiers feature selection genetic selection regularization

Keywords

Regularization Rotational Invariance Logistic Regression Feature Feature Selection Training Learning Page Number Data

Knowls

Knowl 1 — Sample Complexity Bound for L1-Regularized Logistic Regression
theoretical result
For a binary classification problem over $\mathbb{R}^n$ , let $m$ be the number of training examples and $n$ the total number of features. Suppose there exists a true underlying parameter vector $\theta^* \in \mathbb{R}^n$ that is $r$ -sparse (having at most $r$ non-zero components with $r \ll n$ ), where every component satisfies $|\theta_i^*| \le K$ (for $K \ge 1$ ).

Let $\hat{\theta}$ be the parameter vector obtained by training $L_1$ -regularized logistic regression over the constraint set $\Theta_B = \{\theta \in \mathbb{R}^n : \|\theta\|_1 \le B\}$ for $B \in \{0, 1, \dots, C\}$ with $C = rK$ , using a hold-out validation set to select $B$ . For any error parameter $\epsilon > 0$ and confidence parameter $\delta \in (0, 1)$ , to guarantee that the expected negative log-likelihood (log-loss) satisfies $e_l(\hat{\theta}) \le e_l(\theta^*) + \epsilon$ with probability at least $1 - \delta$ , it suffices that the number of training examples satisfies: $m = \Omega\left((\log n) \cdot \text{poly}(r, K, \log(1/\delta), 1/\epsilon, C)\right)$ where $e_l(\theta) = \mathbb{E}_{(x, y) \sim \mathcal{D}}[-\log p(y \mid x; \theta)]$ .

This establishes that the sample complexity of $L_1$ -regularized logistic regression grows only logarithmically with the total number of features $n$ , demonstrating that $L_1$ regularization can successfully learn when the number of irrelevant features is exponentially larger than the training set size.
Knowl 2 — Sample Complexity Lower Bound for Rotationally Invariant Learning Algorithms
theoretical result
Let $\mathcal{L}$ be any learning algorithm that is rotationally invariant. For any error target $\epsilon \in (0, 1/8)$ and confidence parameter $\delta \in (0, 1/100)$ , there exists a distribution $\mathcal{D}$ over $(x, y) \in \mathbb{R}^n \times \{0, 1\}$ in which the class label depends on only a single feature (specifically, $y = 1 \iff x_1 \ge t$ for some threshold $t$ ), such that for $\mathcal{L}$ to achieve a $0/1$ misclassification test error of at most $\epsilon$ with probability at least $1 - \delta$ , the required number of training examples must satisfy: $m = \Omega\left(\frac{n}{\epsilon}\right)$ where $n$ is the total number of input features.

Consequently, any rotationally invariant learning algorithm has a sample complexity that scales at least linearly with the total dimension $n$ , making rotationally invariant algorithms ineffective for feature selection in high-dimensional spaces containing many irrelevant features.
Knowl 3 — Rotational Invariance of Learning Algorithms
definition
Let $\mathcal{M}_R = \{M \in \mathbb{R}^{n \times n} \mid M M^T = M^T M = I, \det(M) = +1\}$ denote the group of $n \times n$ orthogonal rotation matrices.

Given a training dataset $S = \{(x^{(i)}, y^{(i)})\}_{i=1}^m \subset \mathbb{R}^n \times \mathcal{Y}$ , let $MS = \{(M x^{(i)}, y^{(i)})\}_{i=1}^m$ denote the dataset obtained by rotating every input vector $x^{(i)}$ by $M$ .

Let $\mathcal{L}[S]: \mathbb{R}^n \to \mathcal{Y}$ denote the hypothesis (classifier) produced by training a learning algorithm $\mathcal{L}$ on dataset $S$ . The algorithm $\mathcal{L}$ is defined to be rotationally invariant if, for every rotation matrix $M \in \mathcal{M}_R$ , any training set $S$ , and any evaluation point $x \in \mathbb{R}^n$ , the output hypothesis satisfies: $\mathcal{L}[S](x) = \mathcal{L}[MS](Mx)$
Knowl 4 — Rotational Invariance of L2 Regularization and Non-Invariance of L1 Regularization
theoretical result
Logistic regression regularized by the $L_2$ norm is rotationally invariant, whereas logistic regression regularized by the $L_1$ norm is not rotationally invariant.

For $L_2$ -regularized logistic regression with regularizer $R(\theta) = \|\theta\|_2^2 = \theta^T \theta$ , rotating the training data $S' = MS$ (where $M^T M = I$ ) and transforming the parameters as $\theta' = M\theta$ preserves both the conditional likelihood and the regularization penalty: $p(y \mid Mx; M\theta) = \frac{1}{1 + \exp(-(M\theta)^T (Mx))} = \frac{1}{1 + \exp(-\theta^T M^T M x)} = p(y \mid x; \theta)$ $R(M\theta) = (M\theta)^T (M\theta) = \theta^T M^T M \theta = R(\theta)$ As a result, the regularized log-likelihood objective on rotated data satisfies $J'(M\theta) = J(\theta)$ , yielding optimal parameter estimate $\hat{\theta}' = M\hat{\theta}$ and ensuring $\mathcal{L}[MS](Mx) = \mathcal{L}[S](x)$ .

For $L_1$ regularization, the penalty $R(\theta) = \|\theta\|_1 = \sum_{i=1}^n |\theta_i|$ is not invariant under orthogonal transformations (i.e., $\|M\theta\|_1 \ne \|\theta\|_1$ in general). The coordinate-axis alignment of the $L_1$ norm breaks rotational symmetry, enabling $L_1$ -regularized models to perform sparse feature selection along canonical coordinate axes.
Knowl 5 — Regularized Logistic Regression Model Formulations
model/method
Binary logistic regression models the conditional probability of label $y \in \{0, 1\}$ given an input vector $x \in \mathbb{R}^n$ (including a constant feature $x_0 = 1$ to incorporate the intercept term) parameterized by $\theta \in \mathbb{R}^n$ as: $p(y = 1 \mid x; \theta) = \frac{1}{1 + \exp(-\theta^T x)}$

Given $m$ i.i.d. training points $\{(x^{(i)}, y^{(i)})\}_{i=1}^m$ , regularized logistic regression can be trained via two equivalent formulations connected by Lagrangian duality:
1. Unconstrained penalty formulation: $\hat{\theta} = \arg\max_\theta \sum_{i=1}^m \log p(y^{(i)} \mid x^{(i)}; \theta) - \alpha R(\theta)$ where $\alpha > 0$ dictates the regularization penalty.
2. Constrained formulation: $\max_\theta \sum_{i=1}^m \log p(y^{(i)} \mid x^{(i)}; \theta) \quad \text{subject to} \quad R(\theta) \le B$ where $B > 0$ bounds the parameter norm.
For $L_1$ regularization, $R(\theta) = \|\theta\|_1 = \sum_{j=1}^n |\theta_j|$ ; for $L_2$ regularization, $R(\theta) = \|\theta\|_2^2 = \sum_{j=1}^n \theta_j^2$ .
Knowl 6 — L1-Regularized Logistic Regression Training Algorithm with Hold-Out Validation
algorithm
Input: Training dataset $S = \{(x^{(i)}, y^{(i)})\}_{i=1}^m$ , hold-out fraction $\gamma \in (0, 1)$ , maximum constraint bound $C \in \mathbb{N}$
Output: Final parameter vector $\hat{\theta}$
Split $S$ into training subset $S_1$ of size $(1-\gamma)m$ and validation subset $S_2$ of size $\gamma m$
for $B = 0, 1, 2, \dots, C$ do
    Fit logistic regression on $S_1$ subject to the $L_1$ norm constraint:
         $\theta_B = \arg\max_\theta \sum_{(x^{(i)}, y^{(i)}) \in S_1} \log p(y^{(i)} \mid x^{(i)}; \theta) \quad \text{s.t.} \quad \|\theta\|_1 \le B$
    Evaluate empirical log-loss on the validation set $S_2$ :
         $\hat{e}_l(\theta_B) = -\frac{1}{|S_2|} \sum_{(x^{(i)}, y^{(i)}) \in S_2} \log p(y^{(i)} \mid x^{(i)}; \theta_B)$
end for
Select $B^* = \arg\min_{B \in \{0, 1, \dots, C\}} \hat{e}_l(\theta_B)$
return $\hat{\theta} = \theta_{B^*}$
The algorithm fits an $L_1$ -constrained logistic regression model across discrete constraint values $B \in \{0, 1, \dots, C\}$ on training split $S_1$ and chooses the bound $B^*$ that achieves minimal negative log-likelihood on the hold-out split $S_2$ .
Knowl 7 — Rotational Invariance in Standard Machine Learning Algorithms
theoretical result
Several prominent supervised and unsupervised learning algorithms belong to the class of rotationally invariant algorithms:
- Support Vector Machines (SVMs) using linear kernels, polynomial kernels, radial basis function (RBF) kernels, or any kernel $K(x, z)$ that is a function solely of inner products $x^T x$ , $x^T z$ , and $z^T z$ .
- Multilayer Feedforward Neural Networks trained via backpropagation, provided initial weights are sampled independently from a spherically symmetric distribution.
- Unregularized Logistic Regression fit via standard maximum likelihood.
- The Perceptron Algorithm.
- Principal Component Analysis (PCA) and Independent Component Analysis (ICA) for dimensionality reduction, assuming input features are not individually pre-standardized to unit variance.
Because of their rotational invariance, all such algorithms are constrained by the linear sample complexity lower bound $\Omega(n/\epsilon)$ in high-dimensional feature selection settings.
Knowl 8 — Degradation of Support Vector Machines with Irrelevant Features
theoretical result
While Support Vector Machines (SVMs) can learn effectively in high dimensions when a large margin exists, their generalization error degrades linearly with the addition of irrelevant features due to data sphere expansion.

The expected error bound of an SVM classifier depends directly on the ratio: $\frac{r^2}{\gamma^2}$ where $\gamma$ is the geometric margin and $r = \max_i \|x^{(i)}\|_2$ is the radius of the smallest ball enclosing the data.

Introducing $n$ zero-mean, independent irrelevant features does not alter the margin $\gamma$ along the relevant separating dimensions, but it increases the squared radius $r^2$ linearly in $n$ ( $r^2 = O(n)$ ). As a consequence, SVM generalization performance degrades when numerous irrelevant features are present.
Knowl 9 — Experimental Setup for L1 vs. L2 Regularized Logistic Regression
experimental setup
To evaluate the feature selection efficiency of $L_1$ versus $L_2$ regularization, binary classification datasets are generated from a logistic generative model: $p(y = 1 \mid x; \theta) = \frac{1}{1 + \exp(-\theta^T x)}$ where input vectors $x \in \mathbb{R}^n$ are drawn i.i.d. from a standard multivariate Gaussian distribution $\mathcal{N}(0, I)$ .

For each trial, $30\%$ of the generated training data is held out to select the regularization parameter $B$ , and models are evaluated on test data using negative log-likelihood (log-loss) and $0/1$ misclassification error averaged over 100 independent trials. The number of total features $n$ ranges from 1 to 1000 with fixed training sample sizes $m \in \{100, 200\}$ .

Three parameter configurations are evaluated:
1. Single relevant feature: $\theta_1 = 10$ , and $\theta_i = 0$ for all $i > 1$ .
2. Three relevant features: $\theta_1 = \theta_2 = \theta_3 = 10/\sqrt{3}$ , and $\theta_i = 0$ for all $i > 3$ .
3. Exponentially decaying relevance: $\theta_i = \sqrt{75} \cdot (1/2)^{i-1}$ for $i \ge 1$ .
Knowl 10 — Empirical Performance Comparison of L1 and L2 Regularization with Irrelevant Features
empirical result
In synthetic experiments comparing $L_1$ -regularized and $L_2$ -regularized logistic regression across $n = 1$ to $1000$ features with fixed training sample sizes $m = 100$ and $m = 200$ :
- $L_1$ Regularization: Test log-loss and misclassification error remain stable and grow very slowly with the number of irrelevant features. For 1 relevant feature with $m = 100$ , log-loss increases slightly from $\approx 0.22$ at $n=1$ to plateau below $0.30$ at $n=1000$ , and misclassification error remains around $0.10\text{--}0.15$ .
- $L_2$ Regularization: Test error and log-loss degrade rapidly as irrelevant features increase. For 1 relevant feature with $m = 100$ , log-loss rises steeply from $\approx 0.22$ towards $\approx 0.70$ (approaching the random guessing baseline of $\ln 2 \approx 0.693$ ), while misclassification error rises from $< 0.10$ to over $0.40\text{--}0.45$ by $n = 1000$ .
Identical patterns of rapid failure for $L_2$ regularization and robust performance for $L_1$ regularization occur in both the 3-relevant-features and exponentially decaying relevance experiments.

Coverage note — Standard textbook background material covered in the slides (general definitions of overfitting, polynomial cross-validation, standard VC-dimension, and general exponential families/GLM definitions) was omitted as it does not constitute the paper's original contributions.

References

1.Anthony, M., & Bartlett, P. (1999). Neural network learning: Theoretical foundations. Cambridge University Press.
2.Duda, R., Hart, P., Stork, P. (2000). Pattern Classification, 2nd Ed. John Wiley & Sons.
3.Hastie, T., Tibshirani, R., Friedman J. (2001). The Elements of Statistical Learning. Springer-Verlag.
4.Jaakkola, T. (2004). Machine Learning lecture notes. Available online at http://people.csail.mit.edu/people/tommi/courses.html
5.McCullagh, P., & Nelder, J. A. (1989). Generalized linear models (second edition). Chapman and Hall.
6.Ng, A. Y. (1998). On feature selection: Learning with exponentially many irrelevant features as training examples. Proceedings of the Fifteenth International Conference on Machine Learning (pp. 404-412). Morgan Kaufmann.
7.Ng, A. Y. (1998). Machine Learning lecture notes. Available online at http://www.stanford.edu/class/cs229/.
8.Vapnik, V. (1982). Estimation of dependences based on empirical data. Springer-Verlag.
9.Weston, J., Elisseeff, A., Schölkopf, B., Tipping, M. (2003). Use of the Zero-Norm with Linear Models and Kernel Methods. Journal of Machine Learning Research, 1439-1461.
10.Zhang, T. (2002). Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research, 527-550.

Citation

MLA

Ng, A. Y. “Feature Selection, L ₁ Vs. L ₂ Regularization, and Rotational Invariance”. Twenty-first International Conference on Machine Learning - ICML '04, 2004, p. 78, https://doi.org/10.1145/1015330.1015435.

APA

Ng, A. Y. (2004). Feature selection, L ₁ vs. L ₂ regularization, and rotational invariance. Twenty-first International Conference on Machine Learning - ICML '04, 78. https://doi.org/10.1145/1015330.1015435

Chicago

Ng, A. Y. 2004. “Feature Selection, L ₁ Vs. L ₂ Regularization, and Rotational Invariance”. Twenty-first International Conference on Machine Learning - ICML '04, 78. https://doi.org/10.1145/1015330.1015435.

Harvard

Ng, A.Y. (2004) “Feature selection, L ₁ vs. L ₂ regularization, and rotational invariance”, Twenty-first international conference on Machine learning - ICML '04. ACM Press, p. 78. Available at: https://doi.org/10.1145/1015330.1015435.

Vancouver

1. Ng AY (2004) Feature selection, L ₁ vs. L ₂ regularization, and rotational invariance. In: Twenty-first international conference on Machine learning - ICML '04. ACM Press, p 78

BibTeX

@inproceedings{Ng_2004, series={ICML ’04}, title={Feature selection,
                    <i>L</i>
                    <sub>1</sub>
                    vs.
                    <i>L</i>
                    <sub>2</sub>
                    regularization, and rotational invariance}, url={http://dx.doi.org/10.1145/1015330.1015435}, DOI={10.1145/1015330.1015435}, booktitle={Twenty-first international conference on Machine learning  - ICML ’04}, publisher={ACM Press}, author={Ng, Andrew Y.}, year={2004}, pages={78}, collection={ICML ’04} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors

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

Abstract

Topics

Keywords

Knowls

Knowl 1 — Sample Complexity Bound for L1-Regularized Logistic Regression

Knowl 2 — Sample Complexity Lower Bound for Rotationally Invariant Learning Algorithms

Knowl 3 — Rotational Invariance of Learning Algorithms

Knowl 4 — Rotational Invariance of L2 Regularization and Non-Invariance of L1 Regularization

Knowl 5 — Regularized Logistic Regression Model Formulations

Knowl 6 — L1-Regularized Logistic Regression Training Algorithm with Hold-Out Validation

Knowl 7 — Rotational Invariance in Standard Machine Learning Algorithms

Knowl 8 — Degradation of Support Vector Machines with Irrelevant Features

Knowl 9 — Experimental Setup for L1 vs. L2 Regularized Logistic Regression

Knowl 10 — Empirical Performance Comparison of L1 and L2 Regularization with Irrelevant Features

References

Citation

BibTeX

Access the Paper