Antoine Bonnefoy

Valentin Emiya

Liva Ralaivola

Rémi Gribonval

Dynamic Screening

Keywords: Accelerating First-Order Algorithms Screening test, Dynamic screening, Lasso, Group-Lasso, Iterative Soft Thresholding, Sparsity

published or not. The documents may come   L'archive ouverte pluridisciplinaire

I. INTRODUCTION

In this paper, we focus on the numerical solution of optimization problems that consist in minimizing the sum of an ℓ 2 -fitting term and a sparsity-inducing regularization term. Such problems are of the form: P(λ, Ω, D, y) : x arg min

x 1 2
Dxy 2 2 + λΩ(x),

where y ∈ R N is an observation; D ∈ R N ×K with N ≤ K is a matrix called dictionary; Ω : R K → R + is a convex sparsity-inducing regularization function; and λ > 0 is a parameter that governs the tradeoff between data fidelity and regularization. Various convex and non-smooth functions Ω may induce the sparsity of the solution x. Here, we consider two instances of problem (1), the Lasso [START_REF] Tibshirani | Regression shrinkage and selection via the Lasso[END_REF] and the Group-Lasso [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF], which differ from each other in the choice of the regularization Ω. A key challenge is to handle (1) when both N and K may be large, which occurs in many real-world applications including denoising [START_REF] Chen | Atomic decomposition by Basis Pursuit[END_REF], inpainting [START_REF] Elad | Simultaneous cartoon and texture image inpainting using Morphological Component Analysis (MCA)[END_REF] or classification [START_REF] Wright | Robust face recognition via sparse representation[END_REF]. Algorithms relying on first-order information only, i.e. gradient-based procedures [START_REF] Beck | A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems[END_REF], [START_REF] Combettes | Signal recovery by proximal forward-backward splitting[END_REF], [START_REF] Daubechies | An Iterative Thresholding Algorithm for Linear Inverse Problems with a Sparsity Constraint[END_REF], [START_REF] Wright | Sparse reconstruction by separable approximation[END_REF], are particularly suited to solve these problems, as secondorder based methods -e.g. using the Hessian-imply too computationally demanding iterations. In the ℓ 2 data-fitting case the gradient relies on the application of the operator D and its transpose D T . We use this feature to define first order algorithms as those based on the application of D and D T . The definition extends to primal-dual algorithm [START_REF] Arrow | Studies in linear and non-linear programming, With contributions by Hollis B. Chenery[END_REF], [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF]. Accelerating these algorithms remains challenging: even though they provably have fast convergence [START_REF] Nesterov | A method of solving a convex programming problem with convergence rate o (1/k2)[END_REF], [START_REF] Beck | A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems[END_REF], the multiplications by D and D T in the optimization process are a bottleneck in their computational efficiency, which is thus governed by the dictionary size. We are interested in the general case where no fast transform is associated with D. This occurs for instance with exemplar-based or learned dictionaries. Such accelerations are even more needed during the process of learning high-dimensional dictionaries, which requires solving many problems of the form (1). Screening Tests: The convexity of the objective function suggests to use the theory of convex duality [START_REF] Boyd | Convex Optimization[END_REF] to understand and solve such problems. In this context, strategies based on screening tests [START_REF] Dai | An ellipsoid based, two-stage screening test for BPDN[END_REF], [START_REF] Ghaoui | Safe Feature Elimination in Sparse Supervised Learning[END_REF], [START_REF] Tibshirani | Strong rules for discarding predictors in Lasso-type problems[END_REF], [START_REF] Wang | Lasso Screening Rules via Dual Polytope Projection[END_REF], [START_REF] Xiang | Learning sparse representations of high dimensional data on large scale dictionaries[END_REF], [START_REF] Xiang | Fast Lasso screening tests based on correlations[END_REF] have recently been proposed to reduce the computational cost by considering properties of the dual optimum. Given that the sparsity-inducing regularization Ω entails an optimum x that may contain many zeros, a screening test is a method aimed at locating a subset of such zeros. It is formally defined as follows:

Definition 1 (Screening test). Given problem P(λ, Ω, D, y) with solution x, a boolean-valued function T : [1 . . . K] → {0, 1} is a screening test if and only if:

∀i ∈ [1 . . . K], T (i) = 1 ⇒ x(i) = 0.

(

) 2
We assume that solution x is unique -e.g., it is true with probability one for the Lasso if D is drawn from a continuous distribution [START_REF] Tibshirani | The Lasso problem and uniqueness[END_REF]. In general, a screening test cannot detect all zeros in x, that is why relation [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF] is not an equivalence. An efficient screening test locates many zeros among those of x. From a screening test T a screened dictionary D 0 = DT is defined, where the matrix T removes from D the inactive atoms corresponding to the zeros located by the screening test T . T is built by removing, from the K ×K identity matrix, the columns corresponding to screened atoms i.e. columns indexed by i ∈ [1 . . . K] whenever verifies T (i) = 1. Property [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF] implies that x0 , the solution of problem P(λ, Ω, D 0 , y), is exactly the same as x the solution of P(λ, Ω, D, y) up to inserting zeros at the locations of the removed atoms: x = Tx 0 . Any optimization procedure solving problem P(λ, Ω, D 0 , y) with the screened dictionary D 0 therefore computes the solution of P(λ, Ω, D, y) at a lower computational cost. Algorithm 1 depicts the commonly used strategy [START_REF] Ghaoui | Safe Feature Elimination in Sparse Supervised Learning[END_REF], [START_REF] Xiang | Learning sparse representations of high dimensional data on large scale dictionaries[END_REF] to obtain an algorithmic acceleration using a screening test; it rests upon two steps: i) locate some zeros of x thanks to a screening test and construct the screened dictionary D 0 and ii) solve P(λ, Ω, D 0 , y) using the smaller dictionary D 0 .

Dynamic Screening: We propose a new screening principle called dynamic screening in order to reduce even more the computational cost of first-order algorithms. We take the aforementioned concept of screening test one step further, and improve existing screening tests by embedding them in the iterations of first-order algorithms. We take advantage of the computations made during the optimization procedure to perform a new screening test at each iteration with a negligible computational overhead, and we consequently dynamically reduce the size of D. For a schematic comparison, the existing static screening and the proposed dynamic screening are sketched in Algorithms 1 and 2, respectively. One may observe that with the dynamic screening strategy, the dictionary D t used at each iteration t is possibly smaller and smaller thanks to successive screenings.

Illustration: We now present a brief illustration of the dynamic screening principle in action, dedicated to the impatient reader who wishes to get a good grasp of the approach without having to enter the mathematics in too much detail. The dynamic screening principle is illustrated in Figure 1 in the particular case of the combined use of ISTA [START_REF] Daubechies | An Iterative Thresholding Algorithm for Linear Inverse Problems with a Sparsity Constraint[END_REF] and of a new, dynamic version of the SAFE screening test [START_REF] Ghaoui | Safe Feature Elimination in Sparse Supervised Learning[END_REF] to solve the Lasso problem, which is [START_REF] Tibshirani | Regression shrinkage and selection via the Lasso[END_REF] with Ω(x) = x 1 . The screening effect is illustrated through the evolution of the size of the dictionary, i.e., the number of atoms remaining in the screened dictionary D t . In this example the observation y and all the K = 50000 atoms are vectors drawn uniformly and independently on the unit sphere in dimension N = 5000 of D, and we set λ = 0.75 × D T y ∞ . Here, the actual screening begins to have an effect at iteration t = 20. In about ten iterations, the dictionary is dynamically screened down to 5% of its initial size and the computational cost of each iteration gets lower and lower. Then, the last iterations are performed with a reduced computational cost. Consequently, the total running time equals 4.6 seconds while it is 11.8 seconds if no screening is used. One may also observe that the screening test is inefficient in the first 20 iterations. In particular, the dynamic screening at the very first iteration is strictly equivalent to the state-of-the-art (static) screening. Static screening would have been of no use in this case.

Contributions: This paper is an extended version of [START_REF] Bonnefoy | A Dynamic Screening Principle for the Lasso[END_REF]. Here we propose new screening tests for the Group-Lasso and give an unified formulation of the dynamic screening principle for both Lasso and Group-Lasso, which improves screening tests for both problems. The algorithmic contributions and related theoretical results are introduced in Section II. First, the dynamic screening principle is formalized in a general algorithmic scheme (Algorithm 3) and its convergence is established (Theorem 1). Then, we show how to instantiate this scheme for several first-order algorithms (Section II-B1), as well as for the two considered problems the Lasso and Group-Lasso (Sections II-B2 and II-B3). We adapt existing tests to make them dynamic for the Lasso and propose new screening tests for the Group-Lasso. A turnkey instance of the proposed approach is given in Section II-C. Finally, the computational complexity of the dynamic screening scheme is detailed and discussed in Section II-D. In Section III, experiments show how the dynamic screening principle significantly reduces the computational cost of first-order optimization algorithms for a large range of problem settings and algorithms. We conclude this paper by a discussion in Section IV. All proofs are given in Appendix.

II. GENERALIZED DYNAMIC SCREENING Notation and definitions: D

[d 1 , . . . , d K ] ∈ R N ×K denotes a dictionary and Γ {1, . . . , K} denotes the set of integers indexing the columns, or atoms, of D. The i-th component of x is denoted by x(i). For a given set I ⊂ Γ, |I| is the cardinal of I, I c Γ\I is the complement of I in Γ and D [I] [d i ] i∈I denotes the sub-dictionary composed of the atoms indexed by elements of I. The notation extends to vectors: x [I] [x(i)] i∈I . Given two index sets I, J ⊂ Γ and a matrix M, M [I,J ] [M(i, j)] (i,j)∈I×J denotes the sub-matrix of M obtained by selecting the rows and columns indexed by elements in I and J , respectively. We denote primal variables vectors by x ∈ R K and dual variables vectors by θ ∈ R N . We denote by [r] b a max(min(r, b), a) the projection of r onto the segment [a, b]. Without loss of generality, the observation y and the atoms d i are assumed to have unit ℓ 2 norm. For any matrix M, M denotes its spectral norm, i.e., its largest singular value.

A. Proposed general algorithm with dynamic screening

Dynamic screening is dedicated to accelerate the computation of the solution of problem [START_REF] Tibshirani | Regression shrinkage and selection via the Lasso[END_REF]. It is presented here in a general way.

Let us consider a problem P(λ, Ω, D, y) as defined by eq. ( 1). First-order algorithms are iterative optimization procedures that may be resorted to solving P(λ, Ω, D, y). Based only on applications of D and D T , they build a sequence of iterates x t that converges, either in terms of objective values or the iterate itself, to the solution of the problem. In the following, we use the update step function p(•) as a generic notation to refer to any first-order algorithm. The optimization procedure might be formalized as the update

(X t , θ t , α t ) ← p(X t-1 , θ t-1 , α t-1 , D)
of several variables. Matrix X t is composed of one or several columns that are primal variables and from which one can extract x t ; vector θ t is an updated variable of the dual space R N -in the sense of convex duality (see II-B2 equation (5) for details); and α t is a list of updated auxiliary scalars in R. Algorithm 3 makes explicit the use of the introduced notation p(•) in the general scheme of the dynamic screening principle. The inputs are: the data that characterize problem P(λ, Ω, D, y); the update function p(•) related to the first-order algorithm to be accelerated; an initialization X 0 ; and a family of screening tests {T θ } θ∈R N in the sense1 of Definition 1. Iteration t begins with an update step at line 4. It is followed by a screening stage in which a screening test T θt is computed using the dual point θ t obtained during the update. As shown at line 6, it enables to detect new inactive atoms and to update index set I t that gathers all atoms identified as inactive so far. This set is then used to screen the dictionary and the primal variables at lines 7 and 8 using the screening matrix Id [I c t ,I c t-1 ] -obtained by removing columns I t-1 and rows I t from the K ×K-identity matrix-and its transpose. Thanks to successive screenings, the dimension shared by the primal variables and the dictionary is decreasing and the optimization update can be computed in the reduced dimension |I c t |, at a lower computational cost. The acceleration is efficient because lines 6 to 8 have negligible computation impact, as shown in Section II-D and assessed experimentally in Section III.

Algorithm 3 General algorithm with dynamic screening Require: D, y, λ, Ω, X 0 , screening test T θ for any θ ∈ R N and first-order update p(•).

1:

D 0 ← D, I 0 ← ∅, t ← 1,
I t ← {i ∈ Γ, T θt (i)} ∪ I t-1 7: D t ← D t-1 Id [I c t-1 ,I c t ] 8: Xt ← Id [I c t ,I c t-1 ] X t 9:
t ← t + 1 10: end while 11: return X t Since the optimization update at line 4 is performed in a reduced dimension, the iterates generated by the algorithm with dynamic screening may differ from those of the base first-order algorithm. The following results states that the proposed general algorithm with dynamic screening preserves the convergence to the global minimum of problem (1).

Theorem 1.

Let Ω be a convex and sparsifying regularization function and p(•) the update function of an iterative algorithm. If p(•) is such that for any D, y, λ, the sequence of iterates given by p(•) converges to the solution of P(λ, Ω, D, y), then, for any family of screening tests {T θ } θ∈R N , the general algorithm with dynamic screening (Algorithm 3) converges to the same global optimum of problem P(λ, Ω, D, y).

Proof. Since ∀θ ∈ R N , T θ is a screening test, problems P(λ, Ω, D, y) and P(λ, Ω, D t , y) for all t ≥ 0 have the same solution. The sequence {I t } t≥0 of located zeros at time t is inclusion-wise non-decreasing and upper bounded by the set of zeros in x the solution of P(λ, Ω, D, y), so the sequence converges in a finite number of iterations t 0 . Then ∀t ≥ t 0 , D t 0 = D t and the existing convergence proofs of the first-order algorithm with update p(•) apply.

B. Instances of algorithm with dynamic screening

The general form of Algorithm 3 may be instantiated for various algorithms, problems and screening tests. The general form with respect to first-order algorithms is instantiated for a number of possible algorithms in Section II-B1. The algorithm may be applied to solve the Lasso and Group-Lasso problems through the choice of the regularization Ω. Instances of screening tests T θ associated to each problem are described in Sections II-B2 and II-B3 respectively. Proofs are postponed to the appendices for readability purposes.

1) First-order algorithm updates: The dynamic screening principle may accelerate many first-order algorithms. Table I specifies how to use Algorithm 3 for several first-order algorithms, namely ISTA [START_REF] Daubechies | An Iterative Thresholding Algorithm for Linear Inverse Problems with a Sparsity Constraint[END_REF], TwIST [START_REF] Bioucas-Dias | A new TwIST: Two-step iterative shrinkage/thresholding algorithms for image restoration[END_REF], SpaRSA [START_REF] Wright | Sparse reconstruction by separable approximation[END_REF], FISTA [START_REF] Beck | A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems[END_REF] and Chambolle-Pock [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF]. This specification consists in defining the primal variables X t , the dual variable θ t , the possible additional variables α t and the update p(•) used at line 4.

Table I shows two important aspects of first-order algorithms: first, the notation is general and many algorithms may be formulated in this way; second, every p(•) has a computational complexity in O(KN ) per iteration.

Table I makes use of proximal operators prox Ω λ (x) min z Ω (z) + 1 2λ xz 2 2 that handle the nonsmoothness of the objective function introduced by the regularization Ω. Beyond the subsequent definitions of the proximal operators for the Lasso (see eq. ( 4)) and the Group-Lasso (see eq. ( 13)), we refer the interested reader to [START_REF] Combettes | Signal recovery by proximal forward-backward splitting[END_REF] for a full description of proximal methods.

2) Dynamic screening for the Lasso: Let us first recall the Lasso problem before giving the screening tests T θ that may be embedded in the corresponding optimization procedure.

a) The Lasso [START_REF] Tibshirani | Regression shrinkage and selection via the Lasso[END_REF]: The Lasso problem uses the ℓ 1 -norm penalization to enforce a sparse solution. The Lasso is exactly (1) using Ω(x) = x 1 :

P Lasso (λ, D, y) : arg min x 1 2 Dx -y 2 2 + λ x 1 . (3)
The proximal operator of the ℓ 1 -norm is the so-called soft-thresholding operator:

prox Lasso t (x) sign(x) max(|x| -t, 0). (4)
Screening tests [START_REF] Ghaoui | Safe Feature Elimination in Sparse Supervised Learning[END_REF], [START_REF] Xiang | Fast Lasso screening tests based on correlations[END_REF], [START_REF] Xiang | Learning sparse representations of high dimensional data on large scale dictionaries[END_REF] rely on the dual formulation of the Lasso problem:

θ arg max θ 1 2 y 2 2 - λ 2 2 θ - y λ 2 2 (5a) s.t. ∀i ∈ Γ, |θ T d i | ≤ 1. (5b) A dual point θ ∈ R N is said feasible for the Lasso if it complies with constraints (5b). Algorithm Nature of {X t , α t } Optimization update {X t , θ t } ← p(X t-1 , θ t-1 , α t-1 , D) ISTA [8] X t x t , α t L t θ t ← Dx t-1 -y x t ← prox Ω λ L t x t-1 -1 Lt D T θ t L t is
set with the backtracking rule see [START_REF] Beck | A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems[END_REF] TwIST [START_REF] Bioucas-Dias | A new TwIST: Two-step iterative shrinkage/thresholding algorithms for image restoration[END_REF] X

t [x t , x t-1 ], α t ∅ θ t ← Dx t-1 -y x t ← (1 -α)x t-2 + (α -β)x t-1 + β prox Ω λ x t-1 -D T θ t SpaRSA [9] X t [x t ], α t L t Same as ISTA except that L t is set with the Brazilai-Borwein rule [9] FISTA [6] X t [x t , u t ], α t (l t , L t ) θ t ← Du t-1 -y x t ← prox Ω λ/Lt u t-1 -1 Lt D T θ t l t ← 1+ √ 1+4l 2 t-1 2 u t ← x t + ( lt-1-1 lt )(x t -x t-1 ) L t is set with the backtracking rule see [6] Chambolle-Pock [11] X t [x t , u t ], α t (τ t , σ t ) θ t ← 1 1+σt-1 (θ t-1 + σ t-1 (Du t-1 -y)) x t ← prox Ω λτt-1 x t-1 -τ t-1 D T θ t ϕ t ← 1 √ 1+2γτt-1 τ t ← ϕ t τ t-1 ; σ t ← σt-1 ϕt u t ← x t + ϕ t (x t -x t-1 )
Table I: Updates for first-order algorithms.

From the convex optimality conditions, solutions of the Lasso problem (3) and its dual (5), x and θ respectively, are necessarily linked by:

y = Dx + λ θ and ∀i ∈ Γ, | θT d i | ≤ 1 if x(i) = 0, | θT d i | = 1 if x(i) = 0. (6)
We define λ * D T y ∞ . If λ > λ * , the solution is trivial and is derived from the most simple screening test that may be designed, which screens out all atoms. Indeed, starting from the fact that θ = y/λ is the solution of the dual problem -it is feasible and maximizes (5a)-, we have ∀i, |d T i θ| = |y T d i |/λ ≤ λ * /λ < 1 so that the optimality conditions impose that x(i) = 0. In other words, we can screen the whole dictionary before entering the optimization procedure. In the following, we will focus on the non-trivial case λ ∈ ]0, λ * ].

b) Screening tests for the Lasso: The screening tests presented here have been proposed initially in the static perspective in [START_REF] Ghaoui | Safe Feature Elimination in Sparse Supervised Learning[END_REF], [START_REF] Xiang | Fast Lasso screening tests based on correlations[END_REF], [START_REF] Xiang | Learning sparse representations of high dimensional data on large scale dictionaries[END_REF]. They use relation [START_REF] Beck | A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems[END_REF] to locate some inactive atoms d i for which |d T i θ| < 1. The quantity is not directly accessible as the optimal is not known, thus the base concept of screening test is to geometrically construct a region R that is known to contain the optimal θ so that the upper-bound max θ∈R |d T i θ| ≥ |d T i θ| gives a sufficient condition for atom d i to be inactive:

max θ∈R |d T i θ| < 1 ⇒ x(i) = 0.
In particular the previous maximization problem admits a closed form solution when R is a sphere or a dome.

The SAFE test proposed by L. El Ghaoui et al. in [START_REF] Ghaoui | Safe Feature Elimination in Sparse Supervised Learning[END_REF] is derived by constructing a sphere from any dual point θ. Xiang et al. in [START_REF] Xiang | Fast Lasso screening tests based on correlations[END_REF], [START_REF] Xiang | Learning sparse representations of high dimensional data on large scale dictionaries[END_REF] improved it when the particular dual point y is used. We propose here a homogenized formulation relying on any dual point θ for each of the three screening tests, generalizing [START_REF] Xiang | Fast Lasso screening tests based on correlations[END_REF], [START_REF] Xiang | Learning sparse representations of high dimensional data on large scale dictionaries[END_REF] to any dual point, thereby fitting them for use in a dynamic setting. We present these screening tests through the following Lemmata, in order of increasing description complexity and screening efficiency. For more details on the construction of regions R and the solution of the maximization problem please see the references or proofs in Appendix.

Lemma 2 (The SAFE screening test [START_REF] Ghaoui | Safe Feature Elimination in Sparse Supervised Learning[END_REF]). For any θ ∈ R N , the following function T SAFE θ is a screening test for P Lasso (λ, D, y):

T SAFE θ : Γ → {0, 1} i → (1 -|d T i c|) > r θ (7)
where c y λ , r θ y λµθ 2 and µ

