Problems With L0 Regularization
In regression, we sometimes want to penalize the number of non-zero coefficients directly. The $L_0$ "norm" of a coefficient vector $\beta$ counts how many entries are non-zero:
$$\|\beta\|_0 = \#\{j : \beta_j \neq 0\}$$
The $L_0$-regularized regression problem is:
$$\min_{\beta} \|Y - X\beta\|_2^2 + \lambda \|\beta\|_0$$
- Why is this problem fundamentally harder to solve than $L_1$ or $L_2$ regularized regression?
- What specific mathematical properties make $L_0$ regularization intractable for standard optimization algorithms?
- Why is $L_1$ (Lasso) used as a practical substitute, and in what sense is it the "best" convex substitute for $L_0$?
Hints
- Think about what happens to the penalty when a coefficient moves from exactly zero to just slightly above zero -- how does the $L_0$ penalty behave compared to $L_1$ or $L_2$?
- Consider the geometry: how many candidate subsets of features exist with $p$ predictors, and what complexity class does exhaustive search fall into?
- The $L_1$ ball is the convex hull of sparse vectors -- this is why Lasso is the natural convex substitute for $L_0$.
Worked Solution
How to Think About It: The appeal of $L_0$ regularization is obvious -- you want a sparse model, so why not directly penalize the number of non-zero coefficients? The problem is that "count the non-zeros" is a combinatorial objective, not a smooth one. Flipping a coefficient from $0.0001$ to $0$ changes the penalty by exactly $\lambda$, but flipping it from $0.0001$ to $0.0002$ changes the penalty by nothing. This discontinuity is the root of all the trouble. In practice, anyone who has tried best-subset selection on more than about 30-40 features knows it becomes computationally infeasible.
Key Insight: The $L_0$ penalty is non-convex and discontinuous, which means there is no gradient to follow, no efficient descent direction, and no polynomial-time algorithm guaranteed to find the global minimum.
The Method:
The problems with $L_0$ regularization break down into three categories:
- NP-hardness (computational intractability): Solving the $L_0$ problem exactly requires searching over all possible subsets of features. With $p$ features, there are $2^p$ subsets. For $p = 50$, that is over $10^{15}$ subsets -- far beyond any brute-force search. This is equivalent to the classical best-subset selection problem, which is known to be NP-hard. No clever algorithm can avoid the exponential blowup in the worst case.
2. Non-convexity and discontinuity: The function $f(\beta_j) = \mathbb{1}(\beta_j \neq 0)$ is discontinuous at zero. It jumps from 0 to 1 with no smooth transition. This means: - The overall objective $\|Y - X\beta\|_2^2 + \lambda\|\beta\|_0$ is non-convex - Gradient-based optimizers (gradient descent, Newton's method, coordinate descent) cannot be applied because the penalty has no well-defined gradient - Local minima are abundant, so even heuristic search methods may get stuck far from the global optimum
- No efficient relaxation to the same problem: Unlike $L_2$ regularization (Ridge), which gives a closed-form solution $\beta = (X^TX + \lambda I)^{-1}X^TY$, and $L_1$ (Lasso), which is a convex program solvable in polynomial time, $L_0$ has no tractable reformulation that preserves the exact same solution.
Practical Considerations:
- $L_1$ (Lasso) is the tightest convex relaxation of $L_0$. Geometrically, the $L_1$ unit ball is the convex hull of the $L_0$ "ball" (the set of vectors with at most $k$ non-zero entries, intersected with the right constraints). This is why Lasso produces sparse solutions -- it is the best convex approximation to the sparsity-inducing objective.
- In low dimensions ($p \leq 30$ or so), modern mixed-integer programming solvers can actually solve the $L_0$ problem exactly. Recent work has pushed this boundary, but for high-dimensional problems typical in quant finance (thousands of features), $L_1$ remains the go-to.
- Greedy algorithms like forward stepwise selection and matching pursuit are heuristics for the $L_0$ problem. They are fast but offer no global optimality guarantee.
- The SCAD and MCP penalties are non-convex alternatives that sit between $L_0$ and $L_1$ -- they reduce bias on large coefficients while maintaining some computational tractability.
Answer: $L_0$ regularization is intractable because (1) the optimization is NP-hard, requiring a search over $2^p$ subsets, (2) the penalty is non-convex and discontinuous, ruling out gradient-based methods, and (3) there is no polynomial-time algorithm for the global optimum. $L_1$ (Lasso) is preferred because it is the tightest convex relaxation of $L_0$, producing sparse solutions while remaining solvable in polynomial time.
Intuition
The core lesson here is why convexity matters so much in optimization. In theory, $L_0$ is exactly what you want for sparse regression -- it directly counts non-zero coefficients. But "exactly what you want" is useless if you cannot compute it. The jump discontinuity at zero means the objective landscape is riddled with flat plateaus separated by cliffs, giving optimizers no useful local information about which direction to move. This is a recurring theme in quant modeling: the theoretically ideal objective is often intractable, so you work with the best tractable approximation.
In practice, this tradeoff between statistical ideality and computational feasibility shows up everywhere -- from portfolio optimization (the true Markowitz problem with integer cardinality constraints is NP-hard, so you relax it) to feature selection in alpha research (you use Lasso or elastic net, not exhaustive search). Understanding why $L_1$ is the tightest convex relaxation of $L_0$ gives you a principled reason to prefer Lasso over ad-hoc alternatives, and it helps you recognize when non-convex methods like SCAD or MCP might be worth the extra complexity.