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 y = X β + ϵ , where X ∈ R n × p X \in\mathbb{R}^{n \times p} X ∈ R n × p is the data matrix of n n n samples with p p p features, y ∈ R n y \in\mathbb{R}^n y ∈ R n is the response vector, β ∈ R p \beta\in\mathbb{R}^p β ∈ R p is the regression coefficients vector, and ϵ ∈ R n \epsilon\in\mathbb{R}^n ϵ ∈ R n is an errors vector. We assume that each column of X X X has been standardized to mean 0 and L 2 L_2 L 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 β ∥ 2 2 s.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)} β min L ( β ) : = ∥ y − X β ∥ 2 2 s.t. ∥ β ∥ 0 ≤ k , (1)
where the L 0 L_0 L 0 -norm ∥ β ∥ 0 \lVert\beta\rVert_0 ∥ β ∥ 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 ≈ 10 3 p \approx10^3 p ≈ 1 0 3 in several minutes, with significantly worse runtimes as k k k 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 L 0 L_0 L 0 constraint, including L 1 L_1 L 1 aka Lasso [37 ] and L 1 + L 2 L_1+L_2 L 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 L 0 L_0 L 0 with additional regularizers, such as L 0 + L 1 L_0+L_1 L 0 + L 1 and L 0 + L 2 L_0+L_2 L 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 L 0 + L 2 L0+L2 L 0 + L 2 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 ∥ β ∥ 0 such that satisfies y = X β y = X\beta y = X β exactly.
Approach
Motivated by earlier work [23 ] , we consider the estimator
min β f ( β ) = d e f ( L ( β ) + λ 1 ∥ β ∥ 1 + λ 2 ∥ β ∥ 2 2 ) 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)} β min f ( β ) = def ( L ( β ) + λ 1 ∥ β ∥ 1 + λ 2 ∥ β ∥ 2 2 ) s.t. ∥ β ∥ 0 ≤ k . (2)
Here λ 1 ≥ 0 \lambda_1 \ge0 λ 1 ≥ 0 and λ 2 ≥ 0 \lambda_2 \ge0 λ 2 ≥ 0 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 ∥ β ∥ 0 ≤ 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 λ 1 , λ 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 λ 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_2 λ 2 s, and computing the inverse is expensive.) When p p p is large (p ≥ 10 4 p \ge10^4 p ≥ 1 0 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) ( k , λ 1 , λ 2 , η , β o ) values (β o \beta_o β 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) ( λ 1 , λ 2 , k ) —collectively, regularization hyperparameters—to assess the effects of different imposed conditions on the resulting β \beta β and obtain more accurate β \beta β s for regression. Varying β o \beta_o β o and learning rate η \eta η is also important because for a given ( λ 1 , λ 2 , k ) (\lambda_1,\lambda_2,k) ( λ 1 , λ 2 , k ) , the quality of solution depends on β o \beta_o β o and η \eta η , and selecting many β o s \beta_os β o s and η \eta η s 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) ( λ 1 , λ 2 , k , β o , η ) . 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 ≈ 10 4 , p ≈ 10 5 ) (n \approx10^4,p \approx10^5) ( n ≈ 1 0 4 , p ≈ 1 0 5 ) or a single instance for ( n ≈ 10 5 , p ≈ 10 6 ) (n \approx10^5,p \approx10^6) ( n ≈ 1 0 5 , p ≈ 1 0 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) S = S ( β ) 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} T which contains a subset of the p p p features, let P T ( β ) P_{\mathcal{T}}(\beta) P T ( β ) denote the projection of β \beta β onto the elements of T \mathcal{T} T , so that β i = 0 \beta_i=0 β i = 0 if i ∉ T i\notin\mathcal{T} i ∈ / T . Let R T ( β ) R_{\mathcal{T}}(\beta) R T ( β ) denote the compressed vector of length ∣ T ∣ |\mathcal{T}| ∣ T ∣ consisting only of elements of β \beta β whose features are within T \mathcal{T} T . Similarly, let R T ( X , β ) R_{\mathcal{T}}(X,\beta) R T ( X , β ) denote a submatrix of X X X consisting only of the columns corresponding to features of β \beta β within T \mathcal{T} T .
We regard λ 1 , λ 2 , k \lambda_1,\lambda_2,k λ 1 , λ 2 , k as regularization hyperparameters; and λ 1 , λ 2 , k , β , η \lambda_1,\lambda_2,k,\beta,\eta λ 1 , λ 2 , k , β , η as hyperparameters collectively. We define one problem instance, with a particular ( λ 1 , λ 2 , k , β o , η ) (\lambda_1,\lambda_2,k,\beta_o,\eta) ( λ 1 , λ 2 , k , β o , η ) , 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} 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) ( k , λ 1 , λ 2 , η , β ) . For a particular hyperparameter a a a , let C a \mathcal{C}_a C a be the set of different values. Define C a C_a C a as ∣ C a ∣ |C_a| ∣ C a ∣ , i.e. the number of different values hyperparameter a a a takes; similarly, define ∏ C \prod C ∏ C as ∣ C ∣ |C| ∣ C ∣ . An element of C \mathcal{C} C is denoted as c ∈ C c\in\mathcal{C} c ∈ C ; note that c = ( k , λ 1 , λ 2 , η , β ) c=(k,\lambda_1,\lambda_2,\eta,\beta) c = ( k , λ 1 , λ 2 , η , β ) 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
F D ( β ) = L ( β ) + λ 2 ∥ β ∥ 2 2 (3) F_D(\beta)=L(\beta)+\lambda_2\|\beta\|_2^2 \tag*{(3)} F D ( β ) = L ( β ) + λ 2 ∥ β ∥ 2 2 (3)
as the convex differentiable portion of F ( β ) F(\beta) F ( β ) . We observe that F D F_D F D is a L 0 L_0 L 0 -smooth convex function, satisfying
∥ ∇ F D ( β ) − ∇ F D ( α ) ∥ 2 ≤ L 0 ∥ β − α ∥ 2 ∀ β , α ∈ R p (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)} ∥∇ F D ( β ) − ∇ F D ( α ) ∥ 2 ≤ L 0 ∥ β − α ∥ 2 ∀ β , α ∈ R p (4)
where L 0 = 2 ( σ max 2 ( X ) + λ 2 ) L_0=2(\sigma_{\max}^2(X)+\lambda_2) L 0 = 2 ( σ m a x 2 ( X ) + λ 2 ) and σ max ( X ) \sigma_{\max}(X) σ m a x ( X ) refers to the largest singular value of X X X . Using the Descent Lemma {(citep}(Nesterov (2004))}, for any L ′ ≥ L 0 L'\geq L_0 L ′ ≥ L 0 , we obtain the following upper bound on F D ( β ) F_D(\beta) F D ( β ) :
F D ( β ) ≤ F D ( α ) + ⟨ ∇ F D ( α ) , β − α ⟩ + L ′ 2 ∥ β − α ∥ 2 2 = : U L ′ ( β , α ) ∀ β , α ∈ R p . (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)} F D ( β ) ≤ F D ( α ) + ⟨ ∇ F D ( α ) , β − α ⟩ + 2 L ′ ∥ β − α ∥ 2 2 =: U L ′ ( β , α ) ∀ β , α ∈ R p . (5)
Instead of directly minimizing Problem 2, we minimize a local model of F ( β ) = F D ( β ) + λ 1 ∥ β ∥ 1 F(\beta) = F_D(\beta) + \lambda_1\|\beta\|_1 F ( β ) = F D ( β ) + λ 1 ∥ β ∥ 1 around candidate point α \alpha α . This leads to the following optimization problem:
min ∥ β ∥ 0 ≤ k U L ′ ( β , α ) + λ 1 ∥ β ∥ 1 = min ∥ β ∥ 0 ≤ k F D ( α ) + L ′ 2 ∥ β − ( α − 1 L ′ ∇ F D ( α ) ) ∥ 2 2 − 1 2 L ′ ∥ ∇ F D ( α ) ∥ 2 2 + λ 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)} ∥ β ∥ 0 ≤ k min U L ′ ( β , α ) + λ 1 ∥ β ∥ 1 = ∥ β ∥ 0 ≤ k min F D ( α ) + 2 L ′ β − ( α − L ′ 1 ∇ F D ( α ) ) 2 2 − 2 L ′ 1 ∥∇ F D ( α ) ∥ 2 2 + λ 1 ∥ β ∥ 1 (6)
which is equivalent to solving
min ∥ β ∥ 0 ≤ k L ′ 2 ∥ β − ( α − 1 L ′ ∇ F D ( α ) ) ∥ 2 2 + λ 1 ∥ β ∥ 1 (7) \min_{\|\beta\|_0 \le k} \frac{L'}{2}\left\|\beta- \left(\alpha- \frac{1}{L'}\nabla F_D(\alpha)\right)\right\|_2^2 + \lambda_1\|\beta\|_1 \tag*{(7)} ∥ β ∥ 0 ≤ k min 2 L ′ β − ( α − L ′ 1 ∇ F D ( α ) ) 2 2 + λ 1 ∥ β ∥ 1 (7)
because we only include optimization terms dependent on β \beta β . To solve (7) we need to consider the following thresholding operator:
T ( u , k , λ ) : = arg min β ∈ R p : ∥ β ∥ 0 ≤ k 1 2 ∥ β − u ∥ 2 2 + λ ∥ β ∥ 1 (8) T(u,k,\lambda) := \mathop{\arg\min}_{\beta\in\mathbb{R}^p:\|\beta\|_0 \le k} \frac{1}{2}\|\beta-u\|_2^2 + \lambda\|\beta\|_1 \tag*{(8)} T ( u , k , λ ) := arg min β ∈ R p : ∥ β ∥ 0 ≤ k 2 1 ∥ β − u ∥ 2 2 + λ ∥ β ∥ 1 (8)
which can be computed in closed form as shown in the following proposition.
Proposition 2.1. Let T T T be the thresholding operator defined in (8). If β ^ i \hat{\beta}_i β ^ i denotes the i i i th coordinate of T T T , then
β ^ i = { 0 , if i ∉ R k ( u ) sign ( u i ) ⋅ max ( ∣ u i ∣ − λ , 0 ) , if i ∈ R k ( u ) \hat{\beta}_i =
\begin{cases}
0, & \text{if } i \notin R_k(u) \\
\operatorname{sign}(u_i)\cdot\max(|u_i|-\lambda,0), & \text{if } i \in R_k(u)
\end{cases} β ^ i = { 0 , sign ( u i ) ⋅ max ( ∣ u i ∣ − λ , 0 ) , if i ∈ / R k ( u ) if i ∈ R k ( u ) where R k ( u ) R_k(u) R k ( u ) denotes the set of k k k indices corresponding to the k k k largest absolute values of u u u .
A proof is given in Appendix B. When there are ties among the magnitudes of u u u , Problem (8) can have multiple minimizers, so T T T is in general set-valued. Our algorithm is inspired by IHT [9 , 6 ] . Starting from an initial solution β 0 ∈ R p \beta_0 \in\mathbb{R}^p β 0 ∈ R p , we apply an iterative thresholding procedure resulting in a sequence of solutions { β t } \{\beta_t\} { β t } , given by
β t + 1 ∈ T ( β t − η ∇ F D ( β t ) , k , η λ 1 ) , (9) \beta_{t+1} \in T(\beta_t-\eta\nabla F_D(\beta_t),k,\eta\lambda_1), \tag*{(9)} β t + 1 ∈ T ( β t − η ∇ F D ( β t ) , k , η λ 1 ) , (9)
where the learning rate is η = 1 / L ′ \eta= 1/L' η = 1/ L ′ . The procedure is run until a stopping criterion is met; the criteria used in each stage are given in § 2.2 .
By Proposition 2.1, we have the explicit form of (9):
( β t + 1 ) i = { 0 , if i ∉ R k ( β t ) sign ( β t − η ∇ F D ( β t ) ) ⋅ max ( ∣ β t − η ∇ F D ( β t ) ∣ − η λ 1 , 0 ) , if i ∈ R k ( β t ) (10) (\beta_{t+1})_i =
\begin{cases}
0, & \text{if } i \notin R_k(\beta_t) \\
\operatorname{sign}(\beta_t-\eta\nabla F_D(\beta_t))\cdot\max(|\beta_t-\eta\nabla F_D(\beta_t)|-\eta\lambda_1,0), & \text{if } i \in R_k(\beta_t)
\end{cases} \tag*{(10)} ( β t + 1 ) i = { 0 , sign ( β t − η ∇ F D ( β t )) ⋅ max ( ∣ β t − η ∇ F D ( β t ) ∣ − η λ 1 , 0 ) , if i ∈ / R k ( β t ) if i ∈ R k ( β t ) (10)
Proposition 2.2. The updates given in 9 will converge to a particular β \beta β .
We prove Proposition in Appendix B.
We now describe how to parse the computation in (10) so that we can take advantage of GPU parallelism.
We first perform the gradient update step
β ~ t ← β t − η ∇ F D ( β t ) (11) \tilde{\beta}_t \leftarrow\beta_t-\eta\nabla F_D(\beta_t) \tag*{(11)} β ~ t ← β t − η ∇ F D ( β t ) (11)
followed by the soft thresholding step (applied elementwise)
β ~ t ← soft ( β ~ t , η λ 1 ) : = sign ( β ~ t ) ⋅ max ( ∣ β ~ t ∣ − η λ 1 , 0 ) (12) \tilde{\beta}_t \leftarrow\operatorname{soft}(\tilde{\beta}_t,\eta\lambda_1) := \operatorname{sign}(\tilde{\beta}_t)\cdot\max(|\tilde{\beta}_t|-\eta\lambda_1,0) \tag*{(12)} β ~ t ← soft ( β ~ t , η λ 1 ) := sign ( β ~ t ) ⋅ max ( ∣ β ~ t ∣ − η λ 1 , 0 ) (12)
followed by the hard thresholding operator
β t + 1 = H k ( β ~ t ) (13) \beta_{t+1}=H_k(\tilde{\beta}_t) \tag*{(13)} β t + 1 = H k ( β ~ t ) (13)
where
H k ( β i ) = { 0 , if i ∉ R k ( β i ) β i , if i ∈ R k ( β i ) , (14) H_k(\beta_i) =
\begin{cases}
0, & \text{if } i \notin\mathcal{R}_k(\beta_i) \\
\beta_i, & \text{if } i \in\mathcal{R}_k(\beta_i),
\end{cases} \tag*{(14)} H k ( β i ) = { 0 , β i , if i ∈ / R k ( β i ) if i ∈ R k ( β i ) , (14)
and R k \mathcal{R}_k R k is defined in Proposition 2.1 .
We refer to update (10) as a hard-soft thresholding update, as it consists of soft thresholding followed by hard thresholding. It updates the support and the coefficient values on the support at the same time, and every iterate β t \beta_t β t satisfies the constraint ∥ β t ∥ 0 ≤ k \lVert\beta_t\rVert_0 \le k ∥ β t ∥ 0 ≤ k . Moreover, when η ≤ 1 / L D \eta\le1/L_D η ≤ 1/ L D the objective F ( β t ) F(\beta_t) F ( β t ) is nonincreasing in t t t (Proposition B.1 in Appendix § 8 ).
Hard-soft thresholding updates the support and the values of the coefficients on the support. For a fixed support, Problem (2) is convex and can be solved with first-order methods (e.g., proximal gradient descent or PCG). This motivates the two-stage approach we describe here. To obtain good solutions to Problem (2), we use two steps. (i) Support selection: we apply update (10) until a stopping criterion is met, and obtain a support. (ii) Value modification: we solve Problem (2) restricted to the support found in (i), which is a convex problem. In the special case λ 1 = 0 \lambda_1 = 0 λ 1 = 0 we use PCG, and when λ 1 ≠ 0 \lambda_1 \ne0 λ 1 = 0 , we use a proximal gradient procedure (possibly with a different step-size than update (10) ) as described in § 2.2.2 .
ParaDeAl’s Two-Stage Methodology for Problem (2)
In this section we explicitly write the details for getting solutions to Problem (2), building on the preliminaries of § 2.1 .
We consider two separate cases: λ 1 ≠ 0 \lambda_1 \ne0 λ 1 = 0 and λ 1 = 0 \lambda_1 = 0 λ 1 = 0 as they have differences in implementation methodology. For each case we break down our discussion into support selection and value modification.
In support selection, we choose a candidate set K \mathcal{K} K with ∣ K ∣ = k \lvert\mathcal{K}\rvert= k ∣ K ∣ = k such that β i = 0 \beta_i = 0 β i = 0 if i ∉ K i \notin\mathcal{K} i ∈ / K ∀ 1 ≤ i ≤ p \forall1 \le i \le p ∀1 ≤ i ≤ p . We call K \mathcal{K} K a candidate set rather than a support because it is possible that elements within K \mathcal{K} K happen to be zero. The benefits of using a candidate set rather than defining K \mathcal{K} K as the strict support with the possibility that ∣ K ∣ < k \lvert\mathcal{K}\rvert< k ∣ K ∣ < k will be observed later, in value modification. We define our β \beta β after support selection as β w \beta_w β w (for new beta). After the candidate set is chosen, we perform value modification on it, obtaining
Value Modification β ∗ ∈ arg min β F ( β ) s.t. β i = 0 , i ∉ K . (15) \text{Value Modification}\qquad
\beta^* \in\underset{\beta}{\arg\min}\ F(\beta)
\quad\text{s.t.}\quad\beta_i = 0,\ i \notin\mathcal{K}. \tag*{(15)} Value Modification β ∗ ∈ β arg min F ( β ) s.t. β i = 0 , i ∈ / K . (15)
A diagram of the full ParaDeAl procedure, broken down into cases, is provided below in Figure 1 .
Figure 1. ParaDeAl structure. The gray-colored projection onto the candidate set K \mathcal{K} K , shown in value modification for λ 1 ≠ 0 \lambda_1 \ne0 λ 1 = 0 , may or may not be performed depending on implementation choices described in § 2.6 .
Support Selection
The goal of support selection is to quickly find a high-quality support K \mathcal{K} K that corresponds to an optimal or near-optimal objective for Problem (2). We split our method into two cases: If λ 1 ≠ 0 \lambda_1 \ne0 λ 1 = 0 , we apply exactly the procedure described in § 2.1 . If λ 1 = 0 \lambda_1 = 0 λ 1 = 0 , we apply the same procedure except we remove the soft thresholding, as seen in Figure 1 .
We also adjust the stopping criterion. Support selection (Algorithm 1) stops as soon as one update leaves the support unchanged, that is, once two consecutive iterates have the same support. The rule depends on the support only: the role of support selection is to find a support, and the coefficient values are set by value modification. More generally, one can require the support to remain unchanged for r r r consecutive updates; the rule above is r = 1 r = 1 r = 1 . Appendix § 9 examines the effect of r r r .
Once the support stabilizes, we output the final β w \beta_w β w to be passed to the value modification function. Pseudocode for support selection is given below in Algorithm 1, with steps used only when λ 1 ≠ 0 \lambda_1 \ne0 λ 1 = 0 marked in cerulean . We also use an upper limit on the number of iterations (denoted by a pre-specified parameter M S S M_{SS} M S S ).
Returning the lowest-objective support. With the large step sizes of § 3.3 , the objective does not always fall from one update to the next, so the last iterate of support selection is not always the best one seen. We therefore return the iterate with the smallest objective F ( β ) F(\beta) F ( β ) seen during support selection, rather than the one at which support selection ends. The stopping rule is unchanged. Appendix § 22 shows that this choice helps most when k k k is very small, and never makes the result meaningfully worse.
Keeping track of this iterate is done while the gradient steps run, and its cost is low. Like the rest of support selection, it is inherently parallel. Updating the running minimum is one elementwise comparison per configuration, followed by a masked overwrite of the stored iterate (torch.where), so no configuration needs its own branch. The only extra work is computing F ( β ) F(\beta) F ( β ) , which costs at most one additional product with X X X (or with X A X_A X A inside the active set of § 2.7 ) per iteration. For clarity, Algorithm 1 shows the version that returns the last iterate.
Algorithm 1 Support Selection
Require: X X X , y y y , initial β o \beta_o β o , λ 1 \lambda_1 λ 1 , λ 2 \lambda_2 λ 2 , k k k , η \eta η , max number of iterations M S S M_{SS} M S S Return: β w \beta_w β w which satisfies ∥ β ∥ 0 ≤ k \lVert\beta\rVert_0 \le k ∥ β ∥ 0 ≤ k
β w ← β o \beta_w \leftarrow\beta_o β w ← β o and i ← 1 i \leftarrow1 i ← 1
while i ≤ M S S i \le M_{SS} i ≤ M S S do
Update β w \beta_w β w through gradient descent, Equation (11)
Update β w \beta_w β w per soft thresholding operator, Equation (12) {Only if λ 1 ≠ 0 \lambda_1 \ne0 λ 1 = 0 }
β w ← H k ( β w ) \beta_w \leftarrow H_k(\beta_w) β w ← H k ( β w ) per Equation (14) { ∣ S ( β w ) ∣ ≤ k \{\lvert S(\beta_w)\rvert\le k {∣ S ( β w )∣ ≤ k is guaranteed} \} }
if S ( β w ) = S ( β o ) S(\beta_w) = S(\beta_o) S ( β w ) = S ( β o ) then
return β w \beta_w β w
end if
β o ← β w \beta_o \leftarrow\beta_w β o ← β w and i ← i + 1 i \leftarrow i + 1 i ← i + 1
end while
return β w \beta_w β w
Value Modification
Once support selection creates a candidate set K ⊇ S ( β w ) \mathcal{K} \supseteq S(\beta_w) K ⊇ S ( β w ) , we solve Problem 15.
An important consideration, which we explain in § 2.6 , emerges: Can we parallelize value modification using β \beta β s of length k k k (as opposed to e.g. p p p ), given that different β \beta β s likely have different supports? If not, we must project β \beta β s onto their supports. For the sake of completeness, we show the projection step in this section.
Once again, we consider the two cases λ 1 ≠ 0 \lambda_1 \ne0 λ 1 = 0 and λ 1 = 0 \lambda_1 = 0 λ 1 = 0 separately.
Case λ 1 ≠ 0 \lambda_1 \ne0 λ 1 = 0 : If λ 1 ≠ 0 \lambda_1 \ne0 λ 1 = 0 , we use the iterative algorithm given by Equation (9) with two minor changes. First, since support has been determined by algorithm 1, the hard thresholding step (13) is replaced by a projection step P K ( β ) P_{\mathcal{K}}(\beta) P K ( β ) , where
P K ( β i ) = { 0 , i ∉ K β i , i ∈ K . (16) P_{\mathcal{K}}(\beta_i) =
\begin{cases}
0, & i \notin\mathcal{K} \\
\beta_i, & i \in\mathcal{K}.
\end{cases} \tag*{(16)} P K ( β i ) = { 0 , β i , i ∈ / K i ∈ K . (16)
Second, instead of equal support as the termination criterion, we measure whether ∥ β w − β o ∥ 2 2 \lVert\beta_w-\beta_o\rVert_2^2 ∥ β w − β o ∥ 2 2 is sufficiently small. If ∥ β w − β o ∥ 2 2 \lVert\beta_w-\beta_o\rVert_2^2 ∥ β w − β o ∥ 2 2 is smaller than a tolerance threshold T V M T_{\mathrm{VM}} T VM , we terminate the algorithm and return β w \beta_w β w as our β ∗ \beta^* β ∗ .
To summarize, updates for value modification are given by
β t + 1 ∈ P K ( β t − η ∇ F D ( β t ) , k , η λ 1 ) , (17) \beta_{t+1} \in P_{\mathcal{K}}(\beta_t-\eta\nabla F_D(\beta_t), k, \eta\lambda_1), \tag*{(17)} β t + 1 ∈ P K ( β t − η ∇ F D ( β t ) , k , η λ 1 ) , (17)
with a convergence criterion of ∥ β t + 1 − β t ∥ 2 2 < T V M \lVert\beta_{t+1}-\beta_t\rVert_2^2 < T_{\mathrm{VM}} ∥ β t + 1 − β t ∥ 2 2 < T VM .
(Compared with the pseudocode in Algorithm 1, value modification for λ 1 ≠ 0 \lambda_1 \ne0 λ 1 = 0 involves two changes: line 5 is either removed or replaced with β w ← P K ( β w ) \beta_w \leftarrow P_{\mathcal{K}}(\beta_w) β w ← P K ( β w ) ; and line 6 is replaced with the criterion ∥ β w − β o ∥ 2 2 < T V M \lVert\beta_w-\beta_o\rVert_2^2 < T_{\mathrm{VM}} ∥ β w − β o ∥ 2 2 < T VM .)
Case λ 1 = 0 \lambda_1 = 0 λ 1 = 0 : If λ 1 = 0 \lambda_1 = 0 λ 1 = 0 , to solve value modification (15), we could use direct matrix inversion. However, when applied over large ∏ C \prod C ∏ C , finding a way to parallelize appears difficult in our experience and inversion becomes too computationally expensive. We could also use the proximal gradient-type algorithm described in Equation (17) , but empirically we find it slower than PCG, which is what we use.
The optimality condition for Problem (15), found by its derivative, is given by
( X T X + λ 2 I ) β = X T y and β i = 0 , i ∉ K (18) (X^{T}X+\lambda_2I)\beta=X^{T}y \text{ and } \beta_i=0,\ i\notin\mathcal{K} \tag*{(18)} ( X T X + λ 2 I ) β = X T y and β i = 0 , i ∈ / K (18)
By restricting β \beta β to the coefficients in K \mathcal{K} K , the above is equivalent to
( X K T X K + λ 2 I ) β K = X K T y (19) (X_{\mathcal{K}}^{T}X_{\mathcal{K}}+\lambda_2I)\beta_{\mathcal{K}}=X_{\mathcal{K}}^{T}y \tag*{(19)} ( X K T X K + λ 2 I ) β K = X K T y (19)
where X K : = R S ( X , β w ) X_{\mathcal{K}} := R_S(X,\beta_w) X K := R S ( X , β w ) and β K : = R S ( β w ) \beta_{\mathcal{K}} := R_S(\beta_w) β K := R S ( β w ) .
Problem (19) is of the form A β = b A\beta=b A β = b with A = X K T X K + λ 2 I A=X_{\mathcal{K}}^{T}X_{\mathcal{K}}+\lambda_2I A = X K T X K + λ 2 I , b = X K T y b=X_{\mathcal{K}}^{T}y b = X K T y ; and A A A is symmetric positive-definite. Therefore, we can solve (19) with PCG (Shewchuk [32 ] ). However, when we parallelize over multiple β \beta β , we face the same issue as with the λ 1 ≠ 0 \lambda_1 \ne0 λ 1 = 0 case noted above: different β \beta β s are likely to have different supports. As a result, from an implementation standpoint, we can adapt PCG to involve β \beta β s whose length exceeds the support size and include a projection operator where necessary to make sure that the coefficients of β \beta β outside K \mathcal{K} K are zero. The details are seen in Algorithm 2.
For the remainder of our PCG discussion, we include projections for the sake of completeness; if they are unnecessary, then projection steps can be disregarded, and X X X can be replaced with R K ( X , β w ) R_{\mathcal{K}}(X,\beta_w) R K ( X , β w ) .
Our PCG procedure uses initializes the residual r 0 = P K ( X T y − X T X β w − λ 2 β w ) r_0=P_{\mathcal{K}}(X^{T}y-X^{T}X\beta_w-\lambda_2\beta_w) r 0 = P K ( X T y − X T X β w − λ 2 β w ) , then create a preconditioner M = diag ( X T X ) + λ 2 I M=\operatorname{diag}(X^{T}X)+\lambda_2I M = diag ( X T X ) + λ 2 I (where diag ( X T X ) \operatorname{diag}(X^{T}X) diag ( X T X ) is a diagonal matrix) for the matrix X T X + λ 2 I X^{T}X+\lambda_2I X T X + λ 2 I . Next, we introduce preconditioned residual z o = P K ( M − 1 r o ) z_o = P_{\mathcal{K}}(M^{-1}r_o) z o = P K ( M − 1 r o ) , with
M − 1 = [ M 1 , 1 − 1 0 ⋯ 0 0 M 2 , 2 − 1 ⋯ 0 ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ M p , p − 1 ] (20) M^{-1} =
\begin{bmatrix}
M_{1,1}^{-1} & 0 & \cdots& 0 \\
0 & M_{2,2}^{-1} & \cdots& 0 \\
\vdots& \vdots& \ddots& \vdots\\
0 & 0 & \cdots& M_{p,p}^{-1}
\end{bmatrix} \tag*{(20)} M − 1 = M 1 , 1 − 1 0 ⋮ 0 0 M 2 , 2 − 1 ⋮ 0 ⋯ ⋯ ⋱ ⋯ 0 0 ⋮ M p , p − 1 (20)
due to the diagonal nature of M M M . Finally, we initialize search direction θ = z o \theta= z_o θ = z o . The iterative steps of PCG proceed as in Algorithm 2 and involve updating α \alpha α (step size), β w \beta_w β w , r r r , z z z , and μ \mu μ (conjugacy coefficient).
Algorithm 2 Preconditioned conjugate gradient (PCG) on candidate set K \mathcal{K} K
Require: β w \beta_w β w , preconditioner M M M , inaccuracy tolerance T P C G T_{\mathrm{PCG}} T PCG , max number of PCG iterations M P C G M_{\mathrm{PCG}} M PCG
Return: β ∗ \beta^* β ∗ which minimizes f D ( β ) f_D(\beta) f D ( β )
Initialize r o , z o , θ r_o,z_o,\theta r o , z o , θ as described above
i ← 1 i \gets1 i ← 1
while i ≤ M P C G i \le M_{\mathrm{PCG}} i ≤ M PCG do
g ← P K ( X T X θ ) + λ 2 θ g \gets P_{\mathcal{K}}(X^T X\theta) + \lambda_2\theta g ← P K ( X T X θ ) + λ 2 θ {g for ease of calculation/avoid redundancy. S ( θ ) S(\theta) S ( θ ) already equals K \mathcal{K} K }
α = θ T z o θ T g \alpha= \frac{\theta^T z_o}{\theta^T g} α = θ T g θ T z o {α \alpha α is the step size}
β w ← β w + α θ \beta_w \gets\beta_w + \alpha\theta β w ← β w + α θ
r w = r o − α g r_w = r_o - \alpha g r w = r o − α g
z w = P K ( M − 1 r w ) z_w = P_{\mathcal{K}}(M^{-1}r_w) z w = P K ( M − 1 r w )
if ∥ r w ∥ 2 ≤ T P C G ⋅ ∥ P K ( X T y ) ∥ 2 \lVert r_w\rVert_2 \le T_{\mathrm{PCG}} \cdot\lVert P_{\mathcal{K}}(X^T y)\rVert_2 ∥ r w ∥ 2 ≤ T PCG ⋅ ∥ P K ( X T y ) ∥ 2 then
return β w \beta_w β w
end if
μ o ← r o T z o , μ w ← r w T z w \mu_o \gets r_o^T z_o,\ \mu_w \gets r_w^T z_w μ o ← r o T z o , μ w ← r w T z w {μ \mu μ is the conjugacy coefficient; search direction p w p_w p w is A A A -orthogonal to previous p s p_s p s }
θ ← z w + μ w μ o θ \theta\gets z_w + \frac{\mu_w}{\mu_o}\theta θ ← z w + μ o μ w θ
z o ← z w , r o ← r w z_o \gets z_w,\ r_o \gets r_w z o ← z w , r o ← r w {z z z and r r r need old and new versions within an iteration of the loop}
i ← i + 1 i \gets i + 1 i ← i + 1
end while
return β w \beta_w β w
It is worth clarifying that when we refer to η \eta η , we might have to admit two separate learning rates, because the learning rate for support selection should not necessarily be the same as the learning rate for value modification. (It is only necessary to have two learning rates if λ 1 ≠ 0 \lambda_1 \ne0 λ 1 = 0 .) Therefore, when λ q ≠ 0 \lambda_q \ne0 λ q = 0 , we can think of η \eta η as a cross product between η S S \eta_{SS} η S S and η V M \eta_{VM} η V M . However, for simplicity, we use the term η \eta η throughout the paper. The distinction between support selection and value modification learning rates is further explored in § 3.3 .
The best support before value modification is not always the best support after it. Support selection keeps the k k k features with the largest coefficients during the hard-soft thresholding updates, but the quality of the final answer is the objective after value modification, and the two do not always agree. When two features are strongly correlated, their coefficients during support selection can be almost the same size, so which of them survives the hard thresholding step is close to a coin flip. After value modification, the feature that was left out may turn out to give the smaller objective. We checked this directly by refitting several nearby candidate supports with value modification and keeping the best (Appendix § 20 ): a candidate with a smaller objective than the chosen support exists for most configurations on correlated data. Trying more supports in this way recovers only part of the gap, at a higher cost. The pair swap procedure of § 3.4 , which exchanges features in and out of the support after value modification whenever doing so lowers the objective, solves this problem to a very large extent.
The Parallelism Framework
We wish to parallelize Problem (2) to speed up computation across different hyperparameter configurations.
First, Problem 2 involves three regularization parameters λ 1 \lambda_1 λ 1 , λ 2 \lambda_2 λ 2 , k k k . These parameters collectively control model accuracy (prediction performance) and model compactness (number of nonzero coefficients), and practitioners need to obtain solutions to Problem 2 across a wide range of these parameters, because they can result in different solutions in terms of optimizing Problem (2) . This helps them select suitable tradeoffs in model accuracy and interpretability. Additionally, Algorithm 1 depends upon initialization β 0 \beta_0 β 0 and learning rate η \eta η ; due to the nonconvexity of Problem 2, different choices of β 0 \beta_0 β 0 and η \eta η can result in solutions of different quality.
We intend to solve Problem 2 on a collection of hyperparameter configurations denoted by C \mathcal{C} C . We will use GPU parallelism to compute a batch of solutions to Problem 2 across the five hyperparameters ( k , λ 1 , λ 2 , η , β 0 ) (k,\lambda_1,\lambda_2,\eta,\beta_0) ( k , λ 1 , λ 2 , η , β 0 ) . We allow C \mathcal{C} C to be a grid over all hyperparameter choices (i.e. cross product) or a listed subset of pre-specified hyperparameter configurations. The former construct is called a grid; the latter, a tuple.
ParaDeAl takes advantage of GPU parallelism to get speedups from:
Matrix-matrix or matrix-vector multiplication. A core building block of our ParaDeAl approach is matrix-matrix or matrix-vector multiplications, which can be performed much faster on GPUs than CPUs. This is because GPUs contain up to tens of thousands of cores, which can collectively process information much faster than CPUs, which only have a few dozen (Meng et al. [24 ] , Applegate et al. [1 ] ). Moreover, crucially, these multiplications are embarrassingly parallel: they are easy to subdivide or split across large numbers of cores, allowing the GPU to take full advantage and use most or all of its cores.
Multi-configuration computation. The key advantage of ParaDeAl over existing algorithms is parallel processing across multiple problem setups indexed by C \mathcal{C} C . By calling PyTorch functions like vmap, ParaDeAl can achieve large speedups over CPUs — for comparisons, see the experiments in § 4.1 . In popular statistics/machine learning software, such as scikit-learn (Pedregosa et al. [29 ] ), hyperparameter configurations are often done sequentially and/or independently of one another — we refer the reader to § 4.3 for empirical results and the speedups we obtain due to parallelism.
We use two complementary ways to implement parallelism:
vmap Method. Here, we write a function for a single problem instance, then call vmap to execute this function across a collection of instances. For embarrassingly parallel workflows in which there is no communication across different instances and the same function is applied to all instances, we batch all instances for that workflow together using vmap. An example is the gradient descent update in Equation (11) : given shared (static) matrices X X X and y y y , and different instances of β 0 \beta_0 β 0 (initialization), learning rate η \eta η , tuning parameter λ 2 \lambda_2 λ 2 , we can write a function that computes the gradient descent update for one instance of β 0 , η , λ 2 \beta_0,\eta,\lambda_2 β 0 , η , λ 2 , then call vmap over all instances, specifying X X X and y y y as static. (We note that this operation is computationally equivalent to creating large tensors including all possibilities for each of β 0 , η , λ 2 \beta_0,\eta,\lambda_2 β 0 , η , λ 2 and then performing the update in (11) once with the large tensors instead of a single β 0 , η , λ 2 \beta_0,\eta,\lambda_2 β 0 , η , λ 2 . However, where vmap is available, it is preferred due to its simplicity.)
The syntax for vmap is
v m a p ( f u n c _ n a m e , i n _ d i m s = ( a r g s _ s t a t u s ) ) ( a r g s ) (21) \mathtt{vmap(func\_name,\ in\_dims=(args\_status))(args)} \tag*{(21)} vmap ( func_name , in_dims = ( args_status )) ( args ) (21)
where func_name is the name of the function to be called, args_status represents whether each argument, in order, is to be treated as a static argument across all instances (None) or parallelized over (0 for our purposes), and args is the list of arguments to be applied to the function. For example, if we are applying (11) using the function
GD(X, y, beta, eta, lambda2)
over the same X , y , η X,y,\eta X , y , η but different λ 2 \lambda_2 λ 2 and β \beta β , then the batched procedure would look like
vmap(GD, in_dims=(None, None, 0, None, 0))(X, y, betas, eta, lambda2s)
where betas is the tensor of all β \beta β s and lambda2s is the tensor of all λ 2 \lambda_2 λ 2 s organized in the same order as betas.
When tuple search is used, we apply Equation (21) . When grid search is used, we may have to extend the list of hyperparameter values. Using the same example above, supposing we have 1 value each of k k k , η \eta η , and λ 1 \lambda_1 λ 1 , but 15 β 0 \beta_0 β 0 s and 12 λ 2 \lambda_2 λ 2 s, then the lists betas and lambda2s must be of length 180 to match the fact that we have 180 problem instances. To extend the list of λ 2 \lambda_2 λ 2 s from length 12 to 180, we do not have to allocate additional memory; using operations like view, expand, and reshape elongates this list without incurring extra storage cost. In this particular case, adopting the B B B storage convention in Section 2.4, the correct expression is
l2s.view(-1, 1).expand(-1,C_\eta C_\beta).reshape(-1).view(-1, 1).expand(-1,C_k C_{\lambda_1}).T.reshape(-1)
where the C ( ⋅ ) C_{(\cdot)} C ( ⋅ ) are defined in Section 2.4 and l2s is the original list of 12 λ 2 \lambda_2 λ 2 s. Another example of extension is demonstrated in Equation (22) .
Overarching Method. This corresponds to the most general (overarching) case which cannot be captured in the vmap method. We modify the single-instance function to fit all instances. Not all ParaDeAl operations can be batched, especially those which reshape matrices, batch over indexing, or require control-dependent branching (different iteration count for different instances, likely due to if statements). As a result, it is not advisable to directly vmap over all instances, but some level of parallelism can still be achieved if the vmapable individual steps are still vmapped, while control of logic (e.g. if statements) is not parallelized. In effect, the single-instance function changes into an overarching function, where large tensors are explicitly created to handle all instances of non-static arguments at once. An example of this is Algorithm 4.
We note that if a function is vmapable, then we should use the vmap Method, otherwise we should use the more general Overarching Method. Oftentimes, PyTorch code can be carefully rewritten to move from the latter category to the former. For example, if implementing the hard thresholding operation (Equation (13) ) over multiple β \beta β for the same k k k in Equation (14) , using beta[~support] = 0 to set non-support-values of β \beta β to zero is unacceptable because we batch over a data-dependent binary overlay support (i.e. it changes depending on β \beta β ); on the contrary, writing this same operation as beta = torch.where(support != 0, beta, 0) avoids this issue because it calls a PyTorch function where amenable to batching.
A multi-dimensional tensor representation of β \beta β s
Every configuration c = ( β 0 , λ 1 , λ 2 , η , k ) c = (\beta_0, \lambda_1, \lambda_2, \eta, k) c = ( β 0 , λ 1 , λ 2 , η , k ) affects the trajectory of the sequence of solutions β t \beta_t β t obtained by ParaDeAl. We create a multidimensional tensor B B B to store β \beta β s corresponding to every c c c as they are being updated through iterations. (We refer to B B B as a tensor following the PyTorch conventions.)
We consider two main formats of C \mathcal{C} C . It can be (i) a grid, a cross product over each of the 5 dimensions of C a \mathcal{C}_a C a ; or (ii) a tuple, a list of values of c c c . This creates two general search regions of interest: grid search and tuple search.
In grid search, we initialize a tensor B B B consisting of ∏ C = C k C λ 1 C λ 2 C η C β \prod\mathcal{C} = C_k C_{\lambda_1} C_{\lambda_2} C_\eta C_\beta ∏ C = C k C λ 1 C λ 2 C η C β different coefficient vector β \beta β s, with each β \beta β corresponding to a configuration c ∈ C c \in\mathcal{C} c ∈ C . We represent B B B as a multidimensional matrix with ∏ C \prod\mathcal{C} ∏ C elements.
This multidimensional representation facilitates the indexing of distinct values of β \beta β by their corresponding hyperparameters. (Note that certain dimensions of B B B may have length one if we are considering only one instance of that hyperparameter. For example, a user may wish to perform ParaDeAl with only L2 penalties; then, C λ 1 = 1 C_{\lambda_1} = 1 C λ 1 = 1 .)
One example of a 6-dimensional tensor B B B is given in Figure 2 . We choose the ordering of the hyperparameter coordinates to facilitate computation: for instance, in the sequence of operations (11)–(13), the last operation is hard thresholding, so k k k is the outermost dimension.
Figure 2. A concept of a 6-dimensional B B B . Each individual β \beta β is a white length-p p p vector. The nested structure is a byproduct of our representation of B B B and can be described thus: Each label and its color represent the smallest unit that encompasses all values of that label from the dimension it is given. For example, since B B B is ( C k × C λ 1 × C λ 2 × C η × C β × p ) (C_k \times C_{\lambda_1} \times C_{\lambda_2} \times C_{\eta} \times C_{\beta} \times p) ( C k × C λ 1 × C λ 2 × C η × C β × p ) , a single blue C η C_{\eta} C η block is a 3-D tensor consisting of all C η C_{\eta} C η variations of the lower dimensions, in which each purple block (labeled as “C β C_{\beta} C β β \beta β s”) represents one C η C_{\eta} C η over all the lower dimensions (in this case, just C β C_{\beta} C β ).
The chief benefit of this representation is that all β \beta β s corresponding to any of the five hyperparameter coordinates can be indexed by specifying the indices for that variable. For example, if we wish to reference all β \beta β s using the third value of η \eta η we specified, this can be done with B[:, :, :, 2, :, :].
When hyperparameters are stored as a list in the tuple form, the tensor B B B is simply a list of β \beta β s, with dimension ( ∏ C × p × m ) (\prod C \times p \times m) ( ∏ C × p × m ) .
Parallelizing Support Selection
We use vmap to parallelize the gradient descent and soft thresholding steps in Equations (11) and (12) . To make implementation PyTorch-compatible, if k k k is the same across all configurations, we can use vmap on hard thresholding. However, if there are multiple values of k k k , we cannot use vmap. In Algorithm 3, we demonstrate the vmap-enabled case, which forms the basis for the more general approach in Algorithm 4.
Algorithm 3 Single-β \beta β Hard Thresholding (can be used with vmap when k k k is same across instances)
Require: single β \beta β , support size k k k
Return: new β \beta β with at most k k k nonzeros
Obtain the top-k k k indices from ∣ β ∣ |\beta| ∣ β ∣
Generate binary overlay O O O of 1s and 0s based on obtained top-k k k indices {1 if the element is in the top-k k k }
return O ⊙ β O \odot\beta O ⊙ β {⊙ \odot ⊙ denotes Hadamard, i.e. element-wise, product}
When different configurations have different values of the support size k k k , one approach is to run Algorithm 3 in a for loop across different k k k values. We can use binary indicators (1/0) which we refer to as a binary overlay to indicate which elements of β \beta β are among the largest k k k magnitudes. This is not GPU-friendly, so we use an alternative approach described in Algorithm 4. We can operate on the B B B matrix of size ( ∏ C × p ) (\prod C \times p) ( ∏ C × p ) which contains all β \beta β s as introduced in § 2.4 . This procedure, like Algorithm 3, uses a binary overlay, i.e. a tensor of 1s and 0s which either allows or denies each element, but this time it is a matrix of ( ∏ C × p ) (\prod C \times p) ( ∏ C × p ) indicating whether each element of the flattened B B B should be included or not in the final output.
Algorithm 4 applies to both the cases of grid search and tuple search. In tuple search, K K K is the list of k k k s. In grid search, as there are C k C_k C k values of k k k yet ∏ C \prod C ∏ C configurations (thus the input K K K needs to be of length ∏ C \prod C ∏ C ), each k k k will be repeated R k = ( ∏ C ) / C k R_k = (\prod C)/C_k R k = ( ∏ C ) / C k times. We extend the original list of k k k s, here denoted K 0 K_0 K 0 , by a factor of R k R_k R k without using additional memory through a sequence of torch operations, namely
K ← K 0 . v i e w ( − 1 , 1 ) . e x p a n d ( − 1 , R k ) . r e s h a p e ( − 1 ) . (22) K \leftarrow K_0.\mathrm{view}(-1,1).\mathrm{expand}(-1,R_k).\mathrm{reshape}(-1). \tag*{(22)} K ← K 0 . view ( − 1 , 1 ) . expand ( − 1 , R k ) . reshape ( − 1 ) . (22)
Algorithm 4 Correct Overlay Approach for Parallel Hard Thresholding
Require: tensor of β \beta β ’s B B B , support size list per β \beta β K K K Return: new B B B with at most k ∈ K k \in K k ∈ K nonzeroes per β ∈ B \beta\in B β ∈ B
B ← torch.abs ( B ) B \leftarrow\texttt{torch.abs}(B) B ← torch.abs ( B )
For each row of B B B , obtain the sort indices sort_indices using torch.sort {The smallest-magnitude element of a β \beta β is indexed 0, and so on until p − 1 p-1 p − 1 }
R ← [ [ 0 , 1 , … , p − 1 ] ] R \leftarrow[[0,1,\ldots,p-1]] R ← [[ 0 , 1 , … , p − 1 ]] {Ranged vector of size ( 1 × p ) (1 \times p) ( 1 × p ) for overlay production}
K K K becomes ( ∏ C × 1 ) (\prod C \times1) ( ∏ C × 1 ) {Previously it was a vector of length ∏ C \prod C ∏ C }
binary_elts ← R < K \leftarrow R < K ← R < K {PyTorch automatically scales R R R and K K K to ( ∏ C × p ) (\prod C \times p) ( ∏ C × p ) ; binary_elts has the correct number of 1s and 0s but not in the right indices}
Initialize overlay O O O of shape ( ∏ C × p ) (\prod C \times p) ( ∏ C × p )
O ← O \leftarrow O ← scattered binary elts across O O O using sort indices with row dominance {O O O is the final 0-1 overlay of whether to keep the element or not}
return O ⊙ B O \odot B O ⊙ B
Note that in the above none of view, expand, or reshape require additional memory allocation because they use pointer and stride manipulation. (Another possibility is to use torch.repeat_interleave which is shorter codewise, but we do not use it because it requires more memory as each element in the new tensor gets stored in its own memory block.) Notice that in (22) we selected C k C_k C k as the outermost dimension of B B B : the order of β \beta β s in B B B in Algorithm 4 exactly matches the order of the corresponding k k k s in K K K . (If this were not the case, a more cumbersome extension would have to be developed.)
When the algorithm is run across multiple configurations, different instances may require different numbers of iterations to satisfy the termination criterion. Consequently, the control flow depends on the instance. Such instance-dependent control flow cannot be parallelized using standard PyTorch operations. We refer to this challenge as the control-dependent parallelization problem (CDPP) and propose several approaches for parallelizing support selection when the required number of iterations varies across instances.
Max Number of Iterations: We run every instance of support selection for exactly M S S M_{SS} M S S iterations; M S S M_{SS} M S S is chosen a priori. This method allows the entire support update to be vmapped across all configurations, providing the most parallelism possible. However, if M S S M_{SS} M S S is not well-chosen, the method will involve redundant computations if M S S M_{SS} M S S is too large, or cause early termination if M S S M_{SS} M S S is too small.
Flag Approach: We run every instance of support selection until all of them have stabilized support. At every iteration in the overarching function, we flag whether all supports have stabilized using a computationally cheap vectorized boolean operation; once all flags are true, we terminate. This method preserves vmap structure across all iterations while adapting termination to the worst-case configuration.
Only Unstabilized: At every iteration, we run only the instances that have yet to stabilize support. We also use the flag from the Flag Approach. After each iteration, if any instances have converged, we shrink the tensor holding the heretofore unconverged β \beta β s to remove those that just converged. While this method minimizes the number of calculations by entirely removing superfluous ones, it incurs extra cost due to shrinking B B B a large number of times.
Dynamic Shrinking (see § 3.1 ): This is a compromise solution. The Flag Approach requires minimal modification to B B B , but it may perform substantial redundant computation on instances that have already converged. On the other hand, Only Unstabilized eliminates this redundancy, but incurs overhead by repeatedly modifying B B B . Dynamic shrinking is a compromise between these two approaches. Given a shrinkage factor s ∈ ( 0 , 1 ) s \in(0,1) s ∈ ( 0 , 1 ) , we continue processing the full tensor B B B until the number of unconverged β \beta β s falls below s s s times the current tensor size. At that point, we compact the tensor by retaining only the unconverged instances, and proceed. We repeat this procedure until all instances have converged. In practice, we set a threshold (default 100) under which the cost of shrinking outweighs its benefits, and we proceed as in the Flag Approach.
Since the Max Number of Iterations method requires guessing M S S M_{SS} M S S , we disregard it. Empirically, we find out that the overhead of maintaining a flag vector of size Π C \Pi C Π C is minimal, and the B B B -shrinking operation is much cheaper than an iteration of support selection or value modification, as parallel matrix-vector multiplication is more expensive. We compare the viability of the Flag Approach, Only Unstabilized, and Dynamic Shrinking in § 4.2 .
Parallelizing Value Modification
The general analysis of how to parallelize value modification is the same for the λ 1 ≠ 0 \lambda_1 \ne0 λ 1 = 0 (proximal gradient-like procedure, § 2.2.2 ) and λ 1 = 0 \lambda_1 = 0 λ 1 = 0 (PCG, Algorithm 2) scenarios. Because both methods rely on if statements for termination, the CDPP applies to value modification as well.
However, there are additional challenges associated with value modification, specifically in vectorization. Once candidate sets K 1 , K 2 , … \mathcal{K}_1, \mathcal{K}_2, \ldots K 1 , K 2 , … have been chosen for the β w \beta_w β w s (see § 2.2.1 ), we can exploit the fact that they may be similar to condense the length of β \beta β . As we noted in § 2.2.2 , while it is true that for a single β \beta β one can programmatically shrink β \beta β to just the k k k features of its candidate set to reduce the amount of computation, for Π C \Pi C Π C different β \beta β s, the candidate sets may not consist of the same feature indices; therefore, it may be more difficult to compress the length of the β \beta β s to reduce computation. Nevertheless, we can still systematically analyze the different possible cases. We call this the Computation-Memory Tradeoff Problem (CMTP) , as it involves tradeoffs between amount of computation and memory footprint. (All solutions can be fully parallelized except for control-dependent branching.) We propose three ways to address the computation-memory tradeoff, all of which use the Overlay Method due to the if criteria:
Resizing to Candidate Set: We parallelize β w \beta_w β w s over only their candidate sets; that is, over R K ( β w ) R_{\mathcal{K}}(\beta_w) R K ( β w ) and R K ( X , β w ) R_{\mathcal{K}}(X,\beta_w) R K ( X , β w ) (defined in 1.5), so that the support constraint is enforced by the shape of the operands rather than by an explicit projection at every iteration. Upon receiving the β w \beta_w β w s of length p p p from support selection, we restrict each one to its k k k coordinates of largest magnitude, β K ← R K ( β w ) \beta_{\mathcal{K}} \leftarrow R_{\mathcal{K}}(\beta_w) β K ← R K ( β w ) , and restrict X X X to the matching columns, producing a separate ( n × k ) (n \times k) ( n × k ) matrix X K ← R K ( X , β w ) X_{\mathcal{K}} \leftarrow R_{\mathcal{K}}(X,\beta_w) X K ← R K ( X , β w ) for each configuration. Stacking these gives a ( Π C × k ) (\Pi C \times k) ( Π C × k ) tensor and a ( Π C × n × k ) (\Pi C \times n \times k) ( Π C × n × k ) tensor, which we supply as the dynamic arguments of the vmap-based value modification procedure, with y y y and the hyperparameters static.
Maintaining Length p p p : We perform value modification over length-p p p β w \beta_w β w s using projections to maintain the sparsity pattern (β i = 0 \beta_i = 0 β i = 0 , i ∉ K i \notin\mathcal{K} i ∈ / K ; see § 2.2.2 ). To avoid creating the new X K X_{\mathcal{K}} X K matrices, we can use the projection-based value modification procedure (see § 2.2.2 ) directly. To compute P K ( β ) P_{\mathcal{K}}(\beta) P K ( β ) , we use a binary overlay method: we create a length-p p p binary overlay vector O S O_S O S for each configuration, which is 1 for elements of β w \beta_w β w in the support and 0 otherwise. In other words, for a vector v v v , the operation P K ( v ) P_{\mathcal{K}}(v) P K ( v ) is equivalent to performing O S ⊙ v O_S \odot v O S ⊙ v —this can be parallelized using the vmap procedure.
Union Method: We form a union of each β w \beta_w β w 's supports, i.e. U = ⋃ Π C S ( β w ) \mathcal{U} = \bigcup_{\Pi C} S(\beta_w) U = ⋃ Π C S ( β w ) , resize all β w \beta_w β w s and X X X to U \mathcal{U} U once, and parallelize over length-∣ U ∣ |\mathcal{U}| ∣ U ∣ β w \beta_w β w s with projection onto U \mathcal{U} U . By removing features that are not found in any of the Π C \Pi C Π C supports, we may be able to eliminate a large portion of the p p p features; in particular, the upper bound for the number of remaining features is max ( Π C ⋅ k , p ) \max(\Pi C \cdot k,p) max ( Π C ⋅ k , p ) . Then, we proceed as in the above item Maintaining Length p p p .
Notice that in Resizing to Candidate Set , we do not restrict updates to β w \beta_w β w to S ( β w ) S(\beta_w) S ( β w ) itself, but rather K \mathcal{K} K , which is of size k k k exactly. This is beneficial because restricting to supports, which may be of size smaller than k k k , might yield operands of different widths which can be hard to batch using vmap. On the contrary, candidate sets are guaranteed to be of size k k k . Moreover, allowing certain zero coordinates to potentially change value may actually be beneficial, because it enlarges the feasible region of Problem 15 and still obeys the cardinality constraint of Problem 2.
All three approaches to the computation-memory tradeoff problem must accommodate different values of k k k . For Maintaining Length p p p and the Union Method , this can be achieved by applying vmap across O S O_S O S . For Resizing to Candidate Set , however, direct use of vmap is more difficult because each β w \beta_w β w must be resized to its corresponding k k k , implicitly producing a ragged tensor that is difficult to parallelize. Thus, we use an alternative approach inspired by Algorithm 4. There, multiple values of k k k were handled using a single overlay matrix O O O , with one row per configuration. The present setting introduces an additional complication: unlike in hard thresholding, where all β w \beta_w β w vectors had the same length, the vectors here have different lengths. To preserve parallelism, we pad each β w \beta_w β w to length k M k_M k M , where k M k_M k M denotes the maximum value of k k k , and apply the projections through overlay matrices using vmap. Thus, all three approaches implement the required operations as projections.
The methods outlined above have their advantages and shortcomings. We compare these items in the table below.
The values of n n n , k M k_M k M , p p p , and ∏ C \prod C ∏ C determine the memory requirements of the three approaches. In general, large n n n and/or k M k_M k M favor Maintaining Length p p p , whereas small unified support ∣ U ∣ |\mathcal{U}| ∣ U ∣ favors the Union Method over Resizing to Candidate Set . Runtime comparisons are less straightforward because preprocessing complexity and parallel computation complexity are inversely related across the approaches. Preprocessing is a one-time cost but incurs cost on GPUs because it requires indexing, whereas the parallelized computations are iterative but efficient on GPUs. When k M ≪ p k_M \ll p k M ≪ p , Resizing to Candidate Set and the Union Method are generally preferable.
Active Set Procedure
If p p p is large (e.g p ≥ 10 4 p \ge10^4 p ≥ 1 0 4 ), support selection becomes computationally intensive. It must operate across all p p p features across all iterations. Anticipating a sparse solution because k ≪ p k \ll p k ≪ p , we employ an active set procedure which is commonly used in sparse learning ([17 , 18 ] ). We develop a procedure for active set support selection, or active set, which can be operated on GPUs. Our active set procedure works as follows. First, it considers a small subset A \mathcal{A} A among all p p p features with size ∣ A ∣ < p |\mathcal{A}| < p ∣ A ∣ < p on which to perform support selection. After support selection on this active set A \mathcal{A} A is done, we see if performing one more iteration of support selection on the entire p p p -dimensional β \beta β changes the support. If so, we update A \mathcal{A} A to be the ∣ A ∣ |\mathcal{A}| ∣ A ∣ elements of largest magnitude, and continue active set. If not, then support has stabilized and we exit active set. Notice that active set requires two learning rates: one corresponding to the specific A \mathcal{A} A that accounts for its smaller size; and the “general” learning rate for all p p p features.
Pseudocode for active set is provided in Algorithm 5. We keep track of the old ( A o ) (\mathcal{A}_o) ( A o ) and new ( A n ) (\mathcal{A}_n) ( A n ) active sets, both of length p p p , indicating which element indices are in the active set. In line 6, we obtain computational savings by performing support selection on X A X_{\mathcal{A}} X A of size ( n × ∣ A w ∣ ) (n \times|\mathcal{A}_w|) ( n × ∣ A w ∣ ) and β A \beta_{\mathcal{A}} β A of length ∣ A w ∣ |\mathcal{A}_w| ∣ A w ∣ . In line 7 we define E E E as an elongation operator: After line 6, β o \beta_o β o is of length ∣ A w ∣ |\mathcal{A}_w| ∣ A w ∣ . We then restore β o \beta_o β o to its original length p p p by scattering the ∣ A w ∣ |\mathcal{A}_w| ∣ A w ∣ elements back into their original indices which were precisely the 1s in A w \mathcal{A}_w A w (the other p − ∣ A w ∣ p-|\mathcal{A}_w| p − ∣ A w ∣ indices correspond to zeroes). We then perform one more iteration of support selection on the full β o \beta_o β o to see if the support changes; lines 9-12 cover the two cases described above.
The active set procedure is a loop over an iterative method, support selection which operates on a reduced set of features as updating p p p features is computationally expensive. While we may need to perform support selection multiple times due to changes in A \mathcal{A} A , we expect this cost to be outweighed by the runtime reduction of performing support selection with smaller tensors. There is a tradeoff between the size of the active set ∣ A ∣ |\mathcal{A}| ∣ A ∣ and the number of active set iterations: if ∣ A ∣ |\mathcal{A}| ∣ A ∣ is large, we can expect a few iterations of high runtime; if ∣ A ∣ |\mathcal{A}| ∣ A ∣ is small, many iterations of small runtime. Numerically, we find that ∣ A ∣ |\mathcal{A}| ∣ A ∣ is a few multiples of k k k and is much smaller than p p p .
Algorithm 5 Active Set
Require: X X X , y y y , λ 1 \lambda_1 λ 1 , λ 2 \lambda_2 λ 2 , k k k , η \eta η , β o \beta_o β o , max number of iterations M A S M_{AS} M A S Return: new β w \beta_w β w with ∥ β w ∥ 0 ≤ k \lVert\beta_w\rVert_0 \le k ∥ β w ∥ 0 ≤ k
Initialize β w \beta_w β w with (12) {equivalent to (11) if λ 1 = 0 \lambda_1 = 0 λ 1 = 0 }
Initialize A o ← 0 p A_o \gets0_p A o ← 0 p and A w ← O ( H k ( β w ) ) A_w \gets\mathcal{O}(H_k(\beta_w)) A w ← O ( H k ( β w )) and i ← 1 i \gets1 i ← 1 {0 p 0_p 0 p is a vector of zeros with length p p p }
while A w ≠ A o A_w \ne A_o A w = A o and i ≤ M A S i \le M_{AS} i ≤ M A S do
β o ← β w \beta_o \gets\beta_w β o ← β w
Create X A ← R ( X , A w ) X_A \gets R(X,A_w) X A ← R ( X , A w ) , β A ← R ( β o , A w ) \beta_A \gets R(\beta_o,A_w) β A ← R ( β o , A w ) {A w = { i ∣ ( A w ) i = 1 } A_w = \{i|(A_w)_i = 1\} A w = { i ∣ ( A w ) i = 1 } }
β o ← \beta_o \gets β o ← Algorithm 1 applied on X A X_A X A instead of X X X and β A \beta_A β A instead of β w \beta_w β w {support selection}
β o ← E ( β o ) \beta_o \gets E(\beta_o) β o ← E ( β o ) {E E E defined in this section as an elongation operator}
β w ← H k \beta_w \gets H_k β w ← H k ((12) applied on β o \beta_o β o )
if S ( β w ) = S ( β o ) S(\beta_w) = S(\beta_o) S ( β w ) = S ( β o ) then
return β w \beta_w β w
end if
A o ← A w A_o \gets A_w A o ← A w and A w ← O ( β w ) A_w \gets\mathcal{O}(\beta_w) A w ← O ( β w ) and i ← i + 1 i \gets i + 1 i ← i + 1
end while
Parallelizing over active set uses the same techniques as previously seen. We use the Overarching Method (see § 2.3 ) and apply the Flag Approach or Dynamic Shrinking (see § 2.5 ) across configurations to deal with the if condition in line 9 of Algorithm 5. To parallelize line 6, which is support selection, we use the overarching function explained in § 2.5 to update our ∏ C \prod C ∏ C configurations.
No additional machinery is required for the nested control flow. Each branch decision—including the outer if on line 9 and the stopping criterion within support selection—is evaluated separately for each configuration and can therefore be represented by a Boolean overlay across the ∏ C \prod C ∏ C configurations. Nested conditions are then implemented as elementwise products of the corresponding overlays.
Computational Variants & Additions to ParaDeAl
Different variants of ParaDeAl emerge depending upon the problem dimensions and configurations. Here we discuss two key choices: whether to use dynamic shrinkage for large ∏ C \prod C ∏ C (§ 3.1 ), and whether to calculate ( X T X ) β (X^T X)\beta ( X T X ) β or X T ( X β ) X^T(X\beta) X T ( X β ) in gradient update (Section 3.2). We also devise an algorithm for finding good learning rates η \eta η in § 3.3 . Finally, we describe pair swaps, an addition that improves the support after value modification (§ 3.4 ).
Dynamic Shrinking: Addressing the Control-Dependent Parallelization Problem
Support selection and value modification are iterative procedures applied simultaneously to all ∏ C \prod C ∏ C configurations. As established in § 2.5 , these procedures generally require different numbers of iterations to converge across configurations. The Flag Approach mentioned earlier continues updating all trajectories until the slowest trajectory has converged. Although this preserves full vectorization, it performs redundant computations for configurations that have already converged. Alternately, trajectories may be removed as they converge, thereby eliminating redundant computations. However, the indexing operations required to identify and isolate the remaining trajectories may incur its own overhead.
Dynamic shrinking provides a compromise between these approaches, analogous to dynamic-array resizing. Rather than removing converged trajectories individually or retaining all trajectories until termination, it removes them in geometrically sized batches. A working tensor B R B_R B R stores the active trajectories and their associated hyperparameters. Trajectories satisfying the convergence tolerance are flagged and frozen but remain in B R B_R B R until the active count reaches a prescribed threshold. At that point, the converged β \beta β values are written to their final positions, and B R B_R B R is compacted to contain only the remaining trajectories. The shrink factor s s s specifies the maximum fraction of active trajectories that are allowed to remain until compaction. For example, if ∏ C = 1,000 \prod C = 1{,}000 ∏ C = 1 , 000 and s = 0.7 s = 0.7 s = 0.7 , the first resize occurs the moment fewer than or equal to 700 trajectories remain active. If 686 is the first number of active trajectories trajectories that dips below 700, the next occurs below 480 = ⌊ 686 ⋅ 0.7 ⌋ \lfloor686 \cdot0.7 \rfloor ⌊ 686 ⋅ 0.7 ⌋ . Thus, B R B_R B R is approximately reduced to 70% of its size at each resize. Since each resize removes a fixed fraction of the active trajectories, the number of resizes is logarithmic in ∏ C \prod C ∏ C . For 10 6 10^6 1 0 6 configurations, halving and quartering require at most 14 and 7 resizes, respectively, before the active count falls below N min = 100 N_{\min} = 100 N m i n = 100 . Below this threshold, we avoid further compaction because of its additional bookkeeping overhead.
Dynamic shrinking directly reduces computation and storage: after the j j j th resize, each gradient step operates on a tensor of size ( 1 − s ) j (1-s)^j ( 1 − s ) j relative to the original. It may also reduce wall-clock time, as demonstrated in § 4.2 . Pruning at every iteration requires O ( M S S ) O(MS_S) O ( M S S ) gather operations, each interrupting vectorized execution, whereas dynamic shrinking requires only O ( log ∏ C ) O(\log\prod C) O ( log ∏ C ) gathers, independently of the iteration count. Thus, the number of costly gather operations is independent of the computation length, while their benefits persist over subsequent iterations. Dynamic shrinking is therefore most effective when ∏ C \prod C ∏ C is large and iteration counts vary substantially across configurations.
We note that after the first resize, the rows of B R B_R B R no longer form a Cartesian product of the hyperparameter values; hence, the grid representation of § 2.4 cannot be retained. Subsequent updates instead use a tuple representation with an explicit configuration list. Algorithm 6 presents pseudocode for a generic parallel update P \mathcal{P} P , applicable without modification to support selection, value modification, and the active-set procedure. § 4.2 evaluates the validity of dynamic shrinking.
Algorithm 6. Dynamic Shrinking
Require: B B B , the ∏ C \prod C ∏ C initial β \beta β s; hyperparameter lists H H H ; parallel update P \mathcal{P} P ; convergence test T \mathcal{T} T ; shrink factor s s s ; floor N min N_{\min} N m i n ; iteration cap M M M
Return: B F B_F B F , the final β \beta β for each of the ∏ C \prod C ∏ C configurations
B R ← B B_R \leftarrow B B R ← B { B S B_S B S is the working tensor, holding only trajectories still running}
Initialize B F B_F B F of size ( ∏ C × p ) (\prod C \times p) ( ∏ C × p ) {filled in as trajectories retire}
ι ← ( 1 , 2 , … , ∏ C ) \iota\leftarrow(1,2,\ldots,\prod C) ι ← ( 1 , 2 , … , ∏ C ) { ι j \iota_j ι j is the row of B F B_F B F to which row j j j of B R B_R B R belongs}
α ← 1 ∏ C \alpha\leftarrow1_{\prod C} α ← 1 ∏ C { α j = 1 \alpha_j = 1 α j = 1 while trajectory j j j is still running; 1 q 1_q 1 q is a vector of ones of length q q q }
a ← ∏ C a \leftarrow\prod C a ← ∏ C and a R ← ∏ C a_R \leftarrow\prod C a R ← ∏ C {number active now, and number active at the most recent resize}
i ← 1 i \leftarrow1 i ← 1 and grid2tuple ← \leftarrow ← False
while i ≤ M i \le M i ≤ M do
B N ← P ( B R , H ) B_N \leftarrow\mathcal{P}(B_R,H) B N ← P ( B R , H ) {one iteration, taken in parallel over every row of B R B_R B R }
δ ← T ( B R , B N ) \delta\leftarrow\mathcal{T}(B_R,B_N) δ ← T ( B R , B N ) { δ j = 1 \delta_j = 1 δ j = 1 if trajectory j j j has just met its tolerance}
B R ← α ⊙ B N + ( 1 − α ) ⊙ B R B_R \leftarrow\alpha\odot B_N + (1-\alpha)\odot B_R B R ← α ⊙ B N + ( 1 − α ) ⊙ B R {already-retired rows keep their value; torch.where, so no indexing}
α ← α ⊙ ( 1 − δ ) \alpha\leftarrow\alpha\odot(1-\delta) α ← α ⊙ ( 1 − δ ) and a ← ∑ j α j a \leftarrow\sum_j \alpha_j a ← ∑ j α j
if a = 0 a = 0 a = 0 then
B F [ ι ] ← B R B_F[\iota] \leftarrow B_R B F [ ι ] ← B R
return B F B_F B F
end if
if a ≤ ( 1 − s ) ⋅ a R a \le(1-s)\cdot a_R a ≤ ( 1 − s ) ⋅ a R AND a > N min a > N_{\min} a > N m i n then
B F [ { ι j : α j = 0 } ] ← { ( B R ) j : α j = 0 } B_F[\{\iota_j:\alpha_j=0\}] \leftarrow\{(B_R)_j:\alpha_j=0\} B F [{ ι j : α j = 0 }] ← {( B R ) j : α j = 0 } {retire every converged trajectory at once}
B R ← { ( B R ) j : α j = 1 } B_R \leftarrow\{(B_R)_j:\alpha_j=1\} B R ← {( B R ) j : α j = 1 } , H ← { H j : α j = 1 } H \leftarrow\{H_j:\alpha_j=1\} H ← { H j : α j = 1 } , ι ← { ι j : α j = 1 } \iota\leftarrow\{\iota_j:\alpha_j=1\} ι ← { ι j : α j = 1 } {the resize: one gather, incurred O ( log ∏ C ) O(\log\prod C) O ( log ∏ C ) times in total}
α ← 1 a \alpha\leftarrow1_a α ← 1 a and a R ← a a_R \leftarrow a a R ← a
grid2tuple ← \leftarrow ← True {rows of B S B_S B S are no longer a cross product, so P \mathcal{P} P takes its tuple path}
end if
i ← i + 1 i \leftarrow i+1 i ← i + 1
end while
B F [ ι ] ← B R B_F[\iota] \leftarrow B_R B F [ ι ] ← B R
return B F B_F B F
Computing (XTX) Versus XT(X)
Each gradient step in (11) requires X T X β X^{T}X\beta X T X β , where X ∈ R n × p X \in\mathbb{R}^{n \times p} X ∈ R n × p and β ∈ R p \beta\in\mathbb{R}^{p} β ∈ R p . We know that there are two ways in which this operation can be performed, ( X T X ) β (X^{T}X)\beta ( X T X ) β or X T ( X β ) X^{T}(X\beta) X T ( X β ) , with different computational costs. The first form permits X T X ∈ R p × p X^{T}X \in\mathbb{R}^{p \times p} X T X ∈ R p × p to be precomputed and reused, whereas the right-associated form requires both multiplications at every iteration because β \beta β changes. The preferred form depends primarily on the dimensions of X X X . When p ≫ n p \gg n p ≫ n , forming and storing the Gram matrix is costly, favoring X T ( X β ) X^{T}(X\beta) X T ( X β ) . When n ≫ p n \gg p n ≫ p , precomputing X T X X^{T}X X T X is comparatively inexpensive and its cost is amortized across iterations. In intermediate regimes, the choice also depends on the iteration count and Q C QC QC . We evaluate this trade-off empirically, with further analysis provided in Appendix A.
Learning Rate Selection
The analysis of Section 2.1 provides a conservative estimate of the step size η \eta η in Update 9 that is guaranteed to converge. That estimate is likely too small because β \beta β is sparse (k ≪ p k \ll p k ≪ p ). As a result, we would like a more aggressive choice of η \eta η , which is difficult to determine through theoretical analysis. If no η \eta η set has been provided by the ParaDeAl user, we can introduce our own learning rate selection process which works as follows: For the operation requiring a learning rate (e.g. support selection), we test a series of learning rates for a small number T L R T_{LR} T L R of iterations, then select the largest one that has not diverged.
To select a learning rate for support selection, we take a collection of η \eta η s geometrically spaced around η 0 \eta_0 η 0 and run Update 9 for T L R = 15 T_{LR} = 15 T L R = 15 iterations. Afterwards, we select the largest η \eta η , η ∗ \eta^{*} η ∗ , that has not diverged, giving us our learning rate for support selection. (We then continue running support selection with this single η ∗ \eta^{*} η ∗ .)
For value modification when λ 1 ≠ 0 \lambda_1 \ne0 λ 1 = 0 , the η \eta η selection procedure is identical: select a set of candidate learning rates; run value modification for T L R = 15 T_{LR} = 15 T L R = 15 iterations; and select the largest η \eta η that does not diverge.
Our η \eta η selection procedure can also be performed within active set; this will be discussed in Section 4.4. When active set is present, there are two separate operations that require learning rates: value modification within an active set iteration (corresponding to η V M \eta_{VM} η V M ) and value modification on the iteration checking whether we change the active set (corresponding to η S S \eta_{SS} η S S ). As we explained in Section 2.2, there can be several learning rates of different magnitudes depending on the particular algorithm or operation being applied.
Performing learning rate selection is computationally attractive, as it avoids performing ParaDeAl in its entirety across several learning rates. It is worth noting that η ∗ \eta^{*} η ∗ may depend on two hyperparameters: λ 2 \lambda_2 λ 2 , which affects the learning rate bound in Section 2.1; and k k k , which affects the practical amount by which the true η ∗ \eta^{*} η ∗ will be larger than that bound.
Pair Swaps: Improving the Support After Value Modification
Support selection followed by value modification returns a point that the hard-soft thresholding update cannot improve. A better support can still be close by, especially when features are correlated (see the note at the end of Section 2.2). Coordinate descent methods such as L0Learn face the same issue, and Hazimeh and Mazumder [18 ] address it with a local search that tries to exchange features in and out of the support. We add a step of the same kind to ParaDeAl, run after value modification and designed so that every configuration is handled at once.
Moves and their exact cost. Consider one configuration, with solution β \beta β after value modification, support S S S and residual r = y − X β r = y - X\beta r = y − X β . A move removes a set D ⊆ S \mathcal{D} \subseteq S D ⊆ S of features from the support and adds a set J \mathcal{J} J of features from outside it. We allow at most two features on each side, which is why we call the procedure pair swap : add one feature, exchange one for one, add two, drop one and add two, and exchange two for two. Moves that add features are allowed only if the new support still has at most k k k features.
The appeal of these moves is that their effect on the objective can be computed exactly and cheaply. Recall that every column of X X X has unit norm, and let c = X T r c = X^{T}r c = X T r be the correlations of the features with the current residual. If the coefficients outside D ∪ J \mathcal{D} \cup\mathcal{J} D ∪ J are held fixed, adding a single feature j j j with the best possible coefficient u u u lowers the objective by
g ( c j ) = − min u ( − 2 u c j + ( 1 + λ 2 ) u 2 + λ 1 ∣ u ∣ ) = ( 2 ∣ c j ∣ − λ 1 ) + 2 4 ( 1 + λ 2 ) , (23) g(c_j) = -\min_{u}\left(-2u c_j + (1+\lambda_2)u^2 + \lambda_1|u|\right) = \frac{(2|c_j|-\lambda_1)_+^2}{4(1+\lambda_2)}, \tag*{(23)} g ( c j ) = − u min ( − 2 u c j + ( 1 + λ 2 ) u 2 + λ 1 ∣ u ∣ ) = 4 ( 1 + λ 2 ) ( 2∣ c j ∣ − λ 1 ) + 2 , (23)
where ( a ) + = max ( a , 0 ) (a)_+ = \max(a,0) ( a ) + = max ( a , 0 ) , and removing a single feature i i i raises the objective by
d i = 2 β i c i + β i 2 − λ 1 ∣ β i ∣ − λ 2 β i 2 . (24) d_i = 2\beta_i c_i + \beta_i^2 - \lambda_1|\beta_i| - \lambda_2\beta_i^2. \tag*{(24)} d i = 2 β i c i + β i 2 − λ 1 ∣ β i ∣ − λ 2 β i 2 . (24)
Once feature i i i is removed, the residual becomes r + x i β i r+x_i\beta_i r + x i β i and the correlation of feature j j j becomes c j + ( x j T x i ) β i c_j+(x_j^{T}x_i)\beta_i c j + ( x j T x i ) β i . The exact change in the objective of exchanging i i i for j j j is therefore
Δ F ( i → j ) = d i − g ( c j + ( x j T x i ) β i ) . (25) \Delta F(i \to j) = d_i - g\left(c_j+(x_j^{T}x_i)\beta_i\right). \tag*{(25)} Δ F ( i → j ) = d i − g ( c j + ( x j T x i ) β i ) . (25)
Equation (25) shows why exchanges help most when features are correlated. If x j x_j x j is nearly a copy of x i x_i x i , then x j T x i ≈ 1 x_j^{T}x_i \approx1 x j T x i ≈ 1 , so feature j j j inherits almost all of the correlation that feature i i i carried and can take over its role, possibly at a lower objective. Hard thresholding cannot see this, because it compares coefficient sizes rather than the objective after a refit. Moves involving two added features need the best pair of coefficients instead of a single one, which is a 2 × 2 2 \times2 2 × 2 problem with a closed form when λ 1 = 0 \lambda_1 = 0 λ 1 = 0 and a few exact coordinate steps otherwise.
One round. To keep the number of moves small, we only consider adding the M = 16 M = 16 M = 16 outside features with the largest single-feature gain g ( c j ) g(c_j) g ( c j ) . One-for-one exchanges pair each of these with every feature in the support, and the moves that drop two features use the D = 8 D = 8 D = 8 support features that are cheapest to remove. Each configuration then applies its best move, provided that the move lowers the objective by more than a relative 10 − 7 10^{-7} 1 0 − 7 (smaller changes are rounding noise in fp32). Value modification then refits all coefficients on the new support, starting from the current coefficients, and the refit is kept if it lowers the objective further. Because this refit follows every accepted move, each configuration ends pair swaps at the value modification solution on its final support, and no further value modification is needed. A configuration stops when no move lowers its objective, or after at most M P S = 200 M_{PS} = 200 M P S = 200 rounds.
What pair swaps guarantee. Every accepted move strictly lowers the objective, so pair swaps can never make a solution worse, and since there are finitely many supports, the procedure stops. When it stops, no move it considers lowers the objective: the solution is a local minimum with respect to exchanging up to two features, which is a stronger property than being a fixed point of IHT. This is the same kind of guarantee as the swap-based local minima of [18 ] , restricted to the candidate features above.
Pair swaps are inherently parallel. Every step of a round is the same computation for every configuration, so a round runs for all configurations at once, as summarized in Figure 3 and Algorithm 7. The correlations of all configurations come from one matrix product X T R X^{T}R X T R , where R R R holds all residuals, which is the same product as in a support selection update. The scores in Equations (23) –(25) are elementwise operations on tensors of shape (configurations × \times × candidates × \times × support), using small blocks of X T X X^{T}X X T X gathered for each configuration. The best move of each configuration is a row-wise minimum, and the refit is the parallel value modification of § 2.6 . Configurations with no improving move leave the batch, as in Dynamic Shrinking (§ 3.1 ). A round therefore costs about as much as one full-width support selection update, plus a refit on supports of size k k k .
Figure 3. Pair swap. (a) An exchange removes one feature from the support and adds one from outside it; moves with two features on either side work the same way. (b) Each round computes the correlations of all configurations with one matrix product, scores every candidate move exactly, and applies each configuration’s best move followed by a refit. A configuration leaves the batch once no move lowers its objective.
Effect. Pair swaps matter most when features are strongly correlated. On synthetic data with independent features, ParaDeAl without pair swaps already reaches the objective of L0Learn and pair swaps change almost nothing. On synthetic data in which nearby features are strongly correlated, with correlation 0.9 ∣ i − j ∣ 0.9^{|i-j|} 0. 9 ∣ i − j ∣ or 0.99 ∣ i − j ∣ 0.99^{|i-j|} 0.9 9 ∣ i − j ∣ between features i i i and j j j , ParaDeAl without pair swaps reaches on average only 62 to 79% of the objective quality of L0Learn (L0Learn’s objective divided by ParaDeAl’s), and the shortfall comes from supports of moderate size. Pair swaps raise this ratio to between 0.99 and 1.03 over three random datasets, so that ParaDeAl is often slightly better than L0Learn, and they recover about as many of the true features as L0Learn does. They add 0.1 to 0.7 seconds per grid of 900 configurations, and ParaDeAl with pair swaps still takes 0.5 to 1.6 seconds, against 5.7 to 7.4 seconds for L0Learn. Section 5.4 reports the effect on real data, and Appendix O gives the full synthetic results.
Algorithm 7 Parallel Pair Swap
Require: X , y X, y X , y ; solutions B B B of all configurations after value modification; per-configuration k , λ 1 , λ 2 k, \lambda_1, \lambda_2 k , λ 1 , λ 2 ; candidate counts M , D M, D M , D ; maximum number of rounds M P S M_{PS} M P S
Return: B B B , with every row’s objective no larger than before
α ← 1 Q C { α j = 1 \alpha\leftarrow\mathbf{1}_{Q_C}\ \{\alpha_j = 1 α ← 1 Q C { α j = 1 while configuration j j j is still swapping} \} }
for t = 1 , … , M P S t = 1, \ldots, M_{PS} t = 1 , … , M P S do
R ← y − X B R \leftarrow y - XB R ← y − X B and G ← X T R G \leftarrow X^{T}R G ← X T R for the rows with α j = 1 \alpha_j = 1 α j = 1 {one full-width product for all of them}
In parallel over rows: candidate additions J \mathcal{J} J (the M M M largest g ( c j ) g(c_j) g ( c j ) outside the support) and drops (the D D D smallest d i d_i d i )
Gather the blocks X J T X S X_{\mathcal{J}}^{T}X_S X J T X S and X J T X J X_{\mathcal{J}}^{T}X_{\mathcal{J}} X J T X J for every row {batched products of size M × k M \times k M × k and M × M M \times M M × M }
Score every move with Equations (23) –(25) ; Δ F j ∗ ← \Delta F_j^* \leftarrow Δ F j ∗ ← row-wise minimum
α ← α ⊙ 1 { Δ F j ∗ < − 10 − 7 F j } \alpha\leftarrow\alpha\odot\mathbf{1}\{\Delta F_j^* < -10^{-7}F_j\} α ← α ⊙ 1 { Δ F j ∗ < − 1 0 − 7 F j }
if ∑ j α j = 0 \sum_j \alpha_j = 0 ∑ j α j = 0 then
return B B B
end if
Apply the best move to every row with α j = 1 \alpha_j = 1 α j = 1 ; refit those rows with value modification and keep the refit where it lowers F F F
Remove rows with α j = 0 \alpha_j = 0 α j = 0 from the working batch {as in Dynamic Shrinking}
end for
return B B B
Experimental Analysis of ParaDeAl’s Components
This section evaluates the components of ParaDeAl on synthetic data. We study three questions: the benefits of parallelism (on CPU and GPU) and the utility of the GPU (Section 4.1); the relative performance of the solutions to the Control-Dependent Parallelization Problem and the Computation-Memory Tradeoff Problem (Sections 4.2 and 4.3); and the gains from the active set procedure (Section 4.4). Section 5 then compares ParaDeAl with state-of-the-art CPU methods.
For all of the following experiments, our times reported are the median of 3 trials. For the experiments in this section in particular, we have X X X be an i.i.d. Gaussian with mean 0 and standard deviation 1. We standardize all features of X X X so that all features have mean 0 and standard deviation 1. Unless otherwise mentioned, all computation is in fp32 on a single NVIDIA L40S.
Benefits of Parallelism (CPU, GPU) and GPU
ParaDeAl’s central benefit is that it can get solutions to multiple problems in parallel, whereas competing methods can only do so iteratively. This advantage is compounded with ParaDeAl’s ability to be used on both GPUs and CPUs, whereas competing methods are CPU-only.
To measure the individual and joint benefits of these two design choices, we use a 2 × 2 2 \times2 2 × 2 design crossing hardware {GPU, CPU} with execution strategy {parallel aka ParaDeAl, iterative}.
We consider a grid of 3,125 configurations, with each of the 5 hyperparameters receiving 5 different values. Specifically, k ∈ { 5 , 10 , 25 , 50 , 100 } k \in\{5, 10, 25, 50, 100\} k ∈ { 5 , 10 , 25 , 50 , 100 } , λ 1 , λ 2 ∈ { 0.001 , 0.01 , 0.1 , 1 , 10 } \lambda_1, \lambda_2 \in\{0.001, 0.01, 0.1, 1, 10\} λ 1 , λ 2 ∈ { 0.001 , 0.01 , 0.1 , 1 , 10 } , η ∈ { 5 , 2 , 1 , 0.5 , 0.2 } × 10 − 4 \eta\in\{5, 2, 1, 0.5, 0.2\} \times10^{-4} η ∈ { 5 , 2 , 1 , 0.5 , 0.2 } × 1 0 − 4 , and β o \beta_o β o is one of the following five choices: all 0s; all 1s; all -1s; standard Gaussian; uniform on [ − 1 , 1 ] [-1, 1] [ − 1 , 1 ] . There is a single ( X , y ) (X, y) ( X , y ) with n = 500 n = 500 n = 500 and p = 1000 p = 1000 p = 1000 . y y y is generated from a 25-sparse signal at a signal-to-noise ratio ∥ X β ∥ 2 2 / ∥ ϵ ∥ 2 2 \|X\beta\|_2^2/\|\epsilon\|_2^2 ∥ X β ∥ 2 2 /∥ ϵ ∥ 2 2 of 25 (Mazumder et al. [23 ] , see Appendix § 11 ). We force all iterative loops to run for exactly 1,000 iterations with no early termination (tolerance 0), so that each setup performs the same arithmetic and any difference in runtime is due to the implementation alone; that is, we use the Max Number of Iterations approach to the Control-Dependent Parallelization Problem. For the Computation-Memory Tradeoff Problem, we use Maintaining Length p p p . Each wall-clock runtime result is the median of three repetitions following one untimed warm-up, and every GPU measurement is preceded by a device synchronization, without which the recorded time reflects kernel launch rather than kernel execution. All computation is in fp32 on a single NVIDIA L40S GPU and 16 CPU threads of the same node, and the Gram matrix X T X X^T X X T X is formed once and is shared across the four setups.
Of the 3,125 configurations, 3,124 obtain the same support under the iterative and parallel strategies, with nearly identical coefficients (absolute differences below 10 − 2 10^{-2} 1 0 − 2 ). Upon examination, the exception happens because two different supports are selected due to floating point tolerance discrepancy on the order of 10 − 7 10^{-7} 1 0 − 7 . Moreover, it is GPU Iterative which differs from the other three methods (GPU ParaDeAl, CPU ParaDeAl, CPU Iterative) by 0.63% on the objective ∥ y − X β ∥ 2 2 + λ 1 ∥ β ∥ 1 + λ 2 ∥ β ∥ 2 2 \|y - X\beta\|_2^2 + \lambda_1\|\beta\|_1 + \lambda_2\|\beta\|_2^2 ∥ y − X β ∥ 2 2 + λ 1 ∥ β ∥ 1 + λ 2 ∥ β ∥ 2 2 .
The row and column labeled “Speedup” in Table 2 marginalize/separate the two effects. Moving from CPU to GPU while using ParaDeAl yields 35.0× speedup; adopting ParaDeAl while staying on the GPU yields a speedup of 609.6×. Thus, parallelization across configurations, rather than the hardware alone, accounts for most of the acceleration. We emphasize that ParaDeAl is not just a GPU technique: it speeds up CPU-based computation by 12.1×, since a single matrix product over all configurations replaces 3,125 separate products and amortizes memory traffic that the iterative loop pays repeatedly.
Table 2. Wall-clock seconds to solve all 3,125 configurations, with per-configuration milliseconds in parentheses. Numbers are the median of three trials. The marginal entries give the speedup along each factor; the lower-right entry compares ParaDeAl GPU versus iterative CPU. Green marks the fastest cell and red the slowest.
The slowest cell is iterative GPU, not iterative CPU; the CPU is 43% faster. Iterative GPU combines the disadvantages of both settings: the loop over configurations seems to remove the simultaneity that the GPU is supposed to, while each individual iteration, a single p × p p \times p p × p by p × 1 p \times1 p × 1 product, is too small to occupy the device, so iterative GPU becomes bound by kernel launch overhead rather than arithmetic. This deficit depends on the problem size: at n = 1000 n = 1000 n = 1000 , p = 2000 p = 2000 p = 2000 with 2,500 configurations, the same comparison inverts to 1.28× in the GPU’s favor, because the larger products begin to fill the device. As the dimensions (especially p p p ) of X X X grow, the GPU appears more favorable overall.
Does a faster GPU help? Table 3 repeats two workloads on three NVIDIA GPUs, from the L40S to the newer and faster H100 and H200, and reports the runtime and peak memory of each: the ParaDeAl GPU cell of Table 2 , and one full grid from Section 5 (the Crime dataset with 30 × 30 configurations, solved for both penalty families exactly as in that section). The small problem of Table 2 takes the same time on every card: it is limited by the overhead of launching kernels rather than by arithmetic, so a faster card has nothing to speed up. The larger grids run about 2× faster on the H100 and H200 than on the L40S. Peak memory is the same on all three cards and far below the capacity of any of them, so the larger memory of the newer cards brings no benefit here, and the three GPUs return the same supports on all but at most 2 of the 3,125 configurations, with objectives that agree to about 10 − 9 10^{-9} 1 0 − 9 in relative terms.
Table 3. The same workloads on three GPUs. Each time is the median of three trials after an untimed warm-up, in fp32. The L0+L2 time includes the support search with the lowest-objective rule (Section 2.2.1) and the pair swaps (Section 3.4), which take about 0.12 seconds on every card; the L1+L2 time is ParaDeAl with FISTA, as in Section 5.
Comparing Control-Dependent Parallelization Schemes
Section 2.5 introduced the Control-Dependent Parallelization Problem (CDPP): different configurations take different numbers of iterations to converge, both in support selection and in value modification. Section 3.1 described Dynamic Shrinking, which reduces redundant computation by periodically removing converged configurations from the working tensor. Here we compare the Flag Approach with Dynamic Shrinking . Note that Only Unstabilized corresponds to the limiting case of compacting after every iteration (the row s = 1 s = 1 s = 1 (guarded) below).
We consider 7 different values each for ( k , λ 1 , λ 2 , η , β 0 ) (k, \lambda_1, \lambda_2, \eta, \beta_0) ( k , λ 1 , λ 2 , η , β 0 ) , yielding Π C = 7 5 = 16,807 \Pi_C = 7^5 = 16{,}807 Π C = 7 5 = 16 , 807 . We set n = 10 3 n = 10^3 n = 1 0 3 , p = 10 4 p = 10^4 p = 1 0 4 , a relative tolerance of 10 − 4 10^{-4} 1 0 − 4 , and an iteration cap of 10 4 10^4 1 0 4 for each iterative algorithm. For Dynamic Shrinking , we sweep across values of the shrink factor s s s , and we stop once the number of configurations dips below 100. Moreover, the grids are specified as scale-free fractions, so the same specification is meaningful at any problem size: η \eta η as a fraction of the baseline value 1 / σ max 2 ( X ) = 5.796 × 10 − 5 1/\sigma_{\max}^2(X) = 5.796 \times10^{-5} 1/ σ m a x 2 ( X ) = 5.796 × 1 0 − 5 , λ 1 \lambda_1 λ 1 as a fraction of λ max = 2 ∥ X T y ∥ ∞ = 6132 \lambda_{\max} = 2\lVert X^T y \rVert_\infty= 6132 λ m a x = 2 ∥ X T y ∥ ∞ = 6132 , λ 2 \lambda_2 λ 2 as a fraction of σ max 2 ( X ) = 1.725 × 10 4 \sigma_{\max}^2(X) = 1.725 \times10^4 σ m a x 2 ( X ) = 1.725 × 1 0 4 , and k k k as a fraction of p p p , giving k ∈ { 10 , 25 , 50 , 100 , 200 , 350 , 500 } k \in\{10, 25, 50, 100, 200, 350, 500\} k ∈ { 10 , 25 , 50 , 100 , 200 , 350 , 500 } against a true support of k ⋆ = 50 k^\star= 50 k ⋆ = 50 . All configurations converge for these choices of η \eta η . σ max 2 \sigma_{\max}^2 σ m a x 2 is obtained by power iteration, and the gradient is always computed as X T ( X β ) X^T(X\beta) X T ( X β ) because p > n p > n p > n .
The setup is chosen so that the iteration counts vary widely across configurations. In particular, the fastest configuration reaches convergence tolerance in 13 iterations, the median in 236, the 90th percentile in 1547, and the slowest in 5,125, a factor of 394 between the extremes. All 16,807 configurations converge within the cap, ensuring that the cap does not interfere with a fair comparison. The flag approach must carry every configuration for all 5,125 iterations, performing 86.1M row-iterations where 9.5M would suffice, an excess of 811%. Dynamic shrinking removes this excess.
Table 4 reports results across different shrink factors. Every shrink factor s s s improves on the flag approach, and the improvement is large: the best setting, s = 0.99 s = 0.99 s = 0.99 , completes in 36.122 s against 332.740 s, a speedup of 9.21×, while the least effective setting tested, s = 0.25 s = 0.25 s = 0.25 , still gives 4.56×. The observed gather counts track the prediction log ( ∏ C / N min ) / log ( 1 / s ) \log(\prod C/N_{\min})/\log(1/s) log ( ∏ C / N m i n ) / log ( 1/ s ) closely, confirming that the number of resizes is logarithmic in ∏ C \prod C ∏ C and independent of the number of iterations run. The excess column exhibits the mechanism directly: as s s s increases, the working tensor is compacted more often and the redundancy in computation decreases. Meanwhile, the percentage of the runtime consumed by gather operations remains low.
Table 4. Dynamic shrinking against the flag approach at ∏ C = 16,807 \prod C = 16{,}807 ∏ C = 16 , 807 , n = 1,000 n = 1{,}000 n = 1 , 000 , p = 10,000 p = 10{,}000 p = 10 , 000 on one NVIDIA L40S. “pred.” is the predicted gather count log ( ∏ C / N min ) / log ( 1 / s ) \log(\prod C/N_{\min})/\log(1/s) log ( ∏ C / N m i n ) / log ( 1/ s ) ; “excess” is row-iterations above the zero-redundancy floor; “% run” is the share of GPU time spent in gathers. Median of 3 repetitions.
To check that the picture does not depend on the particular shape of the instance, we repeated the sweep with 5 values per axis (∏ C = 3,125 \prod C = 3{,}125 ∏ C = 3 , 125 ) at twice the number of features, p = 20,000 p = 20{,}000 p = 20 , 000 . The qualitative picture remains similar: every shrink factor beats the flag approach, and the best setting is again s = 0.99 s = 0.99 s = 0.99 , with a speedup of 8.36×.
We observe that dynamic shrinking is most attractive when ∏ C \prod C ∏ C is large and the hardest configurations require far more iterations than the easiest.
The resize is the only operation that dynamic shrinking adds, and it is much cheaper than the size of the problem instance would suggest. At ∏ C = 16,807 \prod C = 16{,}807 ∏ C = 16 , 807 and p = 10,000 p = 10{,}000 p = 10 , 000 the working tensor occupies 0.63 GiB, and the first resize must read it, write the surviving portion, and scatter the retired rows into their final positions. This first resize takes 3.097 ms on average across shrink factors, against 64.9 ms for a single full-width iteration: a resize costs 0.048 of one iteration. Summed over an entire run, gathers account for at most 4.7% of GPU time over all tested shrink factors. The reason is that a boolean compaction is not a serial operation. Selecting the live rows is a parallel primitive, a prefix sum over the mask followed by a single scatter, and it runs at streaming memory bandwidth. A resize therefore costs essentially one pass over the tensor, which is negligible next to the O ( n p ∏ C ) O(np\prod C) O ( n p ∏ C ) arithmetic of a gradient step. It appears that reindexing does not hurt computational speed. A resize breaks the Cartesian-product representation of the configuration grid, not vectorization.
The repeated sweep shows what that ratio depends on. With p = 20,000 p = 20{,}000 p = 20 , 000 and ∏ C = 3,125 \prod C = 3{,}125 ∏ C = 3 , 125 , a resize costs 0.055 of one full-width iteration, against 0.048 above, even though p p p doubles and ∏ C \prod C ∏ C shrinks by a factor of 5.4. This agrees with a simple cost count. A gather moves O ( p ∏ C ) O(p\prod C) O ( p ∏ C ) bytes once, whereas an iteration performs O ( n p ∏ C ) O(np\prod C) O ( n p ∏ C ) floating-point operations, so their ratio scales as 1 / n 1/n 1/ n and is insensitive to both p p p and ∏ C \prod C ∏ C .
In practice, the relative cost of a resize is controlled by the number of observations alone: it does not grow with the size of the configuration grid or the number of features, which are exactly the quantities that are large when dynamic shrinking is worth using.
The shrink factor trades the number of gathers against the redundancy left in the tensor between them. Small s s s waits until most configurations have retired and pays for few, large resizes; large s s s compacts as soon as a small fraction has finished and pays for many small ones. Because a gather is so cheap, the optimum sits far toward the aggressive end: s = 0.99 s = 0.99 s = 0.99 here, with 434 gathers costing 0.300 s, or 0.8% of that arm’s runtime. Beyond the optimum, the curve turns over: at s = 1 s = 1 s = 1 the tensor is compacted 2436 times and comes within 0% of the floor, but the gathers now consume 4.7% of the run and the arm is slower, 37.437 s against 36.122 s. This is the only regime in which the cost of reindexing is visible at all. The practical guidance is that s s s should be chosen large. The penalty for over-shrinking is mild and bounded by the gather bill, whereas the penalty for under-shrinking is the full redundancy of the flag approach.
We note two limitations. First, kernel launch costs form an overhead. Once the working B B B becomes small, an iteration is dominated by launch overhead rather than arithmetic, which is why N min N_{\min} N m i n exists. For the values of p p p chosen, the overhead is not large enough relative to arithmetic. However, on smaller instances, dynamic shrinking will look less attractive. Second, dynamic shrinking affects the order in which floating-point operations are reassociated, resulting in bitwise different results to those done by the flag approach, and consequently different supports and objective values. This issue is further explored in Appendix § 10 .
Analyzing Computation-Memory Tradeoffs
Section 2.6 introduced the Computation-Memory Tradeoff Problem: after support selection, different configurations have different supports, and there are several ways to operate on them in parallel. The best method depends on the problem dimensions. We compare the three methods in two setups. In both setups we use five different starting points β o \beta_o β o , so that the candidate sets coming out of support selection actually differ across configurations, which is what the Computation-Memory Tradeoff Problem must centrally address:
n = 1,000 n = 1{,}000 n = 1 , 000 , p = 10,000 p = 10{,}000 p = 10 , 000 , k = 100 k = 100 k = 100 , C λ 1 = C λ 2 = 100 C_{\lambda_1} = C_{\lambda_2} = 100 C λ 1 = C λ 2 = 100 , C β = 5 C_{\beta} = 5 C β = 5 , ∏ C = 50,000 \prod C = 50{,}000 ∏ C = 50 , 000 . We have a sizable number of features with a large number of different L1 and L2 penalties, leading to tens of thousands of configurations. This setup tests whether memory becomes prohibitive for Resizing to Candidate Set, which requires a total of 50,000 ⋅ 100 = 5,000,000 50{,}000 \cdot100 = 5{,}000{,}000 50 , 000 ⋅ 100 = 5 , 000 , 000 gathered columns.
n = 1,000 n = 1{,}000 n = 1 , 000 , p = 10,000 p = 10{,}000 p = 10 , 000 , k = { 10 , 20 , 30 , 50 , 100 } k = \{10, 20, 30, 50, 100\} k = { 10 , 20 , 30 , 50 , 100 } , C λ 1 = C λ 2 = 5 C_{\lambda_1} = C_{\lambda_2} = 5 C λ 1 = C λ 2 = 5 , C β = 5 C_{\beta} = 5 C β = 5 , ∏ C = 625 \prod C = 625 ∏ C = 625 . With a much smaller ∏ C \prod C ∏ C , this setup measures the benefit of working with shorter vectors, as in Resizing to Candidate Set and the Union Method, rather than computing over all p p p features, as in Maintaining Length p p p .
In both setups, we generate y y y through a 50-sparse signal with an SNR of 25 (see Appendix § 11 ). We choose our penalty parameters ( λ 1 , λ 2 ) (\lambda_1, \lambda_2) ( λ 1 , λ 2 ) identical to Section 4.2. For all configurations, λ 1 ≠ 0 \lambda_1 \ne0 λ 1 = 0 , so value modification uses the proximal gradient update in Equation (17) . The 5 starting points are the same as in Section 4.1. Each configuration uses learning rate η = 0.9 × 2 / L D \eta= 0.9 \times2/L_D η = 0.9 × 2/ L D .
We run support selection (Algorithm 1) in parallel over all configurations, with a cap of M S S = 1,000 M_{SS} = 1{,}000 M S S = 1 , 000 iterations. All configurations stabilized well under M S S M_{SS} M S S iterations. The candidate set of each configuration is computed once from this output and given to all three methods, so they all solve exactly the same restricted problem. To equalize the cost of all three methods, we set the value modification tolerance to zero and run exactly 500 iterations. Each single-configuration update is written once and batched with vmap and gradien is computed as X T ( X β ) X^T(X\beta) X T ( X β ) . The reported time includes the one-time preprocessing of each method (building the overlays, and for Resizing to Candidate Set and Union Method, gathering the columns of X X X ) and the final step that writes the β \beta β s back to length p p p . Peak memory is measured above what is already stored before value modification begins, namely X X X , y y y , the output of support selection, and the hyperparameter lists. The results are in Table 5 .
Table 5. The three Computation-Memory Tradeoff Problem methods on 500 iterations of value modification, n = 1,000 n = 1{,}000 n = 1 , 000 , p = 10,000 p = 10{,}000 p = 10 , 000 , five starting points β o \beta_o β o , one NVIDIA L40S. “Width” is the length of each β \beta β during the iterations (k M k_M k M , p p p , and ∣ U ∣ \lvert\mathcal{U}\rvert ∣ U ∣ , respectively). “Preproc.” is the one-time setup before the iterations (building overlays and gathering columns of X X X ), “Iters” is the time for the 500 value modification iterations, and “Total” is their sum plus writing the β \beta β s back to length p p p . “PM” is the peak memory above what is stored before value modification begins. Medians of three trials.
Empirically, we find that the final objective values ∥ y − X β ∥ 2 2 + λ 1 ∥ β ∥ 1 + λ 2 ∥ β ∥ 2 2 \lVert y - X\beta\rVert_2^2 + \lambda_1 \lVert\beta\rVert_1 + \lambda_2 \lVert\beta\rVert_2^2 ∥ y − X β ∥ 2 2 + λ 1 ∥ β ∥ 1 + λ 2 ∥ β ∥ 2 2 and β \beta β s are near-identical across the three methods, with a maximum relative difference in ∥ y − X β ∥ 2 2 \lVert y - X\beta\rVert_2^2 ∥ y − X β ∥ 2 2 of 4.7 × 10 − 7 4.7 \times10^{-7} 4.7 × 1 0 − 7 and a maximum absolute difference in any coefficient of 1.1 × 10 − 6 1.1 \times10^{-6} 1.1 × 1 0 − 6 (the largest coefficient is about 3 in absolute value).
The first setup shows the memory cost of Resizing to Candidate Set. Gathering k = 100 k = 100 k = 100 columns of X X X for each of the 50,000 configurations creates 5 × 10 6 5 \times10^6 5 × 1 0 6 columns, a ( 50,000 × 1,000 × 100 ) (50{,}000 \times1{,}000 \times100) ( 50 , 000 × 1 , 000 × 100 ) tensor of 18.6 GiB, which is about 500 times the size of X X X itself. Together with the length-p p p output, this brings the peak to 20.5 GiB above the baseline. This still fits on the 48 GB L40S, but since the tensor grows as O ( ∏ C ⋅ n k M ) O(\prod C \cdot nk_M) O ( ∏ C ⋅ n k M ) , it would run out of memory at roughly ∏ C = 120,000 \prod C = 120{,}000 ∏ C = 120 , 000 for the same n n n and k k k , less than three times the size of this setup. Maintaining Length p p p needs 13.2 GiB, which comes from holding several ( ∏ C × p ) (\prod C \times p) ( ∏ C × p ) tensors (β \beta β s, the overlay O S O_S O S , and the intermediate results of each step). The Union Method needs 2.1 GiB, almost all of which is the length-p p p output.
The explanation for the runtimes is less obvious. Table 1 ranks Resizing to Candidate Set as doing the fewest superfluous calculations, and it does do the least arithmetic of the three. Yet it is 8.3 times slower than the Union Method in the first setup, and only 2.3 times faster than Maintaining Length p p p , even though it works with vectors 100 times shorter. We find that almost all (98%) of the runtime is spent in the two batched products X K β K X_K\beta_K X K β K and X K T r X_K^{T}r X K T r , which take 30.0 ms and 28.7 ms. Each of them reads the whole 18.6 GiB tensor of gathered columns at 670 to 700 GB/s, which is about 80% of the L40S’s peak bandwidth of 864 GB/s. This means the GPU is mostly waiting on memory, not computing. The reason is that each configuration has its own copy of its columns, and a column that has been read is used for only one configuration. If all configurations share one matrix, the same arithmetic turns into a single matrix-matrix product that reads each column of X X X once and uses it for every configuration. On the same GPU this takes 1.4 ms instead of 58.6 ms. Maintaining Length p p p and the Union Method both work this way, but the Union Method has a much shorter width, and it ends up 19 times faster than Maintaining Length p p p .
Table 1. Comparison of three methods to resolve Computation-Memory Tradeoff Problem. Green is best; red, worst.
The width of the union depends on how much the candidate sets overlap. In the first setup, the 50,000 configurations have 375 distinct candidate sets, and their union U \mathcal{U} U has 499 features, or 5% of p p p . This figure is β o \beta_o β o -dependent. The 10,000 configurations that start from β o = 0 \beta_o = 0 β o = 0 give only 3 distinct candidate sets with a union of 101 features, since the first update ranks the features by ∣ X T y ∣ \lvert X^{T}y\rvert ∣ X T y ∣ for all of them. Each of the other four starting points gives between 67 and 131 candidate sets, with a union of 211 to 254 features. We use several starting points in this experiment for exactly this reason. With β o = 0 \beta_o = 0 β o = 0 alone the candidate sets would be nearly the same, and the Computation-Memory Tradeoff Problem would hardly come up. If the candidate sets have less in common, for example with many more random starting points or a weak signal, ∣ U ∣ \lvert\mathcal{U}\rvert ∣ U ∣ gets close to min ( ∏ C ⋅ k , p ) \min(\prod C \cdot k,p) min ( ∏ C ⋅ k , p ) , and the Union Method is no better than Maintaining Length p p p . Resizing to Candidate Set does not have this problem, but it needs much more memory.
The second setup is small. All three methods finish in under 0.6 s and use at most 0.26 GiB, but the order is the same as before. The Union Method is 5.1 times faster than Resizing to Candidate Set and 8.9 times faster than Maintaining Length p p p . With 625 configurations and ∣ U ∣ = 429 \lvert\mathcal{U}\rvert= 429 ∣ U ∣ = 429 , one iteration of the Union Method takes 0.13 ms, which is about as fast as a GPU iteration gets because of kernel launch overhead. The other two methods are big enough that their actual work sets the time. Padding to k M k_M k M with the overlay, which we use to handle several values of k k k , gives the same β \beta β s as the other two methods. Since we are talking about fractions of a second here, the choice of method only really matters when ∏ C \prod C ∏ C is large.
Based on these results, we use the Union Method by default. It is the fastest in both setups, it used the least memory, and its preprocessing took under 8 ms. When ∣ U ∣ \lvert\mathcal{U}\rvert ∣ U ∣ is close to p p p , we switch to Maintaining Length p p p , which uses less memory than Resizing to Candidate Set in both setups. We only use Resizing to Candidate Set when $\lvert\mathcal{U}\rvert is large, k M ≪ p k_M \ll p k M ≪ p , and the O ( ∏ C ⋅ n k M ) O(\prod C \cdot n k_M) O ( ∏ C ⋅ n k M ) tensor fits easily in GPU memory.
Benefits of the Active Set Procedure
We call an update that operates on all p p p features a full-width update. Without an active set, every support selection update is a full-width update, which costs O ( n p ) O(np) O ( n p ) . The active set procedure of § 2.7 runs support selection on a subset A \mathcal{A} A of the features instead, followed by a single full-width update that checks whether any feature outside A \mathcal{A} A should enter the support. This section shows that, for large p p p , this gives substantial speedups without making the solution worse.
Setup. For each test case we run ParaDeAl twice independently, once with the active set and once without. In each run, ParaDeAl parallelizes across the five starting points β o \beta_o β o of § 4.1 (all zeros, all ones, all negative ones, standard Gaussian, and uniform on [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] ), with one value each of k k k , λ 1 \lambda_1 λ 1 and λ 2 \lambda_2 λ 2 . We take n = 1,000 n = 1{,}000 n = 1 , 000 and p ∈ { 10 5 , 3 × 10 5 , 10 6 } p \in\{10^5, 3 \times10^5, 10^6\} p ∈ { 1 0 5 , 3 × 1 0 5 , 1 0 6 } , and generate the response from a 50-sparse coefficient vector with an SNR of 25. We consider k ∈ { 10 , 50 , 100 } k \in\{10, 50, 100\} k ∈ { 10 , 50 , 100 } at every p p p , and k ∈ { 250 , 500 } k \in\{250, 500\} k ∈ { 250 , 500 } at p ≥ 3 × 10 5 p \ge3 \times10^5 p ≥ 3 × 1 0 5 , one value of k k k at a time. The penalties are λ 1 = 10 − 3 λ max \lambda_1 = 10^{-3}\lambda_{\max} λ 1 = 1 0 − 3 λ m a x and λ 2 = 10 − 3 σ max 2 ( X ) \lambda_2 = 10^{-3}\sigma_{\max}^2(X) λ 2 = 1 0 − 3 σ m a x 2 ( X ) . The gradient is computed as X T ( X β ) X^T(X\beta) X T ( X β ) , since forming the whole gram matrix X T X X^T X X T X would take 4 TB in fp32 at p = 10 6 p = 10^6 p = 1 0 6 .
The arm without an active set needs one learning rate, for the full-width updates. The arm with the active set needs a second one, for support selection on X A X_{\mathcal{A}} X A . Both are chosen by the learning rate selection of § 3.3 , with candidates η p r e d × { 1 / 16 , 1 / 8 , 1 / 4 , 1 / 2 , 1 , 2 } \eta_{\mathrm{pred}} \times\{1/16, 1/8, 1/4, 1/2, 1, 2\} η pred × { 1/16 , 1/8 , 1/4 , 1/2 , 1 , 2 } , each run for 10 iterations. Here η p r e d = 0.9 / ( σ k 2 + λ 2 ) \eta_{\mathrm{pred}} = 0.9/(\sigma_k^2 + \lambda_2) η pred = 0.9/ ( σ k 2 + λ 2 ) , where σ k 2 = n ( 1 + k / n ) 2 \sigma_k^2 = n(1 + \sqrt{k/n})^2 σ k 2 = n ( 1 + k / n ) 2 approximates σ max 2 \sigma_{\max}^2 σ m a x 2 of a k k k -column submatrix of X X X . Both loops use the stopping rule of § 2.2.1 : support selection on X A X_{\mathcal{A}} X A stops when one update leaves the support unchanged, and the outer loop stops when the full-width check leaves the support unchanged. To break cycles of the form A , B , A A, B, A A , B , A , each loop also stops when the support (in the outer loop, the active set) returns to the one from two steps back. The iteration number limits are M S S = 1,000 M_{SS} = 1{,}000 M S S = 1 , 000 and M A S = 100 M_{AS} = 100 M A S = 100 , which are never exceeded in any test.
To compare how good the supports provided by non-active set and active set are, we run value modification on the support each arm returns and compute the objective F ( β ) F(\beta) F ( β ) of Problem (2), including both penalty terms. Value modification is not timed.
Table 6 shows the results. In ten of the twelve rows the active set is faster, by 1.1 to 5.8 times end to end and by 1.6 to 15.7 times on the solve alone (i.e. excluding time for the learning rate search), and its objective is within 2% of the arm without an active set or better. The speedup grows with p p p and k k k . The reason is the number of full-width updates. Without an active set, every update is full-width, and more of them are needed as k k k grows: 80 at p = 10 6 p = 10^{6} p = 1 0 6 , k = 500 k = 500 k = 500 . With an active set, there is one full-width update per round, and the active set needs only 3 to 7 of them in these rows. The rest of the work runs on at most ∣ A ∣ = 2,500 |\mathcal{A}| = 2{,}500 ∣ A ∣ = 2 , 500 features instead of 10 6 10^{6} 1 0 6 . The gap between “total” and “solve” is learning rate selection, a fixed cost that both arms pay once per batch. As ∏ C \prod C ∏ C grows this cost is spread over more configurations, and the end-to-end speedup approaches the solve-only speedup (Appendix § 14 ).
Table 6. Active set against full-width support selection, five starting points in parallel, n = 1,000 n = 1{,}000 n = 1 , 000 . Times are in milliseconds. “total” includes learning rate selection, “solve” excludes it, and “upd.” counts full-width updates. “obj. diff.” is the relative change in the objective F ( β ) F(\beta) F ( β ) after value modification, averaged over the five starting points; negative values mean the active set found the better support. For each ( p , k ) (p,k) ( p , k ) , ∣ A ∣ |\mathcal{A}| ∣ A ∣ is the size from the sweep { 2 k , 3 k , 4 k , 5 k , 8 k , 10 k , 15 k } \{2k, 3k, 4k, 5k, 8k, 10k, 15k\} { 2 k , 3 k , 4 k , 5 k , 8 k , 10 k , 15 k } of Appendix F that gives the best speedup without a worse objective. Red cells mark the two rows where the arm without an active set stops early on a much worse support.
In the two red rows, at k = 100 k = 100 k = 100 with p = 10 5 p = 10^{5} p = 1 0 5 and 3 × 10 5 3 \times10^{5} 3 × 1 0 5 , the arm without an active set stops after 3 updates. It is faster only because it stops early on a much worse support: the active set lowers the objective by 59 to 70%. In these rows the active set trades a slower run for a much better answer. Appendix § 13 shows why the two arms can end on different supports. In short, from a dense starting point the full-width step is too small to move away from the support given by β o \beta_o β o . The inner loop of the active set works on X A X_{\mathcal{A}} X A , where it can take larger steps.
Figure 4 shows the same rows as runtime against objective. Each arrow goes from the run without the active set to the run with it. Most arrows point to the left along the line at 1, so the active set gives the same objective in less time. The two arrows that point to the right and down are the red rows of Table 6 , where the active set is slower but finds a much better support. In two further rows (p = 3 × 10 5 p = 3 \times10^{5} p = 3 × 1 0 5 , k = 500 k = 500 k = 500 and p = 10 6 p = 10^{6} p = 1 0 6 , k = 100 k = 100 k = 100 ), the active set is both faster and better.
Figure 4. Runtime against objective for the rows of Table 6. The objective is divided by the better of the two runs, so 1 marks the better run. Open circles: no active set; filled circles: active set; each arrow points from the first to the second. Colors mark k k k ; the horizontal axis is logarithmic. Accompanying numbers in Table 6 present some additional information.
The choice of ∣ A ∣ |\mathcal{A}| ∣ A ∣ matters more for accuracy than for speed. Every row of Table 6 uses an ∣ A ∣ |\mathcal{A}| ∣ A ∣ between 2 k 2k 2 k and 5 k 5k 5 k , which is the range we recommend. Larger active sets tend to stop the outer loop too early. At p = 10 6 p = 10^{6} p = 1 0 6 and k ≥ 100 k \ge100 k ≥ 100 , ∣ A ∣ = 10 k |\mathcal{A}| = 10k ∣ A ∣ = 10 k and 15 k 15k 15 k give objectives 8 to 157% worse, and at k = 100 k = 100 k = 100 and 500 they stop after one or two rounds. Appendix § 12 gives the full sweep over ∣ A ∣ |\mathcal{A}| ∣ A ∣ , the variation between runs, and the limitations of the procedure.
Peak memory is similar for the two arms, since it is dominated by the length-p p p tensors of the five configurations: at p = 10 6 p = 10^{6} p = 1 0 6 , 149 MiB without the active set and 175 to 195 MiB with it. Throughout this section each batch has a single value of k k k . Batching several values of k k k together is possible if ∣ A ∣ |\mathcal{A}| ∣ A ∣ is shared across the batch (Appendix § 15 ).
ParaDeAl Versus State-of-the-Art
This section compares ParaDeAl with established CPU-based algorithms on three real datasets, which we expand to between 1.9 × 10 4 1.9 \times10^{4} 1.9 × 1 0 4 and 2.8 × 10 5 2.8 \times10^{5} 2.8 × 1 0 5 features. We then repeat the comparison on three further datasets whose features are less strongly correlated, to see how much the results depend on correlation. In every comparison the competitor chooses the hyperparameter configurations and ParaDeAl solves the same configurations, so speed and accuracy are compared configuration by configuration.
The Competitors
Table 7 lists the methods. L0Learn ([18 , 20 ] ) is a state of the art algorithm for L 0 L_0 L 0 -regularized regression and is the benchmark for the L 0 + L 1 L_0+L_1 L 0 + L 1 and L 0 + L 2 L_0+L_2 L 0 + L 2 modes. For the elastic net (L 1 + L 2 L_1+L_2 L 1 + L 2 ), glmnet ([17 ] ) a popular solver, scikit-learn ([29 ] ) is also a widely used Python implementation, and skglm ([5 ] ) is a recent Python library designed for speed. L0Learn and glmnet compute a warm-started regularization path, in which each solution is the starting point for the next. scikit-learn and skglm fit one configuration at a time, as a user sweeping a grid would. None of the four parallelizes across hyperparameter configurations, which is the axis ParaDeAl is built around, and none solves the L 0 + L 1 + L 2 L_0+L_1+L_2 L 0 + L 1 + L 2 mode.
Two differences between ParaDeAl and the competitors shape the comparison. First, L0Learn penalizes the support size instead of constraining it, so we let L0Learn compute its path and give ParaDeAl the support size and penalty of every solution that L0Learn returns. We run L0Learn without its swap-based local search method which is more compute-intensive. Second, the four competitors run on a single CPU core, since their core algorithms are sequential, while ParaDeAl runs on one NVIDIA L40S GPU. The speedups below therefore compare one GPU with one CPU core. We include no mixed integer solver: at these values of p p p , an exact solver such as Gurobi does not finish a single configuration in the time the other methods take for a whole grid. Appendix J describes the algorithms, the software versions and settings, and how each method’s penalty parameters convert to those of ParaDeAl.
Warm starts. The methods differ in what they reuse from one configuration to the next. L0Learn and glmnet warm-start: along each path, every fit starts from the previous solution, which is a large part of what makes a path cheap. scikit-learn and skglm start every configuration from zero, as a user fitting one configuration at a time would. ParaDeAl starts every configuration from β = 0 \beta= 0 β = 0 as well. The only things it shares across configurations are the step-size search, which is run once per distinct ( k , λ 2 ) (k,\lambda_2) ( k , λ 2 ) , and, within pair swaps, each refit starts from the current coefficients of the same configuration. ParaDeAl therefore gets no help from neighboring solutions, so on runtime the comparison with the two path methods is, if anything, tilted in their favor.
Table 7. The methods compared.
Datasets
We use one dataset from each of three application areas (Table 8). In healthcare, the Diabetes 130-US Hospitals data ([13 , 35 ] ) are used to predict the time a patient spends in hospital. In socioeconomics, the Communities and Crime data ([31 , 31 ] ) are used to predict the rate of violent crime in a community. In meteorology, the Air Quality data ([15 , 16 ] ) are used to predict the hourly temperature.
For each of these datasets, we expand the number of features by using pairwise interactions (the original columns together with every product x i x j x_i x_j x i x j , i < j i < j i < j ) and nearest-neighbor features (each row is augmented with the features of its h h h nearest rows). Every column of the training design is then scaled to mean 0 and unit L 2 L_2 L 2 norm, and the test design receives the same transformation. Appendix K gives the full construction. The resulting datasets are in Table 8.
Datasets with softer correlations. The neighbor features above are close copies of one another, so these three datasets contain many pairs of nearly identical columns: in Air Quality every feature has another feature with correlation above 0.9, and in Diabetes 41% of the features have a near-exact duplicate. Strong correlations are exactly the setting in which the choice of support is hardest (§ 3.4 ). To see how the comparison changes when correlations are weaker, we build three further datasets from polynomial features alone, without neighbors. Each base feature is first replaced by its normal score (its rank, mapped to the corresponding quantile of a standard normal distribution), and the features are then all products of one, two or three distinct base features. We apply this to Communities and Crime again (giving the overlap with the first group), to a healthcare dataset from the US National Health and Nutrition Examination Survey (NHANES) ([11 ] ), with systolic blood pressure as the response, and to a European weather dataset ([21 ] ), with the next day’s temperature in Basel as the response. In NHANES and Weather no two columns have correlation above 0.99, and only 15 to 19% of the features have a partner with correlation above 0.9. Crime keeps strong correlations even without neighbors: 86% of its features have a partner above 0.9 and 20% a partner above 0.99, so it is closer to the first group than to the other two. The datasets are in the lower half of Table 8, and Appendix K gives the construction.
Table 8. The datasets after feature expansion. Top: the three datasets with neighbor features. Bottom: the three datasets with polynomial features only, whose correlations are weaker.
Setup
Modes and configurations. With L ( β ) = ∥ y − X β ∥ 2 2 L(\beta)=\lVert y-X\beta\rVert_2^2 L ( β ) = ∥ y − X β ∥ 2 2 , the L1+L2 mode minimizes L ( β ) + λ 1 ∥ β ∥ 1 + λ 2 ∥ β ∥ 2 2 L(\beta)+\lambda_1\lVert\beta\rVert_1+\lambda_2\lVert\beta\rVert_2^2 L ( β ) + λ 1 ∥ β ∥ 1 + λ 2 ∥ β ∥ 2 2 , the L0+L1+L2 mode adds the constraint ∥ β ∥ 0 ≤ k \lVert\beta\rVert_0\leq k ∥ β ∥ 0 ≤ k , and the L0+L1 and L0+L2 modes keep the constraint and one of the two penalties. In the L0 modes, L0Learn computes paths over a grid of G G G values of its L 1 L_1 L 1 or L 2 L_2 L 2 penalty and G G G values of λ 0 \lambda_0 λ 0 , and each solution on the paths defines one ParaDeAl configuration ( k , λ 1 ) (k,\lambda_1) ( k , λ 1 ) or ( k , λ 2 ) (k,\lambda_2) ( k , λ 2 ) . In the L1+L2 mode, glmnet computes a path of G G G values of its overall penalty strength λ \lambda λ for each of G G G values of its mixing parameter, and ParaDeAl, scikit-learn and skglm solve the same ( λ 1 , λ 2 ) (\lambda_1,\lambda_2) ( λ 1 , λ 2 ) pairs. The L0+L1+L2 mode uses these pairs with k = 50 k=50 k = 50 . We write 10 × 10 10\times10 10 × 10 , 30 × 30 30\times30 30 × 30 and 100 × 100 100\times100 100 × 100 for the grids with G = 10 , 30 , 100 G=10,30,100 G = 10 , 30 , 100 .
ParaDeAl. All configurations of a run are solved together on one L40S GPU in fp32, in chunks sized to a 30 GB memory budget, and every loop uses Dynamic Shrinking (§ 3.1 ). In the L0 modes, the step size of each configuration comes from the parallel search of § 3.3 , and support selection runs inside the active set procedure (§ 2.7 ) with ∣ A ∣ = max ( 250 , 5 k ) \lvert A\rvert=\max(250,5k) ∣ A ∣ = max ( 250 , 5 k ) . Support selection stops by the support-unchanged rule and returns the lowest-objective iterate (§ 2.2.1 ), and the value modification solvers stop once the relative change in β \beta β falls below 5 ⋅ 10 − 4 5\cdot10^{-4} 5 ⋅ 1 0 − 4 in the L0 modes and 10 − 3 10^{-3} 1 0 − 3 in the L1+L2 mode. In the L0 modes, value modification is followed by pair swaps (§ 3.4 ) with at most 200 rounds, and the reported runtime includes them. For L1+L2 we use FISTA ([4 ] ), the accelerated version of proximal gradient, with at most 5,000 iterations (note that for these problems unaccelerated proximal gradient with the same budget ends 2–18% above the competitors’ optimization objective). Appendix § 18 gives the full settings, with additional ablation studies.
Measurements. We compare different procedures based on the optimization objective (after standardizing for the different scales used by different implementations, Appendix § 16 ). Additionally we consider the test error ∥ y t e s t − X t e s t β ∥ 2 \lVert y_{\mathrm{test}} - X_{\mathrm{test}}\beta\rVert^2 ∥ y test − X test β ∥ 2 , relative to ParaDeAl. For each configuration we divide the competitor’s optimization objective by ParaDeAl’s, and likewise for the test error; we report the mean of each ratio over configurations, so a ratio below 1 means that the competitor is more accurate. On Diabetes, the feature expansion creates columns that are nearly constant on the training rows, so a few test entries become very large after scaling. We therefore compute the test error with each test feature clipped to the range of its training column, which changes only the scoring, not the fitted coefficients (Appendix § 17 ); on the other datasets, clipping has almost no effect. Runtime is the wall-clock time of the whole solve. For ParaDeAl, the runtime includes the step-size search and both stages. scikit-learn and skglm are too slow to fit the grids in full, so their runtimes are estimated from a random subset of at most 50 configurations of each grid.
When the features are independent, the comparison in the L0 modes is uneventful: on synthetic data with independent features, ParaDeAl matches the objective of L0Learn to within 0.5% without pair swaps and exactly with them (Appendix § 21 ). The differences reported below therefore come from correlation between features.
Results
Table 9 gives the results on the three datasets with strong correlations, and Table 15 in Appendix § 19 gives the same results on the three polynomial datasets. Each block of rows is one dataset and each group of rows within it is one mode, with ParaDeAl in the first row of the group and its competitors below. The three runtime columns give the wall-clock seconds on each grid; for a competitor, the number in parentheses is its runtime divided by ParaDeAl’s, so a number above 1 means that ParaDeAl is faster. The last two columns give the competitor’s optimization objective and test error divided by ParaDeAl’s, averaged over all configurations of the three grids, so a number below 1 means that the competitor is more accurate. In the L0 modes we also show ParaDeAl without pair swaps; for this row the ratios divide L0Learn’s values by its own. Panel (b) of each table splits the accuracy ratios of the L0 modes by support size, into k k k from 1 to 5, 6 to 20, 21 to 50, 51 to 100, and above 100. The L0 modes are meant to select a small number of features that can be interpreted, so the bins up to k = 100 k = 100 k = 100 are the ones that matter most in practice. The configurations are those of L0Learn, and supports larger than 100 occur only on the 100 × 100 100 \times100 100 × 100 grids, where they make up 23 to 46% of the configurations.
Table 9. Results on the three datasets with strong correlations. ParaDeAl uses the lowest-objective support (§ 2.2.1 ) followed by pair swaps (§ 3.4 ) in the L0 modes, and FISTA with tolerance 10 − 3 10^{-3} 1 0 − 3 in the L1+L2 mode; its runtimes are the median of three runs. Ratios are averaged over all configurations of the three grids; test errors are computed with test features clipped to their training range. The runtimes of scikit-learn and skglm are estimated from at most 50 configurations per grid. For ParaDeAl (no swaps), the ratios divide L0Learn’s values by those of ParaDeAl without pair swaps. Panel (b): L0Learn’s objective (top) and test error (bottom) divided by those of ParaDeAl with pair swaps (blue) or without them (orange), so values above 1 favor ParaDeAl. Lines follow the ranges of k k k (solid: L0+L1, dashed: L0+L2); bars pool all configurations.
Figure a. Runtime, and accuracy over all configurations.
Figure b. Accuracy by support size k k k in the L0 modes, pooled over the three grids.
Table 15. Results on the three polynomial datasets, built without neighbor features (§ 5.2 ). Panel (a) and the settings are as in Table 9 . Panel (b) gives the ratios of Table Figure b as numbers: “ParaDeAl” is ParaDeAl with pair swaps, and “Configurations” gives the number of configurations of each size.
ParaDeAl is faster than every competitor on every grid of every dataset, with one exception: on NHANES in the L0+L1 mode (Appendix § 19 ), the pair swaps of the 100 × 100 100 \times100 100 × 100 grid take long enough that ParaDeAl and L0Learn finish in the same time. In the L0 modes, panel (b) shows that with pair swaps ParaDeAl matches L0Learn’s optimization objective on sparse supports. Pooled over all configurations with k ≤ 100 k \le100 k ≤ 100 , the ratio is between 0.976 and 1.006, and within each bin up to k = 100 k = 100 k = 100 it is between 0.98 and 1.01, except on Air Quality and in a few cases with k k k between 51 and 100 (down to 0.93). The lower pooled ratios of panel (a), 0.91 to 0.99, come from supports larger than 100. For k ≤ 100 k \le100 k ≤ 100 , L0Learn’s test error divided by ParaDeAl’s is between 0.89 and 1.07. In the L1+L2 mode, ParaDeAl with FISTA matches the optimization objective of all three competitors. The L0+L1+L2 mode has no competitor; ParaDeAl solves its 100 × 100 100 \times100 100 × 100 grid in 588 s on Diabetes, 135 s on Crime and 27 s on Air Quality, and in 502 s, 52 s and 210 s on the polynomial versions of Crime, NHANES and Weather.
Summary of findings
L0+L1 and L0+L2 against L0Learn: much faster, and as accurate on sparse supports once pair swaps are used. On the 10 × 10 10 \times10 10 × 10 and 30 × 30 30 \times30 30 × 30 grids, ParaDeAl is 5.9–268× faster than L0Learn. On the 100 × 100 100 \times100 100 × 100 grids the advantage shrinks to 1.5–10× (and to a tie on NHANES in the L0+L1 mode), because these grids also contain
supports of up to 500 features, on which pair swaps need many rounds; without pair swaps, ParaDeAl is 8.9–39× \times × faster there.
The breakdown by support size in panel (b) of Table 9 , and of Table 15 in Appendix § 19 , shows where accuracy is gained and lost. Without pair swaps, ParaDeAl falls further behind L0Learn as k k k grows. On Crime in the L0+L1 mode, for example, the objective ratio is 0.970 for k k k from 1 to 5, 0.882 from 6 to 20, 0.788 from 21 to 50, 0.691 from 51 to 100 and 0.449 above 100, and every other dataset shows the same pattern. Pair swaps remove almost all of this gap on the sparse supports that the L0 modes are meant for. For k k k up to 50, the ratio is between 0.98 and 1.01 on every dataset, except Air Quality in the L0+L2 mode with k ≤ 5 k \le5 k ≤ 5 (0.957). For k k k from 51 to 100 it is between 0.96 and 1.00, except Air Quality in the L0+L1 mode (0.929). A clear gap remains only above k = 100 k = 100 k = 100 (0.68 to 0.97), where the limit of 200 rounds stops pair swaps before they converge. Since these large supports make up a quarter to a half of the 100 × \times × 100 grids, they also explain the lower pooled ratios of panel (a) (0.91 to 0.99). What remains of the gap is largest on Air Quality, in which every feature has a near-copy, and smallest on NHANES and Weather, the two datasets with the weakest correlations. This agrees with the synthetic experiments of § 3.4 , where the gap appears only when features are correlated.
On held-out data the two methods are about equally accurate on sparse supports. With pair swaps and k ≤ 100 k \le100 k ≤ 100 , the L0Learn/ParaDeAl test error ratio is between 0.89 and 1.07, and it is below 0.95 only on Air Quality in the L0+L2 mode with k ≤ 20 k \le20 k ≤ 20 . Without pair swaps, ParaDeAl’s test error is lower than L0Learn’s on Diabetes and on both Crime datasets (pooled ratios 1.12–1.33) despite its worse objective, and this advantage grows with k k k , so part of L0Learn’s lower objective on large supports comes with overfitting.
The two methods usually reach these similar objectives with different features. With pair swaps, ParaDeAl returns exactly L0Learn’s support for up to 83% of the configurations with k k k from 1 to 5 (on NHANES), but for at most 26% of the configurations with larger k k k , and for almost none on Diabetes (Appendix § 23 ). When features are strongly correlated, many different supports fit almost equally well, so this is to be expected.
L1+L2: FISTA matches the competitors and is faster than all of them. glmnet, scikit-learn and skglm agree with each other, and ParaDeAl with FISTA matches their training objective to within 0.3% on every dataset (pooled ratios 0.998–1.000; skglm on Crime is the one exception, at 1.010 in ParaDeAl’s favor). With FISTA, ParaDeAl is faster than glmnet on every grid, by 4.0–17.8× \times × . The advantage is largest on the small grids and on Diabetes, and smallest on the large grids of Crime and Air Quality, where glmnet’s warm-started path does very little work per additional λ \lambda λ . Against the methods that solve one configuration at a time, the advantage is much larger: 31–124× \times × against skglm and 546–5,060× \times × against scikit-learn, at the same accuracy. On the polynomial datasets (Table 15 in Appendix § 19 ) the picture is the same: FISTA matches all three competitors (pooled ratios 0.999–1.016), and it is 3.2–52× \times × faster than glmnet, 23–320× \times × faster than skglm and 744–1,829× \times × faster than scikit-learn.
Storage. On the small grids ParaDeAl uses less memory than L0Learn and glmnet. On the large grids ParaDeAl uses more memory than glmnet and, in most cases, than L0Learn; its GPU peak there is bounded by the 30 GB working budget it is given for chunking configurations, and a smaller budget would trade memory for time. L0Learn peaks at 0.2–30 GB of RAM, glmnet at 0.4–18 GB and skglm below 0.1 GB.
Summary and Further Work
We present ParaDeAl, a GPU-based framework that solves large collections of hyperparameter configurations of the L0-constrained regression problem (2) simultaneously, typically within minutes. ParaDeAl supports L1 and L2 penalties, a hard L0 constraint, and both grid and tuple search. Potential applications include:
Sparsity–accuracy tradeoff in ML modeling. The level of compression that can be achieved in weights or activations depends on the acceptable loss of accuracy. An informed decision requires the objective as a function of k k k ; computing it for many values of k k k is expensive in both time and memory, even with large amounts
of parallel hardware. A parallel algorithm that solves hundreds of values of k k k at once makes it quick to locate the ‘elbow’ of this curve, which can then be refined further, so choosing the sparsity level becomes a tractable problem.
Portfolio optimization. Many financial models have the same structure as Problem (2): a loss function with regularization, where the goal is to select a small number of assets from a large universe. Problems of this form can be solved with ParaDeAl. Variants include latent variable models, most commonly probit or logit models, in which additional variables represent underlying traits of the assets. With modification, ParaDeAl may also be applied to hyperparameter tuning for gradient-boosted machines (GBMs), whose accuracy depends strongly on their hyperparameters and for which little theory on hyperparameter selection exists.
Exploring nonconvex landscapes. In high-dimensional nonconvex ML, a central challenge is to ensure that the local minimum returned by GD is the global minimum, or provably close to it. Many ML objective functions have complicated landscapes. Running many starting points and step sizes at once gives a quick map of the local minima that descent methods reach, which can help characterize these landscapes empirically.
Extensions of ParaDeAl include:
Better procedures for the hard thresholding step. From an implementation perspective, torch.vmap does not support a varying k k k , and the existing alternatives are a binary overlay or a for loop, so a more efficient parallel algorithm would be beneficial. From an algorithmic perspective, top-k k k selection by magnitude may not be the best sparsification rule. In ongoing work, we find that sparsifying a fixed proportion per row or per column improves accuracy over plain magnitude pruning for a set of reconstruction objectives. A data-aware rule in the spirit of Wanda [36 ] , which scores coefficients using X X X as well as β \beta β , is also parallelizable and may improve accuracy at some cost in runtime.
Using ( X T X ) β (X^T X)\beta ( X T X ) β Versus X T ( X β ) X^T(X\beta) X T ( X β )
Each gradient step (11) requires the product X T X β X^T X\beta X T X β for every configuration. It can be computed either as ( X T X ) β (X^T X)\beta ( X T X ) β , where the Gram matrix G = X T X G = X^T X G = X T X is formed once before the iterations and reused, or as X T ( X β ) X^T(X\beta) X T ( X β ) , where both products are recomputed at every iteration. We refer to these as the Gram form and the two-product form. This appendix compares their costs and reports timings on an NVIDIA L40S.
Cost analysis
Let B B B be the ( Π C × p ) (\Pi C \times p) ( Π C × p ) matrix whose rows are the β \beta β s of all configurations, and let I I I be the number of iterations. Multiplying an ( a × b ) (a \times b) ( a × b ) matrix by a ( b × c ) (b \times c) ( b × c ) matrix takes a b c abc ab c multiply–add operations. The Gram form computes G G G once, at a cost of n p 2 np^2 n p 2 operations, and then computes B G BG B G at every iteration, at a cost of Π C ⋅ p 2 \Pi C \cdot p^2 Π C ⋅ p 2 . The two-product form computes B X T BX^T B X T and then ( B X T ) X (BX^T)X ( B X T ) X at every iteration, at a cost of 2 Π C ⋅ n p 2\Pi C \cdot np 2Π C ⋅ n p . The additional memory, beyond X X X and B B B , is p 2 p^2 p 2 entries for G G G plus Π C ⋅ p \Pi C \cdot p Π C ⋅ p for the output in the Gram form, and Π C ⋅ n \Pi C \cdot n Π C ⋅ n for the intermediate B X T BX^T B X T plus Π C ⋅ p \Pi C \cdot p Π C ⋅ p for the output in the two-product form. Table 10 summarizes these costs.
Table 10. Arithmetic and memory costs of the two ways of computing X T X β X^T X\beta X T X β for Π C \Pi C Π C configurations over I I I iterations. The first term for ( X T X ) β (X^T X)\beta ( X T X ) β is the one-time cost of forming X T X X^T X X T X .
Comparing the operation counts, the Gram form is cheaper if and only if n p 2 + I Π C ⋅ p 2 < 2 I Π C ⋅ n p np^2 + I\Pi C \cdot p^2 < 2I\Pi C \cdot np n p 2 + I Π C ⋅ p 2 < 2 I Π C ⋅ n p . Dividing by p p p and rearranging gives
p < p ∗ ( n ) : = 2 n ⋅ I Π C n + I Π C . (26) p < p^*(n) := \frac{2n \cdot I\Pi C}{n + I\Pi C}. \tag*{(26)} p < p ∗ ( n ) := n + I Π C 2 n ⋅ I Π C . (26)
When I Π C ≫ n I\Pi C \gg n I Π C ≫ n , the cost of forming G G G is amortized and p ∗ ≈ 2 n p^* \approx2n p ∗ ≈ 2 n : the Gram form is preferable when p < 2 n p < 2n p < 2 n , and the two-product form when p > 2 n p > 2n p > 2 n . When I Π C I\Pi C I Π C is small relative to n n n , the cost of forming G G G is not recovered and p ∗ ≈ 2 I Π C p^* \approx2I\Pi C p ∗ ≈ 2 I Π C . The memory comparison is independent of I I I : the Gram form needs p 2 p^2 p 2 additional entries, which is prohibitive for large p p p (about 40 GB in fp32 at p = 10 5 p = 10^5 p = 1 0 5 ), while the two-product form needs Π C ⋅ n \Pi C \cdot n Π C ⋅ n , which grows with the number of configurations.
The operation count describes the cost on a GPU only when the products are large enough to keep the device busy. For small products, the runtime is dominated by the overhead of launching each kernel and by memory traffic, and the two-product form launches twice as many kernels per iteration. The count also ignores caching: a Gram matrix small enough to stay in the GPU’s cache is cheaper to read than its size suggests. We therefore measure the two forms directly.
Experiments
We time the product alone, without the other gradient terms, for I = 1,000 I = 1{,}000 I = 1 , 000 iterations, with n , p ∈ { 100 , 300 , 1,000 , 3,000 , 10,000 , 30,000 } n,p \in\{100, 300, 1{,}000, 3{,}000, 10{,}000, 30{,}000\} n , p ∈ { 100 , 300 , 1 , 000 , 3 , 000 , 10 , 000 , 30 , 000 } , and with Π C = 1 \Pi C = 1 Π C = 1 and Π C = 1,000 \Pi C = 1{,}000 Π C = 1 , 000 configurations. The entries of X X X are standard Gaussian and its columns are standardized to mean 0 and standard deviation 1. All computation is in fp32 (TF32 disabled) on one NVIDIA L40S (48 GB) with PyTorch 2.7.1 and CUDA 12.6. Times are medians of 3 repetitions, with a device synchronization before each reading. The time of the Gram form includes forming G G G . The two forms agree to a relative difference of at most 1.5 × 10 − 5 1.5 \times10^{-5} 1.5 × 1 0 − 5 . Figure 5 reports the ratio of the time of the two-product form to the time of the Gram form, so values above 1 favor the Gram form.
Figure 5. Runtime of X T ( X β ) X^{T}(X\beta) X T ( X β ) divided by runtime of ( X T X ) β (X^{T}X)\beta ( X T X ) β over 1,000 iterations, including the time to form X T X X^{T}X X T X , on one NVIDIA L40S. Values above 1 favor ( X T X ) β (X^{T}X)\beta ( X T X ) β . The solid line marks where the measured ratio crosses 1, and the dashed line marks the threshold p = p ∗ ( n ) p = p^{*}(n) p = p ∗ ( n ) of (26).
Many configurations. With Π C = 1,000 \Pi C = 1{,}000 Π C = 1 , 000 , the operation count predicts the faster form well. Along p ≈ n p \approx n p ≈ n the measured ratio is 2.0–2.7, against a predicted value of 2. The measured crossover lies 1.1 to 1.4 times above p ∗ ( n ) p^{*}(n) p ∗ ( n ) for n ≥ 300 n \ge300 n ≥ 300 , so the Gram form wins slightly more often than the operation count predicts; the largest deviation is at n = 100 n = 100 n = 100 (1.8 times). Additional measurements at Π C = 100 \Pi C = 100 Π C = 100 and Π C = 10,000 \Pi C = 10{,}000 Π C = 10 , 000 for n ∈ { 300 , 1,000 , 3,000 } n \in\{300, 1{,}000, 3{,}000\} n ∈ { 300 , 1 , 000 , 3 , 000 } place the crossover between 0.96 and 1.41 times p ∗ ( n ) p^{*}(n) p ∗ ( n ) , except at Π C = 100 \Pi C = 100 Π C = 100 , n = 300 n = 300 n = 300 , where the Gram form still wins at p = 1,000 p = 1{,}000 p = 1 , 000 (p ∗ = 598 p^{*} = 598 p ∗ = 598 ). Forming G G G costs at most 2.4% of the total time of the Gram form at Π C = 1,000 \Pi C = 1{,}000 Π C = 1 , 000 (at most 1.4 s, at n = p = 30,000 n = p = 30{,}000 n = p = 30 , 000 ). When both forms are limited by arithmetic, their throughput is similar (about 37 and 36 TFLOP/s at n = p = 30,000 n = p = 30{,}000 n = p = 30 , 000 ).
A single configuration. With Π C = 1 \Pi C = 1 Π C = 1 , every iteration is a matrix–vector product, and the operation count does not predict the outcome. For p ≤ 1,000 p \le1{,}000 p ≤ 1 , 000 the ratio is at least about 2.2 for every n n n , because each iteration is dominated by kernel launch overhead and the two-product form launches two kernels instead of one. For p ≤ 3,000 p \le3{,}000 p ≤ 3 , 000 , G G G (at most 36 MB) fits in the 96 MB L2 cache of the L40S while X X X may not, which makes the Gram form up to 12 times faster at large n n n where the operation count predicts the opposite. For p ≥ 10,000 p \ge10{,}000 p ≥ 10 , 000 , G G G (0.4 to 3.6 GB) must be read from memory at every iteration, and the Gram form is much slower when n n n is small (the ratio is 0.003 at n = 100 n = 100 n = 100 , p = 30,000 p = 30{,}000 p = 30 , 000 ). The measured crossover lies 2.3 to 15 times above p ∗ ( n ) p^{*}(n) p ∗ ( n ) , and at n = 30,000 n = 30{,}000 n = 30 , 000 the Gram form wins for every p p p we tested.
Memory. The measured additional memory matches Table 10 to within about 1 MB in every case. At Π C = 1 \Pi C = 1 Π C = 1 and p = 30,000 p = 30{,}000 p = 30 , 000 , the Gram form needs 3.6 GB and the two-product form 0.24 MB. At Π C = 10,000 \Pi C = 10{,}000 Π C = 10 , 000 , n = 3,000 n = 3{,}000 n = 3 , 000 and p = 3,000 p = 3{,}000 p = 3 , 000 , the order is reversed (156 MB against 240 MB).
Recommendation. For the batch sizes for which ParaDeAl is intended (Π C \Pi C Π C in the hundreds or more), we use the Gram form when p < p ∗ ( n ) ≈ 2 n p < p^*(n) \approx2n p < p ∗ ( n ) ≈ 2 n and X T X X^T X X T X fits in GPU memory, and the two-product form otherwise. In particular, all experiments in this paper with p ≥ 10 4 p \ge10^4 p ≥ 1 0 4 and p ≫ n p \gg n p ≫ n use X T ( X β ) X^T(X\beta) X T ( X β ) . For very small batches the choice should be made by measurement, because launch overhead and caching dominate.
Proofs
Proof of Proposition 2.1
Proof. For a set S ⊆ [ p ] S \subseteq[p] S ⊆ [ p ] with ∣ S ∣ ≤ k |S| \le k ∣ S ∣ ≤ k , consider the objective of (8) over vectors β \beta β with β i = 0 \beta_i = 0 β i = 0 for i ∉ S i \notin S i ∈ / S . It is separable across coordinates. A coordinate i ∉ S i \notin S i ∈ / S contributes 1 2 u i 2 \frac{1}{2}u_i^2 2 1 u i 2 . For a coordinate i ∈ S i \in S i ∈ S , the scalar problem min b ∈ R 1 2 ( b − u i ) 2 + λ ∣ b ∣ \min_{b \in\mathbb{R}} \frac{1}{2}(b-u_i)^2+\lambda|b| min b ∈ R 2 1 ( b − u i ) 2 + λ ∣ b ∣ is solved by b = sign ( u i ) max ( ∣ u i ∣ − λ , 0 ) b = \operatorname{sign}(u_i)\max(|u_i|-\lambda,0) b = sign ( u i ) max ( ∣ u i ∣ − λ , 0 ) , with optimal value 1 2 u i 2 − 1 2 ( max ( ∣ u i ∣ − λ , 0 ) ) 2 \frac{1}{2}u_i^2-\frac{1}{2}\left(\max(|u_i|-\lambda,0)\right)^2 2 1 u i 2 − 2 1 ( max ( ∣ u i ∣ − λ , 0 ) ) 2 . Hence the optimal value of (8) restricted to S S S is
1 2 ∥ u ∥ 2 2 − 1 2 ∑ i ∈ S g ( ∣ u i ∣ ) , g ( t ) = ( max ( t − λ , 0 ) ) 2 . \frac{1}{2}\lVert u\rVert_2^2-\frac{1}{2}\sum_{i\in S}g(|u_i|), \qquad g(t)=\left(\max(t-\lambda,0)\right)^2. 2 1 ∥ u ∥ 2 2 − 2 1 i ∈ S ∑ g ( ∣ u i ∣ ) , g ( t ) = ( max ( t − λ , 0 ) ) 2 .
Since every vector with ∥ β ∥ 0 ≤ k \lVert\beta\rVert_0 \le k ∥ β ∥ 0 ≤ k is supported on some S S S with ∣ S ∣ ≤ k |S| \le k ∣ S ∣ ≤ k , minimizing (8) amounts to choosing S S S with ∣ S ∣ ≤ k |S| \le k ∣ S ∣ ≤ k that maximizes ∑ i ∈ S g ( ∣ u i ∣ ) \sum_{i\in S}g(|u_i|) ∑ i ∈ S g ( ∣ u i ∣ ) . The function g g g is nonnegative and nondecreasing on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) , so a maximizer is given by the indices of the k k k largest values of ∣ u i ∣ |u_i| ∣ u i ∣ , that is, S = R k ( u ) S=R_k(u) S = R k ( u ) (adding an index never decreases the sum). Setting the coordinates in R k ( u ) R_k(u) R k ( u ) to their scalar minimizers and the others to zero gives β ^ \hat{\beta} β ^ , which therefore belongs to T ( u , k , λ ) T(u,k,\lambda) T ( u , k , λ ) . When several indices tie in ∣ u i ∣ |u_i| ∣ u i ∣ at the k k k th position, any choice among them gives the same value, which is why T T T can be set-valued. □
Monotonicity of hard-soft thresholding
Proposition B.1. Let λ 1 , λ 2 ≥ 0 \lambda_1,\lambda_2\ge0 λ 1 , λ 2 ≥ 0 , let L ′ ≥ L D = 2 ( σ max 2 ( X ) + λ 2 ) L' \ge L_D=2(\sigma_{\max}^2(X)+\lambda_2) L ′ ≥ L D = 2 ( σ m a x 2 ( X ) + λ 2 ) and η = 1 / L ′ \eta=1/L' η = 1/ L ′ , and let β t \beta_t β t satisfy ∥ β t ∥ 0 ≤ k \lVert\beta_t\rVert_0\le k ∥ β t ∥ 0 ≤ k . If β t + 1 ∈ T ( β t − η ∇ F D ( β t ) , k , η λ 1 ) \beta_{t+1}\in T(\beta_t-\eta\nabla F_D(\beta_t),k,\eta\lambda_1) β t + 1 ∈ T ( β t − η ∇ F D ( β t ) , k , η λ 1 ) , then
F ( β t + 1 ) ≤ F ( β t ) − L ′ − L D 2 ∥ β t + 1 − β t ∥ 2 2 ≤ F ( β t ) . F(\beta_{t+1})\le F(\beta_t)-\frac{L'-L_D}{2}\lVert\beta_{t+1}-\beta_t\rVert_2^2\le F(\beta_t). F ( β t + 1 ) ≤ F ( β t ) − 2 L ′ − L D ∥ β t + 1 − β t ∥ 2 2 ≤ F ( β t ) .
Proof. Write g = ∇ F D ( β t ) g=\nabla F_D(\beta_t) g = ∇ F D ( β t ) and Δ = β t + 1 − β t \Delta=\beta_{t+1}-\beta_t Δ = β t + 1 − β t . By (6)–(7), β t + 1 \beta_{t+1} β t + 1 minimizes
Q ( β ) = ⟨ g , β − β t ⟩ + L ′ 2 ∥ β − β t ∥ 2 2 + λ 1 ∥ β ∥ 1 Q(\beta)=\langle g,\beta-\beta_t\rangle+\frac{L'}{2}\lVert\beta-\beta_t\rVert_2^2+\lambda_1\lVert\beta\rVert_1 Q ( β ) = ⟨ g , β − β t ⟩ + 2 L ′ ∥ β − β t ∥ 2 2 + λ 1 ∥ β ∥ 1
over { β : ∥ β ∥ 0 ≤ k } \{\beta:\lVert\beta\rVert_0\le k\} { β : ∥ β ∥ 0 ≤ k } , since Q Q Q differs from L ′ L' L ′ times the objective of (8), with u = β t − η g u=\beta_t-\eta g u = β t − η g and λ = η λ 1 \lambda=\eta\lambda_1 λ = η λ 1 , only by a constant. Because β t \beta_t β t is feasible, Q ( β t + 1 ) ≤ Q ( β t ) = λ 1 ∥ β t ∥ 1 Q(\beta_{t+1})\le Q(\beta_t)=\lambda_1\lVert\beta_t\rVert_1 Q ( β t + 1 ) ≤ Q ( β t ) = λ 1 ∥ β t ∥ 1 . By the descent lemma (5) with constant L D L_D L D ,
F ( β t + 1 ) = F D ( β t + 1 ) + λ 1 ∥ β t + 1 ∥ 1 ≤ F D ( β t ) + ⟨ g , Δ ⟩ + L D 2 ∥ Δ ∥ 2 2 + λ 1 ∥ β t + 1 ∥ 1 = F D ( β t ) + Q ( β t + 1 ) − L ′ − L D 2 ∥ Δ ∥ 2 2 ≤ F ( β t ) − L ′ − L D 2 ∥ Δ ∥ 2 2 . \begin{aligned}
F(\beta_{t+1})&=F_D(\beta_{t+1})+\lambda_1\lVert\beta_{t+1}\rVert_1 \\
&\le F_D(\beta_t)+\langle g,\Delta\rangle+\frac{L_D}{2}\lVert\Delta\rVert_2^2+\lambda_1\lVert\beta_{t+1}\rVert_1 \\
&=F_D(\beta_t)+Q(\beta_{t+1})-\frac{L'-L_D}{2}\lVert\Delta\rVert_2^2 \\
&\le F(\beta_t)-\frac{L'-L_D}{2}\lVert\Delta\rVert_2^2.
\end{aligned} F ( β t + 1 ) = F D ( β t + 1 ) + λ 1 ∥ β t + 1 ∥ 1 ≤ F D ( β t ) + ⟨ g , Δ ⟩ + 2 L D ∥ Δ ∥ 2 2 + λ 1 ∥ β t + 1 ∥ 1 = F D ( β t ) + Q ( β t + 1 ) − 2 L ′ − L D ∥ Δ ∥ 2 2 ≤ F ( β t ) − 2 L ′ − L D ∥ Δ ∥ 2 2 .
Proof of Proposition 2.1
Proposition B.2 below is the full version of Proposition 2.1. It adapts Proposition 6 of Bertsimas et al. [7 ] , who study hard-thresholded gradient descent, the same update without the L 1 L_1 L 1 penalty, for a convex loss with a Lipschitz gradient. Our update adds soft thresholding to every step, so the objective F F F is no longer differentiable, and on a fixed support the iteration is a proximal gradient method rather than gradient descent. Parts (a), (b) and (d) below adapt Parts (a), (b) and (c) of Bertsimas et al. [7 ] , and Part (c), on limit points, is added. Parts (d) and (e) of Bertsimas et al. [7 ] treat the case in which the k k k th largest coefficient tends to zero; the gradient of the loss then vanishes along a subsequence, so the iterates approach unconstrained minimizers of the loss. Bertsimas et al. [7 ] regard this case as of little statistical interest, and we do not adapt those parts.
Throughout, L D = 2 ( σ max 2 ( X ) + λ 2 ) L_D = 2(\sigma_{\max}^2(X) + \lambda_2) L D = 2 ( σ m a x 2 ( X ) + λ 2 ) is the Lipschitz constant of ∇ F D \nabla F_D ∇ F D in (4) , and S ( β ) S(\beta) S ( β ) is the support of β \beta β (Section 1.5). For t ≥ 1 t \ge1 t ≥ 1 , let α t \alpha_t α t denote the k k k th largest entry of ∣ β t ∣ |\beta_t| ∣ β t ∣ , so that α t > 0 \alpha_t > 0 α t > 0 if and only if ∥ β t ∥ 0 = k \|\beta_t\|_0 = k ∥ β t ∥ 0 = k . For S ⊆ [ p ] S \subseteq[p] S ⊆ [ p ] , let V S = { β ∈ R p : β i = 0 for i ∉ S } V_S = \{\beta\in\mathbb{R}^p : \beta_i = 0 \text{ for } i \notin S\} V S = { β ∈ R p : β i = 0 for i ∈ / S } .
Proposition B.2. Let λ 1 , λ 2 ≥ 0 \lambda_1, \lambda_2 \ge0 λ 1 , λ 2 ≥ 0 , L ′ > L D L' > L_D L ′ > L D and η = 1 / L ′ \eta= 1/L' η = 1/ L ′ . Let β 0 ∈ R p \beta_0 \in\mathbb{R}^p β 0 ∈ R p be arbitrary and β t + 1 ∈ T ( β t − η ∇ F D ( β t ) , k , η λ 1 ) \beta_{t+1} \in T(\beta_t - \eta\nabla F_D(\beta_t), k, \eta\lambda_1) β t + 1 ∈ T ( β t − η ∇ F D ( β t ) , k , η λ 1 ) for t ≥ 0 t \ge0 t ≥ 0 . Then the following hold.
(a) For every t ≥ 1 t \ge1 t ≥ 1 , F ( β t ) − F ( β t + 1 ) ≥ L ′ − L D 2 ∥ β t + 1 − β t ∥ 2 2 F(\beta_t) - F(\beta_{t+1}) \ge\frac{L'-L_D}{2}\|\beta_{t+1} - \beta_t\|_2^2 F ( β t ) − F ( β t + 1 ) ≥ 2 L ′ − L D ∥ β t + 1 − β t ∥ 2 2 . The sequence F ( β t ) F(\beta_t) F ( β t ) , t ≥ 1 t \ge1 t ≥ 1 , is nonincreasing and converges.
(b) ∑ t ≥ 1 ∥ β t + 1 − β t ∥ 2 2 ≤ 2 F ( β 1 ) / ( L ′ − L D ) \sum_{t \ge1}\|\beta_{t+1} - \beta_t\|_2^2 \le2F(\beta_1)/(L' - L_D) ∑ t ≥ 1 ∥ β t + 1 − β t ∥ 2 2 ≤ 2 F ( β 1 ) / ( L ′ − L D ) . In particular, β t + 1 − β t → 0 \beta_{t+1} - \beta_t \to0 β t + 1 − β t → 0 .
(c) Every limit point β ˉ \bar{\beta} β ˉ of { β t } \{\beta_t\} { β t } is a fixed point of the update: β ˉ ∈ T ( β ˉ − η ∇ F D ( β ˉ ) , k , η λ 1 ) \bar{\beta} \in T(\bar{\beta} - \eta\nabla F_D(\bar{\beta}), k, \eta\lambda_1) β ˉ ∈ T ( β ˉ − η ∇ F D ( β ˉ ) , k , η λ 1 ) .
(d) If lim inf t → ∞ α t > 0 \liminf_{t\to\infty}\alpha_t > 0 lim inf t → ∞ α t > 0 , then the support stabilizes after finitely many iterations: there exist a set S S S with ∣ S ∣ = k |S| = k ∣ S ∣ = k and an index M M M such that S ( β t ) = S S(\beta_t) = S S ( β t ) = S for all t ≥ M t \ge M t ≥ M . Moreover, β t \beta_t β t converges to a point β ∗ \beta^* β ∗ with S ( β ∗ ) = S S(\beta^*) = S S ( β ∗ ) = S that minimizes F F F over V S V_S V S and is a fixed point of the update, as in Part (c).
Proof. Write u t = β t − η ∇ F D ( β t ) u_t = \beta_t - \eta\nabla F_D(\beta_t) u t = β t − η ∇ F D ( β t ) and ϕ t ( β ) = 1 2 ∥ β − u t ∥ 2 2 + η λ 1 ∥ β ∥ 1 \phi_t(\beta) = \frac{1}{2}\|\beta-u_t\|_2^2 + \eta\lambda_1\|\beta\|_1 ϕ t ( β ) = 2 1 ∥ β − u t ∥ 2 2 + η λ 1 ∥ β ∥ 1 . By definition of T T T in (8) ,
ϕ t ( β t + 1 ) ≤ ϕ t ( β ) for every β with ∥ β ∥ 0 ≤ k . (27) \phi_t(\beta_{t+1}) \le\phi_t(\beta) \quad\text{for every } \beta\text{ with } \|\beta\|_0 \le k. \tag*{(27)} ϕ t ( β t + 1 ) ≤ ϕ t ( β ) for every β with ∥ β ∥ 0 ≤ k . (27)
Part (a). The starting point β 0 \beta_0 β 0 need not satisfy ∥ β 0 ∥ 0 ≤ k \|\beta_0\|_0 \le k ∥ β 0 ∥ 0 ≤ k , but every β t \beta_t β t with t ≥ 1 t \ge1 t ≥ 1 is an element of T ( ⋅ , k , ⋅ ) T(\cdot,k,\cdot) T ( ⋅ , k , ⋅ ) and therefore does. Proposition B.1 applies to every t ≥ 1 t \ge1 t ≥ 1 and gives the inequality. Since F ≥ 0 F \ge0 F ≥ 0 , the nonincreasing sequence F ( β t ) F(\beta_t) F ( β t ) is bounded below and converges.
Part (b). Summing the inequality of Part (a) over t = 1 , … , N t = 1,\ldots,N t = 1 , … , N gives
L ′ − L D 2 ∑ t = 1 N ∥ β t + 1 − β t ∥ 2 2 ≤ F ( β 1 ) − F ( β N + 1 ) ≤ F ( β 1 ) . \frac{L'-L_D}{2}\sum_{t=1}^{N}\|\beta_{t+1}-\beta_t\|_2^2 \le F(\beta_1)-F(\beta_{N+1}) \le F(\beta_1). 2 L ′ − L D t = 1 ∑ N ∥ β t + 1 − β t ∥ 2 2 ≤ F ( β 1 ) − F ( β N + 1 ) ≤ F ( β 1 ) .
Since L ′ > L D L' > L_D L ′ > L D , dividing by ( L ′ − L D ) / 2 (L'-L_D)/2 ( L ′ − L D ) /2 and letting N → ∞ N \to\infty N → ∞ proves the bound. The terms of a convergent series tend to zero.
Part (c). Let β t j → β ˉ \beta_{t_j} \to\bar{\beta} β t j → β ˉ . By Part (b), β t j + 1 → β ˉ \beta_{t_j+1} \to\bar{\beta} β t j + 1 → β ˉ as well, and since ∇ F D \nabla F_D ∇ F D is continuous, u t j → u ˉ : = β ˉ − η ∇ F D ( β ˉ ) u_{t_j} \to\bar{u} := \bar{\beta} - \eta\nabla F_D(\bar{\beta}) u t j → u ˉ := β ˉ − η ∇ F D ( β ˉ ) . Both sides of (27) are continuous in ( β t + 1 , u t ) (\beta_{t+1},u_t) ( β t + 1 , u t ) , so taking t = t j t=t_j t = t j and j → ∞ j \to\infty j → ∞ gives 1 2 ∥ β ˉ − u ˉ ∥ 2 2 + η λ 1 ∥ β ˉ ∥ 1 ≤ 1 2 ∥ β − u ˉ ∥ 2 2 + η λ 1 ∥ β ∥ 1 \frac{1}{2}\|\bar{\beta}-\bar{u}\|_2^2+\eta\lambda_1\|\bar{\beta}\|_1 \le\frac{1}{2}\|\beta-\bar{u}\|_2^2+\eta\lambda_1\|\beta\|_1 2 1 ∥ β ˉ − u ˉ ∥ 2 2 + η λ 1 ∥ β ˉ ∥ 1 ≤ 2 1 ∥ β − u ˉ ∥ 2 2 + η λ 1 ∥ β ∥ 1 for every β \beta β with ∥ β ∥ 0 ≤ k \|\beta\|_0 \le k ∥ β ∥ 0 ≤ k . The set { β : ∥ β ∥ 0 ≤ k } \{\beta:\|\beta\|_0\le k\} { β : ∥ β ∥ 0 ≤ k } is closed, so ∥ β ˉ ∥ 0 ≤ k \|\bar{\beta}\|_0\le k ∥ β ˉ ∥ 0 ≤ k , and therefore β ˉ ∈ T ( u ˉ , k , η λ 1 ) \bar{\beta}\in T(\bar{u},k,\eta\lambda_1) β ˉ ∈ T ( u ˉ , k , η λ 1 ) .
Part (d). Let α = lim inf t α t > 0 \alpha=\liminf_{t}\alpha_t>0 α = lim inf t α t > 0 , and choose M 0 M_0 M 0 such that α t ≥ α / 2 \alpha_t\ge\alpha/2 α t ≥ α /2 for all t ≥ M 0 t\ge M_0 t ≥ M 0 . For these t t t , ∥ β t ∥ 0 = k \|\beta_t\|_0=k ∥ β t ∥ 0 = k . Suppose that S ( β t + 1 ) ≠ S ( β t ) S(\beta_{t+1})\ne S(\beta_t) S ( β t + 1 ) = S ( β t ) for some t ≥ M 0 t\ge M_0 t ≥ M 0 . Both supports have k k k elements, so some index i i i lies in S ( β t ) S(\beta_t) S ( β t ) but not in S ( β t + 1 ) S(\beta_{t+1}) S ( β t + 1 ) , and
∥ β t + 1 − β t ∥ 2 ≥ ∣ β t , i ∣ ≥ α t ≥ α / 2. \|\beta_{t+1}-\beta_t\|_2 \ge|\beta_{t,i}| \ge\alpha_t \ge\alpha/2. ∥ β t + 1 − β t ∥ 2 ≥ ∣ β t , i ∣ ≥ α t ≥ α /2.
By Part (b), this can happen for only finitely many t t t . Hence there exist M ≥ M 0 M\ge M_0 M ≥ M 0 and S S S with ∣ S ∣ = k |S|=k ∣ S ∣ = k such that S ( β t ) = S S(\beta_t)=S S ( β t ) = S for all t ≥ M t\ge M t ≥ M . This step follows the proof of Part (c) of Bertsimas et al. [7 ] .
For t ≥ M t\ge M t ≥ M , both β t \beta_t β t and β t + 1 \beta_{t+1} β t + 1 lie in V S V_S V S . Every vector in V S V_S V S has at most k k k nonzeros, so by (27) the point β t + 1 \beta_{t+1} β t + 1 also minimizes ϕ t \phi_t ϕ t over V S V_S V S . On V S V_S V S the function ϕ t \phi_t ϕ t is strongly convex and separable across coordinates, so its minimizer is unique and is given by ( β t + 1 ) i = sign ( u t , i ) max ( ∣ u t , i ∣ − η λ 1 , 0 ) (\beta_{t+1})_i=\operatorname{sign}(u_{t,i})\max(|u_{t,i}|-\eta\lambda_1,0) ( β t + 1 ) i = sign ( u t , i ) max ( ∣ u t , i ∣ − η λ 1 , 0 ) for i ∈ S i\in S i ∈ S and ( β t + 1 ) i = 0 (\beta_{t+1})_i=0 ( β t + 1 ) i = 0 otherwise. This is one step of the proximal gradient method, with step size η \eta η , applied to the convex problem
min β ∈ V S F D ( β ) + λ 1 ∥ β ∥ 1 , (28) \min_{\beta\in V_S}\; F_D(\beta)+\lambda_1\|\beta\|_1, \tag*{(28)} β ∈ V S min F D ( β ) + λ 1 ∥ β ∥ 1 , (28)
whose smooth part F D F_D F D has an L D L_D L D -Lipschitz gradient. Thus, from iteration M M M onward, hard-soft thresholding coincides with the proximal gradient method (ISTA) for (28), started from β M \beta_M β M .
Problem (28) has a minimizer. If λ 1 > 0 \lambda_1 > 0 λ 1 > 0 or λ 2 > 0 \lambda_2 > 0 λ 2 > 0 , its objective is continuous and tends to infinity as ∥ β ∥ 2 → ∞ \lVert\beta\rVert_2 \to\infty ∥ β ∥ 2 → ∞ . If λ 1 = λ 2 = 0 \lambda_1 = \lambda_2 = 0 λ 1 = λ 2 = 0 , the problem is least squares on the columns X S X_S X S , whose normal equations X S T X S β S = X S T y X_S^T X_S\beta_S = X_S^T y X S T X S β S = X S T y always have a solution. For a convex problem that has a minimizer, the iterates of the proximal gradient method with a constant step size in ( 0 , 2 / L D ) (0, 2/L_D) ( 0 , 2/ L D ) converge to a minimizer [14 ] ; see also Beck [3 ] . Since η = 1 / L ′ < 1 / L D \eta= 1/L' < 1/L_D η = 1/ L ′ < 1/ L D , the sequence β t \beta_t β t converges to a minimizer β ∗ \beta^* β ∗ of (28), which is the same as a minimizer of F F F over V S V_S V S . For i ∈ S i \in S i ∈ S and t ≥ M t \ge M t ≥ M , ∣ β t , i ∣ ≥ α t ≥ α / 2 \lvert\beta_{t,i}\rvert\ge\alpha_t \ge\alpha/2 ∣ β t , i ∣ ≥ α t ≥ α /2 , so ∣ β ∗ ∣ ≥ α / 2 > 0 \lvert\beta^*\rvert\ge\alpha/2 > 0 ∣ β ∗ ∣ ≥ α /2 > 0 and S ( β ∗ ) = S S(\beta^*) = S S ( β ∗ ) = S . Finally, β ∗ \beta^* β ∗ is a limit point of { β t } \{\beta_t\} { β t } , so Part (c) shows that β ∗ \beta^* β ∗ is a fixed point of the update.
Remarks. (1) Part (d) also shows that, under its condition, a stopping rule based on the support, such as the support-unchanged rule of § 2.2.1 , is met after finitely many updates. The condition lim inf t α t > 0 \liminf_t \alpha_t > 0 lim inf t α t > 0 concerns the iterates and cannot be checked in advance.
(2) The convergence of the whole sequence { β t } \{\beta_t\} { β t } can also be obtained without the condition of Part (d), at the cost of more advanced tools. The update (9) is a forward–backward (proximal gradient) step for the sum of F D F_D F D and the nonconvex function λ 1 ∥ β ∥ 1 + δ k ( β ) \lambda_1\lVert\beta\rVert_1 + \delta_k(\beta) λ 1 ∥ β ∥ 1 + δ k ( β ) , where δ k \delta_k δ k is 0 0 0 on { β : ∥ β ∥ 0 ≤ k } \{\beta: \lVert\beta\rVert_0 \le k\} { β : ∥ β ∥ 0 ≤ k } and + ∞ +\infty + ∞ elsewhere. This sum is semi-algebraic, so it has the Kurdyka–Łojasiewicz property, and the results of Attouch et al. [2 ] on forward–backward splitting for such functions, which also cover iterative thresholding for sparse recovery, show that a bounded sequence of this kind converges to a critical point, in the sense of the limiting subdifferential. This conclusion concerns the iterates only: when the limit has fewer than k k k nonzeros, the support need not stabilize. The sequence is bounded when λ 1 > 0 \lambda_1 > 0 λ 1 > 0 or λ 2 > 0 \lambda_2 > 0 λ 2 > 0 , because the level sets of F F F are then bounded. When λ 1 = λ 2 = 0 \lambda_1 = \lambda_2 = 0 λ 1 = λ 2 = 0 , the sequence is bounded whenever every set of k k k columns of X X X is linearly independent: there are finitely many supports of size at most k k k , the least squares objective restricted to each of them is coercive, and F ( β t ) ≤ F ( β 1 ) F(\beta_t) \le F(\beta_1) F ( β t ) ≤ F ( β 1 ) for t ≥ 1 t \ge1 t ≥ 1 .
(3) The same argument as in Proposition B.1, with the constraint set { β : ∥ β ∥ 0 ≤ k } \{\beta: \lVert\beta\rVert_0 \le k\} { β : ∥ β ∥ 0 ≤ k } replaced by the convex set { β : β i = 0 , i ∉ K } \{\beta: \beta_i = 0,\ i \notin K\} { β : β i = 0 , i ∈ / K } , shows that the value modification update (17) is also monotone when its step size is at most 1 / L D 1/L_D 1/ L D . In that convex case, F ( β t ) F(\beta_t) F ( β t ) converges to the optimal value of (15) [4 ] , and, for any constant step size in ( 0 , 2 / L D ) (0, 2/L_D) ( 0 , 2/ L D ) , β t \beta_t β t converges to a minimizer [14 ] .
(4) Proposition B.2 requires η < 1 / L D \eta< 1/L_D η < 1/ L D . Step sizes larger than 1 / L D 1/L_D 1/ L D , such as the steps selected by the search of § 3.3 , are not covered by Propositions B.1 and B.2.
Number of Unchanged Updates in the Stopping Rule
Support selection stops once one update leaves the support unchanged (§ 2.2.1 ). Here we examine the more general rule that stops once r r r consecutive updates have left the support unchanged, for r ∈ { 1 , 2 , 3 , 5 , 10 } r \in\{1, 2, 3, 5, 10\} r ∈ { 1 , 2 , 3 , 5 , 10 } . The rule remains support-only for every r r r . We judge each r r r by the support it returns, after value modification on that support.
Setup. We use ( n , p ) ∈ { ( 500 , 5,000 ) , ( 1,000 , 20,000 ) } (n,p) \in\{(500,5{,}000),(1{,}000,20{,}000)\} ( n , p ) ∈ {( 500 , 5 , 000 ) , ( 1 , 000 , 20 , 000 )} . The rows of X X X are Gaussian with correlation ρ ∣ i − j ∣ \rho^{\lvert i-j\rvert} ρ ∣ i − j ∣ between features i i i and j j j , ρ ∈ { 0 , 0.5 } \rho\in\{0,0.5\} ρ ∈ { 0 , 0.5 } , and every column is standardized to mean 0 and standard deviation 1. The true coefficient vector has 25 nonzeros at random positions with standard Gaussian values, and y = X β ∗ + ϵ y = X\beta^* + \epsilon y = X β ∗ + ϵ with signal-to-noise ratio 5. A test set of the same size is drawn from the same model. Each of 3 seeds uses a grid of 180 configurations: k ∈ { 10 , 25 , 50 , 100 } k \in\{10,25,50,100\} k ∈ { 10 , 25 , 50 , 100 } ; λ 1 ∈ { 0 , 10 − 3 , 10 − 2 } × 2 ∥ X T y ∥ ∞ \lambda_1 \in\{0,10^{-3},10^{-2}\} \times2\lVert X^T y\rVert_\infty λ 1 ∈ { 0 , 1 0 − 3 , 1 0 − 2 } × 2 ∥ X T y ∥ ∞ ; λ 2 ∈ { 0 , 10 − 3 , 10 − 2 } × σ max 2 ( X ) \lambda_2 \in\{0,10^{-3},10^{-2}\} \times\sigma^2_{\max}(X) λ 2 ∈ { 0 , 1 0 − 3 , 1 0 − 2 } × σ m a x 2 ( X ) ; and the five starting points of Section 4.1. We use three step sizes: the conservative η = 0.9 / ( σ max 2 ( X ) + λ 2 ) \eta= 0.9/(\sigma^2_{\max}(X) + \lambda_2) η = 0.9/ ( σ m a x 2 ( X ) + λ 2 ) of Section 4.3, and η p r e d / 4 \eta_{\mathrm{pred}}/4 η pred /4 and η p r e d / 2 \eta_{\mathrm{pred}}/2 η pred /2 , where η p r e d = 0.9 / ( n ( 1 + k / n ) 2 + λ 2 ) \eta_{\mathrm{pred}} = 0.9/(n(1+\sqrt{k/n})^2 + \lambda_2) η pred = 0.9/ ( n ( 1 + k / n ) 2 + λ 2 ) is the restricted prediction of Section 4.4. (At η p r e d \eta_{\mathrm{pred}} η pred itself almost every configuration diverged, as expected from the probe results of Section 4.4, which select between 1 / 8 1/8 1/8 and 1 / 2 1/2 1/2 of η p r e d \eta_{\mathrm{pred}} η pred .) At η p r e d / 2 \eta_{\mathrm{pred}}/2 η pred /2 , between 49 and 323 of the 540 configurations per instance type diverged, mostly with k = 100 k = 100 k = 100 ; they are excluded. No configuration diverged at the other two step sizes. The cap is M S S = 1,000 M_{SS} = 1{,}000 M S S = 1 , 000 .
Value modification uses PCG when λ 1 = 0 \lambda_{1} = 0 λ 1 = 0 and proximal gradient otherwise, both to a relative tolerance of 10 − 6 10^{-6} 1 0 − 6 . Computation is in fp32 on one NVIDIA L40S.
Table 11. Effect of r r r , the number of consecutive updates that must leave the support unchanged. Δ F = ( F r − F 1 ) / F 1 \Delta F = (F_r - F_1)/F_1 Δ F = ( F r − F 1 ) / F 1 is the relative change in the training objective after value modification; negative values mean that r r r found a better support than r = 1 r = 1 r = 1 . Pooled over 3 seeds and all kept configurations. Selected rows; Figure 6 shows every instance and r r r .
Results. Table 11 and Figure 6 summarize the results. The choice of r r r matters, and how much it matters depends on the step size and the starting point.
Figure 6. Top: fraction of configurations whose support under rule r r r equals the support under r = 1 r = 1 r = 1 . Bottom: median relative change in the training objective after value modification, relative to r = 1 r = 1 r = 1 . Columns correspond to the three step sizes, with η p r e d = 0.9 / ( n ( 1 + k / n ) 2 + λ 2 ) \eta_{\mathrm{pred}} = 0.9/(n(1 + \sqrt{k/n})^2 + \lambda_2) η pred = 0.9/ ( n ( 1 + k / n ) 2 + λ 2 ) .
Nonzero starting points with small steps. From a nonzero β o \beta_o β o , the first update keeps approximately the k k k largest entries of ∣ β o ∣ |\beta_o| ∣ β o ∣ . When η ∣ ∇ F D ∣ \eta|\nabla F_D| η ∣∇ F D ∣ is small relative to ∣ β o ∣ |\beta_o| ∣ β o ∣ , the second update leaves this support unchanged, and r = 1 r = 1 r = 1 stops after two updates on a support determined by the starting point rather than by the data. At η p r e d / 4 \eta_{\mathrm{pred}}/4 η pred /4 , larger r r r allows the iterates to move away from this support: the median objective after value modification is 50–71% lower at r = 10 r = 10 r = 10 than at r = 1 r = 1 r = 1 , and the median number of true features recovered rises from 0–6 to 15–18. From β o = 0 \beta_o = 0 β o = 0 the effect is smaller, with median improvements of 8–30% at r = 10 r = 10 r = 10 .
The conservative step. With η = 0.9 / ( σ max 2 ( X ) + λ 2 ) \eta= 0.9/(\sigma_{\max}^{2}(X) + \lambda_2) η = 0.9/ ( σ m a x 2 ( X ) + λ 2 ) and p = 20,000 p = 20{,}000 p = 20 , 000 , even r = 10 r = 10 r = 10 keeps the r = 1 r = 1 r = 1 support in 94–96% of configurations, and no r ≤ 10 r \le10 r ≤ 10 recovers true features from a nonzero start. Here the limiting factor is the step size, in line with § 4.4 .
Direction and cost. Increasing r r r almost never worsened the training objective (6 of 8,640 comparisons, by at most 0.6%); test error moved in the same direction in the median but not in every configuration. Supports were still changing between r = 5 r = 5 r = 5 and r = 10 r = 10 r = 10 in 26–53% of configurations at η p r e d / 4 \eta_{\mathrm{pred}}/4 η pred /4 , so these experiments do not identify a value of r r r beyond which results stop changing. The cost of a larger r r r is small: going from r = 1 r = 1 r = 1 to r = 10 r = 10 r = 10 adds roughly 10 to 50 updates per configuration, and support selection took between 1 and 121 ms per batch of 180 configurations for every r r r .
Configurations whose supports cycle are not stopped by any r r r and run to M S S M_{SS} M S S ; the check against the support two updates back used in § 4.4 handles cycles of length two.
Bitwise Differences in Dynamic Shrinking
Dynamic Shrinking does not give bitwise the same results as the Flag Approach . Each resize changes the width of the batched matrix product, so the floating-point operations are summed in a different order, and the computed β \beta β s differ slightly. This appendix looks at how often that leads to a different support, and whether it matters.
In the first experiment of § 4.2 (∏ C = 16,807 \prod C = 16{,}807 ∏ C = 16 , 807 , p = 10,000 p = 10{,}000 p = 10 , 000 ), at most 35 configurations (0.208%) end on a different support than under the Flag Approach , depending on the shrink factor. In the second experiment (∏ C = 3,125 \prod C = 3{,}125 ∏ C = 3 , 125 , p = 20,000 p = 20{,}000 p = 20 , 000 ), the figure is 18 configurations (0.576%).
A different support is not a defect in itself. When two coordinates have nearly the same magnitude at the hard-thresholding boundary, single precision cannot decide which of them is larger, and the problem does not distinguish between the two resulting supports, so either answer is equally valid. At p = 10,000 p = 10{,}000 p = 10 , 000 , the evidence points to this explanation. On the configurations whose supports disagree, the two runs still share 95 to 98% of their selected entries. The objective F ( β ) F(\beta) F ( β ) in (2) , including both penalty terms, is also not systematically worse under Dynamic Shrinking . Across s ∈ { 0.5 , 0.9 , 0.99 } s \in\{0.5, 0.9, 0.99\} s ∈ { 0.5 , 0.9 , 0.99 } , there are 60 disagreeing configurations. Dynamic Shrinking reaches the lower objective on 33 of them and the higher objective on 27. The median relative difference is of order 10 − 4 10^{-4} 1 0 − 4 , and the worst case is 7.9%. Compared with how much the objective varies across the configuration grid itself, the largest discrepancy is only 1.886 × 10 − 3 1.886 \times10^{-3} 1.886 × 1 0 − 3 of that range.
Two more observations support this reading. First, the number of disagreements does not grow with the number of gathers. Across the 9 shrink factors it stays between 4 and 35, while the number of gathers goes from 3 to 2436. If the disagreements came from rounding error building up with each resize, the count would rise with the number of gathers, and it does not. Second, the coefficients that differ are exactly the ones at the hard-thresholding boundary.
Appendix Generating y y y with a Given SNR
The experiment in § 4.1 uses one synthetic instance ( X , y ) (X,y) ( X , y ) with n = 500 n = 500 n = 500 observations, p = 1,000 p = 1{,}000 p = 1 , 000 features, a true coefficient vector β ⋆ \beta^\star β ⋆ with k ⋆ = 25 k^\star= 25 k ⋆ = 25 nonzeros, and a signal-to-noise ratio (SNR) of 25. We define the SNR as
SNR = ∥ X β ⋆ ∥ 2 2 ∥ ϵ ∥ 2 2 . \operatorname{SNR} = \frac{\lVert X\beta^\star\rVert_2^2}{\lVert\epsilon\rVert_2^2}. SNR = ∥ ϵ ∥ 2 2 ∥ X β ⋆ ∥ 2 2 .
where y = X β ⋆ + ϵ y = X\beta^\star+ \epsilon y = X β ⋆ + ϵ . The same instance is used for all 3,125 configurations. Algorithm 8 gives the procedure.
Algorithm 8 Synthetic Data Generation
Require: number of observations n n n , number of features p p p , true sparsity k ⋆ k^\star k ⋆ , target signal-to-noise ratio SNR
Return: X ∈ R n × p X \in\mathbb{R}^{n \times p} X ∈ R n × p , y ∈ R n y \in\mathbb{R}^{n} y ∈ R n , β ⋆ ∈ R p \beta^\star\in\mathbb{R}^{p} β ⋆ ∈ R p
Draw Z ∈ R n × p Z \in\mathbb{R}^{n \times p} Z ∈ R n × p with entries Z i j Z_{ij} Z ij independent standard Gaussian.
for j = 1 , … , p j = 1,\ldots,p j = 1 , … , p do
z ˉ j ← 1 n ∑ i = 1 n Z i j \bar{z}_j \leftarrow\frac{1}{n}\sum_{i=1}^{n} Z_{ij} z ˉ j ← n 1 ∑ i = 1 n Z ij and s j ← ( 1 n ∑ i = 1 n ( Z i j − z ˉ j ) 2 ) 1 / 2 s_j \leftarrow\left(\frac{1}{n}\sum_{i=1}^{n}(Z_{ij}-\bar{z}_j)^2\right)^{1/2} s j ← ( n 1 ∑ i = 1 n ( Z ij − z ˉ j ) 2 ) 1/2
X i j ← ( Z i j − z ˉ j ) / s j X_{ij} \leftarrow(Z_{ij}-\bar{z}_j)/s_j X ij ← ( Z ij − z ˉ j ) / s j for i = 1 , … , n i = 1,\ldots,n i = 1 , … , n {column j j j now has mean 0 and standard deviation 1}
end for
Choose a set S ⋆ S^\star S ⋆ of k ⋆ k^\star k ⋆ indices uniformly at random from { 1 , … , p } \{1,\ldots,p\} { 1 , … , p } , without replacement.
Set β j ⋆ \beta^\star_j β j ⋆ to an independent standard Gaussian draw for j ∈ S ⋆ j \in S^\star j ∈ S ⋆ , and β j ⋆ ← 0 \beta^\star_j \leftarrow0 β j ⋆ ← 0 for j ∉ S ⋆ j \notin S^\star j ∈ / S ⋆ .
μ ← X β ⋆ \mu\leftarrow X\beta^\star μ ← X β ⋆ {the noiseless signal}
Draw u ∈ R n u \in\mathbb{R}^{n} u ∈ R n with entries independent standard Gaussian.
ϵ ← ∥ μ ∥ 2 SNR ∥ u ∥ 2 u \epsilon\leftarrow\frac{\lVert\mu\rVert_2}{\sqrt{\operatorname{SNR}}\lVert u\rVert_2}u ϵ ← SNR ∥ u ∥ 2 ∥ μ ∥ 2 u {rescale the noise to the target ratio}
y ← μ + ϵ y \leftarrow\mu+ \epsilon y ← μ + ϵ
return X X X , y y y , β ⋆ \beta^\star β ⋆
For § 4.1 we call Algorithm 8 with n = 500 n = 500 n = 500 , p = 1,000 p = 1{,}000 p = 1 , 000 , k ⋆ = 25 k^\star= 25 k ⋆ = 25 and SNR = 25 = 25 = 25 . The step that forms ϵ \epsilon ϵ rescales the noise by the norms of the drawn vectors μ \mu μ and u u u , so the target is met exactly for this instance and not only in expectation:
∥ μ ∥ 2 2 ∥ ϵ ∥ 2 2 = ∥ μ ∥ 2 2 ∥ μ ∥ 2 2 ∥ u ∥ 2 2 / ( SNR ∥ u ∥ 2 2 ) = SNR . \frac{\lVert\mu\rVert_2^2}{\lVert\epsilon\rVert_2^2}
=
\frac{\lVert\mu\rVert_2^2}{\lVert\mu\rVert_2^2\lVert u\rVert_2^2/(\operatorname{SNR}\lVert u\rVert_2^2)}
=
\operatorname{SNR}. ∥ ϵ ∥ 2 2 ∥ μ ∥ 2 2 = ∥ μ ∥ 2 2 ∥ u ∥ 2 2 / ( SNR ∥ u ∥ 2 2 ) ∥ μ ∥ 2 2 = SNR .
The direction of ϵ \epsilon ϵ is that of u u u , so the noise is still an isotropic Gaussian direction; only its length is fixed.
Appendix Choosing the Active Set Size
Table 6 reports one active set size ∣ A ∣ \lvert A\rvert ∣ A ∣ per ( p , k ) (p,k) ( p , k ) . This appendix gives the full sweep behind that choice, describes how much the results vary between runs, and lists the limitations of the procedure. The setup is that of § 4.4 .
Speed. Along most rows the solve-only speedup changes little with ∣ A ∣ \lvert A\rvert ∣ A ∣ . Even 15k features is small next to p p p , so the run time is set mainly by the number of full-width updates, not by the size of X A X_A X A . The exceptions are rows where some sizes need many more rounds than others, such as p = 3 × 10 5 p = 3 \times10^5 p = 3 × 1 0 5 , k = 500 k = 500 k = 500 , where 10k and 15k need 17 and 25 rounds against 2 for the smaller sizes.
Accuracy. The objective depends on ∣ A ∣ \lvert A\rvert ∣ A ∣ much more than the run time does. For k ≤ 50 k \le50 k ≤ 50 every size gives an objective within about 1% of full width. For k ≥ 100 k \ge100 k ≥ 100 the differences are large, and the largest active sets are the most likely to be worse. With a large A A A the inner loop can settle on a support that the full-width check accepts after only one or two rounds, so the outer loop stops before the support has been improved. Smaller active sets force more rounds. The pattern is not monotone, and it varies between seeds, so we do not identify a single best size. In every row except p = 3 × 10 5 p = 3 \times10^5 p = 3 × 1 0 5 , k = 250 k = 250 k = 250 , at least one size between 2 k 2k 2 k and 5 k 5k 5 k is within 2% of full width or better, and these are the sizes used in Table 6 . No single size is safe everywhere, however: 2 k 2k 2 k is 34% worse at p = 10 6 p = 10^6 p = 1 0 6 , k = 250 k = 250 k = 250 , and 3 k 3k 3 k to 5 k 5k 5 k are 10 to 25% worse at p = 10 6 p = 10^{6} p = 1 0 6 , k = 500 k = 500 k = 500 . At p = 3 × 10 5 p = 3 \times10^{5} p = 3 × 1 0 5 , k = 250 k = 250 k = 250 , every size we tried gives a worse objective than full width.
Variation between runs. The objective differences above are averages over five starting points, and the medians over three seeds. Individual configurations vary more. For example, at p = 10 6 p = 10^{6} p = 1 0 6 , k = 500 k = 500 k = 500 and ∣ A ∣ = 2 k \lvert A\rvert= 2k ∣ A ∣ = 2 k , the average is 1.7% in favor of the active set, but one of the 15 configurations is 22% worse. Much of this variation does not come from the active set. Full-width support selection is itself sensitive to small changes, since the problem is nonconvex and hard thresholding is discontinuous (Appendix § 13 ). To measure this, we reran full-width support selection with its learning rate multiplied by 0.9 and nothing else changed, over five seeds. Measured as in Table 6 , this alone changes the objective by −62% to +96% for k ≥ 100 k \ge100 k ≥ 100 , and by up to 33% at k = 10 k = 10 k = 10 . A difference between the two arms of a few percent in either direction is therefore within the variation of full-width support selection itself.
Limitations. First, the cycle check only detects cycles of length two, which are the only ones we observed. A longer cycle would run until the cap M A S M_{AS} M A S ; no run here reached it, but this need not hold for other data. Second, the speedup depends on how many full-width updates support selection would need without the active set. This is not known in advance and ranges here from 3 to 80 for the same design. The cost of the active set itself is much more predictable.
Appendix Why the Active Set Returns a Different Support
The active set is intended to carry out the same procedure as full-width support selection at a lower cost. Its inner loop only rearranges features within A \mathcal{A} A , and the full-width check verifies that no feature outside A \mathcal{A} A should enter, so the returned support satisfies the same stopping condition as that of the arm without an active set. Nevertheless, the two arms often disagree. Across all 1,365 configurations of § 1.4 , the median fraction of the full-width support that the active set also selects is 0.60, and the supports agree completely in only 6.5% of configurations. The overlap depends strongly on k k k . It is 0.90 to 0.96 at k = 10 k = 10 k = 10 , and between 0.17 and 0.30 for k > 100 k > 100 k > 100 . At p = 10 6 p = 10^{6} p = 1 0 6 and k = 100 k = 100 k = 100 , the four nonzero starting points give an overlap of 0.00 to 0.01, so the two supports of 100 features share at most one feature. The start β 0 = 0 \beta_{0} = 0 β 0 = 0 always gives the largest overlap of the five, as expected, since from zero both arms begin by ranking the features by ∣ X T y ∣ \lvert X^{T}y\rvert ∣ X T y ∣ .
The disagreement is a consequence of the nonconvexity of Problem (2). Because of the constraint ∥ β ∥ 0 ≤ k \lVert\beta\rVert_{0} \le k ∥ β ∥ 0 ≤ k , feasible set is a union of ( p k ) \binom{p}{k} ( k p ) subspaces, and the problem has many local minima. Our method, like any tractable method for this problem, returns one of them. The stopping rule is a stationarity condition that many supports satisfy, so two procedures with the same stopping rule can end at different supports, depending on the path each one takes. The paths of the two arms differ by construction, since the inner loop of the active set moves only within A \mathcal{A} A and uses its own step size. Moreover, hard thresholding is discontinuous, so a small difference between two iterates can lead to different supports after a single update, after which the two runs evolve independently.
Rounding error does not explain these differences. § 4.3 shows its effect in this code: three methods that perform the same arithmetic in different orders return identical supports, with coefficients that agree to 10 − 6 10^{-6} 1 0 − 6 . Rounding can decide between two nearly tied features, but it cannot explain why one arm finds the signal while the other misses it. Table 13 shows what happens for one instance. For each arm, it reports how many of the 50 true features are recovered and whether the returned support is a fixed point, that is, whether one more full-width update leaves it unchanged.
Table 13. What each arm returns at p = 10 6 p = 10^6 p = 1 0 6 , ∣ A ∣ = 5 k |\mathcal{A}| = 5k ∣ A ∣ = 5 k , for one instance (seed 0). “true found” counts the features of the true signal in the returned support, “fixed pt.” records whether one more full-width update leaves the support unchanged, and “overlap” is the fraction of the full-width support that the active set also selects.
The low overlap has two different causes, which appear at different values of k k k . At k = 100 k = 100 k = 100 , from three of the five starting points, full-width support selection recovers none of the 50 true features, whereas the active set started from the same point recovers 22 or 23. The overlap of 0.01 in these rows therefore does not reflect a choice between interchangeable features. This accounts for the objective difference of about − 35 % -35\% − 35% at p = 10 6 p = 10^6 p = 1 0 6 , k = 100 k = 100 k = 100 , which holds for every ∣ A ∣ |\mathcal{A}| ∣ A ∣ from 2 k 2k 2 k to 8 k 8k 8 k (Table 6 and Table 12 ). Here the cheaper procedure is also the more reliable one. These failures are local optima rather than early stops. Every full-width run in the table stops through the ordinary rule and none through the cycle check, and the Gaussian row is a fixed point that contains no true feature, so additional updates would not help. With a dense starting point, β o \beta_o β o dominates the first update, so the top k k k is drawn from β o \beta_o β o rather than from the data, and the full-width step size is too small to move away from this support. The active set avoids this because its inner loop works on X A X_{\mathcal{A}} X A , where it can take much larger steps and rebuild the support before the full-width check.
Table 12. The full ∣ A ∣ \lvert A\rvert ∣ A ∣ sweep. Each cell gives the solve-only speedup of the active set over full-width support selection (learning rate selection excluded from both arms), followed by the objective difference in percent, as defined in Table 6 . Negative differences mean the active set found the better support.
At k = 500 k = 500 k = 500 the cause is near-ties. Both arms recover part of the true signal (23 to 28 true features without the active set and 15 to 27 with it), but different parts. There are 113 features within 1% of the 500th largest ∣ X T y ∣ |X^T y| ∣ X T y ∣ , compared with 28 at k = 100 k = 100 k = 100 and only 2 at k = 10 k = 10 k = 10 . With so many nearly equal candidates, the selection among them is close to arbitrary. This explains the low overlap at k = 500 k = 500 k = 500 , why neither arm is consistently better there, and why the two arms agree almost perfectly at k = 10 k = 10 k = 10 .
The fixed point column shows a further difference. The active set returns a fixed point in five of five configurations at k = 100 k = 100 k = 100 and three of five at k = 500 k = 500 k = 500 , compared with three and one for the arm without it. The stopping rule compares supports only after a single update while the coefficients continue to change, so a support that is unchanged after one update may still change later. The active set satisfies the rule in this stronger sense more often, because it solves to stability within A \mathcal{A} A before each full-width check.
In summary, both causes stem from the nonconvexity of the problem. At k = 100 k = 100 k = 100 one arm reaches a poor local optimum that the other avoids, and at k = 500 k = 500 k = 500 there are many local optima of nearly equal quality. In neither case is the difference due to rounding error, and in neither case does the active set depart from the method it implements.
Amortizing Learning Rate Selection
Learning rate selection (§ 3.3 ) depends only on the design and on ( k , λ 2 ) (k,\lambda_2) ( k , λ 2 ) . One selection therefore serves the whole batch, however many values of β o \beta_o β o and λ 1 \lambda_1 λ 1 it contains, and its share of the run time should fall as ∏ C \prod C ∏ C grows. To test this, Table 14 grows ∏ C \prod C ∏ C along the λ 1 \lambda_1 λ 1 axis at p = 10 6 p = 10^6 p = 1 0 6 and k = 100 k = 100 k = 100 , with ∣ A ∣ = 5 k |\mathcal{A}| = 5k ∣ A ∣ = 5 k and one seed.
Table 14. Growing ∏ C \prod C ∏ C along the λ 1 \lambda_1 λ 1 axis at p = 10 6 p = 10^6 p = 1 0 6 , k = 100 k = 100 k = 100 , ∣ A ∣ = 5 k |\mathcal{A}| = 5k ∣ A ∣ = 5 k . “LR share” is the fraction of the total run time spent on learning rate selection, which takes 0.17 s in every row.
Learning rate selection takes 0.17 s in every row, while the solve time grows with ∏ C \prod C ∏ C . Its share of the run without an active set falls from 30% to 2%, and the end-to-end speedup rises from 3.0 to 7.2, approaching the solve-only speedup of about 8. At ∏ C = 5 \prod C = 5 ∏ C = 5 , learning rate selection takes up most of the active set’s run time, so the end-to-end figure understates the benefit of the active set by nearly a factor of three. Since ParaDeAl is designed for large batches, the solve-only speedup is the more relevant figure in practice.
Parallelizing the Active Set Across k k k
In § 4.4 each batch has a single value of k k k , and different values of k k k are run one after another. The reason is that k k k is the only hyperparameter that makes the active set ragged. If ∣ A ∣ |\mathcal{A}| ∣ A ∣ depends on k k k , as with ∣ A ∣ = 5 k |\mathcal{A}| = 5k ∣ A ∣ = 5 k , then a batch with several values of k k k produces blocks X A X_{\mathcal{A}} X A of different widths. These blocks must be padded to the largest width and handled with an overlay, as in Resizing to Candidate Set (§ 4.3 ). A configuration with k = 10 k = 10 k = 10 in a batch whose largest k k k is 100 then does ten times more arithmetic than it needs. Unlike in value modification, this padded gather is repeated in every round.
The problem disappears if ∣ A ∣ |\mathcal{A}| ∣ A ∣ is the same for every configuration in the batch. Every block then has size n × ∣ A ∣ n \times|\mathcal{A}| n × ∣ A ∣ , so no padding is needed, and the only remaining difference between configurations is the k k k used in the hard threshold, which Algorithm 4 already handles. A configuration with a small k k k then has a larger active set than it needs. This does no harm, since A \mathcal{A} A only needs to contain the support that is eventually selected.
We test this at p = 10 6 p = 10^6 p = 1 0 6 with k ∈ { 10 , 50 , 100 } k \in\{10, 50, 100\} k ∈ { 10 , 50 , 100 } and a shared ∣ A ∣ = 500 |\mathcal{A}| = 500 ∣ A ∣ = 500 . We compare one batch of 15 configurations (five starting points for each k k k ) with three batches of 5 run one after another. The single batch is 1.82 times faster on the solve (0.088 s against 0.159 s), because the three values of k k k share their full-width updates, which reduces their number from 11 to 5. The end-to-end gain is only 1.14 times, because at this ∏ C \prod C ∏ C both runs are dominated by learning rate selection, which is still run once per value of k k k . The two approaches return the same supports, and their objectives after value modification agree to within 10 − 7 10^{-7} 1 0 − 7 in relative terms on every configuration and seed. The cost is memory: 0.567 GiB against 0.191 GiB, since all 15 configurations are held at once.
Batching across k k k is therefore available when it is needed, at the cost of holding ∣ A ∣ |\mathcal{A}| ∣ A ∣ fixed and of the memory to keep every configuration in the batch at once. For the experiments of § 4.4 we keep k k k sequential. This costs little, since a single case at p = 10 6 p = 10^6 p = 1 0 6 takes well under a second.
The Competitors in Detail
This appendix describes how each competitor of § 5 works and how we run it. All CPU methods run on a single core of the same node, and each method, dataset and grid runs in its own process.
L0Learn
L0Learn [18 , 20 ] fits L 0 L_0 L 0 -regularized linear models. For squared error loss it minimizes
1 2 ∥ y − X β ∥ 2 2 + λ 0 ∥ β ∥ 0 + γ 1 ∥ β ∥ 1 + γ 2 ∥ β ∥ 2 2 , \frac{1}{2}\lVert y-X\beta\rVert_2^2+\lambda_0\lVert\beta\rVert_0+\gamma_1\lVert\beta\rVert_1+\gamma_2\lVert\beta\rVert_2^2, 2 1 ∥ y − X β ∥ 2 2 + λ 0 ∥ β ∥ 0 + γ 1 ∥ β ∥ 1 + γ 2 ∥ β ∥ 2 2 ,
with the L 0 L_0 L 0 penalty on its own or paired with one of the other two penalties (the L0L1 and L0L2 penalties). The main difference from ParaDeAl is that sparsity is penalized, not constrained: the user cannot ask for a support of size k k k , only for a value of λ 0 \lambda_0 λ 0 , and L0Learn reports whatever support that value produces.
The core algorithm of L0Learn is cyclic coordinate descent. Each coordinate is set to the exact minimizer of the objective with all other coordinates fixed, which for the L 0 L_0 L 0 penalty is a thresholding rule. Hazimeh and Mazumder [18 ] show that the points to which coordinate descent converges, the coordinate-wise minima, form a subset of the fixed points of iterative hard thresholding. Coordinate descent can therefore stop at better solutions than IHT, but never at worse ones, which is part of why L0Learn is a strong accuracy benchmark. An optional local search that swaps features in and out of the support (the CDPSI algorithm) improves the solutions further; we use the default, plain coordinate descent (CD).
L0Learn computes a whole path of solutions per call. For each value of γ \gamma γ (a grid of nGamma values between gammaMin and gammaMax), L0Learn chooses a decreasing sequence of nLambda values of λ 0 \lambda_0 λ 0 , each set so that the support changes, shrinking by the factor scaleDownFactor = 0.8. Every solution on the path is warm-started from the previous one. Two further devices keep each fit cheap: an active set (coordinate descent cycles only over the current support until the support stabilizes, then checks the remaining features) and correlation screening (at most screenSize = 1000 candidate features are considered at a time). The path stops early once the support exceeds maxSuppSize. The solver is written in C++ with the Armadillo library and called from R.
Settings. Version 2.1.0 in R 4.4.0, one core, algorithm = "CD", nGamma = nLambda = G G G for G ∈ { 10 , 30 , 100 } G \in\{10, 30, 100\} G ∈ { 10 , 30 , 100 } , maxSuppSize = 500, intercept = FALSE, and the remaining settings at their defaults (maxIters = 200, rtol = 10 − 6 10^{-6} 1 0 − 6 , active set and screening on).
glmnet
glmnet [17 ] is the standard solver for the lasso and the elastic net. For the Gaussian family it minimizes
1 2 n ∥ y − X β ∥ 2 2 + λ ( α ∥ β ∥ 1 + 1 − α 2 ∥ β ∥ 2 2 ) , \frac{1}{2n}\lVert y-X\beta\rVert_2^2+\lambda\left(\alpha\lVert\beta\rVert_1+\frac{1-\alpha}{2}\lVert\beta\rVert_2^2\right), 2 n 1 ∥ y − X β ∥ 2 2 + λ ( α ∥ β ∥ 1 + 2 1 − α ∥ β ∥ 2 2 ) ,
where α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] sets the mix of the two penalties and λ \lambda λ their overall strength. glmnet has no sparsity constraint and no L 0 L_0 L 0 penalty, so the comparison with glmnet is on the elastic net alone.
glmnet is built around the regularization path. For a fixed α \alpha α , the path starts at the smallest λ \lambda λ for which β = 0 \beta= 0 β = 0 , decreases λ \lambda λ geometrically over nlambda values down to lambda.min.ratio times that value (0.01 when n < p n < p n < p , as here), and warm-starts each fit from the previous solution. Neighboring solutions on the path are close, so each warm-started fit needs few passes. Within a fit, glmnet runs cyclic coordinate descent with two devices that make it fast on wide data. Sequential strong rules (Tibshirani et al., [38 ] ) discard most features before the fit starts, based on the previous solution, and check the discarded features afterwards. Active-set cycling iterates over the current nonzeros until they converge before sweeping all features. With p ≥ 500 p \ge500 p ≥ 500 , glmnet uses the “naive” updates, which keep the residual up to date instead of forming inner products of features. The path can also end early, once the explained deviance stops improving (by less than 10 − 5 10^{-5} 1 0 − 5 ) or reaches 0.999. The solver is written in Fortran and called from R.
This design is the main obstacle for ParaDeAl. A warm-started path with screening does very little work per additional λ \lambda λ , while ParaDeAl solves every configuration from zero at full width. ParaDeAl has to win through parallelism and through stopping each configuration as soon as that configuration has converged.
Settings. Version 5.0 in R 4.4.0, one core, a for loop over G α G_{\alpha} G α values of α \alpha α evenly spaced in [ 0.05 , 0.95 ] [0.05, 0.95] [ 0.05 , 0.95 ] , each call computing a path of nlambda = G_{\lambda} values, with standardize = FALSE, intercept = FALSE and the default convergence threshold thresh = 10^{-7}.
scikit-learn
The ElasticNet class of scikit-learn [29 ] minimizes
1 2 n ∥ y − X w ∥ 2 2 + a r ∥ w ∥ 1 + a ( 1 − r ) 2 ∥ w ∥ 2 2 \frac{1}{2n}\lVert y-Xw\rVert_2^2 + ar\lVert w\rVert_1 + \frac{a(1-r)}{2}\lVert w\rVert_2^2 2 n 1 ∥ y − X w ∥ 2 2 + a r ∥ w ∥ 1 + 2 a ( 1 − r ) ∥ w ∥ 2 2
the same objective as glmnet in a different parametrization. The solver is cyclic coordinate descent written in Cython and stops when the largest coordinate update falls below the tolerance and the duality gap confirms convergence. scikit-learn is the most widely used Python implementation and serves here as the plain reference: one configuration at a time, no path, no screening. (scikit-learn does offer a path function; the comparison fits each configuration separately, as a user sweeping a grid would.)
Settings. Version 1.2.2, one core, fit_intercept = False, precompute = False, selection = "cyclic", tol = 10^{-4} (the default) and max_iter = 10,000 so that every fit converges (none reported a convergence warning). Fitting a 100 × 100 100 \times100 100 × 100 grid this way would take days on the larger datasets, so we fit a fixed random subset of at most 50 of glmnet’s configurations and report the per-configuration average times the size of the grid.
skglm
skglm [5 ] is a recent Python library designed for speed on sparse generalized linear models. The library combines a working-set strategy (a sequence of small subproblems on the features most likely to be nonzero, with the set growing until the optimality conditions hold for all features) with coordinate descent accelerated by Anderson extrapolation, and compiles its inner loops with Numba. The ElasticNet class of skglm uses the parametrization and interface of scikit-learn, so skglm can replace scikit-learn directly.
Settings. Version 0.3.1 (the latest release compatible with scikit-learn 1.2.2 on the cluster), one core, fit_intercept = False, tol = 10^{-4}, on the same subset of configurations as scikit-learn, with one untimed warm-up fit so that Numba compilation is not counted.
Converting the penalty parameters
Every solution that a competitor returns defines one ParaDeAl configuration. Both conversions below were verified on the returned solutions, through stationarity on the support (median relative violation 10 − 9 10^{-9} 1 0 − 9 for LoLearn and 10 − 3 10^{-3} 1 0 − 3 for glmnet, the latter at glmnet’s own tolerance).
LOLearn rescales y y y to unit norm before solving, so a returned γ \gamma γ corresponds to λ 1 = 2 γ ∥ y ∥ 2 \lambda_1 = 2\gamma\lVert y\rVert_2 λ 1 = 2 γ ∥ y ∥ 2 (L0+L1) or λ 2 = 2 γ \lambda_2 = 2\gamma λ 2 = 2 γ (L0+L2) in ParaDeAl’s objective, and the support size of the solution becomes k k k .
glmnet fits y / s y y/s_y y / s y with s y = mean ( y 2 ) s_y = \sqrt{\operatorname{mean}(y^2)} s y = mean ( y 2 ) and reports λ \lambda λ in the units of y y y , which is exact for the L 1 L_1 L 1 term but not for the ridge term. A returned pair corresponds to λ 1 = 2 n λ α \lambda_1 = 2n\lambda\alpha λ 1 = 2 nλ α and λ 2 = n λ ( 1 − α ) / s y \lambda_2 = n\lambda(1-\alpha)/s_y λ 2 = nλ ( 1 − α ) / s y . Without the factor 1 / s y 1/s_y 1/ s y , ParaDeAl and glmnet would solve different problems.
What each comparison measures
The four competitors test different things. Against L0Learn, the question is how much speed ParaDeAl gains by parallelizing over the whole grid, and how much accuracy ParaDeAl gives up by using IHT with a sparsity constraint instead of coordinate descent with a penalty. Against glmnet, the question is whether solving every configuration at once, in parallel, can beat a sequential path that reuses each solution to start the next. Against scikit-learn and skglm, the question concerns the more common situation of a user who fits one configuration at a time.
Construction of the Real Datasets
Why the feature count is expanded. In practice, the number of samples n n n is far easier to scale than the number of features p p p : collecting additional data (people, measurements) is a matter of equipment and funding, while devising new characteristics to measure is much harder. Public regression datasets therefore have few features (Section 5.2). Feature expansion should preserve the information in the original features. We considered two techniques and use both.
Powers and interactions. The w w w th power includes all terms of the form ∏ i = 1 p x i r i \prod_{i=1}^{p} x_i^{r_i} ∏ i = 1 p x i r i , with x i x_i x i the i i i th feature and ∑ i = 1 p r i = w \sum_{i=1}^{p} r_i = w ∑ i = 1 p r i = w . The total number of features up to power w w w is ∑ i = 1 w ( i + p − 1 i ) = ( w + p w ) − 1 ≈ p w / w ! \sum_{i=1}^{w} \binom{i+p-1}{i} = \binom{w+p}{w} - 1 \approx p^w/w! ∑ i = 1 w ( i i + p − 1 ) = ( w w + p ) − 1 ≈ p w / w ! ; for p = 3 p = 3 p = 3 and w = 50 w = 50 w = 50 there are already 23,425 features. This construction keeps the original features and lets a linear model capture nonlinear relationships and interactions. The experiments use w = 2 w = 2 w = 2 without squares: the original columns and every product x i x j x_i x_j x i x j , i < j i < j i < j .
Nearest-neighbor features. When n n n is large, each sample can be augmented with the features of its h h h nearest neighbors, giving ( h + 1 ) p (h+1)p ( h + 1 ) p features; for p = 25 p = 25 p = 25 and n = 1,000 n = 1{,}000 n = 1 , 000 , h = 50 h = 50 h = 50 gives 1,275 features. The neighbors may be scaled or transformed to dilute their influence on the original row. The same construction applies to temporal data, by flattening the previous h h h rows into one row vector.
Categorical variables are encoded numerically and missing values are imputed or removed.
The three datasets. Neighbors are found in the z-scored base features and exclude the row itself.
Diabetes ([13 ] ): 47 features (every column except the two IDs and the response, time in hospital), pairwise interactions (1,128 columns), then the interaction features of the 250 nearest neighbors found among all 101,766 rows (p = 283,128 p = 283{,}128 p = 283 , 128 ); 2,500 training and 1,000 test rows.
Communities and Crime ([31 ] ): 122 features with mean imputation, response ViolentCrimes-PerPop, pairwise interactions (7,503 columns), then 10 nearest neighbors (p = 82,533 p = 82{,}533 p = 82 , 533 ); 1,500 training and 250 test rows.
Air Quality ([15 ] ): 12 features predicting the temperature T, 15 nearest neighbors (192 columns), then pairwise interactions (p = 18,528 p = 18{,}528 p = 18 , 528 ); 1,000 training and 1,000 test rows.
Every column of the training X X X has mean 0 and L 2 L_2 L 2 norm 1, the test set receives the training transformation, and y y y is centered with the training mean.
The three polynomial datasets. These datasets use no neighbor features. Each base feature is replaced by its normal score: its values are ranked (over all n n n rows, without using y y y ), rank r r r is mapped to Φ − 1 ( ( r − 1 / 2 ) / n ) \Phi^{-1}((r-1/2)/n) Φ − 1 (( r − 1/2 ) / n ) , where Φ \Phi Φ is the standard normal distribution function, and the result is standardized. This keeps the order of the values but removes skewness and outliers, so that products of features are not dominated by a few extreme rows. The features are then the base features, the products of two distinct base features and the products of three distinct base features (no squares or cubes), each scaled as above.
Communities and Crime: the same 122 base features, response and rows as above; all 122 + 7,381 + 295,240 = 302,743 122+7{,}381+295{,}240=302{,}743 122 + 7 , 381 + 295 , 240 = 302 , 743 products.
NHANES (cycles 2015–16 and 2017–18): adults aged 20 or over with a systolic blood pressure reading. The response is the mean of up to three systolic readings, and the 52 base features are examination and laboratory values. A value is left out if more than 30% of its entries are missing, below the detection limit, or equal to its most common value, or if it has correlation above 0.95 with a value already kept; rows with missing entries are removed, and values with skewness above 2 are log-transformed. All 23,478 products; 2,500 training and 1,000 test rows.
Weather: the weather prediction dataset of Huber et al. [21 ] , daily measurements from 18 European cities in 2000–2010. The response is the next day’s mean temperature in Basel, as a deviation from its seasonal average; the 128 base features are the same-day measurements of the other cities, each also expressed as a deviation from its seasonal average, so that the shared yearly cycle does not make every column look alike. Measurements with correlation above 0.95 with one already kept are left out. Of the 349,632 possible products, 100,000 are sampled at random. The training rows are the first 2,500 days and the test rows are the remaining 1,123 days after a gap of 30 days, so the test set lies entirely in the future.
Clipping the Diabetes test features. Many Diabetes features are rare categories (medications almost nobody takes, uncommon admission codes). Repeating these features through 251 neighbor blocks produces columns that are constant (35,975 of them, set to 0) or nearly constant on the 2,500 training rows. Scaling a nearly constant column to unit norm multiplies the column by a very large factor, so a test row that differs from the training rows in such a column takes a huge value: 332 Diabetes test columns reach magnitudes up to 4,700, against at most 1 in training. Any coefficient on such a column then produces a large test error, for every method. On Crime and Air Quality, the test values stay within a factor of 4 of the training range. We therefore also report the test RE with each test feature clipped to the training range of its column, which is what one would do at prediction time; the solutions are the same, and only the test features used for scoring differ.
Experimental Setup in Detail
Grids. L0Learn: nGamma = nLambda = 10, 30, 100 and maxSuppSize = 500; each solution gives one ParaDeAl configuration, with k k k equal to L0Learn’s support size (support size 0 and repeated tuples are dropped). glmnet: 10, 30 or 100 values of α \alpha α evenly spaced in [ 0.05 , 0.95 ] [0.05,0.95] [ 0.05 , 0.95 ] , each with a path of 10, 30 or 100 values of λ \lambda λ , plus the two additional grids 10 α × 100 λ 10\alpha\times100\lambda 10 α × 100 λ and 30 α × 100 λ 30\alpha\times100\lambda 30 α × 100 λ . L0+L1+L2 uses glmnet’s ( λ 1 , λ 2 ) (\lambda_1,\lambda_2) ( λ 1 , λ 2 ) pairs with k = 50 k=50 k = 50 .
ParaDeAl. fp32 throughout (TF32 off), with all configurations of a run solved together on one L40S, in chunks sized to a 30 GB working budget. In the L0 modes, support selection is proximal gradient with hard thresholding, with at most 100 iterations per sweep and the support-unchanged stopping rule, inside the active set procedure. The step size of every configuration comes from the parallel search for the largest stable η \eta η : a geometric ladder of 17 multiples of η 0 = 1 / ( 2 ( σ max 2 ( X ) + λ 2 ) ) \eta_0=1/(2(\sigma_{\max}^2(X)+\lambda_2)) η 0 = 1/ ( 2 ( σ m a x 2 ( X ) + λ 2 )) , 25 probe iterations, and one probe per distinct pair ( k , λ 2 ) (k,\lambda_2) ( k , λ 2 ) . Support selection returns the iterate with the lowest objective seen in any sweep or active-set round (§ 2.2.1 ). Value modification on the fixed support uses conjugate gradients when λ 1 = 0 \lambda_1=0 λ 1 = 0 and proximal gradient otherwise. Pair swaps (§ 3.4 ) then run with M = 16 M = 16 M = 16 candidate additions, D = 8 D = 8 D = 8 candidate drops, a relative improvement threshold of 10 − 7 10^{-7} 1 0 − 7 and at most 200 rounds; each accepted move is refit by value modification at the same tolerance, warm-started from the current coefficients.
Final configuration. The results of Section 5.4 come from a second full run of ParaDeAl; the competitor runs are unchanged, since their results do not depend on ParaDeAl. Relative to the first run, the second run changes three things.
Dynamic Shrinking everywhere. Every loop in which configurations iterate (IHT sweeps, active-set rounds, conjugate gradients, value modification and L1+L2) freezes a configuration once that configuration has stopped. Whenever another 5% of the current batch has stopped, the loop writes the finished configurations out and compacts every per-configuration tensor to the configurations still running. Compaction stops once 50 or fewer configurations are left, where its indexing costs more than it saves. The first run used the Flag Approach , which keeps computing finished configurations until the whole batch is done.
A looser stopping tolerance. Every value solver (L1+L2, value modification, conjugate gradients) stops a configuration when its relative change ∥ β t + 1 − β t ∥ / ∥ β t + 1 ∥ \lVert\beta_{t+1}-\beta_t\rVert/\lVert\beta_{t+1}\rVert ∥ β t + 1 − β t ∥ / ∥ β t + 1 ∥ (for conjugate gradients, its relative residual) falls below the tolerance. The first run used 10 − 6 10^{-6} 1 0 − 6 , which fp32 cannot resolve, so nearly every configuration ran to the iteration cap. L1+L2 is now run at 10 − 3 10^{-3} 1 0 − 3 and at 5 ⋅ 10 − 4 5 \cdot10^{-4} 5 ⋅ 1 0 − 4 , and the L0 modes at 5 ⋅ 10 − 4 5 \cdot10^{-4} 5 ⋅ 1 0 − 4 . Support selection keeps its support-unchanged rule.
The active set in every L0 run, including Air Quality, with ∣ A ∣ = max ( 250 , 5 k ) \lvert A\rvert= \max(250,5k) ∣ A ∣ = max ( 250 , 5 k ) instead of max ( 250 , 2 k ) \max(250,2k) max ( 250 , 2 k ) .
Three solvers for L1+L2. L1+L2 has no thresholding and is run in three variants: plain proximal gradient with at most 1,000 and with at most 5,000 iterations, and FISTA with at most 5,000 iterations. Section 5.4 reports FISTA.
FISTA. Plain proximal gradient (ISTA) takes each step from the current iterate:
β t + 1 = soft ( β t − η ∇ F ( β t ) , η λ 1 ) , ∇ F ( β ) = 2 X T ( X β − y ) + 2 λ 2 β . \beta_{t+1} = \operatorname{soft}\left(\beta_t-\eta\nabla F(\beta_t),\eta\lambda_1\right), \qquad\nabla F(\beta) = 2X^{T}(X\beta-y)+2\lambda_2\beta. β t + 1 = soft ( β t − η ∇ F ( β t ) , η λ 1 ) , ∇ F ( β ) = 2 X T ( X β − y ) + 2 λ 2 β .
FISTA [4 ] takes the identical step, but from a point pushed further along the direction in which the iterates were already moving:
z t = β t + s t − 1 − 1 s t ( β t − β t − 1 ) , β t + 1 = soft ( z t − η ∇ F ( z t ) , η λ 1 ) , s t = 1 + 1 + 4 s t − 1 2 2 , s 0 = 1. z_t = \beta_t+\frac{s_{t-1}-1}{s_t}(\beta_t-\beta_{t-1}), \qquad\beta_{t+1} = \operatorname{soft}\left(z_t-\eta\nabla F(z_t),\eta\lambda_1\right), \qquad s_t = \frac{1+\sqrt{1+4s_{t-1}^{2}}}{2}, \qquad s_0 = 1. z t = β t + s t s t − 1 − 1 ( β t − β t − 1 ) , β t + 1 = soft ( z t − η ∇ F ( z t ) , η λ 1 ) , s t = 2 1 + 1 + 4 s t − 1 2 , s 0 = 1.
The gradient, the thresholding and the objective are unchanged, and each iteration still costs one product X T ( X z ) X^{T}(Xz) X T ( X z ) . The momentum weight s t s_t s t is a single scalar shared by every configuration, so FISTA batches over configurations exactly like the plain method: the Flag Approach or Dynamic Shrinking , chunking and the tensor layout carry over without change. The two methods differ in four ways.
Rate. The objective error falls like O ( 1 / t ) O(1/t) O ( 1/ t ) for ISTA and like O ( 1 / t 2 ) O(1/t^2) O ( 1/ t 2 ) for FISTA. On strongly correlated designs this difference is the one that matters. On Air Quality (σ max 2 ( X ) = 7,089 \sigma_{\max}^{2}(X) = 7{,}089 σ m a x 2 ( X ) = 7 , 089 with unit-norm columns), a pilot on the 10 × \times × 10 grid gave a glmnet-to-ParaDeAl train RE ratio of 0.915 for plain proximal gradient after 1,000 iterations and 0.990 after 10,000, while FISTA matched glmnet to four decimals after 5,000.
Step size. The guarantee of FISTA needs η = 1 / L \eta= 1/L η = 1/ L with L = 2 ( σ max 2 ( X ) + λ 2 ) L = 2(\sigma_{\max}^{2}(X)+\lambda_2) L = 2 ( σ m a x 2 ( X ) + λ 2 ) ; the plain method may go up to 2 / L 2/L 2/ L and is run at 0.9 ⋅ 2 / L 0.9 \cdot2/L 0.9 ⋅ 2/ L . The steps of FISTA are therefore about half as long, and the momentum makes up for the shorter steps many times over.
FISTA is used only in the L1+L2 mode, where there is no hard thresholding. Momentum combined with H k H_k H k has no standard convergence guarantee, so the L0 modes use the method of § 2 unchanged.
Alternatives tested and not adopted. All of the following were run with Dynamic Shrinking on L1+L2.
An active set for L1+L2. Each configuration starts from the (at most 250) features that violate optimality at β = 0 \beta= 0 β = 0 , solves on its block, then checks optimality at full width and adds the violators, until none remain, which certifies the full solution. The procedure is exact but slower than full width: 60 s against 32 s on Crime 30 × \times × 30 (FISTA, tolerance 10 − 4 10^{-4} 1 0 − 4 ), and 858 s against glmnet’s 570 s on Diabetes 30 × \times × 30. The supports are too large for the procedure to pay off. On Diabetes the block grew to 25,250 columns and some configurations were still adding features after 100 rounds, and growing the block by five times the support size instead of by 250 per round ran out of GPU memory. With supports in the thousands there is little to screen out, and every round pays for a full-width optimality check and restarts the momentum of FISTA.
FISTA with adaptive restart ([28 ] ), which resets the momentum of a configuration when the momentum points against the step. This variant is faster (5.6× \times × glmnet instead of 4.0× \times × on Air Quality 100 × \times × 100) but less accurate (train RE 0.9% and test RE 3% worse than glmnet): after a restart the step is short, so the relative-change rule stops the configuration too early.
Measurements. Accuracy is computed by one Python routine for every method, from the returned coefficients. Runtime and storage are measured in each method’s own language, since R and Python time differently. R uses system.time (elapsed) around the solver calls. Python uses perf_counter, with a CUDA synchronization before each reading for ParaDeAl and after one untimed warm-up. ParaDeAl’s time includes everything from the configurations to the final coefficients (σ max \sigma_{\max} σ m a x , the step-size search and both stages). Storage is peak memory above the resident data: GPU memory for ParaDeAl and process resident memory for the CPU methods, with the peak counter reset right before the solve. scikit-learn and sklearn fit one configuration at a time, so on every grid a fixed random subset of at most 50 configurations is timed and scored, and the full-grid time is the per-configuration average times the grid size.
Results on the Polynomial Datasets
Table 15 repeats the comparison of § 5.4 on the three polynomial datasets of § 5.2 , which are built without neighbor features and whose correlations are weaker. It supports the conclusions drawn there.
Trying Several Supports Before Value Modification
§ 2.2 notes that the support chosen by support selection is not always the support with the smallest objective after value modification. This appendix measures how often that happens and how much is gained by trying several supports instead of one.
Setup. For each configuration we collect about 15 candidate supports from three sources, refit every candidate with ParaDeAl’s own value modification, and keep the one with the smallest objective. (i) The last five distinct supports visited during support selection, together with the support of the lowest-objective iterate. (ii) Four one-for-one exchanges at the edge of the hard threshold: the weakest feature in the support is replaced by one of the strongest features just outside it. (iii) Support selection rerun with the starting step size, a quarter and a sixteenth of the chosen step size, and from a random starting point. The chosen support is the one returned by Algorithm 1 with the last-iterate rule. We use 30 × 30 grids in both L0 modes, on the three real datasets of § 5 and on synthetic data (n = 1,000 n = 1{,}000 n = 1 , 000 , p = 20,000 p = 20{,}000 p = 20 , 000 , 50 true features, SNR 5) with either independent features or columns whose correlation is 0.5 ∣ i − j ∣ 0.5^{\lvert i-j\rvert} 0. 5 ∣ i − j ∣ , as in Appendix § 9 . Pair swaps (§ 3.4 ) are run from the same chosen support for comparison.
Results. Table 16 answers both questions. The chosen support is often not the best one: on the real datasets, some candidate beats it for 66 to 99% of configurations. The gain from picking the best candidate is real but partial. It recovers 30 to 64% of the improvement that pair swaps achieve on the real datasets, and most of it comes from the exchanges at the edge of the hard threshold, at small k k k (between 2 and 20). With independent features the chosen support is already within 0.5% of L0Learn, and the gaps are tiny. On five further real datasets with weaker correlations, the picture is the same: a better candidate exists for 50 to 89% of configurations, and the best candidate recovers 24 to 70% of the pair swap improvement.
Table 16. Trying about 15 supports per configuration. The first three columns of each mode give the optimization objective of L0Learn divided by that of ParaDeAl, averaged over configurations (‘Bo15’ means ‘Best of 15’, and 1 means the same objective; above 1, ParaDeAl is better), for the chosen support, the best of the candidates, and pair swaps. “Gap closed” is the share of pair swap’s improvement over the chosen support that the best candidate recovers. “Not best” is the share of configurations for which some candidate beats the chosen support.
The candidates are also not cheaper than pair swaps. Refitting about 15 supports per configuration added 0.3 to 3.9 s per grid, often more than the whole solve without swaps, whereas pair swaps added 0.07 to 2.2 s and reached an objective at least as good in every case. Trying several supports can be parallelized in the same way as everything else in ParaDeAl, but pair swaps are the better use of the extra computation, which is why they, and not multiple supports, are part of ParaDeAl.
Pair Swaps on Correlated Synthetic Data
This appendix gives the full results behind the paragraph “Effect” in § 3.4 . The data are synthetic, with n = 1,000 n = 1{,}000 n = 1 , 000 , p = 20,000 p = 20{,}000 p = 20 , 000 , 50 true features and SNR 5, generated as in Appendix § 9 , except that features i i i and j j j have correlation ρ ∣ i − j ∣ \rho^{\lvert i-j\rvert} ρ ∣ i − j ∣ with ρ ∈ { 0 , 0.25 , 0.5 , 0.9 , 0.99 } \rho\in\{0, 0.25, 0.5, 0.9, 0.99\} ρ ∈ { 0 , 0.25 , 0.5 , 0.9 , 0.99 } . At ρ = 0.99 \rho= 0.99 ρ = 0.99 each feature is nearly a copy of its neighbors, which is the hardest case for support selection. For each mode we solve the 30 × 30 grid of configurations chosen by L0Learn, and compare three versions of ParaDeAl: the last support of support selection, the lowest-objective support (§ 2.2.1 ), and the lowest-objective support followed by pair swaps. Times are the median of three runs on one L40S GPU; L0Learn runs on one CPU core.
Results. Table 17 shows that the weakness of ParaDeAl without pair swaps is a weakness under correlation. With independent features or ρ = 0.25 \rho= 0.25 ρ = 0.25 , ParaDeAl already matches L0Learn to within 0.4%, and with ρ = 0.5 \rho= 0.5 ρ = 0.5 it falls short only slightly. At ρ = 0.9 \rho= 0.9 ρ = 0.9 and 0.99 0.99 0.99 it reaches only 62 to 79% of L0Learn’s objective, and the shortfall is concentrated at moderate support sizes: at ρ = 0.99 \rho= 0.99 ρ = 0.99 in the L0+L1 mode, the mean ratio is 0.49 for k k k between 6 and 20 and 0.33 for k k k between 21 and 50. Choosing the lowest-objective support helps little here, since the problem is not which iterate is returned but which support is found. Pair swaps remove the shortfall: the ratio becomes 0.99 to 1.00 for every ρ \rho ρ , and 90% of the configurations lie within 0.98 to 1.03 at ρ = 0.9 \rho= 0.9 ρ = 0.9 and within 0.82 to 1.06 at ρ = 0.99 \rho= 0.99 ρ = 0.99 . The test error follows the objective, and pair swaps find about as many of the true features as L0Learn; over the three random datasets they find more in seven of the twelve comparisons, the same number in three and fewer in two. Few of the true features are found by any method at ρ = 0.99 \rho= 0.99 ρ = 0.99 , because each true feature has near-copies that fit almost equally well.
Table 17. Pair swaps on synthetic data with correlation ρ ∣ i − j ∣ \rho^{|i-j|} ρ ∣ i − j ∣ . The objective and test ratios are L0Learn’s value divided by ParaDeAl’s, averaged over configurations, so 1 is a tie and a value below 1 means L0Learn is better. “Last”, “Lowest” and “+ Pair swap” are the three versions of ParaDeAl described in the text. “Pair swap adds” is the time of the pair swaps alone, per grid. “True features found” is the share of the 50 true features in the selected support, averaged over the configurations with k = 50 k = 50 k = 50 (or the nearest k k k on L0Learn’s path).
Pair swaps are cheap. A configuration needs 4 to 7 rounds on average at ρ = 0.9 \rho= 0.9 ρ = 0.9 and 0.99 0.99 0.99 , and at most 31; no configuration in any run was still improving at the limit of 200 rounds. With pair swaps, ParaDeAl solves each grid in 0.2 to 1.7 seconds, against 5.7 to 8.7 seconds for L0Learn.
By support size. Table 18 splits the objective ratios by support size. Without pair swaps, the shortfall under strong correlation grows with k k k up to about 50; pair swaps bring every bin back to between 0.977 and 1.014. Supports larger than 100 occur in at most 8 configurations per grid and change the means by at most 0.003, so they are not shown.
Table 18. Objective ratio (L0Learn divided by ParaDeAl) on the synthetic data of Table 17 , by support size k k k . In each cell, the first number is for the last support without pair swaps, and the second for the lowest-objective support with pair swaps. A dash means that the grid has no configuration of that size.
Other random datasets. We repeated the runs with ρ ∈ { 0.9 , 0.99 } \rho\in\{0.9, 0.99\} ρ ∈ { 0.9 , 0.99 } on two further random datasets. Without pair swaps the mean objective ratio is between 0.61 and 0.80 on all six datasets, and with pair swaps it is between 0.986 and 1.029, so the results above do not depend on one particular draw.
Returning the Last Versus the Lowest-Objective Support
This appendix compares the two ways of choosing which iterate support selection returns (§ 2.2.1 ): the last iterate, and the iterate with the lowest objective. No pair swaps are used, so that the effect of the rule is seen on its own. The grids and settings are those of Appendix § 21 , on the six real datasets of § 5 and on the synthetic data of Appendix § 21 .
Results. The lowest-objective rule is never meaningfully worse than the last-iterate rule: the largest loss in Table 19 is 0.001. It helps most in the L0+L1 mode, on Weather (0.887 to 0.974), the synthetic data with ρ = 0.5 \rho= 0.5 ρ = 0.5 (0.942 to 0.985), NHANES (0.879 to 0.918) and Crime with products of up to 3 (0.869 to 0.898); elsewhere the gain is between 0 and 1%. The gain is largest, and most systematic, at k = 1 k = 1 k = 1 , the case described in § 2.2.1 . On NHANES in the L0+L1 mode, 24 of the 29 configurations with k = 1 k = 1 k = 1 end more than 1% behind L0Learn under the last-iterate rule, and on the synthetic data with ρ = 0.99 \rho= 0.99 ρ = 0.99 , 27 of 29 (and 22 of 29 on a second random dataset). The lowest-objective rule fixes every one of these configurations, and under it the mean ratio at k = 1 k = 1 k = 1 is between 0.997 and 1.000 on every dataset and mode.
Table 19. The last support versus the lowest-objective support, without pair swaps. Each entry is the optimization objective of L0Learn divided by that of ParaDeAl, averaged over all configurations of the grid or over the configurations with k = 1 k = 1 k = 1 only; 1 is a tie and a value below 1 means L0Learn is better. Synthetic data use the first of the random datasets of Appendix § 21 .
The two rules return a different support for between 0 and 40% of the configurations (most often on Air Quality). The lowest-objective support is better after value modification in almost all of these cases, and worse in at most 4% of all configurations. Since value modification can reorder two supports (§ 2.2 and Appendix § 20 ), a lower objective during support selection does not guarantee a lower objective at the end, but it does so in most cases. The rule adds no measurable runtime: the differences between the two rules are within the variation between repeated runs.
Agreement with L0Learn's Supports
Section 5.4 compares ParaDeAl and L0Learn through their objectives and test errors. This appendix compares the supports themselves, on the configurations of Section 5, pooled over the three grids. For each configuration we record whether the two supports are identical, and their overlap ∣ A ∩ B ∣ / ∣ A ∪ B ∣ |A \cap B|/|A \cup B| ∣ A ∩ B ∣/∣ A ∪ B ∣ , where A A A and B B B are the supports returned by ParaDeAl and L0Learn. tbl:20 gives both by support size, for ParaDeAl with the lowest-objective support (Section 2.2.1) and with pair swaps added (Section 3.4).
Table 20a. (a) Share of configurations with identical supports (%), without / with pair swaps.
Table 20b. (b) Mean overlap ∣ A ∩ B ∣ / ∣ A ∪ B ∣ |A \cap B|/|A \cup B| ∣ A ∩ B ∣/∣ A ∪ B ∣ , without / with pair swaps.
tbl:20 : Agreement between the supports of ParaDeAl and L0Learn, by support size k k k . In each cell, the first number is for ParaDeAl with the lowest-objective support and the second for ParaDeAl with pair swaps added. “Crime, products” is Communities and Crime with products of up to 3 features.
Results. Identical supports are common only for the smallest supports. With pair swaps, ParaDeAl returns L0Learn’s support for 62 to 83% of the configurations with k k k from 1 to 5 on NHANES and Weather, for 32 to 48% on the two Crime datasets and Air Quality, and almost never on Diabetes. For k k k above 20, at most a quarter of the supports are identical, and on most datasets almost none. The overlap tells the same story more gradually: pair swaps raise it on every dataset and in every bin, but even with pair swaps, two supports of the same size typically share only between a fifth and two thirds of their features. Since the objectives are nearly equal (Tables 9 and 15), this means that the two methods often find different supports of almost the same quality, as expected when many features are close copies of one another. The agreement is highest on NHANES and Weather, whose features are the least correlated.