θ T y λ θ 2 2 D T θ -1 ∞ -D T θ -1 ∞ .
The notation P in [START_REF] Combettes | Signal recovery by proximal forward-backward splitting[END_REF] means that we take the boolean value of the proposition P as the output of the screening test. We also recall that The screening test ST3 [START_REF] Xiang | Learning sparse representations of high dimensional data on large scale dictionaries[END_REF] is a much more efficient test than SAFE, especially when λ * is high. We extend it in the following Lemma so that it can be used for dynamic screening.

Lemma 3 (The Dynamic ST3: DST3). For any θ ∈ R N , the following function T DST3 θ is a screening test for P Lasso (λ, D, y):

T DST3 θ : Γ → {0, 1} i → (1 -|d T i c|) > r θ ( 8
)
where

c y λ -λ * λ -1 d * , r θ µθ -y λ 2 2 -λ * λ -1 2 , µ θ T y λ θ 2 2 D T θ -1 ∞ -D T θ -1 ∞ and d * arg max d∈{±d i } K i=1 d T y.
When applied with θ = y this screening test is exactly the ST3 [START_REF] Xiang | Learning sparse representations of high dimensional data on large scale dictionaries[END_REF]. Further improvements have been proposed in the Dome test [START_REF] Xiang | Fast Lasso screening tests based on correlations[END_REF] for which we also propose an extended version appropriate for dynamic screening.

Lemma 4 (The Dynamic Dome Test: DDome). For any θ ∈ R N , the following function T DDome θ is a screening test for P Lasso (λ, D, y):

T DDome θ : Γ → {0, 1} i → Q l θ l(d T * d i ) < x T d i < Q u θ (d T * d i ) (9)
where

Q l θ (t) (λ * -λ)t -λ + λr θ √ 1 -t 2 , if t ≤ λ * -(λ -1 + λ/λ * ), if t > λ * (10)
Q u θ (t) (λ -1 + λ/λ * ), if t < -λ * (λ * -λ)t + λ -λr θ √ 1 -t 2 , if t ≥ -λ * (11) r θ µθ -y λ 2 2 -λ * λ -1 2 , µ θ T y λ θ 2 2 D T θ -1 ∞ -D T θ -1 ∞ and d * arg max d∈{±d i } K i=1 d T y.
When applied with θ = y this screening test is exactly the Dome test [START_REF] Xiang | Fast Lasso screening tests based on correlations[END_REF].

Using these Lemmata at dual points θ t obtained during iterations allows to progressively reduce the radius r θ of the considered regions -sphere or dome-and thus improves the screening capacity of the screening tests associated to these regions. The effect of the radius appears clearly in [START_REF] Combettes | Signal recovery by proximal forward-backward splitting[END_REF][START_REF] Daubechies | An Iterative Thresholding Algorithm for Linear Inverse Problems with a Sparsity Constraint[END_REF][START_REF] Arrow | Studies in linear and non-linear programming, With contributions by Hollis B. Chenery[END_REF][START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF]. Note that the choice of a new θ, for one of the previous screening tests T θ , only acts on r θ the radius of the region and not on c its center.

3) Dynamic screening for the Group-Lasso: The Lasso problem embodies the assumption that observation y may be approximately represented in D by a sparse vector x. When a particular structure of the data is known, we may additionally assume that, besides sparsity, the representation of y in D fits this structure. Inducing the structure into x is exactly the goal of structured-sparsity regularizers. Among those we focus on the Group-Lasso regularization because the group-separability of its objective function [START_REF] Nesterov | A method of solving a convex programming problem with convergence rate o (1/k2)[END_REF] particularly fits the screening framework.

a) The Group-Lasso [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF]: The Group-Lasso is a sparse least-squares problem that assumes some group structure in the sparse solution, in the sense that there are groups of zero coefficients in the solution x. This structure, assumed to be known in advance, is characterized by G, a known partition of Γ, and w g > 0 the weights associated with each group g ∈ G (e.g. w g = |g|). Using the group-sparsity inducing regularization Ω(x) g∈G w g x [g] 2 , the Group-Lasso is defined as:

P Group-Lasso (λ, D, G, y) : arg min x 1 2 Dx -y 2 2 + λ g∈G w g x [g] 2 . ( 12
)
The proximal operator of the group sparsity regularization is the group soft-thresholding:

∀g ∈ G, prox Group-Lasso t (x g ) max 0, x g 2 -tw g x g 2 x g . ( 13
)
The dual of the Group-Lasso problem ( 12) is (see [START_REF] Wang | Lasso Screening Rules via Dual Polytope Projection[END_REF]):

θ arg max θ 1 2 y 2 2 - λ 2 2 θ - y λ 2 2 (14a) s.t. ∀g ∈ G, D T [g] θ 2 w g ≤ 1. (14b)
A dual point θ ∈ R N is said feasible for the Group-Lasso if it satisfies constraints (14b).

From the convex optimality conditions, primal and dual optima are necessarily linked by:

y = Dx + λ θ, and ∀g ∈ G D T [g] θ 2 ≤ w g if x[g] = 0, D T [g] θ 2 = w g if x[g] = 0. (15)
We now adapt the definition of λ * to the Group-Lasso so that it corresponds to the smallest regularization parameter resulting into a zero solution of [START_REF] Nesterov | A method of solving a convex programming problem with convergence rate o (1/k2)[END_REF]. Let us define

g * arg max g D T [g] y 2 w g , λ * D T [g * ] y 2 w g * . ( 16
)
As for the Lasso, if λ > λ * one may screen all the atoms and obtain x = 0. Hence for the Group-Lasso setting, we focus on the non-trivial case λ ∈ ]0, λ * ].

Instances of screening tests for the Group-Lasso are presented in the sequel. We extend here the SAFE [START_REF] Ghaoui | Safe Feature Elimination in Sparse Supervised Learning[END_REF] and the DST3 [START_REF] Xiang | Learning sparse representations of high dimensional data on large scale dictionaries[END_REF] screening tests to the Group-Lasso. To our knowledge there are no published results on this extension to the Group-Lasso. b) Screening tests for the Group-Lasso: As just previously for the Lasso, the quantity D T

[g] θ 2
in relation [START_REF] Ghaoui | Safe Feature Elimination in Sparse Supervised Learning[END_REF] is not known except if the problem is solved. Regions R containing the optimum θ are considered to use the upper bound max θ∈R D T

[g] θ 2 to identify some inactive groups g thanks to relation [START_REF] Ghaoui | Safe Feature Elimination in Sparse Supervised Learning[END_REF]. Please see the proofs in the appendix for details on the construction of the regions and the solution of the maximization problem.

For any index i ∈ Γ, we denote by g(i) the unique group g ∈ G that contains i. The following Lemma extends the SAFE screening test to the Group-Lasso: Lemma 5 (The Group-SAFE: GSAFE). For any θ ∈ R N , the following function T GSAFE θ is a screening test for P Group-Lasso (λ, D, G, y):

T GSAFE θ : Γ → {0, 1} i →   w g(i) D [g(i)] - D T [g(i)] c 2 D [g(i)]   > r θ ( 17
)
where

c y λ , r θ y λ -µθ 2 and µ θ T y λ θ 2 2 min g∈G wg D T [g] θ 2 -min g∈G wg D T [g] θ 2
.

The following Lemma extends the screening tests ST3 [START_REF] Xiang | Learning sparse representations of high dimensional data on large scale dictionaries[END_REF] and DST3 (see Lemma 3) to the Group-Lasso.

Lemma 6 (The Dynamic Group ST3: DGST3). For any θ ∈ R N , the following function T DGST3 θ is a screening test for P Group-Lasso (λ, D, G, y):

T DGST3 θ : Γ → {0, 1} i →   w g(i) D [g(i)] - D T [g(i)] c 2 D [g(i)]   > r θ ( 18
)
where .

c Id - nn T n 2 2 y λ + n n 2 2 w 2 g * , n D [g * ] D T [g * ] y λ * , r θ y λ -µθ 2 2 - y λ -c 2
In these two Lemmata, the regions R used to define the screening tests are spheres and the effect of the radius r θ on the screening capacity is visible in [START_REF] Wang | Lasso Screening Rules via Dual Polytope Projection[END_REF] and [START_REF] Xiang | Learning sparse representations of high dimensional data on large scale dictionaries[END_REF].

The proposed screening tests have been given for the Group-Lasso formulation, but can be readily extended to the Overlapping Group-Lasso [START_REF] Jacob | Group Lasso with overlap and graph Lasso[END_REF] thanks to the replication trick.

C. A turnkey instance

As a concrete instance of Algorithm 3, we propose to focus on the Lasso problem solved by the combined use of ISTA and SAFE. We compare the static screening with the dynamic screening, through implementations given in Algorithms 4 and 5, respectively. The usual ISTA update appears at lines 7 to 9 in Algorithm 4 and lines 5 to 7 in Algorithm 5, where the step size L t is set using the backtracking strategy as described in [START_REF] Beck | A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems[END_REF]. The remaining lines of the algorithm, dedicated to the screening process, are described separately in the following paragraphs. ... ISTA update .....

7:

θ t ← D 0 x t-1y 8:

z t ← D T 0 θ t 9:
x t ← prox Lasso λ/Lt x t-1 - The state-of-the-art static screening shown in Algorithm 4 is the successive use of the SAFE screening test -Lemma 2 with θ = y results exactly in lines 2-3prior to the ISTA algorithm. The dictionary is screened once for all, using information from the initially-available data D T y and λ.

µ t ← θ T t y λ θt 2 2 zt -1 ∞ -zt -1 ∞ 10: v t ← µ t θ t 11: r t ← y λ -v t 2 12: I t ← i ∈ Γ, |d T i y| < λ(1 -r t ) ∪ I t-
The proposed dynamic screening principle is shown in Algorithm 5. The iteration is here composed of two stages: a) the ISTA update (lines 5-7) which is exactly the same as lines 7-9 of Algorithm 4 except that the dictionary changes along iterations and b) the screening step (lines 9-13) which aims at reducing the dictionary size thanks to the information contained in the current iterates θ t and z t . The screening process appears at lines 11-13 where the index sets I t of screened atoms form a non-decreasing inclusion-wise sequence (line 12).

D. Computational complexity of the dynamic screening

The screening test introduces only a negligible computational overhead because it mainly relies on the matrix-vector multiplications already performed in the first-order algorithm update. We present now the computational ingredients of the acceleration obtained by dynamic screening.

Algorithm 3 implements the iterative alternation of the update of any first-order algorithm -e.g. those from Table I-at line 4, and a screening process at line 6-8. This screening process consists of the pairing of two distinct stages. First the set I t of screened atoms is computed at line 6 using one of the Lemmata 2 to 6. Analyzing these Lemmata shows that the expensive computation required to evaluate the screening test T θt (i) for all i ∈ Γ is both due to the products d T i c for all i ∈ Γ and to the computation of the scalar µ which needs the product D T t θ t . Thus, determining a set of inactive atoms may cost O(KN ) per iteration. Fortunately, the computation D T c can be done once for all at the beginning of the algorithm. Table I shows that the computation D T t θ t is already done by every first-order algorithm. So determining I t produces an overhead of O( I c t-1 + N ) only. Second the proper screening operations reduce the size of the dictionary and the primal variables at lines 7 and 8, with a small computation requirement because matrix Id [I c t ,I c t-1 ] has only |I c t | non-zero elements. So, finally, the computation overhead entailed by the embedded screening test has complexity O( I c t-1 + N ) at iteration t which is negligible compared with the complexity O( I c t-1 N ) for the optimization update p(•). A detailed complexity analysis is given in Section III-A. Finally the total computation cost of the algorithm with dynamic screening may be much smaller than the base first-order algorithm. This is evaluated experimentally in Section III.

III. EXPERIMENTS

This section is dedicated to experiments made to assess the practical relevance of the proposed dynamic screening principle 2 . More precisely, we aim at providing a rich understanding of its properties beyond what the theory can demonstrate. The questions of interest deal with the computational performance and may be formulated as follows:

• how to measure and evaluate the benefits of dynamic screening?

• what is the efficiency of dynamic screening in terms of the overall acceleration compared to the algorithm without screening or with static screening? • to which extent does the computational gain depend on problems, algorithms, synthetic and real data, screening tests?

A. How to evaluate: performance measures

Let us first notice from Theorem 1 that whatever strategy is used -no-screening/static screening/dynamic screening-, the algorithms converge to the same optimal x. Consequently, there is no need to evaluate the quality of the solution and we shall only focus on computational aspects.

The main figure of merit that we use is based on an estimation of the number of floating-point operations (flops) required by the algorithms with no screening (flops N ), with static screening (flops S ) and with dynamic screening (flops D ) for a complete run. We will represent experimental results by the normalized number of flops flops S flops N and flops D flops N that reflect the acceleration obtained respectively by the static screening and dynamic screening strategies over the base algorithm with no screening. Computing such quantities requires to experimentally record the number of iterations t f and for each iteration t, the size of the dictionary |I c t | and the sparsity of the current iterate x t 0 . They are defined for the Lasso as:

flopsN t f t=1 (K + xt 0 )N + 4K + N flopsS KN + t f t=1 (|I c 0 | + xt 0 )N + 4 |I c 0 | + N flopsD t f t=1 (|I c t | + xt 0 )N + 6 |I c t | + 5N
and for the Group-Lasso as: Note that the primal variable which would be sparse during the optimization procedure which reduce the number of operation required for D t x t from |I c t | N to x t 0 N . Note also that here we do not take into account the time required to compute the matrix norm of the sub-dictionaries corresponding to each group: D [g] , g ∈ G. These quantities do not depend on the problem P(λ, Ω, D, y) but on the dictionary and the groups themselves only, so we consider that they can be computed beforehand for a given dictionary D and a given partition G.

flopsN t f t=1 (K + xt 0 )N + 4K + N + 3 |G| flopsS KN + t f t=1 (|I c 0 | + xt 0 )N + 4 |I c 0 | + N + 3 |G| flopsD t f t=1 (|I c t | + xt 0 )N + 7 |I c t | + 5N + 5 |G| Indeed,
Another option to measure the computational gain consists in actual running times, which we consider as well. The main advantage of this measure would be that it results from actual performance in seconds instead of estimated or asymptotic figure. However, running times depend on the implementation so that it may not be the right measure in the current context of algorithm design. For each screening strategy (no screening/static/dynamic) we measure the running times t N /t S /t D . The performance are then represented in terms of normalized running times t D t N and t S t N . Eventually, one may wonder whether those measures, flops and times, are somehow equivalent, which will be checked and discussed in Sections III-C and III-D.

B. Data material 1) Synthetic data:

For experiments on synthetic data, we used two types of dictionaries that are widely used in the state-of-the-art of sparse estimation and screening tests. The first one is a normalized Gaussian dictionary in which all atoms d i are drawn i.i.d. uniformly on the unit sphere, e.g., by normalizing realizations of N (0, Id N ). The second one is the so-called Pnoise introduced in [START_REF] Xiang | Fast Lasso screening tests based on correlations[END_REF], for which all d i are drawn i.i.d. as e 1 + 0.1κg and normalized, where g ∼ N (0, Id N ), κ ∼ U(0, 1) and e 1 [1, 0, . . . , 0] T ∈ R N is the first natural basis vector. We set the data dimension to N 2000 and the number of atoms to K 10000.

In the experiments on the Lasso, observations y were drawn i.i.d. from the exact same distribution as the atoms of dictionaries described above. In experiments on the Group-Lasso, all groups were built randomly with the same number of atoms in each group. Observations were generated from a Bernouilli-Gaussian distribution: |G| independent draws of a Bernoulli distribution of parameter p = 0.05 were used to determine for each group if it was active or not. Then coefficients of active groups are drawn i.i.d. from a standard Gaussian distribution while they are set to zero in inactive groups. The observation y was generated as the (l 2 -normalized) sum of Dx and of a Gaussian noise such that the signal-to-noise ratio equals 20dB.

2) Audio data: For experiments on real data we performed the estimation of the sparse representation of audio signals in a redundant Discrete Cosine Transform (DCT) dictionary, which is known to be adapted for audio data. Music and speech recordings were taken from the material of the 2008 Signal Separation Evaluation Campaign [START_REF] Vincent | The 2008 signal separation evaluation campaign: A community-based approach to large-scale evaluation[END_REF]. We considered 30 observations y with length N = 1024 and sampling rate 16 kHz and the number of atoms is set to K 10000.

3) Image data: Experiments on the MNIST database [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF] have been performed too. The database is composed of images of N 28 × 28 = 784 pixels representing handwritten digits from 0 to 9 and is split into a training set and a testing set. The dictionary D is composed of K 10000 vectorized images from the training set, with 1000 randomly-chosen images for each digit. Observations were taken randomly in the test set.

C. Solving the Lasso with several algorithms.

We addressed the Lasso problem with four different algorithms from Table I: ISTA, FISTA, SpaRSA and Chambolle-Pock. Algorithms stop at iteration t if either t > 200 or the relative variation

|F (x t-1 )-F (xt)| F (xt)
of the objective function F (x) 1 2 Dxy 2 2 + λΩ (x) is lower than 10 -7 . We used a Pnoise dictionary and three different strategies for each algorithm: no screening, static ST3 screening and dynamic ST3 screening. Algorithms were run for several values of λ to assess the performance for various sparsity levels. Figure 2 shows the normalized running times and normalized number of flops for algorithms with dynamic screening (black squares) and for the corresponding algorithms with static screening (blue circle) as a function of λ/λ * . Lower values account for faster computation. The medians among 30 runs are plotted and the shaded area contains the 25%-to-75% percentiles for FISTA, in order to illustrate the typical distribution of the values (similar areas are observed for the other algorithms but are not reported for readability).

For all algorithms, the dynamic strategy shows a significant acceleration in a wide range of parameter λ ≥ 0.3λ * . For λ ≥ 0.5λ * , computational savings reach about 75% of the running time and 80% of the number of flops. The static strategy is efficient in a much reduced range λ ≥ 0.8λ * , with lower computational gains. Among all tested algorithms, FISTA has the largest ability to be accelerated, which is really interesting as it is also known to be very efficient in terms of convergence rate. Note that due to the normalization of running times and flops, Figure 2 cannot be used to draw any conclusion on which of ISTA, FISTA, SpaRSA or Chambolle-Pock is the fastest algorithm. Finally, one may observe that the running time and flops measures have similar trends, supporting the idea that only one of them may be used to assess computational performance in a fair way.

D. Solving the Group-Lasso for various group sizes

We addressed the Group-Lasso with FISTA using Pnoise data and dictionary as described in III-B with several group sizes. In Figure 3, the median normalized running times and number of flops over 30 runs are plotted, the shaded area representing the 25%-to-75% percentiles when the group size is 5.

The computational gains obtained by the dynamic screening strategy are of the same order than for the Lasso, with large savings in a wide range λ ≥ 0.3λ * . One may anticipate that when groups grow larger it is more difficult to locate some inactive groups, Figure 3 confirms this intuition: screening tests become less and less efficient to locate inactive groups and consequently the acceleration is not as efficient as in the Lasso problem. As for the Lasso, running times and flops have similar trends, even if we observe a larger discrepancy. The discrepancy is due to implementation details. For instance the many loops on groups required for the computation of the screening tests are hard to handle efficiently in python.

E. Comparing screening tests

From the previous experiments, we retained FISTA to solve the Lasso on synthetic data with a Pnoise dictionary and a Gaussian dictionary, on real audio data, and on images. Results are reported in Figure 4 for all the proposed screening tests. For all kinds of data and all screening tests, dynamic screening again provides a large acceleration on a wide range of λ values and improves the static screening strategy. In the case of the Pnoise dictionary and of audio data, the ST3 and Dome tests bring in important improvement over the SAFE test, in the static and dynamic strategies. Indeed, λ * is close to 1 in these cases so that the radius r θ in [START_REF] Combettes | Signal recovery by proximal forward-backward splitting[END_REF] for SAFE is much larger than in (3) for ST3 and in (4) for Dome, which degrades the screening efficiency of SAFE. This difference is even more visible when the dynamic screening strategy is used. As a counterpart, the Gaussian dictionary have small correlation between atoms. In this dictionary, ST3 and Dome do not improve the performance of SAFE, but the dynamic strategy allows a higher acceleration ratio and for a larger range of parameter λ.

IV. DISCUSSION

We have proposed the dynamic screening principle and shown that this principle is relevant both theoretically and practically. When first-order algorithms are used, dynamic screening induces stronger acceleration on the Lasso and Group-Lasso solvings than static screening, and in a wider range of λ.

The convergence theorem (Theorem 1) makes very few assumptions on the iterative algorithm, meaning that dynamic screening principle can be applied to many algorithms -e.g. second order algorithms.

Conversely, dynamic screening tests may produce different iterates than those of the base algorithm on which it is applied and hence may modify the convergence rate. Can we ensure that the dynamic screening preserves the convergence rate of any first-order algorithm? Answering this question would definitely anchor dynamic screening in a theoretical context.

We presented here algorithms designed to compute the Lasso problem for a given λ. Departing from that, one might be willing to compute the whole regularization path as done by the LARS algorithm [START_REF] Efron | Least angle regression[END_REF]. Thoroughly studying how screening might be combined with LARS is another exciting subject that we plan to work on in a near future.

In a recent work [START_REF] Wang | Lasso screening with a small regularization parameter[END_REF] Wang et. al introduce a way to adapt the static dome test in a continuation strategy. This work relies on exact solutions of successive computation for higher λ parameters. Iterative optimization algorithms do not give exact solutions hence examining how the dome test can be adapted dynamically in an iterative optimization procedure might be of great interest and lead to new approaches.

Given the nice theoretical and practical behavior of Orthogonal Matching Pursuit [START_REF] Mallat | Matching pursuits with time-frequency dictionaries[END_REF], [START_REF] Tropp | Greed is good: algorithmic results for sparse approximation[END_REF], investigating how it can be paired with dynamic screening is a pressing and exciting matter but poses the problem of dealing with the non-convex ℓ 0 regularization which prevents from using the theory and toolbox of convex optimality.

Lastly, as in [START_REF] Ghaoui | Safe Feature Elimination in Sparse Supervised Learning[END_REF], we are curious to see how dynamic screening may show up when other than an ℓ 2 fit-to-data is studied: for example, this situation naturally occurs when classification-based losses are considered. As sparsity is often a desired feature for both efficiency (in the prediction phase) and generalization purposes, being able to work out well-founded results allowing dynamic screening is of the utmost importance.

SCREENING TESTS FOR THE Group-Lasso

This section is dedicated to the proofs of the screening tests given in the Lemmata 2 to 6.

Proof of Lemmata 2 and 3. Since the Lasso is a particular case of the Group-Lasso, i.e. groups of size one with w g = 1 for all g ∈ G, Lemmata 2 and 3 are direct corollaries of Lemmata 5 and 6.

Base concept:

Extending what has been proposed in [START_REF] Ghaoui | Safe Feature Elimination in Sparse Supervised Learning[END_REF], [START_REF] Xiang | Learning sparse representations of high dimensional data on large scale dictionaries[END_REF] we construct screening tests for Group-Lasso using optimality conditions of the Group-Lasso (15) jointly with the dual problem [START_REF] Dai | An ellipsoid based, two-stage screening test for BPDN[END_REF]. These screening tests may locate inactive groups in G. According to [START_REF] Ghaoui | Safe Feature Elimination in Sparse Supervised Learning[END_REF], groups g such that D T [g] θ 2 < w g correspond to inactive groups which can be removed from D. The optimum θ is not known but we can construct a region R ⊂ R N that contains θ so that max θ∈R D T

[g] θ 2 gives a sufficient condition to screen groups:

max θ∈R D T [g] θ 2 < w g ⇒ D T [g] θ 2 < w g ⇒ x[g] = 0 (19)
There is no general closed-form solution of the maximization problem in [START_REF] Xiang | Fast Lasso screening tests based on correlations[END_REF] that would apply for arbitrary regions R, moreover the quadratic nature of the maximization prevents closed-form solutions even for some simple regions R. We now present the instance of this concept when R is a sphere. The sphere centered on c with radius r is denoted by S c,r .

Sphere tests: Consider a sphere S c,r that contains the dual optimum θ, the screening test associated with this sphere requires to solve max θ∈Sc,r D T

[g] θ 2 for each group g, which has no closed-form solution. Thus we use the triangle inequality to obtain a closed-form upper-bound on the solution: Lemma 7 provides the corresponding sphere-test.

Lemma 7 (Sphere Test for Group-Lasso). If r ≥ 0 and c ∈ R N are such that θ ∈ S c,r , then the following function T GSPHERE is a screening test for P Group-Lasso (λ, D, G, y):

T GSPHERE : Γ → {0, 1} i →   w g(i) D [g(i)] - D T [g(i)] c 2 D [g(i)]   > r (20)
Proof. Let i ∈ Γ such that T GSPHERE (i) = 1 and r ≥ 0 and c ∈ R N are such that θ ∈ S c,r . We use the triangle inequality to upper bound max θ∈Sc,r D T

[g] θ 2 : max θ∈Sc,r D T [g(i)] θ 2 ≤ D T [g(i)] c 2 + max θ∈Sc,r D T [g(i)] (c -θ) 2 ≤ D T [g(i)] c 2 + r D [g(i)]
Which, as T GSPHERE (i) = 1 gives D T [g(i)] θ 2 < w g(i) . Then using [START_REF] Xiang | Fast Lasso screening tests based on correlations[END_REF] we have that x[g(i)] = 0 and x(i) = 0. Dynamic Construction of feasible point using Dual Scaling for the Group-Lasso: Before giving the proof of Lemmata 5 and 6, we need to introduce the dual-scaling strategy that computes from any dual point θ, a feasible dual point that satisfies (14b) by definition and aim at being close to y/λ to obtain an efficient screening test. Proposed by El Ghaoui in [START_REF] Ghaoui | Safe Feature Elimination in Sparse Supervised Learning[END_REF] for the Lasso this method applied to the Group-Lasso is given in the following Lemma: Lemma 8. Among all feasible scaled versions of θ, the closest to y/λ is v = µθ where:

µ θ T y λ θ 2
) 21
Proof. The dual-scaling problem for the Group-Lasso is:

µ arg min s∈R sθ - y λ 2 s.t. ∀g ∈ G, D T [g] sθ 2 < w g (22)
The solution of ( 22) is the projection onto the feasible segment [-s min , s min ] ⊂ R of the solution of arg min s∈R sθ -y λ 2 . This solution is given in [START_REF] Bonnefoy | A Dynamic Screening Principle for the Lasso[END_REF].

We now prove the SAFE test for Group-Lasso using Lemmata 7 and 8 following the same arguments as in [START_REF] Ghaoui | Safe Feature Elimination in Sparse Supervised Learning[END_REF].

Proof of Lemma 5. Let θ ∈ R N and v be its feasible scaled version obtained by dual-scaling (Lemma 8). Since y/λ attains the minimum of the unconstrained objective (14a) of the dual problem [START_REF] Dai | An ellipsoid based, two-stage screening test for BPDN[END_REF], and since v complies with all the constraints (14b), the distance between the optimum θ and y/λ is upper bounded by y λ v 2 , i.e., θ ∈ S y λ , y λ -v

2

. And Lemma 7 concludes the proof.

Proof of Lemma 6. This proof is illustrated graphically in Figure 5 in 2D. We first construct geometrically objects that are involved in the proof. Recalling that g * arg max

we define the set of dual point complying with the constraint associated with group g * as

V * θ ∈ R N , D [g * ] θ 2 ≤ w g *
This set V * is the set contained in the ellipsoid:

E * θ ∈ R N , D [g * ] θ 2 2 = w 2 g * .
Point y/λ * is on the ellipsoid: we define n as a normal vector to the ellipsoid E * at this point. Such a vector is built from the gradient of f (θ) Then the new sphere S DGST3 is defined as the bounding sphere of A ∩ S y λ , y λ -v 2 , its center is the projection of y λ on H which is given by:

c = y λ - n T y λ -w 2 g * n n 2 2
and its radius is given by the Pythagoras theorem:

r = y λ -c 2 2 - y λ -v 2 2
We now formally check that θ ∈ S c,r by showing that A ∩ S y λ , y λ -v Where the last equality is obtained using the definition of n:

n T y λ -w 2 g * = λ * λ y T n λ * -w 2 g * = λ * λ -1 w 2 g *
Then, using the definition of c, we have:

y λ -v 2 2 ≥ θ-c 2 2 + y λ -c 2 2 + 2 w 2 g * n 2 2 λ * λ -1 w 2 g * -θ T n .
As θ is contained in A we have 0 ≤ w 2 g *θ T n and:

y λ -v 2 2 ≥ θ -c 2 2 + y λ -c 2 2
We finally obtain the radius:

θ -c 2 2 ≤ y λ -v 2 2 - y λ -c 2 2 = r 2 .
Then A ∩ S y λ , y λ -v 2 ⊂ S DGST3 and θ ∈ S DGST3 . Lemma 7 concludes the proof of Lemma 6.

Figure 1 :

 1 Figure1: Size of the dictionary D t (number of atoms) as a function of the iteration t in a basic dynamicscreening setting, starting with a dictionary with K = 5000 atoms.

  [r] b a max(min(r, b), a) denotes the projection of r onto the segment [a, b]. Lemma 2 is exactly El Ghaoui's SAFE test.

Algorithm 4 3 :

 43 ISTA + Static SAFE Screening Require: D, y, λ, x 0 ∈ R K 1: .......... Screening .......... 2:I ← i ∈ Γ, |d T i y| < λ -1 + λ λ * D 0 ← D [I c] , 4: t ← 1 5: while stopping criterion on x t do 6:

Figure 2 :

 2 Figure 2: Normalized running times and normalized number of flops for solving the Lasso with a Pnoise dictionary.

Figure 3 :

 3 Figure 3: Normalized running times an number of flops for FISTA solving the Group-Lasso with different group sizes (5, 10, 50, 100).

Figure 4 :

 4 Figure 4: Computational gain of screening strategies for various data and screening tests, on the Lasso solved by FISTA.

Figure 5 :-v 2 (, y λ -v 2 ⊂ A ∩ S y λ , y λ -v 2 .

 5222 Figure 5: Geometrical illustration of regions associated to the screening tests for the Group-Lasso

2 ⊂

 2

  Update x t using D t D t+1 ← Screen D t using x t+1 end loop

	Algorithm 1	Algorithm 2
	Static screening strategy	Dynamic screening strategy
	D 0 ← Screen D loop t	D 0 ← D loop t
	x t+1 ←Update x t using D 0 end loop	x t+1 ←

This work was supported by Agence Nationale de la Recherche (ANR), project GRETA 12-BS02-004-01. R.G. acknowledges funding by the European Research Council within the PLEASE project under grant ERC-StG-2011-277906.

  2N for the computation of the r θ . The screening step is then computed in |I c t | operations. The static screening approach implies a separated initialization of the screening test which requires KN operations.

one update of a first-order algorithm at iteration t requires at least 2 |I c t | N +|I c t |+N to compute the gradient, and the proximal operator of the Lasso and Group-Lasso need, 3 |I c t | and 3 |I c t | + 3 |G| operations, respectively (see Table I, (4) and (13)). The dynamic screening requires the computation of µ: 2N + |I c t | and 2N + 2 |I c t | + 2 |G| for Lasso and Group-Lasso respectively, (see Lemma 2-6), and

Algorithm 3 uses notation with screening tests indexed by a dual point θ however the proposed Algorithm 3 is valid in a more general case for any screening test T that may be designed. We use the notation T θ since in this paper -and in the literature-screening tests are based on a dual point.

The code in Python and data are released for reproducible research purposes at http://pageperso.lif.univ-mrs.fr/~antoine.bonnefoy.


Jason Mahdjoub
email: jason.mahdjoub@univ-reims.fr

Francis Rousseaux
email: francis.rousseaux@univ-reims.fr

Planning and Optimization of Resources Deployment: Application to Crisis Management

Crisis management challenges decision support systems designers. One problem in the decision marking is to develop systems able to help the coordination of the different involved teams. Another challenge is to make the system work with a degraded communication infrastructure. Each workstation or embedded application must be able to help to make a decision with a degraded network by taking into account the potential decisions made by other agents. We propose in this article a multiagent model, based on an ant colony optimization, and designed to manage the complexity in the deployment of resources to solve a crisis. This model is able to manage data uncertainty, and its global goal is to optimize, in a stable way, fitness functions, like saving lives, defined by multiple users. Moreover, thanks to a reflexive process, the model is able to manage the effects into the environment of its decisions, in order to take more appropriate decisions. Thanks to our transactional model, the system is also able to take into account a large data amount without exploring all potential solutions. The graphical interface should be able to make the user defining rules database. Then, if the nature of the crisis is deeply unchanged, users should be able to change rules' databases.

I. INTRODUCTION

Today, crisis management is an important domain throughout the world. It can concern earthquakes, industrial accidents, nuclear crises, etc [START_REF] Traore | Learning Diagnoser and Supervision Pattern in Discrete Event System : Application to Crisis Management[END_REF]. Moreover, crises can appear as an imbrication of several emergencies, which can produce more complex crises. One isssue is to manage and minimize the effects of this complexity. Our work is centered on the optimization of tasks planning and resources deployment, through an embedded application distributed into an asynchronous network.

This study refers to the project AidCrisis, co-financed by the Champagne Ardenne region and FEDER. The project aims to produce solutions for the decision making, in order to prevent mainly from nuclear, radiological, bacteriologic and chemical risks. Three kinds of aspects have been discriminated [START_REF] Sediri | Vers une représentation de situations de crise gérées par le SAMU[END_REF]. The first one consists of preparing or anticipating potential crises, through classification of circumstances, identification of critical sites, training, scripting events [START_REF] Mawas | Towards a knowledge-intensive serious game for training emergency medical services[END_REF], simulation, etc. The second aspect consists of treating an effective crisis, by identifying it, deploying resources and managing the logistic, dealing with localized events, and exposing results. The third aspect consists of analyzing the crisis after its progression, into order to deduce lessons.

During the treatment step, several groups, like first aid agents, police, Doctors, government delegates must collaborate into the working site. Each group has to follow its own organization, and its own goals, according to a categorized event. Three kinds of groups have been segmented [START_REF] Traore | Learning Diagnoser and Supervision Pattern in Discrete Event System : Application to Crisis Management[END_REF], which are the management centers, the hospital centers, and the agents working on the accident area. We have noticed three kinds of problems which can obstruct the coordination of the different teams:

1) due to a high quantity of information or queries, decision centers or chiefs can be exceeded. Since teams have to wait for orders and can't always take initiatives, this can have as a consequence dramatic deadlocks. [START_REF] Traore | Learning Diagnoser and Supervision Pattern in Discrete Event System : Application to Crisis Management[END_REF] has proposed an adaptive supervision model which enables the decision centers to detect and prevent anomalies into the rescue process. 2) during a crisis, a high number of victims or potential victims can be concerned. Moreover, several events can be imbricated, and several future events can appear. Decision center has to manage uncertain information, and make a decision according to an environment which can be very complex. [START_REF] Matta | Representing Experience on Road Accident Management[END_REF] has proposed a model that organizes and summarizes experiences gained by every agent involved by the crisis management, this in order to screen these experiences at the right time. 3) the network used for the communication between each agent can be degraded, because of an overloaded network, or because of a material degradation of the network due to the crisis. In this case, every group involved can be isolated. Without communication, no decision can be taken, and no action can be deployed.

Considering this context, we work for the development of an embedded application able to manage three aspects. Firstly, the application must perform into several workstations/smartphones, through a distributed and asynchronous network. Each workstation must be autonomous if the network is degraded, and must manage the potential decision of every non-connected workstation. As a consequence, every developed algorithm must work in the perspective of these constraints, in order to prevent the problem number 3. Secondly, the application must optimize the assignment of tasks and the deployment of human and material resources by regarding current events and potential future events, described as uncertain data. This aims to prevent the problem number 2. Thirdly, the application must produce an avatar for each final user, so that it can constitute a profile that describes its practices. By an emerging phenomena, this takes into account the hierarchy decisions, even if the network is degraded, or even if the decision center is exceeded. This aims to prevent the problems number 1 and 3.

We present into this article a model that covers the second aspect, centered around optimization of the tasks choice (i.e. the constitution of a strategy to apply considering a crisis) and the deployment optimization of the human and material resources. The choice of the tasks, which are defined by the user, depends on their efficiency, and the choice of the resources depends on their availability in time and space. In the section II, we relate the different algorithms of optimization and we justify our choice. According to a particular data structure articulating events, goals, tasks, and resources, we propose an adaptation of the chosen algorithm into the section III. This model is adapted for large scale applications, manages uncertainty, and by a reflexive process, adapts its decision process according to the effect of its decisions over the time. We end with a conclusion and perspectives into the section IV.

II. RELATED STUDIES

A. Critical of statistical approaches

Statistical approaches have this default that although their predictions seem in average good, they can seriously induce the human and computer deliberation to severe faults. For example, Parunak et al. [START_REF] Van Dyke | Global convergence of local agent behaviors[END_REF] have demonstrated how a colony of agents, typically a prey/predator ecosystem, can prove wrong a statistical approach. Others objections have been done about more complex statistical approaches. For example, the modern portfolio theory [START_REF] Markowitz | Portfolio selection*[END_REF], which is a well known theory of finance, was criticized for example by [START_REF] Mandelbrot | The Misbehavior of Markets: A Fractal View of Financial Turbulence[END_REF], [START_REF] Taleb | The Black Swan: Second Edition: The Impact of the Highly Improbable[END_REF]: the theory would be elegant but would consider an environment which does not correspond exactly to the reality, in particular the distribution of observed random variables. [START_REF] Taleb | The Black Swan: Second Edition: The Impact of the Highly Improbable[END_REF] proposes to prefer more stable laws like the Pareto law to deal with random variables which does not follow a normal distribution.

The interpretation of a model is often developed according to the model itself, and the only way to develop the criticism and to avoid a kind of fatalism would be to construct new models. By opposition or competition with statistical based models, our way is to develop a simulation based model designed for coordination and affectation of human and material resources. Simulation based model have the advantage to make appear empirically unlikely phenomena, where statistical approaches could consider some potentially important events as insignificant. However, both simulation and statistical based model could accumulate approximations, which should make the system producing incoherent data, then incoherent decisions. To avoid, or at least to limit this phenomena, we suppose that the introduction of the data uncertainty should force the system to have a stable reaction. Then, data should have superposed states, and used fitness functions should return several evaluations, each of them having a probability of apparition. To face up to unstable events which are a signature of crises and social interactions, and to avoid decisions which do not produce dramatic issues as seen in previous examples, we based the combination of our superposed evaluations on the Pareto law. Simulation, optimizations, and finally decision making are done according to several goals which can be independent or correlated. We will describe now the related approaches that deal with multi-goal optimization.

B. Combinatorial optimization 1) General approaches:

A problem of combinatorial optimization can be defined as follow: considering a set of combinations S and a fitness function f : S → IR, the combinatorial optimization consists of find the combination s ∈ S minimizing f such as: f (s) ≤ f (s i ), ∀s i ∈ S.

According the related works exposed in [START_REF] Alaya | Optimisation multi-objectif par colonies de fourmis. Cas des problèmes de sac à dos[END_REF], two main types of optimization algorithms exists: complete approaches and heuristic approaches.

Complete approaches have to explore every combination contained into S. Branch and bound solutions have to explore all branches of a tree, to determine the best branch, then the best solution. Whereas dynamic programming solutions is to begin to resolve the shortest subproblems, and then to go toward problems which are increasingly complex. Complete approaches do not permit to resolve problems whose complexity class is NP. They consume too much resources because of the exploration of the entire combinations.

Heuristic approaches can be decomposed into two kinds of approaches: local search approaches and constructive approaches.

Local search approaches consist of working with current solutions, which can be chosen randomly. For a current solution, the method has to parse neighboring solutions and select the best one. The method is reiterated until no better solution was found. Then, the best returned solution is selected according to the comparison of all fixed current solutions. The main difficulty of this approach is to avoid local optimum. To do that, the Taboue algorithm [START_REF] Glover | Future paths for integer programming and links to artificial intelligence[END_REF] accepts temporarily worse solutions in its neighboring, in order to have a more deeper exploration. Simulated annealing method [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF] was inspired from annealing in metallurgy. It is a statistical method which consist of virtually control the temperature of the material, i.e. the set of solutions. If the temperature is hot (or cold), particles are free (or not) and then solutions are free to move from one to another (or not). Then, the method consist of progressively decreasing the temperature, to make the system converging to the better optimums. Inspired from observations of the nature, genetic approaches [START_REF] Holland | Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence[END_REF] consist of making in competition several individuals of a population. Each individual is determined by a genetic code, itself initially determined randomly. Then according to a selection corresponding to individuals evaluations, these last are authorized to reproduce themselves. Moreover, mutations are possible during the reproduction process. Several strategies have been developed in the genetic algorithms domain, to avoid local optimum, but global optimum cannot be insured. Particle swarm optimization [START_REF] Kennedy | Particle swarm optimization[END_REF] is also an evolutionary approach, but based on a stochastic approach. The method is inspired from the observation of the movement of organisms in a bird flock or fish school. Particles adapt their speed and their directions according to the current optimal solutions, to discover new potential solutions.

Constructive approaches start with empty solutions, and construct them incrementally. Greedy algorithms aims to construct incrementally solutions until obtaining a complete solution. The choice of each element can be made randomly, or according to a heuristic, called gradient criterion. The performance of this approach depends highly on the gradient criterion. So it is not adapted for all applications. Estimation of distribution algorithms [START_REF] Larraaga | Estimation of Distribution Algorithms[END_REF] are evolutionary models based on the progressive construction of probabilities defining the quality of the choice of some elements. If the model evolves initially randomly, it gradually construct solutions whose elements have produced good solutions on the past. Initially proposed in [START_REF] Dorigo | Optimization, Learning and Natural Algorithms[END_REF], optimizations by ant colony consist of taking advantage in the use of the potential of the intelligence emerging from a collective work of an ant colony. The ant colony optimization (ACO) consist for ants in founding the shortest path between the anthill and the nearest located food. Ant colony algorithms are well adapted for problems whose complexity class is NP. We will see how this algorithm is mathematically formalized for multi-goal optimization problems.

In most time, our application should coordinate local resources to manage a crisis. Moreover, every combination of task and every strategy do not have to use all human and material resources. But sometimes, in a severe crisis context, the system could take into account a large set of resources. For example, in a forest fire context, the system could have to call firemen which come from other regions, and sometimes from other countries. Taking account of every resource of every region could become a very complex problem. But the ant colony algorithm let show us that ants do not really explore all their environment and become near from their anthill. Moreover it is possible to limit the exploration of the ants according to the best current obtained path. For this reason, ant colony algorithm appears for us well adapted. Moreover, since this algorithm is also well adapted for routing the Internet traffic [START_REF] Caro | AntNet: Distributed Stigmergetic Control for Communications Networks[END_REF], it is also adapted for an embedded application encapsulated into a distributed cloud, as we are trying to develop. Then, even if a workstation does not have the entire data of the entire regions, the ants can move from a workstation to another to look for their goal. And because, they don't have to explore all their environment, the system can resolve a goal without making all workstations contributing to the problem.

III. THE PROPOSED APPROACH

A. Overview of our approach 1) Goals: Thanks to a rules database, the system has to generate a plan of actions and a plan of deployment of the different human and material resources to manage the crisis ongoing, its uncertainty, and its dynamical reaction to human intervention. Another challenge is to develop an ACO algorithm that do not explore all the space of solutions, when it is not necessary.

2) Data structure: Structurally, the input data is organized as follow. From a graphical interface, and before a crisis appears, different actors into the management center can enter into the system different kind of possible events. These events correspond to possible real events like fire, health problem, aggression, etc. Then, each of these events/problems can be specialized into sub-events. For example, fire can be specified as a house fire, a public building fire or a nuclear power station fire. Moreover, a set of events can be a superposed state. For example, during a crisis, if a user has entered that a fire has appeared, and if he has not got time to specify if the fire concerns a public building or a house, than two events are in a superposed state with their respective probability of apparition. Each event parameter can be fuzzy. For example, the fire can be described by a parameter named 'importance', and this importance can be 'low', 'normal', or 'high'. Moreover, each event can trigger other events. For example, a fire into nuclear power station can trigger several events like 'irradiation events'. More generally, trigger functions are available for the user to trigger an event according to the evolution of the parameters of another event. For each event, the system has to solve a goal. A goal can have several fitness functions to minimize. To reach this goal, the user has to enter a graph of possible tasks to apply. For each task, a list of resources can be used. Moreover, each task can be localized or not. If it is the case, the system generates tasks of transportation of resources. Fitness functions are dependent from event parameters. The application of the main tasks alter the event parameters. Then, this have directly an effect to the results returned by fitness functions.

3) Algorithm: The first step of our method is to decompose according to a discrete grid, events which have superposed time position and space position, into superposed events which have unique positions.

Once we get events with unique space and time positions, the system deduces the list of goals it have to solve. For each goal, the system will have to plan the allocation of resources according to time and space, and without conflict with other goals. One solution to solve these goals is to consider them as a global multi-goal optimization problem. However, this solution will force the system to process a global optimization centralized into one server, and making the entire network dependent from this server. We propose instead of this solution a transactional model. Our solution consists of optimizing each individual goal as bubble of realities. Then, if two bubbles have conflicts of resources, a parent bubble will be generated to solve these conflicts by generating sets of constraints adapted for each possible alternative solution. Thanks to this transactional model, resources data which can be located only into some servers, workstations, or smart-phones, are explored during the goal optimization step only when no close free resource have been detected. As for the transactional memory programming [START_REF] Larus | Transactional Memory[END_REF], this method should give in most cases, better performances. When all bubbles have been optimized, and when all bubbles have any conflict with any bubbles, than the system goes to the dynamical projection step.

When a task is applied into the environment, the state of the system is likely of changing. With our data structure, the application of a task, or the application of another task will change the evolution of the events, and those of the triggered events. So deliberation of the system can alter the variables responsible of this deliberation, and then alter this deliberation. Since we do not consider global exploration (see previous paragraph), we have developed the next strategy. When all bubbles have been optimized, the system project for each bubble their related decisions over time, i.e. for each bubble, the system deduces new events from the application of tasks into the environment. These deduced events are merged with equivalent events which have been deduced in the previous loops. The fusion process consists of considering a same deduced event as an event which has superposed states. From this set of deduced events, is deduced a new set of bubbles, with new bubbles and/or bubbles that have changed. If changes have been detected, the system goes back to the bubble optimization step. Else, it proposes its plan of resources deployment and its plan of tasks to apply.

The figure 1 summarizes the working of our system. The sub-section III-B describes the data structure of our system. The sub-section III-C describes an ant colony optimization algorithm for multi-goal optimization problem. The sub-section III-D describes how we adapted this algorithm into the context of our application.

B. Data structure

The data structure of our model is composed of events, goals and tasks.

1) Events: When events are triggered, their occurrences define each property content and each probability related to each superposed state. However, an event can see some of its properties, like its position, predefined. The occurrence of an event E is noticed O E .

There are different types of events E:

• atomic events AE: they are not reducible. Moreover, the occurrence of these events can have a location which is a superposed state:

|L(O AE ) = ||L(O AE ) | i=1 λ O AE ,i |L(O AE ) i , where |λ O AE ,i | 2 is the probability that the location |L(O AE ) i is valid.
• list of events that must occurs at the same time which is a set SE of events, whatever their types.

• superposed events are events, whatever their types, which are exclusives. |λ SIE,i | 2 = 1 and |λ SIE,φ | the probability that the event |SIE is not an event/is nothing. The occurence of superposed events, is a superposed occurences of events. Events are triggered after relative time T (E), with respect to time of apparition of the parent event. The absolute time of an event is defined as follow: T A(E) = T (E) + T (P arent(E)), where P arent(E) = ∅ if the current event has no parent, and where T (∅) = 0. The time T (E) can be a superposed state |T (E) .

In addition to location and time properties, atomic events have customized properties P (AE) defined by the user. Each property |p(O AE , t) j ∈ P (O AE ) can be a superposed state.

The function EEP (p(O E ) j , t) makes evolve event parameter p(O E ) j at relative time t. This function is defined by the user. It can be defined for example as an affine function, but it can also be defined by a simulation based model. For example, it is possible to add for a radioactive cloud, a simulation model that make evolving parameters according to time.

The function DE(E, t) deduces new events from event E at time t. This deduction is dependant from the evolution of the event parameters. This function is defined by the user.

The function |CE(E, t) tells if the event is closed at time t. This function depends from the evolution of the event parameters.

2) Decomposition of atomic events: Atomic events are decomposed into superposed events if they have superposed location in the space |L(O AE ) , and/or if they have superposed time of triggering |T (E) . The decomposition is done through the algorithm III-B2.

3) Goals and fitness functions: They are defined by users according to predefined fitness functions. For each atomic event AE, a global fitness function to minimize F AE (strategy) is defined. This last evolves according to events parameters which are altered after applying a plan of deployment of resources. It can be composed of several local fitness functions to minimize:

F AE (x) = (f AE (x) 1 , f AE (x) 2 , . . . , f AE (x) m ) m ≥ 1 with F = (f 1 : D → R, f 2 : D → R, . . . , f m : D → R) (1)
Algorithm 1 Decomposition of occurrences of events according to their superposed states of position and time.

LST OE is the list of current occurrences of events.

for all O E ∈ LST OE do if O E is an occurrence of atomic event then if |L(O E )| > 1 or |T (O E )| > 1 then
(if the event have several positions in the space or over the time)

|O SIE ← new superposed event with |L(O E )| × |T (O E )| superposed states. for i = 1 to i = |L(O E )| do for j = 1 to j = |T (O E )| do |O SIE i+j×|L(O E )| ← O E where: L(|O SIE i+j×|L(O E )| ) = |L(O E ) i T (|O SIE i+j×|L(O E )| ) = |T (O E ) j λ O SIE ,i+j×|L(O E )| ← λ L(O E ),i × λ T (O E ),j end for end for Add |O SIE to LST OE . Remove O E from LST OE . end if end if end for
where m if the number of functions to optimize, and x being the vector of decision variables. In our case, x corresponds to the resulting event parameters after the application of a strategy of ressources deployment.

Each of these fitness functions is classified according to an integer greater or equal than zero. The class i is optimized independently and primarily versus class i+1, and the class i+ 1 is optimized only when the class i was optimized, taking only remaining resources. This classification enables us to say that a life-threatening like heart attack is managed independently and primarily than a less critical problem, like an angina. F AE is now defined by a set of functions, each of them defined by a class and a set of functions:

F AE (x) = {Ci AE (x)} with i ∈ C AE , C AE ⊂ N, Ci AE (x) = (f Ci,AE (x) 1 , f Ci,AE (x) 2 , . . . , f Ci,AE (x) m Ci ) with m Ci ≥ 0 (2)
with C AE being the set of classes.

a) Superposed scores: since events parameters are superposed, fitness functions can also be a superposed state. Let |f Ci,AE (x) j being the superposed score of the efftects produced by the strategy x related to the atomic event AE and the fitness function f j (see equation 2). We say for the effects x and y that |f Ci,AE (x) j ≺ |f Ci,AE (y) j , i.e. x is a better situation than y regarding the fitness function f Ci,AE () j , if ∀v ∈ R, p(|f Ci,AE (x) j < v) > p(|f Ci,AE (y) j < v) where p(|f Ci,AE (x) j < v) is the probability that the superposed state |f Ci,AE (x) gives values lower than v. This formula is directly inspired from the Pareto law, and is justified by the necessity to manage uncertainty in a stable way. b) Domination: Domination of a strategy versus another strategy enables to know if a strategy is better from another. According our fitness functions classification, the algorithm III-B3b defines how between two strategies x and y, we can say if x dominates y, if y dominates x, or if x and y are equivalent. If x dominates y, we notice x ≺ y.

Algorithm 2 Relation of dominance between between the effects produced by two strategies x and y.

x c) Fusion: when two managed events needs the same resources, a transactional model is used to managed conflicts of resources. During this process, the fitness functions related to the two events are merged. Let F AE0 being the fitness function related to the event AE 0 and F AE1 being the fitness function related to event AE 1 . The merging of the two fitness functions F AE0 ∪ F AE1 is done as follow:

F AE0+1 = {Ci AE0+1 (x)} with i ∈ C AE0+1 , C AE0+1 = C AE0 ∪ C AE1 , C AE0+1 ⊂ N (3) Ci AE0+1 (x) =(|f Ci,AE0 (x) 1 , . . . , |f Ci,AE0 (x) m Ci,AE 0 , |f Ci,AE1 (x) 1 , . . . , |f Ci,AE1 (x) m Ci,AE 1 )
with m Ci,AE0 ≥ 0, m Ci,AE1 ≥ 0 4) Resources and tasks: A resource O r can be a material, a human, or an autonomous material. Each resource can be organized according to types r, and each type can generalize several types. A resource must be used during the application of a task, and each resource can be used into several tasks. The percentage U (d, r) defines in which proportion the task d use the resource r. A resource can be transportable or not. Moreover, a resource may need other resources to work. For example, ambulances need a driver to be used.

For every atomic event AE, a directed graph G AE (E AE , V AE ) of possible tasks to apply is defined by the user. This graph have a starting node SN and a ending node EN . It corresponds to a set of possible alternatives to apply during a crisis. For example, for a specific health problem, it is possible to send a doctor to treat patient, or it is possible to give instructions through phone conversation, if no doctor is available. Each node d G AE ∈ E AE , d G AE = SN = EN represents a possible task to apply. A task need resources R to be applied. When a task is applied, the system alter event parameters according to the function Inf luence(P (O AE ), d G AE , O R ), where P (O AE ) is the properties of the occurrence of an atomic event AE, and O R is the set of resources used for this tasks.

The association of successive tasks, starting from the node SN and ending to the node EN , determines a plan pl AE ∈ P L AE where P L AE is the set of all possible plans to apply.

The task of human and material transportation need a specific implementation. The objective of our system is to optimize this task according to a specific implementation. Moreover, several alternatives can be generated. For example, a task of transportation of resources used to apply a task A can also be the same task of transportation of resources used into the next task B. The goal of our system is to automatically generate these alternatives as nodes into the graph G AE . Then, for each alternative, the system looks for the best path between a location and the available resources, without exploring paths for each resource.

C. Ant colony optimization (ACO) for multi-goal optimization problems

Our system must be able to solve problems which are formalized according to several goals, i.e. several fitness functions (see section III-B3). [START_REF] Iredi | Bi-criterion optimization with multi colony ant algorithms[END_REF] discussed several ACO approaches adapted to multi-goal problems. Experimentations have been done in [START_REF] Alaya | Optimisation multi-objectif par colonies de fourmis. Cas des problèmes de sac à dos[END_REF] and it appears that the best of these approaches (m-ACO 6 ) is also a Pareto based approach. m-ACO 6 appears also better [START_REF] Alaya | Optimisation multi-objectif par colonies de fourmis. Cas des problèmes de sac à dos[END_REF] than several evolutionary algorithms. We will present in this subsection the mathematical formalism of the m-ACO 6 approach [START_REF] Alaya | Optimisation multi-objectif par colonies de fourmis. Cas des problèmes de sac à dos[END_REF], that will enable us to develop our model.

Considering that ants construct solutions through a graph G = (V, E) whose definition depends on the problem to solve, pheromones are associated to each node of the graph. The algorithm 3 show how an anthill loop is repeated until optimization has found a stable state, or has reached a maximum number of loops. Pheromones are initialized to τ max values. When the algorithm evolves, pheromones who evaporates along time cannot be lower than τ min , with 0 < τ min < τ max . This is done to avoid the system converging too quickly.

To construct a solution, a node υ i from G is chosen according to the probability p(υ i ). It is added to the solution S. Considering the constraints of the graph G, several nodes are added to S until the solution S is considered as complete. The probability to choose a node υ i is defined as follow:

p c (υ i ) = τ c (υ i ) α × η c (υ i ) β υj ∈G τ c (υ j ) α × η c (υ j ) β (4)
where τ c (υ i ) is the pheromone factor and η c (υ i ) is the heuristic factor of the candidate υ i . α and β are the parameters that determine the importance of each of these factors. c corresponds to the c th structure of pheromone, which corresponds the c th fitness function. To update pheromones, when ants have constructed their solutions, each mark of pheromone is evaporated from a constant factor. Then, new pheromones are deposited on elements of G constituting the best solutions:

τ c (υ i ) ← (1 -ρ) × τ c (υ i ) + ∆τ c (υ i ) (5)
where ρ is the factor of evaporation such as 0 ≤ ρ ≤ 1. ∆τ c (υ i ) is the quantity of deposited pheromones for the component υ i . Let S c the solution of the colony that maximizes the c th goal, in our case defined by f Ci,AE0 (x) c (see section III-B3), let S c best the solution that maximizes the c th goal from the beginning of the optimization process, and let S p being the set of non-dominated solutions produced during the anthill loop. The quantity of pheromones deposited for each element υ i ∈ S c , is defined as follow:

∆τ c (υ i ) =    1 1+f Ci,AE (S c )c-f Ci,AE (S c best )c if υ i ∈ S c , 1 if υ i ∈ S p , 0 else.

D. Optimization

When each atomic event has been decomposed according to time and space (see section III-A and section III-B2), each atomic event is transformed into a bubble of reality where optimization are done according to the limited context of the event. When each bubble is optimized, conflicts of resources are analyzed between bubbles and if necessary, bubbles are merged according to the transactional model described into the section III-D2.

1) Bubble optimization: Two kinds of bubbles exists. Leaf bubbles represent atomic events, whereas node bubbles represent peer of bubbles. Peer of bubbles are generated by the transactional model when resources conflicts are detected. Node bubbles contains peer of constraints related to each subbubble.

Leaf bubbles are optimized according to the generic algorithm 3. The construction of a solution by an ant, which is a part of the previous enumerated algorithm, is described by the algorithm 4. The leaf bubbles have to produce a plan pl AE of tasks to apply to solve the problem related to the atomic event AE. This plan results from the optimization of series of possible tasks represented by the graph G AE (E AE , V AE ) (see section III-B4). Some of these possible tasks consists of optimizing a topographic path by choosing the nearest resources from next chosen path. The construction of this topographic path follow the generic algorithm 3, by constructing solutions defined by the algorithm 5. During the path construction, if the path becomes too long, regarding the best already got path, then the path construction is restarted until a sufficiently short path is got. The path is considered too long if f (P ath best ) f (P ath) < µ, where µ is an empirically determined threshold, and f (x) is the value given by a path, finished or not. The figure 2 show how node bubbles are optimized. To optimize the two sub-bubbles, fitness functions of each subbubble is merged according to equation 3.

2) Transactional resolution of independent goals: When each bubble has been optimized, the system checks if there are conflicts of resources between each bubbles. However, instead of checking all bubbles of all related events in all regions, the system checks resources numerically localized into one workstation. Then, if one resource is used by several bubbles, more than it can be used, the system generates a parent bubble destined to solve conflicts between the two bubbles. In this case, considering the conflict, it generates peer of constraints. Each set of constraints should correspond to one sub-bubble. For example, if a resource is managed by two bubbles at the same time, two peers of constraints will be generated. The first one will consider that the first bubble can't use the conflicting resource, and the second one will consider that this Algorithm 5 Constructing a solution for one ant associated to optimization of topographic path between located resources and a located task to apply.

Let P aths being the set of paths to follow repeat choose randomly a transportable resource R j ∈ R to look for. remove R j from R. constructing a path P ath according to the ACO algorithm, until a free occurrence O(R j ) k of the resource type R j was found. is the second bubble that cannot use the conflicting resource. This operation is repeated for each peer of conflicting bubbles, and for each conflicting resources. After that, each bubble is optimized another time, until no new bubble is generated and until no constraints set is altered.

3) Dynamical projection: When all bubbles are optimized, and when no more resources conflicts are detected, the system projects its plan of resource deployment over time. Each task will have an effect to the current events, but some events will evolve by producing new events. For example, if an epidemic is not treated quickly enough, then this epidemic will be propagated over space and time. This propagation is formalized by the generation of new events, each of them being uncertain. This generation is obtained thanks to the function DE(E, t) (see section III-B1), which trigger events according to user's definitions. Then, the system had to opti- mize a plan for the likely future events, which can generate themselves new events, then new bubbles. For each loop of optimization/projection, the system updates events uncertainty according to their occurrences.

IV. CONCLUSION AND PERSPECTIVES

We have proposed a model able to plan a set of tasks and able to deploy a set of resources according to declared events during a crisis, but also according to a set of simulated events over the future. The system processes a reflexive deliberation by applying a projection of its decisions over time, and by deducing related issues to deal with. Moreover, it manages data uncertainty, according to a formalism based on the Pareto law that produces stable results, in the context of a stochastic environment. Finally, the model produces a global optimum by exploring solutions locally in a first step, and globally if necessary. This solution is then adapted to large scale systems, that should be a huge distributed network of workstations. This work can then be introduced into a more global project, i.e. the conception of an asynchronous and distributed embedded application able to manage the deployment of human and material resources in the context of a crisis. Future works should be centered into: the introduction of a user avatar taking into account the preferences of the user; the management of uncertainty related to avatars when workstations are disconnected from the network; the simplification of data managed by users through a participative solution and through an ergonomic interface [START_REF] Ma | Semantically Structured VDL-Based Iconic Tags System[END_REF], [START_REF] Rousseaux | Towards an Anthropological-Based Knowledge Management[END_REF]; the process of experimentations and evaluations.

Fig. 1 .

 1 Fig. 1. Overview of our system (diagram of activities).

Fig. 2 .

 2 Fig. 2. Node bubble optimization process (diagram of activities).

  They are defined as follow |SIE = λ SIE,φ |φ + SIE,i |Event i , |Event i are the alternative states of the super imposed event |SIE , and |λ SIE,i | 2 are their probability of apparition, with |λ SIE,φ | 2 +

	||SIE | i=1 λ ||SIE |
	i=1

  and y are strategies to compare for all i ∈ C AE with C AE ordered do xdom ← true ydom ← true for all j ∈ [1, m Ci ] do if |f Ci,AE (x) j ≺ |f Ci,AE (y) j then ydom ← f alse end if if |f Ci,AE (y) j ≺ |f Ci,AE (x) j then

	xdom ← f alse
	end if
	end for
	if xdom = true and ydom = f alse then
	Returns "x dominates y."
	end if
	if xdom = f alse and ydom = true then
	Returns "y dominates x."
	end if
	end for
	Returns "x and y are equivalent."

  ∈pheromones structures do update the c th structure of pheromones if one mark is lower than τ min , set it to τ min if one mark is higher than τ max , set it to τ max end for until A maximum number of cycles is reached or the optimization process is stable

	Algorithm 3 Generic ACO algorithm for multi-goal optimiza-
	tion problems
	initialize pheromones marks to τ max
	repeat
	processing an anthill loop...
	for all ant k ∈ colony do
	construct a solution
	simulating the application of this solution into the
	environment through Inf luence(P (O AE ), S i , O R )
	choose randomly a fitness function to optimize
	f Ci,AE0 (x) c
	evaluating the results of this simulation thanks to
	chosen fitness function
	forgive the effects of the simulation
	end for
	for all c

  AE (x) j to optimize. CurrentN ode ← SN , where SN is the start node of the graph G AE corresponding the atomic event AE. repeat choose a task d G AE ,i from CurrentN ode with probability p j (d G AE ,j ) if d G AE ,i = EN then if d G AE ,i is a transport mission then Optimize this task (see algorithm 5). EEP (p(O E ) j , T imeEnd di ), where time di is the time corresponding the end of the task d G AE ,i end if add d G AE ,i to S k Inf luence(P (O AE ), d G AE , O R ) (see section III-B4). CurrentN ode ← d G AE ,i end if until d G AE ,i = EN evaluate the simulation of the solution S k forgive AE event modifications until up to mark A.

	Algorithm 4 Constructing a solution for one ant associated to
	a leaf bubble
	Mark A
	constructing a solution where S k is the set of elements of
	this solution:
	choose randomly a function f

  Reset construction if the path is too long. if O(R j ) k must be transported thanks to another resource R t then repeat constructing a path P athT according to the ACO algorithm from the located resource O(R j ) k until an occurrence O(R t ) tk of the resource type R t was found. valid ← true if O(R t ) tk is used by another resource but not located at the same place than O(R j ) k then valid ← f alse end if if valid and O(R t ) tk has not sufficient space to transport O(R j ) k then valid ← f alse end if until valid Mark the resource O(R t ) tk as transporting the resource O(R j ) k . Note that the resource of transportation O(R t ) tk will have finally only one path to follow. if O(R t ) tk is not already used by another resource then P athT ← concatenate P ath with P athT add P athT to P aths end if else add P ath to P aths end if until R is empty Returns the different paths to follow, with their corresponding resources.