High Dimensional Classification through $\\ell_0$-Penalized Empirical\n Risk Minimization

Le-Yu Chen, Sokbae LeearXiv 2018 · DOI · arXiv

Introduction

In the era of big data, researchers frequently encounter high-dimensional classification problems where the number of features ($p$) significantly exceeds the number of observations ($n$). In such settings, traditional statistical methods often fail due to overfitting. To combat this, the principle of "sparsity" is invoked, assuming that only a small subset of features truly influences the outcome. While the $\ell_1$-penalty (Lasso) has become the industry standard for inducing sparsity due to its convexity, it often serves as a biased proxy for the "true" measure of sparsity: the $\ell_0$-norm, which counts the exact number of non-zero coefficients.

This paper investigates a direct approach to this challenge by minimizing the empirical misclassification risk with an explicit $\ell_0$-penalty. By leveraging advances in optimization, the authors demonstrate that this historically "intractable" problem is not only solvable but provides superior theoretical and empirical performance compared to Lasso-based methods.

The $\ell_0$-Penalized ERM Framework

The core of the proposed method is an Empirical Risk Minimization (ERM) procedure. The objective function combines the empirical misclassification risk—the proportion of incorrect predictions in the training set—with a penalty term $\lambda ||\theta||_0$.

Unlike logistic regression, which uses a smooth surrogate loss (like log-loss), this approach directly targets the misclassification rate. The $\ell_0$-penalty ensures that the model remains parsimonious, selecting only the most informative features.

Implementation via Mixed Integer Linear Programming (MILP)

The primary hurdle for $\ell_0$ optimization is its non-convex, discrete nature, which is NP-hard in the general case. The authors overcome this by reformulating the problem as a Mixed Integer Linear Program (MILP).

Key to this reformulation is the "Big-M" constraint method. By introducing a binary indicator variable $e_j \in \{0, 1\}$ for each feature $j$, the optimization can "switch" features on or off. If $e_j = 0$, the corresponding coefficient $\theta_j$ is forced to zero; if $e_j = 1$, the coefficient is allowed to take a value within a bounded range $[-M, M]$. Modern MILP solvers, such as Gurobi or CPLEX, can then navigate this discrete search space efficiently using branch-and-bound algorithms.

Theoretical Guarantees

A significant contribution of this work is the derivation of non-asymptotic probability bounds. Unlike asymptotic theory, which describes behavior as $n$ approaches infinity, non-asymptotic bounds provide guarantees for finite sample sizes.

The authors prove two critical properties:

  1. Sparsity Bound: With high probability, the number of features selected by the $\ell_0$-ERM procedure is remarkably close to the true number of relevant features ($q$), even when $p$ grows exponentially relative to $n$.
  2. Risk Consistency: The excess misclassification risk—the gap between the model's performance and the best possible theoretical classifier—vanishes as the sample size increases, confirming the method's reliability in high-dimensional regimes.

Numerical Performance

The authors validated their approach using Monte Carlo simulations, comparing $\ell_0$-ERM against the standard Lasso-penalized logistic regression. The results highlight several advantages:

  • Feature Selection Accuracy: In high-dimensional scenarios ($p=200, n=100$), the $\ell_0$ method achieved "Oracle selection" (identifying exactly the correct features) at rates between 80% and 95%. In contrast, Lasso-based methods almost never achieved perfect selection, often including many irrelevant variables.
  • Reduced False Positives: On average, Lasso selected over 7 irrelevant features, while the $\ell_0$-ERM selected only 0.15.
  • Predictive Power: The $\ell_0$ approach consistently yielded lower out-of-sample relative risk. For instance, in the $p=200$ case, the relative risk for $\ell_0$-ERM was approximately 1.14, compared to 1.31 for the best-tuned Lasso.
  • Robustness: The method maintained strong performance even under model misspecification, where the underlying data-generating process did not follow a simple logistic structure.

Conclusion and Future Directions

This research demonstrates that $\ell_0$-penalized classification is a viable and powerful tool for high-dimensional data. By moving beyond the $\ell_1$ approximation, researchers can achieve better feature selection and lower predictive risk.

While the MILP approach is computationally feasible for moderate sample sizes, scaling to very large datasets remains a challenge. Future work may focus on "divide-and-conquer" strategies to distribute the computational load or extending these $\ell_0$ guarantees to other domains, such as continuous regression and policy learning.

Summary updated

Abstract

We consider a high dimensional binary classification problem and construct a\nclassification procedure by minimizing the empirical misclassification risk\nwith a penalty on the number of selected features. We derive non-asymptotic\nprobability bounds on the estimated sparsity as well as on the excess\nmisclassification risk. In particular, we show that our method yields a sparse\nsolution whose l0-norm can be arbitrarily close to true sparsity with high\nprobability and obtain the rates of convergence for the excess\nmisclassification risk. The proposed procedure is implemented via the method of\nmixed integer linear programming. Its numerical performance is illustrated in\nMonte Carlo experiments.\n
BibTeX
@misc{chen2018high,
  author = {Le-Yu Chen and Sokbae Lee},
  title = {{High Dimensional Classification through $\textbackslash\{\}\textbackslash\{\}ell\_0$-Penalized Empirical\textbackslash\{\}n Risk Minimization}},
  year = {2018},
  eprint = {1811.09540},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1811.09540},
}
Figure