betaFeedback

WorksMathematics

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.

Introduction

Existing Work

The proliferation of high-dimensional data has increased scientific interest in linear and sparse regression. We start with the standard linear regression model y=Xβ+ϵy = X\beta+ \epsilon, where X∈Rn×pX \in\mathbb{R}^{n \times p} is the data matrix of nn samples with pp features, y∈Rny \in\mathbb{R}^n is the response vector, β∈Rp\beta\in\mathbb{R}^p is the regression coefficients vector, and ϵ∈Rn\epsilon\in\mathbb{R}^n is an errors vector. We assume that each column of XX has been standardized to mean 0 and L2L_2-norm 1. For explainability and parsimony reasons, it is often desirable to sparsify β\beta. One such formulation is the best subsets estimator [25], which solves the problem

min⁡βL(β)≔∥y−Xβ∥22s.t.∥β∥0≤k,(1)\min_{\beta} L(\beta) \coloneqq\lVert y - X\beta\rVert_2^2 \quad\text{s.t.} \quad\lVert\beta\rVert_0 \le k, \tag*{(1)}

where the L0L_0-norm ∥β∥0\lVert\beta\rVert_0 counts the number of nonzeros in β\beta. Exact solutions to Problem 1 can be computed through a mixed integer optimization (MIO) approach in [6], but doing so is compute-intensive. Near-optimal solutions can be found for p≈103p \approx10^3 in several minutes, with significantly worse runtimes as kk increases. Alternatively, one can get approximate solutions to Problem (1) using iterative hard thresholding (IHT) [9, 6], but IHT also suffers from computational inefficiency due to the large matrix multiplications and convergence slowness of gradient descent (GD).

One related line of work focuses on convex proxies for Problem 1 without the L0L_0 constraint, including L1L_1 aka Lasso [37] and L1+L2L_1+L_2 (Elastic Net) (Zou and Hastie (2005)) which is implemented in glmnet (Buhreny and Huang (2011)). Another line of work considers a penalized version for L0L_0 with additional regularizers, such as L0+L1L_0+L_1 and L0+L2L_0+L_2 [18], implemented in L0Learn as approximate procedures that produce good solutions. Such procedures, relying on coordinate descent, are generally much faster than the IHT procedures discussed in [6]. Additionally, L0BnB [19] proposes a tailored branch-and-bound procedure for solving the L0+L2L0+L2 problem exactly. While these formulations are computationally appealing, they do not directly control the support size of β\beta, which Problem (1) does.

In recent years, graphical processing units (GPUs) have gained popularity due to their ability to perform magnitudes more computations than CPUs in the same time [33]. GPUs are already deeply integrated into machine learning (ML) contexts, with tasks like training neural networks [12] and deep learning for high-dimensional data [26]. Additionally, GPUs are used in optimization problems and methods, like linear programming [22, 34] (Świrydowicz et al. 2022) and concurrent work on Branch and Bound [24]. GPU-based methods have been proposed for the noiseless version of Problem (1), compressed sensing [8], which finds the minimum ∥β∥0\lVert\beta\rVert_0 such that satisfies y=Xβy = X\beta exactly.

Approach

Motivated by earlier work [23], we consider the estimator

min⁡βf(β)=def(L(β)+λ1∥β∥1+λ2∥β∥22)s.t.∥β∥0≤k.(2)\min_{\beta} f(\beta) \mathrel{\mathop{=}^{\mathrm{def}}} \left(L(\beta) + \lambda_1\lVert\beta\rVert_1 + \lambda_2\lVert\beta\rVert_2^2\right) \quad\text{s.t.} \quad\lVert\beta\rVert_0 \le k. \tag*{(2)}

