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.
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.
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