Dynamic Sasvi: Strong Safe Screening for Norm-Regularized Least Squares
Authors: Hiroaki Yamada
Makoto Yamada
Venue: NeurIPS 2021 Poster (2021)
Keywords: convex optimization
Lasso
safe screening

Abstract: A recently introduced technique, called ``safe screening,'' for a sparse optimization problem allows us to identify irrelevant variables in the early stages of optimization. In this paper, we first propose a flexible framework for safe screening based on the Fenchel--Rockafellar duality and then derive a strong safe screening rule for norm-regularized least squares using the proposed framework. We refer to the proposed screening rule for norm-regularized least squares as ``dynamic Sasvi'' because it can be interpreted as a generalization of Sasvi. Unlike the original Sasvi, it does not require the exact solution of a more strongly regularized problem; hence, it works safely in practice. We show that our screening rule always eliminates more features compared with the existing state-of-the-art methods.


Dynamic Sasvi: Strong Safe Screening for Norn-Regularized Least Squares
Hiroaki Yamada
Makoto Yamada Kyoto University and RIKEN AIP
Kyoto University
hyamada@ml ist. k.oto-u.aco jp
Abstract
A recently introduced technique, called "safe screening." for sparse optimization problem allows to identify irrelevant variables in the early stages of optimization. In this paper, we first propose a flexible framework for safe screening based on the Fennhhl--Rocafeellar duality and then derive a strong safe screening rule for norm-regularized least squares using the proposed framework. We refer to the proposed screening rule for norm-regularized least squares as "dynamic Sasvi" because it can be interpreted as generalization of Sasvi. Unlike the original Sasvi, it does not require the exact solution more strongly regularized problem; hence, it works safely in practice. We show that our screening rule always eliminates more features compared with the existing state-of-the-a methods.
Introduction
Sparse models such as Lasso [23 and group Lasso [26] have been widely studied in the areas of statistics and machine learning and used for various applications such as compressed sensing [6] and biomarker discovery [4]. Although sparse models can be formulated as a simple convex optimization problem, the computational cost can be large if the numbers of samples and dimensions are extremely
large.
To address this problem, technique called safe screening has been introduced 10 for Lasso problems. Specifically, eliminates variables that are guaranteed be zero in the Lasso solution before solving the original Lasso optimization problem. Many safe screening methods have been proposed for various problems [0 because they require the solution
19 24 I4 25). These are called sequential screening rules more strongly regularized problem. A recent technique, called dynamic screening, has been proposed to eliminate variables through an estimated solution in an iterative solver (3]. In particular, Gap Safe [7] dynamic screening framework, is widely used owing to its generality and efficiency I17 21 18).
In this paper, we propose dynamic safe screening algorithm that is stronger than Gap Safe for the Lasso-Like problem, which includes norm-regularized least squares. To this end, we first propose general screening framework based on the Sasví, a strong safe screening rule for Lasso-like problems. Our framework can regarded as generalization of the Gap Safe framework, and thus, we can derive Gap Safe simply using our results. Moreover, owing to this generalization, we can use the strong problem adaptive inequality. The derived screening rule for Lasso-like problems can be seen dynamic variant of safe screening with variational inequalities (Sasvi) [14), which is a sequential screening rule for Lasso. Therefore, refer this Dynamic Sasvi. Unlike the original Sasvi. dynamic Sasvi does not require exact solution to the problem with another hyper-parameter and, hence, operates safely in practice. Moreover, propose the use of dynamic enhanced dual polytope projection (EDPP) (24) which is a relaxation of dynamic Sasvi due to the introduction of a minimum radius sphere. We show, both
duality and then derive Dynamic
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

