Karim Lounici

High-dimensional stochastic optimization with the generalized Dantzig estimator

Keywords: Dantzig, Sparsity, Prediction, Estimation, Sign consistency. 2000 Mathematics Subject Classification Primary: 62G25, 62G05; Secondary: 62J05, 62J12

We propose a generalized version of the Dantzig selector. We show that it satisfies sparsity oracle inequalities in prediction and estimation. We consider then the particular case of high-dimensional linear regression model selection with the Huber loss function. In this case we derive the sup-norm convergence rate and the sign concentration property of the Dantzig estimators under a mutual coherence assumption on the dictionary.

Introduction

Let Z = X × Y be a measurable space. We observe a set of n i.i.d. random pairs Z i = (X i , Y i ), i = 1, . . . , n where X i ∈ X and Y i ∈ Y. Denote by P the joint distribution of (X i , Y i ) on X × Y, and by P X the marginal distribution of X i . Let Z = (X, Y ) be a random pair in Z distributed according to P . For any real-valued function g on X , define ||g|| ∞ = ess sup x∈X |g(x)|, g = X g(x) 2 P X (dx)

1/2 and ||g|| n = 1 n n i=1 g(X i ) 2 1/2 . Let D = {f 1 , . . . , f M } be a set of real-valued functions on X called the dictionary where M 2. We assume that the functions of the dictionary are normalized, so that f j = 1 for all j = 1, . . . , M . We also assume that ||f j || ∞ L for some L > 0. For any θ ∈ R M , define f θ = M j=1 θ j f j and J(θ) = {j : θ j = 0}. Let M (θ) = |J(θ)| be the cardinality of J(θ) and sign(θ) = (sign(θ 1 ), . . . , sign(θ M )) T where

sign(t) =      1 if t > 0, 0 if t = 0, -1 if t < 0.
For any vector θ ∈ R M and any subset J of {1, . . . , M }, we denote by θ J the vector in R M which has the same coordinates as θ on J and zero coordinates on We assume furthermore that γ(y, •) is convex and differentiable for any y ∈ Y.

We assume that for any y ∈ Y the derivative ∂ u γ(y, •) is absolutely continuous. Then ∂ u γ(y, •) admits a derivative almost everywhere which we denote by ∂ 2 u γ(y, •). Consider the loss function

Q : Z × R M → R + defined by Q(z, θ) = γ(y, f θ (x)). (1)
The expected and empirical risk measures at point θ in R M are defined respectively by

R(θ) △ = E (Q(Z, θ)) ,
where E is the expectation sign, and Rn (θ)

△ = 1 n n i=1 Q(Z i , θ).
Define the target vector as a minimizer of R(•) over R M :

θ * △ = arg min θ∈R M R(θ).
Note that the target vector is not necessarily unique. From now on, we assume that there exists a s-sparse solution θ * , i.e., a solution with M (θ * ) s, and that this sparse solution is unique. We will see that this is indeed the case under the coherence condition on the dictionary (cf. Section 3 below).

Define the excess risk of the vector θ by

E(θ) = R(θ) -R(θ * ),
and its empirical version by

E n (θ) = R n (θ) -R n (θ * ).
Our goal is to derive sparsity oracle inequalities for the excess risk and for the risk of θ * in the l 1 norm and in the sup-norm. We consider the following minimization problem:

min θ∈Θ |θ| 1 subject to ∇ Rn (θ) ∞ r, (2)
where ∇ Rn △ = (∂ θ1 Rn , . . . , ∂ θM Rn ) T , r > 0 is a tuning parameter defined later and Θ is a convex subset of R M specified later. Solutions of (2), if they exist, will be taken as estimators of θ * . Note that we will prove in Lemma 3 that under Assumption 2 the set {θ ∈ Θ : ∇ Rn (θ) ∞ r} is non-empty with probability close to one. Note also that in the applications considered in Section 3, the constraint |∇ Rn (θ)| ∞ r can be defined as a system of inequalities involving convex functions. Thus, solutions to (2) exist and can be efficiently computed via convex optimization. In particular, for the regression model with the Huber loss, the gradient ∇ Rn (θ) is piecewise linear so that (2) reduces in this case to a standard linear programming problem. Denote by Θ the set of all solutions of (2). For the reasons above, we assume from now on that Θ = ∅ with probability close to one.

The definition of our estimator (2) can be motivated as follows. Since the loss function Q(z, •) is convex and differentiable for any fixed z ∈ Z, the expected risk R is also a convex function of θ and it is differentiable under mild conditions. Thus, minimizing R is equivalent to finding the zeros of ∇R. The quantity ∇ Rn (θ) is the empirical version of ∇R(θ). We choose the constant r such that the vector θ * satisfies the constraint |∇ Rn (θ * )| r with probability close to 1. Then among all the vectors satisfying this constraint, we choose those with minimum l 1 norm. Note that if we consider the linear regression problem with the quadratic loss, we recognize in (2) the Dantzig minimization problem of Candes and Tao [START_REF] Candes | The Dantzig selector: statistical estimation when p is much larger than n[END_REF]. From now on, we will call (2) the generalized Dantzig minimization problem.

Bickel et al. [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF], Candes and Tao [START_REF] Candes | The Dantzig selector: statistical estimation when p is much larger than n[END_REF] and Koltchinskii [START_REF] Koltchinskii | Dantzig selector and sparsity oracle inequalities[END_REF] proved that the Dantzig estimator performs well in high-dimensional regression problems with the quadratic loss. In particular they proved sparsity oracle inequalities on the excess risk and the estimation of θ * for the l p norm with 1 p 2.

The problem (2) is closely related to the minimization problem:

min θ∈Θ Rn (θ) + r|θ| 1 , (3)
which is a generalized version of the Lasso. For the Lasso estimator, Bunea et al [START_REF] Bunea | Aggregation for Gaussian regression[END_REF] proved similar results in high-dimensional regression problems with the quadratic loss under a mutual coherence assumption [START_REF] Donoho | Stable recovery of Sparse Overcomplete representations in the Presence of Noise[END_REF] and Bickel et al [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF] under a weaker Restricted Eigenvalue assumption. Koltchinskii [START_REF] Koltchinskii | Sparsity in penalized empirical risk minimization[END_REF] derived similar results for the Lasso in the context of high-dimensional regresssion with twice differentiable Lipschtiz continuous loss functions under a restricted isometry assumption. Van de Geer [START_REF] Van Der Geer | High dimensional generalized linear models and the Lasso[END_REF][START_REF] Van Der Geer | The Deterministic Lasso[END_REF] obtained similar results for the Lasso in the context of generalized linear models with Lipschtiz continuous loss functions.

Lounici [START_REF] Lounici | Sup norm convergence and sign concentration property of the Lasso and Dantzig estimators[END_REF] derived sup-norm convergence rates and sign consistency of the Lasso and Dantzig estimators in a high-dimensional linear regression model with the quadratic loss under a mutual coherence assumption. The paper is organized as follows. In Section 2 we derive sparsity oracle inequalities for the excess risk and for estimation of θ * for the generalized Dantzig estimators defined by (2) in a stochastic optimization framework. In section 3 we apply the results of Section 2 to the linear regression model with the Huber loss and to the logistic regression model. In Section 4 we prove the variable selection consistency with rates under a mutual coherence assumption for the linear regression model with the Huber loss. In section 5 we show a sign concentration property of the thresholded generalized Dantzig estimators for the linear regression model with the Huber loss.

2 Sparsity oracle inequalities for prediction and estimation with the l 1 norm

We need an assumption on the dictionary to derive prediction and estimation results for the generalized Dantzig estimators. We first state the Restricted Eigenvalue assumption [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF].

Assumption 1. ζ(s) △ = min J0⊂{1,...,M}:|J0| s min ∆ =0:|∆ J c 0 |1 |∆J 0 |1 ||f ∆ || |∆ J0 | 2 > 0.
It implies an "equivalence" between the two norms |∆| 2 and f ∆ on the subset {∆ = 0 :

|∆ J(∆) c | 1 |∆ J(∆) | 1 } of R M .
We need the following assumption on f θ * ∞ .

Assumption 2. There exists a constant K > 0 such that f θ * ∞ K.

From now on we take for Θ the set

Θ = {θ ∈ R M : f θ ∞ K}.
The following assumption is a version of the margin condition (cf. [START_REF] Tsybakov | Optimal aggregation of classifiers in statistical learning[END_REF]). It links the excess risk to the functional norm • . Assumption 3. For any θ ∈ Θ there exits a constant c > 0 depending possibly on K such that

f θ -f θ * c(R(θ) -R(θ * )) 1/κ ,
where 1 < κ 2.

We will prove in Section 2.1 below that this condition is always satisfied with the constant κ = 2 for the regression model with Huber loss and for the logistic regression model. We also need the following technical assumption. Assumption 4. The constants K and L satisfy

1 K, L n log M . Define the quantity r = 4 √ 2L log M n + 2 √ 6 log M n . (4)
We assume from now on that r 1.

The main results of this section are the following sparsity oracle inequalities for the excess risk and for estimation of θ * in the l 1 norm. Define

r = 6 ∂ u γ ∞ r. ( 5
)
Theorem 1. Let Assumptions 1 -4 be satisfied. Take r as in [START_REF] Bunea | Aggregation for Gaussian regression[END_REF]. Assume that M (θ * ) s. Then, with probability at least

1 -M -1 -M -K -3M -2K log n log M , we have sup θ∈ Θ E( θ) 2(1 + 2K)cr √ s ζ(s) κ κ-1 + 12 ∂ u γ ∞ κ κ -1 r2 , (6)
and

sup θ∈ Θ | θ -θ * | 1 2c √ s ζ(s) κ κ-1 ((1 + 2K)r) 1 κ-1 + 2K (κ -1)(1 + 2K) r. ( 7
)
Note that the regularization parameter r does not depend on the variance of the noise if we consider the regression model with non-quadratic loss. In this case, the use of Lipschtiz losses enables us to treat cases where the noise variable does not admit a finite second moment, e.g., the Cauchy distribution. The price to pay is that we need to assume that f θ * ∞ K with known K.

Proof. For any θ ∈ Θ define ∆ = θθ * . We have

E( θ) E n ( θ) + E( θ) -E n ( θ) = E n ( θ) + E( θ) -E n ( θ) |∆| 1 + r (|∆| 1 + r) E n ( θ) + sup θ∈Θ:θ =θ * E(θ) -E n (θ) |θ -θ * | 1 + r (|∆| 1 + r). (8)
By Lemma 1 it holds on an event A 1 of probability at least 1 -

M -K - 3M -2K log n log M that sup θ∈Θ:θ =θ * E(θ) -E n (θ) |θ -θ * | 1 + r 2Kr. (9)
For any θ ∈ Θ, we have by definition of the Dantzig estimator that

| θ| 1 |θ * | 1 . Thus |∆ J(θ * ) c | 1 = j∈J(θ * ) c | θj | j∈J(θ * ) |θ * j | -| θj | |∆ J(θ * ) | 1 . (10)
Define the function g : t → R n (θ * + t∆). Clearly g is convex and differentiable on [0, 1]. Thus, the function g ′ is nondecreasing on [0, 1] with derivative

g ′ (t) = ∇R n (θ * + t∆) T ∆. The constraint ∇ Rn (θ) ∞ r in (2) and Lemma 3 yield, on an event A 2 of probability at least 1 -M -1 , E n ( θ) = R n ( θ) -R n (θ * ) = 1 0 ∇R n (θ * + t∆) T ∆dt r|∆| 1 , (11)
for some numerical constant C > 0.

Combining ( 8)-( 11) yields that on the event

A 1 ∩ A 2 E( θ) (2 + 4K)r|∆ J(θ * ) | 1 + 12 ∂ u γ ∞ K r2 . (12)
Next,

2(1 + 2K)r|∆ J(θ * ) | 1 2(1 + 2K)r √ s|∆ J(θ * ) | 2 2(1 + 2K)cr √ s ζ(s) f ∆ c 1 κ ′ 2cr √ s ζ(s) κ ′ + 1 κ f ∆ c κ 1 κ ′ 2(1 + 2K)cr √ s ζ(s) κ ′ + 1 κ E( θD ), (13)
where we have used the Cauchy-Schwarz inequality in the first line, the inequality xy |x| κ /κ + |y| κ ′ /κ ′ that holds for any x, y in R and for any κ, κ ′ in (1, ∞) such that 1/κ + 1/κ ′ = 1 in the third line, and Assumption 2 in the last line.

Combining [START_REF] Koltchinskii | Dantzig selector and sparsity oracle inequalities[END_REF] and ( 13) and the fact that r 1 yields the first inequality. The second inequality is a consequence of ( 6) and [START_REF] Koltchinskii | Oracle inequalities in empirical risk minimization and sparse recovery problems[END_REF].

We state and prove below intermediate results used in the proof of Theorem 1.

Lemma 1. Let Assumptions 2 and 4 be satisfied. Then, with probability at least

1 -M -K -3M -2K log n log M , we have sup θ∈Θ |E(θ) -E n (θ)| |θ -θ * | 1 + r 2Kr, ( 14
)
where r is defined in Theorem 1.

Proof. For any A > 0, define the random variable

T A = sup θ∈Θ:|θ-θ * |1 A |E n (θ) -E(θ)|.
For any θ in Θ and (x, y) in Z we have

|γ(y, f θ (x)) -γ(y, f θ * (x))| ∂ u γ ∞ (L|θ -θ * | 1 ∧ 2K) ,
and

E |γ(Y, f θ (X)) -γ(Y, f θ * (X))| 2 ∂ u γ 2 ∞ |θ -θ * | 2 1 ∧ 2K 2 . Assumption 3 and Bousquet's concentration inequality (cf. Theorem 4 in Section 6 below) with x = (A ∨ 2K) log M , c = 2 ∂ u γ ∞ (AL ∧ 2K) and σ = √ 2 ∂ u γ ∞ (A ∧ √ 2K) yield P (T A E(T A ) + 2AK ∂ u γ ∞ r) M -(2K)∨A .
We study now the quantity E(T A ). By standard symmetrization and contraction arguments (cf. Theorems 5 and 6 in Section 6) we obtain

E(T A ) 4 ∂ u γ ∞ E sup θ∈Θ : |θ-θ * |1 A 1 n n i=1 ǫ i f θ-θ * (X i ) .
Then, observe that the mapping u → 1 n n i=1 ǫ i f u (X i ) is linear, thus its supremum on a simplex is attained at one of its vertices. This yields

E(T A ) 4 ∂ u γ ∞ AE max 1 j M 1 n n i=1 ǫ i f j (X i ) .
Combining Assumption 4 and Lemma 2 we obtain

E(T A ) 4 ∂ u γ ∞ Ar. Thus P (T A 6AK ∂ u γ ∞ r) M -(2K)∨A . (15)
Define the following subsets of Θ

Θ(I) = {θ ∈ Θ : |θ -θ * | 1 r} , Θ(II) = {θ ∈ Θ : r < |θ -θ * | 1 2K} , Θ(III) = {θ ∈ Θ : |θ -θ * | 1 > 2K} .
For any t > 0 define the probabilities

P I = P sup θ∈Θ(I) |E(θ) -E n (θ)| |θ -θ * | 1 + r t P II = P sup θ∈Θ(II) |E(θ) -E n (θ)| |θ -θ * | 1 + r t P III = P sup θ∈Θ(III) |E(θ) -E n (θ)| |θ -θ * | 1 + r t
For any t > 0 we have

P sup θ∈Θ |E(θ) -E n (θ) |θ -θ * | 1 + r t P I + P II + P III .
Now, we bound from above the three probabilities on the right hand side of the above expression. Take t = 12 ∂ u γ ∞ K r. Applying [START_REF] Lounici | Sup norm convergence and sign concentration property of the Lasso and Dantzig estimators[END_REF] to P I yields that

P I P T r 6 ∂ u γ ∞ K r2 M -2K ,
since we have r K by Assumption 4. Consider now P II . We have

Θ(II) ⊂ j0 j=0 {θ ∈ Θ : A j+1 |θ -θ * | 1 A j } ,
where A j = 2 1-j K, j = 0, . . . , j 0 and j 0 is chosen such that 2 1-j0 K > r and 2 -j0 K r. Thus

P II j0 j=0 P T Aj 12 ∂ u γ ∞ A j+1 K r j0 j=0 P T Aj 6 ∂ u γ ∞ A j K r (j 0 + 1)M -2K 3 log n log M -1 M -2K .
Consider finally P III . We have

Θ(III) ⊂ ∞ j=0 θ ∈ Θ : Āj-1 < |θ -θ * | 1 Āj ,
where Āj = 2 1+j K, j 0. Thus

P III ∞ j=1 P T Āj 12 ∂ u γ ∞ Āj-1 K r j0 j=0 P T Aj 6 ∂ u γ ∞ Āj K r ∞ j=1 M -Āj M -K .
We now study the quantity E max 1 j M

1 n n i=1 ǫ i f j (X i )
. This is done in the next lemma.

Lemma 2. We have

E max 1 j M 1 n n i=1 ǫ i f j (X i ) r, ( 16
)
where r is defined in (4).

Proof. Define the random variables

U j = 1 √ n n i=1 ǫ i f j (X i ).
The Bernstein inequality yields, for any j = 1, . . . , M and t > 0,

P (|U j | t) exp - t 2 2(t f j ∞ /(3 √ n) + f j 2 ) . ( 17
) Set b j = f j ∞ /(3 √ n).
Define the random variables T j = U j 1I |Yj|> fj 2 /bj and T ′ j = U j 1I |Yj| fj 2 /bj . For all t > 0 we have

P (|T j | > t) 2 exp - t 4b j , P |T ′ j | > t 2 exp - t 2 4 f j 2 .
Define the function h ν (x) = exp(x ν ) -1, where ν > 0. This function is clearly convex for any ν > 0. We have

E h 1 |T j | 12b j = ∞ 0 e t P(|T j | > 12b j t)dt 1,
where we have used Fubini's Theorem in the first equality. Since the function h 1 is convex and nonnegative, we have

h 1 E max 1 j M |T j | 12b j E h 1 max 1 j M |T j | 12b j E   M j=1 h 1 |T j | 12b j   M,
where we have used the Jensen inequality. Since the function h

-1 1 (x) = log(1+x) is increasing, we have E max 1 j M |T j | 12b j log(1 + M ) E max 1 j M |T j | 4 log(1 + M ) √ n max 1 j M f j ∞ . ( 18
)
Applying the same argument to the function h 2 , we prove that

E max 1 j M |T ′ j | 2 √ 3 log(1 + M ) max 1 j M f j . (19)
Combining ( 18) and ( 19) yields the result.

Lemma 3. Let Assumptions 2 and 4 be satisfied. Then, with probability at least

1 -M -1 , we have |∇ Rn (θ * )| ∞ r,
where r is defined in Theorem 1.

Proof. For any 1 j M define

Z j = 1 n n i=1 ∂ u γ(Y i , f θ * (X i ))f j (X i ). Since the function θ → γ(y, f θ (x)) is differentiable w.r.t. θ and |∂ u γ(y, f θ (x))f j (x)| ∂ u γ ∞ L for any (x, y) ∈ X × Y and θ ∈ R M , we have E(Z j ) = ∂R(θ * ) ∂θ j = 0.
Next, similarly as in Lemmas 1 and 2, we prove that

E(|∇ Rn (θ * )| ∞ ) 4 ∂ u γ ∞ r.
Finally Bousquet's concentration inequality (cf. Theorem 4 in Section 6 below) yields that, with probability at least 1 -M -1 ,

|∇ Rn (θ * )| ∞ E(|∇ Rn (θ * )| ∞ ) + 2 log M n ∂ u γ 2 ∞ + 2 ∂ u γ ∞ LE(|∇ Rn (θ * )| ∞ ) + ∂ u γ ∞ L log M 3n 6 ∂ u γ ∞ r.

Examples

Robust regression with the Huber loss

We consider the linear regression model

Y = f θ * (X) + W, (20)
where X ∈ R d is a random vector, W ∈ R is a random variable independent of X whose distribution is symmetric w.r.t. 0 and θ * ∈ R M is the unknown vector of parameters. Consider the function

φ(x) = 1 2 x 2 1I |x| 2K+α + (2K + α)|x| - (2K + α) 2 2 1I |x|>2K+α ,
where α > 0. The Huber loss function is defined by

Q(z, θ) = φ(y -f θ (x)), (21)
where z = (x, y) ∈ R d × R and θ ∈ Θ.

In the following lemma we prove that for this loss function Assumption 3 is satisfied with κ = 2 and c = (2/P(|W | α)) 1/2 . Lemma 4. Let Q be defined by [START_REF] Tsybakov | Optimal aggregation of classifiers in statistical learning[END_REF]. Then for any θ ∈ Θ we have

P(|W | α) 2 f θ -f θ * 2 E(θ).
Proof. Set ∆ = θθ * . Since φ ′ is absolutely continuous, we have for any θ ∈ Θ

Q(Z, θ) -Q(Z, θ * ) = φ ′ (W )f -∆ (X) + 1 0 1I |W +tf-∆(X)| 2K+α (1 -t)dt f ∆ (X) 2 φ ′ (W )f -∆ (X) + 1 2 1I (|W | α) f ∆ (X) 2 ,
since f θ ∞ K for any θ ∈ Θ. Taking the expectations we get

R(θ) -R(θ * ) P(|W | α) 2 f ∆ 2 ,
for any α > 0 since φ ′ is odd and the distribution of W is symmetric w.r.t. 0.

We have the following corollary of Theorem 1.

Corollary 1. Let Assumptions 1, 2 and 4 be satisfied. If M (θ * ) s, then, with probability at least 1 -M -1 -M -K -3M -2K log n log M , we have

sup θ∈ Θ E( θ) 8(1 + 2K) 2 P(|W | α)ζ(s) 2 sr 2 + 2 3 r 2 ,
and

sup θ∈ Θ | θ -θ * | 1 8(1 + 2K) P(|W | α)ζ(s) 2 sr + K 3(1 + 2K) r.

Logistic regression and similar models

We consider Z = (X, Y ) ∈ X × {0, 1} where X is a Borel subset of R d . The conditional probability P(Y = 1 |X = x) = π(x) is unknown where π is a function on X with values in [0, 1]. We assume that π is of the form

π(x) = Φ ′ (f θ * (x)), (22)
where the function Φ : R → R * is convex, twice differentiable, of derivative Φ ′ with values in [0, 1] and the vector θ * ∈ R M is unknown. Consider, e.g., the logit loss function Φ(u) = log(1 + e u ). We assume that Φ is known. Define the quantity

τ (R) = 1 2 inf |u| R Φ (2) (u), ( 23
)
for any R 0. We want to estimate θ * with the procedure (2) and the convex loss function

Q(z, θ) = -yf θ (x) + Φ(f θ (x)), ( 24
)
where z = (x, y) ∈ R d × {0, 1}. Thus we need to check Assumption 3 to apply Theorem 1.

Lemma 5. Let the loss function be of the form [START_REF] Van Der Vaart | Weak Convergence and Empirical Processes: With Applications to Statistics[END_REF] where Φ satisfies the above assumptions. Then for any θ ∈ R M we have

τ (K) f θ -f θ * 2 E(θ).
Proof. For any θ ∈ Θ, we have

Q(Z, θ) -Q(Z, θ * ) = ∇Q(Z, θ * ) T (θ -θ * ) + 1 0 Φ (2) (H(X) T (θ * + t(θ -θ * )))(1 -t)dt f ∆ (X) 2 ∇Q(Z, θ * ) T (θ -θ * ) + τ ( f θ ∞ ∨ f θ * ∞ )f ∆ (X) 2 .
Since ∇Q(•, •) ∞ < ∞, we can differentiate under the expectation sign, so that

E(∇Q(Z, θ * ) T (θ -θ * )) = ∇R(θ * ) = 0. Thus E(θ) τ ( f θ ∞ ∨ f θ * ∞ ) f θ -f θ * 2 .
Thus Assumption 3 is satisfied with the constants κ = 2 and c =

1 √ τ (K)
.

We have the following corollary of Theorem 1.

Corollary 2. Let Assumptions 1, 2 and 4 be satisfied. If M (θ * ) s, then, with probability at least

1 -M -1 -M -K -3M -2K log n log M , we have sup θ∈ Θ E( θ) 4(1 + 2K) 2 τ (K)ζ(s) 2 sr 2 + 2 3 r 2 ,
and

sup θ∈ Θ | θ -θ * | 1 4(1 + 2K) τ (K)ζ(s) 2 sr + K 3(1 + 2K) r.
4 Sup-norm convergence rate for the regression model with the Huber loss

In this section, we derive the sup-norm convergence rate of the Dantzig estimators to the target vector θ * in the linear regression model under a mutual coherence assumption on the dictionary and Huber's loss. The proof relies on the fact that the Hessian matrix of the risk also satisfies the mutual coherence condition for this particular model. Unfortunately, we cannot proceed similarly in the general case because the Hessian matrix of the risk at point θ * does not necessarily satisfy the mutual coherence condition even if the Gram matrix of the dictionary does. Note that for Huber's loss the Dantzig minimization problem ( 2) is computable feasible. The constraints in (2) are indeed linear, so that ( 2) is a linear programming problem. Denote by Ψ(θ) the Hessian matrix of the risk R evaluated at θ. With our assumptions on the dictionary D and on the function γ, for any θ ∈ R M we have Ψ(θ)

△ = ∇ 2 R(θ) = E ∂ 2 u γ(Y, f θ (X))f j (X)f k (X) 1 j,k M .
Note that for the quadratic loss we have Ψ(•) ≡ 2G where G is the Gram matrix of the design. For Lipschtiz loss functions the Hessian matrix Ψ varies with θ.

We consider the linear regression model [START_REF] Tibshirani | Regression shrinkage and selection via the Lasso[END_REF]. For any functions g, h : X → R, denote by < g, h > the scalar product E(g(X)h(X)). Define the Gram matrix

G by G = (< f j , f k >) 1 j,k M .
From now on, we assume that G satisfies a mutual coherence condition.

Assumption 5. The Gram matrix G = (< f j , f k >) 1 j,k M satisfies G j,j = 1, ∀1 j M,
and max

j =k |G j,k | 1 3βs
,

where s 1 is an integer and β > 1 is a constant.

This assumption is stronger than Assumption 1. We have indeed the following Lemma (cf. Lemma 2 in [START_REF] Lounici | Sup norm convergence and sign concentration property of the Lasso and Dantzig estimators[END_REF]). Lemma 6. Let Assumption 5 be satisfied. Then

ζ(s) △ = min J⊂{1,••• ,M},|J| s min ∆ =0:|∆ J c |1 |∆J |1 f ∆ |∆ J | 2 1 - 1 β > 0.
Note that Assumption 5 the vector θ * satisfying ( 20) such that M (θ * ) s is unique. Consider indeed two vectors θ 1 and θ 2 satisfying (20) such that M (θ 1 ) s and M (θ 2 ) s. Denote θ = θ 1θ 2 and J = J(θ 1 ) ∪ J(θ 2 ). Clearly we have f θ (X) = 0 a.s. and M (θ) 2s. Assume that θ 1 and θ 2 are distinct. Then,

f θ 2 2 |θ| 2 2 = 1 + θ T (G -I M )θ |θ| 2 2 1 - 1 3βs M i,j=1 |θ i ||θ j | |θ| 2 2 1 - 1 3β > 0,
where we have used the Cauchy-Schwarz inequality. This contradicts the fact that f θ (X) = 0 a.s.

For the linear regression model, the Hessian matrix Ψ at point θ is

Ψ(θ) = E(1I |f θ * -θ (X)+W | 2K+α f j (X)f k (X)) 1 j,k M . We observe that Ψ(θ * ) = P(|W | 2K + α)G.
Thus Ψ(θ * ) satisfies a condition similar to Assumption 4 but with a different constant if

P(|W | 2K + α) > 0. The empirical Hessian matrix Ψ at point θ ∈ R M is defined by Ψj,k (θ) = 1 n n i=1 1I |f θ * -θ (Xi)+Wi| 2K+α f j (X i )f k (X i ), 1 j, k M.
We will prove that the empirical Hessian matrix Ψ(θ) satisfies a mutual coherence condition for any θ in a small neighborhood of θ * under some additional assumptions given below.

First, we need an additional mild assumption on the noise. Assumption 6. There c.d.f. F W of W is Lipschitz continuous.

This assumption is satisfied, e.g., if W admits a bounded density so we allow heavy tailed distributions such as the Cauchy. In the sequel we assume w.l.o.g. that the Lipschitz constant of F W equals 1.

We impose a restriction on the sparsity s.

Assumption 7. The sparsity s satisfies s

1 √ r .
This implies that we can recover the sparse vectors with at most O (n/ log M )

1/4 nonzero components. Define V η = {θ ∈ Θ : |θ -θ * | 1 η} where η = C 1 rs and C 1 = 8(1 + 2K)β P(|W | α)(β -1) + 1 6 . ( 25
)
Consider the event

E = sup 1 j,k M,θ∈Vη Ψj,k (θ) -Ψ j,k (θ) 8L 3 η + 4Lr + C 2 √ ns 2 , (26)
where

C 2 = 2 1 + (1 + L 2 ) 8C 1 L 3 + 4L s + 1 + L 2 3 .
We have the following intermediate result.

Lemma 7. Let Assumptions 2-6 be satisfied. Then P(E) 1exp(-√ log M ).

Proof. Define the variable

Z = sup 1 j,k M, θ∈Vη Ψj,k (θ) -Ψ j,k (θ) .
Applying the Bousquet concentration inequality (cf. Theorem 4 in Section 6) with the constants c = (1 + L 2 )/n, σ 2 = 2/n 2 and x = √ n s 2 yields that, with probability at least 1e -x ,

Z E (Z) + 2 √ ns 1 + (1 + L 2 )E (Z) + 1 + L 2 3 √ ns 2 . ( 27
)
We study now the quantity E(Z). A standard symmetrization and contraction argument yields

E(Z) 2E sup 1 j,k M, θ∈Vη 1 n n i=1 ǫ i 1I |f θ * -θ (Xi)+Wi| 2K+α f j (X i )f k (X i ) 2E 1 n n i=1 ǫ i 1I |Wi| 2K+α f j (X i )f k (X i ) + 2E sup 1 j,k M, θ∈Vη 1 n n i=1 ǫ i (1I |f θ * -θ (Xi)+Wi| 2K+α -1I |Wi| 2K+α )f j (X i )f k (X i ) . (28)
Denote by (I) and (II) respectively the first term and the second term on the right hand side of the above expression. The contraction principle yields (I) 4E max

1 j,k M 1 n n i=1 ǫ i f j (X i )f k (X i ) . (29)
Then, similarly as in the proof of Lemma 2 we get

E max 1 j,k M 1 n n i=1 ǫ i f j (X i )f k (X i ) Lr.
Thus, for (II) we have

(II) 2L 2 E sup θ∈Vη 1 n n i=1 |1I |f∆(Xi)+Wi| 2K+α -1I |Wi| 2K+α | 2L 2 P (2K + α -Lη |W | 2K + α + Lη) 8L 3 η. ( 30
)
Assumptions 4 and 7 yield that s

n log M 1/4
. Combining ( 27)-(30) yields the result.

We need an additional technical assumption.

Assumption 8. We have

12L 3 η + Lr + C2 √ ns 2 P(|W | 2K+α) 2
. This is a mild assumption. It is indeed satisfied for n large enough if we assume that P(|W | 2K + α) > 0 since Assumption 6 implies that r → 0 as n → ∞.

We have the following result on the empirical Hessian matrix.

Lemma 8. Let Assumptions 2-8 be satisfied. Then, with probability at least 1exp(-√ log M ), for any θ ∈ V η , we have min

1 j M | Ψj,j (θ)| P(|W | 2K + α) 2 , max j =k | Ψj,k (θ)| C 3 s , ( 31
)
where

C 3 = 1 3β + 12L 3 C 1 + C2 √ ns .
Proof. For any θ in V η and any j, k in {1, . . . , M } we have

Ψ j,k (θ) -Ψ j,k (θ * ) = E (1I |f∆(X)+W | 2K+α -1I |W | 2K+α )f j (X)f k (X) , where ∆ = θ -θ * . Then |Ψ j,k (θ) -Ψ j,k (θ * )| L 2 E |1I |f∆(X)+W | 2K+α -1I |W | 2K+α | L 2 P (|W | 2K + α , |f ∆ (X) + W | > 2K + α) + L 2 P (|W | > 2K + α , |f ∆ (X) + W | 2K + α) . Recall that |f ∆ (X)| Lη. Then |Ψ j,k (θ) -Ψ j,k (θ * )| L 2 P (2K + α -Lη |W | 2K + α + Lη) 2L 2 P (2K + α -Lη W 2K + α + Lη) 4L 3 η, (32)
where we have used the fact that the distribution of W is symmetric w.r.t. 0 in the second line and Assumption 6 in the last line. Lemma 7 and (32) yield that, on the event E, for any θ ∈ V η , min

1 j M Ψj,j (θ) P(|W | 2K + α) -12L 3 η - C 2 √ ns 2 ,
and max

j =k |Ψ j,k (θ)| C 3 s .
Now we can derive the optimal sup-norm convergence rate of the Dantzig estimators.

Theorem 2. Let Assumptions 2-8 be satisfied. If M (θ * ) s, then, on an event of probability at least

1 -M -1 -M -K -exp(- √ log M ) -3M -2K log n log M , we have sup θ∈ Θ | θ -θ * | ∞ C 4 r, where r is defined in Theorem 1, C 4 = 4 + 2C 1 C 3 P(|W | 2K + α) ,
with C 1 and C 3 defined respectively in [START_REF] Wainwright | Sharp thresholds for noisy and high-dimensional recovery of sparsity using l 1 -constrained quadratic programming[END_REF] and Lemma 8.

Proof. For any θ in Θ we have

∇R n ( θ) -∇R n (θ * ) = 1 0 Ψ(θ * + t∆)dt ∆,
where ∆ = θθ * . The definition of our estimator, Lemma 3 and Corollary 1 yield that, on an event A 1 of probability at least 1 -M -1exp(-√ log M ) -3M -2K log n log M , we have that θ ∈ V η and

1 0 Ψ(θ * + t∆)dt ∆ ∞ 2r.
Lemma 8 yields that, on the event A 1 ∩ E,

P(|W | 2K + α) 2 |∆| ∞ 2r + C 3 s |∆| 1 , so that |∆| ∞ C 4 r.
Note that Theorem 2 holds true for the Lasso estimators (2) with exactly the same proof, provided that a result similar to Theorem 1 is valid for the Lasso estimators. This is in fact the case (cf. [START_REF] Van Der Geer | High dimensional generalized linear models and the Lasso[END_REF][START_REF] Koltchinskii | Dantzig selector and sparsity oracle inequalities[END_REF]).

Sign concentration property

Now we study the sign concentration property of the Dantzig estimators. We need an additional assumption on the magnitude of the nonzero components of θ * . Assumption 9. We have

