Adaptive sieving: A dimension reduction technique for sparse optimization problems

Yancheng Yuan, Meixia Lin, Defeng Sun, Kim-Chuan TohMath. Program. Comput 2023

Abstract

In this paper, we propose an adaptive sieving (AS) strategy for solving general sparse machine learning models by effectively exploring the intrinsic sparsity of the solutions, wherein only a sequence of reduced problems with much smaller sizes need to be solved. We further apply the proposed AS strategy to generate solution paths for large-scale sparse optimization problems efficiently. We establish the theoretical guarantees for the proposed AS strategy including its finite termination property. Extensive numerical experiments are presented in this paper to demonstrate the effectiveness and flexibility of the AS strategy to solve large-scale machine learning models.

Introduction

In modern data science, researchers frequently encounter "high-dimensional, sparse" problems where the number of features ($n$) significantly exceeds the number of observations ($m$). While models like the Lasso are designed to handle such data by identifying a small subset of relevant features, solving these models at scale—often involving millions of variables—is computationally demanding.

Existing approaches to mitigate this burden often rely on "feature screening" rules. These rules attempt to predict which features will have zero coefficients in the final solution and discard them early to reduce the problem size. However, traditional screening methods suffer from three primary drawbacks: they are often rigid (tailored to specific models like Lasso), overly conservative (leaving the reduced problem still too large), and typically require sub-problems to be solved with unrealistic exactness. To address these challenges, we introduce Adaptive Sieving (AS), a flexible and aggressive framework for dimension reduction in sparse optimization.

The Adaptive Sieving Strategy

The core of our approach is the Adaptive Sieving Strategy (Algorithm 1). Rather than tackling the full $n$-dimensional problem simultaneously, AS iteratively explores the feature space by solving a sequence of much smaller "reduced" problems.

The Iterative Process

  1. Initialization: The process begins with a small set of "active" features, typically selected using a correlation-based heuristic (e.g., the top 10 features most correlated with the target variable).
  2. Inexact Sub-problem Solving: The optimization problem is solved using only the active features. A critical advantage of AS is that these sub-problems only need to be solved inexactly, which significantly reduces computational overhead.
  3. Residual Checking: We utilize a "proximal residual"—a mathematical diagnostic tool—to determine if any features currently excluded from the active set are actually significant.
  4. Sieving and Updating: If the current solution does not meet global optimality criteria, the features with the largest residuals are "sieved" and added to the active set for the next iteration.
  5. Termination: The process repeats until the global optimality conditions are satisfied.

Furthermore, we extend this logic to Algorithm 2, which efficiently generates "solution paths." This is particularly useful for machine learning workflows where models must be evaluated across a range of sparsity levels for cross-validation.

Key Insights and Theoretical Guarantees

Adaptive Sieving is designed as a "wrapper" strategy. It is not a standalone solver but a framework that can enhance existing algorithms such as ADMM, Proximal Gradient, or Newton-type methods. By focusing computational effort on a small fraction of the total features, it makes slow algorithms fast and fast algorithms even faster.

Unlike "safe" screening rules that are often too cautious to discard features, AS is "aggressive." While it might initially ignore an active feature, the proximal residual check ensures that any important features are eventually identified and incorporated. We provide a rigorous proof of finite termination, ensuring that the algorithm will converge to the correct global solution in a finite number of steps, even when sub-problems are solved inexactly.

One of the most significant advantages of AS is its flexibility. It can handle complex regularizers where traditional screening rules often fail, such as SLOPE (which involves non-separable sorted L1 norms) and Exclusive Lasso (which is not positively homogeneous).

Numerical Results

We evaluated the AS strategy against massive synthetic and real-world datasets, including genomics data (bcTCGA), climate variables (NCEP/NCAR reanalysis), and high-dimensional synthetic sets with up to 1,200,000 features.

  • Significant Speedups: For Lasso models, AS accelerated the state-of-the-art SSNAL solver by up to 43 times. For Sparse Group Lasso, speedups reached as high as 54 times.
  • Memory Efficiency: In tests involving 1.2 million features, standard "warm-start" methods often failed due to memory constraints. In contrast, the AS strategy completed the task in under 12 minutes by maintaining a small active set.
  • Effective Dimension Reduction: In many instances, the reduced problems involved fewer than 1,000 features, despite the original problem containing over a million variables.
  • Competitive Edge: AS consistently outperformed established benchmarks, including Matlab’s built-in lasso function and the Enhanced Dual Polytope Projection (EDPP) screening rule, in both execution speed and objective value accuracy.

Limitations and Future Work

While highly effective, the AS strategy has specific requirements. It relies on the ability to compute the "proximal mapping" of the regularizer efficiently. While this is standard for most popular models, it may be a bottleneck for highly exotic regularizers. Additionally, our current theoretical guarantees are established for convex problems; while the strategy may function for non-convex sparse optimization, its convergence behavior in those contexts remains a subject for future research. Finally, while the algorithm is robust, the efficiency of the first few iterations can be sensitive to the initial feature set selection.

Conclusion

Adaptive Sieving represents a significant step forward in high-dimensional optimization. By combining an aggressive dimension reduction strategy with rigorous theoretical guarantees, it allows researchers to solve large-scale sparse learning problems that were previously computationally prohibitive.

Summary updated

Abstract

In this paper, we propose an adaptive sieving (AS) strategy for solving general sparse machine learning models by effectively exploring the intrinsic sparsity of the solutions, wherein only a sequence of reduced problems with much smaller sizes need to be solved. We further apply the proposed AS strategy to generate solution paths for large-scale sparse optimization problems efficiently. We establish the theoretical guarantees for the proposed AS strategy including its finite termination property. Extensive numerical experiments are presented in this paper to demonstrate the effectiveness and flexibility of the AS strategy to solve large-scale machine learning models.
BibTeX
@article{yuan2023adaptive,
  author = {Yancheng Yuan and Meixia Lin and Defeng Sun and Kim-Chuan Toh},
  title = {{Adaptive sieving: A dimension reduction technique for sparse optimization problems}},
  journal = {Math. Program. Comput.},
  year = {2023},
}
Figure