Sparse Regression Optimizer with L1 Penalty

In machine learning, building predictive models that are both accurate and interpretable is a fundamental challenge. One powerful technique to achieve this balance is L1-regularized linear regression, commonly known as the Lasso (Least Absolute Shrinkage and Selection Operator) method.

Unlike standard linear regression, which can produce models with many non-zero coefficients, L1 regularization adds a penalty proportional to the absolute values of the model weights. This penalty serves two crucial purposes:

1. Automatic Feature Selection: The L1 penalty naturally drives some coefficients to exactly zero, effectively removing irrelevant features from the model
2. Overfitting Prevention: By constraining the magnitude of weights, the regularization prevents the model from fitting noise in the training data

The Optimization Objective

The algorithm seeks to minimize a composite loss function that balances prediction accuracy with model simplicity:

$$J(\mathbf{w}, b) = \frac{1}{2n} \sum_{i=1}^{n} \left( y_i - \left( \sum_{j=1}^{p} X_{ij} w_j + b \right) \right)^2 + \alpha \sum_{j=1}^{p} |w_j|$$

Where:

• n represents the total number of training samples
• p denotes the number of input features
• yᵢ is the actual target value for sample i
• ŷᵢ = Σⱼ Xᵢⱼwⱼ + b is the model's predicted value
• wⱼ is the weight (coefficient) for feature j
• b is the bias (intercept) term, which is not regularized
• α controls the regularization intensity

Gradient Descent Optimization

Since the L1 penalty is not differentiable at zero, we use the subgradient method. For each weight update, the gradient of the L1 term uses the sign function:

$$\frac{\partial}{\partial w_j} |w_j| = \text{sign}(w_j)$$

The update rules become:

• Weights: $w_j \leftarrow w_j - \eta \left( \frac{1}{n} \sum_{i} (\hat{y}i - y_i) X{ij} + \alpha \cdot \text{sign}(w_j) \right)$
• Bias: $b \leftarrow b - \eta \cdot \frac{1}{n} \sum_{i} (\hat{y}_i - y_i)$

Where η is the learning rate.

Your Task

Implement the gradient descent optimization algorithm to train an L1-regularized linear regression model. Your function should iteratively update the weights and bias to minimize the objective function, returning the final optimized parameters.