The Hessian Screening Rule
Authors: Johan Larsson
Jonas Wallin
Venue: NeurIPS 2022 Accept (2022)
Keywords: screening-rules
lasso
l1-regularization
statistics

Abstract: Predictor screening rules, which discard predictors before fitting a model, have had considerable impact on the speed with which sparse regression problems, such as the lasso, can be solved. In this paper we present a new screening rule for solving the lasso path: the Hessian Screening Rule. The rule uses second-order information from the model to provide both effective screening, particularly in the case of high correlation, as well as accurate warm starts. The proposed rule outperforms all alternatives we study on simulated data sets with both low and high correlation for \(\ell_1\)-regularized least-squares (the lasso) and logistic regression. It also performs best in general on the real data sets that we examine. 

The Hessian Screening Rule
Johan Larsson
Jonas Wallin
Department of Statistics Lund University johan. www.ssnsssatt.t... lu.
Department of Statistics Lund University jonas wall wwallin@stat...
Abstract
Predictor screening rules, which discard predictors before fitting a model, have had considerable impact the speed with which sparse regression problems, such the lasso, can solved. this paper we present new screening rule for solving the lasso path: the Hessian Screening Rule. The rule uses second-order information from the model to provide both effective screening, particularly the case of high correlation, well accurate warm starts. The proposed rule outperforms all alternatives we study on simulated data sets with both low and high correlation for & --regularized least-squares (the lasso) and logistic regression. It also performs best in general on the real data sets that we examine.
Introduction
High-din ligh-dimensional data, where the number of features (p) exceeds the number of observations (n), poses a challenge for many classical statistical models. common remedy for this issue is to regularize the model by penalizing the regression coefficients such that the solution becomes sparse. A popular choice of such penalization is the -nomm, which, when the objective is least-squares, leads to the well-known lasso [1]. More specifically, we will focus the following convex optimization
problem:
minimize X): + ) 3EB
where f(3; is smooth and convex. We let 3 the solution vector for this problem and, abusing notation, equivalently let e - IRP be function that returns this vector for given X. Our focus lies in solving (1) along regularization path Å1, À2 .... Am with A 2 Xe 2 2 Am We start the path at Amax. which corresponds to the null (all-sparse) model and finish at some fraction of Amax for which the model is either almost saturated (in the p 2 n setting), for which the solution approaches the ordinary least-squares estimate. The motivation for this focus is that the optimal À typically unknown and must be estimated through model tuning, such as cross- cross-validan validation. This involves repeated refitting of the model to new batches of data, which is computationally demanding.
Fortunately, the introduction of so-called screening rules has improved this situation remarkably. Screening rules use tests that screen and possibly discard predictors from the model before it is fit, which effectively reduces the dimensions of the problem and leads to improvements in performance and memory usage. There are, generally speaking, two types of screening rules: safe and heuristic rules. Safe rules guarantee that discarded predictors are inactive the optimum-heuristi rules do not and may therefore cause violations: discarding active predictors. The possibility of violations mean that heuristic methods need validate the solution through checks of the Trmush-KKhn-Tie (KKT) optimality conditions after optimization has concluded and, whenever there are violations, re- run optimization, which can be costly particularly because the KKT checks themselves are expensive. This means that the distinction between safe and heuristic rules only matters in regards to algorithmic
Amax in fact available in closed form for the lasso it is max, |ej vl.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

details- all heuristic methods that we study here use KKT checks to catch these violations, which means that these methods are in fact also safe.
Screening rules can moreover also be classified as basic, sequential, or dynamic. Basic rules screen predictors based only on information available from the null model. Sequential rules use information from the previous step(s) on the regularization path to screen predictors for the next step. Finally, dynamic rules screen predictors during optimization, reducing the set of screened predictors repeatedly throughout optimization.
Notable examples of safe rules include the basic SAFE rule [2], the sphere tests [3], the R-region test [4], Slores [5], Gap Safe [6. 7]. and Dynamic Sasvi [8]. There is also a group of dual polytope projection rules, most prominently Enhanced Dual Polytope Projection (EDPP) [9]. As noted by Fercoq, Gramfort, and Salmon [6], however, the sequential version of EDPP relies on exact knowledge of the optimal solution at the previous step along the path to be safe in practice, which is only available for Amux- Among the heuristic rules, we have the Strong Rule [10), SIS [11], and ExSIS [12]. But the latter two of these are not sequential rules and solve a potentially reduced form of the problem in (I)-we will not discuss them further here. In addition to these two types of rules, there has also recently been attempts combine safe and heuristic rules into so-called hybrid rules [13].
There are various methods for employing these rules in practice. Of particular interest are so-called working ser strategies, which use a subset of the screened set during optimization, iteratively updating the set based on some criterion. Tibshirani al. [10] introduced the first working set strategy, which we in this paper will refer to simply as the working set strategy. It uses the set of predictors that have ever been active as initial working set. After convergence on this set, it checks the KKT optimality conditions on the set of predictors selected by the strong rule, and then adds predictors that violate the conditions to the working set. This procedure is then repeated until there are no violations, which point the optimality conditions are checked for the entire set, possibly triggering additional iterations of the procedure. Blitz [14] and Celer [15] are two other methods that use both Gap Safe screening and working sets. Instead of choosing previously active predictors as a working set, however, both Blitz and Celer assign priorities to each feature based on how close each feature of violating the Gap Safe check and construct the working set based on this prioritization. In addition to this, Celer uses dual point acceleration to improve Gap Safe screening and speed up convergence. Both Blitz and Celer are heuristic methods.
One problem with current screening rules is that they often become conservative-inncuee numbers of predictors into the screened set-when dealing with predictors that are strongly correlated. Tibshirani et al. [10], for instance, demonstrated this to be the case with the strong rule, which was the motivation behind the working set strategy. (See Appendix F.4 for additional experiments verifying this). Yet because the computational complexity of the KKT checks in the working set strategy still depends on the strong rule, the effectiveness of the rule may nevertheless be hampered in this situation. A possible and-as as we will soon fhlow-powerffu solution to this problem is to make use of the second-order information available from (1), and in this paper we present a novel screening rule based on this idea. Methods using second-order information (the Hessian) are often computationally infeasible for nigh-dimensional problems. We utilize two properties of the problem to remedy this issue: first, we need only to compute the Hessian for the active set, which is often much smaller than the full set of predictors. Second, we avoid constructing the Hessian (and it's inverse) from scratch for each X along the path, instead updating sequentially by means of the Schur complement. The availability of the Hessian also enables us to improve the warm starts (the initial coefficient estimate at the start of each optimization run) used when fitting the regularization path, which plays a key role in our method.
large
We present our main results in Section 3, beginning with reformulation of the strong rule and working set strategy before we arrive at the screening rule that represents the main result of this paper. In Section 4, we present numerical experiments on simulated and real data to showcase the effectiveness of the screening rule, demonstrating that the rule is effective both when p >> n and n >> p. out-performing the other alternatives that we study. Finally, in Section 5 we wrap up with a discussion on these results, indicating possible ways in which they may be extended.
2

---

2 Preliminaries
We use lower-case letters denote scalars and vectors and upper-case letters for matrices. We use and 1 to denote vectors with elements all equal to 0 or respectively, with dimensions inferred from context. Furthermore, we let sign be the standard signum function with domain {-1,0, 1), allowing it to be overloaded for vectors.
Let c(A) = -V a (B(A);;;; X) be the negative gradient, or so-called correlation, and denote A₃ {i lc(A),) > }} as the active set X: the support set of the non-zero regression coefficients corresponding (()). In the interest of brevity, we will let A Ax. We will consider / solution to (1) if it satisfies the stationary criterion
V) Xd.
(2)
Here is the subdifferential of || defined
0, {sign($,)) if +
[-1,1]
otherwise.
This means that there must be â E 0 for given À such that
V (3)(3;X) AĀ O.
(3)
3
Main Results
In this section we derive the main result of this paper: the Hessian screening rule. First, however, now introduce a non-standard perspective on screening rules. In this approach, we that (2) suggests a simple and general formulation for a screening rule, namely: we substitute the gradient vector in the optimality condition of é reggllarized problem with an estimate. More precisely, we discard the jth predictor for the problem at a given if the magnitude of the jthh component of the gradient vector estimate is smaller than this that
Jē(A))l <.
In the following sections, we review the strong rule and working set method for this problem from this perspective, that is, by viewing both methods as gradient approximations. We start with the case of the standard lasso (e-rreguarized least-squares), where we have f(3; X) = X| 3 yll2.
3.1 The Strong Rule
The sequential strong rule for li-penalized least-squares regression [10] discards the jth predictor As+1 if
x (x (Axs - n)1 le(A=)p] < 2 AR-
This is equivalent to checking that
eي (Au+1)) = c(Ab)) + (Ax - (k+1) sign(((())((
(5)
satisfies (4). The strong rule gradient approximation (5) is also known as the unit bound, since assumes the gradient of the correlation vector to be bounded by one.
3.2 The Working Set Method
simple but remarkably effective alternative to direct use of the strong rule the working set heuristic [10]. It begins by estimating 3 at the (k + 1)th step using only the coefficients that have been previously active at any point along the path, i.e. Aisk = A The working set method can be viewed gradient estimate in the sense that
W (M++1) TT
XAI. 3(A441
where A(A,A) argming blly XA8112 + *181.
3

---

3.3 The Hessian Screening Rule
We have shown that both the strong screening rule and the working set strategy can be expressed as estimates of the correlation (negative gradient) for the next step of the regularization path. As we have discussed previously, however, basing this estimate on the strong rule can lead to conservative approximations Fortunately, it turns out that we can produce better estimate by utilizing second- order information.
We start by noting that (3), in the case of the standard lasso, can be formulated as
XTXX
X X A XI
A 0
sign( (ign((())a)
X A
X
X X
A=
+
dx=
=
A
and consequently that
B(A)A = (x
X sign (B₂)).
Note that, for an interval [Λr, Au] in which the active set unchanged, that is, AA = A for all E D>u Ax], then B(A) is a continuous linear function in X (Theorem 3.1)?.
Theorem 3.1. Let B(A) be the solution of (1) where (3: 211 -1l.. Define
BA (A)aa. = 3((")An - (A* A) (X As- XAx )..r))=t) sign (B(2")ax))
and 3x (A)AS. O. for o X E DAo, holds that (i) sign (3^ (A)) = sign (3(x*) and (ii)
< X, then B(A) = 3xx (A) for X E [An, AM
max
See Appendix A for full proof. Using Theorem 3.1, have the following second-order approxima- tion of c(Ax+1);
Gl ((A41))= (N6+1)AA)) - (X3, XA.) sign (B(A)) (6)
Remark 3.2. If no changes in the active set occur in [Λ&+1; Ax]. (6) is in fact exact expression for the correlation at the next step, that is, 2t (A++1) c(Ax+1).
One problem with using the gradient estimate in (6) is that is expensive to compute due to the inner products involving the full design matrix. To deal with this, use the following modification, in which we restrict the computation of these inner products to the set indexed by the strong rule, assuming that predictors outside this set remain inactive:
Act1 sign 3(Ax),
if E Ax
ctd (Aa+1)s =
if les (Ax+1)gl < da+1 and j Axe else.
ctd (A++1)s
For nigh-dimensional problems, this modification leads to large computational gains and seldom proves inaccurate, given that the strong rule only rarely causes violations [10]. Lastly, we make one more adjustment to the rule, which is to add a proportion of the unit bound (used in the strong rule) to the gradient estimate:
e (A++1);==
=
+ 7(x+1 (Ax+t))
Ax) sign(c(>R))),
where 7 E R.,. Without this adjustment there would be no upwards bias on the estimate, which would cause more violations than would be desirable. In our experiments, we have used 7 = 0.01, which has worked well for most problems we have encountered. This finally leads us to the Hessian screening rule: discard the jth predictor at Ax+1 %² (A++1)yl A
We make one more modification in our implementation of the Hessian Screening Rule, which is to the union of the ever-active predictors and those screened by the screening rule our final set of screened predictors. We note that this is a marginal improvement to the rule, since violations of the rule are already quite infrequent. But it is included nonetheless, given that it comes no cost and occasionally prevents violations.
"This result is not new discovery [16]. but is included here for convenience because the following results depend on it.

---

As an example of how the Hessian Screening Rule performs, we examine the screening performance of several different strategies. We fit full regularization path to a design with n 200, p 20 000, and pairwise correlation between predictors of p. (See Section 4 and Appendix F.4 for more information on the setup.) We compute the average number screened predictors across iterations of the coordinate descent solver. The results are displayed in Figure and demonstrate that our method gracefully handles high correlation among predictors, offering a screened set that is many times smaller than those produced by the other screening strategies. In Appendix F.4 we extend these results to & regulaarized logistic regression as well and report the frequency of violations.
0.4
0.8
Hessian
10000
Coler
Predictors
1000
Blitz
100
Strong
10
EDPP
Gap Safe
50
100
Step
Sasvi
Figure 1: The number of predictors screened (included) for when fitting regularization path of l é1-reuularized least-squares a design with varying correlation (p). n 200, and p 20000. The values are averaged over 20 repetitions. The minimum number of active predictors at each step across iterations given as a dashed line. Note that the y-axis is on a log10 scale.
Recall that the Strong rule bounds its gradient of the correlation vector estimate at one. For the Hessian rule, there is such bound. This means that it is theoretically possible for the Hessian rule to include more predictors than the Strong rule'. In fact, it even possible to design special cases where the Hessian rule could be more conservative than the Strong rule. In practice, however, have not encountered any situation in which this is the case.
3.3.1 Updating the Hessian
A potential drawback using the Hessian screening rule is the computational costs of computing the Hessian and its inverse. Let A& be the active set at step l on the lasso path. In order to use the Hessian screening rule we need H = (XT An XAA)= Computing (XT, X Aa directly, however, has numerical complexity O(1-A& 3 [n)l.n). But if we have stored (H H previously, we can utilize it to compute (H₁, Hyx) more efficiently via the so-called sweep operator [17]. We outline this technique in Algorithm I (Appendix B). The algorithm has a reduction step and an augmentation step: in the reduction step, we reduce the Hessian and its inverse to remove the presence of any predictors that are no longer active. In the augmentation step, we update the Hessian and its inverse to account for predictors that have just become active.
The complexity of the steps depends the size of the sets C and & A& O A5-1 The complexity of the reduction step is O( +C][8] (C]1E1) and the complexity of the augmentation step is ((ID)n An iteration of Algorithm I therefore has complexity O(ID
A \ AR-1
(C][E12)
+ (D ( since > max [8), (D). [D|[E++1cT IC
In most applications, the computationally dominant term will be n|D||E| (since, typically, > |8|>
D > C) which could be compared to evaluating the gradient for 3 which n ([D) + (El) when BAy = O. Note that have far assumed that the inverse of the Hessian exists, but this need not be the case. To deal with this issue we precondition the Hessian. See Appendix C for details.
3.3.2 Warm Starts
The availability of the Hessian and its inverse offers coefficient warm start that is more accurate than the standard, naive, approach using the estimate from the previous step. With the Hessian screening rule, we use the following warm start.
B(AR+1)AE = B(Ax)A + +Ax Ax+1) H sign (b(A))AL),
"The chance of this happening tied to the setting of r.
5

---

where H is the Hessian matrix for the differentiable part of the objective. Our warm start is equivalent to the one used in Park and Hastie [18], but is here made much more efficient due due to the efficient updates of the Hessian and its inverse that we use. Remark 3.3. The warm start given by (7) is the exact solution at X if the active remains constant in [
As a first demonstration of the value of this warm start, we look at two data sets; YearPredicitionMSSD and colon-cancer. We fit full regularization path using the setup outlined in Section 4, with or without Hessian warm starts. For YearPredictionMSDD we use the standard lasso, and for colon-cancer l fi-regularized logistic regression.
The Hessian warm starts offer sizable reductions in the number of passes of the solver (Figure 2), for many steps requiring only single pass to reach convergence. On inspection, this is not a surprising find. There are no changes the active set for many of these steps, which means that the warm start is almost exact-"ate "aloss" due to the use of a preconditioner for the Hessian (see Appendix C).
colon-cancer
YearPredictionMSD
Hessian
30
Standard
Passes
20
Mar
1
10
JUL
'
JU
0
50
75
100
Step
Figure 2: Number of passes of coordinate descent along a full regularization path for the colon-cancer (n = 62, p = 2 000) and redrPrrdiii (n = 463 715, = 90) data sets, using either Hessian warm starts (7) or standard warm starts (the solution from the previous step).
3.3.3 General Loss Functions
We now venture beyond the standard lasso and consider loss functions of the form
1(3: X) = Σ ((TT3)
where fi is convex and twice differentiable. This, for instance, includes logistic, multinomial, and Poisson loss functions. For the strong rule and working set strategy, this extension does not make much of difference. With the Hessian screening rule, however, the situation different.
To see this, we start by noting that our method involving the Hessian is really a quadratic Taylor approximation of (I) around specific point 30- For loss functions of the type (8), this approximation is equal to
(03 = f(Bo: X) + Σ
1 ((88-8)0=at f" of (oTTB))(BBB))))) 3o) + 1
3o)
(.) Bo)
= (ū(x)) (0 (0(o, Bo)
1
x (w())) (o(1) X,3) + C(Bo);
where D(w(Su)) is a diagonal matrix with diagonal entries w(O)) where w(Bu); (x Bb) and ū(2); = f((x)/f( (z) - x Bo. whilst (3(b) is constant with respect to B.
Suppose that we are on the lasso path d and want to approximate c(>x+1). In this case, we simply replace f(3; in (1) with Q(3, ((A))), which leads to the following gradient approximation:
(((++1) c(Ax) (A+11 Av) X ((w) (X D(w) sign (B(A))au).
XAA where = (f(Ae)) Unfortunately, we cannot use Algorithm 1 to update X D This means that we are forced to either update the Hessian directly at each step, which can compu- tationally demanding when [Ax is large and inefficient when X is very sparse, to approximate

---

D(w) with an upper bound. In logistic regression, for instance, we can use 1/4 as such a bound, which also means that we once again can use Algorithm I.
In our experiments, we have employed the following heuristic to decide whether to use an up- per bound compute the full Hessian in these cases: we use full updates at each step if sparsity(X)) max n, p} < 10-3 and the upper bound otherwise.
3.3.4 Reducing the Impact of KKT Checks
The Hessian Screening Rule is heuristic, which means there may be violations. This necessitates that we verify the KKT conditions after having reached convergence for the screened set of predictors, and add predictors back into the working set for which these checks fail. When the screened set is small relative to p, the cost of optimization is often large part consumed by these checks. Running these checks for the full set of predictors always needs to be done once, but if there are violations during this step, then we need repeat this check, which best avoided. Here we describe two methods to tackle this issue.
We employ a procedure equivalent to the one used in Tibshirani et al. [10] for the working set strategy: we first check the KKT conditions for the set of predictors singled out by the strong rule and then, if there are no violations in that set, check the full set of predictors for violations. This works well because the strong rule is conservative-vvee vviolationssssss are rare which means that we seldom need to run the KKT checks for the entire set more than once.
If we, in spite of the augmentation of the rule, run into violations when checking the full set of predictors, that is, when the strong rule fails to capture the active set, then we still avoid repeating the full KKT check by relying on Gap Safe screening: after having run the KKT checks and have failed to converge, we screen the of predictors using the Gap Safe rule. Because this is safe rule, we can be sure that the predictors we discard will be inactive, which means that we will not need to include them in our upcoming KKT checks. Because Gap Safe screening and the KKT checks rely on exactly the same quantity-the correlation vector-we can do so at marginal extra cost. To see how this works, we now briefly introduce Gap Safe screening. For details, please see Fercoq, Gramfort, and Salmon [6].
For the ordinary lasso (fx-rauulriized least squares), the primal (1) is P(0) 2 XB13 + \| and the corresponding dual is
1 D(0) 2 11
X²
2
0
2
subject to ||xT S 1. The duality gap is then G(3,0) P(3) D(0) and the relation between
the primal and dual problems is given by y = X0 ~0+ XB, where Ô is the maximizer to the dual problem (9). In order to use Gap Safe screening, we need a feasible dual point, which can be obtained via dual point scaling, taking 0 (v / max (>, X X:3) lo=)). The Gap Safe screening rule then discards the jth feature if | 01 < 1- - | (G 0) Since we have computed xT(y- X3) as part of the KKT checks, we can perform Gap Safe screening at an additional (and marginal) cost amounting to On)) + O(p).
Since this augmentation benefits the working set strategy too, we adopt it in our implementation of this method as well. To avoid ambiguity. we call this version working+. Note that this makes the working set strategy quite similar to Blitz. In Appendix F.8 we show the benefit of adding this type of screening.
3.3.5 Final Algorithm
The Hessian screening method is presented in full in Algorithm 2 (Appendix B).
Lemma 3.4. Let 3 E RPxm be the output of Algorithm 2 for a path of length m and convergence threshold > O. For each step k along the path and corresponding solution ((k) E IR,, there is dual-feasible point (f0) such that G(B(k)
h g0kl < Çe.
Proof. First note that Gap safe screening [7, Theorem 6) ensures that G 2 As. Next, note that the algorithm guarantees that the working set. W. grows with each iteration until lay rl < d for all
7

---

j E G W, at which point
max (Ak, Wu XwwW))l(>) max (Ax, ||
At this iteration, convergence at line 2, for the subproblem (Xw, v), guarantees convergence for the full problem, (X, y), since
y Xwow (kk
((h)
max (Ais || Xw
is dual-feasible for the full problem.
3.3.6 Extensions
Approximate Homotopy In addition to improved screening and warm starts, the Hessian also allows us to construct the regularization path adaptively via approximate homotopy [19]. In brief, the Hessian screening rule allows to choose the next À along the path adaptively, in effect distributing the grid of As to better approach the exact (homotopy) solution for the lasso, avoiding the otherwise heuristic choice, which can be inappropriate for some data sets.
Elastic Net Our method can be extended the elastic net [20], which corresponds to adding quadratic penalty <|| /2/2 to (1). The Hessian now takes the form XTx A + Φz. Loosely speaking, the addition of this term makes the problem "more" quadratic, which turn improves both the
accuracy and stability of the screening and warm starts we use in our method. As far as we know, however, there is unfortunately way update the inverse of the Hessian efficiently in the case of the elastic net. More research in this area would be welcome.
Experiments
Throughout the following experiments, we scale and center predictors with the mean and uncorrected sample standard deviation respectively. For the lasso, also center the response vector, y, with the mean.
To construct the regularization path, we adopt the default settings from glmnet: we use log-spaced path 100 values from Amax to {Amax. where & = 10 p > n and 10-4 otherwise. We stop the path whenever the deviance ratio, dev bev//evvan dev reaches 0.999 or the fractional decrease in deviance is less than 10 Finally, we also stop the path whenever the number coefficients ever to be active predictors exceeds p.
We compare our method against working+ (the modified version of the working set strategy from Tibshirani et al. [10]), Celer [15], and Blitz [14]. We initially also ran our comparisons against EDPP [9], the Gap Safe rule [6], and Dynamic Sasvi [8] too, yet these methods performed so poorly that we omit the results in the main part of this work. The interested reader may nevertheless consult Appendix F66 where results from simulated data has been included for these methods too.
We use cyclical coordinate descent with shuffling and consider the model to converge when the duality gap G(B, 0) < EÇ. where we take Ç to be lgll2 when fitting the ordinary lasso, and log when fitting & rgrreguld logistic regression. Unless specified, we let e = 10 These settings are standard settings and, for instance, resemble the defaults used in Celer. For all of the experiments, we employ the line search algorithm used in Blitz!.
The code used in these experiments was, for every method, programmed in C++ using the Armadillo library [21, 22] and organized as an R package via Repp [23]. We used the renv package [24] to maintain dependencies. The source code, including a Singularity [25] container and its recipe for reproducing the results, are available at Additional details of the computational setup are provided in Appendix D.
com/ jomrsolars.o aolaa//aa/aooo MlessianScreening
'Without the line search, all of the tested methods ran into convergence issues, particularly for the high- correlation setting and logistic regression.
8

---

4.1 Simulated Data
Let X RExp, E TRP and y E IR be the predictor matrix, coefficient vector, and response respectively. We draw the rows of the predictor matrix independently and identically distributed from (0, 23 and generate the response from (X I) with o² = ,,, 2/3/SR, where SNR is the signal-to-noise ratio. We set s coefficients, equally spaced throughout the coefficient vector, to I and the to zero.
In our simulations, we consider two scenarios: a low-lowlnee -iwdemenniooall scenario and a high-dimn high-dimensional scenario. In the former, set 10000, dimensional scenario, we take n = 400, = 40 000, = 20, and set the SNR to These SNR values are inspired by the discussion in Hastie, Tibshirani, and Tibshirani [26] and intend to cover the middle-groumd in terms of signal strength. We run our simulations for 20 iterations.
100, 5, and the SNR to 1. In the high-
From Figure 3, it is clear that the Hessian screening rule performs best, taking the least time in every setting examined. The difference largest for the high-correlation context in the low-dimensional setting and otherwise roughly the same across levels of correlation.
The differences between the other methods are on average small, with the working+ strategy perform- ing slightly better in the > n scenario. Celer and Blitz perform largely on par with one another, although Celer sees an improvement in few of the experiments, for instance logistic regression when p n.
I SquareS
Least- Square
Logistic
Logistic
10000. 100
400, p 40000
n = 10000, p 100
n1 400, 40000
Hessian
Working
Time (relative)
Coler
2
0
0.4
0.8
0.4
0.8
0.4
0.8
0.4
0.8
Correlation (p)
Figure 3: Time to fit full regularization path for & t-regularized equstesquares and logistic regression to design with observations, predictors, and pairwise correlation between predictors of Time relative to the minimal mean time in each group. The error bars represent ordinary 95% confidence intervals around the mean.
4.2
Real Data
In this section, we conduct experiments real data sets. We run 20 iterations for the smaller data sets studied and three for the larger ones. For information on the sources of these data sets, please see Appendix E. For more detailed results of these experiments, please see Appendix F.5.
Starting with the case of f fi-reuulriieed least-squares regression, we observe that the Hessian screening rule performs best for all five data sets tested here (Table I), in all but one instance taking less than half the time compared to the runner-up, which each case the working+ strategy. The difference is particularly large for the YearPredictionMSD and e2006 tfidf data sets.
In the of ( riregulard logistic regression, the Hessian method again performs best for most of the examined data sets, for instance completing the regularization path for the madelon data set around five times faster than the working+ strategy. The exception the arcene data set, for which the working+ strategy performs best out of the four methods.
We have provided additional results related to the effectiveness of our method in Appendix F.

---

Table 1: Average time to fit full regularization path of f--regularized least-squares and logistic regression to real data sets, Density represents the fraction of non-zero entries X. Density and time values are rounded to two and three significant figures respectively.
Time (s)
Datu Set
n
P
Density
Loss
Hessian
Working
Blizz
Celer
beTCGA
536
17 322
1
Least Squaress
3.00
7.67
11.7
10.6
e2006-loglp
16.077
4272 227
1.4 x 10
Least-Squares
205
438
756
835
c2006-tfidf
087
150 360
8.3 10
Least-Squares
14.3
143
277
335
scheetz
120
18 975
1
Least- Least-Squares
0.369
0.6413
0.706
0.801
YeaPredicttinMSSD
403 715
90
1
Least-Squares
78.8
54.1
706
712
arceuc
100
10 000
5.4 10
Logistic
4.35
3.27
4.42
3.99
colon-cuncer
62
2000
1
Logistic
0.0542
0.134
0.177
0.169
duke breast cancer
44
7129
1
Logistic
0.111
0.210
0.251
0.262
ijenn
35 000
22
Logistic
0.939
5.53
4.68
3.50
madclon
2000
500
1
Logistic
48.2
232
240
247
new<20
19 19.996
1 1555 191
3.4
10
Logistic
1290
1620
2230
2170
revl
20 242
236
10
Logistic
132
378
5
Discussion
We have presented the Hessian Screening Rule: a new heuristic predictor screening rule for é1- regularized generalized linear models. We have shown that our screening rule offers large performance improvements over competing methods, both in simulated experiments but also in the majority of the real data sets that we study here. The improved performance the rule appears to come not only from improved effectiveness in screening, particularly in the high-correlation setting, but also from the much-improved warm starts, which enables our method to dominate the n > p setting. Note that although we have focused on & rereeulari least-squares and logistic regression here, rule is applicable to any composite objective for which the differentiable part is diffeeeiffer......e...
One limitation of our method is that it consumes more memory than its competitors owing to the storage of the Hessian and its inverse. This cost may become prohibitive for cases when min(n. p} is large. In these situations the next-best choice may instead be the working set strategy. Note also that we, in this paper, focus entirely on the lasso path. The Hessian Screening Rule is a sequential rule and may therefore not prove optimal when solving for a single X, in which case a dynamic strategy such as Celer and Blitz likely performs better.
With respect to the relative performance of the working set strategy, Celer, and Blitz, we note that our results deviate somewhat from previous comparisons [15, 14]. We speculate that these differences might arise from the fact that we have used equivalent implementations for all of the methods and from the modification that we have used for the working set strategy.
Many avenues remain to be explored in the context of Hessian-baased screening rules and algorithms, such developing more efficient methods for updating of the Hessian matrix for non-least-squares objectives, such as logistic regression and using second-order information to further improve the optimization method used. Other interesting directions also include adapting the rules to more complicated regularization problems, such as the fused lasso [27], SLOPE [28]. SCAD [29], and MCP [30]. Although the latter two of these are non-convex problems, they are locally convex for intervals of the regularization path [31]. which enables the use of our method. Adapting the method for use in batch stochastic gradient descent would also be interesting topic for further study, for
instance by using methods such as the ones outlined in Asar et al. [32] to ensure that the Hessian remains positive definite.
Finally, we do not expect there to be any negative societal consequences of our work given that is aimed solely at improving the performance of an optimization method.
Acknowledgments and Disclosure of Funding
We would like to thank Malgorzata Bogdan for valuable comments. This work was funded by the Swedish Research Council through grant agreement no. 2020-05081 and no. 2018-01726. The computations were enabled by resources provided by LUNARC. The results shown here are in part based upon data generated by the TCGA Research Network: https http://wwccccccc www.:/ccccr..ooottggeeeeee
10

---

References
[1] Robert Tibshirani. "Regression Shrinkage and Selection via the Lasso". In: Journal of the Royal Statistical Society: Series B (Methodological) 58.1 (1996), pp. 267-288, ISSN: 0035-9246.
JSTOR: 2346178.
[2] Laurent El Ghaoui, Vivian Viallon, and Tarek Rabbani. Safe Feature Elimination in Sparse Supervised Learning. UCB/EECS-20104 126. Berkeley: EECS Department, University of California, Sept. 21, 2010.
[3] Zhen J. Xiang, Hao Xu, and Peter J Ramadge. "Learning Sparse Representations of High Di- mensional Data on Large Scale Dictionaries". In: Advances in Neurul Information Processing Systems 24. Neural Information Processing Systems 2011. Ed. by J. Shawe- Taylor et al. Curran Associates, Inc., Dec. 12-17, 2011. pp. 900-908.
[4] Zhen James Xiang and Peter J. Ramadge. "Fast Lasso Screening Tests Based on Correlations". In: 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). 1109/ICASSI IIASSP 2012. 6288334.
Mar. 2012, pp. 2137-2140. DOI: 1109
[5] Jie Wang et al. "A Safe Screening Rule for Sparse Logistic Regression". In: Proceedings of the 27th International Conference Neural Information Processing Systems Volume 1. NIPS 14. Cambridge, MA, USA: MIT Press, Dec. 8, 2014, pp. 1053-1061.
[6] Olivier Fercoq, Alexandre Gramfort, and Joseph Salmon. "Mind the Duality Gap: Safer Rules for the Lasso". In: Proceedings of the 37th International Conference Machine Learning. ICML 2015. Ed. by Francis Bach and David Blei. Vol. 37. Proceedings of Machine Learning Research. Lille, France: PMLR, July 6- 2015, pp. 333-342.
[7] Eugene Ndiaye et al. "Gap Safe Screening Rules for Sparsity Enforcing Penalties". In: Journal
of Machine Leurning Research 18. 128 (2017), pp- 1-33.
[8] Hiroaki Yamada and Makoto Yamada. "Dynamic Sasvi: Strong Safe Screening for Norm- Regularized Least Squares". . In: Advances in Neural Information Processing Systems. NeurIPS 2021. Ed. by M. Ranzato et al. Vol. 34. New Orleans, USA: Curran Associates, Inc., 2021, pp. 14645-14655.
[9] Jie Wang, Peter Wonka, and Jieping Ye. "Lasso Screening Rules via Dual Polytope Projection". In: Journal of Machine Learning Research 16.1 (May 15, 2015), pp. 1063-1101. ISSN: 1532- 4435.
[10] Robert Tibshirani al. "Strong Rules for Discarding Predictors in Lasso- Type Problems". In: Journal of the Royal Statistical Society. Series B: Statistical Methodology 74.2 (Mar. 2012),
pp. 245-266. ISSN: 1369-7412. DOT: 10/c4bb85,
[11] Jianqing Fan and Jinchi Lv. "Sure Independence Screening for Ultrahigh Dimensional Feature Space". In: Journal of the Royal Staristical Society: Series B (Statistical Methodology) 70.5 (2008), pp. 849-911, ISSN: 1467-9868, DOr: 10. 1111/j 1467 2008. 00674.
[12] Talal Ahmed and Waheed U. Bajwa. "ExSIS: Extended Sure Independence Screening for Ettrahigh-Dimensinne
Linear Models". In: Signal Processing 159 (June 1, 2019), pp. 33-48.
ISSN: 0164- DOI: 10. 1016/j- si sigpro 2019. 018.18.
[13] Yaohui Zeng, Tianbao Yang. and Patrick Breheny. "Hybrid Safe-Strong Rules for Efficient Optimization Type Problems". In: Computational Statistics & Data Analysis 153
(Jan. 1, 2021), 107063. ISSN: 0167-9473. DOI: 10. 1016/j csda. 2020 107063.
[14] Tyler B Johnson and Carlos Guestrin. "Blitz: A Principled Meta-Algorithm for Scaling Sparse Optimization". In: Proceedings of the 32nd International Conference on Machine Learning. International Conference on Machine Learning. Vol. 37. Lille, France: JMLR: W&CP 2015,
p. 9.
[15] Mathurin Massias, Alexandre Gramfort, and Joseph Salmon. "Celer: A Fast Solver for the Lasso with Dual Extrapolation". In: Proceedings of the 35th International Conference on Machine Learning. ICML 2018 Ed. by Jennifer Dy and Andreas Krause. Vol. 80. Proceedings of Machine Learning Research. Stockholm, Sweden: PMLR, July 10-15, 2018, pp. 3315-3324. Annals of Statistics 32.2 (Apr. 2004), pp. 407-499. ISSN: 0090-5364. DOI: 10. 02140000003040000000000000000000
[16] Bradley Efron et al. "Least Angle Regression".
[17] James H. Goodnight. "A Tutorial the SWEEP Operator". In: The American Statistician DOI: 10. 2307 22683225. JSTOR: 2683825.
33.3 (1979), pp. 158. ISSN: 0000-1005

---

[18] Mee Young Park and Trevor Hastie. "LI- "LI-Regularization Path Algorithm for Generalized Linear Models". In: Journal of the Royal Statistical Society. Series (Statistical Methodology) 69.4 (2007), pp. 657-677. ISSN: 1369-7412. DOT: 10. 1111/j 1447799888 2007 00607 x. [19] Julien Mairal and Bin Yu. "Complexity Analysis of the Lasso Regularization Path". In: Pro- ceedings of the 29th International Conference on Machine Learning. International Conference Machine Learning 2012. Edinburgh, United Kingdom, June 2012, pp. 1835-1842.
[20] Hui Zou and Trevor Hastie. "Regularization and Variable Selection via the Elastic Net". In: Journal of the Royal Statistical Society. Series B (Statistical Methodology) 67.2 (2005), pp. 301-320. ISSN: 1369-7412.
[21] Dirk Eddelbuettel and Conrad Sanderson. "RoppArmadiloo; Accelerating R with High- Performance C++ Linear Algebra". In: Computational Statistics and Data Analysis 71 (Mar. 2014), pp. 1054-1063.
[22] Conrad Sanderson and Ryan Curtin. "Armadillo: A Template-Bane Based C++ Library for Linear Algebra". In: The Journal of Open Source Software 1.2 (2016), p. 26. DO1: 10. 201001/ss/os 00026.
[23] Dirk Eddelbuettel and Romain François. "Repp: Seamless R and C++ Integration". In: Journal of Statistical Software 40.8 (2011), pp. 1-18. DOI: 10/ gc3gqm.
[24]
Kevin Ushey. Renv: Project Environments. Version 0.13.2 R Studio, 2021.
[25]
Gregory M. Kurtzer, Vanessa Sochat, and Michael W. Bauer. "Singularity: Scientific Containers for Mobility of Compute". In: PLOS ONE 12.5 (May 11, 2017). c0177459. ISSN: 1932-6203.
DOI: 10. / /177/joounal. ournal pone. 0177459.
[26] Trevor Hastie, Robert Tibshirani, and Ryan Tibshirani. "Best Subset, Forward Stepwise or Lasso? Analysis and Recommendations Based on Extensive Comparisons". In: Statistical Science 35.4 (Nov. 2020). pp. 579 19999599.110 ISSN: 0883-4237. DOI: 10. 1014/19- STS733..
[27] Robert Tibshirani et al. "Sparsity and Smoothness via the Fused Lasso". In: Journal of the Royal Statistical Society: Series B (Statistical Methodology) 67.1 (2005), pp. 91-108. ISSN: 2005. 00490.44.....
1467-9868. DOT: 10 1 1111/j
[28] Malgorzata Bogdan et al. "SLOPE Adaptive Variable Selection via Convex Optimization". In: The annals of applied statistics 9.3 (Sept. 2015), pp. 1103-1140. ISSN: 1932-6157. DOI:
10. 1214/15-A0AS842. pmid: 26709357.
[29] Jianqing Fan and Runze Li. "Variable Selection via Nonconcave Penalized Likelihood and Its Oracle Properties". In: Journal of the American Statistical Association 96.456 (Dec. 1, 2001),
pp. 1348-188 1360. ISSN: 0162-1459 DOI: 10/fd7bfs.
[30]
Cun-Hui Zhang. "Nearly Unbiased Variable Selection under Minimax Concave Penalty". In: The Annals of Statistics 38.2 (Apr. 2010), pp. 894-942. ISSN: 0090-5364, 2168-8966. DOI: 10/bp22zz.
[31] Patrick Breheny and Jian Huang. "Coordinate Descent Algorithms for Nonconvex Penalized Regression, with Applications to Biological Feature Selection". In: The Annals of Applied
Statistics 5.1 (Mar. 2011), pp. 232-253. ISSN: 1932-6157, 1941-7330. DOL: 10. 10-4/10- AOAS388.
[32] Özgür Asar et "Linear Mixed Effects Models for Non-Gaussian Continuous Repeated Measurement Data". In: Journal of the Royal Statistical Society: Series C (Applied Statistics) 69.5 (Sept. 9, 2020), pp. 1015-1065. ISSN: 1467-9876. DOI: 10.1111/rsse 12405.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 5
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section 5.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
12

---

(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proof' of all theoretical results? [Yes] See the supplementary material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] See Section (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section as well as the supplementary details and the references to
existing data sets for discussions on test and training splits.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (c.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? (Ys]] See the supplement and Section
(b) Did you mention the license of the assets? [Ys] A LICENSE. md file has been included along with the code.
(c) Did you include any new assets either the supplemental material as URL? [Yes] See Section 4.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] All data we used has been made available in the public domain. (e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] To the best of knowledge, it does not.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] Not applicable our work.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] Not applicable
work. (c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A] Not applicable to our work.
13


Reviews:
[{"review_id": "e15zwWDReZl", "reviewer": "Reviewer_B3d7", "summary": "The paper proposes a heuristic (non-safe) screening rule to deal with l1-regularized estimation problems such as linear regression and logistic regression. The proposed method can be viewed as a generalization of the strong rule used in the glmnet, which only used first-order information.  The paper reports experiments on both synthetic data and real-world data to illustrate the performance of the proposed method.", "questions": "I don't have additional questions for the authors.", "limitations": "Limitations are discussed in the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* the paper addresses an interesting problem in l1-regularized estimation for linear regression and logistic regression. Screening rules are an effective strategy to speed up such estimation.\n* Although the proposed rule is heuristic in nature, the simplicity in its formulation and the effectiveness shown in the experiments offers some advantages of the proposed method. This is also a not-so-common approach that makes use of second-order information for screening.\n* Experiments are exhaustive. six well-known alternative methods are compared on a wide variety of synthetic and real-world data.\n\nWeakness:\n* The authors may consider carrying out experiments on other settings covered by the proposed method such as poison regression and elastic net. It may also be interesting (somewhat orthgonal) to understand how the proposed method performs or scale compared to SGD based approach on very large datasets.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_sUje9-rjZH", "reviewer": "Reviewer_cyeA", "summary": "The paper proposes a screening strategy for L1 sparse modelings. The basic idea is to use a prediction of an optimal solution as a function of the regularization parameter, derived from optimal conditions (which is aka solution path). The authors further propose combining working set selection screening by predicted solution with so-called strong rule to make screening more efficient. ", "questions": "Convergence to the optimal solution is not mentioned. Could you give any information about the optimality of solution in a sense of the KKT conditions of (1)?", "limitations": "In Section 5, limitations were discussed.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, the paper is easy to follow and technical quality is fine. The purpose is clear and the procedure is written in detail. However, a critical issue is that the idea of main proposal (Hessian screening) is not novel. Approaches based on a similar idea have been studies in the context of the path following though it is not fully mentioned. Detailed comments are as follows.\n\nClosely related papers in the path following literature are missed. For example, since the following two papers contains conceptually quite similar approaches, the difference should have been discussed in detail, though currently nothing is mentioned:\n[Rosset2004] S. Rosset, Following Curved Regularized Optimization Solution Paths, NeurIPS 2004. \n[Park2006] M. Y. Park and T. Hastie, L1 Regularization Path Algorithm for Generalized Linear Models, Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2006.\n\nThe proposed algorithm can be seen as a so-called 'predictor-corrector' method in general (e.g., discussed in [Park2006]). Further, [Park2006] also discusses the working set selection based on the update equation (6).\n\nTherefore, most importantly, the idea using Theorem 3.1 to predict the variable c (working set criterion) of the next \\lambda has been already known. Therefore, I do not think the concept of 'Hessian screening' is novel.\n\n[Rosset2004] also discusses a similar idea of approach (Hessian based update) based on an essentially quite similar theoretical property to Theorem 3.1. Further, this paper also provides the error analysis of the predictor.\n\nCombination with strong rule and additional adjustment would be novel, but its technical significance is a bit marginal because these are quite simple heuristics.\n\nTechniques in the 'Updating the Hessian' paragraph have been also known (the same techniques repeatedly discussed in the path following literature). \n\nThe 'Warm Starts' has also been widely known (e.g., [Park2006]).\n\nMinor comments:\n- Since Theorem 3.1 has been widely known, it should clarify more explicitly rather than noting it only in the footnote.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Lj7Pm_uKE82", "reviewer": "Reviewer_ERSS", "summary": "This paper studies the predictor screening rules over the lasso optimization problem. It proposes a Hessian screening rule which utilizes the second-order information. This rule is effective not only in screening but also in accurate warm starts. Updating the second-order information has high computational complexity, and to deal with it, this work replies on the sweep operator. In the experiments, the proposed rule is compared to many baselines and outperforms them significantly on both simulated and real-world data.\n\n", "questions": "See the concerns in the above section.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality\n\nPrevious works on screening rules overlooked the study on the second-order information. Thus I think the direction of this work novel. The proposed rule takes the warm start and the Hessian matrix computation problems into account, and resolves them soundly. Besides, the insightful discussions on the proposed screening rule are provided. They are helpful to understand the rule and to differentiate this approach with previous methods. Therefore, I think the contributions of the work novel.\n\nQuality\n\nI am satisfactory with most contents of this paper. The paper presents a clear overview of the question and previous rules both in words and math. The proposed rule is based on the Hessian matrix and is actually in a form of the second-order Taylor approximation. Speeding up the Hessian matrix computation is based on the sweep operator and the warm starts also benefit from the Hessian matrix. These arguments are demonstrated in the experiments. As far as I checked, the theoretical analyses have no problem.\n\nHowever, I have a concern with the study method. Normally, people select the predictors for better fitting accuracy, but this paper relies heavily on the time cost and the minimum number of active predictors to measure the performance. I am curious about why not including fitting accuracy.\n \nClarity\n\nThe paper is clearly written for me. I can easily follow the contents on the approach and the experiment.\n\nSignificance\n\nThe idea of the approach is sound and practical performance is better than baselines. However, because just the lasso problem is involved, I am afraid that the audience will be very limited. Therefore, I think the significance of this paper is limited.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9q1ahq_JQMk", "reviewer": "Reviewer_ovwH", "summary": "A Hessian screening rule for lasso and its generalized linear model extension for logistic regression was presented to take advantage of the high-order information for more efficient screening, specifically in cases with highly correlated predictors/covariates. The proposed Hessian screening rule together with several speedup tricks has been shown to be effective in both simulated and real datasets. ", "questions": "1. Are there any theoretical guarantee that the Hessian rule will be always less conservative than the Strong rule or Working Set method? \n\n2. How the corresponding prediction accuracy of the resulting models by different screening rules? Are the final \"screened\" predictors all the same as the ones from the optimal solution from the model fitting without screening? \n\n3. There are multiple screening rules published more recently, including: https://proceedings.neurips.cc/paper/2020/hash/11348e03e23b137d55d94464250a67a2-Abstract.html, how does the Hessian screening rule compare with these new rules? ", "limitations": "N/A.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The proposed Hessian screening rule extends the Strong Rule and Working Set by taking advantage of the high-order information for more efficient screening, specifically in cases with highly correlated predictors/covariates. The Hessian screening rule together with several speedup tricks has been shown to be effective in both simulated and real datasets. \n\nIt is not clear based on the current presentation why the Hessian rule can be less conservation from Section 3. In addition to Theorem 3.1, some theoretical analysis for that may help further improve the quality of the submission. The actual final screening in fact was based on the modifications as described from line 133 to 151. It may be interesting also to have ablation comparison to see clearly what led to improved efficiency. \n\nSince, the screening rules are not \"safe\", in particular for logistic regression. In addition to investigating the efficiency, the authors may also need to provide the performance comparison with respect to both predictor selection and model prediction accuracy. \n\nIn the real data experiments, the authors may want to provide some explanations why the Hessian rule performs significantly worse on arcene and rcv2 datasets, for which p is much larger than n, especially for arcene. It is clearly not the case when p is similar as n as discussed in Section 5. \n\nFinally, there are language problems in the submission. For example, in line 188-189 (page 5): \"... this is not a surprising find.\"  In line 257-258 (page 7), \"we also stop the path whenever the number of coefficients ever to be active predictors exceeds p.\" The number of coefficients can be equal to p but will never exceed p. The authors may need to improve the presentation of the submission. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept