Thu-Le Tran
email: thu-le.tran@univ-rennes1.fr

Clément Elvira
email: clement.elvira@centralesupelec.fr

Hong-Phuong Dang
email: dang@univ-brest.fr

Cédric Herzet
email: cedric.herzet@inria.fr

Beyond GAP screening for Lasso by exploiting new dual cutting half-spaces with supplementary material

Keywords: Lasso, convex optimization, safe screening

In this paper, we propose a novel safe screening test for Lasso. Our procedure is based on a safe region with a dome geometry and exploits a canonical representation of the set of half-spaces (referred to as "dual cutting half-spaces" in this paper) containing the dual feasible set. The proposed safe region is shown to be always included in the state-of-the-art "GAP Sphere" and "GAP Dome" proposed by Fercoq et al. (and strictly so under very mild conditions) while involving the same computational burden. Numerical experiments confirm that our new dome enables to devise more powerful screening tests than GAP regions and lead to significant acceleration to solve Lasso.

I. INTRODUCTION

Finding sparse representations is a fundamental problem in signal processing and machine learning. It consists in decomposing some vector y ∈ R m as a linear combination of a few columns (referred to as atoms) of a matrix A = [a 1 , . . . , a n ] ∈ R m×n called dictionary. A popular strategy for obtaining sparse representations is to solve the so-called Lasso problem:

x ⋆ ∈ arg min

x∈R n P (x) ≜ 1 2 ∥y -Ax∥ 2 2 + λ∥x∥ 1 (1)
where λ > 0, see [START_REF] Foucart | A Mathematical Introduction to Compressive Sensing[END_REF]. Inasmuch as solving (1) may require a heavy computational burden as n becomes large, the design of efficient optimization techniques tackling this problem has become an active field of research. Among the most popular approaches addressing [START_REF] Foucart | A Mathematical Introduction to Compressive Sensing[END_REF], one can mention [START_REF] Figueiredo | Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems[END_REF][START_REF] Beck | A fast iterative shrinkagethresholding algorithm for linear inverse problems[END_REF][START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF].

A noteworthy approach in this field is the acceleration method proposed by El Ghaoui et al. in [START_REF] Ghaoui | Safe feature elimination for the Lasso and sparse supervised learning problems[END_REF] and known as safe screening, which aims to design simple tests to identify zeros entries in the minimizers of [START_REF] Foucart | A Mathematical Introduction to Compressive Sensing[END_REF]. This knowledge can then be exploited to (potentially significantly) reduce the dimensionality of the problem by discarding the atoms of the dictionary weighted by zero. Over the past few years, safe

The research presented in this paper is reproducible. Code is available at https://gitlab.inria.fr/cherzet/holder-safe.

screening has sparked a surge of interest in the literature, see e.g., [START_REF] Xiang | Learning sparse representations of high dimensional data on large scale dictionaries[END_REF][START_REF] Bonnefoy | A dynamic screening principle for the Lasso[END_REF][START_REF] Fercoq | Mind the duality gap: safer rules for the Lasso[END_REF][START_REF] Herzet | Safe screening tests for Lasso based on firmly non-expansiveness[END_REF][START_REF] Herzet | Gather and conquer: Region-based strategies to accelerate safe screening tests[END_REF][START_REF] Dai | An ellipsoid based, twostage screening test for BPDN[END_REF][START_REF] Xiang | Fast Lasso screening tests based on correlations[END_REF][START_REF] Liu | Safe screening with variational inequalities and its application to Lasso[END_REF] and beyond ℓ 1 -regularization [START_REF] Ndiaye | Gap safe screening rules for sparsity enforcing penalties[END_REF][START_REF] Elvira | Safe squeezing for antisparse coding[END_REF][START_REF]Safe rules for the identification of zeros in the solutions of the SLOPE problem[END_REF][START_REF] Guyard | Screen & relax: accelerating the resolution of Elastic-Net by safe identification of the solution support[END_REF].

