L1 regularization, also known as Lasso (Least Absolute Shrinkage and Selection Operator), is a technique in machine learning and statistics used to prevent overfitting by adding a penalty term equal to the absolute value of the magnitude of coefficients. It encourages sparsity in the model, effectively performing feature selection by driving some coefficients to zero. This method is widely applied in regression, classification, and other optimization tasks within information technology.
1 Introduction
1.1 Motivation for Regularization
In machine learning and statistical modeling, overfitting occurs when a model learns noise in the training data rather than the underlying pattern, leading to poor generalization on new data. Regularization techniques address this by imposing a penalty on model complexity. L1 regularization is one such method that balances model fit and complexity.
1.2 Definition of L1 Regularization
L1 regularization adds a penalty proportional to the sum of the absolute values of the model coefficients to the loss function. This encourages the model to keep only the most important features, often setting less important coefficients exactly to zero. The name “Lasso” reflects its ability to both shrink coefficients and perform selection.
1.3 Comparison with L2 Regularization
While L2 regularization (Ridge) penalizes the squared magnitude of coefficients, L1 regularization penalizes the absolute magnitude. A key difference is that L1 yields sparse solutions, whereas L2 does not. L2 tends to shrink coefficients uniformly, while L1 can drive some to zero, making it preferred when feature selection is desired.
2 Mathematical Formulation
2.1 Objective Function
For a given loss function \( L(\mathbf{w}) \) (e.g., mean squared error for regression or log-loss for classification), the L1 regularized objective is:
\[
| \min_{\mathbf{w}} L(\mathbf{w}) + \lambda \|\mathbf{w}\|_1 |
|---|
\]
| where \(\mathbf{w}\) is the vector of coefficients and \(\|\mathbf{w}\|_1 = \sum_{j} | w_j | \). |
|---|
2.2 Penalty Term
| The penalty term \(\lambda \|\mathbf{w}\|_1\) is the L1 norm of the coefficient vector scaled by the tuning parameter \(\lambda \geq 0\). This term forces some coefficients to become exactly zero as the penalty increases. |
|---|
2.3 Tuning Parameter (Lambda)
The parameter \(\lambda\) controls the strength of regularization: larger \(\lambda\) increases penalty, leading to more shrinkage and more zero coefficients. \(\lambda = 0\) yields the unregularized solution. Selecting an appropriate \(\lambda\) is critical and typically done via cross-validation.
3 Properties of L1 Regularization
3.1 Sparsity
L1 regularization produces sparse models where many coefficients are exactly zero. This property arises because the L1 penalty has a sharp corner at zero in the constraint region, making zero more likely for optimal solutions.
3.2 Shrinkage
Like other regularizers, L1 shrinks the estimated coefficients toward zero, reducing variance at the cost of some bias. The magnitude of shrinkage depends on the size of each coefficient and the value of \(\lambda\).
3.3 Feature Selection
By setting some coefficients to zero, L1 regularization effectively selects a subset of features that are most relevant to the target variable. This embedded feature selection simplifies models and improves interpretability.
3.4 Geometrical Interpretation
3.4.1 Constraint Region
| The L1 regularization can be viewed as a constrained optimization problem: minimize \(L(\mathbf{w})\) subject to \(\|\mathbf{w}\|_1 \leq t\) for some \(t\). The constraint region is a diamond (in 2D) or a cross-polytope (in higher dimensions), which has sharp corners at the axes. |
|---|
3.4.2 Optimization Path
The solution path as \(\lambda\) varies corresponds to the contours of the loss function intersecting the diamond-shaped constraint region. When the loss contours touch a corner, one or more coefficients become exactly zero, illustrating the sparsity property.
4 Optimization Algorithms
4.1 Coordinate Descent
Coordinate descent optimizes one coefficient at a time while keeping others fixed. For L1 regularization, closed-form updates exist using soft-thresholding. It is efficient for high-dimensional problems and is the algorithm used in the popular glmnet package.
4.2 Subgradient Methods
Since the L1 penalty is not differentiable at zero, subgradient methods are employed.
4.2.1 Subgradient Descent
Standard gradient descent can be adapted by using subgradients—any gradient that lies in the subdifferential of the penalty at zero. This approach updates coefficients iteratively using a subgradient of the objective.
4.2.2 Proximal Gradient Method
This method handles the nondifferentiable penalty via a proximal operator. It first takes a gradient step on the smooth part and then applies the soft-thresholding operator, which is the proximal mapping of the L1 norm.
4.3 Least Angle Regression (LARS)
LARS is a stepwise procedure that builds the entire Lasso solution path efficiently. It adds variables one by one, updating coefficients in a piecewise linear manner, and is particularly fast when the number of features is not too large.
4.4 Alternating Direction Method of Multipliers (ADMM)
ADMM decomposes the L1 regularized problem into simpler subproblems, often using variable splitting. It converges under mild conditions and is well-suited for distributed or large-scale optimization.
5 Applications
5.1 Linear Regression
L1 regularized linear regression (Lasso) is used for modeling relationships where only a few predictors are relevant. It is common in genomics, economics, and other fields with high-dimensional data.
5.2 Logistic Regression
In binary classification, L1 logistic regression performs simultaneous classification and feature selection, useful for text classification, medical diagnosis, and customer churn prediction.
5.3 Neural Networks
5.3.1 Sparse Neural Networks
Applying L1 regularization to neural network weights encourages many weights to become zero, resulting in sparse networks that are more memory-efficient and interpretable.
5.3.2 Weight Pruning
L1 regularization can be used as a pruning strategy: after training, weights that are zero (or near zero) are removed, reducing model size without significant performance loss.
5.4 Compressed Sensing
L1 minimization is fundamental in compressed sensing, where sparse signals are recovered from undersampled measurements. The L1 norm promotes the sparsest solution among infinitely many that fit the data.
5.5 Signal Processing
In signal processing, L1 regularization is applied to problems such as denoising, deconvolution, and image reconstruction, where the underlying signal is assumed to be sparse in some domain (e.g., wavelet or Fourier basis).
6 Relationship with Other Regularization Techniques
6.1 Ridge Regression (L2)
| Ridge regression uses the L2 penalty \(\lambda \|\mathbf{w}\|_2^2\), which shrinks coefficients but never sets them to zero. L1 is preferred when sparsity is needed; ridge is better when all features are relevant. |
|---|
6.2 Elastic Net
| Elastic Net combines L1 and L2 penalties: \(\lambda_1 \|\mathbf{w}\|_1 + \lambda_2 \|\mathbf{w}\|_2^2\). It inherits sparsity from L1 and the grouping effect from L2, handling correlated features better than Lasso alone. |
|---|
6.3 Group Lasso
Group Lasso extends L1 regularization to predefined groups of variables. The penalty is the sum of L2 norms of each group, encouraging sparsity at the group level (either all coefficients in a group are zero or all non-zero).
6.4 Fused Lasso
| Fused Lasso adds a penalty on the differences between consecutive coefficients: \(\lambda_1 \|\mathbf{w}\|_1 + \lambda_2 \sum | w_j - w_{j-1} | \). It encourages both sparsity and smoothness, useful for problems with ordered features (e.g., time series, genomic data). |
|---|
7 Extensions and Variants
7.1 Adaptive Lasso
Adaptive Lasso applies different weights to different coefficients in the L1 penalty, using data-driven weights that are larger for less important coefficients. This improves selection consistency, especially under certain theoretical conditions.
7.2 Relaxed Lasso
Relaxed Lasso performs a two-stage procedure: first apply Lasso for feature selection, then re-estimate (without regularization or with lighter regularization) on the selected subset. This reduces bias from the L1 penalty.
7.3 Bayesian Lasso
Bayesian Lasso treats the L1 regularization as a Laplace prior on the coefficients. By assigning a double exponential prior, it provides a probabilistic interpretation and can yield posterior distributions for uncertainty quantification.
7.4 Structured Sparsity
Structured sparsity extends L1 to incorporate prior knowledge about the structure of features, such as groups, trees, or graphs. Penalties are designed to promote sparsity patterns that align with known structures, e.g., overlapping groups or hierarchies.
8 Practical Considerations
8.1 Choosing the Regularization Parameter
8.1.1 Cross-Validation
The most common method is k-fold cross-validation, where \(\lambda\) is chosen to minimize average validation error over a grid of values. The “1 standard error” rule often selects a simpler model within one standard error of the minimum.
8.1.2 Information Criteria (AIC, BIC)
Information criteria like AIC (Akaike Information Criterion) and BIC (Bayesian Information Criterion) can be used to select \(\lambda\), balancing goodness-of-fit and model complexity. They are faster than cross-validation but rely on asymptotic assumptions.
8.2 Standardization of Features
Because the L1 penalty depends on the magnitude of coefficients, features should be standardized (e.g., zero mean and unit variance) to avoid penalizing large-scale features more heavily. After regularization, coefficients can be transformed back to original scales.
8.3 Handling Categorical Variables
Categorical variables are typically one-hot encoded. However, L1 may select some levels and drop others, which can be undesirable. Alternatives include using group Lasso to keep all levels of a categorical variable together, or applying regularization at the variable level.
9 Limitations and Challenges
9.1 Selection Consistency
Lasso is not always consistent in selecting the correct features, especially when the number of features grows faster than the number of samples, or when the signal-to-noise ratio is low. Adaptive Lasso or thresholding can improve consistency.
9.2 High Correlation Among Features
When features are highly correlated, Lasso tends to arbitrarily select one and drop the others. Elastic Net or group Lasso may be more suitable in such cases, as they encourage grouping of correlated variables.
9.3 Computational Complexity
For very large datasets (millions of features), coordinate descent and LARS can still be computationally intensive. Stochastic or distributed methods (e.g., ADMM on clusters) may be necessary, but trade-offs in convergence speed must be considered.
10 Software Implementations
10.1 Python (scikit-learn, statsmodels)
In scikit-learn, Lasso and LogisticRegression(penalty='l1') are available, with optimization via coordinate descent. statsmodels provides OLS.fit_regularized for L1 regression. The cv modules assist in cross-validated parameter selection.
10.2 R (glmnet)
The glmnet package in R is highly optimized for L1 (and elastic net) regularization, using coordinate descent over a path of \(\lambda\) values. It supports regression, classification, and survival models.
10.3 MATLAB (lasso)
MATLAB’s Statistics and Machine Learning Toolbox includes the lasso function, which uses LARS or coordinate descent to compute the regularization path. Additional options allow specification of cross-validation and weighting.