Abstract
The exclusive lasso (or elitist lasso) has gained prominence for its ability to enforce group-level sparsity while simultaneously encouraging competition within groups. Despite its theoretical advantages, the computational complexity of solving exclusive lasso models at scale has limited its adoption. This paper presents a highly efficient dual Newton-based preconditioned proximal point algorithm (PPDNA) designed to address these challenges. By deriving a rigorous closed-form solution for the proximal mapping of the weighted exclusive lasso and its corresponding HS-Jacobian, we enable the use of a semismooth Newton method to solve the proximal subproblems. Numerical experiments on synthetic and real-world financial data demonstrate that PPDNA significantly outperforms state-of-the-art first-order methods in both speed and robustness.
Introduction
In high-dimensional statistics and machine learning, regularization is a fundamental tool for feature selection and model interpretability. While the standard Lasso promotes global sparsity and the Group Lasso promotes sparsity between predefined blocks of variables, the Exclusive Lasso addresses a different structural requirement: intra-group competition. In an exclusive lasso model, if one variable within a group is selected, the weights of other variables in the same group are suppressed. This is particularly useful in scenarios like portfolio optimization, where one might want to select a representative asset from various market sectors rather than entire sectors at once.
Historically, solving exclusive lasso problems has been computationally expensive. Most existing solvers rely on first-order methods like the Alternating Direction Method of Multipliers (ADMM) or Accelerated Proximal Gradient (APG) methods. While these are easy to implement, they often suffer from slow convergence rates on high-dimensional datasets and lack robustness when faced with small regularization parameters. This paper introduces PPDNA, a second-order optimization framework that bridges the gap between theoretical elegance and practical scalability.
Methodology
The proposed PPDNA framework is built upon three mathematical pillars that allow it to achieve superlinear convergence.
1. Rigorous Proximal Mapping
A critical component of proximal algorithms is the proximal mapping of the regularizer. We provide the first mathematically rigorous proof for the closed-form solution of the proximal mapping for the weighted exclusive lasso. This eliminates the need for the expensive iterative sub-routines previously required by other researchers, significantly reducing the computational cost per iteration.
2. The PPA Framework
We utilize a Preconditioned Proximal Point Algorithm (PPA) as the outer optimization loop. PPA is renowned for its stability and fast convergence, but its efficiency depends entirely on how quickly one can solve the inner subproblem.
3. Semismooth Newton (SSN) and the HS-Jacobian
To solve the PPA subproblem, we apply a Semismooth Newton method to its dual. This requires the derivation of the HS-Jacobian (a generalized derivative) for the exclusive lasso's proximal mapping. By utilizing second-order curvature information, the SSN method can take much larger and more effective steps toward the optimum than first-order methods, even when dealing with the non-differentiable points inherent in sparsity-inducing penalties.
Experimental Evaluation
Synthetic Benchmarks
We evaluated PPDNA against standard solvers using large-scale linear and logistic regression tasks. In tests involving up to 20,000 features, PPDNA demonstrated remarkable efficiency. For instance, in high-dimensional linear regression, PPDNA reached convergence in 27 to 36 seconds, while ADMM required over 8 minutes. In larger instances, PPDNA completed the task in under two minutes, whereas ADMM failed to reach the target accuracy within an hour.
Real-World Application: ETF Tracking
To test the algorithm in a practical setting, we applied it to an Index Tracking problem using 2018 US stock market data from Yahoo Finance. The dataset included 3,074 stocks categorized into 12 sectors. The goal was to construct a sparse portfolio that tracks the S&P 500 index.
The Exclusive Lasso, solved via PPDNA, proved superior to both standard Lasso and Group Lasso. By forcing the model to select representative stocks from every sector (intra-group competition) rather than ignoring entire sectors, the resulting ETF achieved a cumulative return curve that closely mirrored the actual S&P 500 index.
Discussion and Conclusion
The primary insight of this work is that the additional mathematical complexity required to derive Jacobians for second-order methods is well worth the investment for structured sparsity problems. PPDNA is not only faster than first-order alternatives but also significantly more robust to changes in the regularization parameter ($\lambda$). While first-order methods typically "zigzag" and slow down as $\lambda$ decreases, PPDNA maintains stable performance.
Future work may involve extending this dual Newton framework to more complex loss functions, such as those found in deep learning, and optimizing memory management for extremely high-dimensional problems involving millions of features. For now, PPDNA provides a powerful and reliable tool for researchers and practitioners looking to leverage the unique benefits of the Exclusive Lasso at scale.
Summary updated