ρ ∆ = min j∈J(θ * ) |θ * j | > 2C 4 r,
where r is defined in Theorem 1 and C 4 is defined in Theorem 2.

We can find similar assumptions on ρ in the work on sign consistency of the Lasso estimator mentioned above. More precisely, the lower bound on ρ is of the order (s(log M )/n) 1/4 in [START_REF] Meinshausen | Lasso-type recovery of sparse representations for high-dimensional data[END_REF], n -δ/2 with 0 < δ < 1 in [START_REF] Wainwright | Sharp thresholds for noisy and high-dimensional recovery of sparsity using l 1 -constrained quadratic programming[END_REF][START_REF] Zhao | On model selection consistency of Lasso[END_REF], (log M n)/n in [START_REF] Bunea | Consistent selection via the Lasso for high-dimensional approximating regression models[END_REF], s(log M )/n in [START_REF] Zhang | The sparsity and biais of the Lasso selection in high-dimensional linear regression[END_REF] and r in [START_REF] Lounici | Sup norm convergence and sign concentration property of the Lasso and Dantzig estimators[END_REF].

We introduce the following thresholded version of our estimator. For any θ ∈ Θ the associated thresholded estimator θ ∈ R M is defined by

θj = θj , if | θj | > C 4 r, 0 elsewhere.
Denote by Θ the set of all such θ. We have first the following non-asymptotic result that we call sign concentration property. Theorem 3 guarantees that the sign vector of every vector θ ∈ Θ coincides with that of θ * with probability close to one. j ) if j ∈ J(θ * ) on the event A. If j ∈ J(θ * ), sign(θ * j ) = 0 and θj = 0 on A, so that sign( θj ) = 0. The same reasoning holds true simultaneously for all θ ∈ Θ on the event A. Thus, we get the result.

Appendix

We recall here some well-known results of the theory of empirical processes.

Theorem 4 (Bousquet's version of Talagrand's concentration inequality [START_REF] Bousquet | A Bennet concentration inequality and its application to suprema of empirical processes[END_REF]). Let X i be independent variables in X distributed according to P , and F be a set of functions from X to R such that E(f (X)) = 0, f ∞ c and f 2 σ 2 for any f ∈ F. Let Z = sup f ∈F n i=1 f (X i ). Then with probability 1e -x , it holds that Z E(Z) + 2x(nσ 2 + 2cE(Z)) + cx 3 .

Theorem 5 (Symmetrization theorem [START_REF] Van Der Vaart | Weak Convergence and Empirical Processes: With Applications to Statistics[END_REF], p. 108). Let X 1 , . . . , X n be independent random variables with values in X , and let ǫ 1 , . . . , ǫ n be a Rademacher sequence independent of X 1 , . . . , X n . Let F ba a class of real-valued functions on X . Then

E sup f ∈F n i=1 (f (X i ) -E(f (X i ))) 2E sup f ∈F n i=1 ǫ i f (X i ) .
Theorem 6 (Contraction theorem [START_REF] Ledoux | Probability in Banach spaces: Isoperimetry and Processes[END_REF], p. 95). . Let x 1 , . . . , x n be nonrandom elements of X , and let F be a class of real-valued functions on X . Consider Lipschitz functions γ i :→ R, that is,

|γ i (s) -γ i (s ′ )| |s -s ′ |, ∀s, s ′ ∈ R.
Let ǫ 1 , . . . , ǫ n be a Rademacher sequence. Then for any function f * : X → R, we have

