Dynamic Sasvi: Strong Safe Screening for Norm-Regularized Least Squares
Year: 2022

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.

heading: 1 Introduction
text: 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, a technique called safe screening has been introduced [10] for Lasso problems. Specifically, it eliminates variables that are guaranteed to be zero in the Lasso solution before solving the original Lasso optimization problem. Many safe screening methods have been proposed for various problems [10, 19, 24, 14, 25]. These are called sequential screening rules because they require the solution to a 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, 16], a dynamic screening framework, is widely used owing to its generality and efficiency [17, 21, 1, 20, 18].
In this paper, we propose a 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 a general screening framework based on the Fenchel–Rockafellar duality and then derive Dynamic Sasvi, a strong safe screening rule for Lasso-like problems. Our framework can be regarded as a 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 as a dynamic variant of safe screening with variational inequalities (Sasvi) [14], which is a sequential screening rule for Lasso. Therefore, we refer to this as Dynamic Sasvi. Unlike the original Sasvi, dynamic Sasvi does not require an exact solution to the problem with another hyper-parameter and, hence, operates safely in practice. Moreover, we 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
35th Conference on Neural Information Processing Systems (NeurIPS 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-art Gap Safe methods.
Contribution: The contributions of our study are summarized as follows.
• We propose a flexible screening framework based on the Fenchel–Rockafellar duality, which is a generalization of the Gap Safe framework [17].
• We propose two novel dynamic screening rules for norm-regularized least squares: a dynamic variant of Sasvi [14] and a dynamic variant of EDPP.
• We show that Dynamic Sasvi always eliminates more features and increases the speed of the solver compared with Gap Safe [7, 17] .

heading: 2 Preliminary
text: In this section, we first formulate the problem and introduce the key techniques used in this study.

heading: 2.1 Notation
text: Given h : Rm → [−∞,∞], the domain of h is defined by dom(h) := {z ∈ Rm | |h(z)| <∞} and h? : Rm → [−∞,∞], which is the Fenchel conjugate of h, is defined as h?(v) := supz∈Rm v>z − h(z). If h is proper, the Fenchel–Young inequality,
h(z) + h?(v) ≥ v>z, (1) can be proven directly based on definition of the Fenchel conjugate. The subdifferential of a proper function, h : Rm → (−∞,∞], at z is given as
∂h(z) := {v ∈ Rm | ∀w ∈ Rm v>(w − z) + h(z) ≤ h(w)}. The next proposition is important for deriving safe-screening algorithms.
Proposition 1 Assume that h : Rm → (−∞,∞] is a proper lower semi-continuous convex function and z,v ∈ Rm. We then have
v ∈ ∂h(z) ⇐⇒ h(z) + h?(v) = v>z ⇐⇒ z ∈ ∂h?(v).
See Section 16 of [2] for the proof. For convex set C ⊂ Rm, the relative interior of C is defined as relint(C) := {v ∈ C | ∀w ∈ C ∃ > 0 s.t. v + (v − w) ∈ C}.

heading: 2.2 Problem Formulation
text: In this study, we consider an optimization problem, formulated as minimize β∈Rd f(Xβ) + g(β), (2)
where β ∈ Rd is the optimization variable,X ∈ Rn×d is a constant matrix, and f : Rn → (−∞,∞] and g : Rd → (−∞,∞] are proper lower semi-continuous convex functions. We assume
∃β ∈ relint(dom(g)) s.t.Xβ ∈ relint(dom(f)) and the existence of the optimal point, i.e.,
∃β̂ ∈ dom(P ) s.t. P (β̂) = inf β∈Rd P (β),
where P : Rd → R is defined as P (β) = f(Xβ) + g(β). Moreover, we focus on the cases in which g induces sparsity. Although all theorems in this paper hold, we cannot eliminate any variables without sparsity.
This is a popular class of optimization problem, with the most popular example being Lasso [23]:
minimize β∈Rd
1 2 ‖y −Xβ‖22 + λ‖β‖1.
Many extensions of Lasso, including Group-Lasso [26], elastic net [27], and sparse logistic regression [15], are in this class. The dual problems of a support vector machine [5] and a support vector regression [22] are also in this class.

heading: 2.3 Dual Problem
text: In the derivation of a safe screening rule for the optimization problem, Eq. (2), the Fenchel– Rockafellar dual formulation, plays an important role.
Theorem 2 (Fenchel–Rockafellar Duality) If all assumptions for the optimization problem (2) are satisfied, we have the following:
min β∈Rd f(Xβ) + g(β) = max θ∈Rn
−f?(−θ)− g?(X>θ). (3)
The proof of Theorem 2 is provided in the appendix. We denote −f?(−θ) − g?(X>θ) by D(θ). For primal/dual solutions, there are many conditions that are equivalent to 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) β̂ ∈ argmin β∈Rd P (β) ∧ θ̂ ∈ argmax θ∈Rn D(θ)
(b) P (β̂) = D(θ̂)
(c) f(Xβ̂) + f?(−θ̂) = −θ̂ > Xβ̂ = −g(β̂)− g?(X>θ̂)
(d) −θ̂ ∈ ∂f(Xβ̂) ∧X>θ̂ ∈ ∂g(β̂)
(e) Xβ̂ ∈ ∂f?(−θ̂) ∧ β̂ ∈ ∂g?(X>θ̂)
(Proof) (a) ⇐⇒ (b) is directly derived from the strong duality. (b) ⇐⇒ (c) is derived from the Fenchel–Young inequality (1). (c) ⇐⇒ (d) ⇐⇒ (e) are derived from Proposition 1.

heading: 2.4 Relationship of Dual Safe Region and Screening
text: 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 regionR. According to Proposition 3, we have
β̂ ∈ ∂g?(X>θ̂) ⊂ ⋃ θ∈R ∂g?(X>θ).
Hence, if ⋃ θ∈R ∂g
?(X>θ) ⊂ {β | βi = 0} holds, we obtain β̂i = 0. A simple example is the following corollary.
Example 4 Consider an optimization problem, i.e., Eq. (2) with g(β) = ‖β‖1. Assume that θ̂ ∈ R. Then, we have
max θ∈R |x>i θ| < 1 =⇒ β̂i = 0.
(Proof) Based on the definition of g, we have ∂g?(X>θ) ⊂ {β | βi = 0} ⇐⇒ |x>i θ| < 1. When maxθ∈R |x>i θ| < 1, we have β̂ ∈ ⋃ θ∈R ∂g ?(X>θ) ⊂ {β | βi = 0}.
To eliminate features safely, we should first construct a simple region R ⊂ Rn which contains θ̂ and then determine whether ⋃ θ∈R ∂g
?(X>θ) ⊂ {β ∈ Rd | βi = 0} is guaranteed. In this study, we provide a novel general framework for constructing a simple safe region, R ⊂ Rn. By combining it with existing methods to calculate an upper bound of ⋃ θ∈R ∂g
?(X>θ) (cf. [17] for the un-overlapping group L1 norm and sparse group L1 norm, [1] for the ordered weighted L1 norm), we can formulate strong safe screening rules.

heading: 3 General Framework for Constructing Safe Region
text: Herein, we propose a general framework for constructing a dual region that contains the solution to the optimization problem expressed by Eq. (3). Our framework consists of a general lower bound and a problem-adaptive upper bound of the optimal value. Hence, we can derive a narrower region than the framework with a general upper bound under certain situations.
The general lower-bound is derived from the optimal condition and the L-strong convexity. Assume that f? is L-strongly convex (L ≥ 0). Then, as D is L-strongly concave and θ̂ is the optimal point, we have D(θ̃) ≤ D(θ̂)− L2 ‖θ̂ − θ̃‖ 2 2 for ∀θ̃ ∈ Rn. Thus, we have
θ̂ ∈ {θ | L 2 ‖θ − θ̃‖ 2 2 +D(θ̃) ≤ D(θ)}.
Because this region is too complicated for screening, we use a simple upper bound of D(θ) to construct a simple safe region.
Theorem 5 Consider the optimization problem expressed by Eq. (3) and assume that f? is L-strongly convex (L ≥ 0). Let θ̂ be the solution to Eq. (3). Assume that D(θ) is upper-bounded by u(θ), i.e., ∀θ ∈ Rn D(θ) ≤ u(θ). Then, for ∀θ̃ ∈ Rn, we have
θ̂ ∈ R(θ̃, u) = {θ | L 2 ‖θ − θ̃‖ 2 2 +D(θ̃) ≤ u(θ)}.
The complexity ofR(θ̃, u) depends on the complexity of u. For example, if u is linear, thenR(θ̃, u) is a sphere. We can construct a narrow, simple, and safe region with a tight simple upper-bound u. In fact, the Gap Safe Sphere region [7, 17] can be derived easily from this theorem and weak duality.
Corollary 6 (Gap Safe Sphere) Consider the optimization problem described by Eq. (3) and assume that f? is L-strongly convex (L ≥ 0). Let θ̂ be the solution to Eq. (3). For ∀β̃ ∈ Rd and ∀θ̃ ∈ Rn, we have
θ̂ ∈ {θ | L 2 ‖θ − θ̃‖ 2 2 +D(θ̃) ≤ P (β̃)}.
(Proof) Based on a weak duality, we have ∀θ D(θ) ≤ P (β̃). Using this constant function as an upper bound in Theorem 5, we can derive the corollary directly.
Hence, our framework can be seen as a generalization of Gap Safe. Owing to this generalization, we can use a 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.

heading: 4 Safe Region for Lasso-like Problem
text: 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 as a generalization of Sasvi [14] and is narrower than Gap Safe region.

heading: 4.1 Norm-regularized Least Squares Problem and its Generalization
text: Norm-regularized least squares is an optimization problem and is formulated as minimize β∈Rd 1 2‖y −Xβ‖ 2 2 + g(β) where g is a norm. This is a subset of problem 2. Although this formulation includes Lasso [23], (overlapping) group-Lasso [26, 12], and ordered weighted L1 regression [8], the non-negative Lasso is not included. To unify them, we define the Lasso-like problem as follows:
minimize β∈Rd
1 2 ‖y −Xβ‖22 + g(β), (4)
where the problem satisfies all assumptions for Eq. (2) and g satisfies
∀a ≥ 0,β ∈ Rd g(aβ) = ag(β). (5)
For the Lasso-like problem, the Fenchel conjugate functions of f and g are given as
f?(−θ) = 1 2 ‖θ‖22 − y >θ g?(X>θ) = { 0 (∀β θ>Xβ − g(β) ≤ 0) ∞ (∃β θ>Xβ − g(β) > 0).
(6)
Note that {θ | g?(X>θ) = 0} is a closed convex set. Hence, the Lasso-like problem is a class of problems whose Fenchel–Rockafellar dual can be seen as a convex projection.

heading: 4.2 Proposed Dome Region for Lasso-like Problem
text: Using Theorem 5, we can construct a safe region by proposing an upper bound, u(θ). In this section, we propose a tight upper bound for Lasso-like problems. The direct expression of f? in Eq. (6) is sufficiently simple. We only need an upper bound of −g? to construct a simple region. The upper bound is given as follows.
Lemma 7 For Lasso-like problems (4), for ∀β̃ ∈ Rd and ∀θ ∈ Rn, we have
D(θ) ≤ −f?(−θ) + inf a≥0 g(aβ̃)− θ>X(aβ̃) = { −f?(−θ) (g(β̃)− θ>Xβ̃ ≥ 0) −∞ (g(β̃)− θ>Xβ̃ < 0). (7)
The proof of Lemma 7 is given in the appendix. Using the right-hand side of Eq. (7) as an upper bound of D, we can construct a simple and safe region.
Theorem 8 Consider the Lasso-like problem described by Eq. (4) and its Fenchel–Rockafellar dual problem presented in Eq. (3). Let θ̂ be the dual optimal point. We assume that β̃ ∈ Rd and θ̃ ∈ dom(D). Then, θ̂ is within the Dynamic Sasvi region, which is given as the intersection of a sphere and a half space:
RDS(β̃, θ̃) :={θ | 1 2 ‖θ − θ̃‖ 2 2 +D(θ̃) ≤ −f ?(−θ) ∧ 0 ≤ g(β̃)− θ>Xβ̃}
={θ | (y − θ)>(θ̃ − θ) ≤ 0 ∧ 0 ≤ g(β̃)− θ>Xβ̃}.
The proof of Theorem 8 is given in the appendix. As proven in section 4.5,RDS(βk,θk) converges to {θ̂} when limk→∞ P (βk)−D(θk) = 0. When we have good primal/dual feasible points, we can derive a very narrow safe region and eliminate almost all irrelevant features.

heading: 4.3 Relation to Sasvi
text: In this section, we show that safe screening with variational inequality (Sasvi) [14] is a special case of our screening rule. First, we review Sasvi. The target task of Sasvi is to minimize 12 ∥∥λ−1y −Xβ∥∥2 2 + ‖β‖1 with many λs. Sasvi is called “sequential” screening because it is designed to solve a sequence of problems with a sequence of penalty parameters, λ1 > λ2 > . . . > λM . Let β̂ (λ) and θ̂ (λ) be the optimal points of the primal problem and its Fenchel–Rockafellar dual problem, respectively. Because the dual problem can be interpreted as a projection from λ−1y to a closed convex set, {θ ∈ Rn | ‖X>θ‖∞ ≤ 1}, the following two variational inequalities hold:
0 ≥ (λ2−1y − θ̂ (λ2) ) > (θ̂ (λ1) − θ̂ (λ2) ) 0 ≥ (λ1−1y − θ̂ (λ1) ) > (θ̂ (λ2) − θ̂ (λ1) ). (8)
Given θ̂ (λ1) , these inequalities provide a safe region for θ̂ (λ2) . Sasvi finds some zero elements of β̂ (λ2) based on this region. Note that−θ̂ (λ1) =Xβ̂ (λ1)−λ1−1y and−θ̂ (λ1)> Xβ̂ (λ1) = −g(β̂ (λ1) ) are derived from Proposition 3. Then, we have
(λ1 −1y − θ̂ (λ1) ) > (θ̂ (λ2) − θ̂ (λ1) ) = θ̂ (λ2)> Xβ̂ (λ1) − g(β̂ (λ1) ).
Because λ2−1y in Eq. (8) corresponds to y in Theorem 8,RDS(β̂ (λ1) , θ̂ (λ1)
) is equal to the Sasvi region. Hence, we can state that our method is a generalization of Sasvi. Our method requires primal/dual feasible points, unlike the original Sasvi, which requires the dual optimal point of a 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 it 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 [7], some sequential safe screening rules, including Sasvi, are not safe in practice because we cannot provide an exact solution for λ1. Dynamic Sasvi overcomes this problem because it does not require the solution of a problem with another parameter.

heading: 4.4 Comparison to Gap Safe
text: Here, we show that the proposed method is stronger than Gap Safe Dome [7] and Gap Safe Sphere [7], [17] for Lasso-like problems. As shown in [7], for Lasso, the regions of the Gap Safe Dome and Gap Safe Sphere are the relaxation of the intersection of a sphere and the contra of another sphere:
{θ | (y − θ)>(θ̃ − θ) ≤ 0 ∧ −f?(−θ) ≤ P (β̃)},
where β̃ and θ̃ are primal/dual feasible vectors, respectively. (y − θ̂) > (θ̃ − θ̂) ≤ 0 is the variational
inequality, and −f?(−θ̂) ≤ P (β̃) is derived from weak duality. Using a simple transformation, we have
−f?(−θ) ≤ P (β̃) ⇐⇒ − 1 2 ‖θ‖22 + y >θ ≤ 1 2 ‖y −Xβ̃‖ 2 2 + g(β̃)
⇐⇒ − 1 2 ‖y −Xβ̃ − θ‖ 2 2 ≤ g(β̃)− θ >Xβ̃.
Hence, we have 0 ≤ g(β̃) − θ>Xβ̃ =⇒ −f?(−θ) ≤ P (β̃). This means that the region of dynamic Sasvi is a subset of the region of Gap Safe Dome. Our screening is always stronger than Gap Safe Dome and Gap Safe Sphere. Figure 1b shows the regions of Dynamic Sasvi, Gap Safe Dome, and Gap Safe Sphere.

heading: 4.5 Sphere Relaxation (Dynamic EDPP)
text: In some situations, even a dome region is too complicated to calculate ⋃ θ∈R ∂g
?(X>θ). For such cases, we propose using a minimum radius sphere that includes the dynamic Sasvi region. This method can be seen as a dynamic variant of the EDPP [24] because the EDPP is the minimum radius sphere relaxation of Sasvi.
Theorem 9 Consider the Lasso-like problem presented in Eq. (4) and its Fenchel–Rockafellar dual problem in Eq. (3). We assume that β̃ ∈ Rd and θ̃ ∈ dom(D). If n ≥ 2, the minimum radius sphere includingRDS(β̃, θ̃) is
RDE(β̃, θ̃) := {θ | ‖θ − 1 2 (θ̃ + y) + αXβ̃‖
2 2 ≤ 1 4 ‖θ̃ − y‖ 2 2 − α 2‖Xβ̃‖ 2 2}, (9)
Algorithm 1 Coordinate descent with Dynamic Sasvi for Lasso
1: Input: X,y,β0, T, c, 2: Initialize β̃ ← β0, A ← [[d]] 3: for t ∈ [[T ]] do 4: if t mod c = 1 then 5: Compute θ̃ = φA(β̃) 6: if P (β̃)−D(θ̃) ≤ 12‖y‖ 2 2 then 7: break 8: end if 9: R ← RDS(β̃, θ̃)
10: A ← {j ∈ A : maxθ∈R |x>j θ| ≥ 1} 11: for j ∈ [[d]]−A do 12: β̃j ← 0 13: end for 14: end if 15: for j ∈ A do 16: u← β̃j‖xj‖ 2 2 − x > j (Xβ̃ − y) 17: β̃j ← 1‖xj‖22 sign(u)max(0, |u| − 1) 18: end for 19: end for 20: Output:β̃
where
α = max ( 0, ‖Xβ̃‖
−2 2
( 1
2 (θ̃ + y)
> Xβ̃ − g(β̃) )) .
The proof of Theorem 9 is provided in the appendix. Figures 1a and 1c 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 ofRDE(β̃, θ̃). We then have
r < √ P (β̃)−D(θ̃).
The proof is given in the appendix. Because the radius of the Gap Safe Sphere region is√ 2(P (β̃)−D(θ̃)), the squared radius of the Dynamic EDPP region is always less than half that of
Gap Safe Sphere. Furthermore, Theorem 10 shows thatRDE(βk,θk) andRDS(βk,θk) converge to {θ̂} when limk→∞ P (βk)−D(θk) = 0.

heading: 5 Implementation for Lasso
text: In this section, we provide a specific solver based on Theorem 8. Because the algorithm used to calculate ⋃ θ∈R ∂g
?(X>θ) depends on g, we introduce a 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].

heading: 5.1 Choice of a Dual Feasible Point
text: As shown in the previous section, limt→∞RDS(βt,θt) converges to {θ̂} when limt→∞ P (βt)− D(θt) = 0 holds. Because the iterative solver provides a sequence of primal points whose P (βt) converges to D(θ̂), we only need a converging sequence of dual points to obtain a converging safe region. The next theorem provides such a sequence.
Theorem 11 (Converging θt) Consider the optimization problem in Eq. (4) with g(β) = ‖β‖1. Let β̂ ∈ Rd and θ̂ ∈ Rn be the primal/dual solution. Assume that limt→∞ βt = β̂. Let us define φ : Rd → Rn as
φ(β) := 1
max(1, ‖X>(y −Xβ)‖∞) (y −Xβ).
Then, ∀β φ(β) ∈ dom(D) and limt→∞ φ(βt) = θ̂ hold.
(Proof) φ(β) ∈ dom(D) is directly derived from ‖X>φ(β)‖∞ = min(‖X >(y −Xβ)‖∞, 1) ≤ 1. Because {y −Xβt} converges to y −Xβ̂ = θ̂, limt→∞ φ(βt) = θ̂ also holds.
If A is the set of features that is not yet eliminated, we can use
φA(β) := 1
max(1,maxj∈A x>j (y −Xβ)) (Xβ − y)
instead of φ(β). Although φA(β) ∈ dom(D) is not guaranteed, φA(β) is guaranteed to satisfy all the constraints that are active in the dual solution. In other words, φA(β) 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 1. The direct expression of maxθ∈RDS(β̃,θ̃) |x>j θ| is given in the appendix.

heading: 5.2 Computational Cost
text: In the screening part of Algorithm 1, only multiplyingX orX> costs O(nd). Because θ̃ = φA(β̃) is a linear combination ofXβ̃ and y, we can obtainX>θ fromX>Xβ̃ andX>y. BecauseX>y 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 requireX>Xβ̃, including Gap Safe.

heading: 6 Experiments
text: 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, 17], which are state-of-the-art dynamic safe screening methods. All methods were run on a 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 1. In this section, methods are evaluated on Lasso. Experiments on group Lasso are provided in the appendix.

heading: 6.1 Number of Screened Variables
text: 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 [11] (dense data with 72 samples and 7128 features) and λ = 1100‖X
>y‖∞. We used cyclic coordinate descent as the iterative algorithm and screened the variables for 10 iterations each. Figure 2a shows the ratio of the uneliminated features at each iteration. As guaranteed theoretically, we can see that Dynamic Sasvi eliminates more variables in earlier steps compared with both Gap Safe Dome and Gap Safe Sphere. The figure also shows that the Dynamic EDPP, which is a relaxed version of Dynamic Sasvi, eliminates almost the same number of features as Dynamic Sasvi.

heading: 6.2 Gains in the Computation of Lasso Paths
text: Next, we compared the computation time of the path of the Lasso solutions for various values of λ. We used λj = 100− j 99 ‖X>y‖∞ (j = 0, . . . , 99). We used the estimated primal solution for λj with scaling as the initial vector in the solver for the problem with λj+1. The iterative solver stops when the duality gap is smaller than (P (0)−D(0)). Note that P (0)−D(0) makes the stopping criterion independent of the data scale. We used the leukemia and RCV1 3 [13] 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 RCV1. Figures 2b and 2c 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 1 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.

heading: 7 Conclusion
text: In this study, we proposed a framework for safe screening based on the Fenchel–Rockafellar duality and derived Dynamic Sasvi and Dynamic EDPP, which are specific safe screening methods for Lassolike problems. Dynamic Sasvi and Dynamic EDPP can be regarded as dynamic feature elimination 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.

heading: Acknowledgement
text: MY was supported by MEXT KAKENHI 20H04243 and partly supported by MEXT KAKENHI 21H04874.
1Source codes are in https://github.com/k8127i/2021DynamicSasvi 2https://leo.ugr.es/elvira/DBCRepository/Leukemia/ALLAML.html 3https://scikit-learn.org/0.18/datasets/rcv1.html

Review summaries:
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. As 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)

 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.

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.