theoretically and experimentally, that the screening power and computational costs of Dynamic Sasvi and Dynamic EDPP compare favorably with those of other state-of-the ttt-hhhartt arr Gap Safe methods.
Contribution: The contributions our study are summarized as follows.
We propose flexible screening framework based on the is generalization of the Gap Safe framework [T7]
duality, which
We propose two novel dynamic screening rules for norm-regularized least squares: dynamic variant of Sasvi [4] and a dynamic variant EDPP.
We show that Dynamic Sasvi always eliminates more features and increases the speed of the solver compared with Gap Safe 7 17
Preliminary
In this section, we first formulate the problem and introduce the key techniques used in this study.
2.1 Notation
Given h R - 1o00, xo]. the domain of h is defined by (h) = (= E 1 [h(2)] < oo) and
h : R + [-o0, so]. which is the Fenchel conjugate of h, is defined as h (v) = Su1pzeR" v h(2). If h is proper, the Fenchel-Young Young inequality,
h(2) + h (v) 2 2.
can be proven directly based on definition of the Fenchel conjugate. The subdifferential of proper function, h Ih' + (-00, 20), at is given as
0h(z) {v 1 Yw R v v (w 2) + h(2) h(w)).
The next proposition is important for deriving safe-screening algorithms.
Proposition 1 Assume that h R. + (-o0, oc] is proper lower semi-continuou foncttiuuctinn and z, v Th We then have
0h(22)
h(z) h-" (v) TT + E ah"
See Section 16 of 2 for the proof. For convex set C C R,,,, the relative interior of C' defined as relint(C) = (u E C Vw 3c s.t. c(v w) E C).
2.2 Problem Formulation
In this study, we consider an optimization problem, formulated as
minimize ((X,3) + g(B),
(2)
BER
where 3 E Rdd the optimization variable, X nn xd is constant matrix, and f RR + (-00, 2o and g Rdd (-oc, co] are proper lower semi-continuous convex functions. We assume
30 relint(donni (dom(g)) s.t. X33 E relint(dom(
and the existence of the optimal point, i.c.,
33 dom (P) s.t. P( inf P(B), BERd
where P d - R is defined as P(B) f(X + ((3). Moreover, we focus on the cases in which y induces sparsity. Although all theorems in this paper hold, we cannot eliminate any variables without sparsity.
This is popular class of optimization problem, with the most popular example being Lasso 23
minimize BERd
5 X A|||111-
Many extensions of Lasso, including Group-Lasso (26]. elastic net [27] and sparse logistic regression [5]. are in this class. The dual problems of a support vector machine [5] and support vector regression [22 are also in this class.

---

2.3 Dual Problem
In the derivation of a safe screening rule for the optimization problem, Eq. 2). the Fenchel- Rockafellar dual formulation, plays important role.
Theorem Bunnchel-Rocafellie Duality) all assumptions for the optimization problem 2 are satisfied, have the following:
min ((x3) + g(3)) BER
max
OER"
The proof of Theorem is provided in the appendix. denote (- - g" 0) by D(O).
(xTT)
For primal/dual solutions, there are many conditions that are equivalent optimality. Herein, we provide a list of such conditions for convenience.
Proposition 3 (Optimal Condition) If all assumptions for the optimization problem 2 are satisfied, the following are equivalent.
(a) 3 argmin seRd P(B) A argmaX DER" D(0)
(b) P(B) = D(0)
(c) + - X33 = -9(33) 9" (x
(d) 0 (x(3 ^ x 0g((3)
(e) X3 0f ^ 0g* 0)
(Proof) (a) = (b) is directly derived from the strong duality. (b) < (c) is derived from the Youuh inequality T (c) (d) =
(e) are derived from Proposition
2.4 Relationship of Dual Safe Region and Screening
For the optimization problem 2 we can eliminate some features by constructing a simple region that contains Ó. Assume that the dual optimal point, Ô, is within region R. According to Proposition we have
BE 0g c U 0g' (x 0).
BER
Hence, if UPER (X following corollary.
() (@ B, holds, obtain B A simple example is the
Example 4 Consider an optimization problem, i.e., Eq. with g( || Assume that E R. Then, we have
x. 0
3 0.
(Proof) Based on the definition of g. we have Og" (X (XTO)
0) C (3 13= 0] + a 0 < 1. When
maxøeR [e_] 0 1,, we have 3 USER Og*
(X (X
(3 B; = 03.
To eliminate features safely, we should first construct a simple region and then determine whether UøgR (x 0)) c {G E Rd 33 0) is guaranteed. In this study, we provide novel general framework for constructing simple safe region, R C R". By combining it with existing methods to calculate an upper bound of UPeR Ox 0) (cf. [17 for the un-overlapping group III norm and sparse group norm, for ordered weighted norm), can formulate strong safe screening rules.
R" which contains

---

General Framework for Constructing Safe Region
Herein, we propose a general framework for constructing a dual region that contains the solution to the optimization problem expressed by Eq. 33.. Our framework consists of general lower bound and problem-adaptive upper bound of the optimal value. Hence, we can derive a narrower region than the framework with general upper bound under certain situations.
The general lower-bound derived from the optimal condition and the L-strong convexity. Assume that f I-strongly convex (I. 0). Then, as I-strongly concave and 0 is the optimal point, have D(0) = (00)
1 =10 2 for 40 R". Thus, we have
L - 0 011 D(0) & D(0)).
① e (
Because this region is too complicated for screening, we use simple upper bound of D(0) to construct simple safe region.
Theorem Consider the optimization problem expressed by Eq. 3 and assume that f is L-strongly convex (L 2 0). Let 0 be the solution to Eq. B Assume that D(0) is upper-bounded by u(O), i.e.
4O E R D(0) S u()). Then, for v0 E R", we have
0 E R(0, u) = 1 11 000 +12+ u())).
The complexity RR@ u) depends on the complexity of For example, if u linear, then R(0, u) is a sphere. We can construct narrow, simple, and safe region with a tight simple upper-bound In can be derived easily from this theorem and weak duality.
fact, the Gap Safe Sphere region
Corollary (Gap Safe Sphere) Consider the optimization problem described by Eq. 3 and assume that f is L-strongly convex (L 2 0). Let the solution to Eq. 33 For vB E Rd and v0 E IR", we have
T. i E (0
0
01
D(0) = P(β)).
(Proof) Based weak duality, have ve D(0) < P(š). Using this constant function as upper bound in Theorem 5 we can derive the corollary directly.
Hence, our framework can be seen as generalization of Gap Safe. Owing to this generalization, we can use stronger problem-adaptive upper bound rather than a weak duality. In the next section, we derive specific regions for the Lasso-Like problem. Some regions for other problems are presented in the appendix.
Safe Region for Lasso-like Problem
In this section, we introduce a strong upper bound for the dual problems of Lasso and similar problems. The dome region derived from it can be seen generalization of Sasvi [14] and is narrower than Gap Safe region.
4.1 Norm-regularized Least Squares Problem and its Generalization
Norm-regularized least squares is optimization problem and is formulated as 1 x + o(3) where g is norm. This is a subset of problem 2 AI-
minimize
3ER4
though this formulation includes Lasso [23], (overlapping) group-Lasso (26 12). and ordered weighted LI regression [ the non-negative Lasso is not included. To unify them, we define the
Lasso-like problem as follows:
minimize BERd
2 l x,3133 + g(9),
(4)

---

where the problem satisfies all assumptions for Eq. and satisfies
Va 2 0, 3 E R ( = ag(
(5)
For the Lasso-like problem, the Fenchel conjugate functions of f and g are given
(--0)= - - y
(vB 0 X ( -
9 g"(x
(6)
oo
(33 e X3 g > 0).
(x 0) 0} is closed convex set. Hence, the Lasso-like problem is class of problems whose Senchei-Rockafelle dual can be seen as a convex projection.
Note that (0)
4.2 Proposed Dome Region for Lasso-like Problem
Using Theorem 5 we can construct a safe region by proposing an upper bound, u(O). In this section, we propose a tight upper bound for Lasso-like problems. The direct expression of f in Eq. ( is sufficiently simple. We only need an upper bound of -g" to construct simple region. The upper bound is given follows.
Lemma For Lasso-like problems for v/3 E Rdd and 40 E IR", we have
(f (g( x3 20) 0)
D(0)= v (- + inf g(aB) - 0 (TTx(a3) = 100 (g( 0 x <0) 0).
(7)
e20
The proof of Lemma 7 given in the appendix. Using the right-hand side of Eq. 7 as an upper bound of D, we can construct simple and safe region.
Theorem 8 Consider the Lasso-like problem described by Eq. (4) and its Fenchel-Rockafeee Rockafellar dual problem presented in Eq. (3). Let 0 be the dual optimal point. We assume that 3 Rd and E dom D). Then, θ is within the Dynamic Sasvi region, which is given as the intersection of sphere and a half space:
DS (0,0) (0,0):=10
[0
0 0 + D(0) < (- A ( ((3) 00 X(3)
2
=(0 (y (0- 0) < 5000 ( 0- 0x3...
The proof of Theorem is given in the appendix. As proven in section 4.5 R RDS R 0*) converges to {0) when lim P( D(0 = O. When we have good primal/dual feasible points, we can derive very narrow safe region and eliminate almost all irrelevant features.
4.3 Relation to Sasvi
In this section, we show that safe screening with variational incquality (Sasvi) 14 is a special case of our screening rule. First, we review Sasvi. The target task of Sasvi is to minimize x y x x ||ا||| with many λs. Sasvi is called "sequential" screening because it is designed to solve sequence of problems with sequence of penalty parameters, A X the optimal points of the primal problem and its Fenchel-Rockafeee Because the dual problem can be interpreted as a projection from X "y closed convex set, Il < 1). the following two variational inequalities hold:
AM- Let ( and 0 (2) be dual problem, respectively.
(0 g.
||
0 z (A2 ly - (a))) (A1)
((2)))
> (A11'1 - @Dhi))
(0 g(vu))
(8)
Given 9 (a:) these inequalities provide a safe region for (Aa) Sasvi finds some zero elements of (Aa) based on this region. Note that - (A11) = x²²(a1)
-1 -'y and (2.)T x²( = 9 g(
are derived from Proposition 3 Then, we have
(A1 -1 ((r)) (0
x (10)
g((())))
5

---

(a) Regions of dynamic Sasvi (dark green) and dynamic EDPP (light green).
(b) Regions of dynamic Sasvi (green), Gap Safe Sphere (light red) and Gap Safe Dome (dark red).
(c) Regions of dynamic EDPP (green), Gap Safe Sphere (light red), Gap Safe Dome (dark red).
Figure 1: Comparisons of various safe regions for Lasso. The blue region represents the feasible region.
Because X2 12-110 in Eq. () corresponds to y in Theorem RDS (3 (3( O ((an)) is equal to the Sasvi region. Hence, we can state that our method is generalization of Sasvi. Our method requires primal/dual feasible points, unlike the original Sasvi, which requires the dual optimal point of problem with another parameter. Such screening rules are called "dynamic" because they dynamically provide safe regions as iterative optimization proceeds. For this reason, we have labeled as "Dynamic Sasvi." Owing to its "dynamic" property. Dynamic Sasvi eliminates almost all irrelevant features in the late step of the iterative optimization. As reported in 77]. some sequential safe screening rules, including Sasvi, not safe in practice because we cannot provide exact solution for A1- Dynamic Sasvi overcomes this problem because does not require the solution problem with another parameter.
4.4 Comparison to Gap Safe
Here, we show that the proposed method is stronger than Gap Safe Dome and Gap Safe Sphere 77] [17] for Lasso-like problems. As shown in [7], for Lasso, the regions of the Gap Safe Dome and sphere and the contra of another sphere:
Gap Safe Sphere are the relaxation the intersection
(0 (y 0) (Ø 0) = の - P(3)).
where 33 and 0 are primal/dual feasible vectors, respectively. (y - 0) (0 - 0) < 0 is the variational inequality, and f < P(B) is derived from weak duality. Using simple transformation, have
1 X 0 )( 0 x²a.
()) S P( =
01 To 0
< y
x +(())
1
2
Hence, we have 0 S -
0 x x
= (f) < P(3). This means that the region of
dynamic Sasvi subset of the region of Gap Safe Dome. Our screening always stronger than Gap Safe Dome and Gap Safe Sphere. Figure shows the regions of Dynamic Sasvi, Gap Safe Dome, and Gap Safe Sphere.
4.5 Sphere Relaxation (Dynamic EDPP)
In some situations, a dome region is too complicated calculate UPER 0x* T). For such cases, we propose using a minimum radius sphere that includes the dynamic Sasvi region. This method can be seen dynamic variant of the EDPP 24 because the EDPP is the minimum radius sphere relaxation of Sasvi.
Theorem Consider the Lasso-like problem presented in Eq. 4 and its Benchel-Rockaeer dual We assume that B3 Rdd and dom(DD. If 2 2, the minimum radius sphere
problem in Eq.
33.
including R DS
(B, 0) is
R DE (3,0) (0
0
1 0 2
4)
xx 31| - v12 a² -11x811))
2

---

Algorithm Coordinate descent with Dynamic Sasvi for Lasso
Input: X, ,9. T,
2: Initialize 3+ + 3 A - [d]
3: for E [T] do
4: i mod c = 1 then
5: Compute 0 = 0
6: if P(3) D(0) | then
7: break
8:
end if
9:
R + RD 0)
10:
A [j E A: maxØER [z] 0 2 1}
11:
for j E [d] do
12:
B 0 end for
13:
14:
end if'
for j E do
u- 3 | 12 23 (X3 y)
17:
B + 1 sign( u) max(0, [n] 1)
18:
end for
19:
end for Output:
20:
where
a max 00.113116 -2 (- + y) x - g((3)
The proof of Theorem is provided in the appendix. Figures Ia and Ic show the dynamic EDPP region and other regions. To compare the Dynamic EDPP region and the Gap Safe Sphere region in general, we present the next theorem.
Theorem 10 Let r be the radius of R (B, 0). We then have
P()) D(0).
The proof is given in the appendix. Because the radius of the Gap Safe Sphere region is ((( D()),, the squared radius of the Dynamic EDPP region is always less than half that of Gap Safe Sphere. Furthermore, Theorem 10 shows that (B 0%) and RS (B3., @h) converge (0) when lim P( D(0*) O.
Implementation for Lasso
In this section, we provide specific solver based on Theorem g Because the algorithm used calculate UPER 0g* 0) depends on g. we introduce Lasso solver as an example. We must choose an iterative solver to combine with the screening methods because they cannot estimate the solution alone. Although our methods can work with any iterative method, we use coordinate descent, which is recommended in (9].
5.1 Choice of a Dual Feasible Point
As shown in the previous section, lim, RS 0²) converges (0) when lim, P(g)) D(O') 0 holds. Because the iterative solver provides sequence of primal points whose P( converges D(0), we only need converging sequence of dual points obtain converging safe region. The next theorem provides such sequence.

---

Tynamio Seavl
Ratio of Active Variables
Dynami:
Cap Safe Dome
Cap Safe Sphteee
pith con compuuttion Sine Imd
Zshami: 3DPP
Safe Sphere
Cynamic Cacal
Dep Safo Doni
12800
0.5
12000
0.25
6500
500
1000
1500
Number of Iterations
+
(a) Feature
remaining
rate (h) Computational time (Leukemia). (c) Computational time (RCV1).
(Leukemia).
Figure (a): Feature remaining rate of each iteration for Lasso on leukemia (dense data with 72, d = 7128). (b) Average computational time of the Lasso path on subsampled leukemia (dense data with n 50, 7128). (c): Average computational time of the Lasso path on subsampled RCVI (sparse data with 20000, d = 47236).
Table I: Logarithm of acceleration ratio. The larger values indicate greater speed-up.
Dataset
-log
Dynamic Sasvi
Dynamic EDPP
Gap Safe Dome
Gap Safe Sphere
0.468 = 0.066
0.487
0.066
0.349 + 0.066
0.358 1 0.060
Leukemia
6
0.828 = 0.072
0.838 + 0.067
0.719 = 0.074
0.725 = 0.072
0.987 = 0.057
0.997
0.056
0.902 = 0.066
0.907 = 0.066
4
0.257 + 0.0056
0.263 + 0.0078
0.221 = 0.0081
0.228 + 0.0089
RCVI
0.373
0.0065
0.374 = 0.0085
0.345 = 0.0099
0.346 + 0.0114
8
0.417 + 0.0065
0.418 + 0.0079
0.397 = 0.0086
0.398 = 0.0092
Theorem 11 (Converging 6') Consider the optimization problem in Eq.
with ( ||31|
Let B E Rd and Ô E IR" be the primal/dual solution. Assume that lim,
e B. Let define
6: R RD as
6(3) := max(1, [1ax(1,||X (3 x.)
y - xx3)..
Then, VB ((3) E dom( and lime- ((33) = hold.
(Proof) ((B) dom(D) directly derived from X ((3) min[[ (y (y- x,3)l 1) 1.
Because {y- x33)) converges x 0, lim (B3) = Ô also holds.
A is the set of features that is not yet eliminated, we can use
(B) max(1, (1, T (y X(3)) (XB y)
instead of ((3). Although (B3 dom(D) not guaranteed, dx(3) is guaranteed satisfy all the constraints that are active in the dual solution. In other words, ( is in the domain of the dual problem of the small primal problem without eliminated features. Now, we can optimize the problem using the proposed screening method. The pseudocode is described in Algorithm The direct expression RRR [z.]] 0 given the appendix.
5.2 Computational Cost
In the screening part of Algorithm 1 only multiplying X or X costs O(nd). Because Ø (3) is a linear combination of X 3 and y. we can obtain X from X X and X y. Because X is constant, only the calculations of X& and x x cost O(nd). Hence, the screening cost is almost the same for all methods, which require X X including Gap Safe.

---

Experiments
In this section, we show the efficacy of the proposed methods using real-world data, We compared the proposed methods with Gap Safe Sphere and Gap Safe Dome [7], which are state-of-the-ee dynamic safe screening methods. All methods were run on Macbook Air with a 1.1 GHz quad-core Intel Core i5 CPU with 16 GB of RAM. All methods were implemented in C++ using the Accelerate framework In this section, methods are evaluated on Lasso. Experiments on group Lasso are provided in the appendix.
6.1 Number of Screened Variables
First, we compared the number of screened variables among the four dynamic safe screening methods.
We solved the Lasso problem using the leukemia dataset 2 [T]] (dense data with 72 samples and 7128 features) and À 100
|| X ylloo We used cyclic coordinate descent the iterative algorithm and screened the variables for 10 iterations each. Figure shows the ratio the uneliminated features at that Dynamic Sasvi eliminates more variables
each iteration. As guaranteed theoretically, in earlier steps compared with both Gap Safe Dome and Gap Safe Sphere. The figure also shows that the Dynamic EDPP, which is relaxed version of Dynamic Sasvi, eliminates almost the same number of features as Dynamic Sasvi.
6.2 Gains in the Computation of Lasso Paths
Next, we compared the computation time of the path of the Lasso solutions for various values of A. We used > = 100 || T yl 2o (j = O,.... 99). We used the estimated primal solution for X with scaling as the initial vector in the solver for the problem with X The iterative solver stops when the duality gap is smaller than e( (() D())). Note that P(O) D makes the stopping criterion independent of the data scale. We used the leukemia and RCVI I3 datasets (sparse data with 23149 samples and 47236 features). We subsampled the data 50 times and ran all the methods for the same 50 subsamples. The subsampled data size was 50 for leukemia and 20000 for RCVI. Figures and show the average computation times of the Lasso path for the leukemia and RCV1 datasets, respectively. For all settings, dynamic Sasvi and dynamic EDPP outperform Gap Safe Dome and Gap Safe Sphere. Table lists the average values and standard deviations of the negative of the logarithm of the computational time ratio with respect to that for the same subsample without screening. The proposed methods are significantly faster than the Gap Safe methods.
Conclusion
In this study, we proposed framework for safe screening based on the Fenchel-Rockafellar duality and derived Dynamic Sasvi and Dynamic EDPP, which are specific safe screening methods for Lasso- like problems. Dynamic Sasvi and Dynamic EDPP variants of Sasvi and EDPP, respectively. We proved that Dynamic Sasvi always eliminates more features than both Gap Safe Sphere and Gap Safe Dome. Dynamic EDPP is based on the sphere relaxation of the Dynamic Sasvi region and eliminates almost the same number of features as Dynamic Sasvi. We also showed experimentally that the computational costs of the proposed methods are lower than those of Gap Safe Sphere and Gap Safe Dome
be regarded as dynamic feature elimination
Acknowledgement
MY was supported by MEXT KAKENHI 20H04243 and partly supported by MEXT KAKENHI 21H04874.
Source codes are in
htte:://heoourrrraaaaarrgggaaaar ugr
html

---

References
[1] Runxue Bao, Bin Gu, and Heng Huang. Fast oscar and owl regression via safe screening rules. In ICML, 2020.
[2] Heinz H Bauschke, Patrick Combettes, et al. Corvex analysis and monotone operator theory in Hilbert spaces, volume 408. Springer, 2011.
[3] Antoine Bonnefoy, Valentin Emiya, Liva Ralaivola, and Rémi Gribonval. Dynamic screening: Accelerating first-order algorithms for the lasso and group-lasso. IEEE Transactions on Signal Processing, 63(19):5121-511 2015.
[4] Héctor Gonzente-González, Chloé-Agathe Azencott, Samuel Kaski, and Makoto Yamada. Block hsic lasso: model-free biomarker detection for ultra-high dimensional data. Bioinformatics, 35(14):447-i445, 2019.
[5] Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine learning, 20(3):773-
297, 1995.
[6] David L Donoho. Compressed sensing. IEEE Transactions on information theory, 52(4):1289, 1306, 2006.
[7] Olivier Fercoq, Alexandre Gramfort, and Joseph Salmon. Mind the duality gap: safer rules for the lasso. In ICML, 2015.
[8] Mario Figueiredo and Robert Nowak. Ordered weighted I1 regularized regression with strongly correlated covariates: Theoretical aspects. In AISTATS, 2016.
[9] Jerome Friedman, Trevor Hastie, Holger Höffing, and Robert Tibshirani. Pathwise coordinate optimization. Ann. Appl. Stat., 1(2):002-33,, 2007.
[10] Laurent El Ghaoui, Vivian Viallon, and Tarek Rabbani. Safe feature elimination for the lasso and sparse supervised learning problems. arXiv preprint aOXi 1009.4009442 42199, 2010.
[11] T. R. Golub, D. K. Slonim, P. Tamayo, C. Huard, M. Gaasenbeek, J. P. Mesirov, H. Coller, M. L. Loh, J. R. Downing, M. A. Caligiuri, C. D. Bloomfield, and E. S. Lander. Molecular classification of cancer: Class discovery and class prediction by gene expression monitoring. Science, 286(5439)5531-5333 1999.
[12] Laurent Jacob, Guillaume Obozinski, and Jean-Philippe Vert. Group lasso with overlap and graph lasso. In ICML, 2009.
[13] David D Lewis, Yiming Yang, Tony Russell-Rose and Fan Li. Revl: A new benchmark collection for text categorization research. Journal of machine learning research, 5(Apr):361- 397, 2004.
[14] Jun Liu, Zheng Zhao, Jie Wang, and Jieping Ye. Safe screening with variational inequalities and its application to lasso. In ICML, 2014.
[15] Lukas Meier, Sara Van De Geer, and Peter Bühlmann. The group lasso for logistic regression. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 70(1):53-71, 2008.
[16) Eugène Ndiaye, Olivier Fercoq, Alexandre Gramfort, and Joseph Salmon. Gap safe screening rules for sparse multi-task and multi-class models. In NIPS, 2015.
[17] Eugene Ndiaye, Olivier Fercoq, Alexandre Gramfort, and Joseph Salmon. Gap safe screening rules for sparsity enforcing penalties. Journal of Machine Learning Research, 18(1):4671-4700 2017.
[18] Eugene Ndiaye, Olivier Fercoq, and Joseph Salmon. Screening rules and its complexity for active set identification, 2020.
[19] Kohei Ogawa, Yoshiki Suzuki, and Ichiro Takeuchi. Safe screening of non-support vectors in pathwise svm computation. In ICMI., 2013.
[20] Anant Raj, Jakob Olbrich, Bernd Gärtner, Bernhard Schölkopf. and Martin Jaggi. Screening rules for convex problems. arXiv preprint arXiv:1609.074. 07478, 2016.
[21] Atsushi Shibagaki, Masayuki Karasuyama, Kohei Hatano, and Ichiro Takeuchi. Simultaneous safe screening of features and samples in doubly sparse modeling. In ICMI, 2016.
[22] Alex J Smola and Bernhard Schölkopf. tutorial on support vector regression. Statistics and computing, 14(3):199-22 2004.
10

---

[23] Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B [Methodological), 58(1)2667 1996.
[24] Jie Wang, Peter Wonka, and Jieping Ye. Lasso screening rules via dual polytope projection. Journal of Machine Learning Research, 16(1):1033-1011 2015.
[25] Zhen James Xiang, Yun Wang, and Peter J. Ramadge. Screening tests for lasso problems. IEEE Transactions Pattern Analysis and Machine Intelligence, (115):008-1122) May 2017.
[26] Ming Yuan and Yi Lin. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society Series B, 68:49-67, 02 2006.
[27] Hui Zou and Trevor Hastie. Regularization and variable selection via the elastic net. Journal of the royal statistical society: series B (statistical methodology), 67(2):301-320, 2005.


Reviews:
[{"review_id": "nqe_xrtGzYY", "reviewer": "Reviewer_Cu9Q", "summary": " The concern of  the paper is the design of screening rule for sparsity-based regularized convex  optimization problem  such as the Lasso-type problem.  The aim is to screen out  irrelevant parameters during  the optimization  procedure. The  designed screening rule hinges on Fenchel-Rockafellar duality and  encompasses existing  methods (Gap Safe Sphere, Gap Safe Dome, Sasvi). The  paper establishes that the  constructed  safe region for the dual solution is of reduced size than the  ones the aforementioned methods. Hence, the new rule induces a more efficient screening. Empirically evaluation on Lasso problem show that the proposed screening rule brings computation gain when compared to existing methods.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "- Overall, the paper is well written and well  organized. The rationale behind the new screening rule is justified and the  novelty brought  by  the approach is stated clearly.  The key element  to  the rule  is that the dual of  the problem  may be upper- bounded by a term depending on the conjugate of the fitting term provided a primal/dual inequality is met.  In  the context of the Lasso-type problems, the upper bound exploits convexity hence,  it appears somehow obvious. \n\n- The safe region of the advocated screening rule is expressed as the intersection  of  a sphere and  a half space. Compared to Gap Safe Dome or Gap Safe Sphere, that  safe region is of reduced size. Hence, the  obtained screening rule is theoretically shown to be stronger. This fact is illustrated by  empirical findings. Overall the algorithmic derivation and empirical evaluation represents a novelty of the work. The empirical findings show  substantial computation gain that is of interest to practitioners. Notice that a side result of  the paper is  Dynamic EDPP, a relaxation of the proposed screening rule that proves slightly faster  while keeping interesting screening abilities.\n\n- Theorem 5 is trivial provided the safe region expression Lines 116-117.\n\n- The overall safe region construction is devised for a general Lasso-like  problem. However, the remainder of the paper  is restricted to the sole Lasso. Though the empirical findings for Lasso aree convincing, it will be interesting to show the results for other regularizers (for instance elastic-net,  group lasso to name a few). \n-When used to compute the Lasso regularization path, Dynamic EDPP provides slightly better computation time than Dynamic Sasvi. Is this due to a simplified  screening rule? \n\n- Another  question raised is how the proposed Fenchel Duality based derivations might be lifted to problems such as spare logistic regression learning? Gap Sphere method does so. At least the paper should discuss this point. \n\n- Other comments\nThe caption or Figure 1 has to reformatted. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Unless I  was mistaken, the paper does not discuss the broader impact of the proposed approaches. On my view the work does not raise specific issues\n", "review_text": "", "extra_scores": {"ethical_concerns": "The  paper does not raise  any ethical issues.\n", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "SlbOmpUlQ99", "reviewer": "Reviewer_grp2", "summary": "The paper proposes a screening test for sparse models, i.e. a way to remove features from the problem once it is sure that they are not active at optimum. The rule is a generalization of the popular Gap Safe screening.\nAs in GSR, a dual safe region is constructed using strong convexity of the dual objective (obtained from Lipschitz smoothness of the datafit in the primal)", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper proposes to use a Dome region instead of the Gap Safe sphere region, improving upon the dome region that was proposed in the Fercoq et al \"Mind the duality gap...\" 2015 paper. Note that this does not allow to handle more problems than the Gap Safe framework, but only improves the number of screened variable.\nThe paper is wwell-written and easy to follow for someone familiar with the literature.\n\n\nReading the paper, I felt that the theory was promising, and that it would lead to significant speedups in the computation of Lasso solution. The experimental results somehow did not live up to it: the improvements in timings compared to Gap Safe Screening rule are marginal, as visible on Fig 2. Given that there now exist solvers based on aggressive screening such as Blitz or Celer (Johnson and Guestrin 2016, Massias, Gramfort and Salmon 2018) that outperform Gap Safe Screening rules, I feel the practical results are too low for a venue such as NeurIPS.\n\nOther comments:\nThe formula L97 is understandable when one is familiar with the littérature but incorrect, as the LHS is a subset of the dual space while the RHS is a subset of the primal space.  (EDIT: I was wrong, thanks for the clarification)\n\nCosmetic:\nIn 5 the variable k tends to denote an integer, can you use another variable?\nThe legend of Fig 1 is very hard to read, as the captions are not separated; the equations are also very small. \nin Fig 2 the labels are also impossible to read.\nWhat do you mean by \"density of n = 50, p=7129\" ?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "none", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "2r3H2pqQkzh", "reviewer": "Reviewer_dgBv", "summary": "This paper presents a new framework for safe screening based on Fenchel-Rockafellar duality, which generalizes a few existing algorithms in the literature. Given the proposed framework, a tight dome-shape safe region can be constructed for dual variables of Lasso-like problems, so that the zeros in primal solutions can be detected more quickly. The paper has discovered the connection between the new framework and some previously proposed methods, such as Sasvi and EDPP. Theoretically it also shows that the new safe region is always smaller than Gap Safe Dome and Gap Safe Sphere in the literature, which is supported by empirical evidence from experiments.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Originality: Given existing works in the literature, the new framework for safe screening proposed in this paper does not seem to be super novel, but I am glad that in the first few sections the authors have a quite nice summary on the general ideas for attacking the safe screening problem, and clearly differentiate this work with previous ones.   \n\nQuality: The technical quality of this paper is relatively high. Though it looks to me that the most important idea is just to have the upper bound tightened in Theorem 5, proposing its exact form for the Lasso-like problem seems non-trivial, which is more complicated than the constant upper bound proposed previously and may need more careful treatment in terms of math. The result showing its connection to Sasvi is new and interesting. It is also nice to see that the paper theoretically proves that the obtained safe region from such tightening trick is smaller than Gap Safe Dome and Gap Safe Sphere. One thing that is not so clear to me is the application to Elastic-Net in the supplementary material, which is to show the broader applicability of the framework, but technically speaking the function $g$ there is not a norm, which violates Eq. (5). So it the screening method still valid? I am also curious if the result can be extended to group Lasso as well? In the experiments, it would also be ideal to make comparisons on other norms. \n\nClarity: Overall the paper is well-written. The flow for presenting such (generalized) framework is clear, such that readers can easily tell how it is different from existing algorithms. The figure showing the safe regions for different methods is also helpful for understanding. \n\nSignificance: The proposed method, dynamic Sasvi and dynamic EDPP, seem readily applicable to Lasso-like problems to speed up the solving procedure. The framework could be potentially applied to other settings for faster solvers. So this work should be a valuable addition to this research area.\n\n\nOther detailed comments:\n\n1. In theorem 11, a particular convergent sequence of $\\theta^t$ is constructed. For general norms, is there any guidance or recipe that could be provided to help design such sequence?\n\n2. If I understand correctly, the difference between original Sasvi and dynamic Sasvi is just the choice of $\\theta^t$ and $\\beta^t$ that define the safe region, but I did not see a clear explanation for the latter being faster, so it would be better to clarify a little bit. Also, in general is there any insight on how different choices of $\\theta^t$ and $\\beta^t$ affect the efficiency of screening? Same for EDPP and dynamic EDPP.\n\n3. In the experiment, dynamic EDPP seems to be faster than dynamic Sasvi, but it looks like the safe region of EDPP is larger than Sasvi theoretically. So the result is a bit counterintuitive. Is the reason that some computation is faster for EDPP region than Sasvi? Can authors give a comment on this?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers agrees that the derivation of a new screening rule is interesting, and that the mathematical
results are strong and leads to (slight) computational acceleration compared to SOTA methods.

The authors are encouraged to release their code for numerical benchmarks with other screening rules and sparse solvers.
(there exists a open-source project about that, named BenchOpt)

Decision: Accept (Poster)