E sup f ∈F n i=1 ǫ i (γ i (f (x i )) -γ i (f * (x i ))) 2E sup f ∈F n i=1
ǫ i ((f (x i )f * (x i )) .

1 the

 1 complement J c of J. For any integers 1 d, p < ∞ and w = (w 1 , . . . , w d ) ∈ R d , the l p norm of the vector w is denoted by |w| p 1 j d |w j |. Consider a function γ : Y × R → R + such that for any y in Y and u, u ′ in R we have |γ(y, u)γ(y, u ′ )| |uu ′ |.

Theorem 3 .

 3 Let Assumptions 2 and 5-9 be satisfied. If M (θ * ) s, thenP sign( θ) = sign(θ * ), ∀ θ ∈ Θ 1 -M -1 -M -Kexp(log M ) -3M -2K log n log M .

Proof.

  Theorem 2 yields sup θ∈ Θ | θθ * | ∞ C 3 r on an event A of probability at least 1 -6M -1 . Take θ ∈ Θ. For j ∈ J(θ * ) c , we have θ * j = 0, and | θj | c 2 r on A. For j ∈ J(θ * ), we have |θ * j | 2C 3 r and |θ * j | -| θj | |θ * j -θC j | C 3 r on A. Since we assume that ρ > 2C 3 , we have on A that | θj | > c 2 r. Thus on the event A we have: j ∈ J(θ * ) ⇔ | θj | > c 2 r. This yields sign( θj ) = sign( θj ) = sign(θ *

Acknowledgements: I wish to thank Pr. Alexandre Tsybakov for his useful advices.


Dr Marie-Claude Simeone-Senelle

Abdallah Ghanem

Said Abdallatif Saad Amer

Ali Suleyman

Keywords:

Together with the other Modern South Arabian languages, Soqotri is related to the most ancient languages spoken in the Arabian peninsula. The study of Soqotri dialects has allowed to confirm or infirm many hypotheses concerning the evolution of the Semitic languages, and it has underlined the originality of Soqotri within the Modern South Arabian set. Moreover, the study of the dialectal situation, and its development are relevant to evaluate the degree of liveliness of the language today. First, I shall present a brief overview of the sociolinguistic situation on the island of Soqotra, and the geographic distribution of the different Soqotri dialects. Then, in the light of data collected during my surveys (1985)(1986)(1987)(1988)(1989)(1990)(1991)(1992)(1993)(1994)(1995)(1996)(1997)(1998)(1999)(2000)(2001) on the island, I shall try to describe the process of the erasing of dialectal characteristics, not only in vocabulary, but in phonology, morphology, and syntax. Even though Soqotri people still speak in Soqotri to each other, their language is affected by contacts with Arabic. Only some women and old men, in remote settlements, keep the use of their original dialectal variety. Because this process speeded up during the last years, Soqotri must be considered as an endangered language. The developing strategy of the Soqotra Archipelago needs also to include the language which is the means of passing on to future generations the traditions, arts and technics. It is a matter of urgency to go on collecting more linguistic data concerning Soqotri, to enrich the corpus of traditional literature, to set up technical lexicons, in order to save a part of the Human patrimony in Southern Arabia.

M.-Cl. SIMEONE-SENELLE Soqotri Dialectology (Aden, Dec. 2003) 2

Data and acknowledgements

The data quoted without author's name have been collected during my surveys on the Soqotri language, on the island of Soqotra (and for few of them on the mainland, in Aden and in the Hadramawt). I want to express my sincere gratitude to the Yemenite authorities, and specially to the Universty of Aden, for having given a very efficient assistance and support to my work, since 1985.

Introduction

Soqotri, with Mehri, Hobyot, Harsusi, Bathari, and Jibbali, belongs to the Modern South Arabian languages (= MSAL). Nowadays these languages are spoken in the Republic of Yemen and in the sultanate of Oman; they are related to the Southern branch of Western Semitic, as the Semitic languages of the Horn of Africa (spoken in Eritrea and Ethiopia). They are unwritten languages, related to the pre-islamic languages spoken in the Arabian Peninsula, and to the so-called Epigraphic South Arabian (= ESA), the carved languages on the monuments of the ancient kingdoms of Arabia Felix. However, the degree of relationship between the former (modern and unwritten languages) and the latter remains to date a matter of discussion. We ignore if the ancient written languages correspond to the languages spoken in the past, during the same period. From a linguistic point of view, concerning the structure of the language, the MSAL are closer to the Afro-Semitic languages than to Arabic (Central Semitic). Despite historical contacts and a common culture, there is no mutual understanding between native speakers of Arabic and native speakers of any MSAL. Moreover, within the MSAL group, there is no mutual understanding between the native speakers of different Modern South Arabian mother tongues, and Arabic is the language of communication, used as a lingua franca. Among the six MSAL, Soqotri is set apart, and not only for linguistic reasons. Soqotri was the first MSAL discovered in 1834, 170 years ago. It is the only MSAL to be spoken exclusively on islands (Soqotra, Abd-al-Kuri, Samha) 1 . These islands are geographically nearer to Africa than to the Arabian coast, where other MSAL are spoken. In the past, the famous island was very isolated because of its location, its exposition to the two monsoons and the resulting rough sea for five months of the year, and the lack of safe bays. Because of the very hard living conditions on the island, many attempts of occupation came to a sudden end, and only the northern coast was concerned. The Haghier Central range, culminating at 1525 m., protected the inland. In the past, there was no pervasive contact with other populations and languages on the island. The influence of Arabic is recent, and only part of the population, mainly inhabitants of Hadibo and its area were concerned. It follows that, up to the modern period, the Soqotri language underwent a specific internal development, without sizeable external influences. On the mainland, in Yemen and in Oman, for a very long period, each of the five MSAL has been in contact with another MSAL and with Arabic. Such a situation influenced the evolution of the concerned languages. Unlike the other MSAL, the Soqotri language has remained isolated for many centuries. The language preserved many linguistic features which disappeared from the other MSAL. The study of Soqotri allows us to know the MSAL group better, its place within Southern Semitic, and its relationship to Semitic as a whole, particularly to the ESA languages. Moreover, any language is the reflection of the culture of its native speakers and the means of passing on to future generations their traditions, arts and technics. It is thus quite logical that the developing strategy of the Soqotra Archipelago needs to take into account the language of the natives, and its dialects.

Dialectology

The study of dialects is a way to know better the internal structure of a language and its evolution. It may explain some obscure linguistic features of other languages within the same group, or the same family. The diversity of Soqotri dialectology is surprisingly high when one considers the surface of the island (3625 km2 ), and the number of inhabitants (44.000) 2 . The topography of the island, and the way of life of inhabitants have favoured the linguistic diversity. The Soqotri dialectology is very rich. In some parts of the island, particularly in the remote places like in the Haghier range, the area of Diksam, Ras Sha'ab, etc., the inhabitants have had minimal contacts with the capital Hadibo and with the outside world. In rural areas, the speakers have preserved exclusive linguistic features. The situation is changing very fast, mainly due to the contacts with Arabic. Whereas Soqotri is not the less investigated language of the MSAL, its very rich dialectology is hardly studied. It is urgent to carry on a research in this domain, to collect data on all the island and on Abd-al-Kuri, and save the language and the culture of which it bears witness.

Study of Soqotri and its dialects, the state of the art.

The situation of Soqotri in the nineteenth century

The first data on Soqotri were collected by James Raimond Wellstedt during his survey on and around Soqotra, from January, 10 to March, 7, 1834. They were published in 1835. Wellstedt collected toponyms, some tribe names, plant names, figures, but overall,

[he] "subjoined a copious vocabulary of words in general use among the Bedouins, by which I trust the scholar may be able to proceed in an inquiry that can scarcely fail to lead to most interesting results" (Wellstedt,Report: 155,Memoir: 211) This list of 195 items and expressions in the Report (March 1835) was extended to 236 items in the Memoir (April & May 1835). The words are given in Soqotri (in Arabic alphabet, and in Latin transliteration), with Arabic and English translations. 3 It is very difficult to determine the exact origin of the data. Wellstedt surveyed the coasts and the interior of the island (cf. the map published at the end of the Memoir), but he neither specified from whom, nor from where he collected his data. We know that he was working with two guides: Hamed, who had a house in Tamarida (Hadibo), and Suleyman Muscaty who knew very well the tracks inside the island, and could communicate with the Bedouins; maybe, he helped to collect and to translate the vocabulary. Nothing is said about the mother tongue of these guides and language assistants. We guess only that they were able to speak Arabic, Soqotri and maybe English. Wellstedt (Report: 155, Memoir: 211) notes that :

"The Socotran language is in general use even by those who permanently settled on the island ; and Arabic is only spoken by the merchants when transacting business with the traders who arrive in their buggalows" He specifies (Memoir: 214): His classification is not linguistic, and in the same paragraph, he adds that the 'Socotran Arabs', settled here, "have adopted the same language and customs" (as Socotran socalled Bedouins). The vocabulary of the word-list was probably collected or corrected with the same informant. The words have no characteristics of the western dialects (absence of velar fricatives (P and x): ¿éyj and not Payj 'man', Hararhen and not xárhen 'a little'). Palatalization of /g/ occurs in some examples, as in some dialects from Haghier or Diksam: yirbóK for /gÉrbaK, girbaK/ 'savage cat'; jemíher for /gémhel/ 'camels'..., but it is also a characteristic feature of some Arabic dialects, as in Hadramawt (maybe the mother tongue of the translator?). No variant is given by Wellstedt. 41 words out of 236 were noted as Arabic loans by Wellstedt. Some are really Arabic as beïdh (bayD) 'eggs' (Kehélihen in Soqotri) or ¿ajúz 'old woman' (Soqotri Jíbìb), thob (Fob) 'a shirt' (with interdental, absent from the Soqotri consonant system; tob in Soqotri means 'cloth'); many words belong to the old common Semitic vocabulary and are attested in both Arabic and Soqotri: edahn 'ears' (exactly ?ídÊhen), ?aSábi¿ 'fingers' (?ÊSÂbe¿) etc. The contact and influence of Arabic in the main coastal villages is obvious; however these examples could tend to prove that the informant's mother-tongue was an Arabic dialect and not Soqotri. Unfortunately all the data give us but very few information on the real linguistic situation on the island.

The end of the nineteenth century and the early twentieth century

The historical turning point for the knowledge of the MSAL is the Südarabische Expedition of the Viennese Imperial Academy. 1898 is the beginning of the linguistic research on Mehri, Šxawri (a dialect of Jibbali, a language spoken in Oman), and Soqotri. The Viennese scientists began to collect, transcribe, comment, and translate literary texts. Concerning Soqotri, David-Heinrich Müller recorded texts on the island (during a survey in the Haghier (in Aduno pass), and on the Gottfried, the ship of the Expedition, then in Austria. Müller (1905: vii) announces that the texts gathered in the second volume of Soqotritext come from the western region of the island, while those of the first volume (1902) were from the eastern region. In the first volume, the texts were collected with six informants. For four of them, he specifies where they are born or living (1902: vii): one is from Qalansiya and his mother is 'a Bedouin from the mountain', one is from Abd-al-Kuri, and he translated into his dialect the tale der Lebensbrunnen, another is the qadi of Hawlaf, and he gave to Müller many proverbs and poems in 'the dialect of the Bedouins of the Mountain', finally some poems were dictated by a 'Negro from Tamarida'. A young informant whose the origin we ignore translated some excerpts of the Bible and gave him variants of some texts collected with other speakers. A trader, 'living the half of the year in Zanzibar', has aboarded the Gottfried at Pubbet-¸o¿ob for five weeks, and checked some texts. The whole collection of the second volume, is in fact based on one idiolect, because it was gathered from a single informant ¿Ali b. ¿Amer en-NubhÂni. He went with the scientist to Vienna where he stayed for six months (May-December 1902). Müller in the presentation of his informant (1905:viii) does not mention his place of origin, but in the description of the geography of the island (1905: 369), this speaker (l. 27-31) reports that he was born in Kâm (like his father and grandfather), and after their parents' death, he went to Dibeni: both neighbouring villages are situated on the northern coast, some kilometres away to the East of Hawlef. In the two volumes, many dialectal variants are mentioned, without precise localization. They are recorded in the Lexique Soqotri [START_REF] Leslau | Lexique soqoTri (sudarabique moderne) avec comparaisons et explications étymologiques[END_REF] and taken in account by Bittner (1913Bittner ( -1918) ) and Wagner (1953[START_REF] Wagner | Der Dialekt von 'Abd-el-KUrì[END_REF] in their phonetic and grammatical studies. At this stage, following Müller, two dialectal groups are distinguished on the northern coast: the western and oriental dialects. The dialect of Abd-al-Kuri was set apart: it is very different from the other Soqotri dialects in phonetics, morphology, and syntax (cf. the Soqotri text with its translation into the dialect of Abd-al-Kuri, in Müller, 1902: 92-111), and this originality is confirmed by Naumkin (1988: 343) and by the French Linguistic Mission (Simeone-Senelle 1997: 380, 414). This variety of Soqotri is influenced by Hadrami Arabic, because of the regular trading of the Abd-al-Kuri fishermen with Hadramawt (QuSa¿ir area).

In the second mid of the 20 th century

Johnstone published some articles on the phonology and morphology of Soqotri, and he annotated his personal Lexique Soqotri with many lexical variants (essentially from Hadibo, Qalansiya, Qadhub). As a matter of fact, from the second half of the 20 th century, and particularly after the 70', new places were investigated on the island. The new collected data and the works by Naumkin, Porkhomovsky, and the French Mission highlighted a more complex and diversified dialectology. Naumkin undertook fieldworks almost everywhere in the island (and in Abd-al-Kuri), and he worked with informants from the Haghier, particularly from the Di¿rho valley, and the villages of Dirismoyten and ¿Abub; in the region of Diksam (mountainous area adjacent to the western Haghier), in the villages of Hagefeno, Dirhemeten; in the ¿Abalhon valley, in the western part of Diksam. Unfortunately, the origin of the informants or of the data are not always specified, but the linguistic commentaries, following the transcribed and translated Soqotri text, are very precious for the evaluation of Soqotri dialectology. The French Mission4 , from 1985 to 1991, collected data on the Southern coast, in Noged, on the Northern coast in Qadhub, ˆadibo, Šiq, ¿Elha and ˆawlef, in the piedmont of ˆaghyer, in Ma¿nefo, in the Eastern region, in ras Mºmi, on the western coast, in Qalansiya. After 1991, I had the opportunity to enlarge the fieldwork and to collect new dialectal data: in J y o?, in the eastern part, and in the western part of Haghyer (area of Diksam), on the northern coast in the region of Mori, and again to Qadhub, for the recording new texts (tale and poems) and grammatical data. In 1996 and 2001, many data were also recorded in Hadibo, but from different dialects with informants from the town, from Ša¿b (¬ y ¿ab), on the western coast, and from Hendak (ˆendaK) in Noged area. The main purpose of this collection is to compare the Soqotri dialects and to establish the dialectology of the island. Today, no specific study of this type has been carried out and my last survey (2001) pointed to the emergency of such a study, because the process of linguistic change appeared faster than expected few years ago.

Main results of the last dialectal surveys

As in all languages spoken in the world, the research on newly surveyed dialects provides important informations about the evolution of the language. This observation can be checked in Soqotri. Only some results, among the most salient, are presented. Phonology and Phonetic -An exclusive and typical feature of Soqotri is the occurrence of a non-etymological and non-morphological h (in nouns and very rarely in verbs), called parasite h. This phenomenon may explain the parasite h attested in Minean, an ancient (epigraphic) South Arabian language. It is related to two phonetic traits of Soqotri: the rules of stress5 with a particular evolution for original long vowels, and the particular consonantal articulation (with the vocal cords apart at one end), called murmur or breathy voice, resulting in a [¦] or a full /h/. This feature is confirmed by the data collected in all the surveyed dialects: Qadhub SalÉlhIn/ SalÍlihOn 'small valley, small stream'; Hadibo líbÈhOn 'white', Zeriq (Haghyer) Ká¿Ir / Ka¿Íri 'house (sg. / dual)', but plural Ka¿ÍhIr. The same speaker says (in Meyhihe): ¿a'EtÊn or ¿a'éhÈtÊn 'women', but in Hendaq (Noged) only ¿a'éhtÊn is recorded.

-The research in the far west part of Soqotra [START_REF] Naumkin | Ocerki po etnolingvistike sokotry [Essays on Ethnolinguistics of Socotra[END_REF], Simeone-Senelle, 1997) revealed phonological features, which lead to the reappraisal of some conclusion concerning the original consonant system of the ancient Semitic: the first assumptions were based on dialects studied before 1980. Now, it may be assumed that the merging of the velar fricatives /x/ and /ª/ with the pharyngeals /©/ and /º/ is particular to some dialects only; in other dialects the velar fricatives do occur, even in native words:

Qalansiya xoemÊh (Qadhub HÎmeh) 'five'; Qalansiya PayG (Hadibo ¿IyG) 'man'. A new feature, never attested before, was noted in my data collected in the area of Diksam in 2001. It points to the predominant unstable status of the pharyngeals in some Soqotri dialects. The initial /¿/ is articulated as a laryngeal [h], and /H/ > ø:

Diksam hayG 'man'; h'Êh 'woman'; ArírhOn (for HarírhÊn) 'a little'.

-The spirantization or affrication is a very widespread phonetic feature in many dialects, and not only in Hadibo (as already noted by the specialists). Some examples of spirantization: éfo >éBo (cf. Simeone: 1991, Lonnet et Simeone: 1997) in Hadibo; rUGed >rUyed 'name of a village', iGodiHen > iyodiHen 'he comes' in Diksam area (Rujed). In many dialects, included in Haghyer (Zeriq) and Diksam (ˆiloho), one says megÂ¸Ê 'boys', but mÊ'º¸e in J y o', and miyº¸e in Rujed. This phenomenon explains the following shifts: ¿ > h, H > ø (cf. above), and b >ø in intervocalic position: ¿eGík for /¿eGíbÈk/ 'I/you (m.sg.) want(ed)'; ¿eGékÊn for /¿eGébÈkÊn/ 'you (pl.) want(ed)' .

The form ¿ik 'you (m.sg.) want', in many dialects, is an example of the outcome of this process of spirantization, from /¿eGibÈk/ to the ultimate stage ¿ìk or ¿i¢, as in Rujed. We have no attestation of intermediate stages of this process. In Rujed, there are minimal morphematic pairs, with the opposition ¿iG (1 rst sg.) 'I want(ed)' vs ¿i¢ 'you (m.sg.) want(ed)', vs ¿i¸ 'she wants/wanted'.

/l/ > • (also transcribed "): this realisation occurs almost systematically in every dialect for words such as • Ot 'when, if', and, at the beginning of some verbs, with the negation /al/ > A• /O• (with modification of the vocalic timbre: /a/>A/O). This lateralisation and weakening of /l/ may be a morphophonogical explanation for the different negative forms; in some dialects, the loss of l could depend on the initial phoneme of the verb, and not on the verbal mode (indicative vs prohibitive). So, in these dialects, there would be only one negative form, with two combinatory/contextual variants: -Weakening of the nasal final consonant: ¸i-sen > si-sÈ 'with them (f.pl.)' (this phenomenon is recorded in other MSAL, for example in Hobyot).

-Dissimilation of the palateo-alveolar ¸(i)-('with'), when the suffix pronoun is f. (sg. and pl.), -s/-sen: ¸is > sis 'with her' (= Müller III, 64, 26, dialect from the northern coast, east of Hawlef); ¸isÊn >sisÊn/si-sÈ 'with them (f.)' (cf. ¸é¸in in Müller II, 56, 19, in the same dialect of the eastern area of ˆawlef ).

-Assimilation of the dentals (the voiced dental becomes voiceless): d-> t-+ pron. 2dual / 2pl., in the possessive construction: di-ho KA¿R <of-I/ house> 'my house', but t-ti < /d-ti/ 'your (dual)', t-ten 'your (pl.)'.

-The authors have noted the devoicing of the final /¿/, cf. fezaH for feza¿ 'much, many'. In the dialect of ˆandaq (Noged), I noted that the same devoicing occurs also inside the word, in a consonantic cluster: Ko¿ároh 'small house', but plural KoHrEtÊn.

Morphology -Independent Pronouns

It is confirmed that the independent personal pronouns for the 2 nd person singular, E (m.) and ì (f.), are more widespread than het and hit (cf. Leslau 1938: 48). In my data, het and hit are specific to some dialects spoken in the area of Diksam, and in the farwestern area (Qalansiya, Qafiz). In other places, the 2 nd singular, m. and f., are E and ì, and we note that, in the latter system, the subject pronouns are at the full form (with the suffix -hOn/hen/hin).

-

Connective particle

Another morphological particularity in the far-western dialect of Qafiz is the possessive construction. It is based, as in all Soqotri dialects, on the connective d-, followed by a pronoun, but in this dialect, the connective is variable (like the relative pronoun): dwith a singular, and lwith a plural: dihet férham <of-pr.2msg./ girl> 'your(msg.) girl', des 'her'..., but lHan, 'our', ltan 'your (pl.)', lyihan 'their (m.)', lisan 'their (f.)'.

This variation highlight the link between connective, deictic and relative pronoun. In other dialects, a grammaticalization process took place and the singular form was frozen as a connecting invariable particle d-.

-Nominal dual

The nominal dual -in, instead of -i6 is a specific feature to a 15 year old boy7 from Diksam. It maybe due to his idiolect, but the link with classical Arabic dual is interesting: Êsbá¿in 'two fingers'; ba¿írin 'two camels'; Êsáfirºtin 'two birds'; mÊk¸Âmin 'two boys'; but with colour names: ¿aféri 'red (dual)'; HÂri 'black (dual)'.

Syntax -Agreement

In some dialects, the relative pronoun does not agree with plural: le-Ÿfoe d-ize¿em bÈfédÊhOn <deictic(pl.)-people/ rel.(sg)-they stay/ in-mountain> 'this people who stays in the mountain' (Rujed). In remote places, old people use the verbal, nominal and pronominal dual:

eTáyherö ho-w-d-eh KaKa Kalansíye <we go (1dual)/I-and-of-me/ brother/ Qalansiya> 'I and my brother, we go to Qalansiya', but many native speakers (young people or people in contact with Arabic) do not use verbal dual regularly:

¿eGébö tÊThár (for tÊThárö) <they want (3dual)/ go (subj. 3f.sg.) > 'They (both) want to go', and they use plural pronouns instead of the dual form:

tten férhem <of-your (pl.)/girl>'your girl' for /tti férhem/ 'your girl' (to you both).

Many people in contact with Arabic tend to use plural in all cases (verb or pronoun).

Only the nominal dual occurs regularly.

-Negation Cf. above, about the phono-morphological explanation for the two forms of negation. In many dialects, the verbal negation is the same with indicative and prohibitive.

The present dialectal and sociolinguistic situation

Since the unification of Yemen (1990), the island has considerably developed, essentially the northern coast with a new airport, a new road from this modern airport to ˆadibo, a wharf in ˆawlef, and, in ˆadibo, many buildings (public and private) with a Telephone Center, a new market, new schools, hotels, the new Soqotra Conservation Project building etc. The island is opened to the outside world. The increasing number of four-wheel cars makes the contact with the inland easier. The development of contacts inside and outside the island, the progress of schooling in Arabic, all these factors of modernisation have influenced, and changed the linguistic landscape of the island. The change is spectacular. Today, the situation described in 1996 (Simeone-Senelle, 1997: 310) has to be reappraised and updated. The noticeable differences in the new data allowed to distinguish six dialectal groups on Soqotra.

Two groups on the northern coast:

1) The urban dialect of the capital ˆadibo, where the permanent contacts are increasing between Soqotri and other Yemenite citizens (Arabic or Mehri native speakers) or foreigners from Oman, Saudia Arabia, Africa. Arabic is the language of trading and communication in this town which was a big village only ten years ago. Many villagers or Bedouins, from coastal area and from ˆaghier, come regularly there to sell their products (cattle, dates, aloe, pottery, ...).

From the numerous texts collected in the dialect of ˆadibo since the beginning of the studies on the Soqotri language, it can be shown that the dialect is unstable because of the contacts between native speakers of different Soqotri dialects and Arabic. It would be interesting to describe the Soqotri variety used in this contact situation, and to evaluate its influence on the variety spoken by Soqotri natives from ˆadibo.

2) The second group includes the dialects of the villages of the northern plain, near the capital-city. Some villages are inhabited by fishermen and some palm-date farmers, as in the Eastern part, in Šiq and ˆawlef, and in the western part, in Qadhub. ¿Elha (a few kilometres to the south-east of ˆadibo), where people are living on date-palms and market gardening, may be included in this group. Many texts were collected in Qadhub, but data from other places are limited. The dialect of Qadhub is characterised by many lexical archaisms. The old people have preserved some pieces of traditional and ancient literature. Only religious poems show the influence of Arabic with many borrowings from classical Arabic vocabulary and Coranic expressions. Then,

3) The mountain dialects, in the range of ˆaghyer, and in Diksam. These regions are not easy to reach. The people are living in villages, moving around in the same area, depending on the season (rain, wind); sometimes, they are living temporarily in caves.

They are shepherds and cultivate some date-palms. In the past, they collected the resin of Dragon's-blood and sold it in ˆadibo. The contacts with the coast are occasional, and only men are going to ˆadibo. Many old people and women do not speak Arabic, some have a passive and approximate understanding of this language. Their dialect is famed as not being understood by other Soqotri speakers. In fact these dialects show many specific and original features.

4) The rural dialects of the eastern region, in Momi. The texts are relatively rare. The people are living essentially on date-palms, millet and they breed some cattle. In part of this area, they produce lime. This dialect has not been the subject of any specific studies.

