Abstract
The exclusive lasso (also known as elitist lasso) regularization has become popular recently due to its superior performance on structured sparsity. Its complex nature poses difficulties for the computation of high-dimensional machine learning models involving such a regularizer. In this paper, we propose an adaptive sieving (AS) strategy for generating solution paths of machine learning models with the exclusive lasso regularizer, wherein a sequence of reduced problems with much smaller sizes need to be solved. In order to solve these reduced problems, we propose a highly efficient dual Newton method based proximal point algorithm (PPDNA). As important ingredients, we systematically study the proximal mapping of the weighted exclusive lasso regularizer and the corresponding generalized Jacobian. These results also make popular first-order algorithms for solving exclusive lasso models practical. Various numerical experiments for the exclusive lasso models have demonstrated the effectiveness of the AS strategy for generating solution paths and the superior performance of the PPDNA.
Introduction
In modern machine learning, sparsity is a critical property for model interpretability and computational efficiency. While the standard Lasso provides general sparsity and the Group Lasso provides group-level sparsity, the Exclusive Lasso (or elitist lasso) introduces a unique structural constraint: it encourages competition within groups. This ensures that the model selects at least one representative from every predefined group while maintaining overall feature sparsity.
Despite its utility, the Exclusive Lasso is computationally demanding. Its mathematical structure is complex and non-separable, which prevents the application of standard "safe" screening rules used to discard irrelevant features early in the optimization process. For researchers attempting to generate a "solution path"—a sequence of models across varying regularization strengths ($\lambda$)—the computational cost in high-dimensional settings has historically been a significant bottleneck.
Methodology
This research addresses these computational challenges through a two-pronged framework combining a novel selection strategy with a high-performance optimization algorithm.
1. Adaptive Sieving (AS) Strategy
Instead of solving the massive original problem directly, the Adaptive Sieving strategy solves a sequence of much smaller "reduced" problems. By utilizing Karush-Kuhn-Tucker (KKT) optimality conditions, AS adaptively "sieves" the feature set to identify those most likely to be active in the final solution. Unlike traditional screening rules, AS is more flexible and does not require the regularizer to be positively homogeneous, making it highly effective for the exclusive lasso structure.
2. The PPDNA Algorithm
To solve the reduced problems generated by the AS strategy, the authors developed the Preconditioned Proximal Point Dual Newton Algorithm (PPDNA). While first-order methods like ADMM or Proximal Gradient methods are common, they often struggle with high-accuracy requirements and slow convergence. PPDNA is a second-order method that leverages the proximal mapping and the generalized Jacobian of the weighted exclusive lasso. By deriving these mathematical foundations, the authors enable the engine to achieve rapid, robust convergence even in non-smooth optimization landscapes.
Experimental Evaluation
The framework was evaluated across synthetic and real-world datasets to test scalability and practical utility:
- Large-Scale Synthetic Data: Linear and logistic regression simulations with up to 1,200,000 features.
- Index ETF Tracking: Stock price data from 3,074 US stocks categorized into 12 sectors, aimed at tracking the S&P 500.
- Image and Text Classification: The MNIST handwritten digit dataset and the 20 Newsgroups text dataset.
Key Insights
- Second-Order Superiority: The derivation of the generalized Jacobian proves that second-order Newton methods can significantly outperform first-order methods for these specific non-smooth problems.
- Sieving vs. Warm-Starting: While "warm-starting" (using the solution from one $\lambda$ to initialize the next) is standard practice, Adaptive Sieving proved far more efficient. It reduces the problem size so effectively that the reduced problem often matches the actual number of non-zero features in the final solution.
- Structural Advantage in Finance: In ETF tracking, the Exclusive Lasso outperformed standard Lasso and Group Lasso by forcing the model to select stocks from all 12 sectors, resulting in a more diversified and stable out-of-sample performance.
Results and Discussion
The numerical experiments demonstrated substantial improvements over existing benchmarks:
- Computational Speed: In large-scale synthetic tests, PPDNA was at least 100 times faster than ADMM.
- Path Generation Efficiency: The AS strategy was approximately 10 times more efficient than standard warm-start approaches for generating solution paths.
- Scalability: The algorithm successfully processed problems with over one million features on a standard workstation, completing in minutes tasks that took other methods hours or led to convergence failure.
- Accuracy: On MNIST and 20 Newsgroups, the proposed model achieved competitive accuracy while providing more interpretable and efficient feature selection.
Conclusion
The combination of Adaptive Sieving and the PPDNA algorithm makes high-dimensional Exclusive Lasso models practical for the first time. By providing the necessary mathematical foundations for the proximal mapping and generalized Jacobian, this work not only introduces a faster solver but also opens the door for improving other first-order algorithms in the field. Future work may involve extending this framework to non-convex loss functions and exploring even more complex mixed-norm regularizers.
Summary updated