Théo Guyard

Cédric Herzet

Clément Elvira

NODE-SCREENING TESTS FOR L0-PENALIZED LEAST-SQUARES PROBLEM WITH SUPPLEMENTARY MATERIAL

Keywords: Sparse approximation, Mixed-integer problems, Branch and bound, Safe screening

We present a novel screening methodology to safely discard irrelevant nodes within a generic branch-and-bound (BnB) algorithm solving the ℓ 0 -penalized least-squares problem. Our contribution is a set of two simple tests to detect sets of feasible vectors that cannot yield optimal solutions. This allows to prune nodes of the BnB exploration tree, thus reducing the overall solution time. One cornerstone of our contribution is a nesting property between tests at different nodes that allows to implement screening at low computational cost. Our work leverages the concept of safe screening, well known for sparsity-inducing convex problems, and some recent advances in this field for ℓ 0 -penalized regression problems.

INTRODUCTION

Finding a sparse representation is a fundamental problem in the field of statistics, machine learning and inverse problems. It consists in decomposing some input vector y ∈ R m as a linear combination of a few columns (dubbed atoms) of a dictionary A ∈ R m×n . This task can be addressed by solving

min x∈R n 1 2 y -Ax 2 2 + λ x 0 (1)
where x 0 counts the number of nonzero entries in x and λ > 0 is a tuning parameter. Unfortunately, problem (1) has proven to be NP-hard in the general case [START_REF] Chen | Complexity of unconstrained ℓ 2ℓ p minimization[END_REF]Th. 3]. This has led researchers to develop sub-optimal procedures to approximate its solution and address large-scale problems. Among the most popular, one can mention greedy algorithms and methodologies based on convex relaxation, see e.g., [START_REF] Foucart | A Mathematical Introduction to Compressive Sensing[END_REF]Sec. 3.2 and Ch. 4]. Sub-optimal procedures are unfortunately only guaranteed to solve [START_REF] Chen | Complexity of unconstrained ℓ 2ℓ p minimization[END_REF] under restrictive conditions that are rarely

The research presented in this paper is reproducible. Code and data are available at https://gitlab.insa-rennes.fr/Theo.Guyard/ bnb-screening.

met when dealing with highly-correlated dictionaries. On the other hand, there has been recently a surge of interest for methods solving (1) exactly, see [START_REF] Miyashiro | Subset selection by Mallows' C p : A mixed integer programming approach[END_REF][START_REF] Bourguignon | Exact sparse approximation problems via mixed-integer programming: Formulations and computational performance[END_REF][START_REF] Bertsimas | Best subset selection via a modern optimization lens[END_REF][START_REF]Ibm ilog cplex optimization studio[END_REF][START_REF] Ben Mhenni | Sparse branch and bound for exact optimization of ℓ 0 -norm penalized least squares[END_REF] to name a few. Many approaches leverage the fact that finding

p ⋆ = min x∈R n 1 2 y -Ax 2 2 + λ x 0 s.t. x ∞ ≤ M (P )
is equivalent to solve [START_REF] Chen | Complexity of unconstrained ℓ 2ℓ p minimization[END_REF], provided that M is chosen large enough. Interestingly, (P ) can be reformulated as a mixedinteger program (MIP) by introducing binary variables encoding the nullity of the entries of x, see e.g., [START_REF] Bourguignon | Exact sparse approximation problems via mixed-integer programming: Formulations and computational performance[END_REF]. Besides, (P ) has been shown to be solvable for moderate-size problems by both commercial solvers [START_REF]Ibm ilog cplex optimization studio[END_REF] and tailored BnB algorithms [START_REF] Ben Mhenni | Sparse branch and bound for exact optimization of ℓ 0 -norm penalized least squares[END_REF].

In a recent paper, Atamtürk and Gómez extended the notion of safe screening introduced by El Ghaoui et al. in [START_REF] Ghaoui | Safe feature elimination for the lasso and sparse supervised learning problems[END_REF] from sparsity-promoting convex problems to non-convex ℓ 0penalized problems. In particular, they introduced a new methodology that allows to detect (some of) the positions of zero and non-zero entries in the minimizers of a particular ℓ 0 -penalized problem [START_REF] Atamturk | Safe screening rules for l0-regression from perspective relaxations[END_REF]. Their methodology is used as a preprocessing step of any algorithmic procedure and allows to reduce the problem dimensionality.

In this paper, we make one step forward in the development of numerical methods addressing large-scale ℓ 0penalized problems by proposing node-screening rules that can be implemented within any BnB algorithm. In contrast to [START_REF] Atamturk | Safe screening rules for l0-regression from perspective relaxations[END_REF], we emphasize the existence of a nesting property between screening tests at different nodes. This enables to (potentially) prune multiple nodes at any step of the optimization process with marginal cost.

Our exposition is organized as follows. Section 2 gathers the main notations used in the paper. In Section 3, we describe a BnB algorithm tailored to (P ). Section 4 presents our new node-screening tests and explains how to implement them efficiently within the BnB process. In Section 5, we assess the performance of our method on synthetic data. All the proofs are postponed to Appendix A.

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 denotes the all-zeros vector. Since the dimension will usually be clear from the context, it is omitted in the notation. The ith column of a matrix A is denoted a i . Similarly, the ith entry of a vector x is denoted x i . Calligraphic letters (e.g., S) are used to denote sets and the notation | • | refers to their cardinality. If S ⊆ {1, . . . , n} and x ∈ R n , x S denotes to the restriction of x to its elements indexed by S. Similarly, A S corresponds to the restriction of A ∈ R m×n to its columns indexed by S.

BRANCH-AND-BOUND PROCEDURES

Branch-and-bound procedures refer to an algorithmic solution to address MIPs, among others [START_REF] Eugene | Branch-andbound methods: A survey[END_REF]. It consists in implicitly enumerating all feasible solutions and applying pruning rules to discard irrelevant candidates. When particularized to problem (P ), it can be interpreted as a search tree where a new decision regarding the nullity of an entry of the variable x is taken at each node as illustrated in Figure 1a. Formally, we define a node as a triplet ν = (S 0 , S 1 , S) where : i) S 0 and S 1 contain the indices of the entries of x which are forced to be zero and non-zero, respectively; ii) S gathers all the entries of x for which no decision has been taken at this stage of the decision tree.

The BnB algorithm reads as follows: starting from node ν = (∅, ∅, {1, . . . , n}), the method alternates between processing the current node (bounding step) and selecting a new node (branching step). The algorithm identifies the global minimum in a finite number of steps with a worst-case complexity equal to an exhaustive search. In practice, its efficiency depends on both the ability to process nodes quickly and the number of nodes processed. We review below specific choices for these two steps tailored to problem (P ).

Bounding step

When processing node ν = (S 0 , S 1 , S), we prospect if any x with zeros on S 0 and nonzero values on S 1 can yield a global minimizer of (P ). To that end, we look for the smallest objective value achieved by feasible candidates with respect to these constraints, i.e., the value of

p ν = min x∈R n 1 2 y -Ax 2 2 + λ x S 0 + λ|S 1 | s.t.
x ∞ ≤ M and x S0 = 0.

(P ν )
One verifies that p ν ≥ p ⋆ since all minimizers of (P ν ) are also feasible for (P ). Moreover, equality holds whenever the constraints given by S 0 and S 1 match the configuration of one of the minimizers of (P ).

If p ν > p ⋆ , ν can be pruned from the tree since no vector x verifying the constraints defined at this node (and therefore at any sub-nodes) can yield an optimal solution. Unfortunately, the latter pruning rule is of poor practical interest since p ⋆ is not available. Moreover evaluating p ν when S = ∅ is also a combinatorial problem. To circumvent these problems, a relaxed version of the rule is devised: let p ν l and p u be respectively lower and upper bounds on p ν and p ⋆ . Then, a sufficient condition to prune node ν reads p ν l > p u . To obtain p ν l , a standard approach is to consider the following relaxation of (P ν ):

p ν l = min x∈R n 1 2 y -Ax 2 2 + λ M x S 1 + λ|S 1 | s.t. x ∞ ≤ M and x S0 = 0 (P ν l )
where the ℓ 0 -penalty term has been replaced by an ℓ 1 -norm. Interestingly, (P ν l ) is a constrained LASSO problem [START_REF] Gaines | Algorithms for fitting the constrained lasso[END_REF] and can be solved (to machine precision) in polynomial time by using one of the many methods suitable for this class of problems [START_REF] Parikh | Proximal algorithms[END_REF][START_REF] Lee | Efficient sparse coding algorithms[END_REF].

The upper bound p u can be obtained by keeping track of the best known objective value of (P ) during the BnB process. More precisely, we construct a feasible solution of (P ν ) at each node to obtain p ν u . The best known upper bound is then updated as p u ← min(p u , p ν u ). During the BnB procedure, p u converges toward p ⋆ and relaxation are strengthened as new variables are fixed, allowing to prune nodes more efficiently.

Branching step

If node ν = (S 0 , S 1 , S) has not been pruned during the bounding step, the tree exploration goes on. An index i ∈ S is selected according to some branching rule and two direct sub-nodes are created below ν by imposing either "x i = 0" or "x i = 0". Finally, when all nodes have been explored or pruned, the BnB algorithm stops and any candidate yielding the best upper bound p u is a minimizer of (P ).

NODE-SCREENING TESTS

In this section, we present our new node-screening tests. They aim at identifying, with marginal cost, nodes of the search tree that cannot yield a global minimum of (P ).

Dual properties

The crux of our procedure is a connection between the Fenchel dual problem of (P ν l ) at two consecutive nodes. Prior to expose this result, let us define for all u ∈ R m and i ∈ {1, . . . , n} three families of pivot values as

γ i (u) M (|a T i u| -λ M ) γ 0 i (u) M [|a T i u| -λ M ] + γ 1 i (u) M [ λ M -|a T i u|] + (2)
ν (0) ν (1) ν (3) ν (4)
ν (2) ν (5) ν (6) xi 1 = 0

xi 2 = 0 xi 2 = 0 xi 1 = 0 xi 2 = 0 xi 2 = 0 (a) ν (0) ν (1) ν (3) ν (4)
ν (2) ν (5) ν (6) xi 1 = 0 , test (6b) is passed for entries i1 and i2; one can thus directly switch to the sub-node including constraints "xi 1 = 0" and "xi 2 = 0", namely ν (3) . The shaded nodes need not be explored.

xi 2 = 0 xi 2 = 0 xi 1 = 0 xi 2 = 0 xi 2 = 0 Node-screening Set xi 1 = 0 Set xi 2 = 0 (b)
where [z] + max(0, z) for all scalars z. We now express the Fenchel dual of (P ν l ) with respect to these quantities. Proposition 1. The Fenchel dual of (P ν l ) is given by

d ν l = max u∈R m D ν l (u) 1 2 y 2 2 -1 2 y -u 2 2 -i∈ S γ 0 i (u) -i∈S1 γ i (u) (D ν l )
and strong duality holds for

(P ν l )-(D ν l ), i.e., p ν l = d ν l . More- over, if (x ⋆ l , u ⋆ l ) is a couple of primal-dual solutions, one has u ⋆ l = y -Ax ⋆ l . (3)
Hence, at a given node ν, the dual objective of (P ν l ) is the sum of a term common to all nodes and some well-chosen pivot values. Interestingly, the dual objective functions between two consecutive nodes only differ from one pivot value as shown in the following result:

Corollary 1. Let ν = (S 0 , S 1 , S) and ℓ ∈ S, then ∀u ∈ R m , D ν∪{x ℓ =0} l (u) = D ν l (u) + γ 0 ℓ (u) (4a)
D ν∪{x ℓ =0} l (u) = D ν l (u) + γ 1 ℓ (u) (4b)
where ν ∪ {x ℓ = 0} and ν ∪ {x ℓ = 0} denote the two direct sub-nodes of ν where index ℓ has been swapped from S to S 0 or S 1 .

Node-screening tests

We now expose our proposed screening strategy to identify nodes of the tree that provably cannot yield a global minimizer of (P ). Let ν be a node and p u an upper bound on p ⋆ . We have by strong duality between (

P ν l )-(D ν l ) that ∀u ∈ R m , D ν l (u) ≤ d ν l = p ν l ≤ p ν . (5)
Hence, combining [START_REF] Bertsimas | Best subset selection via a modern optimization lens[END_REF] with Corollary 1 leads to the next result:

Proposition 2. Let ℓ ∈ S be some index. Then, ∀u ∈ R m , D ν l (u) + γ 0 ℓ (u) > p u =⇒ p ν∪{x ℓ =0} > p ⋆ (6a) D ν l (u) + γ 1 ℓ (u) > p u =⇒ p ν∪{x ℓ =0} > p ⋆ . ( 6b
)
Stated otherwise, Proposition 2 describes a simple procedure to identify some sub-nodes of ν that cannot yield an optimal solution of (P ). In particular, if both (6a) and (6b) pass for a given index, no feasible vector with respect to the constraints defined at ν is a minimizer of (P ) (ν can therefore be pruned).

Our proposed procedure differs from the pruning methodology described in Section 3 in several aspects. Performing a test only requires the evaluation of one single inner product. They can therefore be implemented at marginal cost compared to the overall cost of the bounding step. Very importantly, they also inherit from the following nesting property: Corollary 2. Let ν = (S 0 , S 1 , S) be a node. Then, if test (6a) or (6b) passes for index ℓ ∈ S, then it also passes for any subnode ν ′ = (S ′ 0 , S ′ 1 , S′ ) ⊂ ν such that ℓ ∈ S′ . In particular, Corollary 2 has the following consequence. Assume that two distinct indexes ℓ and ℓ ′ pass test (6a) at node ν. Then index ℓ ′ will also pass (6a) at node ν ∪{x ℓ = 0}. The same consequence holds for test (6b) and node ν ∪ {x ℓ = 0}. In other words, if several node-screening tests pass at a given node, one can simultaneously prune several sub-nodes of ν, as illustrated in Figure 1b. This is in contrast with the bounding procedure described in Section 3 which has to process each sub-node individually before applying any potential pruning operation.

Implementation considerations

Implementing node-screening tests described by Proposition 2 requires the knowledge of an upper bound p u of p ⋆ and a suitable u ∈ R m , i.e., as close as possible to the maximizer of (D ν l ). The value of p u can be obtained at no additional cost since the standard implementation of BnB already requires storing such valid upper bounds on p ⋆ . To obtain a relevant candidate for u, we suggest the following procedure: assuming the method used to solve (P ν l ) generates a sequence of iterates {x (t) } t∈N that converges to a global minimizer, we set

∀ t ∈ N, u (t) = y -Ax (t) . (7)
This choice enjoys two desirable properties. First, the sequence {u (t) } t∈N converges toward a maximizer of (D ν l ) as a consequence of the optimality condition (3). Second, both u (t) and A T u (t) are already evaluated by most solvers as they correspond to the residual error and the (negative) gradient of the least-squares term of the objective function, respectively. Thus, the computational cost of evaluating the screening tests at all undecided entries is marginal compared to the cost needed to address (P ν l ). The latter choice for u (t) suggests performing node-screening tests during the bounding step. Hence, when some entries passes the test at node ν, the BnB algorithm immediately switches to some sub-node, without solving (P ν l ) at high precision.

NUMERICAL RESULTS

We finally report simulation results illustrating the relevance of the node-screening methodology on two different setups.

Experimental setups

For each trial, we generate a new realization of A ∈ R m×n and y ∈ R m as follows. In the Gaussian setup, we set (m, n) = (500, 1000) and the entries of A are i.i.d. realizations of a normal distribution. In the Toeplitz setup, we set (m, n) = (500, 300) and the first column of A contains a sampled sinc function. The other columns are obtained by shifting the entries in a row-wise fashion so that A inherits from a Toeplitz structure. In both setups, the columns of A are normalized to one. To obtain y, we first sample a k-sparse vector x 0 ∈ R n with uniformly distributed non-zero entries. Each non-zero entry is set to s(1 + |a|), where s ∈ {-1, +1} is a random sign and a is a realization of the normal distribution. In our experiment, we chose k ∈ {5, 7, 9}. Finally, the observation is constructed as y = Ax 0 + ǫ where the entries of ǫ are i.i.d. realizations of a centered Gaussian distribution with standard deviation σ = Ax 0 2 / √ 10m. Such a design leads to a SNR of 10dB in average [START_REF] Don | Signal-to-noise ratio[END_REF]. We tune λ statistically as in [START_REF] Soussen | From Bernoulli-Gaussian deconvolution to sparse signal restoration[END_REF], i.e., by setting λ = 2σ 2 log(n/k -1). Finally, we empirically set M = 1.5 A T y ∞ as advised in [START_REF] Ben Mhenni | Sparse branch and bound for exact optimization of ℓ 0 -norm penalized least squares[END_REF].

We compare three methods that address (P ): i) MIP, that uses CPLEX [START_REF]Ibm ilog cplex optimization studio[END_REF], a state-of-the-art commercial MIP solver; ii) BnB, the algorithm presented in [START_REF] Ben Mhenni | Sparse branch and bound for exact optimization of ℓ 0 -norm penalized least squares[END_REF], which is (up to our knowledge) the fastest BnB algorithm tailored for (P ); iii) BnB+scr which corresponds to BnB enhanced with the node-screening methodology presented in Section 4. Note that both BnB and BnB+scr leverage an efficient implementation of the Active-Set algorithm [START_REF] Wright | Numerical optimization[END_REF]Sec. 16.5] to solve (P ν l ) and the branching rule described in [START_REF] Ben Mhenni | Sparse branch and bound for exact optimization of ℓ 0 -norm penalized least squares[END_REF]Sec. 2.2]. Experiments are run on a MacOS with an i7 CPU, clocked at 2.2 GHz and with 8Go of RAM. We restrict calculations on a single core to avoid bias due to parallelization capabilities. The Academic Version 20.1 of CPLEX is used and both BnB and BnB+scr are implemented in Julia v1.5 [START_REF] Bezanson | Julia: A fast dynamic language for technical computing[END_REF]. Results are averaged over 100 instances of problem (P ).

Method comparison

Table 1 compares the average number of nodes treated (i.e., the number of relaxations (P ν l ) solved at machine precision) and the solution time for the three methods and all simulation setups. One observes that BnB+scr outperforms the two other methods on all scenarii and all figures of merit. We also note that, compared to BnB, the reduction in the solution time is more significant than the reduction in the number of processed nodes. A thorough examination of our results indicates that the bounding step is performed all the faster as many variables are fixed to zero in (P ν l ). Our node-screening methodology allows to reach quickly nodes where the bounding step is performed with a lower computational cost.

As a final remark, we mention that MIP relies on an efficient C++ implementation while BnB and BnB+scr are implemented in Julia. As C++ usually runs faster than Julia, there is still room for improvements in the comparison of BnB and BnB+scr with MIP.

CONCLUSION

In this paper, we presented a novel node-screening methodology aiming at accelerating the resolution of the ℓ 0 -penalized least-squares problem with a branch-and-bound solver. Our contribution leverages a nesting property between the nodescreening tests at two consecutive nodes. Our method leads to significant improvements in terms of number of nodes explored and resolution time on two simulated datasets.

A. PROOFS

This appendix gathers the proofs of the results derived in Section 4. We refer to [START_REF] Ben Mhenni | Sparse branch and bound for exact optimization of ℓ 0 -norm penalized least squares[END_REF] for proofs regarding Section 3.

A.1. Proof of Proposition 1

Our proof of Proposition 1 leverages the Fenchel conjugate of a function f and denoted f * . In particular, we first state the following technical lemma whose proof is postponed to the end of the section

Lemma 1. Define for all z ∈ R m and x ∈ R n f 1 (z) 1 2 y -z 2 2 + ε (8a) f 2 (x) λ M x S 1 + η {x ′ : x ′ S ′ =0} (x) + η B∞(M) (x) (8b) Then, for all u ∈ R m and v ∈ R n f * 1 (u) = 1 2 ( y + u 2 2 -y 2 2 ) -ε (9a) f * 2 (v) = i∈S M [|v i | -λ M ] + + M v S ′′ 1 . (9b)
In the latter result, ε is a scalar, (S, S ′ , S ′′ ) is a partition of {1, . . . , n}, B ∞ (M ) denotes the ℓ ∞ -ball of R n centered at 0 with radius M , η A denotes the indicator function of set A ⊆ R n defined for all x ∈ R n by η A (x) = 0 if x ∈ A and +∞ otherwise. ). Using the functions defined in Lemma 1 with ε = λ|S 1 |, S = S, S ′ = S 0 and S ′′ = S 1 , the relaxed problem (P ν l ) can be rewritten as

min x∈R n f 1 (Ax) + f 2 (x). (10)
Then, the Fenchel dual of ( 10) is given by (see [START_REF] Heinz | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF]Definition 15.19]1 )

max u∈R m -f * 1 (-u) -f * 2 (A T u). (11)
One concludes the proof by remarking that for all u ∈ R m ,

f * 2 (A T u) -ε = i∈ S γ 0 i (u) + M A T S1 u 1 -M M λ|S 1 | = i∈ S γ 0 i (u) + i∈S1 γ i (u).
b) Strong duality. Strong duality holds as a consequence of [START_REF] Heinz | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF]Proposition 15.24]. More particularly, one easily verifies that the condition in item vii) is fulfilled since the functions f 1 and f 2 are proper and continuous. c) Relation (3). Let (x ν l , u ν ) be a couple of primal-dual solution of (P ν l )-(D ν l ). Since strong duality holds, we have by item ii) of [START_REF] Heinz | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF]Theorem 19

.1] that 2 -u ν ∈ ∂f 1 (Ax ν l ) (12)
where ∂f 1 (Ax ν l ) denotes the sub-differential of f 1 evaluated at Ax ν l . One finally obtains (1) by noticing that f 1 is differentiable at Ax ν l so that the sub-differential reduces to the singleton {∇f 1 (Ax ν l )}.

A.2. Proof of Lemma 1.

The Fenchel conjugate of

f 1 evaluated at u ∈ R m is defined as f * 1 (u) = max z∈R m u T z -f 1 (z). (13)
One easily sees that ( 13) is an unconstrained concave optimization problem whose objective function is differentiable.

We then obtain (8a) by noticing that the maximum is attained at z ⋆ = y + u.

Let v ∈ R n . By definition of f * 2 and using the fact that f 2 (x) = +∞ for all x ∈ R n such that x S ′ = 0, We have

f * 2 (v) = max {x∈R n : x ∞ ≤M } v T x -λ M x S 1 = i∈S max {x∈R : |x|≤M} v i x i -λ M |x i | + max {x S ′′ ∈R |S ′′ | : x S ′′ ∞ ≤M} v T S ′′ x S ′′ .
where the optimization problem can be split since it is linear and S, S ′′ have non empty intersection by definition. Let i ∈ S and consider the problem

x ⋆ i ∈ arg max {x∈R : |x|≤M } v i x i -λ M |x i |. (14)
We let the reader check that x ⋆ i defined by

x ⋆ i = 0 if |v i | -λ M ≤ 0 sign(v i )M otherwise ( 15
)
is the maximizer of ( 14). One finally expresses the maximum as a sum of pivot values by injecting the value of x ⋆ i in the objective function. Let ν = (S 0 , S 1 , S) be a node and i be some element of S such that ν ∪ {x i = 0} defines a child node. Using (D ν l ), we have for all u ∈ R m

D ν∪{xi=0} l (u) -D ν l (u) = i ′ ∈ S γ 0 i ′ (u) - i ′ ∈ S\{i} γ 0 i ′ (u) = γ 0 i (u).
Similar calculations lead for all u ∈ R m to

D ν∪{xi =0} l (u) -D ν l (u) = γ 0 i (u) -γ i (u) = γ 1 i (u)
where the last line uses the relation [u] + -[-u] + = u that hold for all scalar u.

A.4. Proof of Corollary 2

Let ν = (S 0 , S 1 , S) be a node. We first state the following lemma which can easily be proved by induction using (4a) and (4b).

Lemma 2. Let ν ′ = (S ′ 0 , S ′ 1 , S′ ) be a child node of ν. Then, for all u ∈ R m

D ν ′ l (u) = D ν l (u) + i∈S ′ 0 \S0 γ 0 i (u) + i∈S ′ 1 \S0 γ 1 i (u). ( 16
)
We now prove Corollary 2. Let ℓ ∈ S be some index such that test (6a) or (6b) passes at node ν. To easier our exposition, we only prove the result for test (6a) as the same rationale can be used for test (6b). Hence, assume that test (6a) passes for index ℓ at node ν, i.e., that D ν l (u) + γ 1 ℓ (u) > p u .

Let ν ′ = (S ′ 0 , S ′ 1 , S′ ) be a child node of ν such that ℓ / ∈ S′ . Using Lemma 2, we have

D ν ′ l (u) = D ν l (u) + i∈S ′ 0 \S0 γ 0 i (u) + i∈S ′ 1 \S0 γ 1 i (u). ( 18
)
Since the pivots values {γ 0 i (u)} n i=1 {γ 1 i (u)} n i=1 are all nonnegative by construction, we necessarily have D ν ′ l (u) ≥ D ν l (u). Hence the test (6a) also passes for index ℓ at node ν ′ .

Fig. 1 :

 1 Fig.1: First nodes of the BnB tree. The root node ν (0) corresponds to problem (P ) and each sub-node corresponds to a sub-problem (P ν ) with different fixed variables. (a) Standard implementation of a BnB where all nodes are processed. (b) Impact of applying node-screening tests on the BnB search tree: at node ν (0) , test (6b) is passed for entries i1 and i2; one can thus directly switch to the sub-node including constraints "xi 1 = 0" and "xi 2 = 0", namely ν(3) . The shaded nodes need not be explored.

  647 106.5 0 10,461 79.3 0 7,881 52.2 0 Toeplitz 9 80,694 353.4 50 47,828 346.4 48 41,166 267.0 40

We now use Lemma 1

 1 to prove : a) the formulation of the dual problem (D ν l ), b) the strong-duality relation linking (P ν l )-(D ν l ) and c) the relation (3). In the sequel, we let ν = (S 0 , S 1 , S) be a given node. a) Dual problem (D ν l

A. 3 .

 3 Second, see thatmax {x S ′′ ∈R |S ′′ | : x S ′′ ∞ ≤M} v T S ′′ x S ′′ = M × max {x S ′′ ∈R |S ′′ | : x S ′′ ∞ ≤1} v T S ′′ x S ′′ = M v S ′′ 1where the last equality holds since one recognizes the Fenchel dual of the indicator function of the unit-ball with respect to the ℓ ∞ -norm[18, item iv) in Example 13.3] in the penultimate line. Proof of Corollary 1

Table 1 :

 1 Number of nodes explored (Nds), solution time in seconds (T) and number of instances not solved within 1,000 seconds (F).

Note that, unlike[START_REF] Heinz | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF] Definition 15.19], we use the formulation of the dual problem that involves a maximization problem.

Again, we note that[START_REF] Parikh | Proximal algorithms[END_REF] involves the opposite of u ν since the authors consider the reformulation of the dual as a minimization problem.


Théo Guyard

Cédric Herzet

Clément Elvira

SCREEN & RELAX: ACCELERATING THE RESOLUTION OF ELASTIC-NET BY SAFE IDENTIFICATION OF THE SOLUTION SUPPORT

Keywords: Convex optimization, Sparsity, Safe screening, Acceleration techniques, Constraint relaxation

In this paper, we propose a procedure to accelerate the resolution of the well-known "Elastic-Net" problem. Our procedure is based on the (partial) identification of the solution support and the reformulation of the original problem into a problem of reduced dimension. The identification of the support leverages the novel concept of "safe relaxing" where one aims at identifying non-zero coefficients of the solution. It can be viewed as a dual approach to "safe screening" introduced in the last decade and allowing to reduce the problem dimension using the identification of zero coefficients of the solution. We show numerically that combining both methodologies in a "Screen & Relax" strategy enables to significantly improve the tradeoff between complexity and accuracy achievable by standard resolution techniques.

INTRODUCTION

Sparse decomposition aims at finding some approximation of a vector y ∈ R m as the linear combination of a few columns (dubbed atoms) of a dictionary A = [a 1 , . . . , a n ] ∈ R m×n . Unfortunately, identifying the sparsest decomposition of a vector according to some accuracy criterion often turns out to be a combinatorial problem [START_REF] Foucart | A Mathematical Introduction to Compressive Sensing[END_REF]Sec. 2.3]. A standard strategy to circumvent this issue consists in approximating this ideal decomposition as the solution of a problem of the form

x ∈ arg min x∈R n 1 2 y -Ax 2 2 + Ω(x) (1)
where Ω : R n → R + is some sparsity-inducing convex regularizer. The common choice Ω(x) = λ x 1 for some λ > 0 leads to the well-known "Lasso" problem and has been extensively studied in the literature [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF][START_REF] Scott Shaobing Chen | Atomic decomposition by Basis Pursuit[END_REF]. Another popular choice

The research presented in this paper is reproducible. Code and data are available at https://gitlab.insa-rennes.fr/Theo.Guyard/ screen-and-relax is Ω(x) = λ x 1 + ε 2 x 2 2 for some parameters λ > 0, ε > 0. In this case, problem (1) is known as "Elastic-Net" and is popular in many applicative domains because its solution enjoys desirable statistical properties [START_REF] Zou | Regularization and variable selection via the elastic net[END_REF].

Because of its clear practical interest, many contributions of the literature have proposed efficient solving procedures for [START_REF] Foucart | A Mathematical Introduction to Compressive Sensing[END_REF], see e.g., [START_REF] Mário | Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems[END_REF][START_REF] Parikh | Proximal algorithms[END_REF][START_REF] Jin | Elastic-net regularization: error estimates and active set methods[END_REF][START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF]. Of particular interest in this paper is the "safe screening" acceleration technique proposed by El Ghaoui et al. in [START_REF] Ghaoui | Safe feature elimination for the lasso and sparse supervised learning problems[END_REF]. Safe screening consists in performing simple tests to identify the zero elements of the minimizers of an optimization problem. This knowledge can then be exploited to reduce the dimensionality of the problem by discarding the atoms of the dictionary weighted by zero safely, i.e., without changing the solution set. Over the past decade, many authors have identified safe screening as a simple procedure to significantly speed up the resolution of many optimization problems, see e.g., [START_REF] Fercoq | Mind the duality gap: safer rules for the lasso[END_REF][START_REF] Xiang | Screening tests for lasso problems[END_REF][START_REF] Liu | Safe screening with variational inequalities and its application to lasso[END_REF][START_REF] Wang | Lasso screening rules via dual polytope projection[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].

In this paper, we introduce a dual approach to safe screening, dubbed "safe relaxing". We focus on a specific instance of problem [START_REF] Foucart | A Mathematical Introduction to Compressive Sensing[END_REF], namely the non-negative version of Elastic-Net. Our method aims at identifying the position of the nonzero coefficients of the minimizer of this problem. We show that, similarly to screening, this knowledge can be exploited to safely reduce the dimensionality of the target problem and accelerate its resolution. We use the terminology "relaxing" as the reduction of the problem dimensionality results from the relaxation of some constraints.

The rest of the paper is organized as follows. The target problem is defined in Sec. 2. The concepts of "safe screening" and "safe relaxing" are presented in Sec. 3 and 4. In Sec. 5, we combine screening and relaxing methodologies in a "Screen & Relax" strategy. A numerical evaluation of the proposed method is finally carried out in Sec. 6.

Notations. Boldface uppercase (e.g., A) and lowercase (e.g., x) letters respectively represent matrices and vectors. 0 n and 1 n stand for the n-dimensional all-zeros and all-ones vectors. I represents the identity matrix whose dimension is usually clear from the context. The ith component of x is arXiv:2110.07281v1 [math.OC] 14 Oct 2021 denoted x(i). Calligraphic letters (e.g., I) are used to denote sets and the notation I refers to the complementary set of I. We denote x I the restriction of x to its elements indexed by I and A I corresponds to the restriction of A to its atoms indexed by I. Finally, for any real symmetric positive definite matrix M, we let x 2 M x T Mx. Throughout this paper, we assume without loss of generality that the columns of A are normalized to one.

TARGET PROBLEM

We focus on the non-negative version of Elastic-Net:

min x≥0n P (x) 1 2 y -Ax 2 2 + λ T x + ε 2 x 2 2
(2-P)

where λ ∈ R n + and ε > 0. We note the standard formulation of Elastic-Net can be seen as a particular case of (2-P) (see e.g., [START_REF] James Xiang | Screening tests for lasso problems[END_REF]Sec. 2]). Since P (x) is continuous, coercive and strongly convex, (2-P) admits a unique minimizer x . The goal of this paper is to accelerate the resolution of (2-P) by identifying the position of the zero and non-zero coefficients of x . Our strategy leverages the primal-dual optimality conditions described below.

The dual problem associated to (2-P) reads

max u∈R m 1 2 y 2 2 -1 2 y -u 2 2 -1 2ε [A T u -λ] + 2 2 (3-D)
where [x] + max(0 n , x) and with the maximum taken component-wise, see [START_REF] Dünner | Primal-dual rates and certificates[END_REF]. Similarly to (2-P), the cost function in (3-D) is continuous, coercive and strongly concave. Problem (3-D) thus admits a unique maximizer u . By Slater's constraint qualification, strong duality holds between (2-P) and (3-D). As a consequence, a couple (x , u ) is a primal-dual solution of (2-P)-(3-D) if and only if

u = y -Ax (4) x = ε -1 [A T u -λ] + . (5)
See [18, Prop. 5.1.5 and 5.3.1] for technical details. In particular, letting J { : x ( ) > 0}, we also easily obtain from ( 4)-( 5) that

x J = (A T J A J + εI) -1 (A T J y -λ J ). (6)

SAFE SCREENING

The goal of safe screening is to identify the zero components of x in order to transform (2-P) into a problem of reduced dimension and speed-up its resolution. More precisely, let

I ⊆ { : x ( ) = 0} (7)
denote a subset of the zero components of x . Then, (2-P) is equivalent to

x = arg min

x∈R n P (x) s.t. x I ≥ 0 nr x I = 0 n-nr (8)
where n r card(I). This problem can also be rewritten more explicitly as

x I = arg min xr≥0n r 1 2 y -A r x r 2 2 + λ T r x r + ε 2 x r 2 2
(9a)

x I = 0 n-nr (9b)
where A r A I ∈ R m×nr and λ r λ I ∈ R nr . In the above formulation, we note that (9a) has the same structure as (2-P) but the dimension of the optimization domain is n r in the former against n in the latter. Hence, if n r n, huge computational savings can potentially be achieved by considering the reduced formulation (9a) instead of (2-P).

Safe screening tests aim at identifying some subset I ⊆ {1, . . . , n} verifying [START_REF] Jin | Elastic-net regularization: error estimates and active set methods[END_REF]. The design of such tests usually leverages the optimality conditions of the problem at stake. As far as (2-P) is concerned, we have from ( 5) that

∀ ∈ {1, . . . , n} : a T u ≤ λ( ) ⇐⇒ x ( ) = 0. (10)
The left-hand side of the equivalence is thus a sufficient condition for x ( ) to be equal to zero. Unfortunately, computing u is usually as difficult as solving primal problem (2-P) and ( 10) is therefore of poor practical interest.

This difficulty can be circumvented by using "safe regions", that is subsets of the dual domain that are guaranteed to contain u . For example, assuming that u belongs to a safe spherical regions, that is

u ∈ S(c, r) {u ∈ R m : u -c 2 ≤ r}, (11)
test [START_REF] Fercoq | Mind the duality gap: safer rules for the lasso[END_REF] can be relaxed as

max u∈S(c,r) a T u = a T c + r ≤ λ( ) =⇒ x ( ) = 0. ( 12
)
Methods to construct safe spheres have been extensively studied in the literature over the past decade, see e.g., [9-12, 14, 15, 19, 20].

SAFE RELAXING

In this section, we expose our "safe relaxing" methodology.

In contrast to safe screening, our goal is to identify the positions of the non-zero coefficients of x . We show that the identification of these components can also lead to an equivalent problem of reduced dimension. More precisely, let

J ⊆ { : x ( ) > 0} (13)
denote a subset of non-zero components of x . Problem (2-P) can then be equivalently expressed as

x = arg min

x∈R n P (x) s.t. x J ≥ 0 nr x J ∈ R n-nr (14)
where n r card(J ). We note that the constraints on the elements in J have been totally removed in [START_REF] Herzet | Safe screening tests for LASSO based on firmly non-expansiveness[END_REF]. This is in contrast with screening where the elements x I were set to zero. Similarly to screening, this relaxation allows to express (2-P) as a problem of reduced dimension.

Let us first notice that the restriction of ( 14) to x J can be written as :

x J = arg min x J ≥0n r min x J ∈R n-nr P (x) . ( 15
)
Since the inner minimization in ( 15) is a strongly-convex quadratic problem, it admits the unique optimizer

x J = Bx J + b (16)
where

B -(A T J A J + εI) -1 A T J A J (17a) b -(A T J A J + εI) -1 A T J y -λ J . (17b)
Plugging ( 16) into the cost function P (x) then leads to the following equivalent formulation of (2-P) :

x J = arg min xr≥0n r 1 2 y r -A r x r 2 2 + λ T r x r + ε 2 x r 2 M (18a) x J = Bx J + b (18b)
where

A r A J + A J B (19a) λ r λ J + B T (λ J + εb) (19b) y r y -A J b (19c) M I + B T B. (19d)
Similarly to screening, the reduced problem (18a) has the same mathematical structure as (2-P). The definition of the parameters (A r , λ r , y r , M) in (18a) differs however quite significantly from those in (9a). In particular, whereas the construction of A r only requires to remove some columns from A in (9a), it involves a matrix inversion in (18a). This operation introduces some complexity overhead and must therefore be performed with care as discussed in Sec. 6. Optimality condition (5) can be exploited to identify some subset J verifying [START_REF] Wang | Lasso screening rules via dual polytope projection[END_REF]. In particular, we have

∀ ∈ {1, . . . , n} : a T u > λ( ) ⇐⇒ x ( ) > 0. (20)
Similarly to screening, we can resort to a safe sphere [START_REF] Xiang | Screening tests for lasso problems[END_REF] to obtain a weaker, yet practical, version of [START_REF] Wang | Lasso screening rules via dual polytope projection[END_REF]. This leads to the following relaxing test:

min u∈S(c,r) a T u = a T c -r > λ( ) =⇒ x ( ) > 0. (21) Algorithm 1: "Screen & Relax" solving procedure Input: x (0) , A, y, λ, ε 1 t ← 1 2 (I, J ) ← (∅, ∅) 3 (A r , λ r , y r , M) ← (A, y, λ, I) 4 while convergence criterion is not met do 5 K ← I ∪ J 6 x (t) K ← DescentStep(x (t-1) K , A r , y r , λ r , M, ε) 7
Compute a new safe sphere S(c (t) , r

SCREEN AND RELAX

The "screening" and "relaxing" procedures described in Sec. 3 and 4 can obviously be combined in a "Screen & Relax" strategy to benefit from the identification of both zero and non-zero components of x . More precisely, let I and J be subsets respectively verifying [START_REF] Jin | Elastic-net regularization: error estimates and active set methods[END_REF] and ( 13) and let K (I ∪ J ) be the set of components of x already identified as zero or non-zero. Applying the same reasoning as in Sec. 3 and 4, we then obtain that (2-P) is equivalent to

x K = arg min xr≥0n r 1 2 y r -A r x r 2 2 + λ T r x r + ε 2 x r 2 M (22a) x J = Bx K + b (22b) x I = 0 card(I) , (22c)
where the parameters (A r , λ r , y r , M) are defined as in (17a)-(19d) by using K instead of J . The dimension of reduced problem (22a) is equal to n r = card(K) and thus benefits from the identification of both the zero and non-zero components of x in its dimensionality reduction. Quite interestingly, when equality holds in ( 7) and ( 13), relations (22b)-(22c) entirely define the solution of (2-P). In this case, (22b) reduces to [START_REF] Parikh | Proximal algorithms[END_REF]. The solution of (2-P) can therefore be computed to machine-precision via simple linear-algebra operations when all components of x have either passed a screening or a relaxing test.

NUMERICAL RESULTS

In this section, we evaluate the computational gain induced by the proposed safe relaxing strategy. We focus on the resolution of (2-P) with λ = λ1 n for some 0 < λ < λ max max(A T y). We mention that x = 0 n as soon as λ ≥ λ max .

We consider the "Screen & Relax" (S&R) procedure described in Alg. 1. The function "DescentStep" in line 6 corresponds to one iteration of an accelerated proximal gradient algorithm [START_REF] Parikh | Proximal algorithms[END_REF]Sec. 4.3] applied to problem (22a). Recall that the beginning of the solving procedure, I = J = ∅. The evaluation of the safe sphere parameters c (t) and r (t) in line 7 follows the "GAP" methodology presented in [START_REF] Ndiaye | Gap safe screening rules for sparse-group lasso[END_REF]Th. 6]. At each iteration, problem (22a) is updated in line 10 upon the identification of additional zero or non-zero components. We note that J typically only varies by (at most) a few elements at each iteration of Alg. 1. This behavior can be exploited to compute efficiently the inverse in (17a)-(17b) by using rankone update rules [START_REF] Hager | Updating the inverse of a matrix[END_REF].

We compare the performance of the S&R procedure with three restricted versions of Alg. 1 : i) no screening and no relaxing is performed (i.e., lines 8-9 are skipped); ii) only screening is performed (i.e., line 9 is skipped); iii) only relaxing is performed (i.e., line 8 is skipped). These variants will respectively be denoted "aPG", "aPGs" and "aPGr" in the sequel. Both aPG and aPGs correspond to standard methodologies of the literature while aPGr and S&R are contributions of the present paper.

We use "Dolan-Moré" performance profiles [START_REF] Dolan | Benchmarking optimization software with performance profiles[END_REF] to assess the performance of these four methods. Our results are gathered in Fig. 1. To generate each curve, we run a solving method with a given computational budget on 100 different instances of problem (2-P). The curve corresponds to the percentage ρ(τ ) of problem instances for which the solving strategy achieves a duality gap [START_REF] Dünner | Primal-dual rates and certificates[END_REF] lower than τ upon completion.

To generate problem data, we consider the four following setups: the elements of A are i.i.d. realizations of i) a standard normal distribution or ii) a uniform law on [0, 1]; iii) the rows of A are randomly-sampled from a DCT matrix [START_REF] Nasir | Discrete cosine transform[END_REF]; iv) A has a Toeplitz structure [START_REF] Gray | Toeplitz and circulant matrices: A review[END_REF] with shifted versions of a Gaussian curve. In all setups, the columns of A are normalized to one. The observation y is drawn according to a uniform distribution on the m-dimensional sphere for "Gaussian" and "DCT" dictionaries and is restricted to the positive orthant for "Uniform" and "Toeplitz" dictionaries. We set m = 100, n = 300 and consider the following choices for the regularization parameters : (λ, ε) = (0.2, 0.5) × λ max or (λ, ε) = (0.5, 0.2) × λ max . Each problem instance is solved with a budget of 2 × 10 6 FLOPs (the number of floatingpoint operations) for "Gaussian" and "DCT" dictionaries, and 2 × 10 7 FLOPs for "Uniform" and "Toeplitz" dictionaries. The difference in the FLOPs budgets stems from the bad conditioning of the "Uniform" and "Toeplitz" dictionaries which leads to slower convergence of standard numerical solvers.

As far as our simulation setups are concerned, we notice that safe relaxing enables to significantly improve the performance. Safe relaxing alone (aPGr) proves to be of particular interest for dictionaries with highly-correlated atoms (e.g., "Uniform" or "Toeplitz"). A careful study of our simulation results led us to the conclusion that this behavior is due to an improvement of the problem conditioning when moving from problem (2-P) to (22a) and therefore of the convergence rate of the proximal gradient algorithm. The combination of screening and relaxing significantly outperforms all the other methods. We notice that S&R attains machine precision (τ = 10 -16 ) for a large proportion of problem instances in most setups. This can be explained by the behavior emphasized in Sec. 5 : when all the zero and non-zero elements of x are identified, the minimizer can be explicitly computed from (22b)-(22c) with simple linear operations. Now, perfect identification of zero and non-zero elements of x always occurs after a finite number of iterations when the GAP methodology is used to construct the safe sphere in tests ( 12) and ( 21) since c (t) → u and r (t) → 0 as t → ∞.

CONCLUSION

In this paper, we proposed a new safe relaxing methodology to detect the position of non-zero components in the solution of the Elastic-Net problem. We showed how to leverage this knowledge to reduce the dimension of the optimization problem, enabling potential computational gains in the resolution. Numerical simulations show the interest of the method, especially when combined with safe screening.

Fig. 1 .

 1 Fig. 1. Dolan-Moré performance profiles for (λ, ε) = (0.2, 0.5)λ max (top) and (λ, ε) = (0.5, 0.2)λ max (bottom).

  (t) )

	8	Update I with test (12)	// Screening test
	9	Update J with test (21)	// Relaxing test
	10	Update A r , y r , λ r , M with (19a)-(19d)
	11	t ← t + 1
	12 end


Pantxika Ospital
email: pantxika.ospital@belharra.fr

Dimitri H Masson
email: d.masson@estia.fr

Cédrick Beler
email: cedrick.beler@enit.fr

Jérémy Legardeur
email: j.legardeur@estia.fr

Toward total traceability and full transparency communication in textile industry supply chain

Keywords: Traceability, Transparency, Textiles and Clothing, Fashion industry, Supply chain

teaching and research institutions in France or abroad, or from public or private research centers.

Introduction

The textile industry is facing two challenges an ecological and an economic crise.

Fast Fashion acceleration

Since the rise of fast fashion, textile industry is one of the major contributors to pollution and waste. More and more garments are being produced relying on cheap manufacturing, frequent consumption, and short-lived garment use. Fashion brands are now producing almost twice the amount of clothing today compared with before the year 2000 [START_REF] Niinimäki | The environmental price of fast fashion[END_REF] . To achieve faster and cheaper production, production is outsourced, only a few brands have or retain their production facilities. Since the 1960s, manufacturing moved from Europe to the Middle East and to Asia [START_REF] Fletcher | Fashion Sustainability: Design for Change[END_REF]. Raw materials are produced in Asia. Whereas Design, Head-quarters, and Retail are still in the USA or Europe. These movements draw a generic map of the textile industry that is complex with a global supply chain. The various stakeholders are spread over several continents. All this stratified system creates a chain of interdependent companies [START_REF] Marino | Understanding fashion complexity through a systemic data approach[END_REF] with multi-disciplinary actors: farms that grow fibres, petrochemical industries, facilities that make and dye yarns, others that knit or weave yarns into fabrics, others that print fabrics, tanneries that transform hide into leather, factories that cut, sew, assemble garments, logistics, retail [START_REF] Jestratijevic | Making Fashion Transparent: What Consumers Know about the Brands They Admire[END_REF].

Awareness-raising

This fragmented supply chain requires different laws and regulations [START_REF] Fletcher | Fashion Sustainability: Design for Change[END_REF]. All this complexity has come to light because of various dramas of our time: child labour, the Rana plaza disaster, the scandal of the Uighur cotton forced production, or the flooding of a clandestine textile workshop in February 2021 in Tangier that has claim twenty-eight lives. Companies can no longer ignore the origin and production conditions of their goods. They must be accountable internally, to their cus-tomers, to the environmental footprint, and in France, since 2017, are legally subject to the duty of vigilance. (LOI n°2017-399 du 27 mars 2017) A directive at the EU level on this issue should be adopted based on these principles in 2021.

Recession and De-consumption perspective

In 2018, 44 percent of consumers bought less clothing and for 40 percent of them, it was a chosen de-consumption. Among them, more than a third of young people (18-25 years old) [START_REF] Delattre | Perspectives Internationales Mode et Textile[END_REF].This phe-nomenon reveals a growing consumer awareness and a growing distrust of the industry's companies. Furthermore, retailers are declining, not meeting customers' needs. Between 2008 and 2018 the textile and apparel industry lost 15 percent of its value in France [START_REF] Delattre | Perspectives Internationales Mode et Textile[END_REF]. This recession affects principally middle markets brands and women Ready to Wear (-18 percent to 20 percent) [START_REF] Delattre | Perspectives Internationales Mode et Textile[END_REF]. This phenomenon may be local before 2020, but because of COVID 19 pandemic recession, this trend may be generalized. A survey conducted in April 2020 across 2035 British and German consumers reveals that 64 percent of them would spend less on fashion during the crisis, and half of them expect that trend to continue after the crisis passes. As well, consumers are open to purchasing more durable fashion items, as well as repairing and keeping them longer [START_REF] Granskog | Survey: Consumer sentiment on sustainability in fashion[END_REF]. This survey reveals a shift in purchasing behaviour. We argue that the textile industry must understand and support these new consumer behaviours by becoming more transparent about their products origin and means of fabrication. Inventory of full process data traceability is necessary to know, justify, analyse, improve, and communicate information. Firstly, we will review the current situation regarding the transparency of information communi-cated by brands. In the second part we will explain some of the specific supply chain complexities of the Textile and Garment industry.

Transparency: what brands communicate

There are legal requirements in Europe that impose a limited communication about the traceability of textile products. Labels on clothes must only describe composition. However, most brands print on their labels the country of manufacture: "made in", because it is mandatory in some countries where these clothes are sold (e.g. US or Japan).

Figure 1. Example of retail information on similar T-shirts with different origins

These 3 t-shirts are similar and have the same identification (bar-code)

The Bulk number XXX1 t-shirt is made in Bangladesh from Chinese cotton, it was transported by boat.

The Bulk number XXX2 t-shirt is made in Turkey from Chinese cotton, it was transported by truck.

The Bulk number XXX3 t-shirt is made in Turkey from Indian cotton, it was transported by plane.

Figure 1 shows the difficulties for consumers to make informed purchasing decisions directly in-store with only the country of manufacture information available in most cases. The United Nations, through its 2030 agenda, defined 17 Sustainable Development Goals. Among those, goal 12 "Ensure sustainable consumption and production patterns" and target 12.8 identifies the need for "people everywhere to have the relevant information and awareness for sustainable development and lifestyles in harmony with nature" [START_REF] Carrone | Traceability and Transparency: A Way Forward for SDG 12 in the Textile and Clothing Industry[END_REF]. Since 2015, Fashion Revolution publishes an annual report of the Fashion Transparency Index [START_REF] Ditty | Fashion transparency index[END_REF]. In 2020 they reviewed 250 of the world's largest fashion brands and retailers and ranked them ac-cording to how much they disclosed about their social and environmental policies, practices, and impacts. Despite progress, most of them still lack transparency: the best brand tops at 73 percent and the average score is 23 percent. Researchers assess the 250 brands with publicly available infor-mation. And in a second time, brands have the opportunity to complete a questionnaire, those that participate typically receive higher scores as researchers may have missed relevant disclosure documents. But only 53 percent of brands are participating by returning and completing a questionnaire, which testifies to the relative commitment of brands. Mass-market brands revealed higher transparency of supply chain disclosures [START_REF] Ditty | Fashion transparency index[END_REF]. The consumer survey by Fashion Revolution in 2018 and 2020 suggests that fashion labels should be transparent with the disclosure of information to consumers: Manufacturer's address, the origin of fabric, and raw material. Some of this information is available on the label's website but on the product and point of sale, most of the time only the garment manufacturer country is available. Concerning future works, we are performing a study on what the Fashion Pact brands communicate in-store compared to what they communicate on their website. This study covers 55 brands among the 77 companies involved in the Fashion Pact, provided that they are distributed and accessible in France online and in-store. For groups, we have picked one brand to consider. We have excluded from our selection the companies involved in the Fashion Pact that are distributors, manufacturers or merchandising suppliers. More research needs to be done to compare the information available online and in-store. From our initial observations, we notice that the country of manufacture is present on the labels of the products in stores in most cases, and is the most accurate information available. On merchant sites, for the same product references, this information is less frequent. On the contrary, the most transparent brands can display the name of their manufacturer as well as information about the manufacturing conditions on their website, and do not communicate this type of information in stores. As per Figure 1., "Made in" doesn't inform precisely about material origin, mill environmental footprint, transport.

Garment supply chain

The garment supply chain is a complex multi-actors buyer-driven production chain (figure 2). Re-tailers promote and sell apparel but rarely produce goods. Manufacturers have different functional capabilities, that involve different models of sourcing goods and therefore traceability for the buyer. However, we argue that from a consumer perspective these production models should have no impact on what information is provided regarding their product.

Figure 2. Generic product traceability process

Actors are grouped vertically by level from raw material production (Level 4) to sales (Level 0):

At Level 0 the brand orders production and is in charge of retail. At Level 1 manufacturers cut, sew, and assemble garments. At Level 2 factories transform yarn into fabric by weaving or knitting. At Level 3 factories process raw materials into yarn. This level includes cleaning steps such as ginning cotton or washing wool and spinning mills.

At Level 4 manufacturers produce raw materials: e.g. farms grow fibers such as cotton or wool, petrochemical industries produce synthetic fibers, or recycled fibers. Production schemes Outsourced manufacturers at level 1 can propose 3 types of services [START_REF] Gereffi | The Global Apparel Value Chain, Trade And The Crisis : Challenges And Opportunities For Developing Countries[END_REF].

Make and trim (CMT)

A Level 1 factory is paid a processing fee and uses fabric and trims sourced and owned by the Level 0. In this production scheme the brand retains the most information about its product origin, mate-rial and transformations. This is the ideal case for the full transparency as the brand is in full control of its supply chain.

Original Equipment Manufacturing (OEM)/ Package Contractor

According to brand (Level 0) specifications, quoted price and design, the manufacturer (Level 1) is capable of sourcing and financing fabric and trims from Level 2 factories of its choice, and providing all production services, finishing, and packaging for delivery to the retail outlet. In this case, the brand (Level 0) has a limited knowledge of the origin of goods and the Level 2, 3 and 4 actors involved in the processes.

Original Design Manufacturing (ODM)/Full Package

A full package garment supplier (Level 1), after agreeing on a quoted price with the brand (Level 0), organizes all steps involved in the production of a finished garment, including design, fabric pur-chasing, cutting, sewing, trimming, packaging, and distribution. As per OEM, the brand (level 0) has a limited knowledge of the origin of goods and the Level 2, 3 and 4. It has in addition a low control on the specifications of the product, for instance regarding materials or fabrication condi-tions. In a competitive industry, companies are reticent to divulge too much information about their sourcing, as it could undermine their competitive advantage. During the transformation process from raw material to garment, all steps involved in production could be traced as a traceable event to identify origin of components, their complete composition, their process, their social and environmental impacts.

Events and assets

Along the supply chain, the traceable assets are transformed many times: from raw material (fibers) to intermediate material (yarn or fabric) to finished product (garment). These traceable assets can be aggregated and disaggregated in batches corresponding to trade or logistic units. Following the Bill of Material for a garment, each component can be identified individually or from a batch of items. To identify or trace each item or batch of items uniquely in the supply chain, they could be tagged as a traceable resource unit (TRU) with technological help: RFID, QR code, Bar-code, Bulk number, Tag, Raw material marker [START_REF] Kumar | Developing a Framework for Traceability Implementation in the Textile Supply Chain Systems[END_REF]. Research from 2016 showed that only 7 percent of companies knew their cotton supplier [START_REF] Jestratijevic | Transparency of sustainability disclosures among luxury[END_REF] . Bales of cotton are mixed during the process, and one t-shirt could be composed of yarn coming from different cotton suppliers. For Global Organic Textile (GOTS) certification, a fashion brand can claim that a t-shirt is made of certified organic origin cotton only if at least 95 percent of the fiber content of the product is certified. Traceability is essential to claim good practices because without proof, brands can be accused of greenwashing [START_REF] Kumar | Developing a Framework for Traceability Implementation in the Textile Supply Chain Systems[END_REF].

Conclusion

Information provided to the customer is sparse and accessibility is low. Online and in-store access remains different. It is difficult for consumers to make informed purchasing decisions directly in-store, without previous active research. Solutions to restitute data today include in-store: sales-person telling a product story and labeling on the product, but these media are not sufficient. Technology could help matching information published online and in-store. Connected touch screens could inform with precise data, adding what is available online to latest data collected e.g. about the environmental impact, taking into account the delivery to the store. Mobile applications including Blockchain technology can share a chronological chain of records of all supply chain transactions for a unique ID product. It can help for valuable goods to have proof of authenticity as a guarantee, but environmental cost can be important. As well, 3rd Part Mobile applications can describe brands' CSR policies but usually do not indicate product information according to a batch number or unique item. Brands become transparent, disclosing more traceability data than before. Prioritizing meaningful information can be difficult not to overload customers with information that would be unnecessary in making their purchase decision. Defining a standard list of data that can be collected and com-municated according to fashion brands and consumer profile is a challenge. Restitution of the data adapting to consumers' profiles is key, scoring may be necessary to create visible, focused, meaningful, and clear information.

Acknowledgments

We thank Université de Bordeaux ESTIA Institute of Technology, and Belharra Numérique for their contribution on previous versions of this document.