5) The rural dialects of the western coast, in the Qalansiya area. The detailed study of the dialect of the village of Qalansiya by the French Mission revealed linguistic features unknown and unsuspected in Soqotri. These results (confirmed by my survey in 2001) contributed undoubtedly to a better knowledge of Soqotri and of the Semitic family as a whole. (Simeone-Senelle 1997, Lonnet and Simeone-Senelle 1997). The whole area has to be investigated more intensively.

6) The Southern coastal dialects of Noged. The villages are scattered in the isolated and barren plain. The majority of the inhabitants are fishermen. This area has not been much investigated. The few linguistic data collected show interesting characteristics different from the other dialects (cf. above): it is essential to carry on the recording of literary texts and discourse, in order to undertake an accurate description of these dialects.

7) On the two islets, Abd-al-Kuri and Samha.

The data are rare for the dialect of Abd-al-Kuri. One long text was spelled to Müller, the translation of a tale; the edition on the same page of the two versions (Soqotri from Soqotra and in the dialect of Abd-al-Kuri) makes the comparison easy (Müller, 1902: 91-111). Naumkin collected some short pieces of poetry, during his 1985' survey, each word is clear and understood, but the general meaning is obscure [START_REF] Naumkin | Sokotrijcy, istoriko-etnograficekij ocerk [The Socotrans: A Historical and ethnographical Study[END_REF](Naumkin, : 271, 1993: 354): 354). Few lexical, and grammatical data were recorded by the French Mission in 1989, in the Hadramawt (cf. Simeone-Senelle 1994), but no text. According to Naumkin (1988: 343, 344), the dialect of Abd-al-Kuri, 'does not come from any of the subdialects that are widespread on Socotra', whereas the dialect of Sam©a, belongs to the western dialects of Soqotra. Nothing was collected and edited about the dialect of this islet.

Evolution of the situation

In a short period of 16 years, from my first survey on the island in 1985 until the last one in 2001, I have noted important changes in the linguistic situation. The progress of Arabic is obvious, and it was speed up after the 1990-s. It is related to schooling, to modernisation and to the economic development of the island, without forgetting the role of television in ˆadibo and in villages like Qalansiya (many old women heard Arabic for the first time by looking at television).

The influence of Arabic is noticeable in the numeration system: seven years ago, Soqotri people, from the inland or remote places, used the Soqotri system of numeration from one to ten in commercial transactions with other Soqotri speakers in ˆadibo. But, in 2001 in ˆadibo, even old people used Arabic system, and it was very difficult to obtain the first ten numbers in Soqotri from young people. When they remember Soqotri, the syntax was often incorrect, and copied from Arabic. Many young people in the town borrow from Arabic, and code-switch with Arabic; they do not remember any piece of literature, they ignore the heroes of traditional texts, and they do not understand any poem.

Changes are not only due to the contact with Arabic. There are also the result of dialectal contacts, and it is related to a social phenomenon. Some (conservative) dialects spoken in remote places are said to be uncomprehensible or original. Native speakers, when they are dealing with speakers of other Soqotri dialects, tend to erase the originality, the characteristics of their speech. The specific features (phonetic, morphological, syntactic and lexical) are avoided. It would be very interesting to evaluate the degree of change (evolution and regression), to determine which domains are more stable or unstable in the dialects.

Concerning the present situation, there are two possibilities: a new variety of Soqotri will emerge from this contact situation or the Soqotri langage will not be spoken in big villages or town, like ˆadibo, and the scope of Soqotri will be narrowing to the remote inland places before extinction.

Conclusion

It is a matter of urgency to go on collecting more linguistic data by carrying on extensive and intensive linguistic surveys, to set up a linguistic atlas of Soqotra and of the two islets. At the same time, it is essential to enrich the corpus of traditional literature, and to set up technical lexicons. The knowledge of languages gives access to the culture (scientific, technical, literary, spiritual) of the native speakers, and it is part of the education of future generations, because of its pedagogical implications. It is well known that many problems in learning second language (Arabic for Soqotri speakers) can be avoided if teachers know the structure of the students' mother tongue. The Soqotri people are conscious of the value of their language, they know that it is a very important part of the Yemenite and Arabian patrimony. As fauna, flora, arts and technics, the Soqotri language belongs to the Human patrimony, and as such it must be saveguarded.

  "[...] I have preserved the name of Bedouin bestowed on the mountain-tribes, [...] I shall retain the name of Arabs, with which the remainder [...] have invested themselves. Under this designation, are included those who occupy Tamarida (= Hadibo), the villages of Cadhoop (= Qadhub) and Colesseah (= Qalansiya), and the greater part of the eastern portion of the island".

  ˆiloho: A-y ìte 'he does not eat'; O-ste 'don't eat!'; Ol ¿Ik lìte <neg./ I want/ I eat (subj.)>'I don't want to eat'. Compare with, in Mogar: Ol ¿ìk lÊfJE? 'I don't want to eat', Ol tsE! 'Don't eat!'. But, in Zeriq (Haghyer): A-t¸emtel! 'don't speak!' Al t¸ÊmÊtol toh 'you (m.sg.) don't speak with me'.

In Oman, a Jibbali dialect is spoken on the island of Kuria-Muria.

Estimation of SAMP (Socotra Archipelago Masterplan project), quoted p. 2 of the booklet Visitor Information.

The 236 words were re-edited with corrections and linguistic and ethnographic commentaries, bySimeone- Senelle (1991[START_REF] Testen | The Loss of the Person-marker t-in Jibbali and Socotri[END_REF].

The French Mission of Linguistic Survey on the MSAL spoken in Yemen included A. Lonnet and M-Cl. Simeone-Senelle, from 1985 to 1991, then from 1991 until now, Marie-Claude Simeone-Senelle alone.

Stress falls on the penultimate or antepenultimate syllable, in S. the unstressed vowel may be preserved by the h parasite.

Except in some words such as colours.

I must note that this young did not understand Arabic well,he did never go to school, and he stayed regularly in Hadibo for short periods.