Standard screening methodologies leverage the concept of "safe region", a set provably containing the optimal solution of the dual problem of [START_REF] Foucart | A Mathematical Introduction to Compressive Sensing[END_REF], see e.g., [START_REF] Xiang | Screening tests for Lasso problems[END_REF]Section 4]. The choice of the safe region reveals to be crucial to the final effectiveness and efficiency of the screening tests. On the one hand, loosely speaking, "smaller" regions lead to more effective tests, see [18, Lemma 1]. On the other hand, the complexity of the tests is closely related to the geometry of the safe region. As a consequence, safe regions with "simple" geometries such as spheres [START_REF] Ghaoui | Safe feature elimination for the Lasso and sparse supervised learning problems[END_REF][START_REF] Xiang | Learning sparse representations of high dimensional data on large scale dictionaries[END_REF][START_REF] Bonnefoy | A dynamic screening principle for the Lasso[END_REF][START_REF] Fercoq | Mind the duality gap: safer rules for the Lasso[END_REF][START_REF] Herzet | Safe screening tests for Lasso based on firmly non-expansiveness[END_REF] or domes [START_REF] Xiang | Fast Lasso screening tests based on correlations[END_REF][START_REF] Liu | Safe screening with variational inequalities and its application to Lasso[END_REF] are commonly considered in the literature.

One state-of-the-art methodology to find a good compromise between these two requirements was proposed in [START_REF] Fercoq | Mind the duality gap: safer rules for the Lasso[END_REF]: the authors introduced two new safe regions (referred to as "GAP sphere" and "GAP dome") whose radii are proportional to the duality gap attained by the primal-dual feasible couple used to design the region. The radii of GAP regions have therefore the desirable feature to converge to zero when the primal-dual feasible couple tends to a primal-dual solution, and thus lead to extremely effective screening tests.

In this paper, we propose a new safe dome which is provably contained in the GAP regions. The definition of our dome is based on a fine characterization of the set of half-spaces (referred to as "dual cutting half-spaces" hereafter) containing the whole dual feasible set. At the time of publication, we become aware of a parallel work [START_REF] Yamada | Dynamic sasvi: Strong safe screening for norm-regularized least squares[END_REF] using a different technique to obtain the same safe region.

The paper is organized as follows. In the next section, we define the notations used throughout the paper. In Section III, some background on Lasso and safe screening is provided. In Section IV, we derive a fine characterization of the set of dual cutting half-spaces and present our new safe dome. The relevance of our proposed approach is finally illustrated in Section V via numerical simulations.

II. NOTATIONS

We use the following notational conventions throughout the paper. Boldface uppercase (e.g., A) and lowercase (e.g., x) letters respectively represent matrices and vectors. 0 n denotes the all-zeros vector of R n . ⟨•, •⟩ stands for the canonical inner product between two vectors. The ith entry of a vector x is denoted x(i). Calligraphic letters (e.g., S) are used for sets.

III. BACKGROUND

In this section, we provide some elements of convex analysis for problem [START_REF] Foucart | A Mathematical Introduction to Compressive Sensing[END_REF] and recall the main ingredients underlying the concept of safe screening for Lasso.

A. Dual problem and optimality conditions

We first note that (1) admits at least one minimizer since P (•) is continuous, proper and coercive [START_REF] Beck | First-Order Methods in Optimization[END_REF]Theorem 2.14]. The dual problem of (1) writes as

u ⋆ = arg max u∈U D(u) ≜ 1 2 ∥y∥ 2 2 -1 2 ∥y -u∥ 2 2
(2)

where

U ≜ {u ∈ R m : ∥A T u∥ ∞ ≤ λ} is the so-called dual feasible set, see [21, Appendix A]. Since U is closed and D(•) is strictly concave, problem (2) admits a unique maximizer u ⋆ .
It is known that strong duality holds between problems (1) and ( 2), that is

∀x ∈ R n , ∀u ∈ U : gap(x, u) ≜ P (x) -D(u) ≥ 0 (3)
with equality if and only if (x, u) is primal-dual optimal, see e.g., [START_REF] Beck | First-Order Methods in Optimization[END_REF]Theorem A.2]. Moreover, any primal-dual optimal couple (x ⋆ , u ⋆ ) must verify the following optimality conditions [21, Section 2]:

u ⋆ = y -Ax ⋆ (4)
and,

⟨a i , u ⋆ ⟩ = λ sign(x ⋆ (i)) if x ⋆ (i) ̸ = 0, s ∈ [-λ, λ] otherwise. (5)
for all i = 1, . . . , n. It is easy to see from these conditions that x ⋆ = 0 n is the unique solution of (1) if and only if

λ ≥ λ max ≜ ∥A T y∥ ∞ . (6)

B. Safe screening

Safe screening tests leverage the following consequence of (5):

|⟨a i , u ⋆ ⟩| < λ =⇒ x ⋆ (i) = 0. (7)
If the inequality in the left-hand side of ( 7) is verified for some index i, the corresponding column of A can therefore be safely removed without changing the minimum value of (1). Although computing u ⋆ is (generally) as difficult as solving (1), a weaker version of ( 7) can be obtained if a region R ⊆ R n containing u ⋆ (often called "safe region") is known. [START_REF] Bonnefoy | A dynamic screening principle for the Lasso[END_REF] can then be relaxed to:

max u∈R |⟨a i , u⟩| < λ =⇒ x ⋆ (i) = 0. (8)
From an effectiveness point of view, R should be chosen as small as possible. In particular, if R ⊆ R ′ then obviously

max u∈R ′ |⟨a i , u⟩| < λ =⇒ max u∈R |⟨a i , u⟩| < λ, (9)
that is the screening test built from R will always detect at least as many zeros as that constructed with R ′ . From a complexity point of view, the computational cost of (8) mostly depends on the evaluation of max u∈R |⟨a i , u⟩|. A simple strategy to lower the cost of this operation consists in building safe regions with "appropriate" geometries. Two standard choices are spheres and domes.

Sphere regions are defined by their center c ∈ R m and radius R ≥ 0:

R = B(c, R) ≜ {u ∈ R m : ∥u -c∥ 2 ≤ R}. ( 10
)
Particularizing the left-hand side of (8) to the case where R is a sphere, we obtain:

max u∈B(c,R) |⟨a i , u⟩| = |⟨a i , c⟩| + R∥a i ∥ 2 . ( 11
)
We see that the solution of the maximization problem then admits a simple closed form. Its computation only requires the evaluation of one inner product between a i and c. Another popular choice of geometry is dome region. A dome is defined as the intersection of a sphere and an halfspace, that is

R = D(c, R, g, δ) ≜ B(c, R) ∩ H(g, δ) (12)
where g ∈ R m , δ ∈ R and1

H(g, δ) ≜ {u ∈ R m : ⟨g, u⟩ ≤ δ}. (13)
In this case, the left-hand side of (8) also admits a closed-form solution, see [START_REF] Xiang | Screening tests for Lasso problems[END_REF]Lemma. 3]. More precisely, we have

max u∈D |⟨a i , u⟩| = max max u∈D ⟨a i , u⟩, max u∈D ⟨-a i , u⟩ (14)
and

∀a ∈ R m \ {0 m }, D ̸ = ∅ and max u∈D ⟨a, u⟩ = ⟨a, c⟩ + R∥a∥ 2 f (ψ 1 , ψ 2 ), (15)
where

f (ψ 1 , ψ 2 ) = 1 if ψ 1 ≤ ψ 2 , ψ 1 ψ 2 + 1 -ψ 2 1 1 -ψ 2 2 otherwise ψ 1 = ⟨a, g⟩ ∥a∥ 2 ∥g∥ 2 , ψ 2 = min δ -⟨g, c⟩ R∥g∥ 2 , 1 .
The cost associated to [START_REF] Elvira | Safe squeezing for antisparse coding[END_REF] is mostly dominated by the computation of ⟨g, c⟩, ⟨a i , c⟩ and ⟨a i , g⟩. Dome tests are therefore usually slightly more complex to implement than sphere tests. However, since dome geometry enables smaller safe regions, they potentially lead to much more effective tests.

C. GAP regions

To conclude this section, we provide the expressions of two well-known state-of-the-art safe regions proposed in [START_REF] Fercoq | Mind the duality gap: safer rules for the Lasso[END_REF]. The first region takes the form of a sphere and is known as the "GAP sphere" in the literature. It is defined by the following choice of parameters:

c = u (16) R = 2gap(x, u)) (17)
where (x, u) can be any primal-dual feasible couple. The second has the geometry of a dome and is usually dubbed "GAP dome". It is defined by the following set of parameters:

c = 1 2 (y + u) (18) R = 1 2 ∥y -u∥ 2 (19) g = y -c (20) δ = ⟨g, c⟩ + gap(x, u) -R 2 (21)
where (x, u) can be any primal-dual feasible couple. In the sequel, with a slight abuse of notation, we will respectively denote the GAP sphere and the GAP dome as B gap (x, u) and D gap (x, u) to explicitly emphasize their dependence on the choice of the primal-dual feasible couple (x, u).

Although not proved explicitly in [START_REF] Fercoq | Mind the duality gap: safer rules for the Lasso[END_REF], it can be easily shown (see Appendix B) that

D gap (x, u) ⊆ B gap (x, u). (22)
These two regions have the desirable feature of having a radius (see (32)) that decreases to zero when the couple (x, u) tends to a primal-dual solution. In particular, if (x, u) = (x ⋆ , u ⋆ ), {u ⋆ } = B gap (x ⋆ , u ⋆ ) and the screening tests based on GAP regions reduce to [START_REF] Bonnefoy | A dynamic screening principle for the Lasso[END_REF].

IV. SAFE DOME WITH GENERAL DUAL CUTTING HALF-SPACES

In this section, we present and motivate our new safe dome region. The construction of our dome is based on the set of dual cutting half-spaces H(g, δ):

G ≜ {(g, δ) ∈ R m × R : ⟨g, u⟩ ≤ δ ∀u ∈ U}. ( 23
)
The next lemma provides a canonical characterization of G. A proof can be found in Appendix A-A.

Lemma 1.

G = {(Ax, δ) : x ∈ R n , δ ≥ λ∥x∥ 1 }. ( 24
)
We now expose our proposed new dome region and state a result showing that it is guaranteed to perform at least as well as GAP safe regions presented in Section III-C.

The definition of the proposed dome is encapsulated in the following theorem:

Theorem 1. Let x ∈ R n , u ∈ U and c = 1 2 (y + u) (25) R = 1 2 ∥y -u∥ 2 (26) g = Ax (27) δ = λ∥x∥ 1 (28) Then u ⋆ ∈ D(c, R, g, δ). (29)
A proof of this result can be found in Appendix A-B. The safeness of H(Ax, λ∥x∥ 1 ) can in fact be seen as a simple consequence of the Hölder inequality:

⟨Ax, u ⋆ ⟩ = ⟨x, A T u ⋆ ⟩ ≤ ∥x∥ 1 ∥A T u ⋆ ∥ ∞ ≤ λ∥x∥ 1 ,
where the last inequality follows from dual feasibility of u ⋆ . In the sequel we will therefore refer to the dome defined in Theorem 1 as "Hölder dome". We note that, similarly to the GAP regions, the Hölder dome is completely specified by the choice of a primal-dual feasible couple (x, u). Hereafter, we will use the notation D new (x, u) to emphasize this fact.

We note that the definition of D new (x, u) only differs from that of D gap (x, u) in the choice of the half-space H(g, δ), where the canonical characterization of G in Lemma 1 is directly exploited in the former. Our next result shows that this choice is beneficial regarding the size of the safe region:

Theorem 2. For x ∈ R n , u ∈ U: D new (x, u) ⊆ D gap (x, u). ( 30
)
Moreover, if P (x) < P (0 n ) and (x, u) is not primal-dual optimal, then the inclusion is strict.

A proof of this result can be found in Appendix A-C. Theorem 2 shows that the Hölder dome is guaranteed to be a subset of the GAP dome and sphere. From [START_REF] Herzet | Safe screening tests for Lasso based on firmly non-expansiveness[END_REF], this suggests that screening tests based on our proposed dome are ensured to perform at least as well as the two other safe regions. We also note that the condition "P (x) < P (0 n )", ensuring D new (x, u) ⊂ D gap (x, u), is very mild and verified in many practical setups. It is for example the case when the iterates {x (t) } ∞ t=1 of an optimization procedure, initialized at x (0) = 0 n and monotically decreasing the cost function, are used to define the primal point x used in the construction of the dome.

V. NUMERICAL EXPERIMENT This section reports an empirical study of the relevance of the Hölder dome presented in Section IV. 2 For the two experiments, our simulation setup is as follows. We set (m, n) = (100, 500). For each trial, new realizations of A and y are generated. The observation y is drawn according to a uniform distribution on the m-dimensional unit sphere while A either satisfies i) the entries are i.i.d. realizations of a normal distribution or ii) A has a Toeplitz structure, i.e., columns are shifted versions of a Gaussian curve. The columns of A are then normalized such that ∥a i ∥ 2 = 1 for all i. Expected value of the ratio (31) as a function of the duality gap achieved by (x, u) for the two dictionaries. Each curve corresponds to a value of the ratio λ/λmax (the value is indicated along the line).

a) Radius of safe regions: In this first experiment, we investigate the size difference between the Hölder and GAP domes. More precisely, we evaluate the ratio

Rad(D new (x, u)) Rad(D gap (x, u)) (31)
for different choices of x ∈ R n and u ∈ U, where Rad(S) denotes the radius of the (closed bounded) set S:

Rad(S) ≜ max u,u ′ ∈S 1 2 ∥u ′ -u∥ 2 . (32)
Figure 1 shows the average value of the ratio (31) as a function of the duality gap achieved by (x, u) for the two considered dictionaries and three values of the ratio λ/λ max . Results have been obtained by averaging over 50 trials. As expected (cf. Theorem 2), the ratios are always lower than 1. One also observes that the radius of the proposed Hölder dome is up to 0.6 smaller than the GAP dome. As far as our simulation is concerned, all the curves seem to converge to a ratio close to 0.7 as the dual gap tends to zero.

b) Benchmarks: In this second experiment, we assess the computational gain obtained with the Hölder dome and GAPbased regions. To do so, we compare three variants of FISTA -a standard method to address (1), see [START_REF] Beck | A fast iterative shrinkagethresholding algorithm for linear inverse problems[END_REF]-where the iterations are interleaved with screening tests that leverage i) the GAP sphere, ii) the GAP dome, iii) the Hölder dome. More precisely, at each iteration t, a screening test is carried out with the corresponding safe region obtained with parameters (x (t) , u (t) ) where x (t) refers to the current iterate and u (t) is obtained by dual scaling of y -Ax (t) (see [START_REF] Ghaoui | Safe feature elimination for the Lasso and sparse supervised learning problems[END_REF]Section 3.3]). We use the "Dolan-Moré" performance profiles [START_REF] Dolan | Benchmarking optimization software with performance profiles[END_REF] to assess the performance of the three methods.

We run each method with a prescribed computational budget (the number of floating point operations) on 200 instances of problem [START_REF] Foucart | A Mathematical Introduction to Compressive Sensing[END_REF]. We then evaluate the (empirical) probability ρ(τ ) that a solver achieves a duality gap lower that τ upon completion. For each setup, the budget is adjusted so that ρ(10 -7 ) = 50% for the solver using the Hölder dome.

Figure 2 shows the performance profiles for the two considered dictionaries and different values of the ratio λ/λ max . One sees that, as far as our simulation setup is concerned, implementing the screening test [START_REF] Fercoq | Mind the duality gap: safer rules for the Lasso[END_REF] with the Hölder dome improves quite significantly the average accuracy achieved in all but one setup. These findings support our claim that the Hölder dome leads to more effective test than the one using GAP based-region. The case where the three safe regions lead to comparable results (Gaussian dictionary and λ/λ max = 0.3) has to be understood as follows: even though the Hölder and GAP domes are expected to perform better than the GAP sphere, the profiles result from a compromise between the effectiveness of the test and its complexity. In particular, a study of our simulation results shows that even though the tests are less effective, more iterations are carried (in average) with the GAP sphere in that specific setup, thus leading to a potentially more accurate solution.

VI. CONCLUSION

