Learning with Lq<1 vs L1-Norm Regularisation with Exponentially Many Irrelevant Features

Ata Kabán, Robert J. Durrant

Abstract

This paper investigates the performance of logistic regression with fractional norm regularization ($L_q$ where $0 < q < 1$) in high-dimensional settings. We demonstrate that $L_{q<1}$ regularization can effectively identify a small number of relevant features among exponentially many irrelevant ones. Theoretically, we show that the required sample size grows only logarithmically with the total number of features. Practically, we introduce a robust variational algorithm based on local quadratic approximations that makes the non-convex optimization problem tractable.

Introduction

In modern machine learning, "high-dimensional, low-sample size" problems are increasingly common, such as in genomics where thousands of markers are measured for a small cohort of patients. Standard statistical theory suggests that models will overfit when the number of features $m$ significantly exceeds the number of samples $n$. However, if the underlying signal is sparse—meaning only $r$ features are relevant—regularization can be used to recover the relevant features.

While $L_1$ regularization (the Lasso) is widely used, fractional norms ($L_{q<1}$) are theoretically superior for inducing sparsity. However, their non-convexity and non-differentiability at zero make them challenging to optimize. This work addresses both the theoretical sample complexity and the practical implementation of these "bridge" estimators.

Methodology

The core contribution is an $L_q$-regularized logistic regression framework. The authors provide a theoretical analysis proving that the sample complexity for $L_{q<1}$ grows as $\Omega(\log m)$, matching the favorable scaling of $L_1$ while potentially offering better sparsity.

To solve the non-convex optimization problem, the paper proposes a Local Quadratic Variational Approximation. Instead of direct optimization, the method uses convex duality to create a sequence of quadratic upper bounds. This transforms the problem into an iterative "reweighted" $L_2$-regularized problem.

Local quadratic variational approximation of the non-convex $L_q$ penalty.

Experimental Evaluation

The framework was tested on synthetic datasets designed to evaluate the "irrelevant feature" hypothesis under controlled conditions:

  • Controlled Sparsity: Data was generated with 1 or 3 relevant features, or with exponentially decaying feature relevance.
  • Dimensionality Scaling: The total number of features $m$ ranged from 100 to 1,000, while the training set size remained small ($n=70$).
  • Metrics: Performance was evaluated using 0-1 misclassification error, log-loss, and feature selection accuracy.

Results and Discussion

The results confirm that $L_{q<1}$ shares the logarithmic sample complexity property of $L_1$, allowing it to handle an exponential number of irrelevant features. Notably, $L_{q=0.5}$ significantly outperformed $L_1$ in scenarios with extreme sparsity (1 or 3 relevant features), maintaining near-zero classification error even with a 1000:1 ratio of irrelevant to relevant features.

A key insight is the equivalence of different approximation strategies. The authors prove that the quadratic approximation is mathematically equivalent to a Local Linear Approximation (which solves a sequence of $L_1$ problems). This suggests that the iterative reweighting scheme is the critical component, rather than the specific choice of the variational bound.

Comparison of local quadratic (left) and local linear (right) approximations for the $L_q$ penalty.

Conclusion

While $L_{q<1}$ regularization offers superior sparsity and robust performance in high-dimensional settings, it comes with challenges. The non-convex nature of the objective means the algorithm finds local optima, though simple initializations proved effective in practice. Future work could explore Bayesian extensions to provide uncertainty estimates and further investigate the "crossover point" where $L_1$ might become preferable as the number of relevant features increases.

Summary updated

Abstract

We study the use of fractional norms for regularisation in supervised learning from high dimensional data, in conditions of a large number of irrelevant features, focusing on logistic regression. We develop a variational method for parameter estimation, and show an equivalence between two approximations recently proposed in the statistics literature. Building on previous work by A.Ng, we show the fractional norm regularised logistic regression enjoys a sample complexity that grows logarithmically with the data dimensions and polynomially with the number of relevant dimensions. In addition, extensive empirical testing indicates that fractional-norm regularisation is more suitable than L1 in cases when the number of relevant features is very small, and works very well despite a large number of irrelevant features.
BibTeX
@inproceedings{kaban2008learning,
  author = {Ata Kabán and Robert J. Durrant},
  title = {{Learning with Lq<1 vs L1-Norm Regularisation with Exponentially Many Irrelevant Features}},
  booktitle = {ECML/PKDD},
  year = {2008},
  doi = {10.1007/978-3-540-87479-9\_56},
}
Figure