Here λ1≥0\lambda_1 \ge0 and λ2≥0\lambda_2 \ge0 are regularization parameters controlling the L1 and L2 norms of β\beta and can help in terms of out-of-sample prediction performance, while the constraint ∥β∥0≤k\lVert\beta\rVert_0 \le k controls the number of nonzero coefficients in β\beta. We obtain feasible approximate solutions to Problem (2) using a two-stage approach: support selection followed by coefficient value optimization, also known as value modification. We use a proximal gradient descent-type procedure [6] to compute a good support for Problem (2), which reduces to IHT when λ1,λ2=0\lambda_1,\lambda_2 = 0. After finding the support, we modify the values of the nonzero coefficients of β\beta by solving Problem (2) restricted to this support. In the special case λ1=0\lambda_1 = 0, value fine-tuning is computed using preconditioned conjugate gradient (PCG) [32], which is generally faster than support-restricted GD. (We do not calculate the exact solution directly using inverses because it is difficult to parallelize over different supports and λ2\lambda_2s, and computing the inverse is expensive.) When pp is large (p≥104p \ge10^4), we also employ an active set-type procedure inspired by Friedman et al. [17] and Hazimeh and Mazumder [18] to achieve computational speedups.

To accelerate computation we use GPUs, as our approach is well-suited for exploiting two types of parallelism offered by GPUs. The foremost type is matrix-matrix and matrix-vector products, forming the backbone of our approach. Moreover, GPUs can parallelize across multiple instances of (k,λ1,λ2,η,βo)(k,\lambda_1,\lambda_2,\eta,\beta_o) values (βo\beta_o means the starting β\beta)—collectively, hyperparameters—solving Problem (2) simultaneously for many hyperparameter configurations. In sparse regression, it is desirable to obtain solutions for multiple (λ1,λ2,k)(\lambda_1,\lambda_2,k)—collectively, regularization hyperparameters—to assess the effects of different imposed conditions on the resulting β\beta and obtain more accurate β\betas for regression. Varying βo\beta_o and learning rate η\eta is also important because for a given (λ1,λ2,k)(\lambda_1,\lambda_2,k), the quality of solution depends on βo\beta_o and η\eta, and selecting many βos\beta_os and η\etas offers us flexibility to better optimize Problem 2. We term our collective methodology ParaDeAl for Parallel Descent Algorithms.

Contributions

Our contributions in this paper are as follows:

  • Massively Parallel Sparse Regression: We propose a GPU-compatible tensor-based framework, ParaDeAl, which obtains good solutions to Problem (2) by parallelizing across the entire hyperparameter space (λ1,λ2,k,βo,η)(\lambda_1,\lambda_2,k,\beta_o,\eta). Unlike existing packages, which are CPU-based and rely on procedures that can only solve problem instances sequentially or iteratively, we simultaneously solve up to thousands of problem candidates.

  • Scalability Beyond Existing Solvers: Our method scales to solve 1000 simultaneous problem instances for (n≈104,p≈105)(n \approx10^4,p \approx10^5) or a single instance for (n≈105,p≈106)(n \approx10^5,p \approx10^6) on a single L40S GPU (48GB storage) within

an hour. The latter problem is larger by one to two orders of magnitude than what existing solvers can solve. The former setup takes the best existing algorithms over 40x as long as ParaDeAl to solve.

Paper Structure

We present the full ParaDeAl architecture, with algorithmic pseudocode on specific parallelization procedures, in Section 2. We then address a set of computational challenges and propose solutions in Section 3. ParaDeAl’s methodological edge over iterative counterparts is reported in Section 4, while ParaDeAl’s speed advantage and comparable accuracy vis-a-vis sparse regression solvers is demonstrated in Section 5 through a series of tests involving synthetic and real-world datasets. We offer concluding remarks in 6. To provide completeness, and due to space limits, we explore certain implementation experiments and results in the appendices.

Notation

Let S=S(β)\mathcal{S}=S(\beta) denote the support of β\beta, i.e. the set of indices of β\beta for which the element value is not zero.

For any set T\mathcal{T} which contains a subset of the pp features, let PT(β)P_{\mathcal{T}}(\beta) denote the projection of β\beta onto the elements of T\mathcal{T}, so that βi=0\beta_i=0 if i∉Ti\notin\mathcal{T}. Let RT(β)R_{\mathcal{T}}(\beta) denote the compressed vector of length ∣T∣|\mathcal{T}| consisting only of elements of β\beta whose features are within T\mathcal{T}. Similarly, let RT(X,β)R_{\mathcal{T}}(X,\beta) denote a submatrix of XX consisting only of the columns corresponding to features of β\beta within T\mathcal{T}.

We regard λ1,λ2,k\lambda_1,\lambda_2,k as regularization hyperparameters; and λ1,λ2,k,β,η\lambda_1,\lambda_2,k,\beta,\eta as hyperparameters collectively. We define one problem instance, with a particular (λ1,λ2,k,βo,η)(\lambda_1,\lambda_2,k,\beta_o,\eta), as a configuration. Each configuration corresponds to its own β\beta-trajectory; note that the number of configurations, which equals the number of β\beta-trajectories, may exceed the number of different initial β\beta values chosen.

Let C\mathcal{C} represent the set of all hyperparameter configurations, where each configuration is a list of 5 hyperparameter values (k,λ1,λ2,η,β)(k,\lambda_1,\lambda_2,\eta,\beta). For a particular hyperparameter aa, let Ca\mathcal{C}_a be the set of different values. Define CaC_a as ∣Ca∣|C_a|, i.e. the number of different values hyperparameter aa takes; similarly, define ∏C\prod C as ∣C∣|C|. An element of C\mathcal{C} is denoted as c∈Cc\in\mathcal{C}; note that c=(k,λ1,λ2,η,β)c=(k,\lambda_1,\lambda_2,\eta,\beta) for some values of those hyperparameters.

ParaDeAl Architecture

In this section, we describe our algorithm for ParaDeAl, the motivation for parallelizing over problem configurations, and GPU-friendly ways to parallelize. In order to achieve parallelism, we may have to introduce redundancies in computation. We thus observe a GPU workflow tradeoff between uninterrupted vectorization and resizing data structures to minimize computation.

Preliminaries

Consider our optimization formulation in Problem (2). Define

FD(β)=L(β)+λ2∥β∥22(3)F_D(\beta)=L(\beta)+\lambda_2\|\beta\|_2^2 \tag*{(3)}

as the convex differentiable portion of F(β)F(\beta). We observe that FDF_D is a L0L_0-smooth convex function, satisfying

∥∇FD(β)−∇FD(α)∥2≤L0∥β−α∥2∀β,α∈Rp(4)\|\nabla F_D(\beta)-\nabla F_D(\alpha)\|_2\leq L_0\|\beta-\alpha\|_2\quad\forall\beta,\alpha\in\mathbb{R}^p \tag*{(4)}

where L0=2(σmax⁡2(X)+λ2)L_0=2(\sigma_{\max}^2(X)+\lambda_2) and σmax⁡(X)\sigma_{\max}(X) refers to the largest singular value of XX. Using the Descent Lemma {(citep}(Nesterov (2004))}, for any L′≥L0L'\geq L_0, we obtain the following upper bound on FD(β)F_D(\beta):

FD(β)≤FD(α)+⟨∇FD(α),β−α⟩+L′2∥β−α∥22=:UL′(β,α)∀β,α∈Rp.(5)F_D(\beta)\leq F_D(\alpha)+\langle\nabla F_D(\alpha),\beta-\alpha\rangle+\frac{L'}{2}\|\beta-\alpha\|_2^2=:U_{L'}(\beta,\alpha)\quad\forall\beta,\alpha\in\mathbb{R}^p. \tag*{(5)}

Instead of directly minimizing Problem 2, we minimize a local model of F(β)=FD(β)+λ1∥β∥1F(\beta) = F_D(\beta) + \lambda_1\|\beta\|_1 around candidate point α\alpha. This leads to the following optimization problem:

min⁡∥β∥0≤kUL′(β,α)+λ1∥β∥1=min⁡∥β∥0≤kFD(α)+L′2∥β−(α−1L′∇FD(α))∥22−12L′∥∇FD(α)∥22+λ1∥β∥1(6)\min_{\|\beta\|_0 \le k} U_{L'}(\beta,\alpha) + \lambda_1\|\beta\|_1 = \min_{\|\beta\|_0 \le k} F_D(\alpha) + \frac{L'}{2}\left\|\beta- \left(\alpha- \frac{1}{L'}\nabla F_D(\alpha)\right)\right\|_2^2 - \frac{1}{2L'}\|\nabla F_D(\alpha)\|_2^2 + \lambda_1\|\beta\|_1 \tag*{(6)}

which is equivalent to solving

References

  1. [1]David Applegate, Mateo Díaz, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan O’Donoghue, and Warren Schudy. Pdlp: A practical first-order method for large-scale linear programming, 2026. URL https://arxiv.org/abs/2501.07018.
  2. [2]Hé​dy Attouch, Jérôme Bolte, and Benar Fux Svaiter. Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods. Mathematical Programming, 137(1–2):91–129, 2013. doi: 10.1007/s10107-011-0484-9.
  3. [3]Amir Beck. First-Order Methods in Optimization. MOS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2017. doi: 10.1137/1.9781611974997.DOI
  4. [4]Amir Beck and Marc Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1):183–202, 2009.DOI
  5. [5]Quentin Bertrand, Quentin Klopfenstein, Pierre-Antoine Bannier, Gauthier Gidel, and Mathurin Massias. Beyond L1: Faster and better sparse models with skglm. In Advances in Neural Information Processing Systems, volume 35, 2022.arxiv.org/abs/2204.07826
  6. [6]Dimitris Bertsimas, Angela King, and Rahul Mazumder. Best subset selection via a modern optimization lens, 2015. URL https://arxiv.org/abs/1507.03133.
  7. [7]Dimitris Bertsimas, Angela King, and Rahul Mazumder. Best subset selection via a modern optimization lens. The Annals of Statistics, 44(2):813–852, 2016. doi: 10.1214/15-AOS1388.DOI
  8. [8]Jeffrey D Blanchard and Jared Tanner. Gpu accelerated greedy algorithms for compressed sensing. Mathematical Programming Computation, 5:267–304, 2013. URL https://link.springer.com/article/10.1007/s12532-013-0056-5.DOI
  9. [9]Thomas Blumensath and Mike E. Davies. Iterative hard thresholding for compressed sensing, 2008. URL https://arxiv.org/abs/0805.0510.
  10. [11]Centers for Disease Control and Prevention, National Center for Health Statistics. National health and nutrition examination survey data, 2015–2016 and 2017–2018. https://www.cdc.gov/nchs/nhanes/, 2020.
  11. [12]Dan C. Cireşan, Ueli Meier, Jonathan Masci, Luca M. Gambardella, and Jürgen Schmidhuber. High-performance neural networks for visual object classification. arXiv preprint arXiv:1102.0183, 2011.arxiv.org/abs/1102.0183
  12. [13]John Clore, Krzysztof Cios, Jon DeShazo, and Beata Strack. Diabetes 130-US hospitals for years 1999–2008. UCI Machine Learning Repository, 2014. URL https://archive.ics.uci.edu/dataset/296/diabetes+130-us+hospitals+for+years+1999–2008.
  13. [14]Patrick L. Combettes and Valérie R. Wajs. Signal recovery by proximal forward-backward splitting. Multiscale Modeling & Simulation, 4(4):1168–1200, 2005. doi: 10.1137/050626090.DOI
  14. [15]Saverio De Vito. Air quality. UCI Machine Learning Repository, 2008. URL https://archive.ics.uci.edu/dataset/360/air+quality.
  15. [16]Saverio De Vito, Ettore Massera, Marco Piga, Luca Martinotto, and Girolamo Di Francia. On field calibration of an electronic nose for benzene estimation in an urban pollution monitoring scenario. Sensors and Actuators B: Chemical, 129(2):750–757, 2008. doi: 10.1016/j.snb.2007.09.060.DOI
  16. [17]Jerome Friedman, Trevor Hastie, and Robert Tibshirani. Regularization paths for generalized linear models via coordinate descent. Journal of Statistical Software, 33(1):1–22, 2010. doi: 10.18637/jss.v033.i01.DOI
  17. [18]Hussein Hazimeh and Rahul Mazumder. Fast best subset selection: Coordinate descent and local combinatorial optimization algorithms, 2020. URL https://arxiv.org/abs/1803.01454.
  18. [19]Hussein Hazimeh, Rahul Mazumder, and Ali Saab. Sparse regression at scale: Branch-and-bound rooted in first-order optimization, 2021. URL https://arxiv.org/abs/2004.06152.
  19. [20]Hussein Hazimeh, Rahul Mazumder, and Tim Nonet. L0learn: A scalable package for sparse learning using l0 regularization, 2023. URL https://arxiv.org/abs/2202.04820.
  20. [21]Florian Huber et al. Weather prediction dataset. Zenodo, 2021.
  21. [22]Haihao Lu and Jinwen Yang. cupdlp.jl: A gpu implementation of restarted primal-dual hybrid gradient for linear programming in julia, 2024. URL https://arxiv.org/abs/2311.12180.
  22. [23]Rahul Mazumder, Peter Radchenko, and Antoine Dedieu. Subset selection with shrinkage: Sparse linear modeling when the snr is low, 2022. URL https://arxiv.org/abs/1708.03288.
  23. [24]Xiang Meng, Ryan Lucas, and Rahul Mazumder. A gpu-accelerated nonlinear branch-and-bound framework for sparse linear models, 2026. URL https://arxiv.org/abs/2602.04551.
  24. [25]Alan Miller. Subset Selection in Regression. Chapman and Hall/CRC, 2 edition, 2002. doi: 10.1201/9781420035933. URL https://doi.org/10.1201/9781420035933.
  25. [26]Sparsh Mittal and Shraiysh Vaishay. A survey of techniques for optimizing deep learning on gpus. Journal of Systems Architecture, 99:101635, 2019. doi: 10.1016/j.sysarc.2019.101635.DOI
  26. [28]Brendan O’Donoghue and Emmanuel Candès. Adaptive restart for accelerated gradient schemes. Foundations of Computational Mathematics, 15(3):715–732, 2015.
  27. [29]Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Andreas Müller, Joel Nothman, Gilles Louppe, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake Vanderplas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Matthieu Perrot, and Édouard Duchesnay. Scikit-learn: Machine learning in python, 2018. URL https://arxiv.org/abs/1201.0490.
  28. [31]Michael Redmond and Alok Baveja. A data-driven software tool for enabling cooperative information sharing among police departments. European Journal of Operational Research, 141(3):660–678, 2002. doi: 10.1016/S0377-2217(01)00264-8.DOI
  29. [32]Jonathan R Shewchuk. An introduction to the conjugate gradient method without the agonizing pain. Technical report, Carnegie Mellon University, USA, 1994.
  30. [33]Pavel Sountsov, Colin Carroll, and Matthew D. Hoffman. Running markov chain monte carlo on modern hardware and software, 2024. URL https://arxiv.org/abs/2411.04260.
  31. [34]Daniele G. Spampinato and Anne C. Elster. Linear optimization on modern gpus. In 2009 IEEE International Symposium on Parallel & Distributed Processing (IPDPS), pages 1–8. IEEE, May 2009. ISBN 978-1-4244-3751-1. doi: 10.1109/IPDPS.2009.5161106.DOI
  32. [35]Beata Strack, Jonathan P. DeShazo, Chris Gennings, Juan L. Olmo, Sebastian Ventura, Krzysztof J. Cios, and John N. Clore. Impact of HbA1c measurement on hospital readmission rates: Analysis of 70,000 clinical database patient records. BioMed Research International, 2014:781670, 2014. doi: 10.1155/2014/781670.DOI
  33. [36]Mingjie Sun, Zhuang Liu, Anna Bair, and J. Zico Kolter. A simple and effective pruning approach for large language models, 2024. URL https://arxiv.org/abs/2306.11695.
  34. [37]Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society. Series B (Methodological), 58(1):267–288, 1996. ISSN 00359246. URL http://www.jstor.org/stable/2346178.
  35. [38]Robert Tibshirani, Jacob Bien, Jerome Friedman, Trevor Hastie, Noah Simon, Jonathan Taylor, and Ryan J. Tibshirani. Strong rules for discarding predictors in lasso-type problems. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 74(2):245–266, 2012.pubmed.ncbi.nlm.nih.gov/25506256

Paper details

vlnc:W_kayhv2cf
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents