ParaDeAl: Parallel Descent Algorithms for Sparse Statistics

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.

Exact Asymptotics for the Harmonic Descent Chain and Extended Convergence Bounds for Recursive Statistics
Sean P. Svihla
arXiv1 Nov 2026PreprintCC BY 4.0Full textProbabilityarXiv
Sparse descent subspace-Newton thresholding algorithm for sparse optimization problems
Zhong-Feng Sun, Nan Meng, Yun-Bin Zhao
arXiv30 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Mirror descent algorithms with logarithmic barriers
Alberto De Marchi, Yura Malitsky, Adrien B. Taylor
arXiv26 Oct 2026PreprintCC BY 4.0Full textNumerical analysis & scientific computing Optimisation & controlarXiv
Generalization Analysis of Distributed Kernel-based Robust Gradient Descent Algorithms
Jun-Yi Meng, Zheng-Chu Guo, Yuan Mao
arXiv10 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEs ProbabilityarXiv
Globally Convergent Block Coordinate Descent Algorithms for Semi-Nonnegative Independent Component Analysis
Zhenyu Cai, Wentao Ding, Jianze Li +1
arXiv12 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{deng2026paradeal,
  title = {{ParaDeAl: Parallel Descent Algorithms for Sparse Statistics}},
  author = {Adam Deng and Rahul Mazumder},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.03529},
  eprint = {2611.03529},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.03529},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - ParaDeAl: Parallel Descent Algorithms for Sparse Statistics
AU  - Adam Deng
AU  - Rahul Mazumder
PY  - 2026
DA  - 2026/11/02
PB  - arXiv
DO  - 10.48550/arxiv.2611.03529
UR  - https://arxiv.org/abs/2611.03529
AB  - 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.
ER  -

Abstract

Related

Cite