In this paper, we introduced a novel safe dome region for Lasso that can be used to design safe screening tests. We showed that our proposed dome region is always a (potentially strict) subset of the GAP sphere and dome, two ubiquitous safe regions in the literature. The proposed methodology is shown to allow significant computational gains when solving Lasso with a prescribed computational budget.

  Fig. 1.Expected value of the ratio (31) as a function of the duality gap achieved by (x, u) for the two dictionaries. Each curve corresponds to a value of the ratio λ/λmax (the value is indicated along the line).

Fig. 2 .

 2 Fig. 2. Performance profiles of screening methods with different safe regions. Each row corresponds to a value of λ/λmax. From top to bottom: .3, .5, .8.

Note that when g = 0m, our definition implies that H(g, δ) either reduces to R m if δ ≥ 0 or is empty if δ < 0.

The code is available at https://gitlab.inria.fr/cherzet/holder-safe.

APPENDIX A PROOFS

A. Proof of Lemma 1

Let g ∈ R m and consider the following optimization problem

By strong duality [START_REF] Beck | First-Order Methods in Optimization[END_REF]Equation (12.4) combined with Theorem A.1], we have

where η{•} denotes the indicator function, which is equal to 0 if the statement in the braces is true and +∞ otherwise. Hence, if g = Ax for some x ∈ R n , we have from (34) that δ ⋆ ≤ λ∥x∥ 1 and therefore (Ax, δ) ∈ G for all δ ≥ λ∥x∥ 1 . Conversely, if (g, δ) ∈ G then δ ⋆ ≤ δ < ∞. From (34), we thus have that there exists some x such that g = Ax and δ ≥ λ∥x∥ 1 .

B. Proof of Theorem 1

First remember that a dome is defined as the intersection of the ball B(c, R) and the half-space H(g, H), see [START_REF] Xiang | Fast Lasso screening tests based on correlations[END_REF]. It is then sufficient to show that both B(c, R) and H(g, δ) are safe. Finally, the safeness of B(c, R) and H(g, H) respectively follows from [13, Section 2.2] and Lemma 1.

C. Proof of Theorem 2

Let H new (x, u) and H gap (x, u) respectively denote the halfspace defining D new (x, u) and D gap (x, u). Consider

where c, R are the parameters defined in ( 18) and ( 19), respectively. Since D new (x, u) and D gap (x, u) only differ in the definition of their half-space, it is sufficient to show that u ′ ∈ H gap (x, u), i.e.,

We have

where the inequality follows from the fact that both y and u ′ belong to B(c, R). Moreover, one can write

where the inequalities result from the non-negativity of ∥y -u ′ -Ax∥ 2 2 and the hypothesis that u ′ ∈ H new (x, u). Combining (37) and (38), we finally obtain (36), that is u ′ ∈ H gap (x, u).

Assume now that P (x) < P (0 n ) and (x, u) is not primal-dual optimal. We next show that the strict inclusion D new (x, u) ⊂ D gap (x, u) holds in that case. To this end, it is sufficient to identify some u 0 ∈ R m satisfying

We note that u 0 is well defined since R ̸ = 0 by construction.

We can show that u 0 ∈ D gap (x, u) as follows. We first easily verify that

The result is then proved if u 0 ∈ B(c, R), i.e.,

We can show that (41) holds by distinguishing between two cases. First, if P (x) -D(u) ≥ R 2 , the absolute value in (41) can be removed and the result follows from P (x)

, the same conclusion holds by using the fact P (x) -D(u) > 0 since (x, u) is not primal-dual optimal by hypothesis.

Let us finally show that u 0 / ∈ D new (x, u). We have

where the inequality follows from (40) and (41). Hence u 0 / ∈ D new (x, u) since we have from (38) that any u ′ ∈ D new (x, u) must verify D(u ′ ) ≤ P (x).

APPENDIX B PROOF OF [START_REF] Dolan | Benchmarking optimization software with performance profiles[END_REF] Let u ′ ∈ D gap (x, u). By definition, we thus have

where c, R and g are the parameters of the GAP dome defined in ( 19)- [START_REF] Beck | First-Order Methods in Optimization[END_REF]. We want to show that ∥u ′ -u∥ 2 ≤ 2gap(x, u).

This follows from ∥u ′ -u∥

where the inequality follows from (42), ( 43) and the fact that cu = yc.