Why the hard and soft constraint problems are equivalent in lasso
Earlier, we skipped over showing that the soft and hard constraints are equivalent for some values of λ and t.
You may be wondering: why must this be the case?
I recommend skipping to the “Solution” section unless you want to try to figure it out yourself first.
Problem set up
(Reminder: the data point or observation index is i, and the feature variable index is j.)
Hard constraint:
(α̂, 𝛽̂) = argmin ∑ᵢ(yᵢ — α — ∑ⱼβⱼxᵢⱼ)², subject to ∑ⱼ |𝛽ⱼ| ≤ 𝑡
Soft constraint:
(α̂, 𝛽̂) = argmin ∑ᵢ(yᵢ — α — ∑ⱼβⱼxᵢⱼ)² + λ∑ⱼ |𝛽ⱼ|
Let’s denote the optimal solution for the hard constraint problem as (α̂ʰ, 𝛽̂ʰ).
In this case, we wonder: can we find a value of λ for which the soft constraint problem will have the same optimal solution as the hard constraint problem?
We can try finding this λ by setting λ = λₒ such that (α̂ʰ, 𝛽̂ʰ) is also the optimal solution for the soft constraint problem.
This means the sum of squared error for the optimal hard constraint estimates plus the coefficient penalty term is less than (or equal to) any other possible coefficient estimates, given we use our magic λₒ.
In other words:
∑ᵢ(yᵢ — α̂ʰ — ∑ⱼ𝛽̂ʰⱼxᵢⱼ)² + λₒ∑ⱼ |𝛽̂ʰⱼ| ≤ ∑ᵢ(yᵢ — α — ∑ⱼβⱼxᵢⱼ)² + λₒ∑ⱼ |𝛽ⱼ|, for all (α, β).
This is what we will try to show. (We haven’t shown if this ends up actually being true yet.)
To be clear: the left hand side of the above is the objective function value of the soft constraint problem evaluated at the optimal solution (α̂ʰ, 𝛽̂ʰ) of the hard constraint problem. The right-hand side of the inequality represents the objective function value of the soft constraint problem evaluated at any other solution (α, β) of the hard constraint problem.
The equation just means that if it is true that minimizing with the hard constraint results in an optimal value of α, β that can be encompassed with the soft constraint formulation, the loss will be as low as it is possible to be.
The constraint can either be “active” (we end up being limited by it) or not active (we don’t hit the constraint — the least squared error estimate falls within the diamond).
If the constraint is not active, (that is, we are inside the diamond and we can achieve the least squares estimate fully), we can easily set λ = λₒ = 0. In this case, effectively remove the penalty term, so the solution of the soft constraint problem will be equivalent to minimizing least squared error, which will be equivalent to the hard constraint solution (since the constraint is inactive).
This happens when ∑ⱼ |𝛽ⱼ| < t (as opposed to = t, which has hit the constraint).
Next, let’s consider the case where we’re using the hard constraint and we end up hitting this constraint when trying to reach the squared error optimal solution; i.e., ∑ⱼ |𝛽̂ʰⱼ| = t. This means that the optimal solution (α̂ʰ, 𝛽̂ʰ) cannot be improved further without violating the constraint, and we are on the edge of the diamond.
In this case, we can show that there exists a value of λ for which the soft constraint problem will have the same optimal solution as the hard constraint problem.
Suppose we set λ = λₒ such that (α̂ʰ, 𝛽̂ʰ) is also the optimal solution (which is at a single point on the edge of the diamond since the constraint is active) for the soft constraint problem.
Recall that we want to show:
∑ᵢ(yᵢ — α̂ʰ — ∑ⱼ𝛽̂ʰⱼxᵢⱼ)² + λₒ∑ⱼ |𝛽̂ʰⱼ| ≤ ∑ᵢ(yᵢ — α — ∑ⱼβⱼxᵢⱼ)² + λₒ∑ⱼ |𝛽ⱼ| for all (α, β)
Can you think of a way to show this when the constraint is active, without using partial derivatives or Lagrange multipliers?
Solution
When λ = 0, the penalty term is null, and the model is identical to ordinary least squares, focusing purely on minimizing the residual sum of squares. As λ increases from zero, each incremental increase adds a penalty for coefficient size, progressively pulling all coefficients towards zero. This shrinkage effect intensifies with increasing λ. The shrinkage isn’t uniform across coefficients; it shrinks some more than others.
The path of coefficients as a function of λ is continuous. This means that for small changes in λ, the changes in coefficients are also small. This property is crucial because it ensures that there are no sudden jumps in coefficient values as λ changes: the coefficients smoothly go towards zero.
(This path is also piecewise linear because although it is continuous, the rate of change can abruptly change when a coefficient goes to zero. The changes in the active set of coefficients (those that are non-zero) occur at only certain values of λ. This doesn’t allow jumps in the path itself.)
The continuity of the solution path ensures that as λ is incremented from 0, the sum of the absolute values of coefficients also changes continuously!
This guarantees that there must be some λ₀ where the total sum of absolute values of the coefficients reaches exactly t for the first time. (Without continuity, it could be possible to jump over this critical value without ever achieving exactly t.)
The piecewise linearity indicates that as we increase λ, if the sum of the absolute values of coefficients at one λ is less than t and at the next λ is more than t, due to linearity, there exists a λ in between where the sum is exactly t. The critical λ (λ = λ₀) is this value, where the soft constraint (through penalization) equivalently enforces the hard constraint of t.
Therefore, there must exist a value λ₀ such that ∑ⱼ |βⱼ| = t.
