A Highly Efficient Algorithm for Solving Exclusive Lasso Problems

Meixia Lin, Yancheng Yuan, Defeng Sun, Kim-Chuan TohOptim. Methods Softw 2023

TL;DR

This paper introduces a novel, highly efficient algorithm called PPDNA for solving "exclusive lasso" problems, a type of feature selection crucial for tasks like portfolio management and multi-task learning. PPDNA significantly outperforms existing methods in terms of speed and accuracy, especially for large-scale datasets.

What Problem Does This Paper Address?

The paper tackles the computational challenge of solving "exclusive lasso" models. This type of regularizer is valuable for feature selection because it encourages sparsity not only at the group level but also within groups, meaning it can select a diverse set of features even from a highly correlated group. This is particularly useful in applications like portfolio optimization where diversifying risk across and within sectors is key. However, the complex mathematical structure of the exclusive lasso regularizer makes it computationally difficult to handle, especially for high-dimensional datasets, hindering its practical application. Existing algorithms struggle to achieve moderate accuracy efficiently, and the proximal mapping (a key component for many optimization algorithms) of the exclusive lasso regularizer has not been well-studied or correctly derived.

Methods

The core contribution is a new algorithm called the Preconditioned Proximal Point Algorithm with Dual Newton method (PPDNA). This algorithm is designed to be highly efficient by leveraging a combination of techniques:

  • Dual Newton Method: This is a second-order optimization method that uses second-derivative information to converge faster. It's applied to a dual problem derived from the original optimization problem.
  • Proximal Point Algorithm (PPA): This is an iterative method that uses proximal operators. The paper introduces a preconditioned version of PPA, which includes an additional term that helps to improve convergence.
  • Systematic Study of Proximal Mapping: A significant part of the work involves deriving and analyzing the proximal mapping of the weighted exclusive lasso regularizer. This is crucial for the efficient implementation of many optimization algorithms, including PPDNA and first-order methods. The paper provides an O(n log n) procedure for this.
  • Generalized Jacobian: To enable the dual Newton method, the paper derives the generalized Jacobian of the proximal mapping, which is essential for handling the non-differentiable nature of the exclusive lasso regularizer.

Datasets

The paper uses synthetic datasets for evaluating the performance of PPDNA against other algorithms. These synthetic datasets are generated for:

  • Linear Regression: With varying numbers of observations (m), groups (l), and features per group (p).
  • Logistic Regression: Similar to linear regression, using synthetic data.

The paper also applies the exclusive lasso model to real-world applications:

  • Index Exchange-Traded Fund (ETF) Tracking: Using historical daily return data for stocks and the S&P 500 index.
  • Image Classification (MNIST): A multi-class classification task.
  • Text Classification (20 Newsgroups): Another multi-class classification task.

Key Insights and Ideas

  • The "Exclusive" Advantage: The exclusive lasso's ability to enforce intra-group sparsity is key to its superior performance in applications like portfolio diversification, where selecting a diverse set of assets within a sector is crucial.
  • Proximal Mapping is Key: The difficulty in solving exclusive lasso problems stems largely from the complexity of its proximal mapping. The paper's systematic derivation and efficient computation of this mapping are critical enablers for better algorithms.
  • Second-Order Methods Shine: While first-order methods are common, the paper demonstrates that a carefully designed second-order method (PPDNA) can achieve significantly better performance for exclusive lasso problems, especially at scale.
  • Generalized Jacobian for Non-Differentiability: Handling the non-smoothness of the exclusive lasso regularizer is essential. The paper's development of the generalized Jacobian is a crucial step for applying advanced optimization techniques like semismooth Newton methods.

Key Results

  • Superior Speed: PPDNA consistently outperforms other popular algorithms (ILSA, ADMM, APG, CD) in terms of computation time, often by orders of magnitude, especially for large-scale problems. For instance, in linear regression, PPDNA is at least 100 times faster than ADMM for large instances. In logistic regression, it can be up to 160 times faster.
  • High Accuracy: PPDNA achieves competitive or superior accuracy compared to other methods, even when they are given significantly more iterations or computation time.
  • Scalability: The algorithm demonstrates excellent scalability, performing well on datasets with up to 20,000 features.
  • Real-World Performance: In real-world applications like index tracking, the exclusive lasso model (solved by PPDNA) shows better out-of-sample performance than lasso or group lasso. For classification tasks, model (M2) using exclusive lasso demonstrates better feature selection by identifying fewer unique features while maintaining comparable accuracy.
  • Warm-Start Benefits: Using a warm-start strategy can further accelerate PPDNA and ADMM, with PPDNA showing a significant speedup (e.g., 8 times faster than ADMM on the 20 Newsgroups dataset).

Limitations and Future Work

  • Parameter Tuning: While PPDNA is shown to be robust, like most optimization algorithms, its performance can be sensitive to hyperparameter choices. The paper provides practical suggestions for parameter settings.
  • Theoretical Guarantees: The paper proves asymptotic superlinear convergence for PPDNA under certain conditions, but further theoretical analysis for specific problem classes might be beneficial.
  • Further Applications: The paper suggests that the developed methods and insights can be applied to other problems involving similar regularizers or optimization challenges. The authors also highlight the potential for further exploration of the exclusive lasso model in various machine learning and data analysis tasks.

Summary updated

Abstract

The exclusive lasso (also known as elitist lasso) regularizer has become popular recently due to its superior performance on intra-group feature selection. Its complex nature poses difficulties for the computation of high-dimensional machine learning models involving such a regularizer. In this paper, we propose a highly efficient dual Newton method based proximal point algorithm (PPDNA) for solving large-scale exclusive lasso models. 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 more practical. Extensive numerical results are presented to demonstrate the superior performance of the PPDNA against other popular numerical algorithms for solving the exclusive lasso problems.
BibTeX
@article{lin2023highly,
  author = {Meixia Lin and Yancheng Yuan and Defeng Sun and Kim-Chuan Toh},
  title = {{A Highly Efficient Algorithm for Solving Exclusive Lasso Problems}},
  journal = {Optim. Methods Softw.},
  year = {2023},
}
Figure