ParaDeAl: Parallel Descent Algorithms for Sparse Statistics
math.OC, stat.ML
Submitted: 2026-11-02
Updated: 2026-11-02
Comments: 35 pages (56 with appendices), 9 tables (20), 4 figures (6)
License: http://creativecommons.org/licenses/by/4.0/
The gist: Best subset selection is a central problem in statistical regression, drawing increasing attention from the broader optimization and machine learning communities.
Abstract
Best subset selection is a central problem in statistical regression, drawing increasing attention from the broader optimization and machine learning communities. Solving the hard L0 sparsity constraint directly has been computationally challenging; as a result, most existing work proposes formulations which do not enforce the constraint, but instead use a mix of L0/L1/L2 penalties to encourage sparsity. Modern methods for solving such penalized formulations are tractable for p = 100,000, but give up direct control over sparsity. In this paper, we propose a two-stage proximal gradient descent-based approach which both enforces the sparsity constraint and incorporates L1/L2 penalties, leveraging GPUs for computational acceleration to find approximate solutions. Our method, ParaDeAl, offers the user the ability to select the problem hyperparameters, solves all configurations in parallel, and obtains solutions up to 15x faster than the best state-of-the-art CPU competitors while achieving almost identical test accuracy for the same support size for large (p > 100,000) synthetic and real-world datasets.
Sources
- PDLP: A Practical First-Order Method for Large-Scale Linear Programming
- Best Subset Selection via a Modern Optimization Lens
- Iterative Hard Thresholding for Compressed Sensing
- High-Performance Neural Networks for Visual Object Classification
- Fast Best Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms
- Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization
- L0Learn: A Scalable Package for Sparse Learning using L0 Regularization
- cuPDLP.jl: A GPU Implementation of Restarted Primal-Dual Hybrid Gradient for Linear Programming in Julia
- Subset Selection with Shrinkage: Sparse Linear Modeling when the SNR is low
- A GPU-accelerated Nonlinear Branch-and-Bound Framework for Sparse Linear Models
- Scikit-learn: Machine Learning in Python
- Running Markov Chain Monte Carlo on Modern Hardware and Software
- A Simple and Effective Pruning Approach for Large Language Models
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise